Network Algorithmics 55
danny writes "Modern network devices have to handle traffic in huge volumes at low
latencies; achieving this requires ideas and approaches from all of
computer science: hardware, algorithms, protocols, software engineering
and their integration in a discipline which Varghese calls "network
algorithmics". Read the rest of Danny's review.
| Network Algorithmics: An Interdisciplinary Approach to Designing Fast Networked Devices | |
| author | George Varghese |
| pages | 465 |
| publisher | Morgan Kaufmann |
| rating | 9 |
| reviewer | Danny Yee |
| ISBN | 0120884771 |
| summary | pulling out all the stops to fix bottlenecks |
After an introduction in chapter one to bottlenecks and techniques for avoiding them, Varghese provides a brief overview of protocols, hardware, network architectures, and operating systems, with examples, in chapter two. This is best suited as a refresher: Network Algorithmics assumes a general familiarity with networking protocols, operating systems and computer architecture, and if used as a text would be suitable for higher undergraduates. (The exercises at the end of each chapter are often open-ended.)
Chapter three introduces the fifteen implementation principles that are the core of Network Algorithmics: P1 Avoid obvious waste; P2 Shift computation in time (precompute, evaluate lazily, share expenses or batch); P3 Relax system requirements (trade certainty or accuracy for time, shift computation in space); P4 Leverage off system components (exploit locality, trade memory for speed, exploit existing hardware), P5 Add hardware (use memory interleaving and pipelining, use wide word parallelism, combine DRAM and SRAM effectively); P6 Create efficient specialized routines; P7 Avoid unnecessary generality; P8 Don't be tied to reference implementation; P9 Pass hints in layer interfaces, P10 Pass hints in protocol headers; P11 Optimize the expected case (use caches); P12 Add state for speed (compute incrementally); P13 Optimize degrees of freedom; P14 Use bucket sorting, bitmaps; and P15 Create efficient data structures. Chapter four presents fifteen problems that illustrate these principles in action, with hints to solutions.
Part II of Network Algorithmics is devoted to end-nodes. A chapter "Copying Data" takes a web server, delivering files from disk to network, as the prototype, and explores different approaches to reduce pressure on the memory and I/O bus by reducing the number of copies required: copy-on-write, fbufs, RDMA, IO-Lite, and more. It also touches on making cache use more effective and the tantalizing possibilities of "integrated layer processing".
"Transferring Control" looks at minimizing scheduling overhead and maximizing concurrency: at context-switches, processes, threads, and event-driven servers. It evaluates the existing Unix select() call and considers ways of speeding it up, with and without changing the API. And it touches on ways of avoiding system calls and reducing interrupt overhead.
There are three shorter chapters. "Maintaining Timers" explores hashed and hierarchical timing wheels, the BSD implementation, and fine granularity. "Demultiplexing" looks at the development of packet filters: CMU/Stanford, Berkeley, Pathfinder, hardware, and Dynamic (generating filter code in real time). And "Protocol Processing" looks at some miscellaneous tasks that can become bottlenecks: buffer management, CRC checks and checksums, TCP and UDP protocol processing, and packet reassembly.
So far I've only skimmed Part III, "Playing with Routers". This has chapters on "Exact-Match Lookups", "Prefix-Match Lookups", "Packet Classification", "Switching", "Scheduling Packets", and "Routers as Distributed Systems". And Part IV offers chapters on "Measuring Network Traffic" and "Network Security", along with a summary and overview.
Varghese gets right down into the details in some places, but he sets the material he covers into its broader context. He often takes a historical approach, looking at how implementations have been driven by changing requirements. And he stresses that only with a broad view can the overall costs and possible optimizations be seen: with web server performance, for example, it is necessary to consider "the whole system, from HTTP and its headers, to the file system, and down to the instruction caches". Where many computing disciplines emphasize the isolation of components, network algorithmics stresses links across layers and boundaries. (It's not overdone, but approaches and principles are often illustrated with analogies to ordinary life serving tables in a restaurant, for example or parallels with other areas of computing.)
Purists might find the practical approach of network algorithmics distressing Varghese admits that it "may seem drab and shallow" compared to "the beauty of theoretical techniques" but it has an attraction all of its own. I've often felt that "computer science" as commonly constructed lacks any coherence, spanning everything from nearly pure mathematics to hardware and engineering, but Network Algorithmics has made me rethink that.
Little in Network Algorithmics is relevant to my job as a system and network administrator I just plug switches in and configure them, and don't have to worry about their internals but I found it fascinating. Apart from curious general readers with a computer science background, or hackers who enjoy stretching their minds, the obvious audience is anyone building high-performance network devices or looking at optimization of networking code, say in the Linux kernel.
Danny Yee has written over 900 other book reviews."
You can purchase Network Algorithmics: An Interdisciplinary Approach to Designing Fast Networked Devices from bn.com. Slashdot welcomes readers' book reviews -- to see your own review here, read the book review guidelines, then visit the submission page.
Re: (Score:1, Offtopic)
I am now terrified.. Unless there is lasers comming out of their freaken heads.
oh please (Score:5, Insightful)
dear danny,
Next time, wait until you actually READ the book before writing a review.
Re:oh please (Score:5, Funny)
I only skimmed the review.
Re:oh please (Score:5, Funny)
I only skimmed the last comment.
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
Just a case of bad wording, they are not really *that* negligent.
Re: (Score:2)
Re: (Score:1)
Maybe I'm reading this wrong... (Score:2)
target audience (Score:1)
Ok, first sign that this is a book more in the "magazine" style than in the "scientific" style.
Apart from curious general readers with a computer science background, or hackers who enjoy stretching their minds, the obvious audience is anyone building high-performance network devices or looking at
Re:target audience (Score:4, Informative)
Though the reviewer is right - many of the algorithms in the book would be useful in software-based routers, though there's room for caution: some of them are encumbered by patents of various sorts, and are recent enough that they'll remain so for a while.
In other news (Score:2, Insightful)
Re: (Score:2)
Re: (Score:2, Funny)
Your concerns will be addressed in TrafficStop 2.0
Re: (Score:2)
OH NO THE HORROR!
Of course, there are times it gets on my nerves too, but then I think about having a commute in say, Chicago... I hear it's horrible.
Network Analytics book review (Score:5, Interesting)
and traffic analysis space, for a living such things are of keen intrest to me. I can
thus recommend it without reservation.
Network Analytics book review -from another reader (Score:1)
In addition, the products George Varghese's research work were implemented by different network device manufacture
Hmm, interdisciplinary (Score:2)
Here is a review from Cisco.com (Score:5, Informative)
http://www.cisco.com/web/about/ac123/ac147/archive d_issues/ipj_8-3/book_review.html [cisco.com]
and i copy:
Book Review
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
Who Varghese is (Score:4, Informative)
His research has been extremely influential in both academia and industry.
Among the numerous of his papers that introduced novel and complete solutions to difficult networking problems,
is for example "Trading Packet Headers for Packet Processing", which introduced the concept of tag/label switching,
what is mostly known to us today as MPLS.
Hey (Score:1)
Re: (Score:1)
Bill Joy?
KFG
Re: (Score:2)
Re: (Score:1)
KFG
Brilliant man (Score:1, Redundant)
one-pass algorithms? (Score:2, Interesting)
When I read the title of this book, I expected it to be about efficient one-pass algorithms, i.e. ones that you can do quickly on a stream of network information without using a ton of memory or CPU time per packet. I took a course in grad school a few years back about this, and it's a pretty interesting (and relatively recent) subject. You can read more about it here (home page of my prof): http://www.cs.rutgers.edu/~muthu/ [rutgers.edu].
Morgan Kauffman (Score:2)
Re: (Score:2)
P2 Shift computation in time (precompute, evaluate lazily, share expenses or batch);
P3 Relax system requirements (trade certainty or accuracy for time, shift computation in space);
P4 Leverage off system components (exploit locality, trade memory for speed, exploit existing hardware),
P7 Avoid unnecessary generality;
P8 Don't be tied to reference implementation;
P11 Optimize the exp
Latency (Score:2)
HIGH latencies. Networks have HIGH latencies. Come on now, editors.
Re: (Score:1)
I think he means "... handle traffic in huge volumes while providing low latencies."
useful for programmers (Score:3, Interesting)
UCSD (Score:2)
Almost makes me proud to be an alumni.
nice (Score:1)