Previous [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [ 10]


Journal of Information Science and Engineering, Vol. 21 No. 3, pp. 547-570 (May 2005)

Combining Precomputation and On-Demand Routing
for Multicast QoS Routing*

Chih-Jen Tseng and Chyouhwa Chen+
Department of Information Management
Northern Taiwan Institute of Science and Technology
Taipei, 112 Taiwan
+Department of Computer Science and Information Engineering
National Taiwan University of Science and Technology
Taipei, 106 Taiwan

In QoS routing, two types of computational approaches have been studied: precomputation and on-demand computation. The precomputation approaches have the advantage of extreme efficiency in connection request processing, but they suffer from large storage overhead for the maintenance of precomputed QoS route and potentially lower connection acceptance probability due to stale topology information. In contrast, the on-demand computation approaches enjoy higher connection acceptance probability but incur a large per-request computation cost and long join latency. In this paper, we try to combine the two approaches and strike a balance between them in the design of a multicast routing protocol PPMRP (Probabilistic Precomputation Multicast Routing Protocol). PPMRP is the first attempt to include the precomputation technique in the design of multicast QoS routing protocols. It employs two innovative ideas to achieve a nice balance between cost and performance: scope-limited adverting of multicast tree information and probabilistic selection of precomputation routers. Through extensive simulations experiments, we demonstrate that PPMRP exhibits the low join latency characteristic of precomputation schemes without excessive computation on a large control message overhead. Meanwhile, it is able to construct low cost multicast trees with superior connection acceptance probability.

Keywords: multicast, dynamic routing, QoS routing, precomputation, scope-limited advertising

Full Text () Retrieve PDF document (200505_04.pdf)

Received November 4, 2003; revised August 4, 2004; accepted August 30, 2004.
Communicated by Yu-Chee Tseng.
* This paper has been presented in IEEE International Conference on Communications (ICC 2004), 2004.