Base tree construction

P2Cast employs the tree-first approach to construct the base tree. In general, there are two types of approaches in constructing the application-level multicast tree: the mesh-first approach and the tree-first approach. The mesh-first approach [6] builds up a mesh among the participating nodes first. The mesh is usually optimized toward the application requirement and is dynamically adjusted to accommodate the underlying network change. For instance, if a new arrival or node departure/failure occurs, the mesh is restructured to adapt to the change. A routing algorithm is run at each node. In the tree-first approach  [7,8], the application-level multicast tree is created directly. The arrival of new nodes or departure/failure of existing nodes triggers the restructure of the tree.

One design goal of P2Cast is to make the client as simple as possible. The mesh-first approach in [6] requires all participants to run a distributed algorithm to maintain the mesh, as well as a routing algorithm to route the traffic to the right peer nodes. In contrast, the nodes in the tree-first approach only need to provide a simple data forwarding function. Moreover, in P2Cast, there are frequent arrivals of new clients, which will keep disturbing the mesh construction and thus affect the overall performance. Based on the above considerations, we choose the tree-first approach. Below we list the design principles followed in the base tree construction in P2Cast.

• Bandwidth first principle. VoD service has a stringent bandwidth requirement but is relatively insensitive to the delay. A ``fat pipe'' (i.e., a path with abundant unused bandwidth) is more likely to offer good quality and be robust to transient network congestion. Therefore we would like to select the node with the fat pipe to the client.
• Local information only principle. Since the number of clients is large and dynamically varies over time, we want to avoid a requirement that any of the nodes have global information, such as the number of clients in the tree, the structure of the tree, etc.. In the process of base tree construction, only local information should be used. By local information, we mean the information about this node itself, its parent node, and its child nodes.

For a new client, the base tree joining process starts with the server. Streaming media service requires a minimum amount of available bandwidth from a parent node to a child node. The server measures the available bandwidth from itself to the new client, and decides whether this client can be its child node. If the server admits the new client, this client joins the base tree and receives the base stream from the server. Otherwise, the server redirects the new client to one of its existing child clients, denoted as candidate client. The candidate client makes its own decision as to whether to admit this new client to be its child node. If not, the new client is further re-directed to its child node. The process continues recursively until the client successfully joins the base tree, or is rejected.