AUDIENCE

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 distributed 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.

WHAT THIS BOOK IS ABOUT

Chapter 1 provides a more detailed introduction to network algorithmics. For now, we informally define network algorithmics as an interdisciplinary systems approach to streamlining 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 systems approach, because routers and servers are systems in which efficiencies can be gained by moving functions in time and space between subsystems.

In essence, this book is about three things: fundamental networking implementation bottlenecks, general principles to address new bottlenecks, and techniques for specific bottlenecks that can be derived from the general principles.

Fundamental bottlenecks for an endnode such as a PC or workstation include data copying, control transfer, demultiplexing, timers, buffer allocation, checksums, and protocol processing. Similarly, fundamental bottlenecks for interconnect devices such as routers and SAN switches include exact and prefix lookups, packet classification, switching, and the implementation of measurement and security primitives. Chapter 1 goes into more detail about the inherent causes of these bottlenecks.

The fundamental methods that encompass network algorithmics include implementation models (Chapter 2) and 15 implementation principles (Chapter 3). The implementation models include models of operating systems, protocols, hardware, and architecture. They are included because the world of network protocol implementation requires the skills of several different communities, including operating system experts, protocol pundits, hardware designers, and computer architects. The implementation models are an attempt to bridge the gaps between these traditionally separate communities.

On the other hand, the implementation principles are an attempt to abstract the main ideas behind many specific implementation techniques. They include such well-known principles as “Optimize the expected case.” They also include somewhat less well-known principles, such as “Combine DRAM with SRAM,” which is a surprisingly powerful principle for producing fast hardware designs for network devices.

While Part I of the book lays out the methodology of network algorithmics, Part II applies the methodology to specific network bottlenecks in endnodes and servers. For example, Part II discusses copy avoidance techniques (such as passing virtual memory pointers and RDMA) and efficient control transfer methods (such as bypassing the kernel, as in the VIA proposal, and techniques for building event-driven servers).

Similarly, Part III of the book applies the methodology of Part I to interconnect devices, such as network routers. For example, Part III discusses effficient prefix-lookup schemes (such as multibit or compressed tries) and efficient switching schemes (such as those based on virtual output queues and bipartite matching).

Finally, Part IV of the book applies the methodology of Part I to new functions for security and measurement that could be housed in either servers or interconnect devices. For example, Part IV discusses efficient methods to compress large traffic reports and efficient methods to detect attacks.

ORGANIZATION OF THE BOOK

This book is organized into four overall parts. Each part is made as self-contained as possible to allow detailed study. Readers that are pressed for time can consult the index or Table of Contents for a particular topic (e.g., IP lookups). More importantly, the opening section of each chapter concludes with a Quick Reference Guide that points to the most important topics for implementors. The Quick Reference Guide may be the fastest guide for usefully skimming a chapter.

Part I of the book aims to familiarize the reader with the rules and philosophy of network algorithmics. It starts with Chapter 2, which describes simple models of protocols, operating systems, hardware design, and endnode and router architectures. Chapter 3 describes in detail the 15 principles used as a cornerstone for the book. Chapter 4 rounds out the first part by providing 15 examples, drawn for the most part from real implementation problems, to allow the reader a first opportunity to see the principles in action on real problems.

Part II of the book, called “Playing with Endnodes,” shows how to build fast endnode implementations, such as Web servers, that run on general-purpose operating systems and standard computer architectures. It starts with Chapter 5, which shows how to reduce or avoid extra data copying. (Copying often occurs when network data is passed between implementation modules) and how to increase cache efficiency. Chapter 6 shows how to reduce or avoid the overhead of transferring control between implementation modules, such as the device driver, the kernel, and the application. Chapter 7 describes how to efficiently manage thousands of outstanding timers, a critical issue for large servers. Chapter 8 describes how to efficiently demultiplex data to receiving applications in a single step, allowing innovations such as userlevel networking. Chapter 9 describes how to implement specific functions that often recur in specific protocol implementations, such as buffer allocation, checksums, sequence number bookkeeping, and reassembly. An overview of Part II can be found in Figure 1.1.

Part III of the book, called “Playing with Routers,” shows how to build fast routers, bridges, and gateways. It begins with three chapters that describe state lookups of increasing complexity. Chapter 10 describes exact-match lookups, which are essential for the design of bridges and ARP caches. Chapter 11 describes prefix-match lookups, which are used by Internet routers to forward packets. Chapter 12 describes packet classification, a more sophisticated form of lookup required for security and quality of service. Chapter 13 describes how to build crossbar switches, which interconnect input and output links of devices such as routers. Finally, Chapter 14 describes packet-scheduling algorithms, which are used to provide quality-of-service, and Chapter 15 discusses routers as distributed systems, with examples focusing on performance and the use of design and reasoning techniques from distributed algorithms. While this list of functions seems short, one can build a fast router by designing a fast lookup algorithm, a fast switch, and fast packet-scheduling algorithms. Part IV, called “Endgame,” starts by speculating on the potential need for implementing more complex tasks in the future. For example, Chapter 16 describes efficient implementation techniques for measurement primitives, while Chapter 17 describes efficient implementation techniques for security primitives. The book ends with a short chapter, Chapter 18, which reaches closure by distilling the unities that underly the many different topics in this book. This chapter also briefly presents examples of the use of algorithmics in a canonical router (the Cisco GSR) and a canonical server (the Flash Web server). A more detailed overview of Parts III and IV of the book can be found in Figure 1.2.

FEATURES

The book has the following features that readers, implementors, students, and instructors can take advantage of.

Intuitive introduction: The introductory paragraph of each chapter in Parts II, III, and IV uses an intuitive, real-world analogy to motivate each bottleneck. For example, we use the analogy of making multiple photocopies of a document for data copying and the analogy of a flight database for prefix lookups.

Quick Reference Guide: For readers familiar with a topic and pressed for time, the opening section of each chapter concludes with a Quick Reference Guide that points to the most important implementation ideas and the corresponding section numbers.

Chapter organization: To help orient the reader, immediately after the Quick Reference Guide in each chapter is a map of the entire chapter.

Summary of techniques: To emphasize the correlation between principles and techniques, at the start of each chapter is a table that summarizes the techniques described, together with the corresponding principles.

Consistent use of principles: After a detailed description in Chapter 3 of 15 principles, the rest of the book consistently uses these principles in describing specific techniques. For reference, the principles are summarized inside the front cover. Principles are referred to consistently by number — for example, P9 for Principle 9. Since principle numbers are hard to remember, three aids are provided. Besides the inside front cover summary and the summary at the start of each chapter, the first use of a principle in any chapter is accompanied by an explicit statement of the principle.

Exercises: Chapter 4 of the book provides a set of real-life examples of applying the principles that have been enjoyed by past attendees of tutorials on network algorithmics. Every subsequent chapter through Chapter 17 is followed by a set of exercises. Brief solutions to these exercises can be found in an instructor’s manual obtainable from Morgan Kaufmann.

Slides: Lecture slides in pdf for most chapters are available at Morgan Kaufmann’s Web site www.mkp.com.

USAGE

This book can be used in many ways.

Textbook: Students and instructors can use this book as the basis of a one-semester class. A semester class on network algorithmics can include most of Part I and can sample chapters from Part II (e.g., Chapter 5 on copying, Chapter 6 on control overhead) and from Part III (e.g., Chapter 11 on prefix lookups, Chapter 13 on switching).

Implementation guide: Implementors who care about performance may wish to read all of Part I and then sample Parts II and III according to their needs.

Reference book: Implementors and students can also use this book as a reference book in addition to other books on network protocols.

WHY THIS BOOK WAS WRITTEN

The impetus for this book came from my academic research into efficient protocol implementation. It also came from three networking products I worked on with colleagues: the first bridge, the Gigaswitch, and the Procket 40 Gbps router. To prove itself against detractors, the first bridge was designed to operate at wire speed, an idea that spread to routers and the entire industry. My experience watching the work of Mark Kempf on the first bridge (see Chapter 10) led to a lasting interest in speeding up networking devices.

Next, the DEC Gigaswitch introduced me to the world of switching. Finally, the Procket router was designed by an interdisciplinary team that included digital designers who had designed processors, experts who had written vast amounts of the software in core routers, and some people like myself who were interested in algorithms. Despite the varied backgrounds, the team produced innovative new ideas, which convinced me of the importance of interdisciplinary thinking for performance breakthroughs. This motivated the writing of Chapter 2 on implementation models, an attempt to bridge the gaps between the different communities involved in high-performance designs.

For several years, I taught a class that collected together these techniques. The 15 principles emerged as a way to break up the techniques more finely and systematically. In retrospect, some principles seem redundant and glib. However, they serve as part of a first attempt to organize a vast amount of material.

I have taught five classes and three tutorials based on the material in this book, and so this book has been greatly influenced by student responses and ideas.

ACKNOWLEDGMENTS

A special thanks to my editors: Karen Gettman and Rick Adams and Karyn Johnson; to all my advisors, who taught me so much: Wushow Chou, Arne Nillson, Baruch Awerbuch, Nancy Lynch; to all my mentors: Alan Kirby, Radia Perlman, Tony Lauck, Bob Thomas, Bob Simcoe, Jon Turner; to numerous colleages at DEC and other companies, especially to Sharad Merhotra, Bill Lynch, and Tony Li of Procket Networks, who taught me about real routers; to students who adventured in the field of network algorithmics with me; to numerous reviewers of this book and especially to Jon Snader, Tony Lauck, Brian Kernighan, Craig Partridge, and Radia Perlman for detailed comments; to Kevin D’Souza, Stefano Previdi, Anees Shaikh, and Darryl Veitch for their reviews and ideas; to my family, my mother, my wife’s father and mother, and my sister; and, of course, to my wife, Aju, and my sons, Tim and Andrew.

I’d like to end by acknowledging my heroes: four teachers who have influenced me. The first is Leonard Bernstein, who taught me in his lectures on music that a teacher’s enthusiasm for the material can be infectious. The second is George Polya, who taught me in his books on problem solving that the process of discovery is as important as the final discoveries themselves. The third is Socrates, who taught me through Plato that it is worth always questioning assumptions. The fourth is Jesus, who has taught me that life, and indeed this book, is not a matter of merit but of grace and gift.