Routing virtual circuits with temporal QoS requirements in virtual path-based ATM networks

Real-time communication with performance guarantees is expected to become an important feature of future computer networks used for embedded real-time systems and/or for interactive multimedia services. Given an ATM network topology, its virtual path (VP) layout, and its traffic demands, we consider in this paper the problem of selecting for each virtual circuit (VG) with user-specified end-to-end temporal QoS requirements a route (i.e., a sequence of VPs) along which sufficient resources are available to meet the delay requirements. Our objective is 1) to provide the temporal QoS guarantee for each VC to be established while not jeopardizing the QoS guarantees to other existing VCs and 2) to reduce the call blocking probability for future VCs by using the minimum possible resources. We adopt the real-time channel model [16], [33], [51] to characterize the traffic characteristics and the temporal QoS requirement of a VC. We impose a deterministic guarantee that every message generated at the source node be delivered to the destination node in a time period no longer than the relative deadline. We then propose a VC routing scheme based on the distributed Bellman-Ford algorithm [9], [41] to identify an "appropriate" route through the network. By "appropriate," we mean that the route traverses a minimum number of VPs among all possible routes that have sufficient resources to fulfill the end-to-end temporal QoS requirement of the VC to be established. To ensure that sufficient bandwidth is available over all the VPs along the selected route, we incorporate in our proposed scheme a priority assignment method to calculate the worst-case delay which messages of a VC will experience on a VP along which the VC is routed. We study the performance of, and the message overhead incurred in, the proposed scheme. We also discuss how to extend the proposed routing scheme to accommodate multicast routing.