Packet Forwarding Technologies

Weidong Wu

• Publisher: Auerbach Publications
• Year: 2007
• ISBN:
  9781000654004
• Edition: 1
• Topic: Computer Science
• Subtopic: Information Technology
• Index: Computer Science

As Internet traffic continues to grow exponentially, there is a great need to build Internet protocol (IP) routers with high-speed and high-capacity packet networking capabilities. The first book to explore this subject, Packet Forwarding Technologies explains in depth packet forwarding concepts and implementation technologies. It covers the

Chapter 1

Introduction

1.1 Introduction

The Internet comprises a mesh of routers interconnected by links, in which routers forward packets to their destinations, and physical links transport packets from one router to another. Because of the scalable and distributed nature of the Internet, there are more and more users connected to it and more and more intensive applications over it. The great success of the Internet thus leads to exponential increases in traffic volumes, stimulating an unprecedented demand for the capacity of the core network. The trend of such exponential growth is not expected to slow down, mainly because data-centric businesses and consumer networking applications continue to drive global demand for broadband access solutions. This means that packets have to be transmitted and forwarded at higher and higher rates. To keep pace with Internet traffic growth, researchers are continually exploring transmission and forwarding technologies.

Advances in fiber throughput and optical transmission technologies have enabled operators to deploy capacity in a dramatic fashion. For example, dense wavelength division multiplexing (DWDM) equipment can multiplex the signals of 300 channels of 11.6 Gbit/s to achieve a total capacity of more than 3.3 Tbit/s on a single fiber and transmit them over 7000 km [1]. In the future, DWDM networks will widely support 40 Gbit/s (OC-768) for each channel, and link capacities are keeping pace with the demand for bandwidth.

Historically, network traffic doubled every year [2], and the speed of optical transmissions (such as DWDM) every seven months [3]. However, the capacity of routers has doubled every 18 months [3], laging behind network traffic and the increasing speed of optical transmission. Therefore, the router becomes the bottleneck of the Internet.

In the rest of this chapter, we briefly describe the router including the basic concept, its functionalities, architecture, and key components.

1.2 Concept of Routers

The Internet can be described as a collection of networks interconnected by routers using a set of communications standards known as the Transmission Control Protocol/Internet Protocol (TCP/IP) suite. TCP/IP is a layered model with logical levels: the application layer, the transport layer, the network layer, and the data link layer. Each layer provides a set of services that can be used by the layer above [4]. The network layer provides the services needed for Internetworking, that is, the transfer of data from one network to another. Routers operate at the network layer, and are sometimes called IP routers.

Routers knit together the constituent networks of the global Internet, creating the illusion of a unified whole. In the Internet, a router generally connects with a set of input links through which a packet can come in and a set of output links through which a packet can be sent out. Each packet contains a destination IP address; the packet has to follow a path through the Internet to its destination. Once a router receives a packet at an input link, it must determine the appropriate output link by looking at the destination address of the packet. The packet is transferred router by router so that it eventually ends up at its destination. Therefore, the primary functionality of the router is to transfer packets from a set of input links to a set of output links. This is true for most of the packets, but there are also packets received at the router that require special treatment by the router itself.

1.3 Basic Functionalities of Routers

Generally, routers consist of the following basic components: several network interfaces to the attached networks, processing module(s), buffering module(s), and an internal interconnection unit (or switch fabric). Typically, packets are received at an inbound network interface, processed by the processing module and, possibly, stored in the buffering module. Then, they are forwarded through the internal interconnection unit to the outbound interface that transmits them to the next hop on their journey to the final destination. The aggregate packet rate of all attached network interfaces needs to be processed, buffered, and relayed. Therefore, the processing and memory modules may be replicated either fully or partially on the network interfaces to allow for concurrent operations.

A generic architecture of an IP router is given in Figure 1.1. Figure 1.1a shows the basic architecture of a typical router: the controller card [which holds the central processing unit (CPU)], the router backplane, and interface cards. The CPU in the router typically performs such functions as path computations, routing table maintenance, and reachability propagation. It runs whichever routing protocols are needed in the router. The interface cards consist of adapters that perform inbound and outbound packet forwarding (and may even cache routing table entries or have extensive packet processing capabilities). The router backplane is responsible for transferring packets between the cards. The basic functionalities in an IP router can be categorized as: route processing, packet forwarding, and router special services. The two key functionalities are route processing (i.e., path computation, routing table maintenance, and reachability propagation) and packet forwarding, shown in Figure 1.1b. We discuss the three functionalities in more detail subsequently.

1.3.1 Route Processing

Routing protocols are the means by which routers gain information about the network. Routing protocols map network topology and store their view of that topology in the routing table. Thus, route processing includes routing table construction and maintenance using routing protocols, such as the Routing Information Protocol (RIP) and Open Shortest Path First (OSPF) [5, 6, 7]. The routing table consists of routing entries that specify the destination and the next-hop router through which the packets should be forwarded to reach the destination. Route calculation consists of determining a route to the destination: network, subnet, network prefix, or host.

Figure 1.1 Generic architecture of a router. (From Aweya, J., Journal of Systems Architecture, 46, 6, 2000. With permission.)

In static routing, the routing table entries are created by default when an interface is configured (for directly connected interfaces), added by, for example, the route command (normally from a system bootstrap file), or created by an Internet Control Message Protocol (ICMP) redirect (usually when the wrong default is used) [8]. Once configured, the network paths will not change. With static routing, a router may issue an alarm when it recognizes that a link has gone down, but will not automatically reconfigure the routing table to reroute the traffic around the disabled link. Static routing, used in LANs over limited distances, requires basically the network manager to configure the routing table. Thus, static routing is fine if the network is small, there is a single connection point to other networks, and there are no redundant routes (where a backup route can be used if a primary route fails). Dynamic routing is normally used if any of these three conditions do not hold true.

Dynamic routing, used in Internetworking across wide area networks, automatically reconfigures the routing table and recalculates the least expensive path. In this case, routers broadcast advertisement packets (signifying their presence) to all network nodes and communicate with other routers about their network connections, the cost of connections, and their load levels. Convergence, or reconfiguration of the routing tables, must occur quickly, before routers with incorrect information misroute data packets into dead ends. Some dynamic routers can also rebalance the traffic load.

The use of dynamic routing does not change the way an IP forwarding engine performs routing at the IP layer. What changes is the information placed in the routing table—instead of coming from the route commands in bootstrap files, the routes are added and deleted dynamically by a routing protocol, as routes change over time. The routing protocol adds a routing policy to the system, choosing which routes to place in the routing table. If the protocol finds multiple routes to a destination, the protocol chooses which route is the best, and which one to insert in the table. If the protocol finds that a link has gone down, it can delete the affected routes or add alternate routes that bypass the problem.

A network (including several networks administered as a whole) can be defined as an autonomous system. A network owned by a corporation, an Internet Service Provider (ISP), or a university campus often defines an autonomous system. There are two principal routing protocol types: those that operate within an autonomous system, or the Interior Gateway Protocols (IGPs), and those that operate between autonomous systems, or Exterior Gateway Protocols (EGPs). Within an autonomous system, any protocol may be used for route discovery, propagating, and validating routes. Each autonomous system can be independently administered and must make routing information available to other autonomous systems. The major IGPs include RIP, OSPF, and Intermediate System to Intermediate System (IS–IS). Some EGPs include EGP and Border Gateway Protocol (BGP).

1.3.2 Packet Forwarding

In this section, we briefly review the forwarding process in IPv4 routers. More details of the forwarding requirements are given in Ref. [9]. A router receives an IP packet on one of its interfaces and then forwards the packet out of another of its interfaces (or possibly more than one, if the packet is a multicast packet), based on the contents of the IP header. As the packet is forwarded hop by hop, the packet’s (original) network layer header (IP header) remains relatively unchanged, containing the complete set of instructions on how to forward the packet (IP tunneling may call for prepending the packet with other IP headers in the network). However, the data-link headers and physical-transmission schemes may change radically at each hop to match the changing media types.

Suppose that the router receives a packet from one of its attached network segments, the router verifies the contents of the IP header by checking the protocol version, header length, packet length, and header checksum fields. The protocol version must be equal to 4 for IPv4, for which the header length must be greater than or equal to the minimum IP header size (20 bytes). The length of the IP packet, expressed in bytes, must also be larger than the minimum header size. In addition, the router checks that the entire packet has been received by checking the IP packet length against the size of the received Ethernet packet, for example, in the case where the interface is attached to an Ethernet network. To verify that none of the fields of the header have been corrupted, the 16-bit ones-complement checksum of the entire IP header is calculated and verified to be equal to 0×ffff. If any of these basic checks fail, the packet is deemed to be malformed and is discarded without sending an error indication back to the packet’s originator.

Next, the router verifies that the time-to-live (TTL) field is greater than 1. The...