Network Algorithms

Switching/Routing

D. Shah, P. Giaccone, B. Prabhakar, "An efficient randomized algorithm for input-queued switch scheduling," IEEE Micro, 22(1):19-25, January-February 2002.
D. Shah, S. Iyer, B. Prabhakar, N. McKeown, "Analysis of a statistics counter architecture," IEEE Micro, 22(1):76-81, January-February 2002.
P. Giaccone, D. Shah, B. Prabhakar, "An implementable parallel scheduler for input-queued switches," IEEE Micro, 22(1):19-25, January-February 2002.
P. Giaccone, E. Leonardi, B. Prabhakar, D. Shah, "Delay performance of high-speed packet switches with low speedup," to appear in Proceedings of the IEEE GLOBECOM 2002, Taipei, Taiwan, November 2002. (CLICK HERE FOR PS FILE)
P. Giaccone, B. Prabhakar, D. Shah, "Towards simple, high-performance schedulers for high-aggregate bandwidth switches," Proceedings of IEEE Infocom Conference on Computer Communications, 3:1160-1169, New York City, June 2002.
D. Shah, S. Iyer, B. Prabhakar, N. McKeown, "Analysis of a statistics counter architecture," Proceedings of Hot Interconnects 9, Stanford University Symposium on High Performance Interconnects, pp.3-8, Stanford, Calif., August 2001.
J.G. Dai, B. Prabhakar, "The throughput of data switches with and without speedup", Proceedings of the IEEE INFOCOM, 2:556-564, Tel Aviv, Israel, March 2000. (CLICK HERE FOR PS FILE)
P. Gupta, B. Prabhakar, S. Boyd, "Near-optimal routing lookups with bounded worst case performance", Proceedings of the IEEE INFOCOM, 3:1184-1192, Tel Aviv, Israel, March 2000. (CLICK HERE FOR PS FILE)
A. Goel, B. Prabhakar, "Stochastic analysis of stable marriages in combined input output queued switches", Proceedings of the IEEE Conference on Decision and Control, Phoenix, Arizona, 3:3096-3101, December 1999. (CLICK HERE FOR PS FILE)
B. Prabhakar, N. McKeown, "On the speedup required for combined input and output queued switching", Automatica, 35(12):1909-1920, 1999. (CLICK HERE FOR PS FILE)
S.-T. Chuang, A. Goel, N. McKeown, B. Prabhakar, "Matching output queueing with a combined input output queued switch", IEEE Journal on Selected Areas in Communications, 17(6):1030-1039, 1999. (A preliminary version appears in Proceedings of INFOCOM '99.) (CLICK HERE FOR PS FILE)
B. Prabhakar, N. McKeown, R. Ahuja, "Multicast scheduling for input-queued switches," IEEE Journal on Selected Areas in Communications, special issue on "Advances in ATM Switching Systems for B-ISDN," 15(5):855-866, 1997.
N. McKeown, B. Prabhakar, M. Zhu, "Matching output queueing with combined input and output queueing," Proceedings of the 35th Allerton Conference on Communication, Control and Computing, Urbana, Illinois, pp.595-603, September 1997.
B. Prabhakar, N. McKeown, J. Mairesse, "Tetris models for multicast switches," Proceedings of the 30th Conference on Information Sciences and Systems, Princeton, New Jersey, 1:216-221, March 1996.


Queue Management

R. Pan, L. Breslau, B. Prabhakar, S. Shenker, "Approximate fairness through differential dropping (summary)," ACM Computer Communication Review, 32(1):72, January 2002. Full paper to appear in ACM Computer Communication Review, 2002.
R. Pan, L. Breslau, B. Prabhakar, S. Shenker, "Flow table-based design to approximate fairness," Proceedings of Hot Interconnect X., Stanford Symposium on High Performance Interconnects, pp.37-42, Stanford, Calif., August 2002.
R. Pan, C. Nair, B. Yang, B. Prabhakar, "Packet dropping schemes, some examples and analysis," Proceedings of the 39th Annual Allerton Conference on Communication, Control and Computing, pp.563-572, October 2001.
K. Psounis, R. Pan, B. Prabhakar, "Approximate fair dropping for variable length packets," IEEE Micro, 21(1):48-56, January 2001.
K. Psounis, R. Pan, B. Prabhakar, "An approximate fair dropping scheme for variable length packets," Proceedings of Hot Interconnects 8, Stanford University, August 2000. (CLICK HERE FOR PS FILE)
R. Pan, B. Prabhakar, K. Psounis, "CHOKe, a stateless active queue management scheme for approximating fair bandwidth allocation", Proceedings of the IEEE INFOCOM, 2:942-951, Tel Aviv, Israel, March 2000. (CLICK HERE FOR PS FILE)


Cache Replacement

K. Psounis, B. Prabhakar, "Efficient randomized web-cache replacement schemes using samples from past eviction times," IEEE/ACM Transactions on Networking, 10(4):441-454, August 2002.
K. Psounis, B. Prabhakar, D. Engler, "A randomized cache replacement approximating LRU," Proceedings of the Conference on Information Sciences and Systems, Princeton, New Jersey, 2:FA05, March 2000. (CLICK HERE FOR PS FILE)


Incentive Mechanism Design

K. Leyton-Brown, R. Porter, B. Prabhakar, Y. Shoham, S. Venkataraman, "Incentive mechanisms for smoothing out a focused demand for network resources," Computer Communication Review, to appear.
K. Leyton-Brown, R. Porter, S. Venkataraman, B. Prabhakar, "Smoothing out focused demand for network resources," Proceedings of the ACM Conference on Electronic Commerce, pp.245-248, Tampa, Florida, October 2001.


Load Balancing

M. Mitzenmacher, B. Prabhakar, D. Shah, "Load balancing with memory," to appear in Proceedings of FOCS, Vancouver, Canada, November 2002. (CLICK HERE FOR PS FILE)
D. Shah, B. Prabhakar, "The use of memory in randomized load balancing," Proceedings of the IEEE International Symposium on Information Theory, p.125, Lausanne, Switzerland, June 2002.
C. Nair, B. Prabhakar, D. Shah, "The randomness in randomized load balancing," Proceedings of the 39th Annual Allerton Conference on Communication, Control and Computing, pp.912-921, October 2001.


Randomized Algorithms

K. Psounis, B. Prabhakar, "Efficient randomized web-cache replacement schemes using samples from past eviction times," IEEE/ACM Transactions on Networking, 10(4):441-454, August 2002.
D. Shah, P. Giaccone, B. Prabhakar, "An efficient randomized algorithm for input-queued switch scheduling," IEEE Micro, 22(1):19-25, January-February 2002.
P. Giaccone, B. Prabhakar, D. Shah, "Towards simple, high-performance schedulers for high-aggregate bandwidth switches," Proceedings of IEEE Infocom Conference on Computer Communications, 3:1160-1169, New York City, June 2002.
C. Nair, B. Prabhakar, D. Shah, "The randomness in randomized load balancing," Proceedings of the 39th Annual Allerton Conference on Communication, Control and Computing, pp.912-921, October 2001.