Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Design for Optimizability: Traffic Management of a Future Internet Read chapter Read first chapter

2010 | OriginalPaper | Chapter

2. Valiant Load-Balancing: Building Networks That Can Support All Traffic Matrices

Author : Rui Zhang-Shen

Published in: Algorithms for Next Generation Networks

Publisher: Springer London

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

This paper is a brief survey on how Valiant load-balancing (VLB) can be used to build networks that can efficiently and reliably support all traffic matrices. We discuss how to extend VLB to networks with heterogeneous capacities, how to protect against failures in a VLB network, and how to interconnect two VLB networks. For the readers’ reference, included also is a list of work that uses VLB in various aspects of networking.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Design for Optimizability: Traffic Management of a Future Internet
next chapter Geometric Capacity Provisioning for Wavelength-Switched WDM Networks
Footnotes
1
We focus on failures in the logical topology, and since several logical links can share a physical link, a physical failure can correspond to multiple logical failures.
 
2
If a node fails, we discard the traffic originating from or terminating at this node.
 
Literature
1.
R. Aleliunas. Randomized parallel communication (preliminary version). In PODC ’82: Proceedings of the first ACM SIGACT-SIGOPS symposium on Principles of distributed computing, pages 60–72, 1982.
2.
K. Argyraki, S. Baset, B.-G. Chun, K. Fall, G. Iannaccone, A. Knies, E. Kohler, M. Manesh, S. Nedevschi, and S. Ratnasamy. Can software routers scale? In PRESTO ’08: Proceedings of the ACM workshop on Programmable routers for extensible services of tomorrow, pages 21–26, 2008.
3.
P. Bernasconi, J. Gripp, D. Neilson, J. Simsarian, D. Stiliadis, A. Varma, and M. Zirngibl. Architecture of an integrated router interconnected spectrally (IRIS). High Performance Switching and Routing, 2006 Workshop on, pages 8 pp.–, June 2006.
4.
C.-S. Chang, D.-S. Lee, and Y.-S. Jou. Load balanced Birkhoff-von Neumann switches, Part I: One-stage buffering. Computer Communications, 25(6):611–622, 2002.CrossRef
5.
C.-S. Chang, D.-S. Lee, and C.-M. Lien. Load balanced Birkhoff-von Neumann switches, Part II: Multi-stage buffering. Computer Communications, 25(6):623–634, 2002.CrossRef
6.
A. Greenberg, P. Lahiri, D. A. Maltz, P. Patel, and S. Sengupta. Towards a next generation data center architecture: scalability and commoditization. In PRESTO ’08: Proceedings of the ACM workshop on Programmable routers for extensible services of tomorrow, pages 57–62, 2008.
7.
M. Henrion, K. Schrodi, D. Boettle, M. De Somer, and M. Dieudonne. Switching network architecture for ATM based broadband communications. Switching Symposium, 1990. XIII International, 5:1–8, 1990.
8.
I. Keslassy, C.-S. Chang, N. McKeown, and D.-S. Lee. Optimal load-balancing. In Proc. IEEE INFOCOM, 2005.
9.
I. Keslassy, S.-T. Chuang, K. Yu, D. Miller, M. Horowitz, O. Solgaard, and N. McKeown. Scaling Internet routers using optics. Proceedings of ACM SIGCOMM ’03, Computer Communication Review, 33(4):189–200, October 2003.
10.
I. Keslassy, M. Kodialam, T. Lakshman, and D. Stiliadis. Scheduling schemes for delay graphs with applications to optical packet networks. High Performance Switching and Routing (HPSR), pages 99–103, 2004.
11.
M. Kodialam, T. V. Lakshman, J. B. Orlin, and S. Sengupta. A Versatile Scheme for Routing Highly Variable Traffic in Service Overlays and IP Backbones. In Proc. IEEE INFOCOM, April 2006.
12.
M. Kodialam, T. V. Lakshman, and S. Sengupta. Efficient and robust routing of highly variable traffic. In HotNets III, November 2004.
13.
D. Mitra and R. A. Cieslak. Randomized parallel communications on an extension of the omega network. J. ACM, 34(4):802–824, 1987.MathSciNetMATHCrossRef
14.
H. Nagesh, V. Poosala, V. Kumar, P. Winzer, and M. Zirngibl. Load-balanced architecture for dynamic traffic. In Optical Fiber Communication Conference, March 2005.
15.
R. Prasad, P. Winzer, S. Borst, and M. Thottan. Queuing delays in randomized load balanced networks. In Proc. IEEE INFOCOM, May 2007.
16.
F. B. Shepherd and P. J. Winzer. Selective randomized load balancing and mesh networks with changing demands. Journal of Optical Networking, 5:320–339, 2006.CrossRef
17.
A. Singh. Load-Balanced Routing in Interconnection Networks. PhD thesis, Department of Electrical Engineering, Stanford University, 2005.
18.
A. Singh, W. J. Dally, B. Towles, and A. K. Gupta. Locality-preserving randomized oblivious routing on torus networks. In SPAA ’02: Proceedings of the fourteenth annual ACM symposium on parallel algorithms and architectures, pages 9–13, 2002.
19.
20.
R. van Haalen, R. Malhotra, and A. de Heer. Optimized routing for providing Ethernet LAN services. Communications Magazine, IEEE, 43(11):158–164, Nov. 2005.CrossRef
21.
P. J. Winzer, F. B. Shepherd, P. Oswald, and M. Zirngibl. Robust network design and selective randomized load balancing. 31st European Conference on Optical Communication (ECOC), 1:23–24, September 2005.
22.
R. Zhang-Shen, M. Kodialam, and T. V. Lakshman. Achieving bounded blocking in circuit-switched networks. IEEE INFOCOM 2006, pages 1–9, April 2006.
23.
R. Zhang-Shen and N. McKeown. Designing a Predictable Internet Backbone Network. In HotNets III, November 2004.
24.
R. Zhang-Shen and N. McKeown. Designing a predictable Internet backbone with Valiant Load-Balancing. Thirteenth International Workshop on Quality of Service (IWQoS), 2005.
25.
R. Zhang-Shen and N. McKeown. Designing a Fault-Tolerant Network Using Valiant Load-Balancing. Proc. IEEE INFOCOM, pages 2360–2368, April 2008.
26.
R. Zhang-Shen and N. McKeown. Guaranteeing Quality of Service to Peering Traffic. Proc. IEEE INFOCOM, pages 1472–1480, April 2008.
Metadata
Title
Valiant Load-Balancing: Building Networks That Can Support All Traffic Matrices
Author
Rui Zhang-Shen
Copyright Year
2010
Publisher
Springer London
Book
Algorithms for Next Generation Networks

Print ISBN: 978-1-84882-764-6

Electronic ISBN: 978-1-84882-765-3

Copyright Year: 2010

DOI
https://doi.org/10.1007/978-1-84882-765-3_2

Premium Partner

    Image Credits