Performance analysis of multicast routing algorithms

Author

Papadimitriou, Dimitri ; Careglio, Davide ; Demeester, Piet

Author_Institution

Alcatel-Lucent, Antwerp, Belgium

fYear

2014

fDate

3-6 Feb. 2014

Firstpage

455

Lastpage

461

Abstract

This paper provides a theoretical performance analysis of different classes of multicast routing algorithms, namely the Shortest Path Tree, the Steiner Tree, compact routing and greedy routing. Our motivation is to determine the routing scheme which would yield the best trade-off between the stretch of the multicast routing paths, the memory space required to store the routing information and routing table as well as the communication cost. For this purpose, we also confront these results to those obtained by simulation on the CAIDA map of the Internet topology comprising 32k nodes.

Keywords

Internet; greedy algorithms; multicast communication; multimedia communication; network theory (graphs); telecommunication network routing; telecommunication network topology; trees (mathematics); CAIDA map; Internet topology; Steiner tree; communication cost; compact routing; greedy routing; memory space; multicast routing algorithm; routing information storage; routing table; shortest path tree; Algorithm design and analysis; Memory management; Performance analysis; Performance evaluation; Routing; Unicast; Upper bound; algorithm; multicast; performance; routing;

fLanguage

English

Publisher

ieee

Conference_Titel

Computing, Networking and Communications (ICNC), 2014 International Conference on

Conference_Location

Honolulu, HI

Type

conf

DOI

10.1109/ICCNC.2014.6785378

Filename

6785378