Deflection routing in an all-optical network in 2D grid : performance evaluation

• Autorzy: Borrero A. , Quessette F.

Warianty tytułu

PL

Badanie wydajności trasowania z wymuszoną zmianą drogi w sieciach w pełni optycznych w przypadku topologii sieci typu dwuwymiarowej siatki

• Języki publikacji: EN

Abstrakty

EN

In this work, we study a deflection routing strategy for the emerging generation of networks, all-optical networks. This investigation is made in order to evaluate the performance of a heuristical deflection routing strategy, known as "Scale Routing", on a synchronous network in a ID grid. We have used this routing strategy to attempt to find the optimal route, even though the packet were deflected. In this case, optimal route does not mean the shortest path, (although in many cases it comes near to it), nor the path with the minimum number of deflections. But it means the route that provides in each slot, in every node, the largest number of selection possibilities. This algorithm is known as the "scale routing algorithm". Furthermore, we add some heuristics to choose the packet(s) to be deflected. The first one is based on the rcmaining distance until its destination node, and the second one is based on the number of deflections that it has already had. Then we have modified the destination given to the packets. At first, it has been a uniform distribution, then a non uniform distribution directed towards a corner and at last a non uniform distribution directed towards the center of the grid. Finally some statistics and curves are presented to be analyzed and to compare the performances of this strategy with the different heuristics and the variation on the traffic. We have got all this results by simulation. For this work, we have used QNAP II modelling tool [14] to design the simulator.

PL

W artykule omawiana jest strategia trasowania z wymuszoną zmianą drogi (Deflection routing), zwaną w artykule odbiciem dla pojawiającej się nowej technologii sieci, jaką są sieci w pełni optyczne. Wymuszona zmiana drogi wynika z braku możliwości kolejkowania pakietów w węzłach optycznych. Jeśli do węzła przychodzi więcej pakietów, niż może być wysłane w prawidłowym dla nich kierunku, niektóre muszą być wysłane (odbite) w innym kierunku, aby nie uległy zniszczeniu. W artykule, dla synchronicznych sieci typu siatka 2D, badano wydajność heurystycznej metody takiego routingu, znanej routingiem ze skalowaniem (scale routing). Strategia ta została wypróbowana dla znajdowania optymalnej ścieżki dla pakietów, które mogły zostać po drodze odbite. W przypadku odbicia pakietu ścieżka optymalna nie oznacza ścieżki najkrótszej (choć w wielu przypadkach przebiega blisko takiej ścieżki) ani ścieżki z najmniejszą liczbą odbić. Oznacza ścieżkę, która dla każdego węzła znajdującego się na drodze pakietu zapewnia największą możliwą liczbę kolejnych ścieżek do wyboru. Taki algorytm nazywa się algorytmem routingu ze skalowaniem. Ponadto dodane zostały pewne heurystyki wybierania, który pakiet (pakiety) zostaną w weźle odbite. Pierwsza z nich opiera się na pozostałym do pokonania dystansie do węzła docelowego, druga bierze pod uwagę liczbę odbić, którą pakiet doświadczyłjuż w sieci. Modyfikowany byłsposób wyboru węzłów docelowych dla pakietów. Na początku miał on rozkład równomierny, następnie zbadano rozkłady nierównomierne. Pakiety zostały skierowane do jednego z rogów siatki węzłów, następnie pakiety kierowane były do środka siatki. Zostały zaprezentowane i przeanalizowane określone statystyki i wykresy oraz porównano wyniki z zastosowanymi heurystykami i różnymi rodzajami ruchu pakietów. Wszystkie wyniki zostały uzyskane za pomocą badań symulacyjnych, z wykorzystaniem narzędzia QNAPII.

Słowa kluczowe

EN

all-optical networks; deflection routing

• Wydawca: Instytut Informatyki Teoretycznej i Stosowanej Polskiej Akademii Nauk
• Czasopismo: Theoretical and Applied Informatics
• Rocznik: 2006
• Tom: Vol. 18, nr 3
• Strony: 213--236
• Opis fizyczny: Bibliogr. 15 poz., rys.

Twórcy

autor

Borrero A.

autor

Quessette F.

• Laboratoire PRiSM Universite de Yersailles 45, Avenue des Etats-Unis, 78035 Yersailles Cedex, France

Bibliografia

• [1] Aroya I.B., Chinn D.D., and Schuster A. A lower bound for nearly minimal adaptive and hot-potato algorithms. Algorithmica, 21(4):347.376, 1998.
• [2] Baran P. On distributed communication networks. IEEE Transactions on Communication Systems, CS-12, 1964.
• [3] Barth D., Berthomé P., Borrero A., Fourneau J.-M., Laforest C., Quessette F., and Vial S. Performance comparisons of eulerian routing and deection routing in a 2d-mesh all optical network. In ESM, 2001.
• [4] Baynat B. Théorie des files d’attente. Des chaines de Markov aux réseaux à forme produit. Hermes Science Publications, 2000.
• [5] Birchler B, Esfahanian A., and Torng E. Toward a general theory unicast-based multicast communication. Lecture Notes in Computer Science, 1017:237.251, 1995.
• [6] Borodin A., Rabani Y., and Schieber B. Deterministic many-to-many hot potato routing. IEEE Transactions on Parallel and Distributed Systems., 8(6):587.596, 1997.
• [7] Brassil J. and Cruz R. Bounds on maximum delay in networks with deection routing. IEEE Transactions on Parallel and Distributed Systems., 6(7):724.732, 1995.
• [8] Feige U. Observations on hot potato routing. In 3rd Israeli Symposium on the Theory of Computing and Systems, ISTCS, pages 30.39, 1995.
• [9] Grammatikakis M., Kraetzl M, and Fleury E. Shorthest-path and hot-potato routing on unbuffered 2-d tori. In IEEE Conference on Global Communications (GLOBECOM), pages 165.169, Phoenix, Arizona, 1997.
• [10] Hajek B. Bounds on evacuation time for deection routing. Distributed Computing, 5:1.6, 1991.
• [11] Kucera L. Wait-free deection routing of long messages. IEEE Transactions on Parallel and distributed Systems, 12(5):476.488, 2001.
• [12] Meyer F. and Westermann M. Hot-potato routing on multi-dimensional tori. In Proc. of the 21st WG (Aachen), pages 209.221, 1995.
• [13] Miltos D., Grammatikakis D., Hsu F, and Sibeyn J.F. Packet routing in xed-connection network: A survey. Journal of Parallel and Distributed Computing, 54(2):77.132, 1998.
• [14] Potier D. New user's introduction to qnap2. Technical Report RT40, INRIA, Roquencourt FRANCE, 1984.
• [15] Varvarigos L. and Lang J. A virtual circuit deection protocol. IEEE/ACM Transactions on Networking, 7(3):335. 349, 1999.