For ease of exposition, we use the CBT protocol as an example protocol, mainly due to its scalability, simplicity, and nature of receiver initiated requests to join a multicast group (which is well-suited to support heterogeneous resource reservation). However, the proposed work can be readily applied to any multicast routing protocol with explicit member join/acknowledgment procedures and soft state refresh/update procedures.

Specifically, we propose to make the following changes to the current CBT specification: each join-request message carries, in addition to the interface information, the accumulative delay information (or the available bandwidth along the route). When an off-tree router receives a join-request message, it forwards the request to the next router on the shortest path toward the core only if the partial path has sufficient resources (in both directions) to satisfy the QoS requirement. When a join-request message reaches the core or an on-tree router, the core/router performs a set of eligibility tests. Only after the branch survives the eligibility tests will it be eligible to join the multicast tree (under which case a join-acknowledgment message is then sent back).

In order to establish the theoretical base for, and realize, the above changes, we consider in this project the following research issues:

1. To avoid potential QoS conflicts among multiple routers that intend to join a multicast group, an off-tree router that receives multiple join-requests will not process the next request until it finishes processing the current join-request and sends back either a rejection-reply or a join-acknowledgment (in the latter case, the router becomes an on-tree router before processing the next request). Since a join-request message is not always routed on the shortest path to the core, loops may occur as demonstrated Figure (a). Moreover, since join requests are processed on a first-come-first-serve basis and are blocked if they arrive at an off-tree router which is currently processing a join request, deadlocks may arise as demonstrated Figure (b)--(d). We have devised a simple and effective method to detect and break loops and deadlocks.
   
   
2. If the partial path does not satisfy the QoS requirement, an off-tree router attempts to send a join-request message on another outgoing interface. If after attempting all possible interfaces without success, the router sends a rejection-reply message one-hop downstream to the router from which the join-request came. The above approach keeps the changes to the current CBT protocol specification as small as possible, while incorporating the QoS consideration. However, the above off-tree search is in nature exhaustive. We have studied how to reduce the message overhead incurred in the off-tree stage search.
   
   
3. For each QoS under consideration, we have derived the sufficient condition that a multicast tree has to satisfy in order to fulfill the QoS considered. Based on the sufficient conditions derived, we have devised effective eligibility tests to verify whether or not a new member can join a multicast tree at adequate QoS, while not violating the existing QoS guarantees to other on-tree members.
   
   
4. We have developed member join/leave procedures that deal with simultaneous multiple membership changes in a decentralized manner. Specifically, we devise auxiliary eligibility tests to determine whether or not join of a new member at an on-tree router may affect the state information kept at other on-tree routers and, in the case that the state information needs to be updated, the subsequent procedure.
   
   
5. To make the proposed framework scalable to multicast groups of large sizes and to a large number of multicast groups, we have identified the minimum set of information needed for eligibility tests, and devised a soft state refresh and update procedure. The state refresh and update procedure can be readily integrated with the state refresh mechanism that already exists in most multicast routing protocols that deploy the soft state concept, e.g., sending of echo-requests and echo-replies in CBT. As a result, the message overhead due to state update and refresh is at most as much as that due to state refresh in the soft state approach.
   
   
6. Using our custom-developed QoS-driven network simulation tool, NetSim^Q, we have studied the performance, and investigated the design tradeoff, of the proposed QoS-driven CBT protocol, in terms of message overheads, probability of locating feasible multicast trees, and scalability. A set of experimental results are listed here.

Return to Project Homepage
Date last modified -- August 3, 1998
Direct comments concerning this WWW site to: jhou@ece.osu.edu