Name
Title | ||
|---|---|---|
An efficient multicast routing algorithm for delay-sensitive applications with dynamic membership |
Abstract | ||
|---|---|---|
We propose an algorithm for finding a multicast tree in packet-switched networks. The objective is to minimize total cost incurred at the multicast path. The routing model is based on the minimum cost Steiner tree problem. The Steiner problem is extended to incorporate two additional requirements. First, the delay experienced along the path from the source to each destination is bounded. Second, the destinations are allowed to join and leave multicasting anytime during a session. To minimize the disruption to on-going multicasting the algorithm adopts the idea of connecting a new destination to the current multicasting by a minimum cost path satisfying the delay bound. To find such a path is an NP-hard problem and an enumerative method relying on generation of delay bounded paths between node pairs is not likely to find a good routing path in acceptable computation time when network size is large. To cope with such difficulty, the proposed algorithm utilizes an optimization technique called Lagrangian relaxation method. A computational experiment is done on relatively dense and large Waxman's networks. The results seem to be promising. For sparse networks, the algorithm can find near-optimal multicast trees. Also the quality of multicast trees does not seem to deteriorate even when the network size grows. Furthermore, the experimental results shows that the computational efforts for each addition of node to the call are fairly moderate, namely the same as to solve a few shortest path problems |
Year | DOI | Venue |
|---|---|---|
1998 | 10.1109/INFCOM.1998.662961 | INFOCOM |
Keywords | Field | DocType |
packet switching,optimisation,multicast tree,delay bound,multicast routing algorithm,trees (mathematics),packet-switched networks,minimum cost path,np-hard problem,minimum cost steiner tree problem,near-optimal multicast trees,waxman's networks,delay-sensitive applications,delays,computational complexity,sparse networks,dynamic membership,telecommunication network routing,lagrangian relaxation method,optimization technique,shortest path problem,computer experiment,satisfiability,steiner tree problem | Source-specific multicast,Protocol Independent Multicast,Mathematical optimization,Shortest path problem,Steiner tree problem,Computer science,Xcast,Computer network,Suurballe's algorithm,Multicast,Distance Vector Multicast Routing Protocol,Distributed computing | Conference |
Volume | ISSN | ISBN |
3 | 0743-166X | 0-7803-4383-2 |
Citations | PageRank | References |
19 | 1.34 | 10 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sung-Pil Hong | 1 | 137 | 13.07 |
| Heesang Lee | 2 | 59 | 8.44 |
| Bum Hwan Park | 3 | 45 | 3.09 |