Fault-Tolerant IP and MPLS Networks

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