Balaji Prabhakar

Professor
Electrical Engineering and Computer Science
Stanford University

Electrical Engineering Department
350 Serra Mall, Room 269
Stanford, CA 94305-9510
USA

Home


Research
  Societal Networks
  Data Centers


Teaching


Biography
Network Algorithms

Algorithms arise in essentially all networking scenarios: switch scheduling, bandwidth partitioning, web caching, load balancing, minimum-energy scheduling, network measurement, and rapid and scalable network performance prediction. Much of this work can be characterized as "designing high-performance algorithms subject to technology and real world constraints". A theme that consistently emerges in my work is the use of randomization. By basing decisions on a small sample of the state or the input, randomized algorithms dramatically reduce the implementation complexity while delivering excellent performance.

Another thread of research considers gossip algorithms in ad hoc wireless networks, determining the time it takes for rumor to spread or a distributed computation to be performed.

Publications


Switch Scheduling

  1. A. Firoozshahian, V. Manshadi, A. Goel, B. Prabhakar, “Efficient, fully local algorithms for CIOQ switches,” Proceedings of INFOCOM 2007, the 26th IEEE International Conference on Computer Communications, pp.2491-2495, May 2007.
  2. M. Bayati, B. Prabhakar, D. Shah, M. Sharma, “Iterative scheduling algorithms,” Proceedings of INFOCOM 2007, the 26th IEEE International Conference on Computer Communications, pp.445-453, May 2007.
  3. P. Giaccone, E. Leonardi, B. Prabhakar, D. Shah, “Delay bounds for combined input-output switches with low speedup,” Performance Evaluation, 55(1-2):113-128, January 2004.
  4. P. Giaccone, B. Prabhakar, D. Shah, “Randomized scheduling algorithms for high-aggregate bandwidth switches,” IEEE Journal on Selected Areas in Communications, 21(4):546-559, May 2003.
  5. P. Giaccone, B. Prabhakar, D. Shah, “Switching under energy constraints,” Proceedings of the 36th Asilomar Conference on Signals, Systems and Computers, 2:1538-1542, November 2002.
  6. P. Giaccone, E. Leonardi, B. Prabhakar, D. Shah, “Delay performance of high-speed packet switches with low speedup,” Proceedings of the IEEE Global Telecommunications Conference, GLOBECOM, 21(1):2636-2640, November 2002.
  7. P. Giaccone, B. Prabhakar, D. Shah, “Towards simple, high-performance schedulers for high-aggregate bandwidth switches,” Proceedings of IEEE INFOCOM Conference on Computer Communications, 21(1):1160-1169, June 2002.
  8. D. Shah, P. Giaccone, B. Prabhakar, “Efficient randomized algorithms for input-queued switch scheduling,” IEEE Micro, 22(1):10-18, January-February 2002.
  9. P. Giaccone, D. Shah, B. Prabhakar, “An implementable parallel scheduler for input-queued switches,” IEEE Micro, 22(1):19-25, January-February 2002.
  10. P. Giaccone, D. Shah, B. Prabhakar, “An implementable parallel scheduler for input-queued switches,” Proceedings of Hot Interconnects 9 Symposium on High Performance Interconnects, pp.9-14, August 2001.
  11. D. Shah, P. Giaccone, B. Prabhakar, “An efficient randomized algorithm for input-queued switch scheduling,” Proceedings of Hot Interconnects 9 Symposium on High Performance Interconnects, pp.3-8, August 2001.
  12. J. Dai, B. Prabhakar, “The throughput of data switches with and without speedup,” Proceedings of IEEE INFOCOM Conference on Computer Communications, 2:556-564, March 2000.
  13. Invited. A. Goel, B. Prabhakar, “Stochastic analysis of stable marriages in combined input output queued switches,” Proceedings of the 38th IEEE Conference on Decision and Control, 3:3096-3101, December 1999.
  14. Invited. B. Prabhakar, N. McKeown, “On the speedup required for combined input and output queued switching,” Automatica, 35(12):1909-1920, December 1999.
  15. 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, special issue on Next Generation IP Switches and Routers, 17(6):1030-1039, June 1999.
  16. S.T. Chuang, A. Goel, N. McKeown, B. Prabhakar, “Matching output queueing with a combined input output queued switch,” Proceedings of IEEE INFOCOM Conference on Computer Communications, 3:1169-1178, March 1999.
  17. B. Prabhakar, N. McKeown, “On the speedup required for combined input and output queued switching,” Proceedings of the IEEE International Symposium on Information Theory, p.165, August 1998.
  18. N. McKeown, B. Prabhakar, M. Zhu, “Matching output queueing with combined input and output queueing,” Proceedings of the 35th Annual Allerton Conference on Communications, Control and Computing, pp.595-603, September 1997.
  19. 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, June 1997.
  20. B. Prabhakar, N. McKeown, J. Mairesse, “Tetris models for multicast switches,” Proceedings of the 30th Annual Conference on Information Sciences and Systems, 1:216- 221, March 1996.
  21. N. McKeown, B. Prabhakar, “Scheduling multicast cells in an input-queued switch,” Proceedings of IEEE INFOCOM Conference on Computer Communications, 1:271-278, March 1996.
  22. B. Prabhakar, N. McKeown, “Designing a multicast switch scheduler,” Proceedings of the 33rd Annual Allerton Conference on Communication, Control and Computing, pp.984-993, October 1995.

Go to top

Bandwidth Partitioning

  1. R. Pan, F. Bonomi, B. Prabhakar, “Approximate bandwidth partitioning – from academia to industry,” Proceedings of the 46th Annual Allerton Conference on Communications, Control and Computing, September 2008.
  2. R. Pan, B. Prabhakar, L. Breslau, S. Shenker, “Approximate fair allocation of link bandwidth,” IEEE Micro, 23(1): 36-43, January-February 2003.
  3. Best Paper Award. R. Pan, L. Breslau, B. Prabhakar, S. Shenker, “Flow table-based design to approximate fairness,” Proceedings of Hot Interconnects 10 - Symposium on High Performance Interconnects, pp.37-42, August 2002.
  4. R. Pan, L. Breslau, B. Prabhakar, S. Shenker, “Approximate fairness through differential dropping (a summary),” from Proceedings of SIGCOMM 2001, ACM Computer Communication Review, 32(1):72, January 2002.
  5. Invited. 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.
  6. Invited. K. Psounis, R. Pan, B. Prabhakar, “Approximate fair dropping for variable length packets,” IEEE Micro, 21(1):48-56, January-February 2001.
  7. K. Psounis, R. Pan, B. Prabhakar, “An approximate fair dropping scheme for variable length packets,” Proceedings of Hot Interconnects 8 - Symposium on High Performance Interconnects, August 2000.
  8. R. Pan, B. Prabhakar, K. Psounis, “CHOKe — a stateless active queue management scheme for approximating fair bandwidth allocation,” Proceedings of IEEE INFOCOM Conference on Computer Communications, pp.942-951, March 2000.
  9. B. Prabhakar, R. Pan, “CHOKe — A stateless mechanism for providing quality of service in the Internet,” Proceedings of the 37th Allerton Conference on Communication, Control and Computing, pp.1122-1131, September 1999.

Go to top

Web Caching

  1. K. Psounis, A. Zhu, B. Prabhakar, R. Motwani, “Modeling correlations in web traces and implications for designing replacement policies,” Computer Networks, 45(4):379-398, July 2004.
  2. 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.
  3. K. Psounis, B. Prabhakar, “A randomized web-cache replacement scheme,” Proceedings of IEEE INFOCOM Conference on Computer Communications, pp.1407-1415, April 2001.
  4. K. Psounis, B. Prabhakar, D. Engler, “A randomized cache replacement approximating LRU,” Proceedings of the Conference on Information Sciences and Systems, 2:FA05, March 2000.

Go to top

Load Balancing

  1. M. Bramson, Y. Lu, B. Prabhakar, "Randomized load balancing with general service time distributions," Proceedings of the ACM Special Interest Group on Computer Systems Performance, SIGMETRICS 2010, June 2010.
  2. V. Farias, C. Moallemi, B. Prabhakar, “Load balancing with migration penalties,” Proceedings of the IEEE International Symposium on Information Theory, pp.558-562, September 2005.
  3. Invited. K. Leyton-Brown, R. Porter, B. Prabhakar, Y. Shoham, S. Venkataraman, “Incentive mechanisms for smoothing out a focused demand for network resources,” Computer Communications, 26(3):237-250, February 2003.
  4. M. Mitzenmacher, B. Prabhakar, D. Shah, “Load balancing with memory,” Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, pp.799-808, November 2002.
  5. D. Shah, B. Prabhakar, “The use of memory in randomized load balancing,” Proceedings of the IEEE International Symposium on Information Theory, p. 125, June 2002.
  6. Invited. 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.

Go to top

Minimum Energy Scheduling

  1. E. Uysal-Biyikoglu, A. El Gamal, B. Prabhakar, “Adaptive transmission of variable-rate data over a fading channel for energy-efficiency,” Proceedings of the IEEE Global Telecommunications Conference, GLOBECOM, 21(1):98-102, November 2002.
  2. Invited. E. Uysal-Biyikoglu, B. Prabhakar, A. El Gamal, “Energy-efficient packet transmission over a wireless link,” IEEE/ACM Transactions on Networking, 10(4):487-499, August 2002.
  3. A. El Gamal, C. Nair, B. Prabhakar, E. Uysal-Biyikoglu, S. Zahedi, “Energy-efficient scheduling of packet transmissions over wireless networks,” Proceedings of IEEE INFOCOM Conference on Computer Communications, 21(1):1773-1782, June 2002.
  4. B. Prabhakar, E. Uysal-Biyikoglu, A. El Gamal, “Energy-efficient transmission over a wireless link via lazy packet scheduling,” Proceedings of IEEE INFOCOM Conference on Computer Communications, pp.386-394, April 2001.

Go to top

Network Measurement

  1. Y. Lu, A. Montanari, B. Prabhakar, "Counter braids: asymptotic optimality of the message passing decoding algorithm," Proceedings of the 46th Annual Allerton Conference on Communications, Control and Computing, September 2008.
  2. Best Paper Award. Y. Lu, A. Montanari, B. Prabhakar, S. Dharmapurikar, A. Kabbani, "Counter braids: a novel counter architecture for per-flow measurement," Proceedings of the 2008 ACM Sigmetrics, International Conference on Measurement and Modeling of Computer Systems, pp.121-132, June 2008.
  3. Y. Lu, A. Montanari and B. Prabhakar, “Counter braids”, Proceedings of the IEEE Information Theory Workshop, pp.220-221, May 2008.
  4. Y. Lu, A. Montanari, B. Prabhakar, “Detailed network measurements using sparse graph counters: The theory,” Proceedings of the 45th Allerton Conference on Communication, Control and Computing, September 2007.
  5. Y. Lu, M. Wang, B. Prabhakar, F. Bonomi, “ElephantTrap: A low cost device for identifying large flows,” Proceedings of HOT Interconnects, August 2007.
  6. Y. Lu, B. Prabhakar, F. Bonomi, “Perfect hashing for network applications,” Proceedings of the 2006 IEEE International Symposium on Information Theory, pp.2774-2778, July 2006.
  7. K. Psounis, A. Ghosh, B. Prabhakar, G. Wang, “SIFT: A simple algorithm for tracking elephant flows and taking advantage of power laws,” Proceedings of the 43rd Allerton Conference on Communication, Control and Computing, September 2005.
  8. Y. Lu, B. Prabhakar, F. Bonomi, “Bloom filters: Design innovations and applications,” Proceedings of the 43rd Allerton Conference on Communication, Control and Computing, September 2005.
  9. D. Shah, S. Iyer, B. Prabhakar, N. McKeown, “Maintaining statistics counters in router line cards,” IEEE Micro, 22(1):76-81, January-February 2002.
  10. D. Shah, S. Iyer, B. Prabhakar, N. McKeown, “Analysis of a statistics counter architecture,” Proceedings of Hot Interconnects 9 - Symposium on High Performance Interconnects, pp.107-111, August 2001.

Go to top

Rapid and Scalable Network Performance Prediction

  1. R. Pan, K. Psounis, B. Prabhakar, D. Wischik, “SHRiNK: A method for enabling scaleable performance prediction and efficient network simulation,” IEEE/ACM Transactions on Networking, 13(5):975-989, October 2005.
  2. R. Pan, B. Prabhakar, K. Psounis, D. Wischik, “SHRiNK: A method for scaleable performance prediction and efficient network simulation,” Proceedings of IEEE INFOCOM Conference on Computer Communications, 22(1):1943-1953, March 2003.
  3. Invited. K. Psounis, R. Pan, B. Prabhakar, D. Wischik, “The scaling hypothesis: simplifying the prediction of network performance using scaled-down simulations,” Proceedings of HotNets-1, October 2002. Also appears in ACM Computer Communication Review, 33(1):35-40, January 2003.
  4. Invited. R. Pan, B. Prabhakar, K. Psounis, M. Sharma, “A study of the applicability of a scaling hypothesis,” Proceedings of the 4th Asian Control Conference, September 2002.

Go to top

Random Assignment Problem

  1. C. Nair, B. Prabhakar, M. Sharma, “Proofs of the Parisi and Coppersmith-Sorkin random assignment conjectures,” Random Structures and Algorithms, 27(4):413-444, December 2005.
  2. C. Nair, B. Prabhakar, M. Sharma, “A new proof of Parisi’s conjecture for the finite random assignment problem,” Proceedings of the IEEE International Symposium on Information Theory, p.61, June 2004.
  3. C. Nair, B. Prabhakar, M. Sharma, “Proofs of the Parisi and Coppersmith-Sorkin conjectures for the finite random assignment problem,” Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, pp.168-178, October 2003.
  4. Invited. M. Sharma, B. Prabhakar, “On Parisi’s conjecture for the finite random assignment problem,” Proceedings of the 40th Annual Allerton Conference on Communication, Control and Computing, pp.657-666, October 2002.

Go to top

Miscellaneous

  1. S. Boyd, A. Ghosh, B. Prabhakar, D. Shah, “Randomized gossip algorithms,” IEEE Transactions on Information Theory, 52(6):2508-2530, June 2006.
  2. B. Prabhakar, “Network hardware algorithms,” Proceedings of the 2005 International Conference on Collaborative Computing: Networking, Applications and Worksharing, p.1, December 2005.
  3. K. Psounis, P. Molinero Fernandez, B. Prabhakar, F. Papadopoulos, “Systems with multiple servers under heavy-tailed workloads,” Performance Evaluation, 62:456-474, October 2005.
  4. S. Boyd, A. Ghosh, B. Prabhakar, D. Shah, “Gossip algorithms: Design, analysis and applications,” Proceedings of IEEE INFOCOM 2005 - The Conference on Computer Communications, 1:1653-1664, March 2005.
  5. S. Boyd, A. Ghosh, B. Prabhakar, D. Shah, “Mixing times for random walks on geometric random graphs,” Proceedings of ANALCO, Workshop on Analytic Algorithmics and Combinatorics, pp.240-249, January 2005.
  6. S. Boyd, A. Ghosh, B. Prabhakar, D. Shah, “Analysis and optimization of randomized gossip algorithms,” Proceedings of the 43rd IEEE Conference on Decision and Control, 5:5310-5315, December 2004.
  7. M. Sharma, D. Katabi, R. Pan, B. Prabhakar, “An in-band easy-to-deploy mechanism for network-to-transport signaling,” Proceedings of the IEEE Global Telecommunications Conference, GLOBECOM, 2:1278-1283, November 2004.
  8. P. Giaccone, B. Prabhakar, D. Shah, “Constrained wireless scheduling: throughput, energy and delay,” Proceedings of the Allerton Conference on Communication, Control and Computing, October 2003.
  9. 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, October 2001.
  10. P. Gupta, B. Prabhakar, S. Boyd, “Near-optimal routing lookups with bounded worst case performance,” Proceedings of IEEE INFOCOM Conference on Computer Communications, pp.1184-1192, March 2000.
  11. B. Prabhakar, P. Gupta, S. Boyd, “A two-bit scheme for routing lookup,” Proceedings of the IEEE Information Theory and Networking Workshop, p.45, June 1999.

Go to top




Web: Balaji Prabhakar
Email:
Office: Packard 269
Phone: (650) 723-5896
Assistant: Andrea Kuduk
Email: kuduk@ee.stanford.edu
Office: Packard 267
Phone: (650) 723-4731