11-09-2013, 12:23 PM
ALGORITHMS FOR ROUTING LOOKUPS AND PACKET CLASSIFICATION
ALGORITHMS FOR ROUTING.pdf (Size: 945.02 KB / Downloads: 29)
Abstract
The work presented in this thesis is motivated by the twin goals of increasing the
capacity and the flexibility of the Internet. The Internet is comprised of packet-processing
nodes, called routers, that route packets towards their destinations, and physical links that
transport packets from one router to another. Owing to advances in optical technologies,
such as Wavelength Division Multiplexing, the data rates of links have increased rapidly
over the years. However, routers have failed to keep up with this pace because they must
perform expensive per-packet processing operations.
INTRODUCTION
The Internet is comprised of a mesh of routers interconnected by links. Communica-
tion among nodes on the Internet (routers and end-hosts) takes place using the Internet
Protocol, commonly known as IP. IP datagrams (packets) travel over links from one router
to the next on their way towards their final destination. Each router performs a forwarding
decision on incoming packets to determine the packet’s next-hop router.
The capability to forward packets is a requirement for every IP router [3]. Addition-
ally, an IP router may also choose to perform special processing on incoming packets.
Examples of special processing include filtering packets for security reasons, delivering
packets according to a pre-agreed delay guarantee, treating high priority packets preferen-
tially, and maintaining statistics on the number of packets sent by different networks. Such
special processing requires that the router classify incoming packets into one of several
flows — all packets of a flow obey a pre-defined rule and are processed in a similar man-
ner by the router. For example, all packets with the same source IP address may be defined
to form a flow. A flow could also be defined by specific values of the destination IP
address and by specific protocol values.
Architecture of a packet-by-packet router
Figure 1.3 shows a block diagram of the architecture of a typical high speed router. It
consists of one line card for each port and a switching fabric (such as a crossbar) that inter-
connects all the line cards. Typically, one of the line cards houses a processor functioning
as the central controller for the router. The path taken by a packet through a packet-by-
packet router is shown in Figure 1.4 and consists of two main functions on the packet: (1)
performing route lookup based on the packet’s destination address to identify the outgoing
port, and (2) switching the packet to the output port.
Architecture of a flow-aware router
Flow-aware routers perform a superset of the functions of a packet-by-packet router.
The typical path taken by a packet through a flow-aware router is shown in Figure 1.13
and consists of four main functions on the packet: (1) performing route lookup to identify
the outgoing port, (2) performing classification to identify the flow to which an incoming
packet belongs, (3) applying the action (as part of the provisioning of differentiated ser-
vices or some other form of special processing) based on the result of classification, and
(4) switching to the output port. The various forms of special processing in function (3),
while interesting in their own right, are not the subject of this thesis. The following refer-
ences describe a variety of actions that a router may perform: admission control [42],
queueing [25], resource reservation [6], output link scheduling [18][74][75][89] and bill-
ing [21].
Outline of the thesis
This thesis proposes several novel lookup and classification algorithms. There is one
chapter devoted to each algorithm. Each chapter first presents background work related to
the algorithm. It then presents the motivation, key concepts, properties, and implementa-
tion results for the algorithm. It also evaluates the algorithm against the metrics outlined
above and against previous work on the subject.
Chapter 2 presents an overview of previous work on routing lookups. It proposes and
discusses a simple routing lookup algorithm optimized for implementation in dedicated
hardware. This algorithm performs the longest prefix matching operation in two memory
accesses that can be pipelined to give the throughput of one routing lookup every memory
access. This corresponds to 20 million packets per second with 50 ns DRAMs (Dynamic
Random Access Memories).