Routing Algorithms

Routing Algorithms

Routing refers to the process of forwarding messages through switching networks. In some cases, routing information is programmed into the switching devices. However, preprogrammed switches cannot adjust to changing network conditions. Most routing devices, therefore, are dynamic, which means that they have the capability of discovering routes through the internetwork and then storing the route information in route tables.

Route tables do not store only path information. They also store estimates of the time taken to send a message through a given route. This time estimate is known as the cost of a particular path. Some of the methods of estimating routing costs are as follows:

Hop count. This method describes the number of routers that a message might cross before it reaches its destination. If all hops are assumed to take the same amount of time, the optimum path is the path with the smallest hop count.
Tic count. This method provides an actual time estimate, where a tic is a time unit as defined by the routing implementation.
Relative expense. This method calculates any defined measure of the cost (including the monetary cost) to use a given link.

After costs are established, routers can select routes, either statically or dynamically, as follows:

Static route selection. This selection method uses routes that have been programmed by the network administrator.
Dynamic route selection. Under this selection method, routing cost information is used to select the most cost- effective route for a given packet. As network conditions change and are reflected in routing tables, the router can select different paths to maintain low costs.

Two common methods of discovering routes are distance vector routing and link-state routing. Both are discussed in the following sections.

Further Information