Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2000-03-21
2004-07-27
Olms, Douglas (Department: 2661)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S412000, C370S443000
Reexamination Certificate
active
06768744
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to improved methods and apparatus for regulating traffic in a communication network. In particular, the invention relates to the advantageous management of communication networks supporting multiple quality of service (QoS) classes utilizing generalized processor sharing (GPS) schedulers. In the present invention, GPS schedulers employing statistical methods allow efficient multiplexing of heterogeneous QoS classes.
BACKGROUND OF THE INVENTION
A simple communication network is comprised of nodes and endpoints, and links that connect individual nodes to other nodes and endpoints. Endpoints may be voice, data, text or video devices such as telephone sets, computers, fax machines, and the like. Individual links transmit voice, data, text, and video signals from endpoints to nodes, and between various nodes within a given communication network. Typically, each link is bi-directional, capable of carrying signals in a forward and reverse direction. Each link is characterized by certain bandwidth parameters that are a measure of a given link's capacity in each direction. Nodes typically include buffers, thereby enabling temporary storage of network traffic at that node. If a given link has insufficient bandwidth to carry the traffic received by that node at a given time, the buffer may be used to store the received traffic until the link can handle the stored traffic.
The explosive growth of consumer demand for Internet access, as well as other network applications, has resulted in a commensurate demand for additional bandwidth in high speed communication networks. The growth in available bandwidth has led to the development of a wide variety of applications with diverse QoS requirements, such as maximum allowable transmission delay and loss of information content, as well as bandwidth characteristics. Despite the growth of available capacity, bandwidth resource management still constitutes a challenge to network providers. The challenge is to provide a service level matched to the needs of a diversity of service requirements that network providers are contractually obligated to guarantee. One significant development in bandwidth resource management has been the utilization of large scale per virtual circuit (per VC) queuing in switch design, since it allows tight control over resource allocation and usage for each network connection. In this context, a virtual circuit (VC) is a connection in an asynchronous transfer mode (ATM) network that appears to the initiating and destination endpoints as a direct connection, regardless of the actual physical network path connecting those endpoints.
GPS schedulers allow substantial network capacity sharing, as well as isolation and QoS guarantees, by assigning a weight to individual connections. These weight assignments are chosen to closely correlate to the actual network traffic characteristics and QoS requirements. Higher weight connections are given a larger proportion of the available bandwidth than lower weight connections in order to maintain the QoS requirements of the particular network.
SUMMARY OF THE INVENTION
The present invention relates to advantageous methods and apparatus for bandwidth resource management in the implementation of GPS schedulers. GPS schedulers allow substantial network sharing capacity, as well as isolation and QoS guarantees. These advantageous properties of GPS schedulers are the result of the proper design of the weights assigned to individual network connections. The weights assigned are closely correlated to the characteristics of the actual network traffic as well as the QoS required for each network connection. In one aspect, the methods disclosed by the present invention allow an arbitrary number of QoS classes of service for an arbitrary number of class connections on a common trunk. In one embodiment, a central limit approximation, based on the central limit theorem, is used to model the aggregate activity of the connections. The performance of the GPS scheduler is governed by the scheduling weights associated with the individual connections. The weight selection for any given connection is formulated as a nonlinear set of algebraic equations. In another embodiment, a Chernoff approximation is applied in a similar manner.
The present invention is applicable to worst-case dual leaky bucket regulated (DLBR) connections, in which connections are classified by their leaky bucket parameters. The QoS is specified by the probability of violating the delay bound, where the probability and delay bound are QoS parameters associated with each connection class. Multiplexing gains are obtained by assuming that the regulated sources are independent and noncolluding.
In another aspect, the present invention provides an advantageous technique based on a reservation mechanism for the slow adaptation of weights, which may also be implemented by switching among a small set of precomputed weights. The technique of the present invention enforces fairness among connections with varying resource requirements, which is an important requirement of connection admission control (CAC).
A more complete understanding of the present invention, as well as further features and advantages, will be apparent from the following Detailed Description and the accompanying drawings.
REFERENCES:
patent: 6567415 (2003-05-01), Elwalid et al.
Kumaran Krishnan
Margrave Geoffrey Edmund
Mitra Debasis
Stanley Keith R.
Lucent Technologies - Inc.
Olms Douglas
Wilson Robert W.
LandOfFree
Methods and apparatus for managing communication networks... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatus for managing communication networks..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for managing communication networks... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3214325