Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

We study the maximum throughput properties of dynamically reconfigurable optical network architectures having wavelength and port constraints. Using stability as the throughput performance metric, we outline the single-hop and multi-hop stability regions of the network. Our analysis of the stability regions is a generalization of the BvN decomposition technique that has been so effective at expressing any stabilizable rate matrix for input-queued switches as a convex combination of service configurations. We consider generalized decompositions for physical topologies with wavelength and port constraints. For the case of a single wavelength per optical fiber, we link the decomposition problem to a corresponding Routing and Wavelength Assignment (RWA) problem. We characterize the stability region of the reconfigurable network, employing both single-hop and multi-hop routing, in terms of the RWA problem applied to the same physical topology. We derive expressions for two geometric properties of the stability region: maximum stabilizable uniform arrival rate and maximum scaled doubly substochastic region. These geometric properties provide a measure of the performance gap between a network having a single wavelength per optical fiber and its wavelength-unconstrained version. They also provide a measure of the performance gap between algorithms employing single-hop versus multi-hop electronic routing in coordination with WDM reconfiguration.

REFERENCES

• 1: M. A. Marsan, E. Leonardi, M. Mellia, and F. Neri, "On the stability of isolated and interconnected input-queueing switches under multiclass traffic," IEEE Trans. Inf. Theory, vol. 45, no. 3, pp. 1167-1174, Mar. 2005.
• 2: G. Birkhoff, "Tres observaciones sobre el algebra lineal," Rev. Universidad Nacional de Tucuman, pp. 147-150, 1946.
• 3: Andrew Brzezinski , Eytan Modiano, Scheduling algorithms for throughput maximization in data networks, Massachusetts Institute of Technology, Cambridge, MA, 2007
• 4: A. Brzezinski and E. Modiano, "Dynamic reconfiguration and routing algorithms for IP-over-WDM networks with stochastic traffic," in Proc. IEEE INFOCOM, Miami, FL, Mar. 2005.
• 5: A. Brzezinski and E. Modiano, "Dynamic reconfiguration and routing algorithms for IP-over-WDM networks with stochastic traffic," J. Lightw. Technol., vol. 23, no. 10, pp. 3188-3205, Oct. 2005.
• 6: A. Brzezinski and E. Modiano, "Achieving 100% throughput in re-configurable optical networks," in Proc. IEEE INFOCOM High-Speed Netw. Workshop, Apr. 2006.
• 7: A. Brzezinski and E. Modiano, "RWA decompositions for optimal throughput in reconfigurable optical networks," in Proc. INFORMS Telecom, Mar. 2006.
• 8: C. S. Chang, W. J. Chen, and H. Y. Huang, "Birkhoff-von Neumann input buffered crossbar switches," in Proc. IEEE INFOCOM, 2000, pp. 1614-1623.
• 9: L. Chen and E. Modiano, "Efficient routing and wavelength assignment for reconfigurable WDM networks with wavelength converters," in Proc. IEEE INFOCOM, Apr. 2003.
• 10: L. Chen and E. Modiano, "Dynamic routing and wavelength assignment with optical bypass using ring embeddings," Opt. Switch. Netw., vol. 1, no. 1, pp. 35-49, Jan. 2005.
• 11: I. Chlamtac, A. Ganz, and G. Karmi, "Lightpath communications: An approach to high bandwidth optical WAN's," IEEE Trans. Commun., vol. 40, no. 8, pp. 1171-1182, Aug. 1992.
• 12: J. S. Choi, N. Golmie, F. Lapeyrere, F. Mouveaux, and D. Su, "A functional classification of routing and wavelength assignment schemes in DWDM networks: Static case," in Proc. OPNET, Jan. 2000, pp. 1109-1115.
• 13: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 14: A. Fumagalli and L. Valcarenghi, "IP restoration versus WDM protection: Is there an optimal choice?," IEEE Network, vol. 14, no. 6, pp. 34-41, Nov.-Dec. 2000.
• 15: Ori Gerstel , Galen Sasaki , Shay Kutten , Rajiv Ramaswami, Worst-case analysis of dynamic wavelength allocation in optical networks, IEEE/ACM Transactions on Networking (TON), v.7 n.6, p.833-846, Dec. 1999 [doi>10.1109/90.811449]
• 16: N. Ghani, S. Dixit, and T. Wang, "On IP-over-WDM integration," IEEE Commun. Mag., pp. 72-84, Mar. 2000.
• 17: K. Kar, D. Stiliadis, T. Lakshman, and L. Tassiulas, "Scheduling algorithms for optical packet fabrics," IEEE J. Sel. Areas Commun., vol. 21, no. 7, pp. 1143-1155, Sep. 2003.
• 18: R. Madan and D. Shah, "Capacity-delay scaling in arbitrary wireless networks," in Proc. Allerton Conf. Commun., Control, Comput., Sep. 2005.
• 19: J. E. Marsden and M. J. Hoffman, Elementary Classical Analysis, 2nd ed. San Francisco, CA: W. H. Freeman, 2000.
• 20: N. McKeown, A. Mekkittikul, V. Anantharam, and J. Walrand, "Achieving 100% throughput in an input-queued switch," IEEE Trans. Commun., vol. 47, no. 9, pp. 1260-1267, Aug. 1999.
• 21: B. Mukherjee, Optical Communication Networks. New York: Mc-Graw-Hill, 1997.
• 22: A. Narula-Tam, P. J. Lin, and E. Modiano, "Efficient routing and wavelength assignment for reconfigurable WDM networks," IEEE J. Sel. Areas Commun., vol. 20, no. 1, pp. 75-88, Jan. 2002.
• 23: C. Qiao, "Labeled optical burst switching for IP-over-WDM integration," IEEE Commun. Mag., pp. 104-114, Sep. 2000.
• 24: K. Ross, N. Bambos, K. Kumaran, I. Saniee, and I. Widjaja, "Dynamic scheduling of optical data bursts in time-domain wavelength interleaved networks," High Performance Interconnects, Aug. 2003.
• 25: K. Ross, N. Bambos, K. Kumaran, I. Saniee, and I. Widjaja, "Scheduling bursts in time-domain wavelength interleaved networks," IEEE J. Sel. Areas Commun., vol. 21, no. 11, pp. 1441-1451, Nov. 2003.
• 26: Poompat Saengudomlert , Eytan H. Modiano , Robert G. Gallager, Architectural study of high-speed networks with optical bypassing, Massachusetts Institute of Technology, 2002
• 27: Poompat Saengudomlert , Eytan H. Modiano , Robert G. Gallager, Dynamic wavelength assignment for WDM all-optical tree networks, IEEE/ACM Transactions on Networking (TON), v.13 n.4, p.895-905, August 2005 [doi>10.1109/TNET.2005.852875]
• 28: Poompat Saengudomlert , Eytan Modiano , Robert G. Gallager, On-line routing and wavelength assignment for dynamic traffic in WDM ring and torus networks, IEEE/ACM Transactions on Networking (TON), v.14 n.2, p.330-340, April 2006 [doi>10.1109/TNET.2006.872549]
• 29: L. Sahasrabuddhe, S. Ramamurthy, and B. Mukherjee, "Fault management in IP-over-WDM networks: WDM protection versus IP restoration," IEEE J. Sel. Areas Commun., vol. 20, no. 1, pp. 21-33, Jan. 2002.
• 30: A. Stolyar, "Maxweight scheduling in a generalized switch: State space collapse and workload minimization in heavy traffic," Ann. Appl. Probab., vol. 14, no. 1, pp. 1-53, Jan. 2004.
• 31: L. Tassiulas and A. Ephremides, "Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks," IEEE Trans. Automat. Contr., vol. 37, no. 12, pp. 1936-1948, Dec. 1992.
• 32: J. von Neumann, "A certain zero-sum two-person game equivalent to the optimal assignment problem," Contrib. Theory of Games, vol. 2, pp. 5-12, 1953.
• 33: J. Y. Wei, "Advances in the management and control of optical Internet," IEEE J. Sel. Areas Commun., vol. 20, no. 4, pp. 768-785, May 2002.
• 34: G. Weichenberg, V. W. S. Chan, and M. Medard, "On the capacity of optical networks: A framework for comparing different transport architectures," MIT LIDS, Tech. Rep. LIDS-P-2655, 2005.
• 35: G. Weichenberg, V. W. S. Chan, and M. Medard, "On the capacity of optical networks: A framework for comparing different transport architectures," in Proc. IEEE INFOCOM, Apr. 2006.
• 36: I. Widjaja, I. Saniee, R. Giles, and D. Mitra, "Light core and intelligent edge for a flexible, thin-layered and cost-effective optical transport network," IEEE Commun. Mag., vol. 41, no. 5, pp. S30-S36, May 2003.
• 37: C. Xin and C. Qiao, "A comparative study of OBS and OFS," in Proc. IEEE/OSA Optical Fiber Conf., 2001, pp. ThG7-1-ThG7-3.
• 38: Y. Yinghua, C. Assi, S. Dixit, and M. A. Ali, "A simple dynamic integrated provisioning/protection scheme in IP over WDM networks," IEEE Commun. Mag., vol. 39, no. 11, pp. 174-182, Nov. 2001.
• 39: M. Yoo, C. Qiao, and S. Dixit, "QoS performance of optical burst switching in IP-over-WDM networks," IEEE J. Sel. Areas Commun., vol. 18, no. 10, pp. 2062-2071, Oct. 2000.

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:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

  E. Data
  E.4 CODING AND INFORMATION THEORY

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Queueing theory

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
Birkhoff-von Neumann (BvN), IP-over-WDM, WDM reconfiguration, input-queueing, matrix decomposition, performance evaluation, queueing network, wavelength division multiplexing (WDM)