Dynamic bandwidth and buffer management algorithm for...

Details Dynamic bandwidth and buffer management algorithm for... Dynamic bandwidth and buffer management algorithm for...

1998-02-03

2001-05-29

Kizou, Hassan (Department: 2662)

Multiplex communications

Data flow congestion prevention or control

Control of data admission to the network

C370S395430

Reexamination Certificate

active

06240066

ABSTRACT:

FIELD OF THE INVENTION
The instant invention relates generally to ATM-based switching technology and, particularly, to a method of providing dynamic allocation of bandwidth and buffer resources capable of meeting quality of service (“QoS”) requirements for each of multiple ATM service classes at an ATM switch.
BACKGROUND OF THE INVENTION
With the ever increasing demand for bandwidth and end-to-end performance guarantees presented by emerging networked applications, high speed networking techniques have been evolving at rapid pace in recent years. One of the most promising enabling technologies is the cell switching and networking techniques of ATM which provides the core transport needed to support multiple services at extremely high speed and fast decreasing cost. Central to this new technology are ATM-based switches that are capable of supporting diverse end-to-end quality-of-services through effective resources and traffic management methods which allow for efficient sharing of switch and network resources.
In recognizing such needs, a number of standards organizations have specified the service classes and various traffic management interfaces and attributes for ATM networks and services. For example, ATM Forum has defined five service categories: constant bit rate (“CBR”), real time variable bit rate (“rt-VBR”), non-real time variable bit rate (“nrt-VBR”), available bit rate (“ABR”) and unspecified bit rate (“UBR”). Quality of service (QoS) is parameterized for each service and can be requested at call setup time for switched and permanent virtual connections. From the perspective of an ATM switch, this presents a challenge to resource and traffic management since one must allocate and share, in real-time, the resources efficiently among diverse services requested by connections.
As an example, a generic output-queuing ATM switch on a single ATM interface card
10
shown in FIG.
1
. Typically such a card includes multiple physical ports
20
such as e.g., T
1
, DS
3
and OC-
3
ports. At each physical port, there are typically multiple queues
30
associated with multiple service classes such as CBR, rt-VBR, etc. In the extreme case there may be per-VC queuing. A buffer
40
is provided that may be shared by all the queues at all the ports or at least among queues for a single port. The bandwidth is shared through e.g., some variation of a weighted round-robin discipline as indicated by link schedulers
15
in FIG.
1
.
In a queuing-theoretic framework, the ATM switch of
FIG. 1
translates to a multi-queue, multi-server environment with a round-robin service discipline within the service classes at a port and a shared buffer across all the ports. From the QoS point of view, the focus relates to the performance bounds for individual connections or at least on a per-queue (class) basis. The literature is severely limited in terms of results for such queuing systems even in the case of a single-server system, however, there has been recent work done on deterministic performance bounds for generalized processor sharing queuing systems, e.g., as described in A. K. Parekh and R. Gallager, “A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks: The Single Node Case,”
IEEE/ACM Transactions on Networking,
Vol. 1, No. 3, pp. 344-357, June 1993, hereby incorporated by reference as if fully set forth herein. However, these deterministic bounds are typically fairly loose, lead to poor link utilization and hence are of limited usefulness.
There has also been work on statistical performance bounds which appear promising, but more work needs to be done to make these bounds suitable for a real-time call admission control (“CAC”). See, Zhi-li Zhang, et al., “Statistical Analysis of Generalized Processor Sharing Scheduling Discipline,” IEEE Journal of Selected Areas in Communication Vol. 13, No. 6 p 1071-80 (August 1995), hereby incorporated by reference as if fully set forth herein.
There however, exists literature on performance bounds for single-queue, single-server fluid models. Additionally, the related problem of Call Admission Control in these systems has been studied extensively where the typical problem addressed is how to estimate the steady state loss or delay performance given fixed buffer and bandwidth resources and a set of connections with specified traffic descriptors and given QoS requirements. In reality, however, buffer and bandwidth are, and need to be, shared among several services as connections arrive and depart in unpredictable patterns. Thus, it would be highly desirable to provide a dynamic scheme by which bandwidth and buffer are managed simultaneously and dynamically allocated to each service. See also Keith Ross, “Multiservice Loss Models in Broadband Telecommunication Networks” (1995) and Raffaele Bolla et al., “Bandwidth Allocation and Admission Control in ATM Networks with Service Separation,” IEEE Communications Magazine Vol. 35, No. 5 (May 1997), hereby incorporated by reference as if fully set forth herein. These references consider dynamic bandwidth allocation but do not consider the buffer resource. Additionally, “Bandwidth Allocation and Admission Control in ATM Networkds with Service Separation,” supra, only allows for homogenous connections, i.e., identical traffic parameters, and QoS requirements within a service class. This is not a realistic scenario in practice.
SUMMARY OF THE INVENTION
The instant invention is a method for resource allocation involving the notion of multiple classes to be allocated buffer and bandwidth resources separately. In the context of the ATM interface card, the individual buffer and bandwidth requirements for ATM service classes are determined separately given the traffic load and QoS requirements. Hence, multiplexing effects only within a service class are accounted for with service class interactions being decoupled. For connection admission purposes, a check is made as to whether the aggregate of the service class buffer and bandwidth requirements is less than total amount of buffer and bandwidth. Since the notion of a resource allocation class is general, however, one can choose to define resource allocations to different classes. For example, nrt-VBR connections that request different CLR QoS′ may be defined as belonging to different classes.
Advantageously, the inventive method for dynamic buffer and bandwidth partitioning manifests several desired properties including: A) tight allocations of buffer and bandwidth; B) allocation of buffer and bandwidth in controlled (weighted) proportion (relative to the total available resources) for nrt-VBR; C) computationally fast operation to allow for real-time execution; D) support of multiple and varied QoS criteria; E) operating independent of the choice of the CAC/QoS computation engine for each class; and F) enablement of controlled rate of changes in the buffer and/or bandwidth allocation.
The various features of novelty which characterize the invention are pointed out with particularity in the claims annexed to and forming a part of the disclosure. For a better understanding of the invention, its operating advantages, and specific objects attained by its use, reference should be had to the drawing and descriptive matter in which there are illustrated and described preferred embodiments of the invention.


REFERENCES:
patent: 5757771 (1998-05-01), Li et al.
patent: 5982748 (1999-11-01), Yin et al.
Keith W. Ross, “Multiservice Loss Models for Broadband Telecommunication Networks,” pp. 145-150 (Springer-Verlag London Limited 1995).
Kiran M. Rege, “Equivalent Bandwidth and Related Admission Criteria for ATM Systems-A Performance Study,”Intern'l Journal of Communication Systems, vol. 7, 181-197 (1994).
Abhay K. Parekh and Robert G. Gallager, “A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks: The Single-Node Case,” IEEE/ACM Transactions On Networking, vol. 1. No. 3 (Jun. 1993).
Zhi-Li Zhang, Don Towsley and Jim Kurose, “Statistical Analysis of Generalized Processor Sharing Scheduling Dis

Affiliated with

Also associated with

Rating

Dynamic bandwidth and buffer management algorithm for... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Dynamic bandwidth and buffer management algorithm for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dynamic bandwidth and buffer management algorithm for... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2509407