Areas of Research of the Networking Research Group

This is a partial list of research topics. To add to the current contents, please contact Matt Siler siler@eecs.berkeley.edu.


 * 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

 * Internet Billing and Pricing

Scheduling Cells in an Input-Queued Switch

Nick McKeown
Profs. Jean Walrand and Pravin Varaiya

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.

Papers:

Admission Control and Resource Management for ATM Network

Ivy Hsu
Prof. Admission Control for Multi-Class ATM Traffic with Overflow Constraints

  • Dynamic Bandwidth Allocation for ATM Switches
  • Quick Detection of Changes in Traffic Statistics: Application to Variable Rate Compression
  • Admission Control for ATM Networks

    Pricing Issues in Multi-Service Networks

    Spyros N. Papadakis
    Prof.
    Jean Walrand

    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.

    Functional Approximation Theorems for Controlled Queueing Networks

    Spyros N. Papadakis
    Prof.
    Jean Walrand

    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.

    Papers:

    The BayBridge: a High Speed Bridge/Router between FDDI and SMDS

    Nick McKeown, Richard Edell, My T. Le, Fred L. Burghardt, Ting Kao, and Karl Petty
    Profs.
    Pravin Varaiya and Jean Walrand

    Summary: 4 pages postscript

    Papers:

    Internet Billing and Pricing

    Richard Edell and Nick McKeown
    Prof. Pravin Varaiya

    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.

    Papers:

    UCB Networking / Matt Siler siler@eecs.berkeley.edu / January 22, 1996