Varghese - Network Algorithmics

Network Algorithmics

An Interdisciplinary Approach to Designing Fast Networked Devices

George Varghese

University of California, San Diego

Morgan Kaufmann

Copyright

Elsevier/Morgan Kaufmann Cover Image: Getty Images Publishing Director: Diane D. Cerra Text Design: Michael Remener Senior Acquisitions Editor: Rick Adams Composition: CEPHA Associate Editor: Karyn Johnson Technical Illustration: Dartmouth Publishing, Inc. Editorial Coordinator: Mona Buehler Copyeditor: Elliot Simon Publishing Services Manger: Simon Crump Proofreader: Physllis Coyne et al. Senior Project Manager: Angela Dooley Indexer: Northwind Editorial Cover Design Manager: Cate Rickard Barr Interior Printer: The Maple-Vail Book Manufacturing Group Cover Design: Yvo Riezebos Design Cover Printer: Phoenix Color

Morgan Kaufmann is an imprint of Elsevier. 500 Sansome Street, Suite 400, San Francisco, CA 94111

This book is printed on acid-free paper.

Designations used by companies to distinguish their products are often claimed as trademarks or registered trademarks. In all instances in which Elsevier is aware of a claim, the product names appear in initial capital or all capital letters. Readers, however, should contact the appropriate companies for more complete information regarding trademarks and registration.

No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means electronic, mechanical, photocopying, scanning, or otherwise without prior written permission of the publisher.

Permissions may be sought directly from Elsevier's Science & Technology Rights Department in Oxford, UK: phone: (+44) 1865 843830, fax: (+44) 1865 853333, e-mail: ) by selecting Customer Support and then Obtaining Permissions.

Library of Congress Cataloging-in-Publication Data, Application submitted

ISBN: 0-12-088477-1

For information on all Morgan Kaufmann publications, visit our website at www.mkp.com.

Printed in the United States of America 08 07 06 05 04 5 4 3 2 1

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

Preface

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 Mothers 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: resource bottlenecks and implementation bottlenecks.

Resource bottlenecks occur when network performance is limited by the speed of the underlying hardware; examples include slow processors in server platforms and slow communication links. Resource bottlenecks can be worked around, at some cost, by buying faster hardware. However, it is quite often the case that the underlying hardware is perfectly adequate but that the real bottleneck is a design issue in the implementation. For example, a Web server running on the fastest processors may run slowly because of redundant data copying. Similarly, a router with a simple packet classification algorithm may start dropping packets when the number of ACL rules grows beyond a limit, though it keeps up with link speeds when classification is turned off. This book concentrates on such network implementation bottlenecks, especially at servers and routers.

Beyond servers and routers, new breeds of networking devices that introduce new performance bottlenecks are becoming popular. As networks become more integrated, devices such as storage area networks (SANs) and multimedia switches are becoming common. Further, as networks get more complex, various special-purpose network appliances for file systems and security are proliferating. While the first generation of such devices justified themselves by the new functions they provided, it is becoming critical that future network appliances keep up with link speeds.

Thus the objective of this book is to provide a set of techniques to overcome implementation bottlenecks at all networking devices and to provide a set of principles and models to help overcome current and future networking bottlenecks.

This book was written to answer a need for a text on efficient protocol implementations. The vast majority of networking books are on network protocols; even the implementation books are, for the most part, detailed explanations of the protocol. While protocols form the foundation of the field, there are just a handful of fundamental network infrastucture protocols left, such as TCP and IP. On the other hand, there are many implementations as most companies and start-ups customize their products to gain competitive advantage. This is exacerbated by the tendency to place TCP and IP everywhere, from bridges to SAN switches to toasters.

Thus there are many more people implementing protocols than designing them. This is a textbook for implementors, networking students, and networking researchers, covering ground from the art of building a fast Web server to building a fast router and beyond.

To do so, this book describes a collection of efficient implementation techniques; in fact, an initial section of each chapter concludes with a Quick Reference Guide for implementors that points to the most useful techniques for each topic. However, the book goes further and distills a fundamental method of crafting solutions to new network bottlenecks that we call network algorithmics. This provides the reader tools to design different implementations for specific contexts and to deal with new bottlenecks that will undoubtedly arise in a changing world.

Here is a detailed profile of our intended audience.

• Network Protocol Implementors: This group includes implementors of endnode networking stacks for large servers, PCs, and workstations and for network appliances. It also includes implementors of classic network interconnection devices, such as routers, bridges, switches, and gateways, as well as devices that monitor networks for measurement and security purposes. It also includes implementors of storage area networks, distributed computing infrastructures, multimedia switches and gateways, and other new networking devices. This book can be especially useful for implementors in start-ups as well as in established companies, for whom improved performance can provide an edge.
• Networking Students: Undergraduate and graduate students who have mastered the basics of network protocols can use this book as a text that describes how protocols should be implemented to improve performance, potentially an important aspect of their future jobs.
• Instructors: Instructors can use this book as a textbook for a one-semester course on network algorithmics.
• Systems Researchers: Networking and other systems researchers can use this text as a reference and as a stimulus for further research in improving system performance. Given that disributed operating systems and distributed computing infrastructures (e.g., the Grid) rely on an underlying networking core whose performance can be critical, this book can be useful to general systems researchers.

network implementations. Network algorithmics is interdisciplinary, because it requires techniques from diverse fields such as architecture, operating systems, hardware design, and algorithms. Network algorithmics is also a