In shortest path (SP) routing, only the shortest path po between a source-and-destination pair is used to route traffic. However, if all data is ‘selfishly’ routed through po, degradation of network performance due to unregulated traffic along po may result. Recent studies show that multipath routing approaches that observe loop-free invariant (LFI) conditions improve network performance. Two new sets of criteria, loose-strain loop-free (LSLF) conditions and simple loose-strain loop-free (SLSLF) conditions, are defined. It is proved that in any given network, PLFIi→j⊆PLSLFi→j and PLFIi→j⊆PSLSLFi→j, where PLFIi→j, PLSLFi→j and PSLSLFi→j are the sets of paths from i to j found under LFI, LSLF and SLSLF conditions and also that any path pi→j∈PLSLFi→j or pi→j∈PSLSLFi→j is loop-free. A series of simulations were performed on many practical network topologies (e.g. APRANET and NSFNET). Favourable empirical results show that LSLF and SLSLF conditions outperform both LFI and SP in terms of average maximum flow and resource utilisation.
References
-
-
1)
-
Vutukury, S., Garcia-Luna-Aceves, J.J.: `MDVA: A distance-vector multipath routing protocol', Proc. IEEE INFOCOM’01, Anchorage, AK, USA, 1, p. 557–564.
-
2)
-
G.D. Caro ,
M. Dorigo
.
AntNet: Distributed stigmergetic control for communications networks.
J. Artif. Intell. Res.
,
317 -
365
-
3)
-
Bahk, S., Zarki, M.E.: `Dynamic multi-path routing and how it compares with other dynamic routing algorithms for high speed wide area network', Proc. ACM SIGCOMM’92, p. 53–64.
-
4)
-
`Enhanced interior gateway routing protocol white paper', 2003.
-
5)
-
Chen, J., Druschel, P., Subramanian, D.: `An efficient multipath forwarding method', Proc. IEEE INFOCOM’98, 1998, 3, p. 1418–1425.
-
6)
-
J.L. Sobrinho
.
Algebra and algorithms for QoS path computation and hop-by-hop routing in the Internet.
IEEE/ACM Trans. Netw.
,
4 ,
541 -
550
-
7)
-
Roughgarden, T., Tardos, E.: `How bad is selfish routing?', Proc. IEEE Symp. on Foundations of Computer Science, 2000, Redondo Beach, CA, USA, p. 93–102.
-
8)
-
Vutukury, S., Garcia-Luna-Aceves, J.J.: `A simple approximation to minimum-delay routing', Proc. ACM SIGCOMM’99, p. 227–238.
-
9)
-
Postel, J.: ‘Internet Protocol’, RFC791, 1981.
-
10)
-
Vutukury, S., Garcia-Luna-Aceves, J.J.: `A distributed algorithm for multipath computation', Proc. IEEE GLOBECOM’99, 3, p. 1689–1693.
-
11)
-
R. Gallager
.
A minimum delay routing algorithm using distributed computation.
IEEE Trans. Commun.
,
73 -
85
-
12)
-
C. Huiterma
.
(1999)
Routing in the Internet.
-
13)
-
Villamizar, C.: ‘OSPF optimized multipath (OSPF-OMP)’. Internet Draft, 1999.
http://iet.metastore.ingenta.com/content/journals/10.1049/ip-com_20040281
Related content
content/journals/10.1049/ip-com_20040281
pub_keyword,iet_inspecKeyword,pub_concept
6
6