WIXLIB

Thus, when a node leaves the system, we consider that a newnode appears. Authors in [13], [14] carried out a measurementcampaign of a large-scale overlay for multimedia streaming,PPLive [15]. Among other statistics, the authors report thatthe median time a user stays in such a system is around 10minutes. In this study, we use this value as the default value(after normalization see the following on default values).Repair rate. When a node has a push operation to carry out,it has first to change its children list, and then to contactits two children implicated in the operation so that they alsochange their neighborhood (father, grandfather or children).This communication takes some amount of time, that can varydepending on the node to contact and congestion inside thenetwork. To take into account this variation, we model therepair time as a random variable with exponential distributionof parameter µ. [16] reports that the communication time in astreaming system is in average 79 ms. Thus, we believe thatassuming an average repair time of 100 ms is appropriate.Default values. In the following, for the ease of reading, wenormalize the repair rate to 1. We call unit of time the averagerepair time, 100 ms. The normalized default churn rate, λ isthus 1/6000 and the system churn rate is Λ nλ 0.17.These default values are indicated as typical examples, but inour experiments we present results for a range of values of Λbetween 0 and 1. We talk of low churn systems for values ofΛ below 0.4, and of high churn systems for values above 0.4.B. Description of the ProtocolsWe now define four different protocols according to fourdifferent ways to select the children during the operations andfour different levels of knowledge of the streaming system. Wewill study the trade-off between knowledge and performancein the following.S MALLEST S UBTREE P ROTOCOL (SSP). In this protocol,each node knows the subtree size of each of its sons. Whena churn occurs, the son with the largest subtree of the failingnode takes over the role of its father by adopting every of itssibling. It is itself adopted by its grandfather. When a nodeis overloaded, its son with the third largest subtree is pushedinto the son with the second largest one.R ANDOM P ROTOCOL (RP). In this protocol, nodes do notkeep information about their subtree sizes. They store theirchildren in a queue and each new node attached to them is putat the end of it. A node receiving the video only gives it to thetwo children at the start of its queue. When a churn occurs,the eldest son takes over the role of its father by adoptingevery of its sibling. It is adopted by its grandfather. There isno interruption in the video transmission between the son andthe father. The order in the grandfather children is conserved(i.e. If the father was the first child of its parent, the son takesthe first place in the grandparent sons). Every of its siblingis reattached to the new father and thus is at the end of thequeue, in the same order as it was in the failing node queue.An overloaded node chooses at random the son that willbe pushed and also the node that will receive the pushed node.N O I NTERRUPTION P ROTOCOL (NIP) This protocol sharessome similarity with the random protocol. The same operationis done when a node leaves the system: the eldest childtakes over the role of the failing node. When an overloadedcarries out a push operation, it chooses uniformly at randoma node not receiving the video and pushes it under a nodereceiving the video. This ensures no interruption of the videodistribution.PARTIAL I NFORMATION P ROTOCOL (PIP) The idea of theprotocol starts with the observation that for most operations,it is relatively easy to determine the largest subtrees withoutstoring the exact size of all subtrees. When a new nodearrives, we know that it has a subtree size of one and that ithas to be pushed to the bottom of the tree. So we will labelit as new. Then, during this arrival process, we will have todecide in which subtree to push it. If we do the hypothesisthat the tree stays relatively well balanced during the protocollifetime, we may choose at random without adding too muchimbalance in the tree. When there is a churn, we know thatone of the children replaces its father. It will have threechildren, one large (its former brother), that we label big, andtwo smaller ones, that we label normal. Hence, it has to pushone of the smaller into the second one. Again, if we supposethat the tree is relatively balanced, this choice can be maderandomly. The subtree pushed is relabeled as big, its newbrothers are labeled as normal, and we remove the label ofits former brothers.C. MetricsTo evaluate the performance of the different protocols, weare interested by the following metrics.Time to attach a new node. When a new node arrives into thesystem, it has to attach to a node which has enough bandwidthto forward the video to it. Basically, it is first attached to theroot and then pushed to the bottom of the tree to become aleaf. Ideally, this takes a small amount of time, logarithmic inthe number of nodes watching the video, n, see Section III.Repair time after a node departure. When a node leaves thesystem, a repair processed starts as described in Section II-A.Basically, one of its son replaces it and some nodes are pushedin its subtree. The simulator records this repair time at eachchurn event.Number of people not receiving the video. Due to thesetwo phenomenas, attachment of a new node and repairs, somepeople do not receive the video during small periods of timeduring the life of the protocols. We study what fraction of thenodes do not receive the video and during which amount oftime.Height of the tree or delay. The height of the diffusion treegives the maximum delay between the source and a node.Ideally, it is equal to blogd nc 1, where d is the maximumnode degree.

Number of interruptions and interruption duration. Wemonitor the number of interruptions of the video diffusion toa node during the protocol lifetime, as well as the distributionof interruption durations.III. A NALYSISIn this section, we analyze the S MALLEST S UBTREE P RO TOCOL . We give analytical formulas to estimate differentmetrics: the repair time, the average number of people notreceiving the video, and the number of interruptions.The analysis is done under an independence hypothesisof the failures, meaning that the repair of one failure isdone before another happens. Remark that it implies thatthe diffusion tree is always a balanced binary tree when afailure happens. Indeed, we are considering a system withconstant population in which a new node arrives when a nodeleaves. Using the information about subtree sizes, SSP willpush this new node in the optimal position. We will considerhere complete binary trees of size n 2h 2, but theanalysis extends to other values. The independence hypothesisis evaluated by simulation for different values of churn inSection IV-B.Analysis of the repair time. We study the repair time ofthe diffusion tree when a node selected at random leaves thesystem. We consider the position of the node in the tree.If the failing node is a leaf, the tree is still balanced andnothing happens.If the failure happens at depth i h, the tree is repaired(that is, all nodes have degrees less or equal to 2) after h i 1push operations. Note that when i h 1, no pushes areneeded.We give now the average time to repair the tree after a nodedeparture. In average, a node carries out an operation in a time1µ . Hence, the average time to carry out h i 1 operations ish i 1. The number of nodes at depth i, 2 i h, is 2i 1 .µThus, the probability that the node leaving the system is ati 1depth i is 2 n . Recall than n 2h 2. If we note T the timeto repair the diffusion tree, we haveh 1Ph 2E[T ] 2h1 2 i 2 2i 1 h i 1 2 µ(2 2(h 1)h 2)µ1 2µwhen h is large.The S MALLEST S UBTREE P ROTOCOL is very efficient. Indeed, only one half operation is needed in average to repairthe tree after a node departure.Analysis of the number of nodes not receiving the video.During the repair process, some nodes do not receive thevideo. Indeed, recall that only the two biggest subtrees of anoverloaded node receive the video. When a node at level ileaves the system, its child with the largest subtree replacesit. It becomes overloaded with three children of subtree sizes2h i 1, 2h i 1 1, and 2h i 1 1 (A node at depth iis of height h i 1. A subtree of height i contains 2i 1nodes). Thus, 2h i 1 1 nodes do not receive the video. Ateach repair, the height of the tree is reduced by one and thisnumber is divided by around two. That is after k repairs, it isFig. 3: Effect of a push operation during a repair.equal to 2h i 1 k 1, see Figure 3. A push operation is donein average in a time µ1 . Hence, if we note ni the number ofpeople without video when the failing node is at level i, wehaveE[ni ] h i 1 Λ X kΛ h i2 h i 1 .(2 1) µµk 0Recall now that the probability that the failing node is at leveli 1i is 22h 2 . If we note nbad , the number of people withoutvideo, we haveE[nbad ] 2h 1 (h 5) 2(h 1) Λ2i 1i 2 2h 2 ni µ2h 2h 5 Λwhenhislarge.2 µPh 2Analysis of the number of interruptions. Recall that whena node leaves the system at level i, its first child is overloadedwith three children of subtree sizes 2h i 1, 2h i 1 1, and2h i 1 1. Only the two biggest sons of a node receive thevideo. Thus, 2h i 1 1 nodes are interrupted. With a repair,the interruption for these nodes stops and the height of the treeinterrupted is reduced by one, that is after k repairs, it is equalto 2h i 1 k 1. Every interrupted node is only interruptedonce. Hence, if we note inti (t) the number of interruptionwhen the failing node is at level i as a function of the time,we haveE[inti (t)] tΛh i 1X2k 1 tΛ(2h i h i 1)k 0Recall now that the probability that the failing node is ati 1level i is 22h 2 . If we note nint (t), the average number ofinterruptions, we haveE[nint (t)] 2h 1 (h 5) 2(h 1)2i 1tΛi 2 2h 2 inti 2h 2h 5tΛwhenhislarge.2Ph 2Analysis of the arrival time. When a new node arrives inthe system, it is first attached to the root. It does not receivethe video until it is then pushed to the bottom of the tree byh 2 successive push operations. Since a node carries out anoperation in an average time of µ1 , if we node T the time forthe new node to receive the video, we have:E[T ] h 2.µ

.050050400403002001000.5Churn1.0Fig. 4: Comparison between the formal model of Section IIIand the simulations for: (Left) Average fraction of peers notreceiving the video as a function of the churn rate due to therepair (1022 nodes). (Right) Average number of interruptionsper node (1022 nodes) for a time of 30,000 units of time.IV. S IMULATIONSWe developed a discrete-event simulator of the streamingsystem described in Section IV-A. We use it to analyze andcompare the different protocols. A summary of results isprovided in this section for different metrics.A. The simulatorOur desire to focus on high level simulation led us todevelop a custom C discrete-event simulator to evaluatemetrics of the system described in Section II-C. We did not uselow level network simulators like NS-2 or OMNET becausethey would require more computation time and give metricsnon pertinent to our analysis. Our goal is to focus on the treestructure after churns and reparations to validate our protocols.B. Validation of the analytical modelTo validate our analysis, we first compared the resultsgiven by the simulator to the analytical formulas obtained inSection III.People without the video. In Figure 4 (Left) is given theaverage fraction of people not receiving the video. New nodesjoining the systems are not taken into account until they startto receive the video. Only the non distribution of video due tothe repairs is counted. As an example, for the default churnrate value, 0.17, only 0.03% of the nodes do not receive thevideo in average, and for a high value of churn 1, only 0.25%.We see that the closed formula models very closely thesystem. Recall that the formulas were given for low churn,that is when a churn event is repaired before another churnevent. This corresponds to values of the churn rate Λ between0 and 0.5. However, we see that, even for larger churn values( 0.5), the system behavior is well predicted by the formula.Interruptions. The average number of video interruptions isgiven in Figure 4 (Right) as a function of the churn rate. Again,the interruptions are due to the repair of the diffusion tree whenthere is a node departure.This number is the average over all nodes of the numberof interruptions per node for a period of 30,000 units of time.For example, for a value of churn of 0.2, the diffusion fora node is interrupted 20 times in average, that is, a 0.2%Number of interruptionsPeers without video0.25%3020101.000.00.5Churn1.0Fig. 5: Average height (over time) of the tree (1022 nodes) asa function of the churn rate for the four repair protocols. Left:y-axis range from 0 to 500. Right: y-axis range from 0 to 50.experiences an interruption every 1500 units of time, thatis every 150 seconds. As we will see it later, the durationsof the interruptions are very short. Thus, they are withoutconsequence for the end-user experience.We see that the analytical formula gives a very goodestimation of the behavior of the system. This is true evenfor high churn.C. Comparison of the protocolsIn this section, we compare by simulation the performancesof the different protocols that we propose. Recall that thesedifferent protocols use different levels of information. Severalproviders of live video may have different criteria on the different metrics and on the implementation, leading to differentchoices of the adequate protocol.Levels of needed information. We recall that, for everyprotocol, each node has at least to store the ids (and addresses)of children, father and grandfather. In RP and NIP, each nodestores the order in which its children attached to it. In SSP,each node needs to know the size of its subtree. Last, in PIP,only two additional bits are necessary: a new node arrivingin the system is tagged as new till it finds a place in thediffusion tree and a node pushed by a repair process is taggedas big. For the detailed discussion, the reader may refer itselfto Section II-B.We now compare the protocols for the different metrics. Aswe will see, the protocols do not behave at all similarly forsome metrics. To improve the readability of the figures, foreach metric, we propose two plots with the same data, butwith different scales of the y-axis.Height of the diffusion tree and delay. Figure 5 shows theaverage height (over time) of the tree as a function of thechurn rate.The first observation is that RP exhibits a very differentbehavior than the other protocols, see Figure 5 (Left). Itbehaves very badly: the height of the diffusion reaches a valueof 500. It is not of order logarithmic in n, the number ofnodes. On the contrary, it gets close to a linear height! Thediffusion tree looks like a path in this case. The protocol is veryinefficient. Thus, pushing the nodes randomly is not possiblein practice.

20%10%0%0.00.5ChurnPeers w\o videoPeers w\o .0Number of interruptionsFig. 6: Average fraction of peers not receiving the video asa function of the churn rate (1022 nodes). Left: y-axis rangefrom 0 to 60%. Right: y-axis range from 0 to 1501001.05000.00.5Churn1.0Fig. 7: Average number of interruptions of the streaming pernode as a function of the churn rate after 10,000 units of time.Left: y-axis range from 0 to 2500. Right: y-axis range from 0to 200.We see again, in Figure 6 (Left), that RP behaves a lotworse than the other three protocols. As much as 52% of thenodes do not get the video for a churn rate of 1. It alreadyreaches 6% for a churn rate of 0.5. This protocol is thus veryinefficient.The three other protocols, SSP, NIP and PIP, behavesimilarly, and are very efficient. The average percentage ofpeople without the video is very small for churn valuesexpected in a viable live streaming system (churn rate between0 and 0.4). For a churn rate of 0.2, the average percentage isrespectively 0.04%, 0.1% and 0.15 % of the nodes for thethree protocols, see Figure 6 (Right).Number of interruptions during the diffusion. We studiedthe number and durations of interruptions of the video diffu-60%50%40%30%Time of interruptionsThe explanation of the different protocols’ efficiency is dueto their different behaviors, (1) when there is a churn event,and, (2) when there is an arrival of a new node.First, when a failing node is close to the root, a large subtreedoes not receive the video anymore and has to be pushed inthe tree by the repair process. The SSP protocol succeeds toreconstruct a perfectly balanced tree by using the informationabout the subtree sizes. It knows exactly what is the rightnode to push. The two protocols RP and NIP do not havethis information: they blindly push the subtree. It can thushappen that a large subtree ends up at the bottom of the treeat the end of the repair process. This can increase its heightsignificantly: in the worst case, the height can be doubled withonly one churn event. We see that PIP has performance not toofar from optimal. We see that, even without the informationof the subtree sizes, a simple guess of the node to be pushedis efficient in terms of delay. The protocols recognizes largesubtrees (of size 2i ) from small subtrees (of size 2i 1 ), leadingto a near optimal repair process.Second, when there is an arrival of a new node in the tree.SSP can push this new node exactly at the right position of thediffusion tree. PIP and NIP cannot distinguish two subtreeswith a small difference of size and thus push the new noderandomly to the bottom of the diffusion tree. RP has in thiscase a very bad behavior. As it does not have any information,it does not know that a node is new. Hence, it pushes randomlya node that can have a very large subtree, instead of the newnode of subtree size one! On the contrary, NIP does not pushsubtrees receiving the video to ensure a continuity of the videodiffusion. Hence, the arrival of a new node in the systemcannot trigger that a large subtree is pushed at the bottomof the tree.To sum up, the repair protocol SSP is optimal in terms oftree height and, thus, of delay. This protocol uses informationabout node subtree sizes. If this information is consideredtoo costly to maintain

Study of Repair Protocols for Live Video Streaming Distributed Systems Fr ed eric Giroire, Nicolas Huin To cite this version: . Huin. Study of Repair Protocols for Live Video Streaming Distributed Systems. IEEE GLOBECOM 2015 - Global Communications Conference, Dec 2015, San Diego, United States. hal-01221319 HAL Id: hal-01221319 https://hal .