Island hopping and path colouring with applications to WDM network design

ABSTRACT

Wavelength division multiplexed (WDM) optical communication offers the advantages of increased capacity and decreased latency for signals (traffic) carried across such networks. The devices used for "switching", however, force additional constraints on the mathematical design of such networks. In this paper we explore two such constaints: (i) optical lightpaths must be assigned individual wavelengths and (ii) sometimes lightpaths must unavoidably go through an optical-electronic-optical (OEO) conversion by means of an expensive piece of equipment called an optical transponder. We term the graph theoretical problems related to these constraints path colouring and island hopping. We present a range of upper and lower bounds for these problems. In particular, we extend the work of Winkler and Zhang (2003) and Anshelevich and Zhang (2004).

REFERENCES

• 1: Alok Aggarwal , Amotz Bar-Noy , Don Coppersmith , Rajiv Ramaswami , Baruch Schieber , Madhu Sudan, Efficient routing in optical networks, Journal of the ACM (JACM), v.43 n.6, p.973-1001, Nov. 1996 [doi>10.1145/235809.235812]
• 2: C. Aggarwal and J. Orlin, On multi-route maximum flows in networks, Networks, 39 (2002), pp. 43--52.
• 3: Ajit Agrawal , Philip Klein , R. Ravi, When Trees Collide: An Approximation Algorithm for theGeneralized Steiner Problem on Networks, SIAM Journal on Computing, v.24 n.3, p.440-456, June 1995 [doi>10.1137/S0097539792236237]
• 4: M. Andrews and L. Zhang, Wavelength assignment in optical networks with fixed fiber capacity., in ICALP, 2004, pp. 134--145.
• 5: M. Andrews and L. Zhang, Bounds on fiber minimization in optical networks., in INFOCOM, 2005.
• 6: E. Anshelevich and L. Zhang, Path decomposition under a new cost measure with applications to optical network design., in ESA, 2004, pp. 28--39.
• 7: D. Barnette, Trees in polyhedral graphs., Canadian Journal of Mathematics, 18 (1966), pp. 731--736.
• 8: S. Baum and L. E. Trotter Jr., Integer rounding and polyhedral decomposition for totally unimodular systems., Optimization and Operations Research, (1978), pp. 15--23.
• 9: Cristina Bazgan , Miklos Santha , Zsolt Tuza, On the approximation of finding a(nother) hamiltonian cycle in cubic hamiltonian graphs, Journal of Algorithms, v.31 n.1, p.249-268, April 1999 [doi>10.1006/jagm.1998.0998]
• 10: B. Beauquier, J.-C. Bermond, L. Gargano, P. Hell, S. Perennes, and U. Vaccaro, Graph problems arising from wavelength-routing in all-optical networks, in WOCS, 1997.
• 11: 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
• 12: C. Chekuri, P. Claisse, R. Essiambre, S. Fortune, D. Kilper, W. Lee, K. Nithi, I. Saniee, B. Shepherd, C. White, and G. Wilfong., Design tools for transparent optical networks., Bell Labs Technical Journal.
• 13: C. Chekuri, P. Claisse, R. Essiambre, S. Fortune, D. Kilper, K. Nithi, W. Lee, I. Saniee, B. Shepherd, G. Wilfong, C. White, and L. Zhang, Design tools for transparent optical networks, Bell Labs Technical Journal, 11 (2006), pp. 129--143.
• 14: L.-W. Chen and E. Modiano, Efficient routing and wavelength assignment for reconfigurable WDM networks with wavelength converters., in INFOCOM, 2003.
• 15: T. Erlebach, A. Pagourtzis, K. Potika, and S. Stefanakos, Resource allocation problems in multifiber WDM tree networks, in WG, 2003, pp. 218--229.
• 16: S. Fortune, J. E. Hopcroft, and J. Wyllie, The directed subgraph homeomorphism problem., Theor. Comput. Sci., 10 (1980), pp. 111--121.
• 17: S. Fortune, W. Sweldens, and L. Zhang, Line system design for DWDM networks., in Networks 2004, 2004, pp. 315--320.
• 18: Martin Fürer , Balaji Raghavachari, Approximating the minimum-degree Steiner tree to within one of optimal, Journal of Algorithms, v.17 n.3, p.409-423, Nov. 1994
• 19: Michel X. Goemans , David P. Williamson, A General Approximation Technique for Constrained Forest Problems, SIAM Journal on Computing, v.24 n.2, p.296-317, April 1995 [doi>10.1137/S0097539793242618]
• 20: R. Hassin, R. Ravi, and F. S. Salman, Approximation algorithms for a capacitated network design problem., Algorithmica, 38 (2003), pp. 417--431.
• 21: William Hesse, Directed graphs requiring large numbers of shortcuts, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 22: A. Hoffman, Some recent applications of the theory of linear inequalities to extremal combinatorial analysis, in Combinatorial Analysis (Proceedings of Symposia in Applied Mathematics, Volume X(R. Bellman and M. Hall, Jr, eds.), Providence, R. I., 1960, American Mathematical Society, pp. 113--127.
• 23: X. Jia, D.-Z. Du, X.-D. Hu, H. Huang, and D. Li, Placement of wavelength converters for minimal wavelength usage in wdm networks., in INFOCOM, 2002.
• 24: Ralf Klasing, Methods and Problems of Wavelength-Routing in All-Optical Networks, University of Warwick, Coventry, UK, 1998
• 25: Jon Kleinberg , Amit Kumar, Wavelength conversion in optical networks, Journal of Algorithms, v.38 n.1, p.25-50, Jan. 2001 [doi>10.1006/jagm.2000.1137]
• 26: J. Könemann , R. Ravi, A Matter of Degree: Improved Approximation Algorithms for Degree-Bounded Minimum Spanning Trees, SIAM Journal on Computing, v.31 n.6, p.1783-1793, 2002 [doi>10.1137/S009753970036917X]
• 27: 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
• 28: V. Kumar and A. Rudra, Approximation algorithms for wavelength assignment., in FSTTCS, 2005, pp. 152--163.
• 29: 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
• 30: E. Lowe, Performance and dimensioning of optical transport networks, PhD thesis, University of Essex, 1995.
• 31: E. Lowe, B. Shepherd, and N. Walker, Routing and configuration of static path optical transport networks, IEE Electronic Letters, 32 (1996), pp. 1913--1914.
• 32: W. Mader., A reduction method for edge-connectivity in graphs., Annals of Discrete Mathematics 3, 22 (1978), pp. 145--164.
• 33: M. Mihail , C. Kaklamanis , Satish Rao, Efficient access to optical bandwidth, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.548, October 23-25, 1995
• 34: 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]
• 35: Ran Raz , Shmuel Safra, A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.475-484, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258641]
• 36: Alexander Schrijver, Theory of linear and integer programming, John Wiley & Sons, Inc., New York, NY, 1986
• 37: B. Shepherd and A. Vetta., Lighting fibers in a dark network., Journal on Selected Areas in Communication, 22 (2004), pp. 1583--1588.
• 38: Thomas E. Stern , Krishna Bala, Multiwavelength Optical Networks: A Layered Approach, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 39: Mikkel Thorup, On Shortcutting Digraphs, Proceedings of the 18th International Workshop on Graph-Theoretic Concepts in Computer Science, p.205-211, June 19-20, 1992
• 40: T. Tutte, A theorem on planar graphs., Trans. Amer. Math. Soc., 82 (1956), pp. 99--116.
• 41: 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
• 42: 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