DocumentCode :
160424
Title :
A heuristic overlay multicast routing algorithm for minimum delay optimization
Author :
Longxin Lin
Author_Institution :
Coll. of Inf. Sci. & Technol., Jinan Univ., Guangzhou, China
fYear :
2014
fDate :
11-13 July 2014
Firstpage :
1
Lastpage :
6
Abstract :
Multicast services can be provided either as a basic network service by IP multicast or as an application layer service called overlay multicast. How to build an efficient data delivery structure is the most critical problem for overlay multicast, which depends on a good routing algorithm. Many routing algorithms have been presented recent years. Some algorithms modeled overlay multicast´s routing problem as a degree constrained spanning tree problem based on undirected completed graph, and some others were built on some special peer to peer routing protocols. However, detecting and obtaining a completed graph´s all network state information needs consume expensive cost and restricts its scalability and sometime be impossible. On the contrary these routing algorithms built on p2p scheme are of good scalability but maybe fail in practical applications. This paper redefines the overlay multicast routing problem as to find a degree constrained sub-tree with minimum delay optimization for a general undirected connected graph not a completed graph. It is a NP-hard problem. A heuristic genetic algorithm for this problem is given and the simulation results verify its effectiveness.
Keywords :
IP networks; directed graphs; genetic algorithms; overlay networks; peer-to-peer computing; routing protocols; IP multicast; NP-hard problem; constrained spanning tree problem; data delivery structure; heuristic genetic algorithm; heuristic overlay multicast routing algorithm; minimum delay optimization; multicast services; network service; peer to peer routing protocols; undirected completed graph; Algorithm design and analysis; Delays; Genetic algorithms; Overlay networks; Routing; Sociology; Statistics; Genetic Algorithm; Overlay Multicast; Routing Algorithm;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Computing, Communication and Networking Technologies (ICCCNT), 2014 International Conference on
Conference_Location :
Hefei
Print_ISBN :
978-1-4799-2695-4
Type :
conf
DOI :
10.1109/ICCCNT.2014.6963071
Filename :
6963071
Link To Document :
بازگشت