Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1999-03-20
2003-05-20
Vincent, David (Department: 2732)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S468000
Reexamination Certificate
active
06567415
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to the field of methods for regulating traffic in a communications network. More particularly, this invention relates to generalized processor sharing (GPS) schedulers, and specifically, to GPS schedulers which statistically multiplex heterogeneous quality of service (QoS) classes.
BACKGROUND OF THE INVENTION
A communications network is one means for transmitting or carrying traffic (e.g., signals representing information such as data, voice, text, and/or video) between endpoints (e.g., host machines, fax machines, or terminals) connected to the network. The network comprises nodes connected, to each other and to the endpoints, by links. Typically, each link is bi-directional (i.e., traffic may be conveyed or transmitted in the forward and reverse directions), and each link is characterized by parameters, such as bandwidth or capacity in each direction. The nodes advantageously include buffers. If a link does not have a sufficient available bandwidth to carry traffic received at a node, a buffer in the node may be used to store the received traffic until such time as the link has a sufficient available bandwidth.
Networks are increasingly being used for the reliable, high-speed transmission of traffic between endpoints over wide areas. This increased use is bringing major changes to network services and architecture/infrastructure design. In particular, a wide spectrum of new consumer and business services, such as video-on-demand and video teleconferencing, are expected to be offered on Broadband Integrated Services Digital Networks (BISDN) as well as Internet telephony. These new services will be characterized by a wide range of traffic characteristics (e.g., bandwidth) and with different quality of service (QoS) requirements (e.g., maximum delay through the network and maximum information loss rate). The principal technique for transmission in BISDN is Asynchronous Transfer Mode (ATM). See, for example, S. E. Minzer, “Broadband ISDN and Asynchronous Transfer Mode,” IEEE Comm. Mag., pp. 17-24. September 1989. Other transmission techniques include Internet Protocol (IP), among others.
When traffic is to be carried in an ATM network, an initiating endpoint requests that a bi-directional path (i.e., a connection comprising nodes and links) be established in the network between the initiating endpoint and a specified destination endpoint. In an ATM network, the path that is established is a so-called “virtual circuit” (VC) by which it is meant that the initiating endpoint simply specifies the destination endpoint, and the network carries the traffic from the initiating endpoint to the destination endpoint as though they are connected by a direct circuit. A VC is also referred to herein as a connection. Traffic in an ATM network is formatted into cells or packets. Note that in Internet Protocol networks, no connection is defined, but packets belonging to different flows are, however, identified.
Admission control policies govern whether the network can accommodate, for example, a request to establish a new VC. The admission decision is typically based on: (1) traffic descriptors (e.g., average bandwidth and burstiness) characterizing the traffic to be carried and (2) any quality of service requirements for the traffic. The admission decision will also be based on what resources are available in the network (e.g., the amount of unused bandwidth in the links, and the unused buffer space in nodes) to accommodate the request. A request for admission typically will specify or provide the traffic descriptors. The network will, in turn (based on the specified traffic descriptors), determine the amount of network resources that will need to be assigned to the request. Based on the determination, the network will decide whether to admit the request. If the request is admitted, a “contract” is made by which the network agrees to carry the traffic and to meet any quality of service guarantees so long as the traffic stays within the specified traffic descriptors. The performance of ATM or IP networks depends on admitted connections complying with their contracts. For example, congestion may be caused by an endpoint supplying information to the network so as to exceed contract specifications, thereby causing statistical fluctuations in the traffic flow through the network. Such fluctuations can degrade network performance and affect quality of service levels for other connections in the network. Accordingly, a network typically monitors, or controls traffic on, connections to ensure that the connections comply with their contracts.
Various techniques have been proposed to monitor and control traffic on networks, as well the allocated resources. Generalized Processor Sharing (GPS) provides the basis for the packet scheduler of choice in Internet Protocol (IP) routers and ATM switches of the future. See, e.g., S. Keshav,
An Engineering Approach to Computer Networking,
Addison-Wesley, Reading, Mass., 1997; G. Kesidis,
ATM Network Performance
, Kluwer, Boston, Mass., 1996; D. Stiliadis and A. Varma, “Rate-proportional servers: A design methodology for fair queueing algorithms”,
IEEE/ACM Trans. Networking
6, April 1998, pp. 164-74; and D. Stiliadis and A. Varma, “Efficient fair queueing algorithms for packet-switched networks”,
IEEE/ACM Trans. Networking
6, April 1998, pp. 175-85. A GPS scheduler defines how cells are serviced out of the buffer of a connection and sent over the link with a specified total link bandwidth.
The currently accepted approach for the design of the GPS scheduler and the control of networks which use it is based on deterministic QoS guarantees. In this connection, the work and bounds of Parekh and Gallager form an important and original point of reference. See, e.g., A. K. Parekh, “A generalized processor sharing approach to flow control in integrated services network”, Ph.D. dissertation, LIDS-TH-2089, MIT, February 1992; A. K. Parekh and R. G. Gallager, “A generalized processor sharing approach to flow control—The single node case”,
IEEE/ACM Trans. Networking
1, June 1993, pp. 344-57; and Parekh et al. and R. G. Gallager, “A generalized processor sharing approach to flow control in integrated services network—The multiple node case”,
IEEE/ACM Trans. Networking
, April 1994, pp. 137-50. However, it is generally accepted that the deterministic bounds using lossless multiplexing are overly conservative, thus limiting capacity and the utility of the approach to guide the design and operations of real networks.
SUMMARY OF THE INVENTION
To address the limitations of deterministic QoS guarantees, this invention develops a framework for GPS scheduling and network control which is based on statistical QoS guarantees and statistical multiplexing. We give the design of GPS weights which maximize coverage of operating points in the number of connections of heterogeneous QoS classes with only a very small repertoire of weights, together with the associated design of connection admission control (CAC). The gain in capacity is then typically significant.
The description and results presented here are in the framework of end-to-end QoS guarantees, but could be used in the context of any scheduling problem requiring QoS guarantees, including IP networks. We consider two heterogeneous QoS classes coexisting with a third, best effort class. These three classes are sometimes referred to in the industry as gold, silver and bronze QoS guarantees. The QoS classes have a specified end-to-end delay requirement together with a bound, typically quite small, on the probability of its violation, or loss. The role of the best effort traffic is important in our conceptual framework, and a high level objective is to maximize the bandwidth available to best effort traffic while just satisfying the guarantees of the QoS classes.
The main contributions of this invention are for a single node in which the service discipline is GPS. The procedure applies to each node on the end-to-end path, provided peak-rate regulation is carried out as described bel
Elwalid Anwar
Mitra Debasis
De La Rosa & De La Rosa, LLC
Lucent Technologies - Inc.
Vincent David
LandOfFree
Packet scheduling in a communication network with... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Packet scheduling in a communication network with..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Packet scheduling in a communication network with... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3020774