Routing table
From Wikipedia, the free encyclopedia
Routing tables are used in computer networks to direct forwarding by matching destination addresses to the network paths used to reach them. The construction of routing tables is the primary goal of routing protocols.
In the simplest model, 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. In practice, hop-by-hop routing is being increasingly abandoned in favor of layered architectures such as MPLS, where a single routing table entry can effectively select the next several hops, resulting in reduced table lookups and improved performance.
The need to record routes to large numbers of devices using limited storage space represents a major challenge in routing table construction. Perhaps the fundamental assumptions of routing is that similar addresses are located near each other in the network, allowing groups of destination addresses to be matched by single routing table entries. The exact nature of how this grouping is done has changed over time and still represents an active area of networking research. In the Internet, the currently dominant address grouping technology is a bitwise prefix matching scheme called Classless Inter-Domain Routing.
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.
