OSA's Digital Library

Journal of Optical Communications and Networking

Journal of Optical Communications and Networking

  • Editors: K. Bergman and V. Chan
  • Vol. 1, Iss. 3 — Aug. 1, 2009
  • pp: 222–234

Mixing Convergence and Deflection Strategies for Packet Routing in All-Optical Networks

D. Barth, P. Berthomé, D. Chiaroni, J. M. Fourneau, C. Laforest, and S. Vial  »View Author Affiliations

Journal of Optical Communications and Networking, Vol. 1, Issue 3, pp. 222-234 (2009)

View Full Text Article

Acrobat PDF (301 KB)

Browse Journals / Lookup Meetings

Browse by Journal and Year


Lookup Conference Papers

Close Browse Journals / Lookup Meetings

Article Tools



We present two routing algorithms based on deflection and convergence, which are able to provide high bandwidth and an ending guarantee for the end-to-end delay in a core network. We study the performance of these routing techniques by using simulations, and we prove the bounds on the delay.

© 2009 Optical Society of America

OCIS Codes
(060.1155) Fiber optics and optical communications : All-optical networks
(060.4251) Fiber optics and optical communications : Networks, assignment and routing algorithms
(060.4259) Fiber optics and optical communications : Networks, packet-switched

ToC Category:
Regular Papers

Original Manuscript: April 28, 2009
Manuscript Accepted: June 2, 2009
Published: July 28, 2009

D. Barth, P. Berthomé, D. Chiaroni, J. M. Fourneau, C. Laforest, and S. Vial, "Mixing Convergence and Deflection Strategies for Packet Routing in All-Optical Networks," J. Opt. Commun. Netw. 1, 222-234 (2009)

Sort:  Author  |  Year  |  Journal  |  Reset


  1. L. Dittman, C. Develder, D. Chiaroni, F. Neri, F. Callegati, W. Koerber, A. Stavdas, M. Renaud, A. Rafel, J. Sole-Pareta, W. Cerroni, N. Leligou, L. Dembeck, B. Mortensen, M. Pickavet, N. Le Sauze, M. Mahony, B. Berde, and G. Eilenberger, “The European IST project DAVID: a viable approach towards optical packet switching,” IEEE J. Sel. Areas Commun. , vol. 7, pp. 1026-1040, 2003. [CrossRef]
  2. P. Baran, “On distributed communication networks,” IEEE Trans. Commun. Syst. , vol. CS-12, pp. 1-9, 1964.
  3. Y. Ofek and M. Yung, “Principles for high speed network control: loss-less and deadlock-freeness, self-routing and a single buffer per link,” in Annu. ACM Symp. on Principles of Distributed Computing, Quebec City, Canada, 1990, pp. 161-175.
  4. J. C. Brassil and R. L. Cruz, “Bounds on maximum delay in networks with deflection routing,” IEEE Trans. Parallel Distrib. Syst. , vol. 6, no. 7, pp. 724-732, 1995. [CrossRef]
  5. A. Schuster, “Bounds and analysis techniques for greedy hot-potato routing,” in Optical Interconnections and Parallel Processing: The Interface, Norwell, MA: Kluwer Academic, 1997, pp. 284-354.
  6. D. Barth, P. Berthomé, and J. Cohen, “The Eulerian stretch of a digraph and the ending guarantee of a convergence routing,” J. Interconnect. Netw. (JOIN) , vol. 5, no. 2, pp. 93-109, 2004. [CrossRef]
  7. C. Laforest and S. Vial, “Short cut Eulerian routing of datagrams in all optical point-to-point networks,” in Proc. Int. Parallel and Distributed Processing Symp., IPDPS 2002, Abstracts and CD-ROM, Ft. Lauderdale, FL, Apr. 15-19, 2002, vol. 1, pp. 39-44.
  8. D. Barth, P. Berthomé, A. Borrero, J. Fourneau, C. Laforest, F. Quessette, and S. Vial, “Performance comparisons of Eulerian routing and deflection routing in a 2D-mesh all optical network,” presented at 15th European Simulation Multiconf., Prague, Czech Republic, June 6-9, 2001.
  9. C. Berge, Graphs and Hypergraphs, Amsterdam, North Holland, 1973.
  10. P. Ferguson and G. Huston, Quality of Service: Delivering QoS on the Internet and in Corporate Networks. New York, NY: Wiley, 1999.
  11. B. Hajek, “Bounds on evacuation time for deflection routing,” Distrib. Comput. , vol. 5, no. 1, pp. 1-6, 1991. [CrossRef]
  12. B. Yener, S. Matsoukas, and Y. Ofek, “Iterative approach to optimizing convergence routing priorities,” IEEE/ACM Trans. Netw. , vol. 5, no. 4, pp. 530-542, Aug. 1997.
  13. U. Feige and R. Krauthgamer, “Networks on which hot-potato routing does not livelock,” Distrib. Comput. , vol. 13, pp. 53-58, 2000. [CrossRef]
  14. U. Feige, “Observations on hot potato routing,” in 3rd Israel Symp. on the Theory of Computing and Systems, 1995. Proceedings, Tel Aviv, Israel, Jan. 4-61995, pp. 30-39.
  15. A. Symvonis, “A note on deflection routing on undirected graphs,” University of Sydney, Dept. of Computer Science, Tech. Rep. TR94-493, 1994.
  16. A. Mayer, Y. Ofek, and M. Yung, “Local fairness in general-topology networks with convergence routing,” in IEEE INFOCOM '95. Fourteenth Annu. Joint Conf. of the IEEE Computer and Communications Societies. Bringing Information to People. Proceedings, Boston, MA, Apr. 2-6, 1995, vol. 2, pp. 891-899.
  17. B. Yener, T. Boult, and Y. Ofek, “Hamiltonian decompositions of regular topology networks with convergence routing,” Columbia University, Computer Science Department, Tech. Rep. CUCS-011094, 1994.
  18. D. Barth, P. Berthomé, T. Czarchoski, F. J.-M., C. Laforest, and S. Vial, “A mixed deflection and convergence routing algorithm: design and performance,” in Euro-Par 2002 Parallel Processing, vol. 2400 of Lecture Notes in Computer Science, Berlin: Springer, 2002, pp. 767-774.
  19. S. Mneimneh, G. Damm, F. Verchère, and F. Quessette, “Minimum deflection routing in bufferless networks,” U.S. Patent Application 20040022240, Feb. 5, 2004.
  20. S. Mneimneh and F. Quessette, “Linear complexity algorithms for maximum advance deflection routing in some networks,” in 2006 Workshop on High Performance Switching and Routing, Poznan, Poland, 2006, pp. 1-7.
  21. D. Barth, P. Berthomé, C. Laforest, and S. Vial, “Some Eulerian parameters about performances of a convergence routing in the 2D-mesh network,” LRI, Tech. Rep. LRI-1346, Jan. 2003.
  22. P. Gravey, S. Gosselin, C. Guillemot, D. Chiaroni, N. Le Sauze, A. Jourdan, E. Dotaro, D. Barth, P. Berthomé, C. Laforest, S. Vial, T. Atmaca, G. Hébuterne, H. El Biaze, R. Laalaoua, E. Gangloff, and I. Kotuliak, “Multiservice optical network: main concepts and first achievements of the ROM program,” J. Lightwave Technol. , vol. 19, pp. 23-31, Jan. 2001. [CrossRef]
  23. A. Borrero, J.-M. Fourneau, and F. Quessette, “Packet selection in a deflection routing algorithm,” in Proc. of the 17th Int. Symp. on Computer and Information Sciences, Orlando, FL, Oct. 28-30, 2002, pp. 103-114.
  24. K. Watabe, T. Saito, N. Matsumoto, T. Tanemura, H. Imaizumi, A. A. Amin, M. Takenaka, Y. Nakano, and H. Morikawa, “80 gb/s multi-wavelength optical packet switching using PLZT switch,” in 11th International Conference on Optical Networking Design and Modeling (ONDM 2007), vol. 4534 of Lecture Notes in Computer Science, Berlin: Springer 2007, pp. 11-20.
  25. M. Veran and D. Potier, “QNAP-2: A Portable Environment for Queueing Network,” in Modelling Techniques and Tools for Performance Analysis. Amsterdam: North-Holland, 1985, pp. 25-63.
  26. D. Barth, J.-M. Fourneau, D. Nott, and D. Chiaroni, “Routing and QoS in an all-optical packet network,” in 2nd Int. Conf. on Broadband Networks, 2005. BroadNets 2005, Boston, MA, Oct. 7, 2005, vol. 2, pp. 1063-1072.
  27. D. Barth, J.-M. Fourneau, and D. Nott, “Two cycles routing and end to end delay bound in all optical network,” presented at Int. Conf. on Photonics in Switching 2008 (PS 2008), Sapporo, Japan, Aug. 4-7, 2008, poster session.
  28. D. Barth and N. Pires, “Robustesse du routage eulérien dans le réseau ROMEO,” Université de Versailles--St. Quentin, 2005, http://www.prism.uvsq.fr/rapports/2005/document_2005_87.doc.

Cited By

Alert me when this paper is cited

OSA is able to provide readers links to articles that cite this paper by participating in CrossRef's Cited-By Linking service. CrossRef includes content from more than 3000 publishers and societies. In addition to listing OSA journal articles that cite this paper, citing articles from other participating publishers will also be listed.

« Previous Article  |  Next Article »

OSA is a member of CrossRef.

CrossCheck Deposited