Using Traffic Regulation to Meet End-to-End Deadlines in ATM Networks.
AbstractThis paper considers the support of hard real-time connections in ATM networks. In an ATM network, a set of hard real-time connections can be admitted only if the worst case end-to-end delays of cells belonging to individual connections are less than their deadlines. There are several approaches to managing the network resources in order to meet the delay requirements of connections. This paper focuses on the use of traffic regulation to achieve this objective. Leaky buckets provide simple and user-programmable means of traffic regulation. An efficient optimal algorithm for selecting the burst parameters of leaky buckets to meet connections' deadlines is designed and analyzed. The algorithm is optimal in the sense that it always selects a set of burst parameters whose mean value is minimal and by which the delay requirements of hard real-time connections can be met. The exponential size of the search space makes this problem a challenging one. The algorithm is efficient through systematically pruning the search space. There is an observed dramatic improvement in the system performance in terms of the connection admission probability when traffic is regulated using this algorithm.
Introduction
There is a growing interest in the application of ATM networks for distributed Hard Real-Time
(HRT) systems. In a distributed HRT system, tasks are executed at different nodes and communicate
amongst themselves by exchanging messages. The messages exchanged by time-critical
tasks have to be delivered by certain deadlines for successful operation of the system. Examples of
such systems include supervisory command and control systems used in manufacturing, chemical
processing, nuclear plants, tele-medicine, warships, etc. This paper addresses the issue of guaranteeing
end-to-end deadlines of time-critical messages in ATM networks that support distributed
HRT systems.
Since ATM is a connection-oriented technology in which messages are packetized into fixed-size
cells, guaranteeing message deadlines is tantamount to ensuring that the worst case end-to-
end delay of a cell does not exceed its deadline. To provide such guarantees, three orthogonal
approaches can be taken:
1. Route selection for connections;
2. Output link scheduling at ATM switches;
3. Traffic regulation at the User Network Interface (UNI).
The first approach is to select appropriate routes for connections such that the delays are
within bounds. Since typical ATM networks for HRT applications are LANs, the scope of this
approach is limited. The second approach focuses on scheduling at the ATM switches' output
links where traffic from different connections is multiplexed. Drawing on the similarities with
CPU scheduling, classical real-time scheduling policies such as the First Come First Serve (FCFS),
Earliest Deadline First (EDF), Generalized Processor Sharing (GPS), Fair Queuing (FQ), etc., are
employed [2, 12, 13, 16, 23, 24, 25]. However, most commercially available switches use a high
priority queue for HRT connections, and this queue is served in a FCFS manner.
In this paper, we focus on the third approach. That is to control the network delays by regulating
the input traffic of each connection. Regulating the input traffic can smooth the burstiness
of the traffic, which tends to reduce the adverse impact of burstiness on the end-to-end delays of
other connections. Most of the existing ATM networks provide for traffic regulation at the UNI.
It is relatively easy to tune the regulation parameters as desired. This justifies our focus on using
the traffic regulator as an access control mechanism for HRT ATM networks. It must be noted
that all the three approaches are important and they complement each other. Our results of using
traffic regulation complement the previous work on route selection and output link scheduling.
The idea behind traffic regulation is to regulate a connection's traffic so that it has a lower
impact on the delays of cells of other connections. When two or more connections are multiplexed
on a single link, an increase in burstiness of one connection's traffic adversely impacts the delays of
the cells of others. Regulating a connection's traffic makes the traffic less bursty, thereby reducing
the delays of other connections' cells. However, regulating a connection's traffic may delay some
of its own cells. Therefore, it is important to choose an appropriate degree of traffic regulation so
that all connections can meet their end-to-end deadlines.
In this paper, we study the impact of input traffic regulation on the worst case end-to-end
delays experienced by cells of a set of hard real-time connections. In particular, we consider the
bucket regulator. The degree of regulation of a connection depends on the leaky bucket
parameters assigned to it. The degree of traffic regulation chosen for a connection affects not only
the delays of that connection, but also those of others sharing resources with that connection.
Thus, the leaky bucket parameters for the entire set of connections must be carefully assigned to
ensure that every connection meets its end-to-end deadline. Berger proposed an analysis model of
bucket regulators in [1]. In his work, Berger examined a single leaky bucket, analysing the job
blocking probabilities (or system throughput) versus the parameters such as job arrival patterns,
capacity of token bank and size of job buffer. Different from Berger's work in [1], we consider the
interactions of a set of leaky bucket regulators, searching for a vector of burst parameters of the
bucket regulators to meet the end-to-end deadlines of all HRT connections.
Our algorithm of searching burst parameters of leaky bucket is optimal in terms that it can
find the vector of burst parameters whose mean value is minimal and by which the delay requirements
of all HRT connections can be met, whenever such an assignment exists. Our algorithm is
computationally efficient and can be utilized during connection setup. The results presented in
this paper are directly applicable to currently available ATM networks without making any modifications
to the hardware and are compatible with the proposed ATM standards. We evaluate the
system's capability to support hard real-time connections in terms of a metric called admission
probability [18]. Admission probability is the probability of meeting the end-to-end deadlines of a
set of randomly chosen connections. We have observed that the admission probability increases
with a proper choice of leaky bucket parameters at the UNI.
While we focus on traffic regulation for meeting end-to-end deadlines, our work also complements
much of the previous studies which essentially concentrate on designing and analyzing
scheduling policies for ATM switches [2, 5, 6, 8, 10, 11, 12, 13, 16, 20, 21, 23, 24, 25]. A modified
FCFS scheduling scheme called was proposed and studied in [2]. The switch scheduling
policy called "Stop and Go" is presented in [8]. A virtual clock scheduling scheme in which cells
are prioritized by a virtual time stamp assigned to them, is discussed in [25]. The use of the Earliest
Deadline First scheduling in wide area networks has also been investigated [6]. [23] discusses
scheduling at the output link by introducing a regulator at each link of an ATM switch. [12]
uses the rate-monotonic scheduling policy in which the input to the scheduler is constrained by
regulating the traffic of each connection traversing the scheduler. Scheduling policies based on fair
queueing and its derivations are discussed in [5, 16]. In our analysis of network delays, we assume
the output link scheduling policy used is FCFS. However, our analysis and methodology can be
easily applied to systems using other scheduling policies.
The outline of the rest of the paper is as follows. Section 2 defines the system model. Section
3 develops a formal definition of the traffic regulation problem for HRT ATM networks. Section
presents our algorithm to select the leaky bucket parameter values. Performance results are
presented in Section 5. We conclude in Section 6 with a summary of results.
Host 4
Host 1 Host 2
Host 3
Switch A Switch B
Switch D Switch C
Network
Interface
Card
Network
Interface
Card
Network
Interface
Card
Network
Interface
Card
From other
hosts or
switches
From other
hosts or
switches
From other
hosts or
switches
From other
hosts or
switches
To other
hosts or
switches
To other
hosts or
switches
To other
hosts or
switches
To other
hosts or
switches

Figure

1: ATM network architecture
2 System model
In this section, we present the network model, the connection model and the traffic descriptors
used to specify the worst case traffic pattern of HRT connections.
2.1 Network model

Figure

1 shows a typical ATM LAN. In ATM networks [4, 9, 22], messages are packetized into
fixed-size cells. The time to transmit a single cell is a constant denoted by CT . We assume that
time is normalized in terms of CT . That is, in this paper time is considered a discrete quantity
with the cell transmission time (CT ) being taken as one time unit.
ATM is a connection-oriented transport technology. Before two hosts begin communication, a
connection has to be set up between them. Figure 2(a) shows a sequence of network components
that constitute a typical connection (illustrated by a connection from Host 1 to Host 2 in Figure 1).
Cells of a connection pass through a traffic regulator at the entrance to the network (the User
Network Interface or UNI) and then traverse one or more ATM switches interconnected by physical
links before reaching their destination host.
Cell Processing
Network
Interface
Card
Input
Switch Fabric
Switch A
Input
Switch Fabric
Switch B
Cell Processing
Network
Interface
Card
Output
Output
From Host 1
To Host 2
Constant Delay Server
From Host 1
To Host 2
VariableDelay Server
Constant Delay Server
VariableDelay Server
Constant Delay Server
Constant Delay Server
Constant Delay Server
VariableDelay Server
Constant Delay Server
Constant Delay Server
Constant Delay Server
Constant Delay Server
(a) The devices and links traversed by
the connection
(b) The sequence of servers traversed by
the connection

Figure

2: Connection decomposition into servers
In most ATM networks, the traffic is regulated at the source using leaky buckets. A leaky bucket
regulator consists of a token bucket and an input buffer. The cells from the source associated
with the leaky bucket are buffered at the leaky bucket. A pending cell from the input buffer is
transmitted if at least one token is available in the token bucket. Associated with each leaky
bucket regulator are two parameters: the burst parameter and the rate parameter. The burst
parameter, denoted by fi, is the size of the token bucket, i.e., the maximum number of tokens that
can be stored in the bucket. The rate parameter, denoted by ae, is the token generation rate in the
bucket. The number of cells that may be transmitted by a leaky bucket regulator in any interval
of length I is bounded by fi
An ATM switch multiplexes a number of connections onto a physical link. The cells of connections
being multiplexed are buffered at the controller of the output link. In most commercially
available switches, cells of connections with stringent delay requirements (i.e., Class A traffic) are
buffered in a high-priority queue and served in an FCFS order. Hence, in this paper, we consider
FCFS scheduling policy for HRT connections.
2.2 Connection model
To support HRT applications, the network must guarantee that all cells from a given set of
connections are transmitted before their deadlines. We will use the following notations concerning
a set of HRT connections. Hereafter, we will omit the qualifier "HRT" for connections since we
only deal with HRT connections.
ffl N denotes the total number of connections in the system.
ffl M is the set of N connections competing for resources within the ATM network:
connection M i is specified by the following information:
- Source address,
Destination address,
Connection route, 1
An upper bound on average cell arrival rate,
Worst case input traffic characteristics.
D is a vector that specifies the end-to-end deadlines of connections in M:
~
where D i is the end-to-end deadline of a cell of connection M i . That is, if a cell arrives at
the source at time t then it should reach at the destination by t +D i .
In a connection (see Figure 2(a)), each of the network components traversed by a connection's
cells can be modeled as a server. Thus, a connection can be considered to be a stream of cells being
served by a sequence of servers [3, 18]. Servers can be classified as constant delay servers and
variable delay servers. A constant delay server is one that offers a fixed delay to every arriving
cell. For example, physical links are considered as constant delay servers. On the other hand, cells
may be buffered in a variable delay server and hence suffer queueing delays. The leaky bucket
traffic regulator and the FCFS output link schedulers at ATM switches are examples of variable
delay servers. Figure 2(b) shows the logical representation of the connection in Figure 2(a).
The traffic pattern of a connection at a point in the network is characterized by a traffic
descriptor . The traffic at the source of a connection is the raw traffic (unregulated) generated by
applications. It is described by the periodic descriptor (C; P ), which means that a maximum of
C cells may arrive at the connection in any interval of length P . The periodic descriptor is very
general to describe real-time traffics at the application level. The classical periodic or synchronous
To ensure system stability, we assume that connection routes do not form loops [3, 16].
traffic (i.e., C contiguous cells arriving at the beginning of every period of length P ) is a special
case of this kind of traffic. Most hard real-time traffic (at source) is assumed to be synchronous
[14, 15], and hence is adequately specified by this traffic descriptor.
The raw traffic of a connection is regulated by the leaky bucket regulator before it gets into
the network. After being regulated by a leaky bucket with parameters (fi, ae), the traffic pattern
becomes any interval of length I. After the regulation, the traffic traverses through
ATM switches. The traffic pattern will becomes more and more irregular as cells are multiplexed
and buffered at the switches. For the description of more general traffic patterns, we use rate
function descriptor [17, 18], \Gamma(I ), to describe the traffic after leaky bucket regulation. \Gamma(I )
specifies the maximum arrival rate of cells in any interval of length I. That is, a maximum of
I \Delta \Gamma(I ) cells of the connection may arrive in any interval of length I. \Gamma(I ) is general to describe
any traffic pattern. For example, the traffic pattern described by fi can be expressed by
the rate function in (61) in appendix A.1.
In the rest of the paper, the following notations are used to describe traffics at different network
points:
(C in server
traffic to the leaky bucket of connection M i .
(\Gamma in server
i;j (I)) and (\Gamma out server
output traffic at FCFS server j of connection M i .
2.3 Delay computations
The set of connections M is admissible in an ATM network if and only if the worst case delays
of cells do not exceed their deadlines. Let ~ d be a vector whose components are the worst case
end-to-end delays for connections in M; that is,
where d i is the worst case end-to-end delay experienced by a cell of connection M i .
the relation "" on vectors as follows. Let
only if
With this relation, M, the set of HRT connections, is admissible if and only if
~ d  ~
Hence, to check whether M is admissible, we need a systematic method of computing the
worst case end-to-end delay experienced by a cell of each connection.
Consider connection M i , M i 2 M. To compute d i , we need to investigate the delays in every
network component traversed by a cell of M i . Now, we can decompose d i into three parts as
follows:
Switch B
Switch A
Bucket
Bucket

Figure

3: Experimental setup
1. d const
i denotes the summation of the delays a cell suffers at all the constant delay servers in
its connection route.
2. d lb
i denotes the worst case queueing delay experienced by a cell at the leaky bucket which
regulates M i 's traffic. When M i 's traffic is not regulated, d lb
i is 0.
3. d net
i denotes the summation of the worst case delays a cell suffers at all the variable delay
servers after the leaky bucket. d net
i can be obtained by decomposing it further as follows.
Suppose the route of connection M i traverses switches (FCFS servers)
be the cell delay of connection M i at FCFS server j. d net
can thus be expressed as:
d net
d i , the worst case end-to-end delay for M i , can now be obtained as
const
const
Since d const
i is a constant, we focus on obtaining upper bounds on d lb
i and d fcfs
i;j .
3 Problem definition
In this section, we formally define the problem of leaky bucket parameter selection for HRT ATM
networks. To motivate the discussion, we first examine some experimental data. We consider a
simple network consisting of two ATM switches (see Figure 3). Each ATM switch has 2 input
lines and 2 output lines. There are 3 connections in the system, M
connections share the same output link at the second switch (switch B). Connections M 1 and M 2
enter the network at switch A and traverse through switches A and B, while connection M 3 enters
the system at switch B and traverses switch B only. The three connections carry identical streams
of video data. The video source under study is a two hour encoding of the movie "Starwars" [7].
The video source provides a total of 171,000 frames, at the rate of 24 frames per second.
bEnd-to-End
delay
(cell
units)

Figure

4: Experimental results
In this experiment we vary fi 1 (the leaky bucket burst parameter of M 1 ) while keeping fi 2 and
burst parameters of M 2 and M 3 , respectively) constant. Figure 4 shows that
as increases, the delay (measured in CT units) experienced by M 1 tends to decrease. However,
when fi 1 is increased, the delay experienced by M 3 tends to increase. Further, we observe that for
the delays experienced by M 1 and M 3 reach constant values. An intuitive explanation
of these results is provided below.
An increase in fi 1
tends to increase the burst size of M 1 's traffic into the network. When a
larger burst size is allowed at the output of M i 's leaky bucket, the need to buffer M i 's cells within
the leaky bucket decreases. This tends to lower connection M 1 's delay as fi 1
is increased. On the
other hand, the increased burstiness of M 1 as fi 1
is increased adversely impacts connection M 3 's
traffic, increasing M 3 's worst case cell delay. However, for large values of fi 1
? 1400), the
delays of either connection are unaffected by any increase in fi 1
. This is because, at such large
values of fi 1 , the burst size allowed for M 1 is so high that no cells of M 1 are queued at the leaky
bucket input buffer, i.e., there is virtually no traffic regulation on M 1 's traffic. In this experiment,
traffic was not monitored, because it is expected to exhibit the same trend as M 3 when fi 1
increases.
Clearly, the experimental results shown in Figure 4 indicate that the choice of fi i s for different
connections plays a critical role in the worst case cell delays experienced by all the connections.
Before the formal definition of the problem, we need some notations:
ffl ~ae is the rate vector , i.e.,
ae i is the rate parameter assigned to the leaky bucket regulating connection M i at its
network interface. We assume that ae i is assigned a value equal to the long term average cell
arrival rate of M i .
ffl ~ fi is the burst vector , i.e.,
where fi i is the burst parameter assigned to the leaky bucket regulating M i 's traffic.
ffl m( ~ fi) is the norm of the burst vector ~ fi, i.e.,
Since we analyze a slotted system, fi i takes positive integers only. Therefore, the minimal
value of m( ~ fi) is N .
ffl ~ d ( ~ fi) is the worst case end-to-end delay vector for a given selection of ~ fi, i.e.,
~ d ( ~
where d i ( ~ fi) is the worst case cell delay of connection M i when ~ fi is the chosen burst vector.
Using (7), d i ( ~ fi) can be expressed as
const
const
where d lb
are the worst case queueing delays at the leaky bucket and at
th FCFS server, respectively, when the burst vector is ~ fi. The computation of d lb
d fcfs
are given by (60) and (63) respectively in Appendix A.
ffl AM is the set of burst vectors for which the connection set M is admissible, i.e.,
Our main goal is to meet (5), i.e., to ensure that the end-to-end deadlines of all the connections
in a given set are met. We have chosen traffic regulation as our means of achieving this objective.
In terms of the above notations, given a set of HRT connections, M, the method must find vector
~ fi that belongs to AM . We are going to design and analyze a ~ fi-selection algorithm for this
purpose. Such an algorithm will take connection set M as its input and return vector ~ fi as its
output.
Clearly, when AM is empty, no assignment of ~ fi can make the connection set admissible. Our
parameter selection algorithm will return an all-zero ~ fi when AM is empty. Furthermore, since the
degree of regulating the traffic stream from M i is higher for smaller values of fi i (i.e. the regulated
traffic is less bursty and thus has less impact to others), it is desirable to select a vector ~ fi having
a small norm, m( ~ fi). Let ~ fi

be the minimum in AM in terms of its norm. That is, ~ fi

satisfies:

~ fi2AM
We define a ~ fi-selection algorithm to be optimal if it always produces the ~ fi

whenever AM is
nonempty.
We now prove that ~ fi

is unique if it exists for a set of connections M. The following Lemma
is introduced to illustrate the relationships between ~ fi and d net
LEMMA 3.1 Consider a connection set M. d net
does not decrease as ~ fi increases.
Lemma 3.1 is valid by intuition. As ~ fi increases, more cells of those connections whose fi values are
increased will get through the leaky buckets and be injected into the network. This will add more
cells to the following FCFS servers, and they will compete network resources with the cells of M i .
Therefore, d net
fi), the total delays of an M i 's cell at all the FCFS servers, will increase, or remain
the same if the servers still have the capacity to transmit the increased amount of cells without
buffering them. So d net
never decrease as ~ fi increases. The formal proof of Lemma 3.1 is
given in [17].
The next theorem proves the uniqueness of ~ fi

THEOREM 3.1 For a given system, ~ fi

, which satisfies

~ fi2AM
is unique if AM 6= ;.
Proof: We prove the theorem by contradiction. Assume that AM 6= ; and that there are two
distinct vectors ~ fi=! fi 0
N ? which satisfy (15).
Thus,
~ fi2AM
We can construct a new vector ~ fi =! fi 1
fisuch that for
Using (17) in (10), we have
Since a leaky bucket regulator is at the entrance of each connection, d lb
is independent from
any fi j where j 6= i. Thus we have:
d lb
Then, because of (17) we have, for 1  i  N
d lb
d lb
d lb
Also, because ~ fi  ~ fiand ~ fi  ~ fi, from Lemma 3.1, we have,
d net
Further, because ~ fiand ~ fiare distinct, for a given i, 1  i  N , we have two cases:
Case 1:
That is,
. Hence, from (20) we get
d lb
and from (21), we get
d net
Therefore,
d lb
But, ~ fisatisfies (15). Therefore,
d lb
Case 2:
Hence, from (20) we get
d lb
and from (21), we get
d net
Therefore,
d lb
But, ~ fisatisfies (15). Therefore,
d lb
Because of (25) and (29), ~ fi is also a feasible assignment for which the connection set is
admissible. However, because of (18) and the definition of ~ fi

, ~ fiand ~ ficannot be ~ fi

. This is a
contradiction. Hence, the theorem holds. 2
4 Algorithm development
In this section, we develop an optimal and efficient algorithm. We first formulate the problem as a
search problem and investigate some useful properties of the search space. These properties help
us in the development of the algorithm.
4.1 Parameter selection as a search problem
By definition, an optimal algorithm takes M as its input and returns ~ fi

whenever AM is nonempty
and returns ! 0; output when AM is empty. We can view the problem of selecting

as a search problem, where the search space consists of all the ~ fi vectors.
Let ~
AM be the set of all ~ fi vectors. AM , the set consisting of ~ fi vectors with which the
deadlines of M are met, is a subset of ~
AM . Let \Gamma! be a relation on ~
AM defined as follows. Given
AM , ~ fi \Gamma! ~ fiif and only if 9j; 1  j  N , such that
Note that m( ~ fidiffers from ~ fi only in the jth component. Let 4( ~ fi; ~ fi)
denote the index j. For example, if ~
The relation \Gamma! allows us to define an acyclic directed graph G over ~
AM , with a node set V
and an edge set E given by
fig.
Thus, G is a graph representation of ~
AM , the search space. Graph G can also be considered as a
rooted leveled graph; vector ! is the root and level p consists of all ~ fi vectors having
norm p (p  N ). Figure 5 illustrates such a graph when
In graph G, let L p be the set of all ~ fi vectors at level p. Note that a node at level p can have
edges only to nodes at level p + 1. Based on this representation of the search space, a simple
breadth-first search method can be constructed to find ~ fi

.

Figure

6 shows the pseudo-code for
such a method. As shown by the dotted search path in Figure 5, this search method first examines
all ~ fi vectors in L p before proceeding to those in L p+1 . For each ~ fi vector considered, the method
uses the procedure 2 Compute ~ d ( ~ fi) to evaluate ~ d ( ~ fi). The first ~ fi encountered in the search path
that satisfies the deadline constraint ~ d ( ~ fi)  ~
D is clearly the ~ fi

vector.
At this point, the reader may raise the following questions about the method shown in Figure 6:
2 For the procedure to compute the worst case end-to-end delay of connections, please refer Appendix A.3.
2,1,3
4,1,1

Figure

5: Example search space graph.
Select Burst Parameters(M)
01. for to 1 do fMain iterative loopg
02. foreach ~ fi 2 L p do
03. ~
04. if ( ~ d  ~
05. return( ~ fi);
06. endif
07. endforeach
08. endfor fEnd of main loopg.

Figure

Pseudocode of the breadth-first search method
1. For a given connection set M, set AM may be empty. In such a case, ~ fi

is not defined and
the algorithm of searching ~ fi

will not terminate.
2. Even if AM is nonempty, the exhaustive nature of the breadth-first search results in exponential
time complexity.
In the next subsection, we overcome the first difficulty by bounding the search space. In the
subsequent subsection, we further reduce the search complexity by pruning the search space and
adopting a search method that is more efficient than the breadth-first search.
4.2 Bounding the search space
In the experiment described in Section 3, an interesting observation was that when fi 1
was increased
beyond 1400, there was no change in the worst case end-to-end delays of any of the connections.
The following theorem asserts that such behavior is to be expected in any ATM network and leaky
bucket regulators. Let fi max
i be the minimum value of fi i for which d lb
i is zero.
THEOREM 4.1 For a connection M i whose traffic is described by (C in server
regulated by a leaky bucket with parameters (fi
i is bounded by C in server
i;lb .
Proof: Let Q i;lb be the maximal queue length at the leaky bucket of M i . From Lemma A.2 in
appendix A.1, we have
i is defined to be the smallest integer value for which the maximum waiting time of
a cell at the leaky bucket queue becomes zero, i.e., Q i;lb becomes zero, solve for the value of fi i
which makes (31) zero. We have
4.2 For any connection M i , increasing the value of fi i beyond fi max
i has no impact
on the worst case end-to-end cell delay of M i or any other connection.
Proof: For a connection M i , since fi max
i is the minimal value of fi i for which d lb
i is zero, no
cell of M i is queued at its leaky bucket when fi i reaches fi max
. That is, any cell that arrives at
the leaky bucket will get through the leaky bucket without being buffered. There is virtually no
traffic regulation on M i 's traffic in this case. Therefore, increasing the value of fi i beyond fi max
has no impact on the worst case end-to-end cell delay of M i or any other connection. 2
An important consequence of Theorem 4.2 is that ~
AM ; the search space of candidate ~ fi vectors,
can be bounded; we only need to consider ~ fi vectors that satisfy
~ fi  ~ fi
Select Burst Parameters(M)
01. Compute( ~ fi
02. for to m( ~ fi
do fMain iterative loopg
03. foreach ~ fi 2 L p and ~ fi  ~ fi max
do
04. ~
05. if ( ~ d  ~
06. return( ~ fi);
07. endif
08. endforeach
09. endfor fEnd of main loopg
10. return (! 0;

Figure

7: Pseudocode of the bounded breadth-first search algorithm
Note that ~ fi
can be precomputed for a given set M.
Consider the example in Figure 5. If we assume that ~ fi
applying
Theorem 4.2 we get another graph shown in Figure 8. The shaded region in Figure 8 is
automatically eliminated from consideration.
Using Theorem 4.2, we modify the breadth-first search procedure shown in Figure 6 to take
into account the bounded search space. The resulting pseudo-code is shown in Figure 7. However,
since the size of L p increases exponentially, the complexity of the algorithm is still exponential.
In the next subsection we will prune the search space to design an efficient algorithm.
4.3 Search space pruning
The breadth-first search algorithm defined in Figure 7 has an exponential time complexity. Now
we consider an alternative to the exhaustive breadth-first search method.
As an alternative to the breadth-first search path, we desire a search path that begins at the
root node ! and follows the directed edges in graph G to locate ~ fi

(if ~ fi

exists).
Such a search path would allow us to examine only one vector ~ fi at each level.
Consider the example in Figure 9 which depicts a case with 3. The shaded region
has already been eliminated from consideration based on ~ fi
being Assume that

We would like our search to be guided along one of the two paths:
2.
To guide the search along the direct path from the root to ~ fi

in G, we must choose an
appropriate child node at each level. For example, in Figure 9, while at node !
2,1,3
4,1,1

Figure

8: Example of bounded search space
2,1,3
4,1,1

Figure

9: Example graph of search space after pruning.
either choose ! our next candidate node. However, if we are at node
?, we must guide our search to choose ! as the next
candidate node.
In order to select candidate nodes at each level, we need to know whether a particular node is
an ancestor of ~ fi

(if ~ fi

indeed exists). A node ~ fi is said to be an ancestor of node ~ fi(denoted
~ fi *
\Gamma! ~ fi) if ~ fican be reached from ~ fi (by a directed path in G). For example, in Figure 9, the
ancestor nodes of ! To formally
define the ancestor relationship, we proceed as follows.
First, each vector in ~
AM is considered an ancestor of itself. Let ~ fi p
and ~ fi p+k
be two vectors
in ~
AM such that m( ~ fi
p+k
\Gamma! ~ fi
p+k
if
9 ~ fi
AM such that ~ fi
\Gamma! ~ fi
\Gamma! ~ fi
\Gamma! ~ fi
p+k
The next theorem states an important result that will help us construct a directed path from
the root node (i.e., ! to ~ fi

for any given M. We need some notations first.
be the status vector associated with a node ~ fi, where
Vector ~s ( ~ fi) indicates the status of each stream (i.e., whether the deadlines of individual streams
are met or not) when ~ fi is selected as the burst parameter vector.
The following Lemmas are introduced to help the proof of the theorem which defines the direct
search of ~ fi

LEMMA 4.1 Consider a connection set M. d j ( ~ fi) does not decrease as the increase of fi i s for
any i where i 6= j.
Lemma 4.1 is valid. As we have before, d j ( ~ const
const
j is a constant and
d lb
is independant from fi i if j 6= i. Only d net
changes as the increase of fi i s for any i where
we have that d net
does not decrease as the increase of ~ fi. Therefore,
Lemma 4.1 holds. The formal proof of this Lemma can be found in [17].
LEMMA 4.2 Consider a connection set M and assume that ~ fi

exists for M. If ~ fi is an ancestor
of ~ fi

, for any y (1  y  N) which makes s y ( ~
y .
Proof: Since ~ fi is an ancestor of ~ fi

, we have ~

. That is,
Now we prove: for any y (1  y  N ), if s y ( ~
y . Because of (35), we only need
to prove fi y 6= fi
y . We prove it by contradiction.
Assume
y . Since s y ( ~ we have d y ( ~ fi) ? D y . From Lemma 4.1, we have that
d y ( ~ fi) does not decrease no matter how much we increase fi i s if i 6= y. We now increment the
corresponding components of ~ fi to make ~ fi equal to ~ fi

. d y ( ~ fi

holds. This contradicts
to the definition of ~ fi

and the existance assumption of ~ fi

. Therefore fi y 6= fi
y . So fi y ! fi
y . 2
THEOREM 4.3 If ~ fi

exists, then the following are true:
is an ancestor of ~ fi

, and
2. if ~ fi is an ancestor of ~ fi

, then there exists a ~ fisuch that
(a) ~ fi \Gamma! ~ fi,
(b) s
(c) either ~ fiis ~ fi

, or an ancestor of ~ fi

Proof: Statement 1 is true since ! is an ancestor of all ~ fi's.
Let ~ fi, ~ fi 6= ~ fi

; be an ancestor of ~ fi

. Therefore, for all x, 1  x  N we have
Since ~ fi

is unique, there exists y, 1  y  N such that s y ( ~
Then, from Lemma 4.2, we have
Now construct ~ fisuch that for all z, z 6= y fi 0
From the definition of "\Gamma!", we have obviously
Thus a) holds.
From the definition of "4", we have 4( ~ fi; ~ y. Also, because s y ( ~ that is
s
Thus b) holds.
By (36) and (37) for all x, 1  x  N we have
x  fi
Thus

Hence, either ~ fi= ~ fi

, or there exists a directed path in G such that
\Gamma! ~ fi

fiis an ancestor of ~ fi

. Thus c) holds. 2
Now consider the claims made by the above theorem. The first claim in Theorem 4.3 is trivial.
It states that if ~ fi

exists, then there must be at least one path from the root node !
to ~ fi

. The second claim in Theorem 4.3 implies that if ~ fi is an ancestor of ~ fi

(i.e., ~ fi

exists) and
the assignment of ~ fi does not make M admissible (i.e., ~ d ( ~ fi) ? ~
assignment ~ fiderived from ~ fi such that ~ fi \Gamma! ~ fiand s
0, is also an ancestor of ~ fi

The first claim helps us to begin the search from the root node. Once we are at level p
examining a node ~ fi 2 L p , the second claim helps us to choose the child node of ~ fi if ~ d ( ~ fi) ? ~
D .
The theorem states that we can choose a child node ~ fiof ~ fi such that s
0. The theorem
ensures that such a child node must also have a directed path to ~ fi

if ~ fi

exists. Hence, ~ fi

can
be found by our search starting from ! using the status vector ~s to guide the
search along a directed path leading to ~ fi

4.4 The efficient algorithm and its properties
In this subsection, we first present an efficient and optimal algorithm, and then prove its properties.

Figure

shows the pseudo-code of the algorithm. The algorithm is derived from the one
in

Figure

7 by pruning the search space. The algorithm is an iterative procedure, starting from
the root, i.e., ! During each iteration the algorithm selects a node from the next
level. The node is selected (line with the help of status vector ~s (computed by function
Compute
D ) in line 8). This iterative process continues until either ~ fi

is found or for some
The following two theorems assert the correctness property and the complexity of the algorithm
from

Figure

10.
THEOREM 4.4 For a connection set M, the algorithm in Figure 10 is optimal.
Proof of this theorem follows from Theorem 4.3 and the pseudo-code of the algorithm.
THEOREM 4.5 The time complexity of the algorithm in Figure 10 is O(N
Proof: In the algorithm shown in Figure 10, the maximum number of iterations is
N+1. During each iteration the algorithm calls three procedures (lines 4, 8, and 9). The worst case
time complexity of the procedure Compute ~ d ( ~ fi) (line 4) is a function of the network size, i.e., the
3 Note that line 9 in the algorithm can be modified to select the connection whose deadline is missed and for
which has the minimum value. This modification improves the average case time complexity of the
algorithm without changing the worst case one.
Select Burst Parameters(M)
01. Compute( ~ fi
02. ~
03. for to m( ~ fi
do fMain iterative loopg
04. ~
05. if ( ~ d  ~
06. return( ~ fi);
07. else
08. ~s ( ~
Find index j(); fSuch that s
10. if (fi
11. return(! 0;
12. else
13. fIncreasing component j by 1g
fBy Theorem 4.3, the new burst vector is also an ancestor of ~ fi
14. endif
15. endif
16. endfor fEnd of main loopg.

Figure

10: Pseudocode of the efficient algorithm
From
HostFrom
HostFrom
HostFrom
HostFrom
HostFrom
HostFrom
HostFrom
HostTo
HostTo
HostTo
HostFrom
HostSwitch
Switch
connections source desitination
Host 00 Host 100
Host 01 Host 101
Host 10j
Host 99 Host 109

Figure

11: Example network used in simulation
longest path in the network. Hence, for a given network the time complexity of Compute
can be bounded by a constant. The procedure Compute
steps of
comparisons, therefore its time complexity is O(N ). Finally, the worst case time complexity of
the procedure Find index j() (line
Hence, the time complexity of the algorithm of Figure 10 is O(N
5 Performance evaluation
In this section, we present performance results to evaluate the impact of leaky bucket regulation
on HRT systems.
We consider the sample network architecture shown in Figure 11. It consists of two stages,
with a total of 11 ATM switches. Each ATM switch has 10 input lines and 10 output lines. The
connections in the network form a symmetric pattern. There are 100 connections in the system and
each connection goes through two switches. The connections are arranged in such a way that
connections share one output link at each stage. At the first stage, connections M
are multiplexed in Switch 0 and are transmitted over link 0. At the second stage, connections
are multiplexed in Switch 10 and are transmitted over a link to Host 100.
We evaluate the performance of the system in terms of the admission probability, AP (U ), which
is defined as the probability that a set of randomly chosen HRT connections can be admitted, given
the traffic load in terms of the average utilization of the links U .
To obtain the performance data, we developed a program to simulate the above ATM network
and the connections. The program is written in the C programming language and runs in a
Sun/Solaris environment. In each run of the program 200 connection sets are randomly generated.
For each connection, the total number of cells per period is chosen from a geometric distribution
with mean 10. The worst case cell arrival rate (C, P ) of the connections sharing a particular link
at the first stage are chosen as random variables uniformly distributed between 0 and U subject to
their summation being U , the average utilization of the link. Similar results have been obtained
with different settings of parameters.
For each connection set generated, the following systems are simulated:
ffl System A. In this system connection traffic is unregulated, i.e., the burst vector selected for
the connection set is ~ fi max
ffl System B. In this system constant burst vectors are used for all the connections. In particular,
System B1 sets the burst vector to be ! 3; sets the burst vector to
be
ffl System C. In this system the burst vector produced by our optimal algorithm is used.

Figures

13 and 14 show the performance figures corresponding to the cases where D i is set to
be 2P i and 1:5P i respectively. It is common that deadlines are associated with periods [14, 15] in
HRT systems.
From these figures, we can make the following observations:
System C, where our optimal algorithm is used to set the burst vectors, performs the best.
The performance gain is particularly significant when the link utilization becomes high, in
comparison with systems A, B1, and B2. For example, in Figure 13, at
is close to 1 for System C, but 0 for systems A and B2. This justifies our early claim that
the burst vector must be properly set in order to achieve the best system performance with
HRT applications.
ffl In general, the admission probability is sensitive to the average link utilization. As the
utilization increases the admission probability decreases. This is expected because higher
the network utilization, the more difficult it is for the system to admit a set of connections.
We can also find the decreasing speed of the admission probability in systems A, B1 and B2
is much faster than in System C, as the increase of the utilization. It suggests that in the
situations where the link utilization is high, the proper selection of burst vector becomes
more important to the system performance.
ffl Comparing the performance of systems A, B1, B2 and System C, we can clearly see the
difference between no-regulation, regulation with a large ~ fi, regulation with a small ~ fi and
regulation with an optimal ~ fi. System A, which does not have any traffic regulation, performs
the worst among all the systems. System B1 with a small ~ fi performs better than system
B2 which has a larger ~ fi. System C, with the optimal ~ fi, performs the best. It is another
evidence which proves of the correct direction of our work: choosing the minimal ~ fi which
can still meet the end-to-end deadlines. The simulation results further strengthen the need
for a good ~ fi selection algorithm.
ffl The performance of all systems is very stable as the change of D i . The curves in Figure 13
all have similar shapes as those in Figure 14. It demonstrates that the simulation results
are stable. They have not been affected by some system dynamic factors, such as system
loading, other system traffics, and so on.
6 Conclusions
In this paper we addressed the issue of guaranteeing end-to-end deadlines of HRT connections in
an ATM network. Much of the previous work has concentrated on scheduling policies used in ATM
switches. Our approach to this problem is to regulate the input traffic at the network interface. In
particular, we consider leaky bucket traffic regulators. This study is the first one that uses traffic
regulation (in particular with leaky buckets) as a method of guaranteeing the end-to-end deadlines
of HRT connections. Traditionally, a leaky bucket has been used as a policing mechanism when
the source traffic at the input of the network does not conform to its negotiated characteristics.
We have designed and analyzed an efficient and optimal algorithm for selecting the burst
parameters of leaky buckets in order to meet connections' deadlines. Our algorithm is optimal
in the sense that if there exists an assignment of burst parameters for which the deadlines of a
set of HRT connections can be met, then the algorithm will always find such an assignment. Our
algorithm is also efficient. We simulated and compared the performance of ATM networks with
different regulation policies. We observed that there is a dramatic improvement in the system
performance when the burst parameters were selected by our algorithm.
Our solution for guaranteeing end-to-end deadlines in HRT ATM networks is effective and
generic. It is independent of the switch architecture and the scheduling policy used at the ATM
switches. It can be used for admission control in any ATM network that uses leaky bucket traffic
regulators.



--R

Performance analysis of a rate-control throttle where tokens and jobs queue
Supporting real-time applications in an integrated services packet network: Architecture and mechanism
A calculus for network delay.
Asynchronous Transfer Mode: Solution for Broadband ISDN.
Analysis and simulation of a fair queueing algorithm.
A scheme for real-time channel establishment in wide-area networks
Contributions toward real-time services on packet switched networks
A framing strategy for congestion management.

Rate controlled servers for very high-speed networks


Scheduling real-time traffic in atm networks
Scheduling algorithms for multiprogramming in a hard-real-time environment
Hard real-time communication in multiple-access networks
A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks.
Real Time Communication in ATM Networks.
Guaranteeing end-to-end deadlines in ATM networks
Admission control for hard real-time connections in ATM LAN's. In Proceedings of the IEEE Infocom'96
Responsive aperiodic services in high-speed networks
Congestion control for multimedia services.
ATM concepts

Comparison of rate-based service disciplines
Virtual clock: A new traffic control algorithm for packet switching networks.
--TR

--CTR
Khalil Shihab, Modeling and performance evaluation of ATM switches, Proceedings of the 5th WSEAS International Conference on Applied Informatics and Communications, p.377-383, September 15-17, 2005, Malta
L. Lo Bello , A. Gangemi, A slot swapping protocol for time-critical internetworking, Journal of Systems Architecture: the EUROMICRO Journal, v.51 n.9, p.526-541, September 2005
network delay analysis;ATM network;hard real-time communication;traffic regulation