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 internally node disjoint dipaths connecting all pairs of distinct nodes in the binary -dimensional hypercube, where . This system of dipaths constitutes a routing protocol that remains functional in the presence of up to faults (of nodes and/or links). The problem of constructing such protocols for general networks was mentioned in [1]. We compute precise values of -wise arc forwarding indexes and give (describe dipaths and color them) nearly optimal all-to-all -fault tolerant protocols for the hypercube network. Our results generalize corresponding results from [1, 4, 14].
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://archive.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://archive.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://archive.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://archive.numdam.org/articles/10.1051/ita:2003019/
[1] All-to-all communication for some wavelength-routed all-optical networks. Networks 33 (1999) 179-187. | Zbl
,[2] 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).
, , , , , and ,[3] Optimal wavelength-routed multicasting. Discrete Appl. Math. 84 (1998) 15-20. | Zbl
, and ,[4] Efficient collective communications in optical networks, in: Proc. 23rd ICALP'96, Paderborn, Germany, Lecture Notes in Comput. Sci. 1099 (1996) 574-585. | Zbl
, , , and ,[5] Dense wavelength division multiplexing techniques for high capacity and multiple access communication systems. J. Selected Areas in Commun. 8 (1990).
, and (eds.),[6] Scheduling of virtual connections in fast networks, in Proc. 4th Workshop on Parallel Systems and Algorithms PASA'96, 13-32.
and ,[7] Colouring paths in directed symmetric trees with applications to optical networks, J. Graph Theory 38 (2001) 183-186. | Zbl
, and ,[8] Concrete mathematics: a foundation for computer science. Addison-Wesley (1989). | MR | Zbl
, and ,[9] Fiber Optic Networks. Prentice Hall (1993).
,[10] 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
, and ,[11] The forwarding index of directed networks. Discrete Appl. Math. 68 (1996) 279-291. | Zbl
and ,[12] Fault-tolerant wavelength allocation in all-optical hypercubes, in Proc. 6th SIROCCO, Informatics 5 (1999) 219-232.
and ,[13] Telecommunications Technology Handbook. Artech House (1991).
,[14] Architectures for linear light-wave networks. Ph.D. Thesis, Dep. of Electrical Engineering and Computer Science, MIT, Cambridge, MA (1992).
,[15] Wavelength requirements of all-optical networks. IEEE/ACM Trans. Network. 3 (1995) 269-280.
and ,[16] Optical all-to-all communication for some product graphs, in Proc. 24th SOFSEM'97, Lecture Notes in Comput. Sci. 1338 (1997) 555-562.
, and ,[17] Minimizing wavelengths in an all-optical ring network, in Proc. ISAAC'96 Lecture Notes in Comput. Sci. 1178 (1996) 346-355.
,Cité par Sources :