Tree-based Overlay Networks

In the tree-based approach, end-hosts are organized into either a single tree or a multi-tree structure. The root of the tree is a multicast source. Data are transmitted from the source to participating peers along the tree route. Each internal node receives data from its parent node, and then forwards the received data to its child nodes if available.

Thus, the content delivery in the tree-based overlay is called a push-based method.

2.2.3.1 Single-tree Approaches

End System Multicast (ESM) [7] is one of the pioneer works, which demonstrates the feasibility of implementing multicast function at end systems without any modification of network infrastructure. ESM does not rely on router support for multicast. It abstracts the physical topology as a Complete Virtual Graph (CVG), and then constructs a spanning tree of CVG so that a peer could send data to others.

Figure 2.6: Examples of IP multicast and End System Multicast.

2.2 APPLICATION LAYER MULTICAST 17

Figure 2.6 (a) illustrates examples of network topology consisting of routers R1, R2 and end hosts A, B, C and D. The numbers indicate link delays. The physical topology can be mapped into a graph as shown in Figure 2.6 (b). Assume that host A is a source wishing to send data to all other nodes. As shown in Figure 2.6 (c), the distribution tree of IP multicast is constructed by a source-based tree method. Since the tree is built with the reverse shortest paths from each receivers to the source, each receiver receive data with the same delay as though source A sending data by unicast.

The graph of this IP multicast is depicted in Figure 2.6 (d). To improve delivery delay, ESM builds the smarter tree as shown in Figure 2.6 (e). Figure 2.6 (f) illustrates how this tree maps onto the underlying network. With ESM, we can see that host D, for example, can receive data from host C with shorter delay than receiving them directly from the source.

PeerCast [27] is another example of tree-based streaming system. In PeerCast, nodes are organized into a single tree overlay. A new node joins the system by sending a request to a source node (root). If the source has available capacity (i.e., degree), it accepts the new node as its child and provides service for the new node directly.

However, if the source has no available capacity, it will redirect the request of the new node to one of its child nodes. The child nodes then repeat this process until the parent of the new node is found. Another tree-based P2P streaming system is ZIGZAG [28].

With a single tree structure, a short end-to-end delay can be achieved since video data are forwarded (pushed) from node to node along the pre-defined routes without a request requirement. Nevertheless, the major problem of the single-tree method is that it usually suffers from service disruption and frequent tree reconstruction caused by the departure or failure of parent nodes, especially those in the high-level close to the source. Moreover, the bandwidth utilization of nodes in the single tree is significantly unfair. This is because the leaf nodes in the single tree overlay only receive data but have no contribution to the system.

2.2.3.2 Multi-tree Approaches

To address the mentioned problems, the multi-tree approaches (e.g., SplitStream [29] and CoopNet [30]) have been proposed. In the multi-tree approach, end-hosts are organized into a forest of multicast trees. The structure of the overlay depends on the download and the upload capacities of the peers and design strategies.

18 CHAPTER 2 BACKGROUND AND RELATED WORK

SplitStream [29] is a typical model of multi-tree based streaming system.

SplitStream is built on top of Scribe multicast system [31], which itself is built on top of Pastry overlay network [16]. In particular, Pastry assigns each node a random identifier, called nodeId. Normally, Pastry forwards a message towards nodes whose nodeIds share longer prefixes with the message’s key. Scribe gives each group of nodes a random key, called, groupId. Then, a Scribe tree can be formed by the routes from all members to the groupID. As a result, the nodeIds of all interior nodes share some number of digits with the tree’s groupID.

Figure 2.7: Multi-disjoint-tree of SplitStream.

The source of SplitStream encodes and splits the original content into several stripes, and multicast each strip through a separate tree. Each stripe is assigned with stripeId starts with a different digit. The typical way to encode the media file is to use a multiple description coding (MDC) technique. With MDC, each description of the encoded content can be dependently decoded by a peer. The more descriptions the peer receives, the higher video quality it can experience. The challenge is to construct the multiple-disjoint-trees such that an interior node in one tree is a leaf node in all the remaining trees. Multiple-disjoint-trees can be formed by placing a node whose nodeID share a prefix with the stripeId as an interior node in that tree and leaf nodes in the other trees. Ideally, if all nodes wish to receive k stripes and then forward all k strips, the forwarding load could be balanced evenly. Figure 2.7 shows the sample multi-tree structure of SplitStream. Node A with nodeId starting with 1 is an interior node in the tree whose stripeId starting with 1 and a leaf node in all other trees.

The robustness in SplitStream derives from the construction of multiple- disjoint-trees where the vast majority of nodes are interior nodes in only one tree.

2.2 APPLICATION LAYER MULTICAST 19

Therefore, the failure or departure of a peer affects only one tree. In the case of packet losses, peers can reconstruct the video stream of the set of received description using error correction codes.

Figure 2.8: Deadlock event when a node cannot rejoin the tree.

However, in the presence of highly dynamic joining and leaving of nodes, a tree could become saturated and unable to accept any new leaf node. This situation is called, a deadlock event. A deadlock event occurs when a tree loses a fraction of its internal nodes which reduces the number of leaf nodes it can accommodate. As a result, some nodes which are impacted by parent departure, cannot rejoin the tree. This situation occurs within a short period of time until the isolated nodes can rejoin the tree successfully. For example, from Figure 2.8, consider the case when node 6 leaves the overlay. Node 2 and node 7 are disconnected from a tree because of node 6’s departure.

One of the child nodes (assumed to be node 2) can take the position of node 6, but another one (i.e., node 7) cannot reconnect since there is no capacity for it. This is because a node cannot be an interior node in more than one tree.