Network Algorithmics

Introduction

My work is a game, a very serious game.

— M. C. ESCHER

Part I dealt with models and principles and Part II dealt with applying these models and principles to endnodes. The third part of this book deals with router algorithmics. This is the application of network algorithmics to building fast routers. However, many of the techniques apply to bridges, gateways, measurement devices, and firewalls. The techniques are applied mostly in a hardware setting, and much of it has to do with processing packets at wire speeds as links get faster. We study exact lookups, prefix lookups, packet classification, switching, and QoS. We also study some other chores within a router, such as striping and flow control across chip-to-chip links within a router. ...