On $𝖿$-wise arc forwarding index and wavelength allocations in faulty all-optical hypercubes
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 37 (2003) no. 3, pp. 255-270.

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. 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].

DOI : https://doi.org/10.1051/ita:2003019
Classification : 68M10,  68M15,  68R05
Mots clés : all-optical networks, fault tolerant system, forwarding index, optical index, hypercube
@article{ITA_2003__37_3_255_0,
author = {Ma\v{n}uch, J\'an and Stacho, Ladislav},
title = {On $\sf f$-wise arc forwarding index and wavelength allocations in faulty all-optical hypercubes},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {255--270},
publisher = {EDP-Sciences},
volume = {37},
number = {3},
year = {2003},
doi = {10.1051/ita:2003019},
zbl = {1106.68304},
mrnumber = {2021317},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ita:2003019/}
}
TY  - JOUR
AU  - Maňuch, Ján
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
DA  - 2003///
SP  - 255
EP  - 270
VL  - 37
IS  - 3
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita:2003019/
UR  - https://zbmath.org/?q=an%3A1106.68304
UR  - https://www.ams.org/mathscinet-getitem?mr=2021317
UR  - https://doi.org/10.1051/ita:2003019
DO  - 10.1051/ita:2003019
LA  - en
ID  - ITA_2003__37_3_255_0
ER  - 
Maňuch, Ján; 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, Tome 37 (2003) no. 3, pp. 255-270. doi : 10.1051/ita:2003019. http://www.numdam.org/articles/10.1051/ita:2003019/

[1] B. Beauquier, All-to-all communication for some wavelength-routed all-optical networks. Networks 33 (1999) 179-187. | Zbl 0940.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. | Zbl 0908.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. | Zbl 1045.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. | Zbl 0996.05055

[8] R.L. Graham, D.E. Knuth and O. Patashnik, Concrete mathematics: a foundation for computer science. Addison-Wesley (1989). | MR 1397498 | Zbl 0668.00003

[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. | Zbl 0881.68004

[11] Y. Manoussakis and Z. Tuza, The forwarding index of directed networks. Discrete Appl. Math. 68 (1996) 279-291. | Zbl 0859.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.

Cité par Sources :