Varghese George - Network Algorithmics

Second edition

George Varghese

UCLA Department of Computer Science, Los Angeles, CA, United States

Jun Xu

School of Computer Science, Georgia Institute of Technology, Atlanta, GA, United States

1. Tables in Chapter 5
2. Tables in Chapter 6
3. Tables in Chapter 7
4. Tables in Chapter 8
5. Tables in Chapter 9
6. Tables in Chapter 10
7. Tables in Chapter 11
8. Tables in Chapter 12
9. Tables in Chapter 13
10. Tables in Chapter 14
11. Tables in Chapter 15
12. Tables in Chapter 16
13. Tables in Chapter 17

1. Figures in Chapter 1
2. Figures in Chapter 2
3. Figures in Chapter 3
4. Figures in Chapter 4
5. Figures in Chapter 5
6. Figures in Chapter 6
7. Figures in Chapter 7
8. Figures in Chapter 8
9. Figures in Chapter 9
10. Figures in Chapter 10
11. Figures in Chapter 11
12. Figures in Chapter 12
13. Figures in Chapter 13
14. Figures in Chapter 14
15. Figures in Chapter 15
16. Figures in Chapter 16
17. Figures in Chapter 17
18. Figures in Chapter 18
19. Figures in Appendix A

Part 1: The rules of the game

Outline

Part 2: Playing with endnodes

Outline

Part 3: Playing with routers

Outline

Part 4: Endgame

Outline

Morgan Kaufmann is an imprint of Elsevier

50 Hampshire Street, 5th Floor, Cambridge, MA 02139, United States

Copyright 2022 Elsevier Inc. All rights reserved.

No part of this publication may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopying, recording, or any information storage and retrieval system, without permission in writing from the publisher. Details on how to seek permission, further information about the Publisher's permissions policies and our arrangements with organizations such as the Copyright Clearance Center and the Copyright Licensing Agency, can be found at our website: www.elsevier.com/permissions.

This book and the individual contributions contained in it are protected under copyright by the Publisher (other than as may be noted herein).

Notices

Knowledge and best practice in this field are constantly changing. As new research and experience broaden our understanding, changes in research methods, professional practices, or medical treatment may become necessary.

Practitioners and researchers must always rely on their own experience and knowledge in evaluating and using any information, methods, compounds, or experiments described herein. In using such information or methods they should be mindful of their own safety and the safety of others, including parties for whom they have a professional responsibility.

To the fullest extent of the law, neither the Publisher nor the authors, contributors, or editors, assume any liability for any injury and/or damage to persons or property as a matter of products liability, negligence or otherwise, or from any use or operation of any methods, products, instructions, or ideas contained in the material herein.

ISBN: 978-0-12-809927-8

For information on all Morgan Kaufmann and Elsevier publications visit our website at https://www.elsevier.com/books-and-journals

Publisher: Mara Conner

Editorial Project Manager: Lindsay C. Lawrence

Production Project Manager: Manchu Mohan

Cover Designer: Matthew Limbert

Typeset by VTeX

For Aju and Tim and Andrew, who made all this possible...

Unless otherwise stated, this preface is written by author Xu, who is referred to as I in the following. Author Varghese is referred to as George in the following.

When George invited me in 2015 to write the second edition and become a co-author of this legendary book, I felt both humbled and honored. I also felt a deep sense of mission, as the bulk of my research and teaching had been on network algorithmics since the mid-1990s and still is.

When I signed the new edition contract with the publisher, I was originally committed to significantly revising only three chapters: Chapter (Exact-match lookups).

I have made the following major revisions to Chapter (Clos networks for medium-size routers), I have added a few paragraphs describing how a 3-stage Clos network can be used for data center networking and switching.

I have made the following major revisions to Chapter , I have described two research proposals towards making packet scheduling reprogrammable in switches and routers.

I have made the following major revisions to Chapter , I provide a crash course on network data streaming and sketching (DSS). DSS, which originated first in the area of databases, has evolved over the past two decades into a booming research subtopic of network measurement and monitoring. For example, in the past decade or so, SIGCOMM and NSDI together accept several network DSS papers almost every year.

George has made significant updates to Chapters (Conclusions).

My work in writing this edition has been supported in part by US National Science Foundation through grants NeTS-1423182, CNS-1909048, and CNS-2007006. I have reported my effort and progress every year in the annual or final project reports.

A special thanks to my current and former editors, Lindsay Lawrence and Brian Romer and Todd Green; to my co-author George, who came up with the ingenious term network algorithmics that defined the bulk of my research in the past 25 years; to my Ph.D. advisor, Mukesh Singhal, who taught me how to write research papers; to all my collaborators on various network algorithmics topics, especially to Bill Lin; to many colleagues at Georgia Tech, especially to Mostafa Ammar and Ellen Zegura; to former and current School Chairs Lance Fortnow and Vivek Sarkar who gave me a reduced service load for this book-writing effort; to former and current Ph.D. students who adventured in the field of network algorithmics with me and who helped me with drawing figures and tables, proofreading, and fixing 100+ book bugs in the first edition collected by George; to anonymous reviewers of this book; to my parents and my brother; to my wife Linda; and to my daughter Ellie.

Computer networks have become an integral part of society. We take for granted the ability to transact commerce over the Internet and that users can avail themselves of a burgeoning set of communication methods, which range from file sharing to Web logs. However, for networks to take their place as part of the fundamental infrastructure of society, they must provide performance guarantees.

We take for granted that electricity will flow when a switch is flicked and that telephone calls will be routed on Mother's Day. But the performance of computer networks such as the Internet is still notoriously unreliable. While there are many factors that go into performance, one major issue is that of network bottlenecks. There are two types of network bottlenecks: