Abstract—Although initially proposed as the deployable alternative to Internet protocol multicast, application-layer overlay network actually revolutionizes the way network applications can be built, since each overlay node is an end host, which is able t
IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS,VOL.22,NO.1,JANUARY200491 oStream:Asynchronous Streaming Multicast in Application-Layer Overlay Networks
Yi Cui,Baochun Li,Member,IEEE,and Klara Nahrstedt,Member,IEEE
Abstract—Although initially proposed as the deployable alter-native to Internet protocol multicast,application-layer overlay network actually revolutionizes the way network applications can be built,since each overlay node is an end host,which is able to carry out more functionalities than simply forwarding packets. This paper addresses the on-demand media distribution problem in the context of overlay network.We take advantage of the strong buffering capabilities of end hosts,and propose a novel overlay multicast strategy,oStream.We have performed extensive analysis and performance evaluation with respect to the scalability and the efficiency of oStream.With respect to the required server bandwidth,we show that oStream defeats the theoretical lower bound of traditional multicast-based approaches,under both sequential and nonsequential stream access patterns.oStream is also robust against bursty requests.With respect to bandwidth consumption on the backbone network,we show that the benefit introduced by oStream overshadows the topological inefficiency (e.g.,link stress and stretch)introduced by using application-layer multicast.
A PPLICATION-LAYER multicast,or overlay multicast,
was initially proposed to facilitate the deployment of multicast-based applications in the absence of Internet protocol (IP)multicast.By organizing end hosts into an overlay network,multicast can be achieved through data relay among overlay members via unicast.Although seemingly it just elevates the multicast functionality into application layer,this approach actually revolutionizes the way network applications can be built.In IP multicast,except for nodes at the edge,the network is composed of routers,whose task is no more than forwarding packets.In contrast,each node in overlay network is an intelligent one that can contribute various resources(CPU, storage,etc.).Such great flexibilities have soon been utilized in the latest network and application designs,such as data/service indirection,resilient routing,and peer-to-peer streaming ,etc.
This paper explores the feasibility of using an overlay-based approach to address the problem of on-demand media dis-
Manuscript received November15,2002;revised May1,2003.This work was supported in part by the National Science Foundation(NSF)Computer and Information Sciences and Engineering(CISE)Infrastructure Grant under Contract NSF EIA99-72884and NSF Information Technology Research(ITR) Grant under Contract NSF CCR00-86094.
Y.Cui and K.Nahrstedt are with the Department of Computer Science, University of Illinois at Urbana-Champaign,Urbana,IL61801USA(e-mail: firstname.lastname@example.org;email@example.com).
B.Li is with the Department of Electrical and Computer Engineering,Univer-sity of Toronto,Toronto,ON M5S3G4,Canada(e-mail:firstname.lastname@example.org). Digital Object Identifier10.1109/JSA
(a) IP Multicast
Fig.1.Conceptual comparison of IP multicast and AM.
tribution.The fundamental challenge of this problem is the unpredictability of user requests in the following aspects: 1)asynchrony–users may request the same media object at different times;2)nonsequentiality–users’stream access pattern is VCR-type,instead of sequential(from beginning to end);and3)burstiness–the request rate for a certain media object is highly unstable over time.The basic approach of traditional IP-multicast-based solutions–is to repeat the same media content on different multicast channels over time. Clients are either enforced to be synchronized at the price of service delay,or required to participate in several multicast sessions simultaneously.
We argue that this is not necessarily the case in the context of overlay networks.In fact,we should leverage the temporal cor-relation of asynchronous requests and the buffering capabilities of overlay nodes to address the above challenges.As shown in Fig.1,by enabling data buffering on the relaying nodes in an application-layer multicast tree,requests at different times can be satisfied by the same stream,thus achieving efficient media delivery.Based on this foundation,we propose oStream,an ap-plication-layer asynchronous streaming multicast mechanism. The main contributions of introducing oStream include the fol-lowing favorable properties,supported and verified by extensive analytical and experimental results.
1)Scalability:We derive the required server bandwidth
in oStream,which defeats the theoretical lower bound of traditional multicast-based approaches,under both sequential and nonsequential access patterns.This may be achieved when we allow each relaying node in the multicast tree to buffer at most10%of the media streams.
Furthermore,over a certain threshold,the required server bandwidth no longer increases as the request rate grows, which suggests the robustness of oStream against“flash crowds.”
2)Efficiency:In previous works,server bandwidth has been
used as the sole metric to evaluate system scalability