Simunet - komputerowa realizacja problemu routingua cd.

2. PROBLEM WYBORU ŚCIEŻKI

Sieć wieloserwerowa może być symbolicznie zobrazowana jako graf skierowany, z wierzchołkami jako serwerami oraz krawędziami jako połączenia-mi. Podobnie jak w rzeczywistości krawędzie powinny być krawędziami kierunkowymi, ponieważ łącze pomiędzy dwoma serwerami jest często zrealizowane jako łącze asymetryczne o różnych prędkościach przesyłu do i z serwera (np. technologia ADSL). Wagami poszczególnych krawędzi stają się podane przez użytkownika parametry, takie jak szybkość łącza T – Transfer Rate (przepustowość wyrażona w kilobitach na sekundę, kbit/s) oraz koszt jego użycia C – Cost (w złotych/cykl). Rozwiązanie problemu sprowadza się do odnalezienia w tak zdefiniowanym grafie najlepszej ścieżki według założonego kryterium. Dodatkowym zagadnieniem, jakie pojawia się w tym przypadku jest istnienie pewnego dodatkowego „ruchu” w sieci, symulującego jej wykorzystanie przez innych użytkowników. W opisanym uprzednio grafie zostaje to odzwierciedlone przez losową (rozkład równomierny) zmianę wag poszczególnych krawędzi.

Aby odnaleźć optymalną ścieżkę w grafie wykorzystywane są dwa opracowane przez nas algorytmy. Przede wszystkim podane przez użytkownika parametry łączy są przechowywane w tzw. macierzy przyległości, czyli tablicy dwuwymiarowej. Na podstawie dokonanego przez użytkownika wyboru kryterium poszukiwania drogi do obliczeń wykorzystujemy wartość przepustowości T lub też koszt użycia łącza w pojedynczym cyklu C.

Pierwszy z algorytmów odpowiada za wyznaczenie najkrótszych możliwych dróg z wierzchołka początkowego do wszystkich pozostałych. Jeśli serwer początkowy ze wskazanym serwerem nie ma połączenia bezpośrednio lub pośrednio, to wagą oznaczoną dla takiego wierzchołka jest nieskończoność. Algorytm przebiega po wszystkich węzłach i sprawdza ich łączność z pozostałymi. Jeśli dane wierzchołki nie mają żadnego bezpośredniego połączenia to nie jest wykonywana aktualizacja oznaczonych wcześniej wag. Natomiast, jeżeli dane dwa serwery mają bezpośrednie połączenie i waga w serwerze docelowym jest nieskończona, to jest ona nadpisywana sumą wagi wierzchołka źródłowego i wagi łącza pomiędzy nimi. Natomiast w przypadku, gdy w wierzchołku docelowym znajdowała się waga skończona, to sprawdza się czy obecnie badana ścieżka nie daje w rezultacie wagi mniejszej. Jeśli tak jest, stara wartość jest nadpisywana i jednocześnie sprawdza się, czy indeks wierzchołka początkowego nie jest większy od indeksu wierzchołka docelowego. Gdy ten warunek jest spełniony, to cofamy się z przeszukiwaniem do indeksu wierzchołka docelowego, który staje się początkowym. Wynikiem działania algorytmu jest struktura zawierająca informacje o wartościach najkrótszych dróg łączących pierwszy wierzchołek z pozostałymi (są to wagi tych wierzchołków).

Zadaniem drugiego algorytmu jest na podstawie danego grafu z określonymi wagami węzłów odnaleźć drogę (uszeregowanie) łączącą wierzchołek końcowy z początkowym. Zaczynając od serwera końcowego poruszamy się wstecz po tych ścieżkach, których waga jest równa różnicy wag wierzchołków, które są nią połączone. Operacje te wykonywane są tak długo aż nie dotrzemy do wierzchołka o wadze „0” (czyli początkowego). Wynikiem działania algorytmu jest tablica zawierająca jako kolejne elementy indeksy wierzchołków, składają-cych się na optymalną ścieżkę w grafie.