资源描述
*,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,http:/www.ee.kth.se/gyuri,An Analytical Study of Low Delay Multi-tree-based Overlay Multicast,Gyrgy Dn and Viktria Fodor,School of Electrical Engineering,KTH,Royal Institute of Technology,Stockholm,Sweden,Peer-to-Peer Streaming and IP-TV Workshop,Motivation,Live peer-to-peer streaming,Many proposed systems,Push-based vs.Pull-based,Tree-based vs.mesh-based vs.unstructured,Multi-hop data delivery,Failures node departures,packet losses,Delivery time hard to predict,Playback delay and playout buffer dimensioning,Does playback delay matter?,Designers goal:Control the playback delay(minimize?),Our goal:Identify sources of delay,A packets eye view of the overlay,Four components of delay:D,d,=D,p,+D,tr,o,+D,pr,+D,tr,i,(,a,:pkt size,C,in,:,input bandwidth,C,out,:,output bandwidth),R,A spanning tree of the overlay traversed by a packet,D,pr,D,tr,i,=,W,in,+,a,/,C,in,D,p,D,tr,o,=,W,out,+,a,/,C,out,D,d,Tree properties depend on,Tree-based:Overlay maintenance,Unstructured:Scheduling algorithm,One-hop propagation model,Possession-propagation-reception,D,d,1,1,Layer l-1,Layer l,h,Possession probability,h,Per-hop delay,Reception probability,h,One-hop propagation model,Possession-propagation-reception,D,d,h,1,h,1,Layer l-1,Layer l,h,Possession probability,Per-hop delay,Reception probability,Multi-hop propagation model,Without FEC,Apply the one hop model to every layer,Result is the convolution of the per-hop delays,R,With FEC,Apply the one hop model to every layer,Calculate the result iteratively,Multi-hop propagation model,Probability of reception by time,h,in layer,l,for packet,j,Probability of possession by time,h,in layer,l,for packet,j,Source node initial condition,Numerical solution,Converges,Scalable,A control theoretic interpretation:Dynamical system with,Input signal,Output signals,Multi-hop propagation model,Probability of possession with playback delay,b,(playout deadline of packet j:,h,j,=,b,+(,j,1),a,/,B),Probability of possession for arbitrary node and packet,Inputs of the model,Initial condition,N,l,number of nodes in layer,l,F,d,(h),node-to-node delay distribution,-Source playout strategy,-Overlay structure,-Scheduling,structure,Application Multi-tree overlay,Source and,N,nodes,Source capacity m*B,t,trees,each node forwards in,d,trees,Retransmissions and FEC(n,k)for error control,Packets sent at round-robin from the source,R1,5,8,6,2,3,9,7,4,1,R3,1,8,7,2,5,4,3,9,6,R2,1,7,6,4,3,9,8,2,5,Tree 2,Tree 3,Tree 1,P1,P2,P3,h,1,j=1,j=2,j=3,Initial condition,Overlay structure,Number of nodes per layer(N,l,),Calculated recursively based on,Node output capacity distribution,Prioritization scheme,Capacity allocation scheme,Prioritization schemes,Contribution based,Contributors prioritized over non-contributors(NP),Priority proportional to potential contribution(P),Capacity allocation schemes,In case of excess capacity,Proportional contribution(MM),Non-proportional contribution(FU),Node-to-node Delay,Input link,D,tr,i,=W,in,+a/C,in,W,in,waiting time of a packet in a,G/D/1,queue,Output link,D,tr,o,=,W,out,+,uIdat,/,(,r,B),whereI,1,r,/d,W,out,waiting time as seen by an arriving batch of,r,/d,packets in a,GI,X,/D/1,queue,Retransmissions,Loss detection,etc,Arrival processes,What is a realistic model?,h,Model validation,Discrete event driven simulator,Steady state,Media server on a 10Mbps-20Mbps link(m=50),Low bitrate media,B=112kbps,Nodes buffer 15s worth of packets,Input and output capacity constraints,Propagation delays,Random network topology GT-ITM,Node churn for randomness,Results shown for packet losses,Deterministic arrival process,Inf.cap.C,in,=C,out,=10 Mbps,Inf.incap.C,in,=10 MbpsC,out,=128 kbps,Fin.cap.C,in,=C,out,=128kbps,Number of trees influences the delay is there an optimal number?,D,pr,plays a minor role,but increasing importance,N=10,4,p=0.1,Poisson arrival process,Inf.cap.C,in,=C,out,=10Mbps,Inf.incap.C,in,=10MbpsC,out,=128kbps,Fin.cap.C,in,=C,out,=128kbps,Queuing delay significant,Decrease utilization,N=10,4,p=0.1,Simulation,Inf.incap.C,in,=10 MbpsC,out,=128 kbps,Fin.cap.C,in,=C,out,=128 kbps,Similar to deterministic arrival process,N=10,4,p=0.1,FEC and retransmissions,Dynamically adjust playback delay,FEC cannot achieve,(b)=1,But FEC can help to keep the playback delay low,Scalability?,Capacity allocation and prioritization,Scen.,Share,C,out,kbps,CH,100%,256,CI,65%,128,35%,512,Prioritization and uneven capacity allocation best:,increases the average output capacity of the contributing nodes,Inhomogeneous upload capacity can help to achieve better performance,Capacity allocation,MM:proportional,FU:non-proportional,Prioritization,NP:contributor/non-contributor,P:proportional to contribution,FU+P,MM+P,N=10,4,Conclusion,Main factors that determine the delay,Average upload capacity of,contributing nodes,Waiting times in queues at the nodes,The ways to decrease the end-to-end delay are,decreasing
展开阅读全文