Method of admission control for packetized communication...

Details Method of admission control for packetized communication... Method of admission control for packetized communication...

2000-03-23

2004-08-03

Kizou, Hassan (Department: 2662)

Multiplex communications

Data flow congestion prevention or control

Control of data admission to the network

C370S395200, C370S395400

Reexamination Certificate

active

06771598

ABSTRACT:

FIELD OF THE INVENTION
This invention relates to methods of Connection Admission Control (CAC) in packetized communication networks. More particularly, the invention relates to CAC in networks that apply the Earliest-Deadline-First (EDF) scheduling discipline.
ART BACKGROUND
FIG. 1
schematically depicts a simplified packet network in which users
10
.
1
-
10
.
3
,
12
.
1
-
12
.
4
, and
15
.
1
-
15
.
3
can intercommunicate via interconnected servers or switches
20
.
1
-
20
.
5
. The network has been simplified for illustrative purposes; real-life networks will typically have many more users and servers than shown in the figure. If, e.g., user
10
.
1
wishes to reach user
15
.
1
through the network, user
10
.
1
will issue a request to its associated server
20
.
1
to set-up a session. A session is a collection of related packets having a fixed path from a source to a destination, and having a specified description of properties such as packet-injection rate, burst size, and maximum packet length. The fixed path will typically be determined when the user makes the set-up request, and may be determined by the first server
20
.
1
. The set-up request is passed to every server along the path. Each server engages a function, referred to as Connection Admission Control (CAC), which determines whether to admit the requested session. If the session is admitted by every server along the path, the set-up request is honored and the packets can be sent.
Each server e has a finite processing rate C
e
. That is, each server e can relay its queued packets to the next server (or from the last server to the destination user) at a rate no greater than C
e
bits per unit time. Because this processing rate is finite, some bits will generally accrue delay at some or all of the servers along the path.
Excessive packet delay may be intolerable to customers of various kinds of network traffic, such as voice traffic, which is notoriously delay-sensitive. It is of increasing interest to specify, inter alia, the delay performance demanded of a network under the rubric of Quality of Service (QoS) requirements. In this regard, a typical QoS requirement is that packet delay in a specified class of service must always be less than a specified threshold, or (if it is a probabilistic requirement) that there must be no more than a specified probability that packet delay will exceed the threshold.
In networks subject to QoS requirements, the CAC function will consider whether the specified limits on delay can be met. If it is determined that the specified limits cannot be met, the offered session will be denied admission. Whether these limits can be met will depend, in part, on how the resources of the server are allocated among sessions. (It should be noted that the term “session” as used herein is synonymous with the term “connection” in the sense that would apply in the present context.) Such allocations are governed by so-called scheduling disciplines. Two prominent scheduling disciplines are those known as Generalized Processor Sharing (GPS) and Earliest-Deadline-First (EDF). Under GPS, the server partitions its resources among connections according to specified weights. Under EDF, the server assigns a deadline d
p
to each incoming packet p upon arrival, and then always serves the packet with the earliest deadline. For a given network state, each scheduling discipline may lead to a different decision regarding the admissibility of a newly offered session.
Most approaches to the delay-based admission decision have relied on worst-case assumptions, e.g., that all sessions will simultaneously send a burst of packets at the peak arrival rate. Approaches that rely on such assumptions are disadvantageous because they will deny admission to an excessive number of calls. Some improvement in the amount of carried traffic has been achieved, at least exploratorily, through the approach known as statistical multiplexing, which takes advantage of the statistical nature of the offered traffic in order to accept more offered sessions while adhering to probabilistic delay bounds. Discussions of statistical multiplexing as applied to GPS scheduling can be found, for example, in A. Elwalid et al., “Design of generalized processor sharing schedulers which statistically multiplex heterogeneous QoS classes,”
Proc. IEEE INFOCOM '
99 (March 1999) 1220-1230, and in K. Kumaran et al., “Novel techniques for the design and control of Generalized Processor Sharing schedulers for multiple QoS classes,” submitted for publication in
Proc. IEEE INFOCOM '
00, (March 2000).
Until now, however, there has been no application of statistical multiplexing to delay-based admission decisions under the EDF scheduling discipline.
SUMMARY OF THE INVENTION
I have developed a new method for estimating the probability of violating a packet-delay bound under the EDF scheduling discipline. My method takes into account the statistical properties of offered network traffic, and thus comes under the scope of statistical multiplexing. My method will make it possible for a server employing EDF to satisfy probabilistic QoS requirements while admitting many more offered sessions than possible using the older CAC methods that rely on worst-case assumptions about the offered traffic.
Thus, in one aspect, my invention involves a method for determining the admissibility of an offered session of traffic of a specified class to a server in a packetized communication network. Each class c has a peak traffic rate r(c). The server has a total processing rate C. Admitted packets are scheduled according to an EDF scheduling discipline. The method for determining admissibility comprises defining an operating point for the server. The operating point represents the number of sessions N
c
of each respective class currently offered or currently being served. The method further comprises determining whether the defined operating point falls within a set of operating points that together define an admissible region. The admissible region consists of operating points for which the probability of violating a delay bound for any packet is below a threshold. In contrast to methods of the prior art, the admissible region includes at least one point that would lead to violations of the packet-delay bound if all sessions were to simultaneously start sending a burst of packets at the peak arrival rate.


REFERENCES:
patent: 5357507 (1994-10-01), Hughes et al.
patent: 5838663 (1998-11-01), Elwalid et al.
patent: 5978356 (1999-11-01), Elwalid et al.
patent: 6028840 (2000-02-01), Worster
patent: 6442138 (2002-08-01), Yin et al.
Elwalid, A. et al., “Design of Generalized Processor Sharing Schedulers which Statistically Multiplex Heterogeneous QoS Classes,”Proc. IEEE INFOCOM '99pp. 1220-1230 (1999).
Kumaran, K. et al., “Novel Techniques for the Design and Control of Generalized Processor Sharing Schedulers for Multiple QoS Classes,”Proc. IEEE INFOCOM '00(Mar. 2000).
Liebeherr, J. et al., “Exact Admission Control for Networks with a Bounded Delay Service,”IEEE Transactions on Networking 4(1996).
Georgiadis, L. et al., “Optimal Multiplexing on a Single Link: Delay and Buffer Requirements,”IEEE Transactions on Information Theory 43.
Andrews, M. et al., “Dynamic Packet Routing with Per-Packet Delay Guarantees of O(distance+1/session rate)”Proceedings of the 38thAnnual Symposium on Foundations of Computer Science,pp. 294-302 (1997).
Andrews, M. et al., “Minimizing End-to-End Delay in High-Speed Networks with a Simple Coordinated Schedule”Proceedings of IEEE INFOCOM '99,pp. 380-388 (1999).
Andrews, M. et al., “Packet Routing with Arbitrary WEnd-to-End Delay Requirements”Proceedings of the 31stAnnual ACM Symposium on Theory of Computing,pp. 557-565 (1999).
Chiussi, F. et al., “Achieving High Utilization in Guaranteed Services Networks Using Early-Deadline-First Scheduling,”Proceedings of the 6thIEEE/IFIP International Workshop on Quality of Servicepp. 209-217 (1998).
Elwalid, A. et al., “Design of Generalized Processor sharing Schedulers Which Statistic

Affiliated with

Also associated with

Rating

Method of admission control for packetized communication... 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 of admission control for packetized communication..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of admission control for packetized communication... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3297787