C HAPTER
2
IP Forwarding Plane: Achieving
Nonstop Forwarding
IP routers contain two interrelated but largely independent components, namely control and
forwarding. The IP control plane consists of routing protocols that provide routing informa-
tion used to build a Forwarding Information Base (FIB). The IP forwarding plane comprises
a FIB, or forwarding table, that is used to forward packets toward their destination. On the
other hand, the IP forwarding plane performs time-critical tasks such as address lookup,
packet switching from incoming to outgoing links, and packet scheduling for transmission
on the outgoing link. Among these tasks, IP address lookup usually is a major bottleneck
in high-performance routers.
This chapter begins with an overview of the FIB and its usage to forward IP packets. After
a brief description of the IP address lookup operation, an overview of the trie-based data
structures is presented. Trie-based prefix representations are attractive because the perform-
ance metrics of the resulting lookup schemes can be conveniently tuned by varying certain
parameters. This is followed by an overview of the centralized forwarding architecture
paradigm. The discussion continues with analysis of the factors causing performance de-
gradation in the centralized forwarding architecture and trends toward distributed forward-
ing architecture that avoid such shortcomings. This naturally leads to a description of a
fault-tolerant control-plane architecture framework that allows nonstop forwarding opera-
tions in a router across its control-plane failure. The chapter concludes with a brief chapter
summary.
Overview of IP Forwarding
The Internet is a collection of interconnected networks for forwarding packets between
hosts using Internet Protocol (IP). IP provides connectionless datagram service without
end-to-end delivery guarantees. Throughout this book, unless explicitly stated otherwise,
the term IP refers to IP version 4 (IPv4).
1
In the Internet model, systems that forward IP packets are called routers. That is, one of the
primary functions of a router is to forward packets toward their final destinations. To
accomplish this task, a router needs to make a forwarding decision for each packet to
determine the next-hop address and the outgoing link information. The routing information
is obtained through routing protocols and is used to build the FIB or forwarding table.
24 Chapter 2: IP Forwarding Plane: Achieving Nonstop Forwarding
The forwarding process generally consists of three distinct operations:
Address lookup to determine the outgoing link
Forwarding packets through the switching fabric when the outgoing link resides on a line
card different than that on which the packet was received, or forwarding packets locally
without traversing the switching fabric (for example, when the outgoing link is on the
same line card)
Scheduling
The step that involves a forwarding table search using an incoming packet’s IP destination
address as the search key is called the address lookup. The subsequent step of transferring the
packet to a link on a different or the same line card using forwarding information retrieved by
address lookup is known as switching. In the final step, called scheduling, the packet is
scheduled for transmission on the outgoing link. Figure 2-1 shows the basic sequence of IP
forwarding-plane operations.
Figure 2-1 Basic Operations in IP Forwarding
Because IP packets are forwarded based on the IP destination address, the design and
complexity of the address lookup operation is influenced by the addressing scheme used.
IPv4 addresses are 32 bits long and are partitioned into a network part and a host part (see
Figure 2-2). The class of the IP address (denoted as A, B, and C) determines the number of bits
in the network and the host part. For example, Class A addresses assign 8 bits to the network
part and 24 bits to the host part. Similarly, Class B and Class C addresses assign 16 and 24 bits,
respectively, in the network part.
Outgoing
Link
Header
IP Packet
Prefix Next Hop Out Link
SwitchingForwarding DecisionScheduling
Address Lookup
Incoming Link
Switching Fabric (or Interconnect)
Forwarding Table
Next Hop, Out Link

Get Fault-Tolerant IP and MPLS Networks now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.