Enhanced-Delivery Overlay Multicasting Scheme by Optimizing Bandwidth and Latency Discrepancy Ratios

With optimized bandwidth and latency discrepancy ratios, Node Gain Scores (NGSs) are determined and used as a basis for shaping the max-heap overlay. The NGSs - determined as the respective bandwidth-latency-products - govern the construction of max-heap-form overlays. Each NGS is earned as a synergy of discrepancy ratio of the bandwidth requested with respect to the estimated available bandwidth, and latency discrepancy ratio between the nodes and the source node. The tree leads to enhanceddelivery overlay multicasting – increasing packet delivery which could, otherwise, be hindered by induced packet loss occurring in other schemes not considering the synergy of these parameters on placing the nodes on the overlays. The NGS is a function of four main parameters – estimated available bandwidth, Ba; individual node's requested bandwidth, Br; proposed node latency to its prospective parent (Lp); and suggested best latency as advised by source node (Lb). Bandwidth discrepancy ratio (BDR) and latency discrepancy ratio (LDR) carry weights of α and (1,000 - α ) , respectively, with arbitrary chosen α ranging between 0 and 1,000 to ensure that the NGS values, used as node IDs, maintain a good possibility of uniqueness and balance between the most critical factor between the BDR and the LDR. A max-heap-form tree is constructed with assumption that all nodes possess NGS less than the source node. To maintain a sense of load balance, children of each level's siblings are evenly distributed such that a node can not accept a second child, and so on, until all its siblings able to do so, have already acquired the same number of children. That is so logically done from left to right in a conceptual overlay tree. The records of the pair-wise approximate available bandwidths as measured by a pathChirp scheme at individual nodes are maintained. Evaluation measures as compared to other schemes – Bandwidth Aware multicaSt architecturE (BASE), Tree Building Control Protocol (TBCP), and Host Multicast Tree Protocol (HMTP) - have been conducted. This new scheme generally performs better in terms of trade-off between packet delivery ratio; link stress; control overhead; and end-to-end delays.

• Omar F. Hamad
• T. Marwala

• Overlay multicast
• Available bandwidth
• Max-heapform overlay
• Induced packet loss
• Bandwidth-latency product
• Node Gain Score (NGS).

[1] K. Kim.: Bandwidth Dependent Overlay Multicast Scheme: In
International Conference on Communication Systems, 2006. ICCS 2006.
10th IEEE Singapore, IEEE 2006.
[2] T. M. T. Kwan et al.: On Overlay Multicast Tree Construction and
Maintenance: In International Conference on Collaborative Computing:
Networking, Applications and Worksharing, IEEE 2005.
[3] S. Zhu et al: Efficient Security Mechanisms for Overlay Multicast Based
Content Delivery: In Computer Communications 30 (2007), Elsevier
B.V., pp 793-806.
[4] V. J. Ribeiro et al., "pathChirp: Efficient Available
Bandwidth Estimation for Network Paths," In Proceedings of
PAM (Passive and Active Measurement Workshop), Apr. 2003.
[5] Y. Jiang et al: A Hierarchical Overlay Multicast Network: In 2004 IEEE
International Conference on Multimedia and Expo (ICME), IEEE 2004.
[6] M. Hosseini et al: End System Multicast Routing for Multi-party
Videoconferencing Applications: In Computer Communications 29
(2006), 2005 Elsevier B.V., pp. 2046-2065.
[7] S. S. Wang et al: Fast End-to-End Available Bandwidth Estimation for
Real-Time Multimedia Networking: In 8th Workshop on Multimedia
Signal Processing, IEEE 2006.
[8] M. Jain et al: End-to-End Available Bandwidth: Measurement
Methodology, Dynamics, and Relation with TCP Throughput: In
SIGCOMM 2002.
[9] Melander et al: A New End-to-End Probing and Analysis Method for
Estimating Bandwidth Bottlenecks: In Proceedings of IEEE Globecom,
Nov. 2000.
[10] O. Dolejs et al: Optimality of the Tree Building Control Protocol: In
Proceedings of the International Conference on Parallel and Distributed
Processing Techniques and Applications, CSREA Press, 2002.
[11] L. Mathy et al: An Overlay Tree Building Control Protocol: In J.
Crowcroft and M. Hofmann (Eds.): NGC 2001, LNCS 2233, pp. 76-87.
[12] Abderrahim Benslimane: Multimedia Multicast on the Internet, British
Library Cataloguing-in-Publication Data.
[13] Doru Constantinescu: Overlay Multicast Networks: Elements,
Architectures and Performance: Publisher: Blekinge Institute of
Technology Printed by Printfabriken, Karlskrona, Sweden 2007, ISBN
978-91-7295-125-9.
[14] A. Kim: OPNET Tutorial: OPNET Modeler (OPNET Technologies),
March 7, 2003.
[15] K. Kim et al: A Novel Overlay Multicast Protocol in Mobile Ad Hoc
Networks: Design and Evaluation: IEEE Trans. on Vehicular Tech., Vol.
54, No. 6, Nov. 2005, pp. 2094-2101.
[16] K. Fall et al: The ns Manual (formerly ns Notes and Documentation):
The VINT Project: A Collaboration between researchers at UC
Berkeley, LBL, USC/ISI, and Xerox PARC, June 22, 2007.
[17] A. Eswaradass et al: Network Bandwidth Predictor (NBP): A System for
Online Network performance Forecasting: In Proceedings of the Sixth
IEEE International Symposium on Cluster Computing and the Grid
(CCGRID'06), IEEE 2006.
[18] A. Habib et al: Incentive Mechanism for Peer-to-Peer Media Streaming:
12th IEEE International Workshop on Quality of Service, IWQOS 2004.
[19] J. A. Strauss: Choosing Internet Paths with High Bulk Transfer
Capacity, Department of Electrical Engineering and Computer Science,
Massachusetts Institute of Technology (2001), September 2002.
[20] Y. Cui et al: Max-Min Overlay Multicast: Rate Allocation and Tree
Construction: In Tech. Rep. UIUCDCS-R2003-2373/UILU-ENG-2003-
1760, 2003.
[21] K. K. To et al: Parallel Overlays for High Data-rate Multicast Data
Transfer: In Computer Networks 51 (2007), Elsevier B.V., pp 31-42.