Centralized Routing
Centralized routing means that all interconnection information is generated and maintained at a single central location. This location then broadcasts that information to all network nodes so that each may define its own routing table. One way to maintain routing information centrally is through a routing matrix. It consists of a row and column for each node in the network. A row corresponds to a source node and a column to a destination node. The entry in the position specified by the row and the column indicates the first node in the route from the source to the destination. From this, the entry to the entire route can be extract The routes selected are the cheapest one. In the case where there are two routes, both having the cheapest cost, one is chosen arbitrarily.
Consider again the route from A to F. According to the matrix's first row and six



columns, node B is the first one in the cheapest route. The next node is determined by considering the route from B to F.
Examining the second row and sixth column indicates that node E is the next. Finally, the node following E (node F) is found in the fifth row and sixth column. Thus, the route is from A to B to E to F.
Creating a routing table for a network node requires the row from the matrix corresponding to the node. For example, node A's routing table in Figure 10.4 (minus the cost, we did not include costs in the routing matrix but it is a simple matter to do so, by storing the cost with each node in the matrix) is the same as row 1 of the matrix. Similar statements apply for the other nodes.

 
 Distributed Routing
Distributed routing means there is no central control. Each node must determine and maintain its routing information independently. A node usually does this by knowing who its neighbours are, calculating the cost to get there and determining the cost for a neighbour to send data to specific destinations. Each neighbour, in turn, does the same thing. From the information each node can derive its own routing table. This method is more complex than centralized routing because it requires each node to communicate with each of its neighbours independently.
It is difficult to appreciate the complexity of this approach because examples typically show a global view of a network with its connection and their costs. This overview can bias the way we see the strategy unless we constantly remind ourselves that one node's knowledge of the entire network is very limited. To illustrate, consider the network shown in Figure columns, node B is the first one in the cheapest route. The next node is determined by considering the route from B to F.
Examining the second row and sixth column indicates that node E is the next. Finally, the node following E (node F) is found in the fifth row and sixth column. Thus, the route is from A to B to E to F.
Creating a routing table for a network node requires the row from the matrix corresponding to the node. For example, node A's routing table in Figure 10.4 (minus the cost, we did not include costs in the routing matrix but it is a simple matter to do so, by storing the cost with each node in the matrix) is the same as row 1 of the matrix. Similar statements apply for the other nodes.

Distributed Routing
Distributed routing means there is no central control. Each node must determine and maintain its routing information independently. A node usually does this by knowing who its neighbours are, calculating the cost to get there and determining the cost for a neighbour to send data to specific destinations. Each neighbour, in turn, does the same thing. From the information each node can derive its own routing table. This method is more complex than centralized routing because it requires each node to communicate with each of its neighbours independently.
It is difficult to appreciate the complexity of this approach because examples typically show a global view of a network with its connection and their costs. This overview can bias the way we see the strategy unless we constantly remind ourselves that one node's knowledge of the entire network is very limited. To illustrate, consider the network shown in Figure.

Assume that each node initially knows only the cost to its neighbour; later on, it can add to its information base anything its neighbours tell it. For example, A initially knows only that it can send something to B (Cost = 1) or to D (Cost = 2). It has no
knowledge whatsoever that nodes C and E even exist. Other nodes have similar knowledge (or lack of it). However, if neighbouring nodes communicate, A learns the identity of B's and D's neighbours and soon learns of nodes C and E. By learning of B's and D's costs to get there, and knowing the cost to get to B and D, node A can calculate the cost to get to C and E. By periodically exchanging information about neighbouring nodes, each one learns the identity of others in the network and the cheapest paths to them.
Static Routing
Static routing means that once a node determines its routing table, the node does not change it. In other words, the cheapest path is not dependent on time. There is the underlying assumption that the conditions that led to the table's definition have not changed. This is sometimes a valid assumption because costs often depend on distances and the data rates between intermediate nodes. Except for major equipment upgrades and moving of equipment, these parameters do not change.
Adaptive Routing
Static routing works well as long as network conditions do not change. In some networks, however, this is a bad assumption. For example, if the cost of each link depends on network traffic, it is time dependent. Consider the problem of sending packets from node A to node E in the network of Figure 10.5. The optimal route is A-D-C-E. Suppose that after node A transmits the packet to node D, the D-C link and the D-E link costs, each increases to 10 because of a surge of heavy traffic. The cheapest route from A is now A-B-C-E and the route on which the packet embarked initially is now very expensive. In this case it would actually be cheaper to send the packet back to A and start over again. An adaptive routing strategy allows a network node to respond to such changes and update its routing tables accordingly.
There are pitfalls of this system. For example, suppose that in our current example, D does send the packet back to A and then the cost of the A-B link increases to 10. The logical choice would be: send the packet back to D. You can now see the problem: conceivably, the packet could shuttle back and forth among several nodes,never making any progress towards its eventual destination. One technique to avoid this is to maintain a counter in the packet header that is incremented on each transmission. If the count exceeds some value, the packet is removed from the network. In such cases the routing logic will not guarantee delivery of the packets. However, there is usually a flow control protocol running at a higher layer, which will time out and respond the packet.
In general, adaptive routing is difficult to implement efficiently. Nodes can keep up with changing conditions only by getting reports from other nodes about link costs. These reports add to network traffic and, in turn, contribute more to the changing conditions. They also take time, so that by the time a node learns of a changing condition, that condition may no longer be in effect.
Table 10.1 gives a brief summary and comparison of the four types of routing.

BACK