Abstract

We present a heuristic for solving the discrete maximum-minimum (maxmin) rates for dense WDM- (DWDM-) based optical subnetworks. Discrete maxmin allocation is proposed here as the preferred way of assigning wavelengths to the flows found to be suitable for lightpath switching. The discrete maxmin optimality condition is shown to be a unifying principle underlying both the continuous maxmin and discrete maxmin optimality conditions. Among the many discrete maxmin solutions for each assignment problem, lexicographic optimal solutions can be argued to be the best in the true sense of maxmin. However, the problem of finding lexicographic optimal solutions is known to be NP-complete (NP is the class that a nondeterministic Turing machine accepts in polynomial time). The heuristic proposed here is tested against all possible networks such that |<i>Γ</i> + <i>Ω</i>| ≤ 10, where <i>Γ</i> and <i>Ω</i> are the set of links and the set of flows of the network, respectively. From 1,084,112 possible networks, the heuristic produces the exact lexicographic solutions with 99.8% probability. Furthermore, for 0.2% cases in which the solutions are nonoptimal, 99.8% of these solutions are within the minimal possible distance from the true lexicographic optimal solutions.

© 2002 Optical Society of America

PDF Article

References

  • View by:
  • |

  1. J. Bannister, J. Touch, A. Willner, and S. Suryaputra, “How many wavelenthgs do we really need? a study of the performance limits of packet over wavelengths,” Opt. Netw. Mag. (February 2000), pp. 17–28.
  2. S. Sarkar and L. Tassiulas, ”Fair allocation of discrete bandwidth layers in multicast networks,” in Infocom 2000: Proceedings of the Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies (Institute of Electrical and Electronics Engineers, New York, 2000), pp. 1491–1500.
  3. Wei K. Tsai and M. Iyer, “Constraint precedence in max–min fair rate allocation,” in Proceedings of the Conference on Computer Communications (Institute of Electrical and Electronics Engineers, New York, 2000), pp. 490–494.
  4. J. Ros and W. K. Tsai, “A general theory of constrained max–min rate allocation or multicast networks,” in Proceedings of the International Conference on Networks (Institute of Electrical and Electronics Engineers, New York, 2000), pp. 327–335.
  5. D. Basak, D. O. Awduche, J. Drake, and Y. Rekhter, “Multi-protocol lambda switching: issues in combining MPLS traffic engineering control with optical cross-connects,” Internet Draft (Internet Engineering Task Force, August 2000), <a href="http://www.globecom.net/ietf/draft/draft-awduche-mpls-te-optical-01.txt">http://www.globecom.net/ietf/draft/draft-awduche-mpls-te-optical-01.txt</a>.
  6. E. Gafni and D. Bertsekas, “Dynamic control of session input rates in communication networks,” IEEE Trans. Autom. Control AC29, 1009–1016 (1984).
  7. Y. Hou, H. Tzeng, and S. Panwar, “A generalized max–min rate allocation policy and its distributed implementation using the ABR flow control mechanism,” in Infocom 1998: Proceedings of the Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies (Institute of Electrical and Electronics Engineers, New York, 1998), pp. 1366–1375.
  8. Y. H. Long, T. K. Ho, A. B. Rad, and S. P. S. Lam, “A study of the generalised max–min fair rate allocation for ABR control in ATM,” Comput. Commun. 22, 1247-1259 (1999).
  9. J. Ros and Wei K. Tsai, “Zero-queue flow allocation protocol for DWDM networks,” Working Paper (Departement of Electrical and Computer Engineering, University of California, Irvine, Irvine, Calif. 92697).
  10. J. Ros and W. K. Tsai, ”A general theory of discrete max–min rate assignment,” Tech. Rep. (University of California—Irvine, Irvine, Calif., May, 2000). Available at <a href="http://www.eng.uci.edu/~netrol">http://www.eng.uci.edu/~netrol</a>.

Comput. Commun. (1)

Y. H. Long, T. K. Ho, A. B. Rad, and S. P. S. Lam, “A study of the generalised max–min fair rate allocation for ABR control in ATM,” Comput. Commun. 22, 1247-1259 (1999).

IEEE Trans. Autom. Control (1)

E. Gafni and D. Bertsekas, “Dynamic control of session input rates in communication networks,” IEEE Trans. Autom. Control AC29, 1009–1016 (1984).

Other (8)

Y. Hou, H. Tzeng, and S. Panwar, “A generalized max–min rate allocation policy and its distributed implementation using the ABR flow control mechanism,” in Infocom 1998: Proceedings of the Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies (Institute of Electrical and Electronics Engineers, New York, 1998), pp. 1366–1375.

J. Ros and Wei K. Tsai, “Zero-queue flow allocation protocol for DWDM networks,” Working Paper (Departement of Electrical and Computer Engineering, University of California, Irvine, Irvine, Calif. 92697).

J. Ros and W. K. Tsai, ”A general theory of discrete max–min rate assignment,” Tech. Rep. (University of California—Irvine, Irvine, Calif., May, 2000). Available at <a href="http://www.eng.uci.edu/~netrol">http://www.eng.uci.edu/~netrol</a>.

J. Bannister, J. Touch, A. Willner, and S. Suryaputra, “How many wavelenthgs do we really need? a study of the performance limits of packet over wavelengths,” Opt. Netw. Mag. (February 2000), pp. 17–28.

S. Sarkar and L. Tassiulas, ”Fair allocation of discrete bandwidth layers in multicast networks,” in Infocom 2000: Proceedings of the Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies (Institute of Electrical and Electronics Engineers, New York, 2000), pp. 1491–1500.

Wei K. Tsai and M. Iyer, “Constraint precedence in max–min fair rate allocation,” in Proceedings of the Conference on Computer Communications (Institute of Electrical and Electronics Engineers, New York, 2000), pp. 490–494.

J. Ros and W. K. Tsai, “A general theory of constrained max–min rate allocation or multicast networks,” in Proceedings of the International Conference on Networks (Institute of Electrical and Electronics Engineers, New York, 2000), pp. 327–335.

D. Basak, D. O. Awduche, J. Drake, and Y. Rekhter, “Multi-protocol lambda switching: issues in combining MPLS traffic engineering control with optical cross-connects,” Internet Draft (Internet Engineering Task Force, August 2000), <a href="http://www.globecom.net/ietf/draft/draft-awduche-mpls-te-optical-01.txt">http://www.globecom.net/ietf/draft/draft-awduche-mpls-te-optical-01.txt</a>.

Cited By

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