Network Algorithmics
Network Algorithmics: An Interdisciplinary Approach to Designing Fast Networked Devices, by George Varghese, ISBN 0120884771, Morgan Kaufmann, 2004.

This is not a generic algorithms book (that is, it does not overlap much at all with Sedgewick or Coleman as an introduction to algorithms), nor is it a typical introduction to TCP/IP networking book (for example, there is no chapter defining the TCP/UDP/IP header fields, thank goodness). It might best be described as an algorithms analysis book set in the context of networking and also in the context of implementations that mix hardware and software solutions. For those familiar with Radia Perlman's book Interconnections, I found aspects of the writing style and approach to be similar. George Varghese—in addition to having been a networking professor for many years—has had a lot of industry experience from licensing algorithms to networking companies, to consulting with Procket Networks in the company's early days of architecting its core router, to starting a security company that was recently acquired by Cisco Systems. I have been doing architecture work at Cisco for several years and can say that George's book has real grounding in how systems are built and analyzed today.

Organization
Chapter 2 presents abstractions for networking protocols, hardware design, routers, memory technology, and Internet end nodes (servers). This is a great introduction into "systems" thinking. In section 2.2.7, "Final Hardware Lessons," one thing I thought George should have mentioned along with metrics of chip size, speed, I/O, and memory is power. Power is becoming a major systems concern in many platforms and deserves mention as an optimization constraint.

Chapters 3 and 4 go through a list of 15 implementation principles to use in approaching algorithmic design in systems and then give examples of these principles in action. What I find interesting about this section is that from working with George in the past, he really does believe and practice "principle"-based architecture thinking. I remember discussing several of the principles with him several years ago, and you can see how his many years of experience working in the networking field have shaped these principles. Many have probably employed some of these, but as George says in the chapter introduction, having them explicitly documented with examples is useful to help clarify our thinking. Some of the principles (and both the short examples in this chapter as well as examples cited in more detail in later chapters) are really fundamental, and I think reading through examples helped clarify in my mind when to use them.

Chapter 5 covers copying data, for example, in a server design. I really like this type of chapter, in which a subject (in this case the effect of packet copying on Web server performance) is explored in detail but with a focus on where algorithms and systems design play an important part.

My biggest question about this chapter is that I was unsure how applicable this is to, say, modern server design using Linux and with latest Gigabit Ethernet network-interface-card (NIC) designs. I know there was a lot of interesting work in the late 1990s, but this chapter without any data is more along the lines of an extended example of how to apply implementation principles.

Chapters 6 through 9 are not what I would consider the meat of the book; they treat the topics of implementation and analysis for servers, timers, parsing/classification of packets, and buffer management (memory allocation).

Chapter 10 covers exact match lookups. There is not a lot of meaty algorithmic discussion, but the history of scaling performance of bridges is used to elegantly show an evolution of algorithmic approaches to exact matching.

Chapter 11 is an awesome overview of the state-of-the-art in longest prefix match (used for destination address matching in routers and switches). A good read of this chapter will yield an understanding of the trade-offs in all major published algorithms, although there may be variations or tuned versions of these algorithms in use at companies like Cisco. I believe this chapter covers all the major categories of solutions.

Chapter 12 extends the prior chapter into more general packet classification (which is used in applications like extended access lists). Like the lookup chapter, this chapter addresses one of George's prime core competencies. There is good discussion on leading published approaches (Grid-of-Trie, cross producting, geometric, and decision treebased approaches). I strongly recommend this chapter.

Chapters 13 and 14 cover packet switching (that is, architecture of fabrics like crossbars for connecting line cards in a router or switch) and then packet scheduling. These topics get a good academic treatment (after all, George is one who introduced Modified Deficit Round Robin (MDRR) to the industry as well as academia), and although there are gaps between what many networking markets are defining as requirements for packet scheduling and what is in this chapter, the chapter is still useful.

Chapter 15 is a short chapter that tries to treat at a high analytic level the algorithmic problems involved with routing protocols. It covers this topic without getting very specific into nonrelevant (to the analysis) networking details.

Chapter 16, which addresses measuring network traffic, was probably one of my least favorite chapters. Some of it is academically interesting but requires network level changes that I just do not think will occur. There are some cute tricks relative to counters and such, but I think they are similar to approaches already being used.

Chapter 17 is a network security chapter and seems to serve as an early introduction to the topic of algorithms in network security; this is not a major focus area of the book.

Areas for Improvement
There is always room for improvement, and I list here three areas in which this book could have been improved:

1.	There is a running thread in the book of prefacing technical discussions in some cases with an example from the "normal world," like comparing packets to envelopes in the postal system. I estimate this is less than 1 percent of the content of the book and fairly easy to ignore if it annoys you.
2.	I would have enjoyed better (more detailed) figures. A well-done, detailed figure can incorporate multiple concepts in the text around it and make it much clearer. On the positive side, there are numerous figures in the specifications, even if they do tend to be simple and high level.
3.	Another area that I would have enjoyed seeing more on is empirical data (tables of data and graphs). I enjoy detailed empirical data of the type that Hennessy and Patterson so effectively use in their Computer Architecture book. There are many places (for example, Web server optimizations in Chapter 5) that I think could have benefited from detailed empirical data. However, I think folks often rely on empirical data too much when a simple analysis like the type done throughout the book could be done to help optimize the problem.

Recommended
Many chapters in this book are directly relevant to the development of networking equipment and software, as well as what is "under the hood" of networking equipment. The book is fun to read and I believe succeeds in trying to convey an organized systems approach to thinking about problems in the networking space.

—Will Eatherton
will@cisco.com

Read Any Good Books Lately?
Then why not share your thoughts with the readers of IPJ? We accept reviews of new titles, as well as some of the "networking classics." In some cases, we may be able to get a publisher to send you a book for review if you don't have access to it. Contact us at ipj@cisco.com for more information.