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 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 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 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.