Deflection routing with Hamiltonian cycles

• Autorzy: Szcześniak, I.

Warianty tytułu

PL

Trasowanie z defleksją i cyklami Hamiltona

• Języki publikacji: EN

Abstrakty

EN

For the mixed routing algorithm running on the networks with non buffering nodes this article presents an improvement in which an Eulerian cycle is replaced with Hamiltonian cycles. The new upper bound on a data packefs end to end number of hops is eąual to or lower than the original upper bound.

PL

W artykule proponuje się ulepszenie mieszanego algorytmu trasującego dla sieci z węzłami, które nie przechowują pakietów (ang. non-buffering nodes). Ulepszenie polega na wykorzystaniu cykli Hamiltona w zamian cyklu Eulera, co sprawia, że górna granica na liczbę skoków pakietu jest mniejsza od (albo w najbardziej niekorzystnym przypadku równa) górnej granicy przed wprowadzeniem ulepszenia.

Słowa kluczowe

PL

trasowanie z defleksją; cykl Hamiltona; cykl Eulera

EN

deflection routing; Hamiltonian cycle; Eulerian cycle

• Czasopismo: Studia Informatica
• Rocznik: 2003
• Tom: Vol. 24, nr 4
• Strony: 251-257
• Opis fizyczny: Bibliogr. 5 poz., rys.

Twórcy

autor

Szcześniak, I.

• Politechnika Śląska, Instytut Informatyki, ul. Akademicka 16, 44-101 Gliwice, Polska,

Bibliografia

• 1. Green P.: Progress in Optical Networking. IEEE Communications Magazine, January 2001, pp. 54-61.
• 2. Xu L., Perros H.G., Rouskas G.: Techniques for optical packet switching and optical burst switching. IEEE Communications Magazine, vol. 39, no. 1, Jan. 2001, pp. 136-142.
• 3. Barth D., Berthome P., Czachorski T., Foumeau J.M., Laforest C., Vial S.: A Mixed Deflection and Convergence Routing Algorithm: Design and Performance. Euro-Par 2002, pp. 767-774.
• 4. Lee J.H., Shin C.S., Chwa K.Y.: Directed Hamiltonian Packing in d-dimensional meshes and its application. Proc of 7th International Symposium on Algorithms and Computation (ISAAC’96) LNCS 1178, Springer Verlag, 1996, pp. 295-304.
• 5. Yener B., Boult T., Ofek Y.: Hamiltonian Decomposition of Regular Topology Networks with Convergence Routing. Technical Report CUCS-011094, Columbia University, Computer Science Department, 1994.