Algorithms in a Nutshell
George T. Heineman, Gary Pollice, Stanley Selkow
In the midst of the SDN craze (or haze, depending on your point of view), we often forget that all networks are, in the final analysis, driven by software. Every control plane ever developed or deployed is a software application running on top of a physical device. And every control plane, every queuing mechanism, every forwarding mechanism, and everything we work on in the networking field is based on some sort of algorithm. But what is an algorithm, really? What sorts of algorithms are there, and what are they used for? These are the questions this book specifically takes aim at answering.
The authors begin with a chapter discussing the concepts of algorithms; this chapter contains a really helpful section on the difference between the classes of algorithms available, such as greedy and Chapter 2 focuses on the math of algorithm performance, providing information on the difference between O(1), O(n), O(n log n), and many other expressions describing the feed at which algorithms operate. This is one of the most helpful and clearly explained sections in the book. The third chapter explains the building blocks of algorithms, specifically focusing on the conventions used in the book, and some challenges around measuring the performance and accuracy of any given algorithm.
Chapter 4 considers sorting algorithms, and chapter 5 search. These three kinds of algorithms probably cover 80-90% of all algorithm usage in real code. These three classes of algorithms actually provide the building blocks for many other kinds of algorithms. For instance, Shortest Path First (SPF) requires a sorted heap or list of nodes, edges, and reachable destinations in the network—but we have to sort a list to have a sorted list to use in SPF.
Chapter 6 jumps into material directly applicable to network engineering; here is where Dijkstra’s SPF algorithm is covered. This chapter will be extremely useful to network engineers to read and understand, even though the terminology is often different. Chapters 7, 9, and 11, on path finding in AI, computational geometry, and emerging algorithm categories, are interesting, but not all that useful for the average (or above average) network engineer.
Chapter 8 discusses network flow diagrams, which are a superset of many of the traffic engineering, service chaining, and queuing theory problems engineers face in real networks. Chapter 10 should be familiar to engineers who’ve looked at the m-way trees and treis used in packet switching.
Overall, this is really useful book for network engineers who want to dig deeper into the software roots of how network protocols and switching work. There are a few chapters that don’t directly apply to the common sets of problems network engineering involves, but readers won’t miss a lot skipping those sections if the overall length of the book seems like it’s too much.
The reading difficulty is moderate, and the time to read is pretty long (partially because of the many code examples and the depth of the concepts covered).