Distributed Routing

For routing in a network having two or more routers, routing tables are used to determine the destination to which a packet is to be forwarded. If two or m9re routes are available, the route that requires the least possible cost (link cost) should be selected so that the packet can be sent to the destination more quickly and more reliably. Cost can be generally considered as the number of routers via which the packet is to be sent. If changes are made to this network configuration, there are two methods to update the contents of routing tables, which will be described next.

Link Cost

Link cost can be defined in a variety of ways. Routing algorithm, on the other hand, functions regardless of the intention with which link cost has been specified. If there is no specific intention, the cost for a single link is usually set at 1. In this case, only the number of hops is taken into consideration. Calculations for determining the route are made on the assumption that the route with the minimum number of hops is the optimum route. If response time is important, the route with the minimum delay will be the best choice. For example, if there are two routes, one in which packets are sent over a single 9600 bps line, and the other in which packets are sent over two 100 Mbps FDDI lines, the latter route is better because there is less delay although there are more hops. To ensure that route calculations are performed in this way, the cost should be smaller for a link with smaller delay, and the cost should be larger for a link with larger delay.

Also, the user may wish to minimize the communication cost. For example, if user has a choice between two routes, i.e. packet switching network in which he is billed for the amount of communication made and leased line in which the cost is fixed; the latter route will not result in additional cost. Therefore, leased line is better from the point of view of cost. In ·this case, link cost must be proportional to cost arising from use of that link.

Load Distribution Methods

If there are two or more routes to reach the same destination at the same cost, throughput can improve because load is distributed. In addition, delay can be reduced because traffic per route is reduced. Therefore, it is useful to be able to perform multipath routing when two or more routes are available at the same cost. Multipath routing can be achieved in both distance-vector type and link-state type. If there are two or more routes to reach the same destination at the same cost, one of the following methods is applicable to determine which of these routes is to be used and how to select this route.

Round robin method Sequentially selects each of the routes

Random election method With the round robin method, there will be a difference in traffic between routes because packet lengths are different. To solve this problem, random numbers and, so on are used to randomly select the route

Mixed method Mixture of the above two methods, with also route availability taken into consideration and selects the route that b comparatively less busy.

The mixed method seems superior to other methods in that the availability routes are taken into consideration. In the mixed method, however, the router must check in real-time whether routes are available. Therefore, this method remains ineffective for the amount of processing required.