Complexity of wavelength assignment in optical network optimization

ABSTRACT

We study the complexity of a set of design problems for optical networks. Under wavelength division multiplexing (WDM) technology, demands sharing a common fiber are transported on distinct wavelengths. Multiple fibers may be deployed on a physical link.

Our basic goal is to design networks of minimum cost, minimum congestion and maximum throughput. This translates to three variants in the design objectives: 1) MIN-SUMFIBER: minimizing the total cost of fibers deployed to carry all demands; 2) MIN-MAXFIBER: minimizing the maximum number of fibers per link to carry all demands; and 3) MAX-THROUGHPUT: maximizing the carried demands using a given set of fibers.

We also have two variants in the design constraints: 1) CHOOSEROUTE: Here we need to specify both a routing path and a wavelength for each demand; 2) FIXEDROUTE: Here we are given demand routes and we need to specify wavelengths only. The FIXEDROUTE variant allows us to study wavelength assignment in isolation.

Combining these variants, we have six design problems. Previously we have shown that general instances of the problems MIN-SUMFIBER-CHOOSEROUTE and MIN-MAXFIBER-FIXEDROUTE have no constant-approximation algorithms. In this paper, we prove that a similar statement holds for all four other problems. Our main result shows that MIN-SUMFIBER-FIXEDROUTE cannot be approximated within any constant factor unless NP-hard problems have efficient algorithms. This, together with the previous hardness result of MIN-MAXFIBER-FIXEDROUTE, shows that the problem of wavelength assignment is inherently hard by itself.

We also study the complexity of problems that arise when multiple demands can be time-multiplexed onto a single wavelength (as in time-domain wavelength interleaved networking (TWIN) networks) and when wavelength converters can be placed along the path of a demand.

REFERENCES

• 1: M. Andrews and L. Zhang, "Wavelength assignment in optical networks with fixed fiber capacity," in Proc. 31st ICALP, Turke, Finland, Jul. 12-16, 2004, pp. 134-145.
• 2: M. Andrews and L. Zhang, "Bounds on fiber minimization in optical networks with fixed fiber capacity," in Proc. IEEE INFOCOM'05, Miami, FL, Mar. 13-17, 2005, pp. 409-419.
• 3: Indra Widjaja , Iraj Saniee, Simplified layering and flexible bandwidth with TWIN, Proceedings of the ACM SIGCOMM workshop on Future directions in network architecture, August 30-30, 2004, Portland, Oregon, USA [doi>10.1145/1016707.1016710]
• 4: K. Kumaran, C. J. Nuzman, and I. Widjaja, "Wavelength assignment for partially transparent networks with reach constraints," J. Opt. Netw., vol. 2, no. 8, pp. 285-302, 2003.
• 5: S. Antonakopoulos and L. Zhang, "Heuristics for fiber installation in optical network optimization," in Proc. IEEE GLOBECOM, Washington, DC, Nov. 26-30, 2007, pp. 2342-2347.
• 6: Matthew Andrews , Lisa Zhang, Hardness of the undirected edge-disjoint paths problem, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060632]
• 7: Matthew Andrews , Lisa Zhang, Hardness of the undirected congestion minimization problem, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060633]
• 8: Uriel Feige , Joe Kilian, Zero Knowledge and the Chromatic Number, Proceedings of the 11th Annual IEEE Conference on Computational Complexity, p.278, May 24-27, 1996
• 9: Rajiv Ramaswami , Kumar N. Sivarajan, Routing and wavelength assignment in all-optical networks, IEEE/ACM Transactions on Networking (TON), v.3 n.5, p.489-500, Oct. 1995 [doi>10.1109/90.469957]
• 10: Alok Aggarwal , Amotz Bar-Noy , Don Coppersmith , Rajiv Ramaswami , Baruch Schieber , Madhu Sudan, Efficient routing and scheduling algorithms for optical networks, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.412-423, January 23-25, 1994, Arlington, Virginia, United States
• 11: D. Banerjee and B. Mukherjee, "A practical approach for routing and wavelength assignment in large wavelength-routed optical networks," IEEE J. Sel. Areas Commun., vol. 14, no. 5, pp. 903-908, Jun. 1996.
• 12: Ioannis Caragiannis , Afonso Ferreira , Christos Kaklamanis , Stephane Perennes , Hervé Rivano, Fractional Path Coloring with Applications to WDM Networks, Proceedings of the 28th International Colloquium on Automata, Languages and Programming,, p.732-743, July 08-12, 2001
• 13: Prabhakar Raghavan , Eli Upfal, Efficient routing in all-optical networks, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.134-143, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195119]
• 14: Mihalis Yannakakis , Fanica Gavril, The maximum k-colorable subgraph problem for chordal graphs, Information Processing Letters, v.24 n.2, p.133-137, January 1987 [doi>10.1016/0020-0190(87)90107-4]
• 15: P. Fishburn, Interval Orders and Interval Graphs. New York: Wiley, 1985.
• 16: Vijay Kumar, Approximating Circular Arc Colouring and Bandwidth Allocation in All-Optical Ring Networks, Proceedings of the International Workshop on Approximation Algorithms for Combinatorial Optimization, p.147-158, July 18-19, 1998
• 17: Gordon Wilfong , Peter Winkler, Ring routing and wavelength translation, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.333-341, January 25-27, 1998, San Francisco, California, United States
• 18: C. Nomikos, A. Pagourtzis, and S. Zachos, "Minimizing request blocking in all-optical rings," in Proc. IEEE INFOCOM'03, San Francisco, CA, Mar. 30-Apr. 3, 2003.
• 19: P. J. Wan and L. Liu, "Maximal throughput wavelength-routed optical networks," DIMACS Ser. Discrete Math. Theor. Comput. Sci., vol. 46, pp. 15-26, 1998.
• 20: M. Mihail , C. Kaklamanis , Satish Rao, Efficient access to optical bandwidth, Proceedings of the 36th Annual Symposium on Foundations of Computer Science, p.548, October 23-25, 1995
• 21: Vijay Kumar , Eric J. Schwabe, Improved access to optical bandwidth in trees, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.437-444, January 05-07, 1997, New Orleans, Louisiana, United States
• 22: Thomas Erlebach , Klaus Jansen , Christos Kaklamanis , Milena Mihail , Pino Persiano, Optimal wavelength routing on directed fiber trees, Theoretical Computer Science, v.221 n.1-2, p.119-137, June 28, 1999 [doi>10.1016/S0304-3975(99)00029-8]
• 23: Thomas Erlebach , Klaus Jansen, The Maximum Edge-Disjoint Paths Problem in Bidirected Trees, SIAM Journal on Discrete Mathematics, v.14 n.3, p.326-355, 2001 [doi>10.1137/S0895480199361259]
• 24: Arun K. Somani , Mani Mina , Ling Li, On trading wavelengths with fibers: a cost-performance based study, IEEE/ACM Transactions on Networking (TON), v.12 n.5, p.944-951, October 2004 [doi>10.1109/TNET.2004.836130]
• 25: Peter Winkler , Lisa Zhang, Wavelength assignment and generalized interval graph coloring, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 26: Christos Nomikos , Aris Pagourtzis , Stathis Zachos, Routing and path multicoloring, Information Processing Letters, v.80 n.5, p.249-256, December 15, 2002 [doi>10.1016/S0020-0190(01)00167-3]
• 27: C. Chekuri, M. Mydlarz, and F. B. Shepherd, "Multicommodity demand flow in a tree," in Proc. 30th ICALP, Eindhoven, The Netherlands, Jun. 30-Jul. 4, 2003, pp. 410-425.
• 28: T. Erlebach, A. Pagourtzis, K. Potika, and S. Stefanakos, "Resource allocation problems in multifiber WDM tree networks," in Proc. 29th Int. Workshop Graph Theor. Concepts in Comput. Sci., Elspect, The Netherlands, Jun. 19-21, 2003, pp. 218-229.
• 29: B. Shepherd and A. Vetta, "Lighting fibers in a dark network," IEEE J. Sel. Areas Commun., vol. 22, no. 9, pp. 1583-1588, Nov. 2004.
• 30: John Kleinberg , Amit Kumar, Wavelength conversion in optical networks, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.566-575, January 17-19, 1999, Baltimore, Maryland, United States
• 31: X. Jia, D. Du, X. Hu, H. Huang, and D. Li, "Placement of wavelength converters for minimal wavelength usage in WDM networks," in Proc. IEEE INFOCOM'02, New York, Jun. 23-27, 2002, pp. 1425-1431.
• 32: S. Fortune, W. Sweldens, and L. Zhang, "Line system design for DWDM networks," in Proc. 11th Int. Telecommun. Netw. Strategy Planning Symp. (Networks), Vienna, Austria, 2004.
• 33: E. Anshelevich and L. Zhang, "Path decomposition under a new cost metric," in Proc. 12th Annu. ESA, Bergen, Norway, Sep. 14-17, 2004, pp. 28-39.
• 34: A. Koster and A. Zymolka, "Minimum converter wavelength assignment in all-optical networks," Konrad-Zuse-Zentrum fur Informationstechnik Berlin, Berlin-Dahlem, Germany, Tech. Rep. ZIB-Report 03-45, 2003.
• 35: Matthew Andrews , Julia Chuzhoy , Lisa Zhang, Hardness of the Undirected Edge-Disjoint Paths Problem with Congestion, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.226-244, October 23-25, 2005 [doi>10.1109/SFCS.2005.41]
• 36: J. Håstad , S. Khot, Query Efficient PCPs with Perfect Completeness, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.610, October 14-17, 2001
• 37: S. Khot, Improved Inapproximability Results for MaxClique, Chromatic Number and Approximate Graph Coloring, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.600, October 14-17, 2001
• 38: V. Guruswami and K. Talwar, "Hardness of low congestion routing in undirected graphs," Elec. Colloq. Comput. Complexity, vol. 13, 2006.
• 39: Martin Raab , Angelika Steger, "Balls into Bins" - A Simple and Tight Analysis, Proceedings of the Second International Workshop on Randomization and Approximation Techniques in Computer Science, p.159-170, October 08-10, 1998
• 40: B. Awerbuch , Y. Azar, Buy-at-bulk network design, Proceedings of the 38th Annual Symposium on Foundations of Computer Science, p.542, October 19-22, 1997
• 41: Y. Bartal, Probabilistic approximation of metric spaces and its algorithmic applications, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.184, October 14-16, 1996
• 42: Yair Bartal, On approximating arbitrary metrices by tree metrics, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.161-168, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276725]
• 43: Jittat Fakcharoenphol , Satish Rao , Kunal Talwar, A tight bound on approximating arbitrary metrics by tree metrics, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780608]
• 44: M. Garey, D. Johnson, G. Miller, and C. Papadimitriou, "The complexity of coloring circular arcs and chords," SIAM J. Algorithms Discrete Math., vol. 1, no. 2, pp. 216-227, 1980.
• 45: Thomas Erlebach , Klaus Jansen, The complexity of path coloring and call scheduling, Theoretical Computer Science, v.255 n.1-2, p.33-50, March 28, 2001 [doi>10.1016/S0304-3975(99)00152-8]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
          Subjects: Network management
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation

General Terms:
Algorithms, Design, Performance

Keywords:
approximation algorithms, hardness of approximation, optical networking, routing and wavelength assignment