![Cisco-Gigabit-Switch-Router-Performance-Route-Processor-0a](https://upload.wikimedia.org/wikipedia/commons/4/4f/Cisco-Gigabit-Switch-Router-Performance-Route-Processor-0a.jpg)
In
routing
Routing is the process of selecting a path for traffic in a network or between or across multiple networks. Broadly, routing is performed in many types of networks, including circuit-switched networks, such as the public switched telephone netw ...
, the forwarding plane, sometimes called the data plane or user plane, defines the part of the
router architecture that decides what to do with packets arriving on an inbound interface. Most commonly, it refers to a table in which the router looks up the destination address of the incoming packet and retrieves the information necessary to determine the path from the receiving element, through the internal forwarding fabric of the router, and to the proper outgoing interface(s).
In certain cases the table may specify that a packet is to be discarded. In such cases, the router may return an ICMP "destination unreachable" or other appropriate code. Some security policies, however, dictate that the router should drop the packet silently, in order that a potential attacker does not become aware that a target is being protected.
The incoming forwarding element will also decrement the time-to-live (TTL) field of the packet, and, if the new value is zero, discard the packet. While the
Internet Protocol
The Internet Protocol (IP) is the network layer communications protocol in the Internet protocol suite for relaying datagrams across network boundaries. Its routing function enables internetworking, and essentially establishes the Internet.
IP h ...
(IP) specification indicates that an
Internet Control Message Protocol
The Internet Control Message Protocol (ICMP) is a supporting protocol in the Internet protocol suite. It is used by network devices, including routers, to send error messages and operational information indicating success or failure when communi ...
(ICMP)
time exceeded message should be sent to the originator of the packet (i.e. the node indicated by the source address), the router may be configured to drop the packet silently (again according to security policies).
Depending on the specific router implementation, the table in which the destination address is looked up could be the
routing table
In computer networking, a routing table, or routing information base (RIB), is a data table stored in a router or a network host that lists the routes to particular network destinations, and in some cases, metrics (distances) associated with tho ...
(also known as the routing information base, RIB), or a separate
forwarding information base
A forwarding information base (FIB), also known as a forwarding table or MAC table, is most commonly used in network bridging, routing, and similar functions to find the proper output network interface controller to which the input interface shou ...
(FIB) that is populated (i.e., loaded) by the
routing control plane, but used by the forwarding plane for look-ups at much higher speeds. Before or after examining the destination, other tables may be consulted to make decisions to drop the packet based on other characteristics, such as the source address, the IP protocol identifier field, or
Transmission Control Protocol
The Transmission Control Protocol (TCP) is one of the main protocols of the Internet protocol suite. It originated in the initial network implementation in which it complemented the Internet Protocol (IP). Therefore, the entire suite is commonly ...
(TCP) or
User Datagram Protocol
In computer networking, the User Datagram Protocol (UDP) is one of the core communication protocols of the Internet protocol suite used to send messages (transported as datagrams in packets) to other hosts on an Internet Protocol (IP) network. ...
(UDP) port number.
Forwarding plane functions run in the forwarding element. High-performance routers often have multiple distributed forwarding elements, so that the router increases performance with parallel processing.
The outgoing interface will
encapsulate the packet in the appropriate data link protocol. Depending on the router software and its configuration, functions, usually implemented at the outgoing interface, may set various packet fields, such as the
DSCP field used by
differentiated services
Differentiated services or DiffServ is a computer networking architecture that specifies a mechanism for classifying and managing network traffic and providing quality of service (QoS) on modern IP networks. DiffServ can, for example, be used t ...
.
In general, the passage from the input interface directly to an output interface, through the fabric with minimum modification at the output interface, is called the ''fast path'' of the router. If the packet needs significant processing, such as segmentation or encryption, it may go onto a slower path, which is sometimes called the ''services plane'' of the router. Service planes can make forwarding or processing decisions based on higher-layer information, such as a Web URL contained in the packet payload.
Data plane
The data plane is the part of the
software
Software is a set of computer programs and associated documentation and data. This is in contrast to hardware, from which the system is built and which actually performs the work.
At the lowest programming level, executable code consists ...
that processes the data requests. By contrast, the
control plane
In network routing, the control plane is the part of the router architecture that is concerned with drawing the network topology, or the information in a routing table that defines what to do with incoming packets. Control plane functions, such as ...
is the part of the software that configures and shuts down the data plane.
The conceptual separation of the data plane from the control plane has been done for years.
[ An early example is ]Unix
Unix (; trademarked as UNIX) is a family of multitasking, multiuser computer operating systems that derive from the original AT&T Unix, whose development started in 1969 at the Bell Labs research center by Ken Thompson, Dennis Ritchie, and ot ...
, where the basic file operations are open, close for the control plane and read, write for the data plane.
The conceptual separation of the data plane from the control plane in software programming has proven useful in the packet switching
In telecommunications, packet switching is a method of grouping Data (computing), data into ''network packet, packets'' that are transmitted over a digital Telecommunications network, network. Packets are made of a header (computing), header and ...
field where it originated. In networking, the data plane is sometimes referred to as the forwarding plane, as it separates the concerns: the data plane is optimized for speed of processing, and for simplicity and regularity. The control plane is optimized so as to allow configuration
Configuration or configurations may refer to:
Computing
* Computer configuration or system configuration
* Configuration file, a software file used to configure the initial settings for a computer program
* Configurator, also known as choice board ...
, handling policies, handling exceptional situations, and in general facilitating and simplifying the data plane processing.
Issues in router forwarding performance
Vendors design router products for specific markets. Design of routers intended for home use, perhaps supporting several PCs and VoIP telephony, is driven by keeping the cost as low as possible. In such a router, there is no separate forwarding fabric, and there is only one active forwarding path: into the main processor and out of the main processor.
Routers for more demanding applications accept greater cost and complexity to get higher throughput in their forwarding planes.
Several design factors affect router forwarding performance:
* Data link layer processing and extracting the packet
* Decoding the packet header
* Looking up the destination address in the packet header
* Analyzing other fields in the packet
* Sending the packet through the "fabric" interconnecting the ingress and egress interfaces
* Processing and data link encapsulation at the egress interface
Routers may have one or more processors. In a uniprocessor design, these performance parameters are affected not just by the processor speed, but by competition for the processor. Higher-performance routers invariably have multiple processing elements, which may be general-purpose processor chips or specialized application-specific integrated circuit
An application-specific integrated circuit (ASIC ) is an integrated circuit (IC) chip customized for a particular use, rather than intended for general-purpose use, such as a chip designed to run in a digital voice recorder or a high-efficie ...
s (ASIC).
Very high performance products have multiple processing elements on each interface card. In such designs, the main processor does not participate in forwarding, but only in control plane and management processing.
Benchmarking performance
In the Internet Engineering Task Force
The Internet Engineering Task Force (IETF) is a standards organization for the Internet and is responsible for the technical standards that make up the Internet protocol suite (TCP/IP). It has no formal membership roster or requirements and a ...
, two working groups in the Operations & Maintenance Area deal with aspects of performance. The Interprovider Performance Measurement (IPPM) group focuses, as its name would suggest, on operational measurement of services. Performance measurements on single routers, or narrowly defined systems of routers, are the province of the Benchmarking Working Group (BMWG).
RFC 2544 is the key BMWG document. A classic RFC 2544 benchmark uses half the router's (i.e., the device under test (DUT)) ports for input of a defined load, and measures the time at which the outputs appear at the output ports.
Forwarding information base design
Originally, all destinations were looked up in the RIB. Perhaps the first step in speeding routers was to have a separate RIB and FIB in main memory, with the FIB, typically with fewer entries than the RIB, being organized for fast destination lookup. In contrast, the RIB was optimized for efficient updating by routing protocols.
Early uniprocessing routers usually organized the FIB as a hash table
In computing, a hash table, also known as hash map, is a data structure that implements an associative array or dictionary. It is an abstract data type that maps keys to values. A hash table uses a hash function to compute an ''index'', als ...
, while the RIB might be a linked list
In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes whic ...
. Depending on the implementation, the FIB might have fewer entries than the RIB, or the same number.
When routers started to have separate forwarding processors, these processors usually had far less memory than the main processor, such that the forwarding processor could hold only the most frequently used routes. On the early Cisco AGS+ and 7000, for example, the forwarding processor cache could hold approximately 1000 route entries. In an enterprise, this would often work quite well, because there were fewer than 1000 server or other popular destination subnets. Such a cache, however, was far too small for general Internet routing. Different router designs behaved in different ways when a destination was not in the cache.
Cache miss issues
A cache miss condition might result in the packet being sent back to the main processor, to be looked up in a slow path that had access to the full routing table. Depending on the router design, a cache miss might cause an update to the fast hardware cache or the fast cache in main memory. In some designs, it was most efficient to invalidate the fast cache for a cache miss, send the packet that caused the cache miss through the main processor, and then repopulate the cache with a new table that included the destination that caused the miss. This approach is similar to an operating system with virtual memory, which keeps the most recently used information in physical memory.
As memory costs went down and performance needs went up, FIBs emerged that had the same number of route entries as in the RIB, but arranged for fast lookup rather than fast update. Whenever a RIB entry changed, the router changed the corresponding FIB entry.
FIB design alternatives
High-performance FIBs achieve their speed with implementation-specific combinations of specialized algorithms and hardware.
Software
Various search algorithm
In computer science, a search algorithm is an algorithm designed to solve a search problem. Search algorithms work to retrieve information stored within particular data structure, or calculated in the search space of a problem domain, with eith ...
s have been used for FIB lookup. While well-known general-purpose data structures were first used, such as hash tables
In computing, a hash table, also known as hash map, is a data structure that implements an associative array or dictionary. It is an abstract data type that maps keys to values. A hash table uses a hash function to compute an ''index'', als ...
, specialized algorithms, optimized for IP addresses, emerged. They include:
* Binary tree
In computer science, a binary tree is a k-ary k = 2 tree data structure in which each node has at most two children, which are referred to as the ' and the '. A recursive definition using just set theory notions is that a (non-empty) binary t ...
* Radix tree
In computer science, a radix tree (also radix trie or compact prefix tree or compressed trie) is a data structure that represents a space-optimized trie (prefix tree) in which each node that is the only child is merged with its parent. The resul ...
* Four-way trie
* Patricia tree
In computer science, a radix tree (also radix trie or compact prefix tree or compressed trie) is a data structure that represents a space-optimized trie (prefix tree) in which each node that is the only child is merged with its parent. The resu ...
A multicore CPU architecture is commonly used to implement high-performance networking systems. These platforms facilitate the use of a software architecture in which the high-performance packet processing is performed within a fast path environment on dedicated cores, in order to maximize system throughput. A run-to-completion model minimizes OS overhead and latency.
Hardware
Various forms of fast RAM and, eventually, basic content-addressable memory
Content-addressable memory (CAM) is a special type of computer memory used in certain very-high-speed searching applications. It is also known as associative memory or associative storage and compares input search data against a table of stored d ...
(CAM) were used to speed lookup. CAM, while useful in layer 2 switches that needed to look up a relatively small number of fixed-length MAC address
A media access control address (MAC address) is a unique identifier assigned to a network interface controller (NIC) for use as a network address in communications within a network segment. This use is common in most IEEE 802 networking techno ...
es, had limited utility with IP addresses having variable-length routing prefixes (see Classless Inter-Domain Routing
Classless Inter-Domain Routing (CIDR ) is a method for allocating IP addresses and for IP routing. The Internet Engineering Task Force introduced CIDR in 1993 to replace the previous classful network addressing architecture on the Internet. Its g ...
). Ternary CAM (CAM), while expensive, lends itself to variable-length prefix lookups.
One of the challenges of forwarder lookup design is to minimize the amount of specialized memory needed, and, increasingly, to minimize the power consumed by memory.
Distributed forwarding
A next step in speeding routers was to have a specialized forwarding processor separate from the main processor. There was still a single path, but forwarding no longer had to compete with control in a single processor. The fast routing processor typically had a small FIB, with hardware memory (e.g., static random-access memory
Static random-access memory (static RAM or SRAM) is a type of random-access memory (RAM) that uses latching circuitry (flip-flop) to store each bit. SRAM is volatile memory; data is lost when power is removed.
The term ''static'' differen ...
(SRAM)) faster and more expensive than the FIB in main memory. Main memory was generally dynamic random-access memory
Dynamic random-access memory (dynamic RAM or DRAM) is a type of random-access semiconductor memory that stores each bit of data in a memory cell, usually consisting of a tiny capacitor and a transistor, both typically based on metal-oxide ...
(DRAM).
Early distributed forwarding
Next, routers began to have multiple forwarding elements, that communicated through a high-speed shared bus or through a shared memory. Cisco used shared busses until they saturated, while Juniper preferred shared memory.
Each forwarding element had its own FIB. See, for example, the Versatile Interface Processor on the Cisco 7500Hardware Architecture of the Cisco 7500 Router
''Inside Cisco IOS Software Architecture (CCIE Professional Development'', V. Bollapragada ''et al.'',Cisco Press, 2000
Eventually, the shared resource became a bottleneck, with the limit of shared bus speed being roughly 2 million packets per second (Mpps). Crossbar fabrics broke through this bottleneck.
Shared paths become bottlenecks
As forwarding bandwidth increased, even with the elimination of cache miss overhead, the shared paths limited throughput. While a router might have 16 forwarding engines, if there was a single bus, only one packet transfer at a time was possible. There were some special cases where a forwarding engine might find that the output interface was one of the logical or physical interfaces present on the forwarder card, such that the packet flow was totally inside the forwarder. It was often easier, however, even in this special case, to send the packet out the bus and receive it from the bus.
While some designs experimented with multiple shared buses, the eventual approach was to adapt the
crossbar switch
In electronics and telecommunications, a crossbar switch (cross-point switch, matrix switch) is a collection of switches arranged in a matrix configuration. A crossbar switch has multiple input and output lines that form a crossed pattern of int ...
model from telephone switches, in which every forwarding engine had a hardware path to every other forwarding engine. With a small number of forwarding engines, crossbar forwarding fabrics are practical and efficient for high-performance routing. There are multistage designs for crossbar systems, such as
Clos networks.
See also
*
Control plane
In network routing, the control plane is the part of the router architecture that is concerned with drawing the network topology, or the information in a routing table that defines what to do with incoming packets. Control plane functions, such as ...
*
Management plane
*
Network processor
A network processor is an integrated circuit which has a feature set specifically targeted at the networking application domain.
Network processors are typically software programmable devices and would have generic characteristics similar to gene ...
*
Network search engine Computer networks are connected together to form larger networks such as campus networks, corporate networks, or the Internet. Routers are network devices that may be used to connect these networks (e.g., a home network connected to the network of ...
References
{{reflist
Internet architecture
*