Routing Algorithm in Networks on the Globe

Abstract

Packet switching of data in networks is done by either the distance-vector or the link-state routing protocols. These protocols use the Bellman-Ford and the Dijkstra's algorithms re-spectively for the least cost path from a source base station to a destination station. For inter-network transmission, the path-vector routing protocol is in use. With progress oftime, the network topologies are becoming huge in size, requiring large demand on book keeping of routing tables and transmission of the data packets dynamically to several otherstations of the network by broadcast, increasing the load on the network. Here, assuming the router stations to be terrestrially located with links along the ground, a large networkis assumed to lie on a spherical surface, and so the shortest geodesic path from source to destination becomes a great circular arc. For fast transmission, the cost of a link to a nodeis multicast to its neighboring nodes only for selection of the path lying as close as possible to the geodesic line between the source and the destination. As the arrival and dispatchof data packets at a nodal station occurs randomly, the cost of a link is estimated in this paper by the waiting time of a queueing process. This process at a router station is thus modeled by the Markovian M=M=c model, where c is the number of servers at the router station. If other commercial xed charge is involved for the use of a link, then that can be included in the total cost of a link. Finally, a method of search of a mobile destinationis also presented using sphericity of the network. Algorithms for the near geodesic path, costs of links as waiting times and destination search in mobile environment are clearlypresented.