Routing Algorithm in Networks on the Globe

Sujit Kumar Bose

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.

Full Text:

PDF

References


M. Abramowitz and I.A. Stegun, Hand-

book of Mathematical Functions,Dover

Publications, New York, (1972)

M. Arellano-Vazquez, M. Benitez-Perez,

J. Ortega-Arjono, A consensus routing algo-

rithm for mobile distributed systems, Int. J.

of Distributed Sensor Networks, 11, (2015)

R.E. Bellman, On a routing problem,

Quart. Appl. Math. 16, (1958), 87-90

S.K. Bose, Operations Research Meth-

ods, Narosa Publishing, New Delhi, (2012)

C. Busch, Tirthapura: Analysis of Rout-

ing Algorithms, SIAM J. Comput. 35, 305-

, (2005)

Cisco Systems: IOS IP Routing, RIP

Conguration Guide (2011)

Cisco Systems: An Introduction to

IGRP, (2005)

Cisco Systems: IOS IP Routing, OSPF

Command Reference (2011)

T.H. Cormen, C.E. Leiserson, R.L.

Rivest, C. Stein, Introduction to Algo-

rithms, McGraw-Hill (2009), 651-655

A. Dutta, H. Schulzrine, Mobility Pro-

tocols and Handover Optimization, John

Wiley, New York, (2014)

L.R. Ford, Network Flow Theory,

RAND Corporation paper P-923, Santa

Monica, California (1956)

P. Li, S. Guo, S. yu, A.V. Vasilkos, Reli-

able Multicast with Pipelined Network Cod-

ing using Opportunistic Feeding and Rout-

ing, IEEE Transactions on Parallel and Dis-

tributed Systems, 25 (2014)




DOI: https://doi.org/10.31449/inf.v45i2.3200

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.