OSA's Digital Library

Journal of Optical Communications and Networking

Journal of Optical Communications and Networking

  • Editor: Richard A. Linke
  • Vol. 4, Iss. 3 — Mar. 4, 2005
  • pp: 157–175

Percolation routing in a three-dimensional multicomputer network topology using optical interconnection

Ekpe Okorafor and Mi Lu  »View Author Affiliations

Journal of Optical Networking, Vol. 4, Issue 3, pp. 157-175 (2005)

View Full Text Article

Acrobat PDF (295 KB)

Browse Journals / Lookup Meetings

Browse by Journal and Year


Lookup Conference Papers

Close Browse Journals / Lookup Meetings

Article Tools



We investigate the network communication behavior of a three-dimensional (3D) multicomputer system using optical interconnection in which faulty nodes are left in place, a concept called "fail-in-place." We call this the percolation problem in which various amounts of missing nodes fixed in position in the network may have a dramatic effect on the network's ability to transport data effectively. As the number of failed nodes increases, data have to be rerouted through intermediate nodes creating potential "hot spots." These hot spots become the bottleneck that degrades performance. The ability to absorb rerouted data without ejecting it from the network is critical in massively parallel computing systems. Optical technology is a promising solution for internode communication with extraordinarily quick response time supporting enormous bandwidth. To adopt it in multiprocessor systems, efficient routing techniques are needed. We adapt self-routing strategies for all-optical packet routing in 3D mesh networks and investigate the percolation properties. To achieve percolation routing, we incorporate the features inherent in optics to achieve decoding and routing capability in real time. The objective is to develop a dynamic communication environment that adapts and evolves with a high density of missing units or nodes, and by employing analytical, experimental, and simulation methods, show that optical interconnection in a dense 3D system reduces considerably this percolation problem.

© 2004 Optical Society of America

OCIS Codes
(060.4510) Fiber optics and optical communications : Optical communications
(200.4650) Optics in computing : Optical interconnects

ToC Category:

Original Manuscript: January 3, 2005
Revised Manuscript: December 26, 2004
Published: March 4, 2005

Ekpe Okorafor and Mi Lu, "Percolation routing in a three-dimensional multicomputer network topology using optical interconnection," J. Opt. Netw. 4, 157-175 (2005)

Sort:  Journal  |  Reset


  1. N. R. Adiga and researchers at IBM and the Lawrence Livermore National Laboratory, "An overview of the BlueGene∕L supercomputer," in Proceedings of the IEEE/ACM SC2002 Conference (IEEE, 2002).
  2. Cray Research Incorporated, Cray T3D System Architecture Overview (September 1993).
  3. Intel Corporation,Paragon XP∕S Product Overview (1991).
  4. W. J. Dally, "The J-machine: system support for actors," Actors: Knowledge-Based Concurrent Computing, Hewitt and Agha, eds. (MIT Press, 1989).
  5. R. K. Koeninger, M. Furtney, and M. Walker, "A shared memory MPP from Cray Research," Dig. Tech. J. 6(2), 8-21 (1994).
  6. A. V. Krishnamoorthy and D. A. B. Miller, "Firehose architectures for free-space optically interconnected VLSI circuits," J. Parallel Distrib. Comput. 41(1), 109-114 (1997).
  7. P. J. Marchand, A. V. Krishnamoorthy, G. I. Yayla, S. C. Esener, and U. Efron, "Optically augmented 3-D computer: system technology and architecture," J. Parallel Distrib. Comput., Special Issue on Optical Interconnects, 41(1), 20-35 (1997).
  8. G. A. Betzos and P. A. Mitkas, "Performance evaluation of massively parallel processing architectures with three-dimensional optical interconnections, Appl. Opt. 37, 315-25 (1998).
  9. J. W. Goodman, F. J. Leonberger, S. C. Kung, and R. A. Athale, "Optical interconnections for VLSI systems," Proc. IEEE 72, 850-66 (1984).
  10. C. B. Stunkel, "Commercial MPP networks: time for optics?" in Proceedings of the Fourth International Conference on Massively Parallel Processing Using Optical Interconnections (1997), pp. 90-95.
  11. R. Germann, H. W. M. Salemink, R. Beyeler, G. L. Bona, F. Horst, and B. J. Offrein, "Silicon-oxynitride layers for optical waveguide applications," J. Electrochem. Soc. 147, 2237-2241 (2000).
  12. G. L. Bona, R. Germann, F. Horst, B. J. Offrein, and H. W. M. Salemink, "Versatile silicon-oxynitride planar lightwave circuits for interconnect applications," in Proceedings of the 6th International Conference on Parallel Interconnects (IEEE, Los Alamitos, 2000), pp. 145-148.
  13. D. A. B. Miller, "Rationale and challenges for optical interconnects to electronic chips," Proc. IEEE 88, 728-749 (2000).
  14. S. Esener and P. Marchand, "Present and future needs of free-space optical interconnects," in IPDPS Workshop (2000), pp. 1104-1109.
  15. D. J. Goodwill, "Free-space optical interconnect for terabit network elements," in Proceedings of Optics in Computing Conference (1999).
  16. B. F. Almohammad and B. Bose, "Fault-tolerant communication algorithms in toroidal networks," IEEE Trans. Parallel Distrib. Syst. 10, 976-983 (1999).
  17. J. Wu, "A fault-tolerant adaptive and minimal routing approach in 3D meshes," IEEE Trans. Parallel Distrib. Syst. 11, 149-159 (2000).
  18. Z. Jiang and J. Wu, "A limited-global fault information model for dynamic routing in 3D meshes," in Second IEEE International Symposium on Network Computing and Applications (IEEE, 2003), pp. 333-340.
  19. H. Shen, F. Chin, and Y. Pan, "Efficient fault-tolerant routing in multi-hop optical WDM networks," IEEE Trans. Parallel Distrib. Syst. 10, 1012-1025 (1999).
  20. C. Ho and L. Stockmeyer, "A new approach to fault-tolerant wormhole routing for mesh-connected parallel computers," IEEE Trans. Comput. 53, 427-438 (2004).
  21. I. Glesk, K. I. Kang, and P. R. Prucnal, "All-optical address recognition and self-routing in a 250 Gbit∕s packet switched," Electron. Lett. 30, 1322-1323 (1994).
  22. A. E. Willne, D. Gurkan, A. B. Sahin, J. E. McGeehan, and M. C. Hauer, "All-optical address recognition for optically-assisted routing in next-generation optical networks," IEEE Commun. Mag. 41(5), S38-S44 (2003).
  23. N. Calabretta, Y. Liu, H. de Waardt, M. T. Hill, G. D. Khoe, and H. J. S. Dorren, "Multiple-output all-optical header processing technique based on two-pulse correlation principle," Electron. Lett. 37, 1238-1240 (2001).
  24. M. T. Hill, A. Srivatsa, N. Calabretta, Y. Liu, H. deWaardt, G. D. Khoe, and H. J. S. Dorren, "1X2 optical packet switch using all-optical header processing," Electron. Lett. 37, 774-775 (2001).
  25. P. Toliver, I. Glesk, R. J. Runser, K. L. Deng, B. Y. Yu, and P. R. Prucnal, "Routing of 100 Gb/s words in a packet-switched optical networking demonstration (POND) node," J. Lightwave Technol. 16, 2169-2180 (1998).
  26. K. L. Deng, R. J. Runser, P. Toliver, C. Coldwell, D. Zhou, I. Glesk, and P. R. Prucnal, "Demonstration of highly scalable 100Gbit/s OTDM computer interconnect with rapid interchannel switching capability," Electron. Lett. 34, 2418-2419 (1998).
  27. G. Castanon, "Optical packet switching with multiple path routing," Comput. Netw. 32, 653-662 (2000).
  28. H. Shi and J. Lin, "Theoretical analysis on polarization deviation and switch window optimization in nonlinear optical loop mirror demultiplexer," J. Lightwave Technol. 17, 2572-2576 (1999).
  29. L. Tangjun, P. Cuizhu, and Z. Yucheng, "Study on improving the performance of OTDM device," IEEE Photon. Technol. Lett. 11, 2572-2576 (1999).
  30. T. R. Mathies, "Percolation theory and computing with faulty arrays of processors," in Proceedings of the Third Annual Symposium on Discrete Algorithms (SODA) (1992), pp. 100-103.
  31. W. W. Wilcke, S. Kirkpatrick, R. B. Garner, and H. Huels, "Percolation in dense storage arrays," Physica A 314(1-4), 220-229 (2002).
  32. R. Gao, Z. Ghassemlooy, G. Swift, and P. Ball, "Simulation of all optical time division multiplexed router," in Proceedings of West Electronics 2001 (2001).

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

OSA is a member of CrossRef.

CrossCheck Deposited