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 respectively 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 of time, 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 other stations 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 network is 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 node is 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 dispatch of 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 fixed 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 destination is 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 clearly presented.