Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
1998-06-05
2002-04-02
Marcelo, Melvin (Department: 2663)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
C370S238000
Reexamination Certificate
active
06366559
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates generally to traffic admission control and routing in communications networks, and more particularly, to systems and methods for controlling admission and routing of multi-rate, circuit-switched traffic in communications networks.
A communications network generally includes a plurality of nodes interconnected by transmission links (or “links”). Each link includes one or more trunks, which, in combination, define the total bandwidth (or “capacity”) of the link. In a circuit-switched network, the network must set up a dedicated connection between a set of nodes in order to transport certain incoming traffic through the network. The selected set of nodes that make up a connection is generally referred to as a route.
When traffic arrives at the circuit-switched network, the network must determine whether to admit the traffic into the network, and if admitted, must determine how to route the traffic through the network given the current state of the links in the network. The state of a link may be represented by the available bandwidth in the link, for example, the number of free trunks in the link. A routing scheme that is based on the current state of each link in the network is referred to as a state-dependent routing scheme.
In a circuit-switched network, single-rate traffic includes calls that have identical bandwidth requirements and mean durations. Single-rate traffic may include one or more calls that carry only a single class of traffic, for example, voice. Multi-rate traffic, however, includes one or more calls that have different bandwidth requirements and durations and are multiplexed together onto a single link. For example, multi-rate traffic may include calls that carry multiple classes of traffic, for example, voice, video, and data, which are multiplexed together.
When a communications network multiplexes different classes of traffic onto a link, the traffic loss rate of the link may increase depending upon the specific bandwidth requirements, grades of service, and holding times of the different classes of traffic that are multiplexed together, even though the multiplexing results in a higher throughput in the link. For example, when two traffic classes with different mean holding times are combined onto a single link, it is possible that the loss rate of the combined traffic stream may be higher than the loss rate of each individual traffic stream when each stream is served by its own dedicated link, assuming that the single link has a bandwidth equal to the sum of the capacities of the dedicated links. A similar effect occurs when the two classes of traffic have different bandwidth requirements and require different grades of service. Thus, the network must provide a mechanism for controlling and routing the multi-rate traffic through the network while minimizing the traffic loss rate in the network.
As a result, when a network multiplexes together traffic streams of dissimilar characteristics to generate multi-rate traffic, the loss rate of some traffic classes may increase as a result of the multiplexing, while at the same time the loss rate of other traffic classes may decrease. Thus, in order to achieve multiplexing efficiency in all cases, there is a need for a traffic control and routing method that does not increase the loss rate of the resulting multi-rate traffic in the network.
One solution is to impose a set of bandwidth reservation-levels on the different classes of traffic that are multiplexed together onto a link, restricting admission of certain classes of traffic even when there is sufficient bandwidth available at the time the traffic arrives. This restriction protects the service level (i.e., the traffic loss rate) of other classes of traffic. However, there is yet no satisfactory method or system for determining an optimum set of bandwidth reservation levels for the different traffic classes that would minimize the traffic loss rate in the network.
Several solutions exist for determining traffic admission and routing rules that would minimize the traffic loss rate in a circuit-switched communications network. U.S. Pat. No. 4,704,724, entitled “Routing of Network Traffic” and U.S. Pat. No. 4,788,721, entitled “Routing of Network Traffic,” disclose state-dependent routing methods for single-rate traffic that take into consideration the number of future traffic rejections in the network. While these two methods may be sufficient for single-rate traffic, the application of these methods to multi-rate traffic, especially for large number of traffic classes, is computationally intractable.
A. Kolarov and J. Hui, “On Computing Markov Decision Theory-Based Cost For Routing In Circuit-Switched Broadband Networks,” Journal of Network and Systems Management, 3 (1995), discloses a method for routing multi-rate traffic in a network by partitioning the bandwidth of each link in the network among different classes of traffic. This method, however, is also computationally intractable, especially when applied to a network with a large number of classes of traffic.
R-H. Hwang, J. F. Kurose, and D. Towsley, “State-Dependent Routing For Multi-Rate Loss Networks,” IEEE Globecom 1992, Orlando (1992), discloses a method for routing multi-rate traffic in a network based on the total occupancies (i.e., allocated bandwidth) of links in the network. This method, however, is based on an approximation that treats multi-rate traffic as single-rate traffic.
Thus, it is desirable to have methods and systems for controlling and routing multi-rate traffic in a circuit-switched communications network that do not have the above-mentioned disadvantages.
DESCRIPTION OF THE INVENTION
The present invention comprises a method and system for controlling multi-rate traffic onto a link in a communications network by determining, with respect to a fixed occupancy in the link, a set of expected admission costs that corresponds to a set of occupancies in the link, respectively, and determining a difference between the expected admission cost that corresponds to the occupancy of the link resulting from admission of the multi-rate traffic onto the link and the expected admission cost corresponding to a current occupancy of the link. If the difference is less than a pre-determined cost threshold, the network admits the multi-rate traffic onto the link. If the difference is equal to or greater than the cost threshold, the network rejects the multi-rate traffic such that the total traffic loss rate in the link is minimized.
Specifically, the occupancy of a link is defined by the total traffic that is in progress in the link or the number of busy trunks in the link. The expected admission cost of the think is defined by the expected additional number of future calls that the network will have to reject from the link as a result of admitting the current call onto the link.
The present invention further comprises a method and system for routing multi-rate traffic in a communications network by determining a first expected admission cost difference corresponding to admission of the traffic onto a single-link route. An expected admission cost difference is a difference between the expected admission cost that corresponds to the occupancy of the single-link route resulting from admission of the traffic onto the single-link route and the expected admission cost corresponding to a current occupancy of the single-link route. If the first expected admission cost difference is less than a pre-determined cost threshold, the network routes the traffic through the single-link route.
If the first expected admission cost difference is equal to or greater than the cost threshold, the network determines a second set of expected admission cost differences that corresponds to admission of the traffic onto a set of multi-link routes, and selects the multi-link route that has a minimum expected admission cost difference. If the minimum expected admission coat difference is less than the cost threshold, the network routes the traffic through the selected mult
de Bucs Frank Huebner-Szabo
Krishnan Komandur R.
Falk James W.
Giordano Joseph
Marcelo Melvin
Telcordia Technologies Inc.
Trinh D.
LandOfFree
Method and system for state-dependent admission control and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for state-dependent admission control and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for state-dependent admission control and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2917657