## Selective randomized load balancing and mesh networks with changing demands

Journal of Optical Networking, Vol. 5, Issue 5, pp. 320-339 (2006)

http://dx.doi.org/10.1364/JON.5.000320

Acrobat PDF (445 KB)

### Abstract

We consider the problem of building cost-effective networks that are robust to dynamic changes in demand patterns. We compare several architectures using demand-oblivious routing strategies. Traditional approaches include single-hop architectures based on a (static or dynamic) circuit-switched core infrastructure and multihop (packet-switched) architectures based on point-to-point circuits in the core. To address demand uncertainty, we seek minimum cost networks that can carry the class of hose demand matrices. Apart from shortest-path routing, Valiant's randomized load balancing (RLB), and virtual private network (VPN) tree routing, we propose a third, highly attractive approach: selective randomized load balancing (SRLB). This is a blend of dual-hop hub routing and randomized load balancing that combines the advantages of both architectures in terms of network cost, delay, and delay jitter. In particular, we give empirical analyses for the cost (in terms of transport and switching equipment) for the discussed architectures, based on three representative carrier networks. Of these three networks, SRLB maintains the resilience properties of RLB while achieving significant cost reduction over all other architectures, including RLB and multihop Internet protocol/multiprotocol label switching (IP/MPLS) networks using VPN-tree routing.

© 2006 Optical Society of America

**OCIS Codes**

(060.4250) Fiber optics and optical communications : Networks

**ToC Category:**

RESEARCH PAPERS

**History**

Original Manuscript: November 21, 2005

Revised Manuscript: March 6, 2006

Manuscript Accepted: March 8, 2006

Published: April 5, 2006

**Citation**

F. B. Shepherd and P. J. Winzer, "Selective randomized load balancing and mesh networks with changing
demands," J. Opt. Netw. **5**, 320-339 (2006)

http://www.opticsinfobase.org/jocn/abstract.cfm?URI=jon-5-5-320

Sort: Year | Journal | Reset

### References

- A. Altin, E. Amaldi, B. Pelotti, and M. Pinar, 'Provisioning virtual private networks under traffic uncertainty,' presented at the International Network Optimization Conference, Lisbon, Portugal, March 2005.
- D. Applegate and E. Cohen, 'Making intradomain routing robust to changing and uncertain traffic demands: understanding fundamental tradeoffs,' in Proceedings of the ACM SIGCOMM 2003 Conference on Applications, Technologies, Architectures and Protocols for Computer Communications (Association for Computing Machinery, 2003), pp. 313-324.
- W. Ben-Ameur and H. Kerivin, 'New economical virtual private networks,' Commun. ACM 44(6), 69-73 (2003).
- W. Ben-Ameur and H. Kerivin, 'Routing of uncertain demands,' Optimization Eng. 6, 283-313 (2005).
- C.-S. Chang, D.-S. Lee, and Y.-S. Jou, 'Load balanced Birkhoff-von Neumann switches. Part I. One-stage buffering,' presented at the 2001 IEEE Workshop on High Performance Switching and Routing (HPSR), Kobe, Japan, 26-29 May 2001.
- C. Chekuri, G. Oriolo, M. G. Scutella, and F. B. Shepherd, 'Hardness of robust network design,' presented at the International Network Optimization Conference, Lisbon, Portugal, March 2005.
- N. G. Duffield, P. Goyal, A. Greenberg, P. Mishra, K. K. Ramakrishnan, and J. E. van der Merwe, 'Resource management with hoses: point-to-cloud services for virtual private networks,' IEEE/ACM Trans. Netw. 10, 679-692 (2002).
- F. Eisenbrand and F. Grandoni, 'An improved approximation algorithm for virtual private network design,' presented at the 16th Annual Association for Computing Machinery-Society for Industrial and Applied Mathematics Symposium On Discrete Algorithms, Vancouver, British Columbia, Canada, 23-25 January 2005.
- T. Erlebach and M. Ruegg, 'Optimal bandwidth reservation in hose-model VPNs with multi-path routing,' in IEEE INFOCOM 2004 (IEEE Computer Society, 2004), Vol. 4, pp. 2275-2282.
- J. A. Fingerhut, S. Suri, and J. Turner, 'Designing least-cost nonblocking broadband networks,' J. Algorithms 22, 287-309 (1997).
- A. Gupta, J. Kleinberg, A. Kumar, R. Rastogi, and B. Yener, 'Provisioning a virtual private network: a network design problem for multicommodity flow,' presented at the 33rd Annual ACM Symposium on Theory of Computing, Hersonissos, Crete, Greece, July 2001.
- A. Gupta, A. Kumar, and T. Roughgarden, 'Simpler and better approximation algorithms for network design,' presented at the 35th Annual ACM Symposium on Theory of Computing, San Diego, California, 9-11 June 2003.
- C. A. J. Hurkens, J. C. M. Keijsper, and L. Stougie, 'Virtual private network design: a proof of the tree routing conjecture on ring networks,' in Proceedings of the 11th International Integer Programming and Combinatorial Optimization Conference, Vol. 3509 of Lecture Notes in Computer Science (Springer-Verlag, 2005), pp. 407-421.
- G. Italiano, S. Leonardi, and G. Oriolo, 'Design of networks in the hose model,' in Proceedings of 3rd Workshop on Approximation and Randomization Algorithms in Communication Networks (ARACNE) (Carleton Scientific, 2002), pp. 65-76.
- I. Keslassy, S.-T. Chuang, K. Yu, D. Miller, M. Horowitz, O. Solgaard, and N. McKeown, 'Scaling Internet routers using optics,' in Proceedings of the ACM SIGCOMM 2003 Conference on Applications, Technologies, Architectures and Protocols for Computer Communications (Association for Computing Machinery, 2003), 189-200.
- M. Kodialam, T. V. Lakshman, and S. Sengupta, 'Efficient and robust routing of highly variable traffic,' presented at HotNets III, San Diego, California, November 2004.
- T. Leighton and S. Rao, 'An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms,' in Proceedings of the 29th IEEE Symposium on Foundations of Computer Science (IEEE, 1988), pp. 422-431.
- D. Leung and W. D. Grover, 'Capacity planning of survivable mesh-based transport networks under demand uncertainty,' Photon. Netw. Commun. 10, 123-140 (2005).
- D. Mitra and R. A. Cieslak, 'Randomized parallel communications on an extension of the omega network,' J. Assoc. Comput. Mach. 32, 802-824 (1987).
- H. Nagesh, V. Poosala, V. Kumar, P. J. Winzer, and M. Zirngibl, 'Load-balanced architecture for dynamic traffic,' presented at the Optical Fiber Communication Conference, Anaheim, California, March 2005, paper OME67.
- H. Nagesh, V. Poosala, S. Sengupta, M. Alicherry, and V. Kumar, 'NetSwitch: load-balanced data-over-optical architecture for mesh networks,' Lucent Technical Memorandum ITD-04-45867F (Lucent Technologies, 2004).
- A. Kumar, R. Rastogi, A. Silberschatz, and B. Yener, 'Algorithms for provisioning virtual private networks in the hose model,' IEEE/ACM Trans. Netw. 10, 565-578 (2002).
- H. Räcke, 'Minimizing congestion in general networks, 'in Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science (IEEE, 2002), pp. 43-52.
- S. Sengupta, V. Kumar, and D. Saha, 'Switched optical backbone for cost-effective scalable core IP networks,' IEEE Commun. Mag. 41(6), 60-70 (2003).
- L. G. Valiant, 'A scheme for fast parallel communication,' SIAM J. Comput. 11(2), 350-361 (1982).
- I. Widjaja and A. I. Elwalid, 'Exploiting parallelism to boost data-path rate in high-speed IP/MPLS networking,' presented at the IEEE Workshop on High-Speed Networking, New York, New York, 23 June 2002.
- P. J. Winzer, F. B. Shepherd, P. Oswald, and M. Zirngibl, 'Robust network design and selective randomized load balancing,' presented at the European Conference on Optical Communications (ECOC'05), Glasgow, Scotland, 25-29 September 2005.
- R. Zhang-Shen and N. McKeown, 'Designing a predictable Internet backbone network,' presented at HotNets III, San Diego, California, November 2004.
- 'Definitions and terminology for automatically switched optical networks (ASON),' ITU-T Recommendation G.8081 (International Telecommunication Union, 2004).

## Cited By |
Alert me when this paper is cited |

OSA is able to provide readers links to articles that cite this paper by participating in CrossRef's Cited-By Linking service. CrossRef includes content from more than 3000 publishers and societies. In addition to listing OSA journal articles that cite this paper, citing articles from other participating publishers will also be listed.

OSA is a member of CrossRef.