On 𝖿 -wise arc forwarding index and wavelength allocations in faulty all-optical hypercubes

Ján Maňuch; Ladislav Stacho

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2003)

  • Volume: 37, Issue: 3, page 255-270
  • ISSN: 0988-3754

Abstract

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

How to cite

top

Maňuch, Ján, and 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 37.3 (2003): 255-270. <http://eudml.org/doc/244666>.

@article{Maňuch2003,
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 $f+1$ internally node disjoint dipaths connecting all pairs of distinct nodes in the binary $r$-dimensional hypercube, where $0\le f&lt;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].},
author = {Maňuch, Ján, Stacho, Ladislav},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {all-optical networks; fault tolerant system; forwarding index; optical index; hypercube},
language = {eng},
number = {3},
pages = {255-270},
publisher = {EDP-Sciences},
title = {On $\sf f$-wise arc forwarding index and wavelength allocations in faulty all-optical hypercubes},
url = {http://eudml.org/doc/244666},
volume = {37},
year = {2003},
}

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
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 $f+1$ internally node disjoint dipaths connecting all pairs of distinct nodes in the binary $r$-dimensional hypercube, where $0\le f&lt;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].
LA - eng
KW - all-optical networks; fault tolerant system; forwarding index; optical index; hypercube
UR - http://eudml.org/doc/244666
ER -

References

top
  1. [1] B. Beauquier, All-to-all communication for some wavelength-routed all-optical networks. Networks 33 (1999) 179–187. Zbl0940.90018
  2. [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. [3] B. Beauquier, P. Hell and S. Pérennes, Optimal wavelength-routed multicasting. Discrete Appl. Math. 84 (1998) 15–20. Zbl0908.90122
  4. [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. Zbl1045.90502
  5. [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. [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. [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. Zbl0996.05055
  8. [8] R.L. Graham, D.E. Knuth and O. Patashnik, Concrete mathematics: a foundation for computer science. Addison-Wesley (1989). Zbl0668.00003MR1397498
  9. [9] P.E. Green, Fiber Optic Networks. Prentice Hall (1993). 
  10. [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. Zbl0881.68004
  11. [11] Y. Manoussakis and Z. Tuza, The forwarding index of directed networks. Discrete Appl. Math. 68 (1996) 279–291. Zbl0859.05048
  12. [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. [13] D. Minoli, Telecommunications Technology Handbook. Artech House (1991). 
  14. [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. [15] R.K. Pankaj and R.G. Gallager, Wavelength requirements of all-optical networks. IEEE/ACM Trans. Network. 3 (1995) 269–280. 
  16. [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. [17] G. Wilfong, Minimizing wavelengths in an all-optical ring network, in Proc. ISAAC’96 Lecture Notes in Comput. Sci. 1178 (1996) 346–355. 

NotesEmbed ?

top

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.