Construction of an efficient overlay multicast infrastructure for real-time applications

TitleConstruction of an efficient overlay multicast infrastructure for real-time applications
Publication TypeConference Papers
Year of Publication2003
AuthorsBanerjee S, Kommareddy C, Kar K, Bhattacharjee B, Khuller S
Conference NameINFOCOM 2003. Twenty-Second Annual Joint Conference of the IEEE Computer and Communications. IEEE Societies
Date Published2003/04/03/march
Keywordsapplication-layer;, applications;, communication;, criterion;, decentralized, distributed, entities;, forwarding, infrastructure;, Internet;, iterative, media-streaming, methods;, MSN;, Multicast, nodes;, NP-hard;, OPTIMIZATION, overlay, real, real-time, scheme;, service, systems;, TIME

This paper presents an overlay architecture where service providers deploy a set of service nodes (called MSNs) in the network to efficiently implement media-streaming applications. These MSNs are organized into an overlay and act as application-layer multicast forwarding entities for a set of clients. We present a decentralized scheme that organizes the MSNs into an appropriate overlay structure that is particularly beneficial for real-time applications. We formulate our optimization criterion as a "degree-constrained minimum average-latency problem" which is known to be NP-hard. A key feature of this formulation is that it gives a dynamic priority to different MSNs based on the size of its service set. Our proposed approach iteratively modifies the overlay tree using localized transformations to adapt with changing distribution of MSNs, clients, as well as network conditions. We show that a centralized greedy approach to this problem does not perform quite as well, while our distributed iterative scheme efficiently converges to near-optimal solutions.