# 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

top## How 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. Zbl0940.90018
- 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. Zbl1045.90502
- 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. Zbl0996.05055
- R.L. Graham, D.E. Knuth and O. Patashnik, Concrete mathematics: a foundation for computer science. Addison-Wesley (1989). Zbl0668.00003
- 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. Zbl0881.68004
- Y. Manoussakis and Z. Tuza, The forwarding index of directed networks. Discrete Appl. Math.68 (1996) 279-291. Zbl0859.05048
- 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 ?

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