Routing table
Encyclopedia
In computer networking a routing table, or Routing Information Base (RIB), is a data table stored in a router or a networked computer
that lists the routes to particular network destinations, and in some cases, metrics
(distances) associated with those routes. The routing table contains information about the topology
of the network immediately around it. The construction of routing tables is the primary goal of routing protocol
s. Static routes are entries made in a routing table by non-automatic means and which are fixed rather than being the result of some network topology 'discovery' procedure.
needs to send data to another node on a network, it must know where to send it, first. If the node cannot directly connect to the destination node, it has to send it via other nodes along a proper route to the destination node. Most nodes do not try to figure out which route(s) might work; instead, a node will send an IP
packet to a gateway in the LAN
, which then decides how to route the "package" of data to the correct destination. Each gateway will need to keep track of which way to deliver various packages of data, and for this it uses a Routing Table. A routing table is a database which keeps track of paths, like a map, and allows the gateway to provide this information to the node requesting the information.
With hop-by-hop routing, each routing table lists, for all reachable destinations, the address of the next device along the path to that destination: the next hop. Assuming that the routing tables are consistent, the simple algorithm of relaying packets to their destination's next hop thus suffices to deliver data anywhere in a network. Hop-by-hop is the fundamental characteristic of the IP Internetwork Layer and the OSI Network Layer
.
(CIDR).
Since in a network each node presumably possesses a valid routing table, routing tables must be consistent among the various nodes or routing loops can develop. This is particularly problematic in the hop-by-hop routing model in which the net effect of inconsistent tables in several different routers could be to forward packets in an endless loop. Routing loops have historically plagued routing, and their avoidance is a major design goal of routing protocols.
Depending on the application and implementation, it can also contain additional values that refine path selection:
Routing tables are also a key aspect of certain security operations, such as unicast reverse path forwarding (uRPF). In this technique, which has several variants, the router also looks up, in the routing table, the source address of the packet. If there exists no route back to the source address, the packet is assumed to be malformed or involved in a network attack, and is dropped.
Shown below is an example of what the table above could look like on an average computer connected to the internet via a home router:
.
This router architecture separates the Control Plane
function of the routing table from the Forwarding Plane
function of the forwarding table. This separation of control and forwarding provides uninterrupted forwarding in production environments, along with enhanced performance.
Computer
A computer is a programmable machine designed to sequentially and automatically carry out a sequence of arithmetic or logical operations. The particular sequence of operations can be changed readily, allowing the computer to solve more than one kind of problem...
that lists the routes to particular network destinations, and in some cases, metrics
Metrics (networking)
Metrics is a property of a route in computer networking, consisting of any value used by routing algorithms to determine whether one route should perform better than another. The routing table stores only the best possible routes, while link-state or topological databases may store all other...
(distances) associated with those routes. The routing table contains information about the topology
Network topology
Network topology is the layout pattern of interconnections of the various elements of a computer or biological network....
of the network immediately around it. The construction of routing tables is the primary goal of routing protocol
Routing protocol
A routing protocol is a protocol that specifies how routers communicate with each other, disseminating information that enables them to select routes between any two nodes on a computer network, the choice of the route being done by routing algorithms. Each router has a priori knowledge only of...
s. Static routes are entries made in a routing table by non-automatic means and which are fixed rather than being the result of some network topology 'discovery' procedure.
Basics
A routing table utilizes the same idea that one does when using a map in package delivery. Whenever a nodeNode (networking)
In communication networks, a node is a connection point, either a redistribution point or a communication endpoint . The definition of a node depends on the network and protocol layer referred to...
needs to send data to another node on a network, it must know where to send it, first. If the node cannot directly connect to the destination node, it has to send it via other nodes along a proper route to the destination node. Most nodes do not try to figure out which route(s) might work; instead, a node will send an IP
Internet Protocol
The Internet Protocol is the principal communications protocol used for relaying datagrams across an internetwork using the Internet Protocol Suite...
packet to a gateway in the LAN
Local area network
A local area network is a computer network that interconnects computers in a limited area such as a home, school, computer laboratory, or office building...
, which then decides how to route the "package" of data to the correct destination. Each gateway will need to keep track of which way to deliver various packages of data, and for this it uses a Routing Table. A routing table is a database which keeps track of paths, like a map, and allows the gateway to provide this information to the node requesting the information.
With hop-by-hop routing, each routing table lists, for all reachable destinations, the address of the next device along the path to that destination: the next hop. Assuming that the routing tables are consistent, the simple algorithm of relaying packets to their destination's next hop thus suffices to deliver data anywhere in a network. Hop-by-hop is the fundamental characteristic of the IP Internetwork Layer and the OSI Network Layer
Network Layer
The network layer is layer 3 of the seven-layer OSI model of computer networking.The network layer is responsible for packet forwarding including routing through intermediate routers, whereas the data link layer is responsible for media access control, flow control and error checking.The network...
.
Difficulties with routing tables
The need to record routes to large numbers of devices using limited storage space represents a major challenge in routing table construction. In the Internet, the currently dominant address aggregation technology is a bitwise prefix matching scheme called Classless Inter-Domain RoutingClassless Inter-Domain Routing
Classless Inter-Domain Routing is a method for allocating IP addresses and routing Internet Protocol packets. The Internet Engineering Task Force introduced CIDR in 1993 to replace the previous addressing architecture of classful network design in the Internet...
(CIDR).
Since in a network each node presumably possesses a valid routing table, routing tables must be consistent among the various nodes or routing loops can develop. This is particularly problematic in the hop-by-hop routing model in which the net effect of inconsistent tables in several different routers could be to forward packets in an endless loop. Routing loops have historically plagued routing, and their avoidance is a major design goal of routing protocols.
Contents of routing tables
The routing table consists of at least three information fields:- the network id: i.e. the destination network id
- cost: i.e. the cost or metric of the path through which the packet is to be sent
- next hop: The next hop, or gateway, is the address of the next station to which the packet is to be sent on the way to its final destination
Depending on the application and implementation, it can also contain additional values that refine path selection:
- quality of service associated with the route. For example, the U flag indicates that an IP route is up.
- links to filtering criteria/access lists associated with the route
- interface: such as eth0 for the first Ethernet card, eth1 for the second Ethernet card, etc.
Routing tables are also a key aspect of certain security operations, such as unicast reverse path forwarding (uRPF). In this technique, which has several variants, the router also looks up, in the routing table, the source address of the packet. If there exists no route back to the source address, the packet is assumed to be malformed or involved in a network attack, and is dropped.
| Network id | Cost | Next hop |
|---|---|---|
| ........ | ........ | ........ |
| ........ | ........ | ........ |
Shown below is an example of what the table above could look like on an average computer connected to the internet via a home router:
| Network Destination | Netmask | Gateway | Interface | Metric |
|---|---|---|---|---|
| 0.0.0.0 | 0.0.0.0 | 192.168.0.1 | 192.168.0.100 | 10 |
| 127.0.0.0 | 255.0.0.0 | 127.0.0.1 | 127.0.0.1 | 1 |
| 192.168.0.0 | 255.255.255.0 | 192.168.0.100 | 192.168.0.100 | 10 |
| 192.168.0.100 | 255.255.255.255 | 127.0.0.1 | 127.0.0.1 | 10 |
| 192.168.0.255 | 255.255.255.255 | 192.168.0.100 | 192.168.0.100 | 10 |
- The columns Network Destination and Netmask together describe the Network id as mentioned earlier. For example, destination 192.168.0.0 and netmask 255.255.255.0 can be written as network id 192.168.0.0/24.
- The Gateway column contains the same information as the Next hop, i. e. it points to the gateway through which the network can be reached.
- The Interface indicates what locally available interface is responsible for reaching the gateway. In this example, gateway 192.168.0.1 (the internet router) can be reached through the local network card with address 192.168.0.100.
- Finally, the Metric indicates the associated cost of using the indicated route. This is useful for determining the efficiency of a certain route from two points in a network. In this example, it is more efficient to communicate with the computer itself through the use of address 127.0.0.1 (called “localhost”) than it would be through 192.168.0.100 (the IP address of the local network card).
Forwarding table
Routing tables are generally not used directly for packet forwarding in modern router architectures; instead, they are used to generate the information for a smaller forwarding table. A forwarding table contains only the routes which are chosen by the routing algorithm as preferred routes for packet forwarding. It is often in a compressed or pre-compiled format that is optimized for hardware storage and lookupLookup
In computing, lookup usually refers to searching a data structure for an item that satisfies some specified property. For example, variable lookup performed by a language interpreter, virtual machine or other similar engine usually consists of performing certain...
.
This router architecture separates the Control Plane
Control plane
In routing, the control plane is the part of the router architecture that is concerned with drawing the network map, or the information in a routing table that defines what to do with incoming packets. Control plane functions, such as participating in routing protocols, run in the architectural...
function of the routing table from the Forwarding Plane
Forwarding plane
In routing, the forwarding plane, sometimes called the data plane, defines the part of the router architecture that decides what to do with packets arriving on an inbound interface...
function of the forwarding table. This separation of control and forwarding provides uninterrupted forwarding in production environments, along with enhanced performance.
See also
- Route summarization
- Forwarding table
- Packet forwarding
- Luleå algorithmLuleå algorithmThe Luleå algorithm of computer science, designed by , is a patented technique for storing and searching internet routing tables efficiently. It is named after the Luleå University of Technology, the home institute of the technique's authors...