Tamer Basar (University of Illinois, Urbana-Champaign)
Monday, February 17, 2003
Regulating Traffic on High-Speed Communication Networks: Resource Management, Pricing, and Congestion Control

Today's communication networks, such as the Internet, can be seen as super-fast expressways, transporting packets from sources to destinations along most efficient routes, while respecting priorities and quality-of-service specifications. They can be viewed as large-scale systems with multiple levels of decision making, involving service providers (at the higher level) and individual users (at the lower level). The decisions that each user is faced with, which are generally guided by an appropriate performance index, are (i) at what (flow) rate to inject packets into the network, and (ii) how to adjust these rates in response to (delayed) congestion information received from the network. Occasionally, users are also faced with the task of making decisions on routing, again based on information received from the network. The decisions the network service providers are faced with, on the other hand, are what to charge for the offered resources (such as bandwidth on each link), on what basis to admit users to the network, and whether or not to add additional capacity to any of the links--all driven by revenue maximization.

Modeling and analysis of such large-scale systems, as well as architecting such networks and constructing routing and congestion control policies present challenges of mathematical, engineering and economic nature. This talk will address a number of issues that arise in this context, and present mathematical models that capture the decision making processes at the higher as well as the lower levels. The model for the former is game-theoretic, with the service provider being the revenue-maximizing price-setter and the users being utility maximizing price-takers, with the decisions made on a slower time scale. For the lower level, on the other hand, the model is a nonlinear hybrid control system with uncertain delays, which operates on a relatively faster time scale and with decentralization. For both models, some concrete results will be presented on issues such as optimum pricing, admission control, and capacity expansion at the higher level, and stability of decentralized rate control algorithms at the lower level. The talk will conclude with a discussion of several open problems in this area. [ESE Colloquium Speaker]

In this talk we present a methodology for providing QoS in wireless networks, that deals effectively with the main peculiarity of wireless networks, that differentiates them from their wireline counterparts, namely coordination of transmissions of neighboring interfering links.  An end-to-end session may specify its bandwidth requirements in terms of constant bit rate requirements, or in terms of a guaranteed minimum rate and best effort above that or in terms of a minimum necessary and a maximum rate or in a combination of the above.  Those requirements can be mapped to appropriate quantitative requirements to the rate of each session.  Then allocating the rates according to the solution of the resulting max-min optimization problem will have as a result that the requirements of the users will be satisfied while the residual bandwidth if any will be shared in a fair manner to those session requiring best effort additional bandwidth.  We provide a distributed algorithm that does virtual bandwidth allocation to the different flows based on a token mechanism.  Then scheduling of transmissions is done based on the bandwidth that has been virtually allocated already.  That algorithm has proven to be optimal, providing max-min fair bandwidth allocation.  In fact, despite the large amount of work on QoS provisioning in wireless networks lately, it is the first proven fair bandwidth allocation algorithm in a wireless system that spans more than one node.  It provides a general framework in which practical QoS algorithms can be pursued.

Albert Greenberg (AT&T Research Labs)
Monday, March 3, 2003
Tomogravity – Fast, Accurate Inference of Traffic Matrices for IP Networks

Steven Low (California Institute of Technology)
Monday, March 17, 2003
FAST Kernel

We interpret TCP/AQM (active queue management) as carrying out a distributed primal-dual algorithm over the Internet to maximize aggregate source utility. Different protocols correspond to different optimization algorithms to solve the same prototype problem with different utility functions, and we derive these utility functions explicitly. All equilibrium properties such as throughput, queue length, fairness are determined by this underlying utility maximization problem.

We show that the equilibrium of TCP/RED become unstable as delay increases, or more strikingly, as network capacity increases. It turns out that TCP Vegas has the right scaling with respect to capacity. It can still become unstable if feedback delay is large, but a simple modification stabilizes it.

Finally we describe a new TCP stack, called the FAST Kernel, that implements and demonstrates these advances, and illustrate its performance with recent experimental results.

(With FAST Team and Partners at http://netlab.caltech.edu/FAST)

Nick McKeown (Stanford University)
Monday, March 17, 2003
Trends in the Design and Analysis of Internet Routers

Purpose-built Internet routers were first introduced in the mid-1980s and have since increased in capacity by approximately 2.2-fold every 18 months (that's just slightly ahead of Moore's Law). Along the way, the architecture of commercial routers has changed quite a bit: From a simple shared bus and central CPU, to dedicated parallel crossbar switches with specialized hardware processing pipelines, and recently to multistage, distributed architectures. At the same time, the analytical tools to design routers (including look-up algorithms, scheduling algorithms, and memory architectures) have been steadily improving. In this talk, I will give a quick overview of the evolution of both architectures and analytical techniques, with particular emphasis on our work at Stanford. I'll make some predictions of what the next generation of routers will look like. Then I'll make the preposterous claim that, eventually, Internet core routers must be replaced by optical circuit switches, putting me -- and a lot of other people -- out of a job. [ESE Colloquium Speaker]

Jack Wolf (University of California at San Diego)
Wednesday, March 19, 2003
Constrained Sequences, Crossword Puzzles, and Shannon

Claude Shannon, the father of information theory, is famous for his work on coding for noisy channels and data compression. In this talk I will describe some of Shannon's lesser known results having to do with special sequences and crossword puzzles. [ESE Colloquium Speaker]

Ran Canetti (IBM Research)
Monday, March 24, 2003
How to Authenticate Multicast Streams

One of the main problems in securing multicast communication is source authentication, or enabling receivers of multicasted data to verify that the received data originated with the claimed source and was not modified en-route. The problem becomes more challenging in common settings where other receives of the data are not trusted, and where multicast communication is lossy.

Several source authentication schemes for multicast have been suggested in the past, but none of these schemes is satisfactorily efficient. The talk will describe two schemes for source authentication. The first one is very efficient, and is based on shared-key message authentication codes (MACs), together with loose time synchronization between the sender and receivers and delayed release of keys. This scheme is in the process of being standardized at the Internet Engineering Task Force (IETF). The second scheme is also quite efficient, and does not require any time synchronization. It is based on digital signatures on selected packets with appropriate hashing in between.

The talk will be self-contained and will not assume background in cryptography.

Joint work with Adrian Perrig, Dawn Song and Doug Tygar.

David Sincoskie (Telcordia Technologies)
Monday, March 31, 2003
Broadband Packet Switching: A Personal Perspective

This talk will present the speaker's personal perspective on the development of broadband packet switching from 1980 to 1995 in the context of the Internet's development during the same timeframe. The development of today's Internet is also placed into a 40-year perspective of a mature deployment of a national broadband packet infrastructure. A conclusion that today's Internet is still in the early stages of deployment will be developed. Perspectives on activities like the development of ATM, the CNRI gigabit testbeds, and local ATM will be provided.

R. Srikant (University of Illinois, Urbana-Champaign)
Monday, April 7, 2003
The Timing Capacity of Single-Server Queues with Multiple Input and Output Terminals

We consider an exponential server queue accessed by many different flows. It is assumed that the source and destination information of each flow is available in the packet header. We compute upper and lower bounds on the sum timing capacity of this channel.

We also discuss the implications of this result for a single flow, where packets can be "colored" to distinguish them, and the amount of covert information that can be transmitted over this channel in the presence of eavesdroppers who are allowed to observe the packet headers. We will also discuss the role of the scheduling discipline at the server on the amount of covert information that can be conveyed.

Joint work with Xin Liu. [ESE Colloquium Speaker]

In this talk we will show that significant simplicity can be obtained in both the analysis and the control of large networking systems.

The first part of this talk will focus on the development of a network decomposition technique for the analysis of a network of queues.  The queueing analysis of a network is a well known hard problem, and even after several decades of research, results have been obtained only in a limited number of special cases (e.g., Jackson networks, BCMP networks, etc.).  The typical problem with network analysis is that although we may have a good idea if the traffic characteristics of exogenous flows entering the network, the complex non-linear interactions that take place within the network make it very difficult to characterize the traffic inside the network.  Thus, the problem of network analysis appears to be daunting within the confines of traditional stochastic and queueing techniques.  In this work, I will show that under very general settings, when a large number of traffic flows are multiplexed (a typical scenario) the queue-length of “downstream” queues in a network can be shown to converge (asymptotically in the number of flows) to that of an equivalent queue fed only by exogenous flows.  The type and bounds on the rate of convergence (and thus the error incurred) vary depending on the traffic being considered.  These results have obvious implications for network measurements and design because it allows the use of well established single-queue analytical results to approximately characterize congestion within a network serving a moderate to large number of traffic flows.

In the second part of the talk, I will focus on the problem of network control using pricing for a large system.  We consider a “dynamic” network where users arrive with Poisson arrivals and hold the resources for an arbitrary time.  The network provider can control the admission of the users by charging different prices to different users.  I will show that, when the system becomes large, the performance (in terms of expected revenue) of an appropriately chosen static pricing scheme, whose price is independent of the current network utilization, will approach that of the optimal dynamic pricing scheme.  Further, I will show that under certain conditions, this static price is independent of the route that the flows take.  This suggests that the time-of-day flat pricing scheme used in the domestic long distance telephone service in the US may in fact be a sufficiently good pricing mechanism.  I will also show how the result can be extended to the case of dynamic routing and rate control for real-time streaming.

Balaji Prabhakar (Stanford University)
Monday, April 21, 2003
Simple, Scalable Network Algorithms and Performance Prediction

Randomized algorithms are particularly well-suited for coping with the so-called “curse of dimensionality” from which many networking problems suffer.  The main idea of randomized algorithms is simple to state:  Rather than contend with a large state space, the trick is to base decisions upon a few randomly chosen samples.

This talk will illustrate how randomization and sampling based techniques may be applied for devising simple-to-implement, high-performance network algorithms and for scaleable performance prediction.

Joint work with:  P. Giaccone, R. Pan, K. Psounis, D. Shah, M. Sharma and D. Wischik