ABSTRACT
Network Algorithmics studies techniques for efficient network protocol implementations. It is primarily about two things: a set of fundamental networking performance bottlenecks, and a set of interdisciplinary techniques to address these bottlenecks. NetworkAlgorithmics is an interdisciplinary approachbecause it encompasses suchfields as archi-
tecture and operating systems (for speeding up servers), hardware design (for speeding up network devices such as routers), and algorithm design (for designing scalable algorithms). Network Algorithmics is also a systems approach because it exploits the fact that routers and servers are systems, in which efficiencies can be gained by moving functions in time and space between subsystems. Bottlenecks arise from the simultaneous desire tomake networks easy to usewhile at the same time
realizing the performance of the raw hardware. Ease of use comes from the use of powerful network abstractions such as socket interfaces andprefix-based forwarding. Such abstractions can exact a large performance penalty compared to the raw transmission capacity of optical links. The bottlenecks are different for the two fundamental categories of networking devices, endnodes and routers. Endnodes are the endpoints of the network and include personal computers, workstations, and
large servers. To run an arbitrary code, personal endnodes typically have an operating system that mediates between applications and the network. To ease software development, most operating systems are structured as layered software; to protect the operating system from other applications, operating systems implement a set of protectionmechanisms; finally, core operating system routines such as schedulers and allocators are written using general mechanisms that target as wide a class of applications aspossible.Unfortunately, the combinationof layered software, protectionmechanisms, and excessive generality can slow down networking software greatly even with the fastest processors. Unlike endnodes, routers are special-purpose devices devoted to networking. Thus there is very
little structural overhead within a “router,” with only the use of a very lightweight operating system and a clearly separated forwarding path that often is completely implemented in hardware. Instead
28-1
of structure, the fundamental problems faced by routers are caused by scale and services. Optical links keep getting faster, going from 1 to 40 Gbps links. Besides bandwidth scaling, there is also population scaling as endpoints get added to the Internet as more enterprises go online. While scaling has historically driven the design of routers, recently it has become important to instrument routers to provide network guarantees-delay in times of congestion, protection during attacks, and availability when failures occur. Finding ways to implement these new services at high speeds will be a major challenge for router vendors in the next decade. In the rest of the chapter, we make these concepts more specific by providing examples from
Router Algorithmics (Section 28.2) and Endnode Algorithmics (Section 28.3). Before we do so, we provide a brief survey of the measures we use and a model of memory technologies. This is because optimizing memory accesses is crucial for both endnode and router algorithmics.
