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

PDF Article

References

  • View by:
  • |
  • |
  • |

  1. 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.
  2. 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.
  3. W. Ben-Ameur and H. Kerivin, 'New economical virtual private networks,' Commun. ACM 44(6), 69-73 (2003).
  4. W. Ben-Ameur and H. Kerivin, 'Routing of uncertain demands,' Optimization Eng. 6, 283-313 (2005).
  5. 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.
  6. 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.
  7. 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).
  8. 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.
  9. 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.
  10. J. A. Fingerhut, S. Suri, and J. Turner, 'Designing least-cost nonblocking broadband networks,' J. Algorithms 22, 287-309 (1997).
  11. 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.
  12. 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.
  13. 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.
  14. 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.
  15. 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.
  16. 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.
  17. 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.
  18. D. Leung and W. D. Grover, 'Capacity planning of survivable mesh-based transport networks under demand uncertainty,' Photon. Netw. Commun. 10, 123-140 (2005).
  19. D. Mitra and R. A. Cieslak, 'Randomized parallel communications on an extension of the omega network,' J. Assoc. Comput. Mach. 32, 802-824 (1987).
  20. 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.
  21. 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).
  22. 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).
  23. 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.
  24. 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).
  25. L. G. Valiant, 'A scheme for fast parallel communication,' SIAM J. Comput. 11(2), 350-361 (1982).
  26. 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.
  27. 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.
  28. R. Zhang-Shen and N. McKeown, 'Designing a predictable Internet backbone network,' presented at HotNets III, San Diego, California, November 2004.
  29. 'Definitions and terminology for automatically switched optical networks (ASON),' ITU-T Recommendation G.8081 (International Telecommunication Union, 2004).

2005

W. Ben-Ameur and H. Kerivin, 'Routing of uncertain demands,' Optimization Eng. 6, 283-313 (2005).

D. Leung and W. D. Grover, 'Capacity planning of survivable mesh-based transport networks under demand uncertainty,' Photon. Netw. Commun. 10, 123-140 (2005).

2003

W. Ben-Ameur and H. Kerivin, 'New economical virtual private networks,' Commun. ACM 44(6), 69-73 (2003).

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).

2002

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).

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).

1997

J. A. Fingerhut, S. Suri, and J. Turner, 'Designing least-cost nonblocking broadband networks,' J. Algorithms 22, 287-309 (1997).

1987

D. Mitra and R. A. Cieslak, 'Randomized parallel communications on an extension of the omega network,' J. Assoc. Comput. Mach. 32, 802-824 (1987).

1982

L. G. Valiant, 'A scheme for fast parallel communication,' SIAM J. Comput. 11(2), 350-361 (1982).

Alicherry, M.

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).

Altin, A.

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.

Amaldi, E.

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.

Applegate, D.

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.

Ben-Ameur, W.

W. Ben-Ameur and H. Kerivin, 'Routing of uncertain demands,' Optimization Eng. 6, 283-313 (2005).

W. Ben-Ameur and H. Kerivin, 'New economical virtual private networks,' Commun. ACM 44(6), 69-73 (2003).

Chang, C.-S.

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.

Chekuri, C.

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.

Chuang, S.-T.

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.

Cieslak, R. A.

D. Mitra and R. A. Cieslak, 'Randomized parallel communications on an extension of the omega network,' J. Assoc. Comput. Mach. 32, 802-824 (1987).

Cohen, E.

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.

Duffield, N. G.

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).

Eisenbrand, F.

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.

Elwalid, A. I.

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.

Erlebach, T.

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.

Fingerhut, J. A.

J. A. Fingerhut, S. Suri, and J. Turner, 'Designing least-cost nonblocking broadband networks,' J. Algorithms 22, 287-309 (1997).

Goyal, P.

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).

Grandoni, F.

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.

Greenberg, A.

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).

Grover, W. D.

D. Leung and W. D. Grover, 'Capacity planning of survivable mesh-based transport networks under demand uncertainty,' Photon. Netw. Commun. 10, 123-140 (2005).

Gupta, A.

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.

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.

Horowitz, M.

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.

Hurkens, C. A. J.

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.

Italiano, G.

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.

Jou, Y.-S.

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.

Keijsper, J. C. M.

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.

Kerivin, H.

W. Ben-Ameur and H. Kerivin, 'Routing of uncertain demands,' Optimization Eng. 6, 283-313 (2005).

W. Ben-Ameur and H. Kerivin, 'New economical virtual private networks,' Commun. ACM 44(6), 69-73 (2003).

Keslassy, I.

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.

Kleinberg, J.

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.

Kodialam, M.

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.

Kumar, A.

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).

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.

Kumar, V.

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).

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).

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.

Lakshman, T. V.

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.

Lee, D.-S.

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.

Leighton, T.

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.

Leonardi, S.

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.

Leung, D.

D. Leung and W. D. Grover, 'Capacity planning of survivable mesh-based transport networks under demand uncertainty,' Photon. Netw. Commun. 10, 123-140 (2005).

McKeown, N.

R. Zhang-Shen and N. McKeown, 'Designing a predictable Internet backbone network,' presented at HotNets III, San Diego, California, November 2004.

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.

Miller, D.

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.

Mishra, P.

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).

Mitra, D.

D. Mitra and R. A. Cieslak, 'Randomized parallel communications on an extension of the omega network,' J. Assoc. Comput. Mach. 32, 802-824 (1987).

Nagesh, H.

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).

Oriolo, G.

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.

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.

Oswald, P.

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.

Pelotti, B.

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.

Pinar, M.

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.

Poosala, V.

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).

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.

Räcke, H.

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.

Ramakrishnan, K. K.

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).

Rao, S.

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.

Rastogi, R.

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).

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.

Roughgarden, T.

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.

Ruegg, M.

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.

Saha, D.

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).

Scutella, M. G.

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.

Sengupta, S.

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).

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).

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.

Shepherd, F. B.

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.

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.

Silberschatz, A.

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).

Solgaard, O.

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.

Stougie, L.

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.

Suri, S.

J. A. Fingerhut, S. Suri, and J. Turner, 'Designing least-cost nonblocking broadband networks,' J. Algorithms 22, 287-309 (1997).

Turner, J.

J. A. Fingerhut, S. Suri, and J. Turner, 'Designing least-cost nonblocking broadband networks,' J. Algorithms 22, 287-309 (1997).

Valiant, L. G.

L. G. Valiant, 'A scheme for fast parallel communication,' SIAM J. Comput. 11(2), 350-361 (1982).

van der Merwe, J. E.

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).

Widjaja, I.

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.

Winzer, P. J.

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.

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.

Yener, B.

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).

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.

Yu, K.

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.

Zhang-Shen, R.

R. Zhang-Shen and N. McKeown, 'Designing a predictable Internet backbone network,' presented at HotNets III, San Diego, California, November 2004.

Zirngibl, M.

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.

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.

Commun. ACM

W. Ben-Ameur and H. Kerivin, 'New economical virtual private networks,' Commun. ACM 44(6), 69-73 (2003).

IEEE Commun. Mag.

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).

IEEE/ACM Trans. Netw.

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).

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).

J. Algorithms

J. A. Fingerhut, S. Suri, and J. Turner, 'Designing least-cost nonblocking broadband networks,' J. Algorithms 22, 287-309 (1997).

J. Assoc. Comput. Mach.

D. Mitra and R. A. Cieslak, 'Randomized parallel communications on an extension of the omega network,' J. Assoc. Comput. Mach. 32, 802-824 (1987).

Optimization Eng.

W. Ben-Ameur and H. Kerivin, 'Routing of uncertain demands,' Optimization Eng. 6, 283-313 (2005).

Photon. Netw. Commun.

D. Leung and W. D. Grover, 'Capacity planning of survivable mesh-based transport networks under demand uncertainty,' Photon. Netw. Commun. 10, 123-140 (2005).

SIAM J. Comput.

L. G. Valiant, 'A scheme for fast parallel communication,' SIAM J. Comput. 11(2), 350-361 (1982).

Other

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).

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).

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.

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.

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.

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.

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.

Cited By

OSA participates in CrossRef's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.

Alert me when this article is cited.