On ƒ-wise Arc Forwarding Index and Wavelength Allocations in Faulty All-optical Hypercubes
RAIRO - Theoretical Informatics and Applications (2010)
- Volume: 37, Issue: 3, page 255-270
- ISSN: 0988-3754
Access Full Article
top
Abstract
topHow to cite
topMaňuch, Ján, and Stacho, Ladislav. "On ƒ-wise Arc Forwarding Index and Wavelength Allocations in Faulty All-optical Hypercubes." RAIRO - Theoretical Informatics and Applications 37.3 (2010): 255-270. <http://eudml.org/doc/92723>.
@article{Maňuch2010,
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 ƒ+1
internally node disjoint dipaths connecting all pairs of distinct
nodes in the binary r-dimensional hypercube, where 0 ≤ ƒ < r. 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].
},
author = {Maňuch, Ján, Stacho, Ladislav},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {All-optical networks; fault tolerant system; forwarding
index; optical index; hypercube.},
language = {eng},
month = {3},
number = {3},
pages = {255-270},
publisher = {EDP Sciences},
title = {On ƒ-wise Arc Forwarding Index and Wavelength Allocations in Faulty All-optical Hypercubes},
url = {http://eudml.org/doc/92723},
volume = {37},
year = {2010},
}
TY - JOUR
AU - Maňuch, Ján
AU - Stacho, Ladislav
TI - On ƒ-wise Arc Forwarding Index and Wavelength Allocations in Faulty All-optical Hypercubes
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/3//
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 ƒ+1
internally node disjoint dipaths connecting all pairs of distinct
nodes in the binary r-dimensional hypercube, where 0 ≤ ƒ < r. 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].
LA - eng
KW - All-optical networks; fault tolerant system; forwarding
index; optical index; hypercube.
UR - http://eudml.org/doc/92723
ER -
References
top- B. Beauquier, All-to-all communication for some wavelength-routed all-optical networks. Networks33 (1999) 179-187.
- 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).
- B. Beauquier, P. Hell and S. Pérennes, Optimal wavelength-routed multicasting. Discrete Appl. Math.84 (1998) 15-20.
- 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.
- 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).
- 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.
- L. Gargano, P. Hell and S. Pérennes, Colouring paths in directed symmetric trees with applications to optical networks, J. Graph Theory38 (2001) 183-186.
- R.L. Graham, D.E. Knuth and O. Patashnik, Concrete mathematics: a foundation for computer science. Addison-Wesley (1989).
- P.E. Green, Fiber Optic Networks. Prentice Hall (1993).
- 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.
- Y. Manoussakis and Z. Tuza, The forwarding index of directed networks. Discrete Appl. Math.68 (1996) 279-291.
- J. Manuch and L. Stacho, Fault-tolerant wavelength allocation in all-optical hypercubes, in Proc. 6th SIROCCO, Informatics5 (1999) 219-232.
- D. Minoli, Telecommunications Technology Handbook. Artech House (1991).
- R.K. Pankaj, Architectures for linear light-wave networks. Ph.D. Thesis, Dep. of Electrical Engineering and Computer Science, MIT, Cambridge, MA (1992).
- R.K. Pankaj and R.G. Gallager, Wavelength requirements of all-optical networks. IEEE/ACM Trans. Network.3 (1995) 269-280.
- 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.
- G. Wilfong, Minimizing wavelengths in an all-optical ring network, in Proc. ISAAC'96 Lecture Notes in Comput. Sci. 1178 (1996) 346-355.
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.