Competitive analysis of online traffic grooming in WDM rings

ABSTRACT

This paper addresses the problem of traffic grooming in wavelength-division multiplexing (WDM) rings where connection requests arrive online. Each request specifies a pair of nodes that wish to communicate and also the desired bandwidth of this connection. If the request is to be satisfied, it must be allocated to one or more wavelengths with sufficient remaining capacity. We consider three distinct profit models specifying the profit associated with satisfying a connection request. We give results on offline and online algorithms for each of the three profit models. We use the paradigm of competitive analysis to theoretically analyze the quality of our online algorithms. Finally, experimental results are given to provide insight into the performance of these algorithms in practice.

REFERENCES

• 1: A. L. Chiu and E. H. Modiano, "Traffic grooming algorithms for reducing electronic multiplexing costs in WDM ring networks," J. Lightw. Technol., vol. 18, no. 1, pp. 2-12, Jan. 2000.
• 2: Rudra Dutta , George N. Rouskas, On optimal traffic grooming in WDM rings, Proceedings of the 2001 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.164-174, June 2001, Cambridge, Massachusetts, United States
• 3: J.-Q. Hu, "Traffic grooming in wavelength-division-multiplexing ring networks: A linear programming solution," J. Opt. Netw., vol. 1, no. 11, pp. 397-408, Oct. 2002.
• 4: C. Zhao and J. Q. Hu, "Traffic grooming for WDM rings with dynamic traffic," manuscript, 2003.
• 5: Rudra Dutta , Shu Huang , George N. Rouskas, Traffic grooming in path, star, and tree networks: complexity, bounds, and algorithms, Proceedings of the 2003 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 11-14, 2003, San Diego, CA, USA
• 6: Farid Farahmandz , Xiaodong Huangy , Jason P. Jue, Efficient Online Traffic Grooming Algorithms in WDM Mesh Networks with Drop-and-Continue Node Architecture, Proceedings of the First International Conference on Broadband Networks, p.180-189, October 25-29, 2004 [doi>10.1109/BROADNETS.2004.37]
• 7: S. Huang and R. Dutta, "Research problems in dynamic traffic grooming in optical networks," in Proc. 1st Int. Workshop on Traffic Grooming, San Jose, CA, Oct. 2004.
• 8: H. Zhu, H. Zang, K. Zhu, and B. Mukherjee, "Dynamic traffic grooming in WDM mesh networks using a novel graph model," Opt. Netw. Mag., vol. 4, no. 3, pp. 65-75, May/Jun. 2003.
• 9: G. Maier, A. Pattavina, S. D. Patre, and M. Martinelli, "Optical network survivability: Protection techniques in the WDM layer," Photon. Netw. Commun., vol. 4, no. 3/4, pp. 251-269, 2002.
• 10: Yair Bartal , Stefano Leonardi, On-line routing in all-optical networks, Theoretical Computer Science, v.221 n.1-2, p.19-39, June 28, 1999 [doi>10.1016/S0304-3975(99)00025-0]
• 11: B. Awerbuch, Y. Azar, A. Fiat, S. Leonardi, and A. Rosen, "On-line competitive algorithms for call admission in optical networks," Algorithmica vol. 31, no. 1, pp. 29-43, 2001 [Online]. Available: citeseer. ist.psu.edu/article/awerbuch96line.html
• 12: C. Law and K.-Y. Siu, "On-line routing and wavelength assignment in single-hub WDM rings," IEEE J. Sel. Areas Commun., vol. 18, no. 10, pp. 2111-2122, Oct. 2000.
• 13: A. Tuchscherer, "Dynamical configuration of transparent optical telecommunication networks," in Oper. Res. Proc., 2004, pp. 25-32.
• 14: J. Li, C. Qiao, and D. Xu, "Maximizing throughput for optical burst switching networks," in Proc. IEEE INFOCOM, 2004, pp. 1853-1863.
• 15: Baruch Awerbuch , Yair Bartal , Amos Fiat , Adi Rosén, Competitive non-preemptive call control, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.312-320, January 23-25, 1994, Arlington, Virginia, United States
• 16: B. Awerbuch , Y. Azar , S. Plotkin, Throughput-competitive on-line routing, Proceedings of the Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science, p.32-40, November 03-05, 1993 [doi>10.1109/SFCS.1993.366884]
• 17: Allan Borodin , Ran El-Yaniv, Online computation and competitive analysis, Cambridge University Press, New York, NY, 1998
• 18: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 19: Bala Kalyanasundaram , Kirk R. Pruhs, An optimal deterministic algorithm for online b-matching, Theoretical Computer Science, v.233 n.1-2, p.319-325, Feb. 28 2000 [doi>10.1016/S0304-3975(99)00140-1]
• 20: Aranyak Mehta , Amin Saberi , Umesh Vazirani , Vijay Vazirani, AdWords and Generalized On-line Matching, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.264-273, October 23-25, 2005 [doi>10.1109/SFCS.2005.12]
• 21: N. Buchbinder, K. Jain, and J. Naor, "Online primal-dual algorithms for maximizing ad-auction revenue," manuscript, 2006.
• 22: Michael R. Garey , David S. Johnson, Computers and Intractability; A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1990
• 23: Srinivasan Ramasubramanian , Arun K. Somani, Analysis of optical networks with heterogeneous grooming architectures, IEEE/ACM Transactions on Networking (TON), v.12 n.5, p.931-943, October 2004 [doi>10.1109/TNET.2004.836094]
• 24: R. M. Karp , U. V. Vazirani , V. V. Vazirani, An optimal algorithm for on-line bipartite matching, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.352-358, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100262]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: High-speed (e.g., FDDI, fiber channel, ATM)

Additional Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Online computation

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Experimental design

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis

General Terms:
Algorithms, Design, Experimentation, Performance, Theory

Keywords:
competitive analysis, online algorithms, optical networks, wavelength-division multiplexing (WDM) rings