Analysis of transmission properties of 3rd degree chordal rings

• Autorzy: Bujnowski S. , Dubalski B. , Zabłudowski A.

Warianty tytułu

PL

Analiza własności transmisyjnych pierścieni cięciwowych trzeciego stopnia

• Języki publikacji: EN

Abstrakty

EN

A method of evaluating transmission abilities of 3rd degree chordal rings with the use od adjacent matrix analysis is presented in the paper.

PL

Systemy telekomunikacyjne, w których zarówno transmisja jak i komutacja odbywa się na drodze optycznej, umożliwiają przesyłanie dużych bloków informacji z bardzo dużymi prędkościami, gdyż cechują je znacznie większe przepływności aniżeli te, które występują w tradycyjnych sieciach przesyłających sygnały elektryczne. Konieczność zwiększenia szybkości transmisji została spowodowana znaczącym wzrostem zapotrzebowania na szerokopasmowy dostęp do Internetu, co umożliwia przesyłanie użytkownikom indywidualnym i biznesowym dużych ilości danych. W sieciach optycznych stosowane są systemy zwielokrotnienia falowego WDM (Wavelength-Division Multiplexing) zwiększające stopień wykorzystania możliwości transmisyjnych mediów, jakimi są światłowody. W nieodległej przyszłości powstaną sieci całkowicie optyczne, w których wszystkie informacje przesyłane są w postaci fali świetlnej bez konwersji ich w sygnały elektryczne. Tego typu systemy mogą być modelowane przy wykorzystaniu grafów skierowanych, a dokładniej przy użyciu grafów symetrycznych. To oznacza, że graf skierowany G o zbiorze wierzchołków V(G) i zbiorze krawędzi E(G), charakteryzuje się tym, że jeśli krawędź [vi,vj] należy do zbioru E(G), wówczas i krawędź [vj, vi] należy do tego zbioru. Zatem krawędź digrafu łącząca węzły vi i vj może być zastąpiona przez dwie krawędzie skierowane [vi,vj] oraz [vj,vi], co odpowiada w realizacji fizycznej sieci optycznej połączeniu dwóch dowolnych węzłów dwoma włóknami światłowodowymi, z których jedno służy do przesyłania sygnałów pomiędzy węzłami vi oraz vj, zaś drugie — pomiędzy vj oraz vi. Wielu autorów w swych pracach porusza problem określania rutingów oraz oceny ich wpływu na sprawność transmisji informacji przesyłanych w sieciach. Prace te odnoszą się zarówno do sieci komputerowych, jak i telekomunikacyjnych sieci optycznych. W przypadku sieci optycznych problem rutowania polega na określeniu ścieżki oraz przydzieleniu odpowiedniej długości fali świetlnej dla każdego wywołania spośród całego zbioru wywołań. Przez wywołanie rozumiana jest uporządkowana para węzłów (vj, vj), która odpowiada informacji wysłanej z węzła vi do węzła vj. Zadanie, które stoi przed projektantem sieci, polega na przyjęciu takiego rozwiązania, które wyeliminuje możliwość pojawienia się dwóch wywołań wykorzystujących to samo łącze i transmitowanych przy użyciu tej samej długość fali. Ponieważ koszt optycznych komutatorów jest proporcjonalny do liczby przełączanych długości fal, zatem zaleca się by ta liczba była minimalna. Zatem określenie rutingu w sieciach optycznych polega na rozwiązaniu skorelowanych ze sobą dwóch zadań — przydziału drogi oraz długości fali świetlnej dla każdego wywołania. Problem ten został określony jako problem klasy NP-trudny, zatem może być on rozwiązany jedynie dla specyficznych przypadków. Na własności transmisyjne analizowanego systemu telekomunikacyjny w istotny sposób wpływa zastosowana topologia połączeń pomiędzy modułami komutacyjnymi. W pracy [6] dokonano przeglądu szeregu znanych struktur połączeniowych pod względem: minimalnego kosztu sieci — wyrażonego sumaryczną liczbą łączy; minimalnego opóźnienia przysyłania informacji — miarą tego parametru jest wielkość średnicy oraz średnia długość ścieżki; odporności na uszkodzenia, którą charakteryzuje liczba niezależnych ścieżek pomiędzy dwoma węzłami albo minimalna liczba węzłów lub krawędzi, po usunięciu których sieć przestaje być spójna; regularności i symetrii; prostoty routingów; skalowalności. Na podstawie tej i innych prac, dotyczących sieci opisanych przy pomocy grafów symetrycznych, sformułowano wniosek, że korzystne dla modelowania sieci optycznych, ze względu na prostotę i przejrzystość topologii, odporność na uszkodzenia oraz dobrą skalowalność, będzie stosowanie struktur zwanych pierścieniami cięciwowymi. Prekursorami wykorzystania tego typu sieci do budowy multi-komputerów byli Arden i Lee [8]. Zdefiniowali oni ten typ struktur następująco: Pierścieniem cięciwowym stopnia 3 nazywany jest graf regularny, w którym każdy parzysty węzeł o numerze i = 0,2,4,..., w - 2 jest połączony z węzłem o numerze (i-s) mod w lub, co jest równoznaczne, każdy nieparzysty węzeł j = 1,3,5,..., w - 1 jest połączony z węzłem o numerze (i + s) mod w, gdzie s < w/2 oznacza długość cięciwy, która z założenia jest wartością dodatnią i nieparzystą, a w określa liczbę węzłów. Pierścienie cięciwowe k-tego stopnia są opisywane notacją G(w; s1,s2,..., sk), gdzie w oznacza liczbę węzłów występujących w grafie, zaś si — długości cięciw, przy czym s1 = 1. W przypadku pierścieni stopnia trzeciego notacja ta posiada postać G(w; 1,s). Przedmiotem artykułu jest zaprezentowanie metody oceny własności transmisyjnych sieci opisanych grafami cięciwowymi trzeciego stopnia przy wykorzystaniu macierzy przyległości (sąsiedztwa). Macierz sąsiedztwa określa przyległość między sobą (incydencję) węzłów grafu [11], Macierz opisująca pierścień cięciwowy jest macierzą kwadratową wymiaru w x w (w oznacza liczbę węzłów w grafie), o współczynnikach bij, które przyjmują wartości ze zbioru (0,1), przy czym: - bij = 1, wtedy, gdy istnieje krawędź łącząca węzły vi, oraz vj, - bij = 0, wtedy, gdy nie istnieje krawędź łącząca węzły vi oraz vj . Potęgi macierzy sąsiedztwa umożliwiają obliczenie liczby marszrut o długości równej wykładnikowi tej macierzy łączących dowolne węzły grafu. Marszrutą nazywany jest dowolny ciąg naprzemienny węzłów i krawędzi, w którym zarówno każdy węzeł jak i krawędź mogą pojawić się dowolną liczbę razy [13]. Macierz sąsiedztwa można wykorzystać dla wyznaczenia minimalnych długości dróg łączących poszczególne wierzchołki grafu oraz jego średnicy stanowiącej największy element zbioru dróg minimalnej długości. Badanie potęg macierzy sąsiedztwa może również posłużyć, co zostało pokazane w artykule, do określenia własności transmisyjnych pierścieni cięciwowych, gdyż obliczone rozkłady marszrut łączące sąsiednie węzły tworzą ciągi liczbowe, które można porównać z rozkładem charakterystycznym dla grafu odniesienia, nazwanego grafem optymalnym. Jako wprowadzenie do analizy tych rozkładów, w pracy podano twierdzenie określające liczby marszrut występujące pomiędzy dwoma przyległymi węzłami w pierścieniu stopnia 2, czyli dla cyklu Hamiltona. Wykazano, że liczba tych marszrut jest ściśle związana z liczbami tworzącymi ciąg Catalana [12]. Pokazano, że cechą charakterystyczną pierścieni cięciwowych trzeciego stopnia, w których długość cięciwy s2 jest równa w/2, są rozkłady marszrut o długości równej nieparzystej liczbie krawędzi. Udowodniono, że liczba marszrut o długości l łączących sąsiednie węzły będącej nieparzystą wielokrotnością liczby krawędzi: - leżące na pierścieniu — tworzy ciąg, którego wyrazami są odpowiadające liczbie krawędzi l zcentralizowane współczynniki trójmianowe (Centered Trinomial Coefficients) [14] występujące w kolumnie k = 0; - poprzez cięciwę — tworzą ciąg, którego wyrazami są odpowiadające liczbie krawędzi I zcentralizowane współczynniki trójmianowe występujące w kolumnach k = 1 lub k = — 1. - liczba marszrut, o długości będącej nieparzystą wielokrotnością liczby krawędzi łączących sąsiednie węzły leżące na pierścieniu, tworzy ciąg liczbowy, którego wyrazy są iloczynem długości tych marszrut i odpowiadającej im współczynników występujących w kolumnie k = 1 trójkąta Motzkina [15]; - marszruty o długości będącej parzystą wielokrotnością liczby krawędzi nie występują. Analizując elementy potęg macierzy sąsiedztwa opisujące rozkłady marszrut w grafach trzeciego stopnia, w których długość cięciwy s jest mniejsza od w/2, stwierdzono, iż liczby marszrut o określonej długości, łączących węzły oddalone od siebie o długość jednej krawędzi, tworzą ciągi liczbowe, które można wykorzystać do oceny własności transmisyjnych badanych struktur. Na podstawie analizy otrzymanych wyników postawiono hipotezę, że obok średnicy oraz średniej długości ścieżki, istotną rolę odgrywa rozkład liczby marszrut określonej długości, który będzie odnoszony do rozkładu charakterystycznego dla grafu idealnego. Im mniej różni się on od rozkładu liczby marszrut wyznaczonego dla grafu optymalnego, tym prawdopodobieństwo odrzucenia realizacji połączenia jest mniejsze. Dla sprawdzenia prawdziwości tej hipotezy przetestowano szereg pierścieni cięciwowych odnosząc otrzymane wyniki do ich własności transmisyjnych wyznaczonych dzięki badaniom symulacyjnym. Rezultaty te nie zaprzeczyły słuszności tej hipotezy, a na ich podstawie można stwierdzić, iż rozkład marszrut łączących sąsiednie węzły grafu w większym stopniu decyduje o własnościach transmisyjnych pierścieni cięciwowych niż średnica oraz średnia długość drogi w tym grafie. Ponadto stwierdzono, że odgrywa on decydującą rolę w badaniu izomorfizmu analizowanych struktur sieciowych.

Słowa kluczowe

EN

distributed switching system; network topology; chordal ring; adjacent matrix; transmission abilities

PL

system telekomunikacyjny; sieć optyczna; pierścień cięciwowy; macierz sąsiedztwa; własności transmisyjne

• Wydawca: Wydawnictwo Naukowe PWN SA
• Czasopismo: Kwartalnik Elektroniki i Telekomunikacji
• Rocznik: 2005
• Tom: Vol. 51, z. 4
• Strony: 521--539
• Opis fizyczny: Bibliogr. 15 poz., wykr.

Twórcy

autor

Bujnowski S.

• Instytut Telekomunikacji, Akademia Techniczno-Rolnicza, Al. Kaliskiego 7, 86-796 Bydgoszcz

autor

Dubalski B.

• Instytut Telekomunikacji, Akademia Techniczno-Rolnicza, Al. Kaliskiego 7, 86-796 Bydgoszcz

autor

Zabłudowski A.

• Instytut Telekomunikacji, Akademia Techniczno-Rolnicza, Al. Kaliskiego 7, 86-796 Bydgoszcz

Bibliografia

• 1. L. N. Bhuyan: Interconnection Networks for Parallel and Distributed Processing. IEEE Computer Vol. 20 No. 6, 1987, pp. 9-12.
• 2. G. Yanovsky: Evolution and Convergence in Telecommunications. www.ssgrr.it/en/ssgrr2002s/ papers/262.pdf.
• 3. A. Jajszczyk: Optyczne Sieci Szerokopasmowe. Szerokopasmowe sieci światłowodowe. XVI Krajowa Szkoła Optoelektroniki. Z. 3, Zakopane 2001, ss. 1-38.
• 4. L. Narayanan, J. Opatrny, D. Sotteau : All-To-All Optical Routing in Chordal Rings of Degree 4. Algorithmica Vol. 31, 2001, pp. 155-178.
• 5. M. M. Freire and H. J. A. da Silva: Assessment of Blocking Performance in Bidirectional WDM Ring Networks with Node-To- Node and Full-Mesh Connectivity. European Conference on Networks and Optical Communications (NOC’99), Delft, 1999.
• 6. G . Kotsis : Interconnection Topologies and Routing for Parallel Processing Systems. ACPC, Technical Report Series, ACPC/TR92-19, 1992.
• 7. S. Bujnowski : Analysis & Synthesis Homogeneous Structure Networks Connecting Communications Modules - Ph. D. Dissertation. ATR Bydgoszcz 2003.
• 8. W. Arden, H. Lee : Analysis of Chordal Ring Network. IEEE Transactions on Computers Vol. 30 No. 4, 1981, pp. 291-295.
• 9. S. Bujnowski, B. Dubalski, A. Zabłudowski : The Method of Searching for Chordal Rings Minimizing Probability of Cali Rejection. Advanced School and Workshop on Mathe- matical Techniques and Problems in Telecommunications, Tomar 2003, pp. 257-279.
• 10. J . C. Bermond, F. Comellas, D. Hsu : Distributed Loop Computer Networks: A Survey. Journal of Parallel and Distributed Computing, No. 24, 1995, 2-10.
• 11. K. A. Ross, Ch. R. B. Wright : Discrete Mathematics. Prentice Hall Inc. 1992.
• 12. R. L. Graham, D.E. Knuth, O. Patashnik : Cone rete Mathematics. Addison-Wesley Comp. Inc. 1994.
• 13. F. R. Bernhart : Catalan, Motzkin, and Riordan Numbers. Discrete Mathematics, 204, 1999, pp. 73-112.
• 14. J. L. Arregui : Tangent and Bernoulli Numbers Related to Motzkin and Catalan Numbers by Means of Numerical Triangles. Mathematics Subject Classification, 1991.
• 15. On-Line Encyclopedia of Integer Seąuences - A087457.