Scheduling Cells in an Input-Queued Switch 
Scheduling Cells in an Input-Queued Switch
Admission Control and Resource Management for ATM Networks
Pricing Issues in Multi-Service Networks
Functional Approximation Theorems for Controlled
Queueing Networks
The BayBridge: a High Speed Bridge/Router between FDDI
and SMDS
Nick McKeown
The past few years has seen increasing interest in ATM as a cell-based local
area network. But to realize the potential advantages of ATM, a high
performance switch is needed to take data arriving on an input link and
quickly deliver it to the appropriate output link. A switch requires three
functions: a switch fabric, scheduling to arbitrate when cells arrive on
different inputs destined for the same output, and (optionally) queueing at
inputs or outputs to hold those cells that lose the arbitration. A large
number of alternative switch designs have been proposed with varying
approaches to these three functions The goal of this paper is to make a
quantitative comparison of scheduling policies for input-queued switches,
considering both hardware complexity and switch performance. We observe
that while it can be tempting to throw hardware at improving switch
performance, that strategy may be counter-productive in practice, since
simpler solutions can be easier to implement at high speed.
The longstanding view has been that input-queued switches are impractical
because of poor performance. If FIFO queues are used to queue cells at each
input, only the first cell in each queue is eligible to be forwarded. As a
result, FIFO input queues suffer from head of line (HOL) blocking --
if the cell at the front of the queue is blocked, other cells in the queue
cannot be forwarded to other unused inputs.
Our work so far has two main results. First, we have found a novel switch
scheduling policy, called SLIP, which for small switches generally outperforms
the best previously proposed algorithm. Second, SLIP has the advantage of
being much simpler to implement; a scheduler for a moderate-scale switch
(<= 32inputs/outputs) can fit onto a single chip; this appears not to be
the case with most other approaches. Single chip implementations will be
crucial if we are to be able to keep up with increasing link speeds --
a 32 way ATM switch with 10 Gbit/sec links would need to make more than a
billion scheduling decisions per second.
Ivy Hsu
Spyros N. Papadakis
We are currently witnessing a revolution in the telecommunications
industry which moves away from the traditional fixed service networks to
high-bandwidth networks capable of supporting and integrating a multitude
of diverse services. In principle, the high-bandwidth networks currently
under development will be service/independent in that they are not
designed around or optimized for a specific service. On the contrary
the objective is to design and develop "information highways" whose
capability to support a service will be limited only by the imagination
and marketing capability of the service providers.
These services will have different quality requirements and will therefore
be competing for different resources in the network. Interactive services,
for example, demand consistently short delays and thus require high bandwidth
and virtually no queueing as opposed to off-line services like e-mail or
file transfers that can tolerate significantly higher delays but may require
extensive storage. On the other hand the performance of the network with
respect to one of those types of services is tightly coupled with the
performance and resource needs with respect to the other in ways that are
not well understood yet.
A significant problem one faces in the development of these networks, beyond
and above the technological issues, is that of pricing. The question is
how to compare these diverse services and price them rationally and fairly.
Rationality is important from the view point of using pricing as a control
and management tool while fairness is important from the regulatory and
business point of view.
Although not much work has been done in the area, a couple of different
approaches have already been suggested the most radical being a free market
approach in which users bid their offers and the network makes admission
decisions under revenue maximizing criteria. This approach has the advantage
of relieving the network operator from the need of knowing the fine structure
of the process according to which different services interact. On the other
hand it poses questions of stability and network accessibility for the average
residential customer.
In this project, we propose to investigate different approaches to pricing
mainly with respect to stability and network-management.
Spyros N. Papadakis
Our objective is to analyze the behavior of both closed and open networks of
GI/GI/1 queues with state-dependent service rates. Such networks arise as
models of controlled computer systems, flexible manufacturing plans and
communication networks.
We concentrate on macroscopic properties of these networks rather than their
microscopic behavior, the latter being analytically intractable and hope that
these macroscopic characteristics can be used to efficiently control the
network.
Motivated by the work of Kogan et al., we have, in the near past, proved that
under conditions of "uniformly heavy traffic" and some technical conditions on
the service rates the normalized queue length vector converges uniformly in
probability to the solution of a system of ODEs provided that none of the
queues were ever allowed to become empty, i.e., provided that the trajectory
of the normalized queue-length process lay entirely in the interior of its
support.
Furthermore, we were able to extend the result and allow the quelength process
to hit the boundary of its support, i.e., allow for the situation where one or
moreof the queues become empty. In particular, we studied and exhaustively
analyzedthe paradigm of two GI/GI/1 queues in tandem.
These provide a complete first-order approximation to the queuelength process
in the form of a functional law of large numbers. Our research now culminates
in refining these results by establishing a corresponding functional central
limit theorem. The crucial step has been the development of a functional
approximation theory for controlled renewal processes. This enabled us to
prove that, when appropriately scaled, the deviation of the actual queue
length process from the deterministic limiting trajectory converges to a
certain diffusion process.
Nick McKeown, Richard Edell, My T. Le,
Fred L. Burghardt, Ting Kao, and Karl Petty
Papers:
Richard Edell and
Nick McKeown
We have designed a system for billing users for their TCP traffic.
This is achieved by postponing the establishment of connections while the user
is contacted, verifying in a secure way that they are prepared to pay.
By presenting the user with cost and price information, the system can be used
for cost recovery and to encourage efficient use of network resources.
The system requires no changes to existing protocols or applications and can
be used to recover costs between cooperating sites.
Statistic collected from a trace of traffic between the University of
California at Berkeley and the rest of the Internet demonstrate that such a
billing system is practical and introduces acceptable latency.
Our study indicates that pricing schemes may be used to control network
congestion either by rescheduling time-insensitive traffic t a less expensive
time of the day, or by smoothing packet transfers to reduce traffic peaks.
Scheduling Cells in an Input-Queued Switch
Profs. Jean Walrand and Pravin Varaiya
Papers:
Admission Control and Resource Management for ATM Network
Prof. Admission Control for Multi-Class ATM Traffic
with Overflow Constraints
Pricing Issues in Multi-Service Networks
Prof. Jean Walrand
Functional Approximation Theorems for Controlled Queueing Networks
Prof. Jean Walrand
Papers:
The BayBridge: a High Speed Bridge/Router between FDDI and SMDS
Profs. Pravin Varaiya and
Jean Walrand
Summary: 4 pages postscript
Internet Billing and Pricing
Prof. Pravin Varaiya
Papers:
UCB Networking / Matt Siler
siler@eecs.berkeley.edu / January 22, 1996