Introduction
Overlay networks is a vehicle for delivering next generation network services over heterogeneous networks. Overlay networks allows service providers to create new services without the universal adoption from network providers, thus allowing accelerated deployment. Multicast is one of the network services that can be materialized using overlay networks. Historically, multicast has been viewed as a network primitive data service. The IP network has a specific range of addresses allocated as class D multicast addresses. However, despite of the continuing research effort, IP multicast has not lived up to its expectation and is plagued by the difficulties in scalable address allocation, membership control, and efficient resource usage. Without solving all of these technical issues, IP multicast is not likely to prevail and deliver what it has promised so long ago.
Overlay multicast service is a promising new direction that stands up at where IP multicast has failed. By shifting the multicast service from a primitive network layer mechanism to a service level infrastructure, overlay networks allow service providers to assume full control of its own service networks and make it easier for users to create sessions and obtain better quality of services. However, overlay multicast network presents new challenges from the network design perspective. How to provision the network so that service providers can efficiently allocate resources for as many sessions as possible while ensuring users receiving their desired service qualities? In this project, we investigate the main issues in designing an overlay multicast network.
Overview of Overlay Multicast Network
We refer to a generic advanced multicast service architecture using overlay networks as AMcast, illustrated on the left. In AMcast, Multicast Service Nodes (MSN) are placed in strategic locations and act as multicast proxies for end users. When a user wants to join an AMcast session, its proxy MSN joins the session and replicate and forward packets on this user's behalf. Among all MSNs within a session, they create a virtual multicast tree where each tree branch is an point-to-point connection. The use of unicast connections leverages the existing Internet infrastructure and avoids changes to routers or to user's operating systems.
Network Design Problems
MSN Placement The first problem faced by a service provider who wants to build an AMcast network is where to place the MSNs? There are two objectives for this problem: first, the service provider wants to minimize the network cost, represented by the number of deployed MSNs and the access bandwidth cost at each of the MSNs. Secondly, the service provider wants to place the MSNs such that all potential clients are within the service range of its nearest MSN so that the clients are able to receive good service qualities. Since bandwidth is rather plentiful in the backbone networks, the cost of the overlay network can be singly represented by the number of MSNs needed to support all clients within the service range. Futhermore, the service provider would like to investigate several variations of the placement strategy and their associated costs. For example, what if each client should be served by a backup MSN as well as a primary MSN? What is the cost if backup MSNs are allowed to be placed twice the range of the primary? What is the cost saving if service range can be relaxed? Or if we can compromise the service quality of some non-premier clients? In the following paper, we solve the placement problem by formulating it as a Integer programming problem for the set cover problem. The transformation from the placement problem to the set cover incorporates the various aforementioned strategies. We showed that under several network models, such a formulation can find a solution very close to the optimal solution.
Capacity Assignment The capacity assignment problem asks the question of How to assign access bandwidth capacity to individual MSNs given a fixed cost budget? For a multicast session, the number of tree branches at each MSN determines the amount of interface bandwidth required to support a session. MSNs located at geographical centers are likely to have larger number of branching connections, since branching at these places is more efficient in terms of the network resources used by the tree. Additionally, each MSN serves a different number of sessions depending on the number of local clients subscribed to the MSN. Therefore, the bandwidth capacity at an MSN is determined by its geographical location and the its client population. With a fixed cost budget, MSNs should be dimensioned accordingly in order to prevent the uneven use of interface bandwidths. In the following paper, we presented an iterative approach that dimension the MSNs to best carry a hypothesized multicast traffic load.
Multicast Routing The resources management in overlay networks is different from that in conventional network and routing procedures have to cope with these differences. The main resource concerned by a network service provider is the amount of total access bandwidth purchased at individual MSN locations. Additionally, the perceived performance of a multicast session can be viewed as the maximum delay experienced by any pair of nodes. Therefore, an overlay multicast routing algorithm must balance the bandwidth usage at MSNs as well as create a small diameter tree. Unfortunately, these two goals conflict: balancing the bandwidth usage often creates a tree with long paths, while a small diameter tree often concentrates traffic at a center node. In the following paper, we studied several heuristic algorithms that tackle the optimization problems and produce promising results for multicast routing in overlay networks.
Overlay Network Cost
While overlay network is promising in delivering the multicast service, it could exploit the resources of the underlying networks since the routing algorithm does not manage these resources explicitly. To study the cost associated with overlay multicast networks and the relative application performance of overlay multicast vs. IP multicast, we constructed two different types of networks, reflecting realistic networks as well as more homogeneous networks and simulated the performance of overlay multicast trees. For each of the performance metric, we compared the ideal and the pathological performance of overlay multicast trees with the optimal tree for the specific metric.