Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
1999-05-14
2003-03-11
Vanderpuye, Ken (Department: 2661)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
C370S235100
Reexamination Certificate
active
06532213
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a system for scheduling packets in packet networks and, more particularly, to guaranteeing data transfer delays from data sources to destinations.
BACKGROUND
FIG. 1
shows a packet network in which a plurality of switches
2
are connected to each other by communication links
8
. A number of data sources
4
and destinations
6
are connected to the communication switches
2
. From time to time, a network connection is established or torn down from each of these data sources
4
to a corresponding destination. The connection establishment process involves one of the data sources
4
sending a packet including control information that indicates one of the destinations
6
to which it desires the connection and the desired envelope of the data traffic it agrees to send on the connection, along with the desired delay bounds at each of the communication switches
2
on the path to the destination. The above desired connection and envelope are specified in terms of leaky-bucket parameters as disclosed in R. Cruz, “A Calculus for Network Delay, Part II: Network Analysis,”
IEEE Transactions on Information Theory
, pp. 121-141, January 1991. For the tear-down of a connection, the data source sends a packet including control information indicating that the connection needs to be torn down.
When one of the switches
2
in the network receives a data packet indicating that a connection needs to be established, the switch executes a call admission control (CAC) procedure to determine whether or not the delay required by the connection can be guaranteed by the network, If the result of such a procedure in every switch on the path of the connection in the network indicates that the delay can be guaranteed by the network, then the connection is accepted in the network. On the other hand, if the result of such a procedure in at least one of the switches
2
on the path of the connection in the network indicates that the delay cannot be guaranteed by the network, then the connection is not accepted in the network.
The provision of quality-of-service (QoS) guarantees, such as bandwidth, delay, jitter, and cell loss, to applications of widely different characteristics is a primary objective in emerging broadband packet-switched networks. In such networks, packet-scheduling disciplines are necessary to satisfy the QoS requirements of delay-sensitive applications, and they ensure that real-time traffic and best-effort traffic can coexist on the same network infrastructure. Among the scheduling algorithms that have been proposed in literature, two classes of schemes have become popular: those based on generalized processor sharing (GPS) and those based on earliest deadline first (EDF). For a survey of these algorithms, see S. Keshav,
An Engineering Approach to Computer Networking. ATM Networks, the Internet, and the Telephone Network
, Addison-Wesley, Ithaca, N.Y., 1996; H. Zhang, “Service Disciplines for Guaranteed Performance Service in Packet-Switching Networks,”
Proceedings of the IEEE
, pp. 1374-1396, October 1995.
EDF scheduling has been known for many years in the context of processor scheduling as disclosed in C. L. Liu and J. W. Wayland, “Scheduling algorithms for multiprogramming in a hard real time environment,”
Journal of ACM
, pp. 46-61, January 1973. Furthermore, it has been more recently proposed as a possible packet-scheduling discipline for broadband networks as disclosed in D. Ferrari and D. Verma, “A Scheme for Real-Time Channel Establishment in Wide-Area Networks,”
IEEE Jour. Sel. Areas Commun
., pp. 368-379, April 1990; D. Verma, H. Zhang, D. Ferrari, “Guaranteeing Delay Jitter Bounds in Packet Switching Networks,”
Proc. TRICOMM
, pp. 35-46, Chapel Hill, N.C., October 1991. The EDF scheduling discipline generally works as follows: each connection i at a switch k is associated with a local delay deadline d
i
k
; then an incoming packet of connection i arriving to the scheduler at time t is stamped with a deadline t+d
i
k
, and packets in the scheduler are served by increasing order of their deadline.
For a single switch, EDF is known to be the optimal scheduling policy as disclosed in L. Georgiadis, R. Guerin, and A. Parekh, “Optimal Multiplexing on a Single Link: Delay and Buffer Requirements,” RC 19711 (97393),
IBM T. J
., Watson Research Center, August 1994; J. Liebeherr, D. Wrege, and D. Ferrari, “Exact Admission Control for Networks with a Bounded Delay Service,”
IEEE/ACM Trans. Networking
, pp. 885-901, December 1996. Optimality is defined in terms of the schedulable region associated with the scheduling policy. Given N connections with traffic envelopes {overscore (A)}
i
(t) (i=1, 2, . . . , N) sharing an output link, and given a vector of delay bounds {right arrow over (D)}=(d
1
, d
2
, . . . , d
N
), where d
i
is an upper bound on the scheduling delay that packets of connection i can tolerate, the schedulable region of a scheduling discipline &pgr; is defined as the set of all vectors {right arrow over (D)} that are schedulable under &pgr;. EDF has the largest schedulable region of all scheduling disciplines, and its non-preemptive version (NPEDF) has the largest schedulable region of all the non-preemptive policies. The schedulable region of the NPEDF policy consists of those vectors that satisfy the following constraints:
L
r
≤
d
1
(
1
)
L
+
∑
i
=
1
N
A
_
i
(
t
-
d
i
)
≤
rt
,
L
r
≤
t
≤
d
N
(
2
)
∑
i
=
1
N
A
_
i
(
t
-
d
i
)
≤
rt
,
t
≥
d
N
(
3
)
where d
i
≦d
2
≦ . . . ≦d
N
, L is the packet size (if the packet size is variable, then L is the maximum packet size), r is the link rate, and {overscore (A)}
i
(t)=0 for t<0. Within a single node, once the traffic envelopes are known, a 100% link utilization can be achieved (at least in principle) with this characterization.
The difficulties arise in a multi-switch or multi-node network where the traffic envelopes are no longer determined at the inputs of the nodes inside the network, and the interactions that distort the traffic are not easily characterizable. This problem is not peculiar of EDF, but is common to any scheduling discipline. As a general framework to handle the multi-node problem, H. Zhang and D. Ferrari, “Rate-Controlled Service Disciplines,”
Jour. High Speed Networks
, pp. 389-412, 1994, propose a class of schemes called rate-controlled service (RCS) disciplines which reshape the traffic at each hop within the network. As schematically shown in
FIG. 2
, an RCS server
10
has two components: a shaper
12
which reshapes the traffic of each connection and a scheduler
14
which receives packets released by the shaper and schedules them according to a specific scheduling discipline, such as EDF as disclosed in L. Georgiadis, R. Guerin, V. Peris, and K. Sivarajan, “Efficient Network QoS Provisioning Based on per Node Traffic Shaping,”
IEEE/ACM Trans. Networking
, pp. 482-501, August 1996 (“Georgiadis et al.”), who build upon this model and derive expressions for the end-to-end delay bounds in terms of the shaper envelope and scheduling delay at each node. They also show the following useful properties of RCS.
Identical shapers at each switch along the path of a connection i (i.e., shapers having identical shaper envelopes for connection i) produce end-to-end delays that are no worse than those produced by different shapers at each switch. Therefore, for any given connection, identical shapers can be used at each node. This shaper envelope common to all shapers for connection i is denoted as {overscore (E)}
i
(t).
The end-to-end delay bound for connection i is given by:
D
_
i
=
D
(
A
_
i
&LeftBracketingBar;
&RightBracketingBar;
E
_
i
)
+
∑
k
=
1
k
i
d
i
k
(
4
)
where {overscore (D)}
i
=D({overscore (A)}
i
∥{overscore (E)}
i
) denotes the maximum shaper delay, and d
i
k
is the bound on the scheduler delay for packets of connection i at th
Chiussi Fabio M.
Sivaraman Vijay
Agere Systems Inc.
Hughes Ian M.
Mendelsohn Steve
Vanderpuye Ken
LandOfFree
Guaranteeing data transfer delays in data packet 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 Guaranteeing data transfer delays in data packet networks..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Guaranteeing data transfer delays in data packet networks... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3015557