# On $\U0001d5bf$-wise arc forwarding index and wavelength allocations in faulty all-optical hypercubes

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2003)

- Volume: 37, Issue: 3, page 255-270
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topMaňuch, Ján, and Stacho, Ladislav. "On $\sf f$-wise arc forwarding index and wavelength allocations in faulty all-optical hypercubes." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 37.3 (2003): 255-270. <http://eudml.org/doc/244666>.

@article{Maňuch2003,

abstract = {Motivated by the wavelength division multiplexing in all-optical networks, we consider the problem of finding an optimal (with respect to the least possible number of wavelengths) set of $f+1$ internally node disjoint dipaths connecting all pairs of distinct nodes in the binary $r$-dimensional hypercube, where $0\le f<r$. This system of dipaths constitutes a routing protocol that remains functional in the presence of up to $f$ faults (of nodes and/or links). The problem of constructing such protocols for general networks was mentioned in [1]. We compute precise values of $f$-wise arc forwarding indexes and give (describe dipaths and color them) nearly optimal all-to-all $f$-fault tolerant protocols for the hypercube network. Our results generalize corresponding results from [1, 4, 14].},

author = {Maňuch, Ján, Stacho, Ladislav},

journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},

keywords = {all-optical networks; fault tolerant system; forwarding index; optical index; hypercube},

language = {eng},

number = {3},

pages = {255-270},

publisher = {EDP-Sciences},

title = {On $\sf f$-wise arc forwarding index and wavelength allocations in faulty all-optical hypercubes},

url = {http://eudml.org/doc/244666},

volume = {37},

year = {2003},

}

TY - JOUR

AU - Maňuch, Ján

AU - Stacho, Ladislav

TI - On $\sf f$-wise arc forwarding index and wavelength allocations in faulty all-optical hypercubes

JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

PY - 2003

PB - EDP-Sciences

VL - 37

IS - 3

SP - 255

EP - 270

AB - Motivated by the wavelength division multiplexing in all-optical networks, we consider the problem of finding an optimal (with respect to the least possible number of wavelengths) set of $f+1$ internally node disjoint dipaths connecting all pairs of distinct nodes in the binary $r$-dimensional hypercube, where $0\le f<r$. This system of dipaths constitutes a routing protocol that remains functional in the presence of up to $f$ faults (of nodes and/or links). The problem of constructing such protocols for general networks was mentioned in [1]. We compute precise values of $f$-wise arc forwarding indexes and give (describe dipaths and color them) nearly optimal all-to-all $f$-fault tolerant protocols for the hypercube network. Our results generalize corresponding results from [1, 4, 14].

LA - eng

KW - all-optical networks; fault tolerant system; forwarding index; optical index; hypercube

UR - http://eudml.org/doc/244666

ER -

## References

top- [1] B. Beauquier, All-to-all communication for some wavelength-routed all-optical networks. Networks 33 (1999) 179–187. Zbl0940.90018
- [2] B. Beauquier, C.J. Bermond, L. Gargano, P. Hell, S. Perennes, and U. Vaccaro, Graph Problems arising from wavelength-routing in all-optical networks, in Proc. of the 2nd Workshop on Optics and Computer Science, part of IPPS’97, (1997).
- [3] B. Beauquier, P. Hell and S. Pérennes, Optimal wavelength-routed multicasting. Discrete Appl. Math. 84 (1998) 15–20. Zbl0908.90122
- [4] J.-C. Bermond, L. Gargano, S. Perennes, A. Rescigno and U. Vaccaro, Efficient collective communications in optical networks, in: Proc. 23rd ICALP’96, Paderborn, Germany, Lecture Notes in Comput. Sci. 1099 (1996) 574–585. Zbl1045.90502
- [5] N.K. Cheung, K. Nosu and G. Winzer (eds.), Dense wavelength division multiplexing techniques for high capacity and multiple access communication systems. J. Selected Areas in Commun. 8 (1990).
- [6] T. Erlebach and K. Jansen, Scheduling of virtual connections in fast networks, in Proc. 4th Workshop on Parallel Systems and Algorithms PASA’96, 13–32.
- [7] L. Gargano, P. Hell and S. Pérennes, Colouring paths in directed symmetric trees with applications to optical networks, J. Graph Theory 38 (2001) 183–186. Zbl0996.05055
- [8] R.L. Graham, D.E. Knuth and O. Patashnik, Concrete mathematics: a foundation for computer science. Addison-Wesley (1989). Zbl0668.00003MR1397498
- [9] P.E. Green, Fiber Optic Networks. Prentice Hall (1993).
- [10] C.C. Lam, C.H. Huang and P. Sadayappan, Optimal algorithms for all-to-all personalized communication on rings and two dimensional tori. J. of Parallel and Distributed Comput. 28 (1997) 3–13. Zbl0881.68004
- [11] Y. Manoussakis and Z. Tuza, The forwarding index of directed networks. Discrete Appl. Math. 68 (1996) 279–291. Zbl0859.05048
- [12] J. Maňuch and L. Stacho, Fault-tolerant wavelength allocation in all-optical hypercubes, in Proc. 6th SIROCCO, Informatics 5 (1999) 219–232.
- [13] D. Minoli, Telecommunications Technology Handbook. Artech House (1991).
- [14] R.K. Pankaj, Architectures for linear light-wave networks. Ph.D. Thesis, Dep. of Electrical Engineering and Computer Science, MIT, Cambridge, MA (1992).
- [15] R.K. Pankaj and R.G. Gallager, Wavelength requirements of all-optical networks. IEEE/ACM Trans. Network. 3 (1995) 269–280.
- [16] H. Shröder, O. Sýkora and I. Vrto, Optical all-to-all communication for some product graphs, in Proc. 24th SOFSEM’97, Lecture Notes in Comput. Sci. 1338 (1997) 555–562.
- [17] G. Wilfong, Minimizing wavelengths in an all-optical ring network, in Proc. ISAAC’96 Lecture Notes in Comput. Sci. 1178 (1996) 346–355.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.