Performance evaluation of an optimal deflection routing Algorithm on an Odd Torus

• Autorzy: Czachórski T. , Fourneau J.-M.

Warianty tytułu

PL

Ocena efektywności algorytmu z odbiciami dla sieci o topologii torusa z nie parzystą liczbą węzłów

• Języki publikacji: EN

Abstrakty

EN

We analyze the performance of all optical packet networks. As optical storage of packets is not available, we assume that the routing protocol is based on deflection. This routing strategy does not allow packets loss. However it keeps the pockets inside the network, increases the delay and reduces the bandwidth. Thus the transport delay distribution is the key performance issue for these networks. Here, we consider a 2D tours the size of which is odd. The method is based on a fixed point system between two sub-models. The first subsystems described the global network performances while the second one models the stochastic behavior of two types of packets. We prove the existence of a solution and we present an algorithm to obtain a fixed point.

PL

Artykuł dotyczy badania efektywności sieci całkowicie optycznych. Ponieważ nie ma jeszcze pamięci optycznej o dostępie swobodnym dla kolejkowania pakietów w węzłach, zakłada się, że wybór drogi pakietów jest oparty na "odbiciach": jeżeli w danym takcie pracy sieci pakiet nie może być skierowany w pożądanym kierunku (liczba pakietów przekracza możliwość łącza), jest odbity, czyli kierowany do innego węzła. Taka strategia zapobiega stratom pakietów w sieci, ale zwiększa ich opóźnienie i redukuje przepustowość łączy. Przy założonej topologii sieci jako dwuwymiarowego torusa o nieparzystej liczbie węzłów, artykuł proponuje metodę oceny efektywności pracy sieci opartą na poszukiwaniu punktu stałego operacji pomiędzy modelami dwu podsystemów. Pierwszy podsystem przedstawia globalne działanie sieci, drugi modeluje losowe zachowanie się dwu typów pakietu. Podano dowód istnienia rozwiązania i algorytmu dla uzyskania punktu stałego operacji.

• Wydawca: Instytut Informatyki Teoretycznej i Stosowanej Polskiej Akademii Nauk
• Czasopismo: Archiwum Informatyki Teoretycznej i Stosowanej
• Rocznik: 2004
• Tom: T. 16, z. 4
• Strony: 257--277
• Opis fizyczny: Bibliogr. 21 poz., rys., wykr.

Twórcy

autor

Czachórski T.

• Institute of Theoretical and Applied Informatics, Polish Academy of Sciences, Bałtycka 5, 44-100 Gliwice

autor

Fourneau J.-M.

• PRiSM, Universite de VersaillesSaint-Quentin, 45 Av. des Etats Unis, 78000 Versailles, France

Bibliografia

• [1] J. Bannister, F. Borgonovo, L. Fratta, M. Gerla, ”A versatile model for predicting the performance of deflection routing networks”, Performance Evaluation, V16, pp 201-222, 1992.
• [2]P. Baran. On distributed communication networks. IEEE Transactions on Communication Systems, CS-12, 1964.
• [3]D. Barth, P. Berthome, A. Borrero, J.M. Fourneau, C. Laforest, F. Quessette, and S. Vial. Performance comparisons of Eulerian routing and deflection routing in a 2d-mesh all optical network. In ESM'2001, 2001.
• [4]D. Barth, P. Berthome, T. Czarchoski, J.M. Fourneau, C. Laforest, S. Vial, A Mixed Deflection and Convergence Routing Algorithm: Design and Performance, Europar, 2002, LNCS 2400.
• [5]A. Bonnoni, P.P. Prucnal, ’’Analytical evaluation of improved access techniques in deflection routing networks”, IEEE/ACM Trans, on Networking, V4, N5, 1996.
• [6]A. Borrero, J.M. Fourneau and F. Quessette Packet Selection in a deflection routing algorithm. ISCIS 2002, Orlando, USA, CRC Press.
• [7]J. C. Brassil and R. L. Cruz. Bounds on maximum delay in networks with deflection routing. IEEE Transactions on Parallel and Distributed Systems, 6(7):724-732, 1995.
• [8]T. Czachorski, and J.M. Fourneau. Performance of Deflection and Mixed Routing Algorithms, Germano-Polish Teletrafic symposium, Gdansk, 2002.
• [9]J. Fabrega and X. Munoz, A study of Network Capacity under Deflection routing schemes, Europar 03, LNCS 2790, pp 989-994.
• [10]U. Feige and R. Krauthgamer. Networks on which hot-potato routing does not livelock. Distributed Computing, 13:53-58, 2000.
• [11]C.D. Garcia and W.I. Zangwill, Pathways to solutions, fixed points and equilibria. Prentice Hall, Englewood Cliffs, N.J., 1981.
• [12]W.K. Grasman, M.I. Taksar, D.P. Heyman, Regenerative analysis and steady-state distributions for Markov chains, Oper. Res., vol. 13, 1985, p. 1 107-1 I 16.
• [13]P. Gravey, S. Gosselin, C. Guillemot, D. Chiaroni, N. Le Sauze, A. Jourdan, E. Dotaro, D. Barth, P. Berthome, C. Laforest, S. Vial, T. Atmaca, G. Hebuterne, H. El Biaze, R. Laalaoua, E. Gangloff, and I. Kotuliak. Multiservice optical net¬work: Main concepts and first achievements of the ROM progr am. Journal of Ligthwave Technology, 19:23-31, January 2001.
• [14]J. Mchugh. Algorithmic Graph Theory, Prentice Hall, 1990.
• [ 15] V. A. Malysev and M. V. Mensikov. Ergodicity, continuity and analyticity of count¬able markov chains. Trans. Moscow Math. Soc., V39(l):pp 1-48, 1979.
• [16] S. Mneimeh and F. Quessette. Minimum Deflection Routing Algorithm, Alcatel Patent Application #135945, 2002
• [ 17] Qin Wei Performance du routage par deflexion pour les rseaux tout optique, PhD, University of Versailles, 1999
• [18]Y. Ofek and M. Yung. Principles for high speed network control: loss-less and deadlock-freeness, self-routing and a single buffer per link. In ACM Symposium On Principles of Distributed Computing, pages 161-175, 1990.
• [19]A. Schuster. Optical Interconnections and Parallel Processing: The Interface, chapter Bounds and analysis techniques for greedy hot-potato routing, pages 284- 354. Kluwer Academic Publishers, 1997.
• [20]I. Szczęśniak, Analysis of a finite number of deflections in fully and uniformly loaded regular networks, Networking 2004, Greece.
• [21]S. Yao, B. Mukherjee, and S. Dixit. Plato: a generic modeling technique for optical packet switched networks International Journal on Wireless and Optical Communications, VI, Nl, 2003, pp 91-101. World Scientific Publishing.