Document Contents

• Overview
• Recent Accomplishments
• Current Work
• IETF Internet Draft Submission

More Information

Project Investigator

A brief bio of the PI.

People

People who work on the project.

Our Lab

A sketch of our lab.

Recent Papers

A list of papers on the project.

Research Facilities

A listing of the equipments in the Lab.

Related Projects

Other real-time related projects led by the PI.

Overview:

There has been an increasing need of highly predictable, timely, and dependable communication services with QoS guarantees on an end-to-end basis either for embedded real-time applications or for multimedia-integrated distributed control. In particular, the RSVP Working Group of the IETF has developed a resource ReSerVation Protocol (RSVP) protocol to provide receiver-initiated setup of resource reservations for unicast/multicast data flows. RSVP supports receiver-initiated, fixed/shared reservation styles under the assumption that a underlying routing protocol is available to provide unicast routes/multicast trees with sufficient resources to maintain adequate QoS. However, few of the existing multicast routing protocols explicitly support QoS-based routing. The main intent of this project is thus to develop a QoS routing framework and its associated admission control, member join/leave procedures, and state refresh and update procedures, to allow deployment of QoS routing capabilities in scalable core-based multicast routing protocols, e.g., Core Based Tree (CBT) Protocol, with the minimum possible impact to the existing infrastructure.

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.

Recent Accomplishments:

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 investigate the design tradeoff, of the proposed QoS-driven CBT protocol, in terms of message overheads, probability of locating feasible multicast trees, and scalability.

Current Work:

1. Based on the findings from the above research tasks, we are studying how to (optionally) support QoS-based multicasting for receiver heterogeneity, and how to accommodate controlled-load and guaranteed QoS network services. (the latter with the various reservation styles, e.g., fixed-filter, shared-explicit, and wildcard-filter reservation styles, as specified in RSVP).
   
   
2. As an alternative to provide the inter-destination delay jitter bound, we are developing a packet eligible time calculation mechanism and the associated information update and buffer management strategies. This mechanism, coupled with any multicast routing protocol that renders multicast trees which satisfy the end-to-end delay bound, can provide temporal QoS to applications.
   
   
3. Using the GateD Multicast source code (developed by the GateD Consortium, Merit Network, Inc.) as a software platform, we will
   prototype the proposed multicast routing scheme (as part of the multicast routing daemon (mrouted),
   define and implement an interface with RSVP that supports QoS-based routing (which may require minor changes in RSRR, the currently recommended routing interface for RSVP),
   develop an application level library to exploit the proposed services and provide a suite of multicast services with different levels of QoS.

IETF Internet Draft Submission