http:^^www-net.cs.umass.edu^modeling.html

This data set contains WWW-pages collected from computer science departments of various universities

Date: Tue, 14 Jan 1997 21:49:40 GMT
Server: NCSA/1.5.1
Last-modified: Sun, 06 Oct 1996 18:13:54 GMT
Content-type: text/html
Content-length: 17449


<title>
Design and Analysis of ATM Networks 
</title>

<h1> Design and Analysis of ATM Networks </h1>

<h3> Computer Networks Research Group<br>
in the Department of Computer Science <br>
at the University of Massachusetts 
</h3>

<p>
Unlike traditional data networks, future broadband-ISDN (BISDN)
wide-area networks will be required to carry a broad range of traffic
classes ranging from bursty, variable-rate sources, such as voice and
variable-rate coded video, to smooth, constant bit rate sources.
Moreover, these networks will have to do so while providing a
guaranteed performance or quality-of-service (QOS) to these traffic
classes.  The problem of characterizing performance in such networks
is thus particularly important since this must be done not only for
the traditional off-line tasks of dimensioning and design (e.g.,
determining link bandwidths, buffer capacities and processing
capacities at network switchpoints) but also for on-line, <i>
performance-driven </i> traffic control purposes such as session-level
admission control.  In this section, we outline our research aimed
at providing the analytical tools and techniques for analyzing such
networks and their diverse workloads and for designing and
characterizing the properties of scheduling policies in these
networks. 

<p>
Traditional approaches towards performance evaluation of
communication networks
are generally not
applicable in a high-speed network environment for a number of
reasons.  First, the traffic in future high-speed networks is
projected to be ``bursty,'' often processing complex correlations in
the cell arrival processes.  Simple Markovian assumptions (such as
memoryless inter-arrival times) are thus likely to be invalid in such
networks.  The gigabit rates of future high-speed networks also render
simulation ineffective for systems of any realistic size.  The very
performance metric(s) of interest in a high-speed network will also be
different -- average delay will no longer be the primary performance
measure, and, instead, <i> secondary performance measures </i> such as
probability of buffer overflow, maximum packet delay, and the tail of
delay distributions must be considered.  In this respect, there is
evidence that even relatively sophisticated performance models which
work well for predicting average delay in the presence of correlated
arrivals may be less well-suited for computing these new performance
measures of interest [Naga91].
We also note that many previous performance
evaluation techniques have been confined to studying the performance
of the <i> aggregate traffic </i> generated by a set of <i> identical </i>
sources at a <i> single </i> multiplexer in isolation; in
connection-oriented high-speed networks with QOS guarantees, it is
clear that performance must be examined on a <i> per-session </i> basis
and in a <i> network </i> setting [Kuro92,Schu92].
Finally, we note that given the
potentially complex nature of network traffic, it is becoming
increasingly valuable to be able to broadly characterize properties
(such as optimality, or near optimality) of network control mechanisms
which hold over a wide range of traffic models and assumptions.  Thus
far, however, little work has been reported on this problem for
traditional networks, much less for high-speed networks.

<p>
Given the above considerations, it is evident that new performance
evaluation techniques will be required for the design and analysis
future high-speed networks.  Furthermore, given the QOS requirements
of such emerging standards as ATM, these techniques will also be
needed for <i> on-line </i> performance driven, traffic control purposes
such as session-level admission control.  Our research in
these areas is aimed at addressing this need.  Our research divides
broadly into four areas:

<ul>
<li>
We are developing a methodology for obtaining tight pessimistic
bounds on the per-session performance of a collection of heterogeneous
sessions within a high-speed network [Kuro92].
The metrics of interest are
<i> the distribution of the packet delay and the probability of
buffer overflow.</i>  Our research is unique in that we are
interested in computing provable performance <i> bounds </i>, and in doing so
on a <i> per-session </i> basis in a very general <i> network </i> setting
in which sessions may traverse a number of hops.  This methodology
is useful, not only for the purpose of analyzing session- and
network-level performance, but also as a mechanism to be used for call
admission where performance (QOS) guarantees are to be provided.
<li>
We conjecture that the bounds computed using the above methodology may
sometimes be too loose to be of practical interest.  In these cases,
it will be of interest to compute performance, albeit in an
approximate manner, once again -- in a <i> network </i> setting. 
We have thus also examined a number of
approximate approaches towards evaluating the performance of
heterogeneous sessions within a high-speed network
[Schu91,Naga91,Schu92].  The primary
performance metric of interest is probability of buffer
overflow.  Our research here is noteworthy in considering
heterogeneous sources and in doing so in a network setting.
<li>
We have developed a methodology for designing and analyzing the
qualitative behavior of scheduling policies.
This is based
on 
sample path analysis and the theory of majorization 
[Tows90].  Our
focus is on a wide class of performance metrics, including the
average and maximum packet delay, the probability of buffer overflow,
and the length of a buffer overflow burst.  As discussed above, this
work is of particular interest and value in that it can characterize
properties of scheduling mechanisms (such as their optimality, or near 
optimality) over a wide range of assumptions, thus obviating the need
for a potentially time-consuming and/or difficult case-by-case
performance analysis. 
<li> We are also developing <i> routing policies</i> for 
   high-speed networks [Hwan91,Hwan92].  Given the need to
   provide QOS guarantees to admitted sessions (and thus implicitly
   ``reserve'' resources for on-going calls), the routing problem in
   high-speed networks shares much more in common with circuit-switched
   routing algorithms than with 
   routing in traditional data communication networks.
   Our research in [Hwan92,Hwan92a] is aimed at
   exploiting the similarities with routing in traditional circuit-switched 
   networks and adapting these policies for the case
   of high-speed ATM networks.  Of particular interest is the
   fact that ATM routing will be more processing intensive [Hwan92],
   and will be required to route traffic with heterogeneous
   bandwidth requirements [Hwan92a].
</ul>

<p>
<b> BIBLIOGRAPHY </b>

<p> <b> [Bacc92] </b> 
  F. Baccelli, Z. Liu, D. Towsley, ``Optimal Scheduling of Parallel
  Processing Systems With and Without Real-Time Constraints'', to
  appear in <i> Journal of the ACM. </i>
<p> <b> [Chip89] </b>  R. Chipalkatti, J.F. Kurose, and D. Towsley,
  ``Scheduling Policies for Real-Time and Non-Real-Time Traffic
   in a Statistical Multiplexer,''
   <i> Proc. IEEE Infocom'89, </i> (Ottawa Canada), pp. 774-783.
<p> <b> [Goli90] </b> P. Goli, J. Kurose, and D. Towsley,
  ``Approximate Minimum Laxity Scheduling Algorithms for Real-Time
  Systems,'' Technical Report 90-88, Department of Computer and
  Information Science, University of Massachusetts, Amherst, MA.
<p> <b> [Hong89] </b> J. Hong, X. Tan, and D. Towsley, ``A Performance Analysis of
   Minimum Laxity and Earliest Deadline Scheduling in a Real-Time System,''
  <i> IEEE Transactions on Computers</i>, Vol. 38, No.~12, (December 1989),
  1736--1744.
<p> <b> [Hwan91] </b>
   R.H. Hwang and J.F. Kurose, ``On Virtual Circuit Routing and Re-Routing
        in Packet-Switched Networks,''
   <i> 1991 IEEE Int. Conf. on Communications,</i> pp. 318-323.
<p> <b> [Hwan92] </b> R. Hwang, J.F. Kurose, D. Towsley,
    ``The Effect of Processing Delay and QOS Requirements in High Speed
     Networks,''
     <i> 1992 IEEE Infocom Conference, </i> (Florence, Italy, May 1992),
     pp. 160-169.
<p> <b> [Hwan92a] </b> R. Hwang, J.F. Kurose, D. Towsley,
   ``State Dependent Routing for Multi-Rate Loss Networks,''
    to appear in <i> Proc. 1992 IEEE Globecom Conference,</i>
    (Dec. 1992, Orlando, Fla.).
<p> <b> [Kuro90] </b> J. Kurose, ``An Exact Analysis of Customer Loss Under
   Minimum Laxity Scheduling in Discrete Time Queueing Systems,''
   to appear in <i> Performance Evaluation.</i>
<p> <b> [kuro91] </b> J.F. Kurose, D. Towsley, C,.M. Krishna, `Design and
  Analysis of Processor Scheduling Policies for  Real-Time  Systems''
  <i> Foundations of Real-Time Computing: Scheduling
  and Resource Management,</i> Ed. A. VanTilborg, Kluwer Publishers, 1991.
<p> <b> [Kuro92] </b> J. Kurose, ``On Computing Per-Session Performance Bounds in
     High-Speed  Multi-hop Computer Networks,''
     1992 <i> ACM SigMetrics Conference,</i> (Newport Beach, RI, June 1992),
     pp. 128-139.

<p> 
<!WA0><a href="ftp://gaia.cs.umass.edu/pub/Lopr95:TR95-109.ps.Z">
<b>[Lopr95:TR95-109]</b></a>,