Routing

ROUTING

A switch or router needs to be able to look at the packet’s destination address and then to determine which of the output ports is the best choice to get the packet to that address.

The forwarding table is used when a packet is being forwarded and so must contain enough information to accomplish the forwarding function. This means that a row in the forwarding table contains the mapping from a network number to an outgoing interface and some MAC information, such as the Ethernet address of the next hop.

The routing table is the table that is built up by the routing algorithms as a precursor to building the forwarding table. It generally contains mappings from network numbers to next hops. It may also contain information about how this information was learned, so that the router will be able to decide when it should discard some information.

The forwarding table needs to be structured to optimize the process of looking up a network number when forwarding a packet, while the routing table needs to be optimized for the purpose of calculating changes in topology. The forwarding table may even be implemented in specialized hardware, whereas this is rarely if ever done for the routing table.

Example rows from (a) routing and (b) forwarding tables.

Network as a Graph

Routing is, in essence, a problem of graph theory. a graph representing a network. The nodes of the graph, labeled A through F, may be hosts, switches, routers, or networks. The edges of the graph correspond to the network links. Each edge has an associated cost, which gives some indication of the desirability of sending traffic over that link. The basic problem of routing is to find the lowest-cost path between any two nodes, where the cost of a path equals the sum of the costs of all the edges that make up the path.