Projektowanie sieci rozległych
Problemy związane z projektowaniem struktur rozległych sieci komputerowych są istotne z praktycznego punktu widzenia gdyż poprawa wskaźników jakości działania sieci nawet o kilka procent może w dużej sieci obniżyć koszty utrzymania łączy transmisyjnych.
Zadania projektowania sieci WAN
Zadanie wyznaczania przepływów w sieci Flow Assignment (FA).
Zadanie równoczesnego wyznaczania przepływów i przepustowości kanałów Capacity and Flow Assignment (CFA).
Zadanie równoczesnego wyznaczania przepływów, przepustowości i struktury sieci Topology, Capacity and Flow Assignment (TCFA).
Rozwiązanie tych zadań wymaga wprowadzenia odpowiedniego modelu sieci opartego na teorii grafów i teorii masowej obsługi oraz wymaga zastosowania różnych metod optymalizacji.
Wskaźniki jakości sieci WAN
Zadania projektowania sieci WAN rozwiązuje się przy różnych założeniach oraz dla różnych wskaźników jakości działania sieci. Ważniejszych wskaźniki jakości:
średnie opóźnienie pakietu,
koszt budowy sieci,
przepustowość sieci,
parametry niezawodnościowe,
koszt korzystania z usług komunikacyjnych.
Przepływy w sieciach
Podstawowe pojęcia teorii grafów (1)
Grafem zorientowanym nazywamy parę uporządkowaną 
, gdzie N jest zbiorem węzłów, a L jest zbiorem par uporządkowanych określonych na zbiorze N.
Parę uporządkowaną 
nazywamy łukiem zorientowanym węzeł x oznacza początek, a węzeł y koniec łuku.
Przez n oznaczymy liczbę węzłów, a przez p liczbę łuków. Jeżeli L jest zbiorem par nieuporządkowanych, zwanych łukami niezorientowanymi, to graf 
nosi nazwę grafu niezorientowanego. Gdy zbiór L zawiera łuki zorientowane i niezorientowane, to graf 
nazywamy grafem mieszanym.
Grafy niezorientowane i mieszane traktujemy jako szczególny przypadek grafów zorientowanych, ponieważ każdy łuk niezorientowany możemy zastąpić parą łuków zorientowanych w przeciwnych kierunkach.
Grafy, w których każdej uporządkowanej (nieuporządkowanej) parze węzłów przyporządkowano co najwyżej jeden łączący je łuk zorientowany (niezorientowany) nazywamy unigrafami.
Jeżeli każdej uporządkowanej (nieuporządkowanej) parze węzłów może odpowiadać więcej niż jeden łuk zorientowany (niezorientowany), to graf nazywamy multigrafem.
Podstawowe pojęcia teorii grafów (2)
Przez 
będziemy oznaczać zarówno łuk zorientowany jak i łuk niezorientowany, przy czym rodzaj łuku wynika z rodzaju rozważanego grafu.
Łuk 
wychodzący z węzła x i wchodzący do tego węzła nazywamy pętlą.
Graf nazywamy grafem właściwym, jeżeli nie zawiera pętli.
Siecią nazywamy graf właściwy 
wraz z funkcjami określonymi na jego łukach. Sieć będziemy oznaczać w następujący sposób:
,
gdzie 
są funkcjami przyporządkowującymi każdemu łukowi ze zbioru L nieujemną liczbą rzeczywistą.
Niech 
będzie ciągiem różnych węzłów sieci S, takich że 
jest łukiem zorientowanym dla każdego 
. Ciąg węzłów i łuków 
nazywamy trasą od węzła 
do węzła 
.
Trasę, dla której 
nazywamy cyklem.
Niech 
będzie ciągiem różnych węzłów o tej własności, że albo 
albo 
jest łukiem zorientowanym dla każdego 
. Powstały w ten sposób ciąg węzłów i łuków nazywamy ścieżką od węzła 
do węzła 
.
Podstawowe pojęcia teorii grafów (3)
Ścieżka różni się od trasy tym, że możliwa jest różna orientacja łuków w stosunku do orientacji ścieżki wyznaczonej kierunkiem od węzła 
do węzła 
. Łuki 
nazywamy łukami zgodnymi ścieżki, a pozostałe łuki tej ścieżki nazywamy niezgodnymi.
Modelowanie sieci rozległej
Rozległa sieć komputerowa jest siecią w znaczeniu technicznym. Własności tej sieci zostają uwzględnione w jej modelu, którym jest sieć oparta na pojęciach teorii grafów. W takim modelu sieci rozległej łuki odpowiadają kanałom. Łuki zorientowane odpowiadają kanałom jednokierunkowym, a łuki niezorientowane kanałom półdupleksowym. Pary łuków zorientowanych w przeciwnych kierunkach odpowiadają kanałom dupleksowym, ponieważ kanał dupleksowy jest równoważny dwóm kanałom jednokierunkowym pracującym w przeciwnych kierunkach. Zbiór węzłów modelu odpowiada dokładnie węzłom sieci rozległej.
Przepustowości kanałów
Przepustowości kanałów są określone zaleceniami ITU-T lub innych organizacji standaryzujących. Zalecenia te definiują skończony zbiór dostępnych przepustowości kanałów. Koszty dzierżawy kanału zależą przede wszystkim od dwóch czynników: przepustowości kanału i długości łącza transmisyjnego, na którym ten kanał jest zorganizowany.
Koszty dzierżawy kanałów
W modelu sieci rozległej uwzględniamy koszty dzierżawy oraz przepustowości kanałów poprzez wprowadzenie następujących funkcji opisanych na łukach:
funkcja przepustowości łuków; przepustowość łuku 
oznaczymy przez 
,
funkcja kosztów budowy (dzierżawy) łuków; koszt budowy łuku 
oznaczymy przez 
.
Model sieci rozległej
Przez strukturę sieci rozległej rozumiemy schemat rozmieszczenia kanałów. W modelu 
struktura sieci rozległej jest określona przez graf G. Parametry kanałów są w modelu reprezentowane przez funkcje c oraz d. Przepustowość łuku 
odpowiada przepustowości kanału łączącego węzeł x z węzłem y w sieci rozległej. Koszt budowy łuku 
odpowiada kosztowi dzierżawy kanału łączącego węzły x oraz y.
W tak określonym modelu sieci możemy również odwzorować przepływ pakietów. Przepływ wieloskładnikowy w modelu S odpowiada średniemu przepływowi pakietów w rozległej sieci komputerowej w przyjętej jednostce czasu.
Wyznaczania najkrótszej trasy
Problem wyznaczania najkrótszej trasy jest jednym z podstawowych problemów spotykanych w sieciach komputerowych, szczególnie ważny dla algorytmów i protokołów trasowania (routingu). Podstawowy problem wyznaczania najkrótszej trasy polega na znalezieniu najkrótszej drogi z ustalonego źródła s do wierzchołka t dla grafu, w którym wszystkim łukom przypisane są wagi. Wagi mogą reprezentować długość łuków, opóźnienie lub inną wybraną miarę.
Algorytm Dijkstry
Dana jest sieć dana w postaci macierzy wag W=[wij]. Tablica dist zawiera wartości cech węzłów, tablica pred zawiera bezpośredni poprzednik węzła, tablica final zawiera stan węzła, zmienna recent oznacza węzeł, którego cecha została ostatnio ustalona.
Inicjalizacja:
for 
do begin
dist(v)←
; final(v) ←false; pred(v)←-1
end;
dist(s)←0; final(s)←true; recent←s;
Iteracja:
while final(t)=false do begin
for każdego bezpośredniego następnika v węzła recent, jeśli not final(v) do begin
newlabel←dist(recent)+wrecent,v;
if newlabel<dist(v) then begin
dist(v)←newlabel; pred(v)←recent;
end;
end;
znaleźć y - węzeł o najmniejszej cesze tymczasowej, różnej od 
final(y)←true; recent←y;
end;
Przykład zastosowania algorytmu Dijkstry
|
recent |
|
s |
a |
b |
c |
d |
t |
Inicjalizacja |
s |
dist |
0 |
|
|
|
|
|
|
s |
final |
true |
false |
false |
false |
false |
false |
|
s |
pred |
-1 |
-1 |
-1 |
-1 |
-1 |
-1 |
Iteracja 1 |
s |
dist |
0 |
15 |
|
|
9 |
|
|
s |
final |
0 |
false |
false |
false |
true |
false |
|
s |
pred |
-1 |
-1 |
-1 |
-1 |
s |
-1 |
Iteracja 2 |
d |
dist |
0 |
13 |
|
11 |
9 |
|
|
d |
final |
0 |
false |
false |
true |
true |
false |
|
d |
pred |
-1 |
-1 |
-1 |
d |
s |
-1 |
Iteracja 3 |
c |
dist |
0 |
13 |
|
11 |
9 |
18 |
|
c |
final |
0 |
true |
false |
true |
true |
false |
|
c |
pred |
-1 |
c |
-1 |
d |
s |
-1 |
Iteracja 4 |
a |
dist |
0 |
13 |
48 |
11 |
9 |
18 |
|
a |
final |
0 |
true |
false |
true |
true |
true |
|
a |
pred |
-1 |
c |
-1 |
d |
s |
a |
Przepływ pojedynczego składnika (1)
Rozważmy sieć S, której strukturę określa unigraf właściwy i zorientowany 
. Niech s oraz u będą węzłami zbioru N. Przepływem statycznym o wartości v od węzła s do węzła u w sieci S nazywamy funkcję f odwzorowującą zbiór łuków L w zbiór nieujemnych liczb rzeczywistych, której wartości 
przypisane poszczególnym łukom 
spełniają:
|
(1) |
dla każdego 
.
|
(2) |
gdzie
jest zbiorem węzłów sieci, do których prowadzą łuki wychodzące z węzła x,
jest zbiorem węzłów sieci, od których prowadzą łuki skierowane do węzła x.
Wartość 
nazywamy przepływem w łuku 
. Węzeł s nazywamy węzłem źródłowym lub źródłem, a węzeł u nazywamy węzłem docelowym, odpływem lub ujściem. Ograniczenia (1) nazywamy równaniami zachowania przepływu w węzłach, a ograniczenia (2) są związane z nieujemnością przepływów.
Przepływ pojedynczego składnika (2)
Przepływ może spełniać również inne, dodatkowe ograniczenia. Najczęściej stosowanym dodatkowym ograniczeniem jest ograniczenie związane ze skończoną przepustowością łuków:
|
(3) |
Przepływ zerowy, tzn. przepływ dla którego 
i 
, dla każdego 
, spełnia ograniczenia (1-3).
W literaturze formułuje i rozwiązuje się różne zadania związane z przepływami pojedynczego składnika w sieciach. Z punktu widzenia rozległych sieci komputerowych najistotniejsze są dwa zagadnienia: problem maksymalnego przepływu i problem maksymalnego przepływu o minimalnym koszcie.
Problem maksymalnego przepływu
Problem maksymalnego przepływu od węzła s do węzła u polega na maksymalizowaniu zmiennej v przy zachowaniu ograniczeń (1-3). Niech 
oznacza wektor przepływów 
we wszystkich łukach sieci 
. Problem maksymalnego przepływu w sieci S od węzła s do węzła u możemy sformułować w następującej postaci:
|
(4) |
przy ograniczeniach (1-3).
Algorytm wyznaczania maksymalnego przepływu
Niech Q i Z będą rozłącznymi podzbiorami zbioru węzłów N. Przez 
oznaczymy zbiór wszystkich łuków 
takich, że xQ i yZ. Niech 
będzie dopełnieniem zbioru Q w zbiorze węzłów N.
Przekrojem rozdzielającym węzeł 
od węzła 
nazywamy zbiór łuków 
gdzie 
oraz 
. Przepustowość przekroju, oznaczana przez 
, jest równa sumie przepustowości łuków ze zbioru 
. Przekrój 
nazywamy przekrojem minimalnym rozdzielającym węzeł sQ od węzła u
, jeżeli jego przepustowość jest najmniejsza spośród przepustowości wszystkich możliwych przekrojów rozdzielających węzły s i u.
Idea algorytmu wyznaczania maksymalnego przepływu opiera się na następującym twierdzeniu udowodnionym przez Forda i Fulkersona:
W dowolnej sieci wartość maksymalnego przepływu z węzła s do węzła u jest równa przepustowości minimalnego przekroju rozdzielającego s od u.
Postępowanie zaczynamy od nadania cech węzłom sieci. Cecha ma postać 
lub 
, 
, jest dodatnią liczbą całkowitą lub . W trakcie Fazy I węzeł sieci może być nieocechowany, ocechowany i sprawdzony lub ocechowany i niesprawdzony. Na początku węzły są nieocechowane. Cecha nadana węzłowi x zawiera dwa elementy: znacznik pozwalający określić ścieżkę od s do x, ilość jednostek składnika do przesłania tą ścieżką od s do x.Algorytm Forda-Fulkersona
Postępowania A proces cechowania
Krok 1. Źródłu s nadajemy cechę 
. Węzeł s staje się węzłem ocechowanym i niesprawdzonym.
Krok 2. Wybieramy dowolny niesprawdzony węzeł x ocechowany za pomocą 
.
a) Wszystkim nieocechowanym węzłom y takim, że 
nadajemy cechę 
, gdzie 
.
b) Wszystkim nieocechowanym węzłom y takim, że 
nadajemy cechę 
, gdzie 
.
Węzeł x staje się węzłem ocechowanym i sprawdzonym.
Krok 3. Jeżeli ujście u zostało ocechowane, to przejść do Fazy II. Jeżeli istnieje w sieci węzeł ocechowany i niesprawdzony, to przejść do kroku 2. W przeciwnym razie kończymy obliczenia. Wyznaczony przepływ jest przepływem maksymalnym od węzła s do węzła u.
Postępowania B zmiana przepływu
Krok 1. Jeżeli ujście u otrzymało cechę 
, to podstawić 
. Jeżeli ujście u otrzymało cechę 
to podstawić 
.
Krok 2. Jeżeli węzeł y otrzymał cechę 
, to podstawić 
. Jeżeli węzeł y otrzymał cechę 
, to podstawić 
.
Krok 3. Jeżeli wyznaczony w kroku 2 węzeł x jest taki, że x=s, to należy odrzucić stare cechy i przejść do Fazy I. W przeciwnym razie podstawić y=x i przejść do kroku 2.
Przykład zastosowania algorytmu Forda-Fulkersona
|
Postępowanie A
s←(-, |
Postępowanie B (nasycanie przepływu) |
a←(s+,3), c←(a+,1), |
a←(s+,2), b←(a+,2), d←(b+,2), e←(d+,2), f←(e+,2), t←(f+,2) |
d←(s+,10), e←(d+,6), |
d←(s+,7), e←(d+,3), a←(e-,1), b←(d+,5), c←(b+,1), f←(c+,1), t←(f+,1) |
d←(s+,6), b←(d+,4), a←(b-,4), e←(d+,3) |
Przekrój Maksymalny przepływ v=11 |
Zastosowania problem maksymalnego przepływu
Wyznaczenie maksymalnej liczby bitów jaką można przesłać między parą węzłów sieci, zakładając, że w tym samym czasie nie ma transferu danych między pozostałymi parami węzłów.
Wyznaczenie maksymalnej liczby różnych tras między parą węzłów sieci rozległej. Dwie trasy prowadzące z węzła s do węzła u są różne jeśli, poza s i u, nie zawierają tych samych węzłów i kanałów.
Wyznaczanie maksymalnej liczby różnych tras
Każdemu węzłowi sieci rozległej odpowiadają w modelu dwa węzły oraz jeden dodatkowy łuk. Rozważmy węzeł x sieci rozległej. W modelu jest on reprezentowany przez węzły x' i x'' oraz łuk 
. Wszystkie kanały, które dochodzą do węzła sieci rozległej są reprezentowane w modelu przez łuki dochodzące do węzła x', a wszystkim kanałom wychodzącym z węzła x sieci rozległej odpowiadają łuki wychodzące z węzła x''. Każdemu łukowi modelu przypisujemy przepustowość równą jedności. Maksymalna liczbę różnych tras od węzła s do węzła u równa się maksymalnemu przepływowi od węzła s'' do węzła u'.
Przepływ wieloskładnikowy (1)
Przepływ wieloskładnikowy odpowiada średniemu przepływowi pakietów w rozległej sieci komputerowej w przyjętej jednostce czasu. Przez składnik rozumiemy zbiór pakietów mających ten sam węzeł źródłowy i ten sam węzeł docelowy. Przez 
oznaczymy średnie natężenie strumienia pakietów kierowanych z węzła i do węzła j wyrażone w pakietach/s, a przez 1/ oznaczymy średnią długość pakietu w bitach/pakiet. Zatem 
jest średnim natężeniem strumienia bitów kierowanych od węzła i do węzła j wyrażonym w bitach/s. Przez 
oznaczymy macierz elementów 
nazywaną macierzą natężeń z zewnątrz wprowadzanych.
Ponumerujemy wszystkie składniki od 1 do q. Z k-tym składnikiem jest związana para węzłów 
i 
jako źródło i ujście. Przez 
oznaczymy średnie natężenie k-tego składnika, tzn. 
, gdzie 
, 
; 
nazywamy również wartością k-tego składnika.
Niech S będzie siecią, której strukturę określa unigraf właściwy i zorientowany 
. Przepływem wieloskładnikowym w sieci S realizującym macierz z zewnątrz wprowadzanych natężeń R nazywamy zespół funkcji
,
których wartości 
przypisane poszczególnym łukom 
spełniają następujący układ warunków:
Przepływ wieloskładnikowy (2)
|
(5) |
dla każdego 
.
|
(6) |
nazywamy przepływem k-tego składnika w łuku 
. Oznaczmy przez 
sumaryczny przepływ w łuku 
.
|
(7) |
Często wprowadza się dodatkowe ograniczenie na przepływ wieloskładnikowy, związane ze skończoną przepustowością łuków
|
(8) |
Przepływ wieloskładnikowy bez rozgałęzień
Ważną klasą przepływów wieloskładnikowych są wieloskładnikowe przepływy bez rozgałęzień nazywane też przepływami bez rozgałęzień. Przepływ bez rozgałęzień to taki przepływ wieloskładnikowy, w którym każdy składnik przepływa od swojego źródła do ujścia wzdłuż tylko jednej trasy. Przykłady: ATM, X.25, Frame Relay, MPLS.
Przepływy z rozgałęzieniami zakładają możliwość przesyłania składnika wieloma różnymi trasami jednocześnie. Przykłady: IP, IPX,
Kryteria optymalizacji przepływów
Z punktu widzenia rozległych sieci komputerowych najistotniejsze dwa kryteria optymalizacji przepływów wieloskładnikowych:
średnie opóźnienie pakietu T,
koszt korzystania z usług komunikacyjnych K.
Średnie opóźnienie pakietu wyrażone jest zależnością (Kleinrock)
|
(9) |
gdzie 
jest natężeniem sumarycznego strumienia pakietów wprowadzanych do sieci. Średnie opóźnienie pakietu ma zazwyczaj wymiar s/pakiet. Zależność (9) określono przy pewnych założeniach.
W celu sformułowania problemu optymalizacji przepływów wieloskładnikowych ze względu na koszt wprowadźmy zespół funkcji
zwanych funkcjami kosztu przepływu. Wartości funkcji 
przypisane poszczególnym łukom 
nazywamy kosztami przepływu jednostki i-tego składnika po łuku 
. Koszty przepływu 
mogą mieć różną interpretację fizyczną, np. opłaty za korzystanie z łączy, miary niezawodnościowe.
Koszt korzystania z usług komunikacyjnych K określa zależność
|
(10) |
Metodologia projektowania sieci rozległych
Budowa rozległej sieci komputerowej jest przedsięwzięciem złożonym. Po to, aby sieć rozległa spełniła oczekiwania użytkownika, powinna zostać zaplanowana i wykonana w oparciu o szczegółowo opracowany plan działań. Czynności wykonywane od planowania do realizacji sieci rozległej można podzielić na trzy kolejne etapy:
etap wstępnego rozpoznania,
etap projektowania,
etap instalacji i wdrożenia.
Etap wstępnego rozpoznania
Podstawowym celem tego etapu jest zebranie wiadomości o użytkowniku, niezbędnych do wykonania projektu sieci rozległej. Pod pojęciem użytkownika rozumiemy tu podmiot, dla którego sieć rozległa jest realizowana. Może to być przedsiębiorstwo, bank czy też urząd administracji państwowej. Na podstawie uzyskanych danych powinniśmy na tym etapie ocenić celowość budowy rozległej sieci komputerowej. Etap wstępnego rozpoznania ma podetapy:
Przygotowania danych. Polega to na zebraniu potrzebnych informacji (np. o użytkowniku, inwentaryzacji, wymaganiach, natężeniu strumieni bitów, ) oraz na dokonaniu ich analizy i przygotowaniu raportu końcowego.
Ocena celowości przedsięwzięcia. Etap konieczna dla podjęcia ostatecznej decyzji co do budowy sieci rozległej.
Etap projektowania
Po podjęciu decyzji, co do budowy sieci rozległej możemy przystąpić do jej projektowania. W trakcie prac projektowych musimy uwzględnić uzgodnienia dokonane podczas konsultacji z przyszłym użytkownikiem na poprzednim etapie. Zwłaszcza rozległa sieć komputerowa musi zostać tak zaprojektowana, aby jej koszt nie przekroczył wcześniej uzgodnionego i zatwierdzonego budżetu.
Do zadań, które powinny być wykonane na etapie projektowania rozległej sieci komputerowej należą:
określenie lokalizacji węzłów,
ustalenie sposobu i miejsca dostępu do sieci rozległej dla wszystkich lokalizacji,
wybór protokołu komunikacyjnego,
wyznaczenie struktury sieci,
określenie sposobu dołączenia sieci prywatnej do publicznej sieci rozległej,
ustalenie stopnia ochrony danych przesyłanych w sieci,
dokonanie oceny dostępnego sprzętu i wybór platformy sprzętowej,
opracowanie schematu adresacji dla poszczególnych lokalizacji użytkownika,
ustalenie sposobu zarządzania siecią,
przygotowanie projektu sieci rozległej w postaci raportu.
Etap instalacji i wdrażania
Prace związane z instalacją i wdrażaniem sieci rozległej polegają na zgromadzeniu wszystkich elementów sprzętowo-programowych sieci, zainstalowaniu, testowaniu i doprowadzeniu sieci do stanu gotowości do rozpoczęcia działania. Na tym etapie mogą zastać zamienione elementy sieci przyjęte w projekcie. Równocześnie można jeszcze wprowadzić dodatkowe elementy, których nie przewidziano do zastosowania na poprzednim etapie. Jednak wszelkie zmiany powinny być uzgodnione i zatwierdzone przez użytkownika.
Podstawowe czynności wykonywane na tym etapie są następujące:
zaplanowanie implementacji sieci,
instalacja sprzętu i oprogramowania,
testowanie sieci,
opracowanie dokumentacji,
przeprowadzenie szkoleń.
Zakończenie instalacji i wdrażania sieci rozległej umożliwia przejście do etapu jej normalnej pracy. Jednak z czasem może się pojawić potrzeba modernizacji sieci. W miarę rozwoju lokalizacji użytkownika mogą okazać się konieczne zmiany w rozległej sieci komputerowej. W związku z tym, pożądana staje się ciągła współpraca administratora sieci rozległej z firmą, która tę sieć projektowała i wdrażała.
(19)
Projektowanie sieci WAN.
K. Walkowiak, SK
Wyszukiwarka