Higashino Lab. Maximizing User Gain in Multi-flow Multicast Streaming on Overlay Networks Y.Nakamura, H.Yamaguchi and T.Higashino Graduate School of Information Science and Technology, Osaka University Higashino Lab. Research Goal Realizing Multi-party video conferencing systems Many-to-many multicast application which consists of hundreds of users User hosts exchange multiple video streams in realtime Efficient use of bandwidth is required Internet 9 May 2006 FMUIT'06 2 Higashino Lab. Application Layer Multicast (ALM) ALM is multicast on overlay networks End users act as multicast routers Does not require special hardware such as IP multicast enable routers Application-specific routing protocols can be designed More efficient than Unicast because a sender does not need to send data to all receivers Unicast A ALM B S A B S C C D 9 May 2006 D FMUIT'06 3 Higashino Lab. Related works Overcast，CAN，RMX HBM aiming at an efficient delivery of video stream in a large-scale group aiming at overlay network construction for the mobile terminal Narada，ALMI，Yoid aiming at delivery of single video stream in small-scale group also target the conference application Few research to deliver the two or more streams simultaneously and continuously for the video conferencing 9 May 2006 FMUIT'06 4 Higashino Lab. Issues to be considered Each video uses some amount of bandwidth on overlay networks →In delivering multiple video streams, they compete for bandwidth on overlay links Users may have priority requirements to video streams e.g. users may prefer the speaker’s video than audience’s video Internet 9 May 2006 FMUIT'06 5 Higashino Lab. Emma/QoS New ALM protocol for multi-party communication systems Users construct overlay network Each user sends its own video continuously and receives some of other user hosts’ video streams on overlay networks Each user filters and adjusts the quality of streams and make the space for a new requested stream Red Overlay Network Internet 9 May 2006 Red FMUIT'06 6 Higashino Lab. Overlay network construction New user joins the session by constructing the overlay link Measuring the delay with another user, and constructing the overlay link with the number of appropriate users When the link is constructed, the link capacity (number of streams that can be delivered) is negotiated and decided The participating users enhance the delivery routing tree The routing tree of the source user is constructed with the shortest path tree by flooding A C Overlay Network E B 9 May 2006 D FMUIT'06 Underlying Network 7 Higashino Lab. Leaving failure management Many users frequently leave on the overlay network We need guarantee the continuance delivery of the stream Descendant node cannot receive the stream Need to make the stream had delivered through the left node can immediately delivered from another node again Each node knows the nodes can deliver the stream by periodical message If neighbor node leaves, the node is immediately reconnected to one of them 9 May 2006 FMUIT'06 8 Higashino Lab. Loss/Gain-based rate adaptation Problem Because of the restriction and a decrease of the link capacity, all requests of stream cannot be accepted Solutions Simple way Narada When the stream cannot be delivered, all requests of the stream are not accepted When it is impossible to deliver the stream in the received rate in each user, user reduces the rate of the stream so that it can be delivered Emma/QoS 9 May 2006 Each user decides that it increases / reduces the rate of the stream according to the value of the gain obtained by receiving the requested stream and cutting the rate of the delivering stream Requests are accepted as many as possible FMUIT'06 9 Higashino Lab. User gain function Every user defines for each stream User gain is added when a unit of bandwidth is added to current receiving stream Linear approximation We use utility function This function shows the priority of the user for each unit of bandwidth e.g. In the typical streaming, utility tends to increase suddenly by the rate of a at least necessary quality, and to increase gradually in a rate increase after that ｝User gain Utility function User gain is calculated by the difference of the following two values Value on utility function of k-1 units Value on utility function of added k-th unit 9 May 2006 FMUIT'06 k-1 k k denotes certain amount of bandwidth on the overlay links 10 Higashino Lab. Protocol operations Every node periodically sends messages about user gain (negative gain) for each stream Request message is transmitted calculating the optimal allocation of each unit Negative gain : Value of user gain lost in descendant nodes when a unit is deprived from delivering stream from user gain and a negative gain that increases by the request acceptance when requesting it As a result, each user can know and decide which stream should be reduced 9 May 2006 FMUIT'06 B # of units of links is 3 ： Streams 11 Higashino Lab. Performance evaluations We have implemented a simulator of Emma/QoS simulated in a typical video conferencing scenario compared with Narada (one of the most popular ALMs) We examined the following items Link stress : the number of copies of a single packet delivered on a physical link Path stretch : the ratio of the sum of unicast hops of the overlay links between two nodes to that on the shortest path on the underlying physical network User satisfaction ratio : the ratio of the sum of user gain obtained by each node to that of user gains requested by the node Variation of user gain 9 May 2006 FMUIT'06 12 Higashino Lab. Link stress and path stretch Compare with the performance of Narada Emma/QoS has better values than unicast 1000 Narada assumes the delay between hosts to be optimizing metric and constructs mesh-like overlay network On this overlay network Narada constructs shortest path tree Maximum link stress is about 10th of the unicast The performance of Narada is not so quite different from that of Emma/QoS 50 # of physical links Unicast Emma/QoS Narada Emma/QoS Narada # of users 0 1 10 100 0 1 Link Stress 9 May 2006 4 8 Path Stretch FMUIT'06 13 Higashino Lab. Distribution of users’ satisfaction The ratio of the total gain of accepted requests to that of all requests Requests not accepted at all is much smaller than Narada and FCFS (First Come First Serve method) The admission control mechanism of Emma/QoS is useful to video-conference systems 250 Emma/QoS Narada FCFS # of requests 200 150 100 50 0 0 0.2 0.45 0.6 0.8 0.88 0.89 0.9 1 satisfaction ratio 9 May 2006 FMUIT'06 14 Higashino Lab. Variation of user gain Emma/QoS achieves higher user gain than Narada when users join/leave during the session when users’ preferences to stream s are changed during the session # of users 45 800 # of users gain (avg.) Emma/QoS Narada 0 0 1 15 31 time 9 May 2006 FMUIT'06 15 Higashino Lab. Conclusion We have proposed new ALM protocol called Emma/QoS To avoid resource competition, we use utility-based admission control in decentralized way From the experimental results 9 May 2006 Higher satisfaction of users than a simple method Even though some users leave from or join to a session, users’ satisfaction is kept high FMUIT'06 16
© Copyright 2024 ExpyDoc
