• Active Queue Management
• Multimedia over Networks
• Scalable Performance Prediction and Efficient Network Simulation
• Switching
• TCP Performance
• Web Caching and Performance

Active Queue Management:

• We are researching on various packet dropping schemes that ensure fair bandwidth allocation to all flows at a congested router. Presently the widely used congestion control scheme is RED. However it is not effective in ensuring fair bandwidth allocation when all flows coming to the router are not identical. We simulate and analyse randomized algorithms that ensure fairness with very little complexity and memory.

 
Publications:

• "Approximate Fairness through Differential Dropping", R. Pan, L. Breslau, B. Prabhakar, S. Shenker, ACM Computer Communication Review, July 2003.
• "A Flow Table-based Design to Approximate Fairness", R. Pan, L. Breslau, B. Prabhakar, S. Shenker, BEST PAPER AWARD, Proceedings of Hot Interconnects, 2002 and by invitation IEEE Micro January/February 2003.
• "Packet Dropping Schemes: Some Examples and Analysis", R. Pan, C.Nair, B.Yang, B. Prabhakar, Proceedings of the Allerton Conference on Communication, Control, and Computing, Urbana, Illinois, 2001.
  
• "An Approximate Fair Dropping Scheme for Variable Length Packets", K. Psounis, R. Pan, B Prabhakar, Proceedings of Hot Interconnects, Aug 16-18, 2000. Stanford University and IEEE Micro January/February 2001.
• "CHOKe, A Stateless Active Queue Management Scheme for Approximating Fair Bandwidth Allocation", R. Pan, K. Psounis, B. Prabhakar, Proceedings of INFOCOM 2000.
• "CHOKe: A Stateless Mechanism for Providing Quality of Service in the Internet", R Pan, B. Prabhakar. Proceedings of the 37th Annual Allerton Conference on Communication, Control and Computing, 1999

• Multimedia applications (e.g. VoIP, video streaming) over packet networks face challenges such as packet loss, delay and delay jitter. Typically, these applications consider the network as a "black box" and rely on the end-systems to minimize the effect of impairments. We are interested in algorithms that react to network variations by optimizing packet transmission and playout speed.

  On the other hand, the collaboration between network and traditional data applications has been proven very successful in many cases, including congestion control and wireless loss notification. We are currently investigating how to use notification from the network to assist multimedia applications, by providing them with an improved (more accurate and earlier) knowledge of the state of the network. In particular, we are studying the use of ECN-like notification to improve the performance of adaptive media playout and multipath video transmission.

  These problems become particularly important in wireless packet networks (such as 802.11 wireless LANs), where bandwidth is inherently limited and variability plays an important role.

• Measuring the performance of the Internet and predicting it behavior under novel protocols and architectures are important
  research problems. These problems are made difficult by the sheer size and heterogeneity of the Internet. We explore a method to sidestep these problems by combining sampling, modeling and simulation. Our hypothesis is this: if we take a sample of the input traffic, and feed it into a suitably scaled version of the system, we can extrapolate from the performance of the scaled system to that of the original.  

 
Publications:

• "SHRiNK: A Method for Scaleable Performance Prediction and Efficient Network Simulation", R. Pan, B. Prabhakar, K. Psounis, D. Wischik, Proceedings of INFOCOM 2003.
• "The Scaling Hypothesis: Simplifying the Prediction of Network Performance using Scaled-down Simulations". K. Psounis, R. Pan, B Prabhakar, Damon Wischik, Proceedings of SIGCOMM HotNets-I, 2002.
• "A Study of the Applicability of a Scaling Hypothesis", R Pan, B. Prabhakar, R. Pan, B. Prabhakar, K. Psounis, M. Sharma, Proceedings of the 4th Asia Control Conference, Singapore, 2002.

• Input Queued(IQ) switches/routers have been of recent interest due to their ability of working at same speed as line rate. The Schedular is a very important component of an IQ switch. There has been lot of work to design good switch scheduling algorithms. The algorithms suggested in past suffer from the problem of: either (a) they do not good throughput/delay; or (b) they are not feasible to implement as they do not scale with speed and size. Our goal is to address this difficult problem using some sort of randomization. We have designed efficient, implementable and high performance switch scheduling algorithms which are provably good. We believe that they can be implemented. We further explore possibility of coming up with better algorithms.
• The problem of route address lookup has received much attention recently and several algorithms and data structures for performing address lookups at high speeds have been proposed. We are researching into ideas from Information Theory to derive efficient algorithms that compute near optimal routing lookups.
• We are also looking into issues on the speedup and QoS guarantees on a Input Queued and CIOQ switch. These include issues on minimum speedup for ensuring QoS guarantees and various efficient algorithms for a CIOQ switch that would meet these guarantees.

 
Publications:  

• "Switch Scheduling via Edge coloring", G. Aggarwal, R. Motwani, D. Shah, A. Zhu, Proceedings of FOCS, 2003.
• "Maximal Scheduling is good enough", D. Shah, Proceedings of Globecom, 2003.
• "Input Queued Switches: Cell switching v/s Packet switching", Y. Ganjali, A. Keshavarzian, D. Shah, Proceedings of Infocom (selected as one of the top 10 papers), 2003. 
• "Switch scheduiing under Heavy Traffic", D. Shah, D. J. Wischik, under preparation. ( Slides from a talk at Workshop on Heavy Traffic Analysis, Eindhoven, 2003.
• "Delay Performance of High-Speed Packet Switches with Low Speedup",  P. Giaccone, E. Leonardi, B. Prabhakar, D. Shah, Proceedings of Globecom 2002.
• "Switching Under Energy Constraint", P. Giaccone, B. Prabhakar, D. Shah, invited paper at Asilomar 2002.
• "Towards Simple, High-Performance Schedulers for High-aggregate Bandwidth Switches", P. Giaccone, B. Prabhakar, D. Shah,  Proceedings of Infocom 2002.
• "Delay Bounds for Approximate Maximum Weight Matching Algorithms for Input-Queued Switches", P. Giaccone, B. Prabhakar, D. Shah,  Proceedings of Infocom 2002.
• "An Efficient Randomized Algorithm for Input-Queued Switch Scheduling", D. Shah, P. Giaccone, B. Prabhakar, IEEE Micro, 22(1):19-25, January-February 2002.
• "An Implementable Parallel Scheduler for Input-Queued Switches", P. Giaccone, D. Shah, B. Prabhakar, IEEE Micro, 22(1):19-25, January-February 2002.
• "Stable algorithms for Input Queued switches", D. Shah, Proceedings of the Allerton Conference on Communication, Control, and Computing, Urbana, Illinois, 2001.
• "The Throughput of Data Switches with and without Speedup", B. Prabhakar, J Dai. Proceedings of INFOCOM 2000.
• "Stochastic Analysis of Stable Marriages in a Combined Input Output Queued Switch", A. Goel, B. Prabhakar. Proceedings of 38th IEEE Conference on Decision and Control, 1999.
• "On the Speedup required for Combined Input Output Queued Switch", B. Prabhakar, N McKeown. Invited Paper, Automatica Vol. 35, no. 12, Dec 1999.
• "Matching Output Queueing with a Combined Input Output Queued Switch". S-T Chuang, A. Goel, N McKeown, B. Prabhakar, IEEE JSAC, vol.17, n.6, pp. 1030-1039, Dec. 1999.
• "Multicast scheduling for input-queued switches",  B. Prabhakar, N. McKeown, R. Ahuja, IEEE Journal on Selected Areas in Communications, special issue on "Advances in ATM Switching Systems for B-ISDN," 15(5):855-866, 1997.
• "Matching output queueing with combined input and output queueing", N. McKeown, B. Prabhakar, M. Zhu,  Proceedings of the 35th Allerton Conference on Communication, Control and Computing, Urbana, Illinois, pp.595-603, September 1997.
• "Tetris models for multicast switches", B. Prabhakar, N. McKeown, J. Mairesse, Proceedings of the 30th Conference on Information Sciences and Systems, Princeton, New Jersey, 1:216-221, March 1996.
• "Scheduling Multicast Cells in an Input-Queued Switch", N. McKeown and B. Prabhakar, Proceedings of IEEE Infocom '96, San Francisco, Vol 1, pp. 271-278, March 1996.
• "Designing a Multicast Switch Scheduler", B. Prabhakar and N. McKeown, Proceedings of the 33rd Annual Allerton Conference on Communication, Control, and Computing. pp. 984-993.
  Monticello, Illinois, October 1995.

TCP Performance:

• Studies have shown that  the file size distribution of Internet traffic, 90% of which uses the TCP protocol,  has a heavy-tail. In simple terms, it means that most TCP connections are ``mice'' (with short lifetimes, still in the slow start phase), but a few large TCP flows referred as ``elephants'' (with long lifetimes, in congestion avoidance phase) generate most of the traffic. However,  little is known regarding how the mice and the elephants interact with each other when they share a common link. We are studying how long-lived TCP flows' performance is affected by the existence of "mice".
  
  

Web Cache Performance and Analysis:

• The problem of document replacement in web caches has received much attention in recent research, and it has been shown that the eviction rule ``replace the least recently used document'' performs poorly in web caches. Instead, it has been shown that using a combination of several criteria, such as the recentness and frequency of use, the size, and the cost of fetching a document, leads to a sizeable improvement in hit rate and latency reduction. However, in order to implement these novel schemes, one needs to maintain complicated data structures. We propose randomized algorithms for approximating any existing web-cache replacement scheme and thereby avoid the need for any data structures.
• A number of web-cache-related algorithms rely on specific characteristics present in the sequence of requests for efficient performance. For example, cache replacement policies exploit the temporal locality between requests and the long term popularity of web documents during eviction times, and prefetching policies take advantage of correlations present in inter-document requests. Given that algorithm design relies on the characteristics of web traces, we aim to obtain a simple and accurate model of web-cache-request traces. The model we propose precisely captures the degrees to which time correlations and document popularity influence web trace requests. As an important by-product our model provides guidelines for designing efficient replacement algorithms.

 
Publications:  

• "Efficient Randomized Web-Cache Replacement Schemes Using Samples from Past Eviciton-Times", Konstantinos Psounis and Balaji Prabhakar, IEEE/ACM Transactions on Netwrorking, August 2002.
• "A randomized web-cache replacement scheme",  K. Psounis, B. Prabhakar, Proceedings of IEEE INFOCOM 2001.
• "A Randomized cache replacement scheme approximating LRU", K. Psounis,  B. Prabhakar, D. Engler, Proceedings of  34th Annual Conference on Information Sciences and Systemsar, 2000.

ISNL
 

Copyright © 2003 Stanford University Last modified: 4 Sept 2003 Send comments and questions to kopi@stanford.edu