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

DOI : 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},
     mrnumber = {2021317},
     zbl = {1106.68304},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita:2003019/}
}
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
SP  - 255
EP  - 270
VL  - 37
IS  - 3
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita:2003019/
DO  - 10.1051/ita:2003019
LA  - en
ID  - ITA_2003__37_3_255_0
ER  - 
%0 Journal Article
%A Maňuch, Ján
%A Stacho, Ladislav
%T On $\sf f$-wise arc forwarding index and wavelength allocations in faulty all-optical hypercubes
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2003
%P 255-270
%V 37
%N 3
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ita:2003019/
%R 10.1051/ita:2003019
%G en
%F ITA_2003__37_3_255_0
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

[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

[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

[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

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

[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

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

[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 :