信息通信专业资料SurveyonApplicationLayerMulticast档英文版

1、Survey on Application Layer MulticastGroup Members assignments:略1. introductionApplication layer multicast is increasingly being used to overcome the problem of non-ubiquitous deployment of IP multicast across heterogeneous networks. It offers accelerated deployment, simplified configuration and bet

2、ter access control at the cost of additional traffic load in the network through an overlay-based approach. The general approach to building an application layer multicast architecture involves tracking network characteristics and building appropriate topologies by having the end users to self-organ

3、ize into logical overlay networks for efficient data delivery. Data delivery is accomplished via a data delivery tree which can either be the overlay itself or is embedded in the overlay. The overlay must be capable of failure detection and attempts to match the underlying network topology. Since th

4、e overlay abstracts away the details of multipoint message forwarding through the network and implements them at the end users, application level multicast is also popularly termed as end-system multicast or host multicast.In this survey, we present the recent research work on application layer mult

5、icast. Section 2 is the survey body, while Section 3 gives our conclusion.2. Our SurveyIn this chapter, we will review some research work on application layer multicast based on our survey. For concision, well introduce a few of our surveyed papers in detail, while give a brief introduction for the

6、others.2.1. ZIGZAG: An Efficient P2P Scheme for Media StreamingZIGZAG is a p2p technique for single-source media streaming, which allows the media server to distribute content to many clients by organizing them into an appropriate tree rooted at the server. This application-layer multicast tree has

7、a height O(logkN) and a node degree O(k2), where N is the number of receivers and k a constant. This helps reduce the number of processing hops on the delivery path to a client while avoiding network bottleneck.The ZIGZAG scheme which consists of two important entities: the administrative organizati

8、on representing the logical relationships among the peers, and the multicast tree representing the physical relationships among them.2.1.1. Implementationa) Administrative organizationAn administrative organization is used to manage the peers currently in the system. In ZIGZAG, peers are organized i

9、n a multi-layer hierarchy of clusters recursively defined as follows, where H denotes the number of layers and k is a predefined constant (An example of such hierarchical structure is depicted in Fig 1).l Layer 0 contains all peers.l Peers in layer j H 1 are partitioned into clusters of sizes in k,

10、3k. Layer H 1 has only one cluster which has a size in 2, 3k.l A peer in a cluster at layer j H is selected to be the head of that cluster. This head becomes a member of layer j + 1 if j H 1. The server S is the head of any cluster it belongs to.Fig 1 Administrative organization of peersb) Multicast

11、 treeWe may notice that the multi-layer structure of ZIGZAG is exactly the same with that of NICE. However, based on this identical peer-organization, ZIGZAG derives its multicast tree with a totally different way. The administrative organization in ZIGZAG does not infer a data delivery topology. Fo

12、r instance, the head of a cluster at a layer j H 1 does not forward the content to any of its members. Three rules are defined to derive multicast tree from the per-defined hierarchical structure. The rules are listed below (demonstrated by Fig 2)l A peer, when not at its highest layer, cannot have

13、any link to or from any other peer. E.g., peer 4 at layer 1 has neither outgoing nor incoming links.l A peer, when at its highest layer, can only link to its foreign subordinates. E.g., peer 4 at layer 2 only links to peers 5, 6, and 7 at layer 1, which are foreign subordinates of 4. The only except

14、ion is the server; at the highest layer, the server links to each of its subordinates.l At layer j H1: since non-head members of a cluster cannot get the content from their head, they must get it somehow. In our multicast tree, they get the content directly from a foreign head. E.g., non-head peers

15、in layer-0 cluster of peer 1 have a link from their foreign head 2; peers 1, 2 and 3 have a link from their foreign head S.Fig 2 The multicast tree of peers (H = 3, k = 4)It is easy to prove that the multicast tree has many attractive properties, such as:l The worst-case node degree of the multicast

16、 tree is O(k2).l The height of the multicast tree is O(logkN) where N is the number of peers.The benefit of constructing multicast tree in this way is that:l No bottleneck peer: compare with the worst-case node degree of the multicast tree in NICE (O(klogkN), that value of ZIGZAG is O(k2).l Quick fa

17、ilure recovery: when the parent peer fails, the head of its children is still working, thus helping reconnect the children to a new parent quickly and easily.c) Control protocolTo maintain its position and connections in the multicast tree and the administrative organization, each node X in a layer-

18、j cluster periodically communicates with its layer-j clustermates, its children and parent on the multicast tree.Thanks to the well-formed multicast tree, although the worst-case control overhead of a node is O(k logkN), the amortized worst-case overhead is O(k).d) Peer join, departureThe below step

19、s are pursued by a peer X on receipt of a join request (in this algorithm, D(Y ) denotes the currently end-to-end delay from the server observed by a peer Y , and d(Y , P) is the delay from Y to P measured during the contact between Y and P):1. If X is a leaf2. Add P to the only cluster of X3. Make

20、P a new child of the parent of X4. Else5. If Addable(X)6. Select a child Y :Addable(Y ) and D(Y )+d(Y , P) is min7. Forward the join request to Y8. Else9. Select a child Y :Reachable(Y ) and D(Y )+d(Y , P) is min10. Forward the join request to YWhile peers join in, split operation may take place (il

21、lustrated in Fig 3):1. Separate the target cluster into U plus V (assume the original leader X is in U).2. Disconnect the links from U to Vs child members and at the same time select new parents for these child members from V itself. Similar procedure also applied to Us child members.3. Elect a new

22、leader Y for V. Put Y into the higher cluster and let another qualified clustermate Z take over Ys ex-children.Fig 3 Split illustrationWhile peers depart, recovery operation may take place (illustrated in Fig 4):1. Assume that X is failed and Y is the cluster leader of Xs children. When Y detect tha

23、t X is gone, it try to find another clustermate Z to take over its cluster members.2. In Layer0, another peer X is elected to replace X. All that should be done is just put X in the original highest layer of X.Fig 4 Recovery illustrationThe complexity associated with peer join & departure is rather

24、promising:l The join overhead is O(logkN) in terms of number of nodes to contact.l The worst-case split overhead is O(k2).l In the worst case, the number of peers that need to reconnect due to a failure is O(k2).l The worst-case merge overhead is O(k2).e) Comparison with NICENICE also organizes the

25、peers in a hierarchy of bounded-size clusters as ZIGZAG does. However, NICE and ZIGZAG are fundamentally different due to their own multicast tree construction and maintenance strategies. For example, NICE always uses the head of a cluster to forward the content to the other members, whereas ZIGZAG

26、uses a foreign head instead. Obviously from Table 1, ZIGZAG is no worse than NICE in terms of join overhead and control overhead. Furthermore, ZIGZAG is significantly better than NICE in terms of node degree.Node degree (worst-case)Control overhead (worst-case)Control overhead (average)Join overhead

27、 (worst-case)NICEO(logN)O(logN)O(k)O(logN)ZIGZAGO(k2)O(k logkN)O(k)O(logkN)Table 1 Comparison of NICE and ZIGZAG 2.1.2. Experimental resultsHere are three experimental results. Fig 5 and Fig 6 are overhead of join and split operation of ZIGZAG in a failure-free circumstance. A scale of 2000 peers ne

28、twork is tested. Fig 7 shows the comparison of NICE and ZIGZAG in terms of average recovery overhead, where ZIGZAG constantly outperforms NICE for any peer failure-possibility.Fig 5Fig 6Fig 72.2. A Framework for Architecting P2P Receiver-driven OverlaysAbstract: In this part we will present a simple

29、 and scalable framework for architecting peer-to-peer overlays called Peer-to-peer Receiver-driven Overlay (or PRO). PRO is designed for non-interactive streaming applications and its primary design goal is to maximize delivered bandwidth (and thus delivered quality) to peers with heterogeneous and

30、symmetric bandwidth. To achieve this goal, PRO adopts a receiver-driven approach where each receiver (or participating peer) (i) independently discovers other peers in the overlay through gossiping , and (ii) selfishly determines the best subset of parent peers through which to connect to the overla

31、y to maximize its own delivered bandwidth. Participating peers form an unstructured overlay which is inherently robust to high churn rate. Furthermore, each receiver leverages congestion controlled bandwidth from its parents as implicit signal to detect and react to long-term changes in network or o

32、verlay condition without any explicit coordination with other participating peers.2.2.1. PROBLEM RVISITINGOverlay structures are layered over the best-effort Internet, so any approach for constructing overlay should address the following fundamental challenges: (i) Scalability with the number of par

33、ticipating peers, (ii) Robustness to dynamics of peer participation, (iii) Adaptation to variations of network bandwidth, and (iv) Accommodating heterogeneity and symmetry of bandwidth connectivity among participating peers.Solutions for constructing peer-to-peer overlays often require two key mecha

34、nisms to be implemented at each peer: Peer Discovery (PD) and Parent Selection (PS). And the solutions should incorporate the following design properties: (i) it should use an unstructured, multi-parent peer-to-peer overlay, (ii) it should provide a scalable peer discovery mechanism that enables eac

35、h peer to find its good parents efficiently, (iii) it should detect (and possibly avoid) any shared bottleneck among different connections in the overlay, and (iv) it should deploy congestion controlled connections but ensure in-time arrival of delivered segments to each receiver.2.2.2. P2P RECEIVER

36、-DRIVEN OVERLAYIn PRO, each peer (or receiver) progressively searches for a subset of parents that collectively maximize delivered bandwidth and minimize overall delay from all parents to the receiver. Such a subset of parents may change over time as some parents join (or leave) the overlay, or avai

37、lable bandwidth from current parents significantly changes. Note that each peer can be both receiver and parent at the same time 4. Each receiver periodically exchanges messages (i.e., gossips) with other peers in the overlay to learn about those participating peers that are potentially good parents

38、. Potentially good parents for a receiver are identified based on their relative utility for the receiver. The utility of a parent peer pi for a receiver pj is a function of their relative network distance (delij) and the outgoing access link bandwidth of the parent (outbwi), (i.e., U(pi, pj) = f(de

39、lij , outbwi ) ).Using parents access link bandwidth instead of available bandwidth has several advantages:(i)outgoing bandwidth is an upper bound for available bandwidth from a parent. Therefore, it enables the receiver to roughly classify different parents. (ii) estimating available bandwidth requ

40、ires end-to-end measurement and such a solution does not scale with the number of peers, and more importantly, (iii) given a utility function, this approach enables any peer in the overlay to estimate relative utility of any other two peers. Each receiver only maintains information about a fixed (an

41、d relatively small) number of promising parent peers in its local image.In PRO, each receiver leverages congestion controlled bandwidth from its parents as an implicit signal to detect two events: (i) any measurable shared bottleneck among connections from different parents, and (ii) any change in n

42、etwork or overlay conditions (e.g., departure or arrival of other close-by peers). 2.2.3. GOSSIP-BASED PEER DISCOVERYPeer discovery at each receiver is basically a search among all participating peers in the overlay for a certain number (img sz) of peers with the highest relative utility. PRO adopts

43、 a gossip-like approach to peer discovery.The gossip mechanism works as follow: each peer maintains a local image that contains up to img sz records where each record represents the following information for a previously discovered peer pi in the overlay: 1) IP address, 2) GNP coordinates, 3) number

44、 of received layers, 4) timestamp when the record was last generated by a peer, 5) outbwi and 6) inbwi. To bootstrap the discovery process, a new receiver needs to learn about a handful of other participating peers in the overlay. This information can be obtained from the original server (or a well-

45、known rendezvous point). The server should implement a strategy for selecting the initial peers that are provided to each new receiver. We call this the initial parent selection mechanism. Once the initial set of peers are known, each peer pi periodically invokes a target selection mechanism to dete

46、rmine a target peer (pj) from its local image for gossip. Given a utility function, peer pi uses a content selection strategy to select sgm records (or smaller number when sgm records are not available) from its local image that are most useful for pj and send those records to pj . In response, pj f

47、ollows the same steps and replies with a gossip message that includes sgm records from its local image that are most useful for pi, i.e., bidirectional gossip. When a gossip message arrives at each peer, an image maintenance scheme integrates new records into the current local image and discards exc

48、ess records such that certain property of the local image is improved (e.g., increase overall utility of peers in the image) Aggregate performance of a gossip mechanism can be presented by two average metrics and their distribution among peers: (i) Average Convergence Time: average number of gossip

49、messages until all peers in an overlay reach their final images, and (ii) Average Efficiency Ratio: average ratio of unique records to the total number of received records by each peer. 2.2.4. PARENT SELECTIONThe PS mechanism at each peer is essentially a progressive search within the local image fo

50、r a subset of parent peers such that the following design goals are achieved: (I maximizing delivered bandwidth 5, (ii) minimizing the total delay from all parents to the receiver, and (iii) maximizing diversity of paths from parents (whenever it is feasible). The number of active parents (nopi(t) f

51、or each receiver should be within a configured range min nop, max nop. Each receiver tries to maximize its delivered bandwidth with the minimum number of parents. If this goal can not be achieved after evaluation of a certain number of new parents, the receiver will gradually increase its number of

52、parents. This flexibility is important in order to utilize available bandwidth from low bandwidth parents, i.e., cope with bandwidth heterogeneity. The number of active parents (nopi(t) for each receiver should be within a configured range min nop, max nop. Each receiver tries to maximize its delive

53、red bandwidth with the minimum number of parents. If this goal can not be achieved after evaluation of a certain number of new parents, the receiver will gradually increase its number of parents. This flexibility is important in order to utilize available bandwidth from low bandwidth parents, i.e.,

54、cope with bandwidth heterogeneity.The number of children for each peer should not be limited. Instead, each peer only limits maximum outgoing bandwidth that it is able (or willing) to provide to its children. This allows child peers to compete for congestion controlled bandwidth from a parent which

55、motivates child peers with poor bandwidth connectivity to look for other parents (i.e., properly reshape the overlay). 2.2.5. CONCLUSIONS In this part, we presented a simple receiver-driven framework for architecting peer-to-pee overlay structures called PRO. PRO allows each peer to selfishly and in

56、dependently determine the best way to connect to the overlay to maximize its performance. Therefore, PRO should be able to maximize delivered quality to peers with heterogeneous and asymmetric bandwidth connectivity. Both peer discovery and peer selection in this framework are scalable. Furthermore,

57、 PRO uses congestion controlled bandwidth as an implicit signal to detect shared bottleneck among existing parents as well as changes in network or overlay conditions to properly reshape the structure.2.3. Mesh Based P2P StreamingCommon approach: organize participating peers into a single tree-struc

58、tured overlayTwo limitations of the approach: (i) the delivered quality to individual peers is limited by the minimum bandwidth among the upstream connections from the source. This problem is further aggravated by the heterogeneity and asymmetry of access link bandwidth among peers. (ii) more importantly, the content delivery mechanism can not utilize the outgoing bandwidth of a large fraction of peers that are leaves in the tree. An extension of this approach organizes participating peers into multiple diverse trees.Two problems about Mesh-Based P2P: What is the global patt