POLITECHNIKA RZESZOWSKA
Im. Ignacego A
ukasiewicza
WYDZIAA
ELEKTROTECHNIKI I INFORMATYKI
ZAKA
AD SYSTEMÓW ROZPROSZONYCH
METODY I RODKI
PROJEKTOWANIA
SIECI KOMPUTEROWYCH
PRACA DYPLOMOWA IN YNIERSKA
PROMOTOR: AUTORZY:
dr hab inz. Mach SÅ‚awomir
Georgy Loutsky prof PRz Maci ga Jacek
Rzeszów, 2002 r.
=D SRPRF XG]LHORQ Z QDSLVDQLX WHM SUDF\ V]F]HJyOQH
SRG]L NRZDQLD SUDJQLHP\ VNLHURZDü SURPRWRURZL
3DQX GU KDE LQ *HRUJ\ /RXWVN\ SURI 35] RUD] MHM
UHFHQ]HQWRZL 3DQX GU LQ 0LURVáDZ +DMGHU
1
Wst p................................................................................................................................................. 5
Cel i zakres pracy ............................................................................................................................. 6
1. Ogólne zasady projektowania................................................................................................. 7
1.1. Etapy projektowania sieci ..................................................................................................... 7
1.1.1. Opracowanie zało e projektowych ..................................................................8
1.1.2. Analiza wymaga projektowych........................................................................8
1.1.3. Projektowanie logiczne i fizyczne .....................................................................8
2. Media ........................................................................................................................................ 9
2.1. Media przewodowe ............................................................................................................. 10
2.1.1. Media elektryczne ............................................................................................10
2.1.1.1. Kategorie i klasy skr tek ........................................................................................ 10
2.1.2. Media optyczne ................................................................................................11
2.1.2.1. Budowa kabla wiatłowodowego........................................................................... 12
2.1.2.1.1. Podstawowe typy wiatłowodów...................................................................... 13
2.1.2.1.2. wiatłowód jednomodowy ............................................................................... 13
2.1.2.1.3. wiatłowód wielomodowy ............................................................................... 14
2.2. Media bezprzewodowe........................................................................................................ 15
3. Topologie ................................................................................................................................ 16
3.1. Topologia logiczna.............................................................................................................. 16
3.2. Topologia fizyczna .............................................................................................................. 17
3.2.1. Terytorialna klasyfikacja sieci komputerowych ..............................................17
3.2.1.1. Topologie komputerowych sieci WAN i MAN ..................................................... 18
3.2.1.1.1. Topologia kratowa............................................................................................ 18
3.2.1.1.2. Topologia toroidalna......................................................................................... 18
3.2.1.2. Sieci szkieletowe .................................................................................................... 19
3.2.2. Topologie komputerowych sieci lokalnych .....................................................20
3.2.2.1. Topologia magistrali (szynowa)............................................................................. 20
3.2.2.2. Topologia pier cienia ............................................................................................. 21
3.2.2.3. Topologia gwiazdy ................................................................................................. 22
3.2.2.4. Topologie zło one.................................................................................................. 22
4. Reguły doboru trasy .............................................................................................................. 24
4.1. Podział reguł doboru trasy................................................................................................... 24
4.1.1. Parametry charakteryzuj ce reguł doboru trasy .............................................27
4.1.1.1. Czas przechodzenia pakietu przez kanał ................................................................ 28
4.2. Metody znajdowania tras najkrótszych ............................................................................... 29
4.2.1. Definicja grafu .................................................................................................29
1.1.1.1. Graf skierowany ..................................................................................................... 29
4.2.1.2. Suma grafów .......................................................................................................... 29
4.2.1.3. Graf spójny............................................................................................................. 29
4.2.1.4. S siedztwo.............................................................................................................. 29
4.2.1.5. Macierz s siedztwa................................................................................................. 30
4.2.2. Minimalne drzewa rozpinaj ce ........................................................................30
4.2.2.1. Algorytm Kruskala................................................................................................. 31
4.2.2.2. Algorytm Prima...................................................................................................... 33
4.2.3. Najkrótsze cie ki z jednym ródłem ..............................................................36
4.2.4. Najkrótsza cie ka mi dzy par wierzchołków ...............................................37
4.2.5. Najkrótsze cie ki mi dzy wszystkimi parami wierzchołków.........................38
4.2.5.1. Algorytm Dijkstry .................................................................................................. 39
4.2.5.2. Algorytm Bellmana  Forda................................................................................... 41
4.2.6. Maksymalizacja przepływów...........................................................................44
2
4.2.6.1. Sieci przepływowe i przepływy ............................................................................. 45
4.2.6.2. Sieci z wieloma ródłami i uj ciami....................................................................... 47
4.2.6.3. Algorytm Forda-Fulkersona................................................................................... 48
4.2.6.3.1. Opis działania algorytmu.................................................................................. 48
4.2.6.3.2. Wynajdowanie drogi......................................................................................... 49
4.2.6.3.3. Transformacja grafu ......................................................................................... 50
5. Minimalizacja sieci o strukturze drzewiastej...................................................................... 54
5.1. Doł czenie w zła o najmniejszym koszcie ł czenia ........................................................... 55
5.1.1. Przykład doł czenie w zła o najmniejszym koszcie ł czenia..........................56
5.2. Metoda odwróconego drzewa ............................................................................................. 58
5.2.1. Algorytm odwróconego drzewa.......................................................................59
5.3. Metoda Essau-Williamsa..................................................................................................... 60
5.3.1. Algorytm optymalizacyjny wykorzystuj cy zasad najszybszego przyrostu ..61
5.3.2. Koszt tworzenia sieci .......................................................................................61
5.3.3. Algorytm Essau-Williamsa ..............................................................................62
5.3.4. Przykładowe rozwi zanie metod Essau-Williamsa........................................63
6. Optymalizacja topologii sieci ................................................................................................ 66
6.1. Problem optymalizacji topologicznej.................................................................................. 66
6.2. Funkcja kryterialna optymalizacji. ...................................................................................... 66
6.3. Realizacja sieci o danej symetrycznej macierzy przepustowo ci........................................ 67
6.4. Realizacja sieci na podstawie sieci macierzy symetrycznej................................................ 68
6.5. Optymalizacja sieci o danej symetrycznej macierzy przepustowo ci. ................................ 69
6.6. Metoda  dziel i zwyci aj . ................................................................................................ 70
6.6.1. Opis poszczególnych kroków minimalizacji ...................................................72
7. Metoda dost pu do Å‚ cza CSMA/CD ................................................................................... 74
7.1. Algorytm stacji nadaj cej.................................................................................................... 74
8. Powi zania mi dzy routingiem a modelem OSI ................................................................. 77
8.1. Warstwowy model sieci OSI............................................................................................... 77
8.1.1. Warstwa Å‚ cza danych......................................................................................78
8.1.2. Warstwa sieci ...................................................................................................79
8.1.3. Przykład działania modelu OSI........................................................................80
8.2. Podstawowe poj cia na temat routingu ............................................................................... 81
8.2.1. Funkcje routera.................................................................................................81
8.2.2. Zasada działania routera...................................................................................82
9. Protokoły routingu................................................................................................................. 85
9.1. Protokoły trasowane a protokoły routingu .......................................................................... 86
9.2. Routing wieloprotokołowy.................................................................................................. 86
9.3. Klasy protokołów routingu.................................................................................................. 87
9.3.1. Routing wektora odległo ci..............................................................................87
9.3.2. Routing stanu Å‚ cza ..........................................................................................88
9.3.3. Przedstawienie odległo ci za pomoc metryki ................................................89
9.3.4. Podstawowe czynno ci zwi zane z wyszukiwaniem tras ................................92
9.3.5. Wyszukiwanie tras ...........................................................................................94
1.1.1.1. Wyszukiwanie trasy krok po kroku........................................................................ 95
9.3.5.2. cie ki równoległe ................................................................................................. 96
9.3.6. Rola podziału sieci ...........................................................................................98
9.3.7. Poison reverse i aktualizacje wymuszone........................................................99
9.4. Protokoły routingu IP ........................................................................................................ 100
9.4.1. Optymalna trasa .............................................................................................101
3
9.4.2. Prostota i wydajno ć ......................................................................................101
9.4.3. Odporno ć ......................................................................................................101
9.4.4. Nagła zbie no ć .............................................................................................102
9.4.5. Elastyczno ć...................................................................................................103
9.4.6. Routing statyczny...........................................................................................103
9.4.7. Routing dynamiczny ......................................................................................103
9.4.8. Metody routingu.............................................................................................104
9.4.9. Konfiguracja routingu IP................................................................................104
9.4.10. Opis protokołu routingu IGRP.......................................................................105
9.4.10.1. Porównanie wewn trznych i zewn trznych tras IGRP .................................... 106
9.4.10.2. Zasada podzielonych sieci ............................................................................... 107
9.4.10.3. Uaktualnienia niepoprawnej odpowiedzi......................................................... 107
9.4.10.4. Informacje dostarczane IGRP przez metryki ................................................... 108
9.4.10.5. Uaktualnienia IGRP ......................................................................................... 108
9.4.10.6. Maksymalna liczba skoków............................................................................. 109
10. Zastosowanie routingu w sieci LAN................................................................................... 110
10.1. Ogólny opis problematyki segmentacja sieci LAN ...................................................... 110
10.2. Segmentacja przy u yciu routerów ............................................................................... 111
10.2.1. Zastosowanie routerów do budowy skalowalnych sieci ................................113
10.2.2. Wykorzystanie routerów do nadawania struktury logicznej..........................115
10.3. Zastosowanie routingu w sieciach wirtualnych ............................................................ 115
1.1.1. Scentralizowany routing w sieciach VLAN...................................................115
10.3.2. Brzegowy routing w sieciach VLAN.............................................................116
10.3.3. Wykorzystanie sieci VLAN do zapewnienia bezpiecze stwa .......................118
11. Podsumowanie...................................................................................................................... 119
12. Literatura ............................................................................................................................. 120
4
WST P
W dobie dzisiejszej cywilizacji okre lanej mianem cywilizacji informacji bardzo
wa nym czynnikiem decyduj cym o pozycji, czy wr cz istnieniu firmy na rynku, jest
szybki przepływ informacji. W ostatnich latach bardzo dynamicznie rozwijaj si techniki
zarz dzania, oparte na systemach informatycznych. Poci ga to za sob konieczno ć prze-
syłu coraz wi kszych ilo ci danych. Bardzo du o aplikacji wspieranych jest technikami
multimedialnymi, które wymagaj niezawodnych sieci o du ych przepływno ciach.
Dzi ki dynamicznemu rozwojowi technik informatycznych i technologii układów scalo-
nych, mo liwy jest stały rozwój sieci komputerowych, zarówno rozległych obejmuj cych
swoim zasi giem poszczególne kraje i całe kontynenty, jak i lokalnych, budowanych dla
potrzeb jednej instytucji.
Sieci komputerowe bez wzgl du na ich rozległo ć i wiadczone usługi, s syste-
mami bardzo skomplikowanymi. Prawidłowe ich funkcjonowanie, wymaga ju na etapie
opracowywania projektu uwzgl dnienia zasad zarówno wymiany informacji na ró nych
poziomach ogólno ci, jak te sposobu prezentacji przesyłanych wiadomo ci. Od sieci
komputerowej, tak jak od ka dego systemu komputerowego oczekujemy wysokiej efek-
tywno ci, a zwłaszcza wysokiej efektywno ci na koszt jednostkowy [5]. Projektowana
sieć powinna zapewniać uniwersalne, wydajne, sprawiedliwe, trwałe i wysokoefektywne
poł czenie mi dzy du liczb komputerów. Aby sprostać tym wymaganiom stworzone
zostały ogólne ramy dla projektów, zwane architektur sieci QHWZRUN DUFKLWHFWXUH które
steruj projektowaniem i implementacj sieci. Wprowadzone zostały poziomy abstrakcji,
które ujmuj wybrane aspekty systemu, umieszczaj c je w obiekcie zapewniaj cym inter-
fejs, który daje si stosować przez inne składniki systemu, ukrywaj c jednocze nie szcze-
góły implementacji obiektu przed u ytkownikiem. Abstrakcja prowadzi do pojawienia si
warstwy, szczególnie w systemach sieciowych. Podział na warstwy ma dwie zalety. Po
pierwsze sprawia, e budowanie sieci rozkłada si na elementy, a po drugie daje projekt
maj cy bardziej modularny charakter. Dzi ki takiemu rozwi zaniu przy wprowadzaniu
nowej usługi, musimy tylko zmodyfikować funkcje w jednej warstwie. W systemie sie-
ciowym obiekty abstrakcyjne zwane s protokołami [5].
5
Cel i zakres pracy
Celem naszej pracy jest przybli enie niektórych aspektów projektowania sieci
komputerowych. W poszczególnych rozdziałach omówili my kolejno ogólne zasady pro-
jektowania, media stosowane do budowy sieci komputerowych  po wi caj c nieco wi cej
miejsca medium przewodowemu, jakim jest kabel wiatłowodowy. Trzeci rozdział to
omówienie topologii sieci komputerowych, kryterium podziału sieci na sieci WAN, MAN,
LAN. W kolejnych rozdziałach pokazali my reguły doboru tras, poprzez minimalizacj
drzewa rozpinaj cego przy zastosowaniu algorytmów Kruskala, Prima, Dijkstry, Forda
Bellmana oraz sposoby maksymalizacji przepływów z zastosowaniem algorytmu Forda
Fulkersona. Rozdział siódmy to przybli enie działania algorytmu wielodost pu do ł cza z
wykrywaniem kolizji CSMA/CD. Kolejnym tematem jest omówienie warstwowego mode-
lu sieci OSI. Stanowi to baz wyj ciow niezb dn do przybli enia mechanizmów routin-
gu. Protokoły routingu, zasady wyszukiwania tras, podział sieci na podsieci, podstawowe
funkcje routera, jak równie tworzenie wirtualnych sieci to tematy dwu ostatnich rozdzia-
łów naszej pracy.
6
1. OGÓLNE ZASADY PROJEKTOWANIA
Projektowaniem nazywamy zalgorytmizowany proces tworzenia obiektu o ci le okre-
lonych cechach fizycznych. Proces projektowania nie podlega formalizacji.
O procesie projektowym decyduje wiele czynników mi dzy innymi: technologia, charakte-
rystyki techniczne, ergonomia, estetyka. Sam proces projektowania nie mo e zostać jedno-
znacznie sformalizowany gdy ka dy projektowany obiekt wymaga indywidualnego roz-
patrzenia ze wzgl dów technicznych, ekonomicznych oraz oczekiwa u ytkowników.
Przy projektowaniu sieci nale y uwzgl dnić nast puj ce zało enia ogólne:
x Sieć powinna pracować bez opó nie (tolerancja opó nienia w granicach 3-5 se-
kund)
x Sieć nie powinna mieć adnych ogranicze zwi zanych z protokołami i interwor-
kingiem, jednak w swoim rdzeniu musi być sieci jednoprotokołow .
x Sieć powinna pracować bez bł dów
x Sieć powinna posiadać nieograniczon dost pno ć (powinna pracować ci gle i bez
przestojów). W tym celu system sieciowy powinien być odporny na uszkodzenia 
posiadać spójno ć technologiczn .
x Sieć powinna posiadać wysoki poziom bezpiecze stwa i prywatno ci.
x Powinna być prosta w u yciu (niezb dne jest okre lenie kompromisu pomi dzy
wysokim poziomem bezpiecze stwa i prostot wu yciu)
x W projekcie nale y uwzgl dnić zapis dotycz cy wykonania pełnej dokumentacji
powykonawczej (przebiegi trasowe, pomiary powykonawcze).
1.1. Etapy projektowania sieci
Ka dy proces projektowy składa si z sekwencyjnego wykonywania procesów analizy,
syntezy i oceny. Je eli pierwszym z procesów jest analiza projektowanie takie okre lamy
terminem wschodz cego. Polega ono na okre leniu charakterystyk konkretnego obiektu a
nast pnie na ich uszczegóławianiu. Analiza wykonywana jest najcz ciej z wykorzysta-
niem modeli empirycznych, symulacyjnych, b d analitycznych.
Synteza to proces tworzenia nowego obiektu na bazie elementarnych obiektów o ci le
okre lonych charakterystykach.
Proces projektowania składa si z: opracowania zało e projektowych, analizy wyma-
ga projektowych oraz projektowania logicznego i fizycznego.
7
1.1.1. Opracowanie zało e projektowych
Podstawowym znaczeniem przy okre laniu wymaga projektowych ma rozpoznanie pro-
filu firmy oraz oczekiwa u ytkowników systemu, pod k tem aplikacji, które maja praco-
wać w projektowanej sieci, jak równie okre lenia mo liwo ci rozbudowy istniej cej sieci.
Nie mo na pomin ć w przypadku projektowania sieci rozległych wpływu istniej cego ro-
dowiska telekomunikacyjnego.
Opracowanie zało e technicznych mo e być prowadzone jedn z trzech metod:
x Intuicyjna  stosowana głównie przy projektowaniu obiektów powtarzalnych (np.
przy budowie sieci hipermarketów)
x Wywiadów z u ytkownikami  oparta jest na opiniach u ytkowników danego sys-
temu w powi zaniu z ich oczekiwaniami dotycz cymi jego poprawy. Nale y tutaj
uwzgl dnić fakt, e dopiero około 40% poprawa działania sieci, zostaje zauwa one
przez jej u ytkowników.
x Testy laboratoryjne  polega ona na symulacji rzeczywistego funkcjonowania sieci
w warunkach laboratoryjnych, lub w oparciu o ocen pracy sieci na urz dzeniach
wynaj tych od producenta.
1.1.2. Analiza wymaga projektowych
W analizie kosztowej nale y uwzgl dnić takie elementy jak : koszty projektu (ewentu-
alne uzgodnienia i zezwolenia w przypadku konieczno ci uzyskania pozwolenia na budo-
w od wła ciwych organów administracyjnych) , koszty sprz tu i okablowania, wydatki
zwi zane z modernizacj pomieszcze oraz urz dze i sieci zasilaj cej. W ogólnych kosz-
tach przewidzieć nale y równie szkolenie personelu, wydatki zwi zane z administracj
sieci, jak równie wzrost zu ycia energii elektrycznej.
1.1.3. Projektowanie logiczne i fizyczne
Projektowanie logiczne (projektowanie przepływów, protokołów, serwisów i usług
oraz adresacji i routingu). Projektowanie fizyczne (projektowanie rozprowadzenia okablo-
wania, przył czenia do intersieci). Te zagadnienia s szerzej omawiane w dalszej cz ci
pracy.
8
2. MEDIA
Ka da komunikacja pomi dzy komputerami, wymaga kodowania danych w jak po-
stać energii i przesłania jej za pomoc medium transmisyjnego. Medium transmisyjnym,
okre lamy rodowisko wykorzystywane do przesyłania informacji, pomi dzy nadawc i
odbiorc [10].
W sieciach typu Ethernet mo na stosować ró norodne rodzaje mediów transmisyjnych. Ich
wybór opiera si o kilka cech, które nale y rozwa yć projektuj c sieć [15]:
x wymagania szeroko ci pasma aplikacji i u ytkownika,
x perspektywy rozwoju sieci,
x odległo ci mi dzy systemami komputerów,
x rodowisko geograficzne (kabel, transmisja radiowa lub satelitarna),
x wymagana tolerancja bł du  zdolno ć sieci do funkcjonowania pomimo powa nej
awarii, najcz ciej jest funkcj topologii sieci,
x rodowisko  rodzaj i moc zakłóce generowanych przez otoczenie,
x cena.
Je eli pomi dzy nadawc i odbiorc istnieje kanał z ciała stałego, to medium takie okre-
lamy mianem przewodowego, w przeciwnym wypadku mówimy o medium bezprzewo-
dowym.
Podział ten mo na rozgraniczyć na podstawie okre lenia pasma cz stotliwo ci:
Media przewodowe:
1. Elektryczne pracuj ce w pa mie cz stotliwo ci do 2MHz
2. Optyczne pracuj ce w zakresie długo ci fal 850  1550 nm. tj. około 190THz
Media bezprzewodowe [9]:
1. Optyczne sieci bezprzewodowe  wykorzystuj te same długo ci fal, co kable wia-
tłowodowe ( niewidzialna fala wietlna na poziomie od 1350 -1550 nm.)
2. Radiowe sieci bezprzewodowe  pracuj ce w zakresie 900 MHz  40 GHz (28
GHz jest cz stotliwo ci standaryzowan ).
9
2.1. Media przewodowe
Media przewodowe mo emy podzielić na media elektryczne oraz media optyczne.
2.1.1. Media elektryczne
W konwencjonalnych sieciach komputerowych kable s podstawowym medium Å‚ -
cz cym komputery. Uwarunkowane jest to ich stosunkowo nisk cen oraz Å‚atwo ci insta-
lacji. W chwili obecnej ze wzgl du na ograniczenie szybko ci, niewygodny sposób instala-
cji, słab skalowalno ć i trudno ć w lokalizacji usterki nie stosuje si kabli koncentrycz-
nych. Szeroko stosowana jest skr tka komputerowa. Dzi ki zastosowaniu ustalonych roz-
wi za , okablowanie skr tkowe, charakteryzuje si du niezawodno ci .
Skr tka współpracuje z technologiami 10Mbit, 100Mbit, 1Gbit ethernet, ATM, przy czym
maksymalna długo ć kabla wynosi 100 m, a maksymalna ilo ć komputerów w segmencie
1024.
2.1.1.1. Kategorie i klasy skr tek
W celu okre lenia charakterystyk, kable skr tkowe podzielono na kategorie
uwzgl dniaj ce liczb par skr tki oraz maksymaln cz stotliwo ć sygnału no nego.
Podział ten, w standardzie EIA/TIA 586 Commercial Building Wiring przedstawia si na-
st puj co[11]:
Kat. 1  (klasa A) tradycyjna nieekranowana skr tka telefoniczna przeznaczona do przesy-
łania głosu (64kb/s) w zasadzie nie przystosowana do transmisji danych
Kat. 2  (klasa B) skr tka nieekranowana o szybko ci transmisji do 1MHz
Kat. 3  (klasa C) czteroparowa skr tka stosowana głównie w sieciach Ethernet 10Base-T
o szybko ci transmisji do 10MHz.
Kat. 4  (klasa C) skr tka działaj ca z szybko ci do 16MHz stosowana głównie w sie-
ciach Token Ring.
Kat. 5  (klasa D) pozwalaj ca na transmisj danych z szybko ci 100MHz na odległo ć
100m.
10
Kat. 6  (klasa E) pozwalaj ca na transfer danych do 300MHz
Kat. 7  (klasa F) transmisja z szybko ci do 600MHz
Ze wzgl du na sposób wykonania skr tk komputerow podzielić mo na na kable
typu [11] :
x UTP (Unshielded Twisted Pair)  skr tka nieekranowana ze zmiennym splotem (1
zwój na 6-10 cm)
x FTP  (Foiled Twisted Pair) skr tka ekranowana za pomoc folii aluminiowej (fo-
liowana para , foliowany kabel) , z przewodem lub bez przewodu uziemiaj cego.
x STP (Shielded Twisted Pair)  posiada zewn trzny ekran w postaci oplotu. Jest
bardziej odporna na zakłócenia impulsowe oraz szkodliwe przeniki zbli ne i zdalne
x S-STP  (Screened STP) najnowszy typ miedzianych kabli skr tkowych, przysto-
sowany do do wysokich przepustowo ci (kat. 7), ka da para jest foliowana (lub
ekranowana) oddzielnie, a dodatkowo cały kabel ekranowany oplotem miedzia-
nym, lub foli aluminiow . W celu uzyskania wy szych przepływno ci stosuje si
przewody miedziane o wy szej rednicy.
2.1.2. Media optyczne
Do ł czenia sieci komputerowych, oprócz opisanych wy ej kabli miedzianych, u ywa
si równie kabli wiatłowodowych. W wiatłowodach do transmisji informacji wykorzy-
stywana jest wi zka wiatła, która jest odpowiednikiem pr du w kablach miedzianych.
Wi zka ta jest modulowana zgodnie z tre ci przekazywanych informacji. Transmisja
wiatłowodowa polega na przepuszczeniu przez szklane włókno wi zki wiatła generowa-
nej przez diod lub laser (emisja fotonów). Wi zka ta to zakodowana informacja binarna,
rozkodowywana nast pnie przez fotodekoder na ko cu kabla. wiatłowód w przeciwie -
stwie do kabli miedzianych, nie wytwarza pola elektromagnetycznego. Główn wad tego
medium jest łatwa mo liwo ć przerwania kabla, a jego ponowne zł czenie jest bardzo
kosztowne.
Mo na wyró nić wiatłowody do poł cze zewn trznych i wewn trznych oraz wielomo-
dowe i jednomodowe [6].
11
2.1.2.1. Budowa kabla wiatłowodowego.
W chwili obecnej do realizacji wiatłowodów wykorzystuje si praktycznie wył cz-
nie szkło kwarcowe. Materiał powinien charakteryzować si nadzwyczajn czysto ci .
Dzi ki temu absorpcja materiałowa, b d ca podstawow przyczyn tłumienia, jest mini-
malna.
wiatłowód w cało ci zbudowany jest ze szkła, przy czym składa si z dwóch jego warstw:
warstwy wewn trznej nazywanej rdzeniem, oraz zewn trznego płaszcza ochronnego. W
celu zapewnienia funkcjonowania wiatłowodu, współczynnik załamania rdzenia ( ) po-
winien być wi kszy ni płaszcza ( ).
Rys. 2.1 Budowa kabla wiatłowodowego
Rozmiary wiatłowodu s standardyzowane i zale od jego typu.
Rys. 2.2 Przekrój włókna kabla wiatłowodowego
12
Rozmiar zewn trzny jest stały dla wszystkich typów wiatłowodu. Wynika to z potrzeby
ł czenia wiatłowodów ze sob i konieczno ci przekazywania sygnału mi dzy nimi. Obec-
nie spotyka si wiatÅ‚owody o grubo ci 125 µm, choć obecne s jeszcze takie o rozmiarze
140 µm.Rozmiar rdzenia: wyró niamy dwa typy. Pierwszy o grubo ci 9 µm i drugi  w
starszej wersji jako 62,5 µm oraz nowszej 50 µm (o gorszych parametrach tÅ‚umienno cio-
wych, ale lepszych dyspersyjnych) [6].
2.1.2.1.1. Podstawowe typy wiatłowodów
Podstawowa klasyfikacja dzieli wiatłowody na:
1) jednomodowe
2) wielomodowe
wiatło rozchodzi si w tak zwanych wi zkach. Wi zki te nazywane s modami. W
zale no ci, czy przesyłany jest pojedynczy mod (pojedyncze mody), czy ich du a liczba,
wiatłowody dziel si na wiatłowody jednomodowe lub wielomodowe. W wiatłowodzie
wielomodowym liczba modów przekracza 600 [11].
2.1.2.1.2. wiatłowód jednomodowy
Standardowy kabel typu SMF jest kablem o zerowej dyspersji (dotyczy to wył cz-
nie jednego konkretnego okna transmisyjnego). Jest to rodzaj wiatłowodu preferowany
przy transmisji długodystansowej. Zawiera do ć cienki rdze (w przedziale od 4 do 9
µm)oraz pÅ‚aszcz o standardowych rozmiarach. Mniejszy przekrój rdzenia gwarantuje
mniejsz tłumienno ć.
W przypadku wiatłowodu jednomodowego stosuje si ródła wiatła spójnego, które daj
faktycznie równoległe wi zki wiatła. Przesyłane s one równolegle do osi, co praktycznie
eliminuje dyspersj .
13
Rys. 2.3 Przebieg sygnału w wiatłowodzie jednomodowym
2.1.2.1.3. wiatłowód wielomodowy
wiatłowód wielomodowy skokowy - dyspersja wynosi (w zale no ci od typu ka-
bla i producenta) od 10 do 30 ns/km. Bezpieczna dyspersja dla standardów ethernetowych
(optycznych) to 2 do 3 ns/km. Tak, wi c kabel ten nie mo e być stosowany do transmisji
długodystansowych. Ogranicza si go do kilkudziesi ciu (kilkuset) metrów. Jest to kabel z
rdzeniem 62,5 b d 50 µm. PÅ‚aszcz ochronny grubo ci 125 µm. WpÅ‚yw dyspersji modal-
nej, je li sygnałem wej ciowym jest fala prostok tna, na wyj ciu osi ga si sygnał podob-
ny do sinusoidalnego. Mo e si zdarzyć, e dwa s siednie impulsy prostok tne b d na
wyj ciu na siebie nachodzić.
Rys. 2.4 Przebieg sygnału w wiatłowodzie wielomodowym skokowym
wiatłowód wielomodowy gradientowy  jego budowa jest w zasadzie taka sama jak wia-
tłowodu skokowego. Wyj tkiem jest zmienny współczynnik załamania wiatła w rdzeniu
(zwi kszaj cy si wraz ze zbli aniem si do osi rdzenia). Przyczynia si to do powstania
zmiennej dyspersji -co powoduje  doginanie równolegle do osi promienia wietlnego pa-
14
daj cego pod k tem. Efektem jest zmniejszony wpływ dyspersji na bieg wiatła (ok. 1
ns/km).
Rys. 2.5 Przebieg sygnału w wiatłowodzie wielomodowym gradientowym
2.2. Media bezprzewodowe
Pierwsze lokalne sieci radiowe wykorzystywały pasmo 900MHz, przy szybko ci trans-
misji rz du 0,5Mb/s. W 1997r. opracowana została przez IEEE norma 802.11, obejmuj ca
transmisj w podczerwieni i dwa rodzaje transmisji radiowej. Standard IEEE 802.11 opiera
si na działaniu inteligentnego protokołu DFWMAC (Distribution Foundation Wireless
Medium Access Protokol), który jest protokołem warstwy ł cza danych modelu OSI/ISO.
Standard ten pracuje w zakresie pasma 2400-2483.5 MHz i szeroko ci pasma 80 MHz.
Wykorzystuje on dwie techniki rozproszonego widma: DSSS (Direct Sequence Spread
Spectrum) oraz FHSS (Frequency Hopping Spread Spectrum) [9].
15
3. TOPOLOGIE
Topologi nazywamy charakterystyk sieci uwzgl dniaj c wył cznie wła ciwo ci istnie-
nia i spójno ci. Dla celów projektowych najlepiej przedstawić jest sieć jako graf.
Projektuj c sieć nale y zapewnić jej skalowalno ć, czyli mo liwo ć zmiany ilo ci w złów,
nie powoduj cych zmiany podstawowych wła ciwo ci sieci oraz procesów w niej realizo-
wanych. Sieć nazywamy regularn , je eli stopie wszystkich jej wierzchołków jest iden-
tyczny. Maksymalny stopie wierzchołka grafu to stopie grafu. Jest to jeden z najwa -
niejszych parametrów sieci, im jest on wy szy tym wy szy koszt sieci. Innym parametrem
okre laj cym topologi sieci jest jej rednica, czyli najkrótsza droga ł cz ca dwa najbar-
dziej odległe wierzchołki. Wzrost rednicy powoduje pogorszenie charakterystyk koszto-
wych i przepustowo ci sieci. Miar rednicy jest liczba przechodzonych w złów po red-
nich. Cech sieci gwarantuj c prostot opisu routingu i operacji obliczeniowych jest algo-
rytmiczno ć, czyli zdolno ć danej topologii, do wykonywania zło onych zada , poprzez
ich podział na cz stkowe elementy.
Topologie sieci LAN mog być opisane zarówno na płaszczy nie fizycznej, jak i logicznej.
Topologia logiczna opisuje wszelkie mo liwe poł czenia mi dzy parami mog cych si
komunikować punktów ko cowych sieci. Za jej pomoc opisywać mo na, które punkty
ko cowe, mog si komunikować, z którymi, a tak e ilustrować, które z takich par maj
wzajemne, bezpo rednie poł czenie fizyczne. Zadaniem topologii logicznej jest zapewnie-
nie, e informacje b d przesyłane jak najszybciej i bez bł dów.
3.1. Topologia logiczna
Ka da topologia logiczna korzysta z jednej, z trzech metod tworzenia poł cze mi dzy
stacjami. Metody te to [8]:
x Komutacja obwodów
x Komutacja komunikatów
x Komutacja pakietów
Sieci korzystaj ce z komutacji obwodów s u yteczne przy dostarczaniu informacji, które
musz być odbierane w takiej kolejno ci, w jakiej zostały nadane. Wad tego typu komu-
Stopie wierzchołka to liczba gał zi jemu incydentnych.
16
tacji jest fakt, e poł czenie jest aktywne, nawet je li nie s przesyłane przez nie dane. Ty-
powymi przedstawicielami tych sieci s : PSTN telefoniczna sieć publiczna, ISDN, ATM
(Asynchronous Transfer Mode), linie dzier awione.
Komutacja komunikatów ma bardzo ograniczone znaczenie praktyczne. W komutacji tej
cała przekazywana informacja buforowana jest w w le tranzytowym przed jej wysłaniem
do kolejnego w zła podsieci komunikacyjnej zgodnie z zasad  zapami taj i przeka  .
Komutacja komunikatów zwi ksza wymagania pami ciowe i przetwarzania na sprz cie
przej ciowym, w celu przechowania informacji przed jej dostarczeniem.
Komutacja pakietów jest najcz ciej wykorzystywan metod w obecnych topologiach
sieci. W metodzie tej ka da przesyłana ramka, mo e przej ć inn cie k do miejsca prze-
znaczenia. W tym typie komunikacji, przesyłane pakiety, mog docierać do miejsca prze-
znaczenia w ró nej kolejno ci. Jest to wad przy przekazach multimedialnych. Sieciami
korzystaj cymi z komytacji pakietów s wszystkie topologie Ethernet, FDDI, 100VG-
ANYLAN, Frame Relay oraz X.25.
3.2. Topologia fizyczna
Topologia fizyczna okre la geometryczn organizacj sieci lokalnych. Nie jest ona jed-
nak map sieci. Jest natomiast teoretyczn struktur graficznie przedstawiaj c kształt i
struktur sieci LAN.
3.2.1. Terytorialna klasyfikacja sieci komputerowych
Jednym z głównych podziałów sieci, jest jej rozgraniczenie, ze wzgl du na rozpi -
to ć. Według tego kryterium sieci klasyfikujemy jako [11]:
WAN :LGH $UHD 1HWZRUN rozległy system komunikacyjny, ł cz cy urz dzenia znacznie
oddalone od siebie geograficznie. Sieć taka ł czy ze sob nie tylko pojedyncze komputery,
ale równie sieci lokalne i metropolitalne, bez ogranicze narzuconych na odległo ć mi -
dzy nimi.
MAN 0HWURSROLWDQ $UHD 1HWZRUN miejska lub kampusowa szkieletowa sieć komputero-
wa. Pod wzgl dem zasi gu, jest ona po rednia pomi dzy sieciami LAN i WAN. Najcz -
ciej swym obszarem pokrywa miasto b d jedno osiedle.
17
LAN /RFDO $UHD 1HWZRUN sieć komputerowa o charakterze lokalnym, ł cz ca grup
u ytkowników pracuj c na niewielkim obszarze. Zawiera zwykle od kilku do kilkudzie-
si ciu urz dze , poł czonych za po rednictwem fizycznych kanałów o niewielkich długo-
ciach.
3.2.1.1. Topologie komputerowych sieci WAN i MAN
Do budowy sieci WAN i MAN wykorzystuje si topologie hierarchiczne i topologie
kratowe.
3.2.1.1.1. Topologia kratowa
Rys. 3.1 5\VXQHN SU]HGVWDZLD VWUXNWXU NUDW\ UHJXODUQHM ]XSHáQHM
Krata nie musi być struktur regularn . Mo e mieć charakter niezupełny (brak pewnych
poł cze lub elementów).
Główn wad tej struktury jest potrzeba do ć pracochłonnej, długotrwałej transmisji po-
mi dzy dwoma skrajnymi elementami.
3.2.1.1.2. Topologia toroidalna
Topologie toroidalne to modyfikacje topologii kratowych, w których poł czono do-
datkowo skrajne elementy.
18
Rys. 3.2 7RSRORJLD WRURLGDOQD
3.2.1.2. Sieci szkieletowe
We wszystkich omówionych wcze niej topologiach nie istniała wydzielona struktura
przeznaczona do realizacji komunikacji mi dzy w złami sieci. Je eli struktura takowa zo-
staje wydzielona to sieć taka nosi nazw sieci szkieletowej [11].
Szkielet sieci realizuje funkcj krytyczn . A
czy on wszystkie zasoby sieci lokalnej i
ewentualnie sieć lokaln z sieci rozległ . Wyró nia si nast puj ce rodzaje sieci szkiele-
towych:
x Szkielet szeregowy  jest szeregiem koncentratorów poł czonych ze sob ła cu-
chowo. Topologia ta jest odpowiednia wył cznie do zastosowa w małych sie-
ciach.
x Szkielet rozproszony  mo e być utworzony przez umieszczenie koncentratora
szkieletowego w centralnym miejscu sieci. Wszystkie poł czenia rozchodz si od
niego do pozostałych koncentratorów obsługuj cych dan sieć. Szkielet o topologii
rozproszonej umo liwia pokrycie sieci LAN obszarów znacznie wi kszych ni
szkielet szeregowy i nie zachodzi tutaj obawa o przekroczenie maksymalnych
rednic sieci.
x Szkielet segmentowy  topologia ta oparta jest na routerze Å‚ cz cym wszystkie
segmenty sieci LAN. Dzi ki zastosowaniu routera mo na skutecznie tworzyć wie-
le domen kolizji i rozgłaszania, zwi kszaj c w ten sposób wydajno ć ka dego z
segmentów sieci. Mog jednak ograniczać efektywn wydajno ć ka dej transmisji,
prowadzonej mi dzy ró nymi segmentami sieci.
19
x Szkielet równoległy  jest to modyfikacja szkieletu segmentowego pozwalaj ca na
wzrost wymaga bezpiecze stwa sieciowego oraz zwi kszenie stopnia dost pu do
sieci.
3.2.2. Topologie komputerowych sieci lokalnych
Rodzaj topologii fizycznej wynika z rodzaju zastosowanej technologii sieci LAN. W
wyniku zastosowania koncentratorów powstały sieci o topologii pier cieni gwia dzistych.
Podobnie wprowadzenie przeł czania sieci LAN zmieniło sposób klasyfikowania topolo-
gii. Lokalne sieci przeł czane, niezale nie od rodzaju ramki i metody dost pu, s topolo-
gicznie podobne. Pier cie jednostki dost pu do stacji wieloterminalowej, który do nie-
dawna u ywany był do przył czania - na poziomie elektroniki - wszelkich urz dze do
sieci Token Ring, nie pełni ju tej funkcji. Zamiast niego ka de z przył czanych urz dze
ma własny minipier cie , do którego przył czone s tylko dwa urz dzenia: ono samo oraz
port przeł czania [13].
3.2.2.1. Topologia magistrali (szynowa)
Topologie magistrali wyró nia to, e wszystkie w zły sieci poł czone s ze sob za
pomoc pojedynczego, otwartego (umo liwiaj cego przył czenie kolejnych urz dze ) ka-
bla. Kabel ten obsługuje tylko jeden kanał i nosi on nazw magistrali. Niektóre technologie
oparte na magistrali korzystaj z wi cej ni jednego kabla, dzi ki czemu obsługiwać mog
wi cej ni jeden kanał, mimo e ka dy z kabli obsługuje niezmiennie tylko jeden kanał
transmisyjny. Oba ko ce magistrali musz być zako czone opornikami ograniczaj cymi,
zwanymi równie cz sto terminatorami. Oporniki te chroni przed odbiciem sygnału. Zaw-
sze gdy komputer wysyła sygnał, rozchodzi si on w przewodzie automatycznie w obu kie-
runkach. Je li sygnał napotka na swojej drodze terminatora, to dochodzi do ko ca magi-
strali, gdzie zmienia kierunek biegu. W takiej sytuacji pojedyncza transmisja mo e całko-
wicie zapełnić wszystkie dost pne szeroko ci pasma i uniemo liwić wysyłanie sygnałów
wszystkim pozostałym komputerom przył czonym do sieci [13].
Typowa magistrala składa si z pojedynczego kabla ł cz cego wszystkie w zły w sposób
charakterystyczny dla sieci równorz dnej. Kabel nie jest obsługiwany przez adne urz -
dzenia zewn trzne. Zatem wszystkie przył czone do sieci urz dzenia słuchaj transmisji
przesyłanych magistral i odbieraj pakiety do nich zaadresowane. Brak jakichkolwiek
20
urz dze zewn trznych, w tym wzmacniaków, sprawia, e magistrale sieci lokalnych s
proste i niedrogie.
Podstawow zalet topologii magistralowej jest rednica równa 1.
Do jej wad zaliczamy:
1) rozgłoszeniowy charakter ruchu
2) falowo ć medium transmisyjnego
3) pogorszenie parametrów transmisyjnych b d ce rezultatem przył cze do magistrali
Sieć oparta na magistrali ma charakter rozgłoszeniowy. Je eli warunkiem funkcjonowania
sieci jest zainstalowanie protokołów  gadatliwych i wykorzystanie pakietów rozgłosze-
niowych, wysyłanych przez te wła nie protokoły, to z pewno ci ta technologia jest do-
brym rozwi zaniem.
Z tego wła nie powodu, ale równie z powodów technologicznych, ta technologia została
zaimplementowana w technologii zapadni tego rdzenia [13].
W technologii zapadni tego rdzenia (collapsed backbone) magistrala ma charakter elektro-
niczny (realizowana jest w wewn trznej architekturze urz dze ). W magistrali tej wysłany
sygnał dociera do wszystkich elementów do niej doł czonych, w danym momencie czasu
mo e odbywać si wył cznie komunikacja pomi dzy jedn par u ytkowników (pomijaj c
ruch rozgłoszeniowy). Rozgłoszeniowy charakter ruchu ogranicza w tej strukturze jej
przepustowo ć.
W celu poprawy parametrów niezawodno ciowych oraz przepustowo ci sieci szeregu sys-
temów wykorzystuje si magistrale wielokanałowe b d ce poł czeniem szeregu niezale -
nych magistral jednokanałowych.
3.2.2.2. Topologia pier cienia
Pierwsz topologi pier cieniow była topologia prostej sieci równorz dnej. Ka da
przył czona do sieci stacja robocza ma w ramach takiej topologii dwa poł czenia, po jed-
nym dla ka dego ze swoich najbli szych s siadów. Poł czenie takie musiało tworzyć fi-
zyczn p tl , czyli pier cie . Dane przesyłane były wokół pier cienia w jednym kierunku.
Ka da stacja robocza działała podobnie jak wzmacniak, pobieraj c i odpowiadaj c na pa-
kiety do nich zaadresowane, a tak e przesyłaj c dalej pozostałe pakiety do nast pnej stacji
roboczej wchodz cej w skład sieci.
Pierwotna pier cieniowa topologia sieci LAN umo liwiała tworzenie poł cze równorz d-
nych mi dzy stacjami roboczymi. Poł czenia te musiały być zamkni te; czyli musiały two-
21
rzyć pier cie . Pier cienie te zostały wyparte przez sieci Token Ring, które to korzystały z
koncentratorów wzmacniaj cych [13]. Wyeliminowało to podatno ć sieci pier cieniowej
na zawieszenia si przez wyeliminowanie konstrukcji ka dy z ka dym pier cienia. Sieci
Token Ring mimo pierwotnego kształtu pier cienia, tworzone s przy zastosowaniu topo-
logii gwiazdy i metody dost pu cyklicznego.
Sieć ta gwarantuje naturalne mechanizmy potwierdzania poprawno ci transmisji. Jest ona
preferowana dla sieci z dost pem deterministycznym, dla których pozwala to prioryteto-
wać ruch. Sieć ta jest zło ona w rozbudowie a czas propagacji w sieci zale ny jest od ilo ci
doł czonych do niej stacji.
W topologii tej, bardzo niskim kosztem osi gni to spójno ć równ 2. Usuni cie jednego
wierzchołka (b d jednej gał zi) nie powoduje rozł czenia całej struktury. Istnieje zawsze
mo liwo ć zmiany kierunku ruchu i sieć powinna dalej funkcjonować [13].
3.2.2.3. Topologia gwiazdy
Poł czenie sieci LAN o topologii gwiazdy z przył czonymi do niej urz dzeniami
rozchodz si z jednego, wspólnego punktu, którym jest koncentrator. Ka de urz dzenie
przył czone do sieci w topologii gwiazdy mo e uzyskiwać bezpo redni i niezale ny od in-
nych urz dze dost p do no nika. W tym celu urz dzenia te musz współdzielić dost pne
szeroko ci pasma koncentratora [13].
Topologie gwiazdy stały si dominuj cym we współczesnych sieciach LAN rodzajem to-
pologii. S one elastyczne, skalowalne i stosunkowo tanie w porównaniu z bardziej skom-
plikowanymi sieciami LAN o ci le regulowanych metodach dost pu.
Istnienie centralnego w zła daje doskonał mo liwo ć scentralizowanego zarz dzania ru-
chem w systemie (mo liwo ć zabraniania i zezwalania ruchu, ledzenia ruchu poszczegól-
nych u ytkowników). Rol w złów centralnych pełni specjalistyczne urz dzenia typu
przeł cznik (switch), koncentrator (hub), router
Wad tej topologii jest fakt, e w przypadku awarii urz dzenia centralnego, uszkodzeniu
podlega cała struktura sieciowa.
3.2.2.4. Topologie zło one
Topologie zło one s rozszerzeniami i/lub poł czeniami podstawowych topologii fi-
zycznych. Topologie podstawowe s odpowiednie jedynie do bardzo małych sieci LAN.
22
Skalowalno ć topologii podstawowych jest bardzo ograniczona. Topologie zło one two-
rzone s z elementów składowych umo liwiaj cych uzyskanie topologii skalowalnych
[13].
Najprostsz z topologii zło onych otrzymać mo na w wyniku poł czenia szeregowego
wszystkich koncentratorów sieci. Taki sposób ł czenia znany jest jako ła cuchowanie.
Wykorzystuje ono porty ju istniej cych koncentratorów do ł czenia ich z kolejnymi kon-
centratorami. Dzi ki temu unikn ć mo na ponoszenia kosztów dodatkowych zwi zanych z
tworzeniem odpowiedniego szkieletu. Małe sieci LAN mog być zwi kszane (skalowane
dodatnio) przez ł czenie koncentratorów w ła cuchy. A
a cuchy stanowiły alternatywn ,
wobec sieci LAN pierwszej generacji, metod przył czania urz dze [13].
23
4. REGUA
Y DOBORU TRASY
W sieciach bardzo cz sto istnieje mo liwo ć wyboru kilku ró nych tras mi dzy t sam
par w złów. Reguły doboru trasy okre laj wybór takich tras, które ze wzgl du na kon-
kretne parametry s trasami optymalnymi. Problemy optymalizacji przesyłania informacji
pomi dzy wieloma biegunami przez sieci umo liwiaj ce wiele ró nych poł cze pomi dzy
konkretnymi w złami s bardzo zło one. Z tego wzgl du analiza oraz optymalizacja nawet
prostego systemu przesyła informacji przez sieć jest bardzo trudna. Zagadnienie optymali-
zacji przesyłanej informacji przez pojedynczy kanał, okre lenie optymalnej lub zbli onej
do optymalnej reguły doboru trasy stanowi pierwsz czynno ć podczas rozwi zywania za-
gadnienia optymalizacji. Dalsz czynno ci jest okre lenie jako ci wybranej reguły dobory
trasy. Przy optymalizacji trasy za kryterium jako ci doboru trasy mo emy przyj ć redni
liczb w złów, przez które musz przej ć dane, lub redni czas przechodzenia informacji
przez sieć [2].
4.1. Podział reguł doboru trasy
Reguł doboru trasy jest zasada, według której informacja od bieguna ródłowego S
jest przesyłana do bieguna przeznaczenia T. Reguły te mo na podzielić ze wzgl du na kil-
ka cech. Istotna cecha wi e si z tym czy informacj wysłan od w zła ródłowego przez
cały czas przesyłania musimy traktować jako niepodzieln , czy mo emy j podzielić w
trakcie przesyłania jej przez kolejne w zły sieci. W pierwszym wypadku informacja po
doj ciu do danego w zła jest dalej wprowadzana w cało ci do jednego z kanałów wycho-
dz cych z tego w zła i nosi nazw reguły doboru trasy bez rozgał zie Rys. 4.2. Nato-
miast, kiedy informacj mo na podzielić w danym w le i przesyłać mniejsze cz ci tej in-
formacji ró nymi drogami mówimy, e jest to reguła doboru trasy z rozgał zieniami
Rys. 4.3. Trasy z rozgał zieniami wchodz wgr równie w sytuacji, kiedy chodzi o do-
starczenie tej samej informacji do wielu biegunów (transmisja rozgłoszeniowa) lub o
zwi kszenie pewno ci dostarczenia informacji do bieguna docelowego. Funkcje te reali-
zowane s za pomoc kopiowania informacji i wysyłania jej ró nymi trasami. Reguła ta
nosi nazw reguły doboru trasy z powieleniem Rys. 4.4. Stosowanie jednak tej reguły ma
swoje wady. Je eli w złów jest du o oraz du o jest kanałów wychodz cych z jednego w -
24
zła, liczba przesyłanych kopii informacji staje si przy powielaniu bardzo wielka i dlatego
tak reguł nazywamy  zalewaniem sieci" pakietami [2].
Nast pn istotn cech reguły doboru trasy jest sposób zestawiania trasy. W gr wchodz
dwie klasy zasad wyboru trasy: sztywnego oraz zmiennego [2]. W wypadku reguły wyboru
sztywnego, trasa do przesyłania informacji pomi dzy dwoma biegunami jest z góry ustalo-
na i niema na ni wpływu stan sieci (routing statyczny). Do klasy reguł zmiennego doboru
trasy zaliczamy reguły, w których trasa pomi dzy w złem pocz tkowym i ko cowym, mo-
e być zmieniona, w zale no ci od stanu sieci (routing dynamiczny). Klasyfikacje na regu-
ły stosuj ce trasy bez odgał zie oraz z odgał zieniami, jak równie wyboru sztywnego
lub zmiennego, s nawzajem niezale ne. Mo emy, wi c mieć na przykład reguł z trasami
bez odgał zie wybieranych w sposób sztywny lub zmienny. Omawian tu klasyfikacj
ilustruje Rys. 4.1.
Rys. 4.1 Ogólna klasyfikacja reguł doboru trasy
Rysunki Rys. 4.2, Rys. 4.3, Rys. 4.4 przedstawiaj rozpływ sygnału w przykładowej sieci
zło onej z poł czonych ze sob w złów. Linia ci gła symbolizuje kanał, linia przerywana
oznacza tras przebiegu sygnałów z w zła S do T [2].
25
Rys. 4.2 Reguła doboru trasy bez odgał zie
Rys. 4.3 Reguła doboru trasy z odgał zieniami
Rys. 4.4 Reguła doboru trasy z powielaniem
26
4.1.1. Parametry charakteryzuj ce reguł doboru trasy
Parametry charakteryzuj ce reguł doboru trasy mo na podzielić na trzy grupy ze
wzgl du na [2] :
x koszt realizacji reguły,
x koszt przesyłania pakietu,
x jako ć przesyłania pakietu.
Okre lenie parametrów, charakteryzuj cych koszt realizacji reguły doboru trasy jest trud-
ne. Poniewa na ogół trasa uzale niona jest od informacji o stanie sieci, na koszt realizacji
reguły doboru trasy składa si nie tylko koszt urz dze przetwarzaj cych sygnały, ale te
koszt kanałów pomocniczych doprowadzaj cych informacje o stanie sieci. Ogólnie jednak
mo na stwierdzić, e realizacja reguły kierowania scentralizowanego wymaga przewa nie
o wiele bardziej rozbudowanej sieci - ze wzgl du na konieczno ć dostarczania informacji
pomocniczych o stanie sieci wła ciwej - ni reguły kierowania zdecentralizowanego, w
której kolejne segmenty trasy okre lane s w poszczególnych w złach. Sieć kierowania
scentralizowanego wymaga te dodatkowo drugiej sieci pomocniczej, doprowadzaj cej do
w złów decyzje podj te w centrum sterowania [2]. Wobec trudno ci okre lenia w sposób
ogólny parametrów, charakteryzuj cych koszt realizacji reguły doboru trasy, ograniczymy
si tu jedynie do ogólnych charakterystyk zło ono ci tej reguły.
Na koszt przesyłania pakietu przez sieć składaj si koszty korzystania z kanałów i w -
złów. Koszt ten zale y w głównej mierze od długo ci fizycznej kanału oraz od nat enia
strumienia przesyłanych pakietów. Przy zało eniu, e stosujemy trasy bez odgał zie , na-
t enie strumienia, jaki jest przesyłany przez kanał, jest równe nat eniu informacji po-
dawanych przez ródło, a wi c jest ustalone. Tak, wi c koszt przesyłania pakietów przez
kanały zale y w du ej mierze od ł cznej długo ci kanałów składaj cych si na tras [2].
Cz sto sieć utworzona jest przez kanały o długo ciach fizycznych podobnego rz du, wów-
czas koszt przesyłania pakietu, przez kanały tworz ce tras , zale y w głównej mierze od
liczby kanałów wchodz cych w skład trasy. Je li si przyjmie, e ka dy z kanałów ma dłu-
go ć jednakow G Z Y , to liczb kanałów wchodz cych w skład trasy S T , któr
oznaczymy 1 > S T @ mo emy zapisać w postaci
1 [W ( S,T)] Åš G(Z,Y)
(4.1)
27
Koszt korzystania z w zła zale y w głównej mierze od nat enia przesyłanego strumienia
pakietów. Przy stosowaniu tras bez odgał zie nat enie to jest ustalone. Koszt korzysta-
nia z w złów zale y, wi c w głównej mierze od liczby w złów na trasie, ta za jest o jeden
wi ksza od liczby kanałów. Tak, wi c istotnym parametrem, od którego zale y koszt ko-
rzystania z kanałów i w złów, jest liczba 1 kanałów, z których si składa trasa [2].
4.1.1.1. Czas przechodzenia pakietu przez kanał
Metody przeciwdziałania przypadkowym zniekształceniom sygnałów pozwalaj w
znacznej mierze zmniejszyć prawdopodobie stwo tego, e do bieguna docelowego b dzie
doprowadzona informacja zniekształcona. W tej sytuacji podstawowym parametrem pkre-
laj cy jako ć przesyłania informacji staje si parametr charakteryzuj cy czas przechodze-
nia pakietu przez sieć, stanowi cy uogólnienie poj cia parametru charakteryzuj cego czas
przechodzenia pakietu przez system wielodost powy. Je li informacj przesyłamy w po-
staci pakietu pojedynczego, czas przechodzenia pakietu równy jest czasowi, jaki upływa
od chwili wprowadzenia pakietu do bieguna ródłowego, do chwili dostarczenia informacji
do bieguna docelowego. Je li informacja dzielona jest na segmenty, na przykład przy sto-
sowaniu tras z odgał zieniami, czas przechodzenia przez sieć jest okre lany jako czas, jaki
upływa od chwili wprowadzenia informacji do bieguna ródłowego, do chwili, gdy ostatni
jej segment dotrze do bieguna docelowego. Dalej analizujemy przypadek, gdy pakiety nie
s dzielone na mniejsze jednostki w trakcie przesyłania przez sieć.
Podstaw do okre lenia parametrów charakteryzuj cych czas przechodzenia pakietu przez
sieć, jest czas Z Y przechodzenia pakietu przez pojedynczy kanał. Na czas ten składaj
si [2]:
7E czas przebywania pakietu w buforze,
7V czas trwania sygnału nios cego ten pakiet,
7SU czas propagacji sygnału przez kanał,
7SU] czas przetwarzania sygnału w nadajniku i odbiorniku.
Czas ten zapisujemy wzorem:
W (Z,Y) 7 7 (Z,Y) 7 (Z Y), 7
(4.2)
28
4.2. Metody znajdowania tras najkrótszych
Zagadnienie znajdowania tras najkrótszych jest typowym zagadnieniem teorii grafów.
Poni ej przedstawiamy kilka podstawowych definicji i twierdze , niezb dnych przy roz-
wa aniu sieci jako grafu.
4.2.1. Definicja grafu
Grafem * nazywamy niepusty sko czony zbiór 9 * , którego elementy nazywamy
wierzchołkami(lub w złami), i sko czonej rodziny par nieuporz dkowanych ( * elemen-
tów 9 G) nazywanych kraw dziami [7].
4.2.1.1. Graf skierowany
Graf * składa si z niepustego sko czonego zbioru 9 * , którego elementy nazywa-
my wierzchołkami (lub w złami) i sko czonej rodziny par uporz dkowanych ( * ele-
mentów 9 * nazywanych kraw dziami [7].
4.2.1.2. Suma grafów
Dane s dwa grafy * 9 * ( * i * 9 * ( * Sum grafów * i *
b dzie graf *, którego zbiór wierzchołków 9 * jest sum zbiorów 9 * i 9 * , a zbiór
kraw dzi jest sum zbiorów ( * i ( * [7].
4.2.1.3. Graf spójny
Graf spójny to taki, którego nie da si przedstawić jako sumy dwóch grafów. W
przeciwnym wypadku graf nazwiemy niespójnym [7].
4.2.1.4. S siedztwo
Powiemy, e dwa wierzchołki Y i Z grafu s s siednie, je eli istnieje kraw d ^Y Z`
która je ł czy. Dwie kraw dzie s s siednie, je eli maj wspólny wierzchołek [7].
29
4.2.1.5. Macierz s siedztwa
Je eli * jest grafem, którego wierzchołki s oznakowane liczbami ^ Q` to macie-
rz s siedztwa a jest macierz wymiaru Q [ Q której wyraz o indeksach L,M jest równy
liczbie kraw dzi łacz cych wierzchołek L z wierzchołkiem M. Minimalne drzewa rozpi-
naj ce
4.2.2. Minimalne drzewa rozpinaj ce
Minimalne drzewa rozpinaj ce s stosowane podczas działania mostów w sieci. Bie-
rzemy je równie pod uwag w czasie projektowania sieci. Okre laj one najkorzystniejsz
drog w sieci od danego wierzchołka do wszystkich pozostałych wykluczaj c zjawisko
wyst powania cykli (wielodróg) do wierzchołków [1].
Problem ł czenia w złów mo na modelować za pomoc spójnego grafu nieskierowanego
* 9 ( w którym 9 jest zbiorem w złów, a ( jest zbiorem mo liwych poł cze mi -
dzy parami w złów. Z ka d kraw dzi X Y ( jest zwi zana waga Z X Y okre laj ca
koszt (długo ć potrzebnego przewodu) poł czenia wierzchołków X i Y Wówczas naszym
celem jest znalezienie acyklicznego podzbioru 7 %7ń ( który ł czy wszystkie wierzchołki i
którego ł czna waga jest najmniejsza [1].
Z(7 ) (4.3)
ÅšZ(X,Y)
Poniewa 7 jest acykliczny i ł czy wszystkie wierzchołki, wi c jest drzewem. Drzewo 7
UR]SLQD JUDI * dlatego jest nazywane drzewem rozpinaj cym. Problem wyznaczania
drzewa 7 nazywamy problemem minimalnego drzewa rozpinaj cego [1].
Do obliczenia drzewa rozpinaj cego słu dwa algorytmy, Kruskala oraz Prima. Oba algo-
rytmy s przykładami zachłannych algorytmów optymalizacyjnych [1]. W ka dym kroku
takiego algorytmu musimy dokonać jednego z kilku mo liwych wyborów. Stosuj c strate-
gi zachłann , dokonujemy wyboru, który jest w danej chwili najlepszy. Taka strategia
ogólnie nie gwarantuje znalezienia rozwi zania optymalnego. Dla problemu minimalnego
drzewa rozpinaj cego mo emy jednak udowodnić, e stosuj c pewne strategie zachłanne,
otrzymamy drzewo rozpinaj ce o minimalnej wadze [1].
30
W algorytmie Kruskala zbiór $ jest lasem. Kraw d $ jest zawsze t kraw dzi w grafie,
która ma najmniejsz wag i która ł czy dwie ró ne składowe. W algorytmie Prima zbiór
$ tworzy pojedyncze drzewo. Kraw d bezpieczna dodawana do $ jest zawsze t kraw -
dzi w grafie, która ma najmniejsz wag i która ł czy drzewo wyznaczone przez $ z
wierzchołkiem spoza tego drzewa [1].
4.2.2.1. Algorytm Kruskala
Algorytm Kruskala jest oparty na schemacie obliczania minimalnego drzewa rozpi-
naj cego. W tym algorytmie kraw dzi dodawan do rozrastaj cego si lasu jest kraw d
X Y o najmniejszej wadze spo ród kraw dzi ł cz cych ró ne drzewa w lesie. Algorytm
Kruskala jest algorytmem zachłannym, poniewa wka dym kroku do lasu jest dodawana
kraw d o najmniejszej mo liwej wadze. Poni ej przedstawiamy przykład obrazuj cy w
kolejnych krokach działanie algorytmu Kruskala. Przyjmujemy graf, który posłu y nam do
wykre lenia na nim drzewa rozpinaj cego. Zakładamy, e startujemy z wierzchołka D. Dla
grafu wprowadzane s wszystkie odcinki X Y oraz waga drogi mi dzy tymi wierzchoł-
kami posortowana w kierunku rosn cym. Wyznaczanie drzewa rozpinaj cego realizujemy
przez ł czenie wierzchołków, których waga jest najmniejsza, sprawdzaj c przy tym czy
kolejne doł czenie wierzchołka nie spowoduje p tli w grafie. Je eli wyst pi taka sytuacja
odrzucamy t drog i przechodzimy do nast pnej w bazie.
Tworzymy list gał zi w kolejno ci ich wag  rosn co.
Rys. 4.5 Analizowany graf.
Z posortowanych wag gał zi wybieramy pierwsz o najmniejszej wadze.
31
Rys. 4.6 Wybór pierwszego poddrzewa o najmniejszej wadze.
Post pujemy analogicznie jak wcze niej
Rys. 4.7 Wybieramy gał b-d.
Rys. 4.8 Wybieramy gał c-d.
Poniewa wybór gał zi a-b powoduje cykl w grafie zostaje ona odrzucona
Rys. 4.9 Odrzucona gał a-b.
32
Rys. 4.10 Wybór gał zi c-d.
Rys. 4.11 Wybór gał zi d-f.
Otrzymany graf pozwala na osi gni cie z wierzchołka D ka dego z pozostałych wierzchoł-
ków z wykluczeniem cykli w grafie.
4.2.2.2. Algorytm Prima
Podobnie jak algorytm Kruskala, algorytm Prima jest szczególnym przypadkiem
schematu obliczania minimalnego drzewa rozpinaj cego. W algorytmie Prima kraw dzie
ze zbioru $ tworz zawsze pojedyncze drzewo. Pocz tkowo takie drzewo składa si z do-
wolnie wybranego wierzchołka-korzenia U a nast pnie ro nie do chwili, w której rozpina
wszystkie wierzchołki z 9. W ka dym kroku kraw d lekka [1] ł cz ca wierzchołek z $ z
wierzchoÅ‚kiem z 9 ² $ jest dodawana do drzewa. Stosuj c t zasad , do drzewa dodajemy
tylko kraw dzie bezpieczne dla $ Dlatego z chwil zako czenia działania algorytmu kra-
w dzie z $ tworz minimalne drzewo rozpinaj ce. Ta strategia jest zachłanna, poniewa w
ka dym kroku drzewo jest rozszerzane o kraw d , której waga wnosi najmniej do wagi te-
go drzewa [1].
33
Kluczem do efektywnej implementacji algorytmu Prima jest zapewnienie szybkiego wy-
znaczania nowej kraw dzi dodawanej do drzewa tworzonego przez kraw dzie ze zbioru $
[1]
Poni ej przedstawiony jest przykład obrazuj cy w kolejnych krokach działanie algorytmu
Prima. Przyjmujemy graf, który posłu y nam do wykre lenia na nim drzewa rozpinaj ce-
go. Zakładamy, e startujemy z wierzchołka D. Wyznaczanie drzewa rozpinaj cego reali-
zujemy przez ł czenie wierzchołków, których waga jest najmniejsza sprawdzaj c przy tym
czy kolejne doł czenie wierzchołka nie spowoduje p tli (cyklu) w grafie. Je eli wyst pi
taka sytuacja odrzucamy t drog i przechodzimy do nast pnej w bazie. Algorytm ten ró ni
si tym od algorytmu Kruskala, e baza danych dróg jest napełniana sukcesywnie przecho-
dz c do kolejnych wierzchołków grafu.
Rys. 4.12 Analizowany graf.
Rys. 4.13 Wybór gał zi c-d.
34
Rys. 4.14 Wybór gał zi c-d.
Rys. 4.15 Wybór gał zi b-d.
Poniewa wybór gał zi a-b powoduje cykl w grafie zostaje ona odrzucona
Rys. 4.16 Wybór gał zi a-b.
35
Rys. 4.17 Wybór gał zi c-e.
Rys. 4.18 Otrzymany graf
Otrzymany graf pozwala na osi gni cie z wierzchołka D ka dego z pozostałych wierzchoł-
ków z wykluczeniem cykli w grafie.
4.2.3. Najkrótsze cie ki z jednym ródłem
Przypu ćmy, e chcemy przesłać dane najkrótsz tras z jednego serwera do drugiego
odległego serwera. Jednym ze sposobów znalezienia trasy jest sporz dzenie wykazu
wszystkich mo liwych tras poł cze pomi dzy serwerami, zsumowanie odległo ci po-
szczególnych odcinków na ka dej trasie i wybranie trasy najkrótszej. A
atwo jednak zauwa-
yć, e je li nawet pominiemy w naszych rozwa aniach trasy z cyklami, to i tak pozostanie
wiele mo liwo ci, z których wi kszo ć nie jest warta rozwa enia [1].
Algorytmy znajdowania tras najkrótszych wykorzystywane s przez protokoły routingu
wektora odległo ci. Nale do nich min. RIP, IGRP. Dokładniej omawiamy te protokoły
cz ci naszej pracy po wi conej routingowi.
36
W problemie najkrótszych cie ek jest dany wa ony graf skierowany * 9 ( z funkcj
wagow Z ( o 5 przyporz dkowuj c kraw dziom wagi o warto ciach rzeczywistych.
Wag cie ki S Y Y Y ! jest suma wag tworz cych j kraw dzi:
Z( S) ,Y ) (4.4)
ÅšZ(Y
Wag najkrótszej cie ki z wierzchołka X do wierzchołka Y definiujemy jako:
min{Z( S) : X oY},
G (X,Y) (4.5)
®
Żf,
Najkrótsz cie k z wierzchołka X do wierzchołka Y jest ka da cie ka S = X GR Y dla któ-
rej Z S G X Y
W przykładzie omawianym wcze niej mo liwe poł czenia mo emy modelować za pomo-
c grafu, w którym wierzchołki reprezentuj kolejne serwery, a kraw dzie odcinki dróg po-
ł cze mi dzy serwerami. Wagami kraw dzi s długo ci tych odcinków. Wagi kraw dzi
mo na interpretować inaczej ni odległo ci. Wagi kraw dzi reprezentuj cz sto czas,
koszt, kar lub inne wielko ci, które narastaj liniowo wzdłu cie ki i które chcemy mi-
nimalizować.
W tej cz ci pracy skupimy si na problemie najkrótszych cie ek z jednym ródłem, w
którym: dany jest graf * = 9 ( i wyró niony wierzchołek V 9 nazywany ródłem; dla
ka dego wierzchołka Y 9 nale y znale ć najkrótsz cie k z V do Y Wiele innych pro-
blemów mo na rozwi zać, wykorzystuj c algorytmy dla problemu z jednym ródłem. Na-
le do nich nast puj ce warianty omawianego problemu.
Najkrótsze cie ki z jednym wierzchołkiem docelowym. Nale y znale ć najkrótsz cie k
z ka dego wierzchołka Y do danego wierzchołka docelowego W Odwracaj c zwrot ka dej
kraw dzi, mo emy zredukować ten problem do problemu z jednym ródłem.
4.2.4. Najkrótsza cie ka mi dzy par wierzchołków
Nale y znale ć najkrótsz cie k z wierzchołka X do Y dla danej pary wierzchołków X
L Y Je li rozwi emy problem najkrótszych cie ek ze ródłem w wierzchołku X to tak e
37
rozwi emy ten problem. Podkre lmy, e dla problemu najkrótszej cie ki mi dzy par
wierzchołków nie jest znany aden algorytm działaj cy w najgorszym przypadku asympto-
tycznie [1] szybciej ni najlepszy znany algorytm dla problemu z jednym ródłem.
4.2.5. Najkrótsze cie ki mi dzy wszystkimi parami wierzchołków
Dla ka dej pary wierzchołków X Y nale y znale ć najkrótsz cie k z X do Y Ten
problem mo na rozwi zać, wykonuj c dla ka dego wierzchołka w grafie algorytm dla pro-
blemu z jednym ródłem. Rozwi zuje si go jednak zazwyczaj inaczej, a jego struktura jest
sama w sobie interesuj ca.
Kraw dzie z ujemnymi wagami.
W pewnych zastosowaniach problemu najkrótszych cie ek z jednym ródłem mog poja-
wić si kraw dzie z ujemnymi wagami. Je li aden cykl o ujemnej wadze nie jest osi gal-
ny ze ródła V to dla ka dego wierzchołka Y 9 waga najkrótszej cie ki V Y jest dobrze
zdefiniowana nawet, je eli jej warto ć jest ujemna. Jednak e je li cykl o ujemnej wadze
jest osi galny ze ródła V to wagi najkrótszych cie ek nie s dobrze zdefiniowane. adna
cie ka z V do jakiegokolwiek wierzchołka na takim cyklu nie mo e być najkrótsza - zaw-
sze mo na znale ć cie k krótsz , rozszerzaj c cie k ,,najkrótsz " wła nie o ten cykl
[1]. Je li na pewnej cie ce z V do Y znajduje si cykl o ujemnej wadze, to definiujemy go
G V Y 
Na Rys. 4.19 jest pokazany wpływ ujemnych wag na wagi najkrótszych cie ek. Poniewa
jest dokładnie jedna cie ka z V do D ( cie ka V D!), G V D Z V D 3 . Podobnie,
istnieje dokładnie jedna cie ka z V do E i dlatego
G V E Z V D Z D E -1. Istnieje niesko czenie wiele cie ek z V do c:
, , V c, G F G c> itd. Poniewa cykl ma wag 6+(-3)=3>0,
najkrótsz cie k z wierzchołka V do F jest V F! o wadze G V F 5. Podobnie, najkrót-
sz cie k z wierzchołka V do d jest Analogicznie, jest niesko czenie wiele cie ek z wierzchołka V do H V H! V H I H!
V H I H I H! itd. Poniewa jednak cykl H I H! ma wag 3 + (-6) = -3 < 0, nie istnieje
najkrótsza cie ka z wierzchołka V do H Przechodz c cykl (o ujemnej wadze) do-
wolnie wiele razy, mo emy znajdować cie ki z V do H o dowolnie małych wagach i st d
G V H -" Podobnie G V I -" Poniewa wierzchołek g jest osi galny z wierzchołka I
mo emy tak e znajdować cie ki o dowolnie małych ujemnych wagach z wierzchołka V do
38
J st d G V J -" Wierzchołki K L oraz M tworz tak e cykl o ujemnej wadze. Jednak e te
wierzchołki nie s osi galne z V i dlatego G V K G V L G V M " [1].
W pewnych algorytmach dla problemu najkrótszych cie ek, na przykład w algorytmie
Dijkstry, zakłada si , e wszystkie wagi na kraw dziach w grafie wej ciowym s nieujem-
ne . W innych rozwi zaniach, na przykład w algorytmie Bellmana-Forda, dopuszcza si
ujemne wagi na kraw dziach i otrzymuje si poprawne wyniki, je eli tylko aden cykl o
ujemnej wadze nie jest osi galny ze ródła. Zazwyczaj, je li cykl o ujemnej wadze istnieje,
to algorytm wykrywa go i informuje o jego istnieniu.
Rys. 4.19 Graf skierowany z ujemnymi wagami na kraw dziach
Liczba wewn trz ka dego wierzchołka jest wag najkrótszej cie ki ze ródła V GR tego
wierzchołka. Poniewa wierzchołki H oraz I tworz cykl o ujemnej wadze i jest on osi gal-
ny ze rodka V wagi najkrótszych cie ek prowadz cych do tych wierzchołków wynosz
-". Poniewa wierzchołek J jest osi galny z wierzchołka, którego waga najkrótszej cie ki
jest -", waga najkrótszej cie ki do J wynosi tak e -". Wierzchołki K L oraz M nie s osi -
galne ze ródła V i dlatego wagi ich najkrótszych cie ek wynosz ", chocia wierzchołki
te le na cyklu o ujemnej wadze.
4.2.5.1. Algorytm Dijkstry
Algorytm Dijkstry słu y do rozwi zywania problemu najkrótszych cie ek z jednym
ródłem w wa onym grafie skierowanym * = 9 ( w przypadku, gdy wagi wszystkich
kraw dzi s nieujemne. W tym rozdziale zakładamy, wi c e Z X Y ! 2 dla ka dej kra-
w dzi X Y (
39
W algorytmie Dijkstry jest pami tany zbiór 6 zawieraj cy te wierzchołki, dla których wagi
najkrótszych cie ek ze ródła V zostały ju obliczone. To znaczy, e dla ka dego wierz-
chołka Y 6 mamy G>Y@ G V Y Algorytm Dijkstry polega na wielokrotnym powtarzaniu
nast puj cych operacji: wybrania wierzchołka X H 9 6 R najmniejszym oszacowaniu wagi
najkrótszej cie ki, dodania wierzchołka X do 6 wykonania relaksacji kraw dzi opuszcza-
j cych wierzchołek X [1].
W celu lepszego przedstawienia zasady działania algorytmu przedstawimy praktyczny
przykład obliczania najkrótszej cie ki t metod .
W przedstawionym algorytmie pami tany jest zbiór 4 wierzchołków, dla których nie obli-
czono jeszcze najkrótszych cie ek, oraz wektor '>L@ odległo ci od wierzchołka V do L. Po-
cz tkowo zbiór 4 zawiera wszystkie wierzchołki a wektor ' jest pierwszym wierszem ma-
cierzy wag kraw dzi $.
Algorytm wybiera z kolei 4 "najl ejszy" wierzchołek, tzn. jest oparty o strategi zachłan-
n [1]. Wprawdzie metoda zachłanna nie zawsze daje wynik optymalny, jednak algorytm
Dijkstry jest algorytmem dokładnym.
Rys. 4.20 Przykładowy graf
40
Tabela 4.1
a b c d E
a 0 10 " " 5
b " 0 1 " 2
c " " 0 4 "
d 7 " 6 0 "
e " 3 9 2 0
Obliczenia przebiegaj nast puj co: (Dla S=a)
(gwiazdka oznacza symbol niesko czono ci, najl ejszy wierzchołek jest podkre lony,
wierzchołki, dla których wyznaczono ju najkrótsze cie ki s w zacienionych polach )
Tabela 4.2
Q D(a) D(b) D(c) D(d) D(e)
a 0 10 * * 5
b 0 18 14 7 5
c 0 8 13 7 5
d 0 8 9 7 5
e 0 8 9 7 5
Istnieje kilka odmian implementacji Dijkstry; najprostsza u ywa tablicy do przechowywa-
nia wierzchołków ze zbiory Q. Inne wersje algorytmu u ywaj kolejki priorytetowej lub
kopca Fibonacciego. Po znalezieniu najkrótszej odległo ci mi dzy wierzchołkami mo emy
znale ć drog ł cz c te wierzchołki za pomoc algorytmu konstrukcji drogi [1].
4.2.5.2. Algorytm Bellmana  Forda
Algorytm Bellmana-Forda słu y do rozwi zywania problemu najkrótszych cie ek z
jednego ródła w ogólniejszym przypadku, w którym wagi na kraw dziach mog być
ujemne. Dla danego wa onego grafu skierowanego * 9 ( ze ródłem V i funkcj wa-
gow Z(o5 algorytm Bellmana-Forda zwraca warto ć logiczn wskazuj c , czy istnieje
lub nie cykl o ujemnej wadze osi galny ze ródła. Je li taki cykl istnieje, to algorytm in-
formuje, e najkrótszych cie ek w grafie * nie mo na obliczyć. Je li takiego cyklu nie
ma, to algorytm oblicza najkrótsze cie ki i ich wagi.
Podobnie jak w algorytmie Dijkstry, w algorytmie Bellmana-Forda wykorzystuje si me-
tod relaksacji [1], zmniejszaj c stopniowo oszacowanie G>Y@ na wag najkrótszej cie ki
41
ze ródła V do ka dego wierzchołka Y 9, a zostanie osi gni ta rzeczywista waga naj-
krótszej cie ki G V Y Algorytm zwraca warto ć logiczn prawd wtedy i tylko wtedy,
gdy graf nie zawiera cykli o ujemnych wagach osi galnych ze ródła.
W celu lepszego przedstawienia zasady działania algorytmu przedstawimy praktyczny
przykład obliczania najkrótszej cie ki t metod . Dla podanego grafu macierz $ dla ka -
dej pary wierzchołków X i Y zawiera wag kraw dzi X Y przy czym je li kraw d X Y
nie istnieje, to przyjmujemy, e jej waga wynosi niesko czono ć i wpisujemy "*".
Algorytm Forda-Bellmana w ka dym kroku oblicza górne oszacowanie ' Y [1] odległo-
ci od wierzchołka V do wszystkich pozostałych wierzchołków Y . W pierwszym kroku
przyjmujemy ' Y $ V Y Gdy stwierdzimy, e ' Y !' X $ X Y , to ka dorazowo po-
lepszamy aktualne oszacowanie i podstawiamy ' Y ' X $ X Y . Algorytm ko czy si ,
gdy adnego oszacowania nie mo na ju poprawić, macierz ' Y zawiera najkrótsze odle-
gło ci od wierzchołka V do wszystkich pozostałych. Algorytm mo na ulepszyć sprawdza-
j c w ka dej iteracji, czy co si zmieniło od poprzedniej i je li nie, to mo na zako czyć
obliczenia. Przyjmujemy V=1, symbol "*" oznacza niesko czono ć:
Rys. 4.21 Rozwa any graf
42
Tabela 4.3
1 2 3 4 5 6
1 0 2 4 * * *
2 * 2 * * 4 *
3 * * 0 -2 3 *
4 1 * * 0 * 2
5 * * * * 0 *
6 * 2 * * 1 0
Oto przykład oblicze :
Tabela 4.4
K D(1) D(2) D(3) D(4) D(5) D(6)
0 0 2 4 * * *
1 0 2 4 2a 6b 4c
2 0 2 4 2 5d 4
3 0 2 4 2 5 4
Obja nienia:
W pierwszym kroku N ' Y $ Y . Przepisujemy pierwszy wiersz macierzy wag
kraw dzi.
a). Pierwsze skrócenie drogi: w poprzednim kroku ' gdy nie istnieje kraw d od
do . Teraz jednak mo emy przej ć przez wierzchołek (odległo ć od do wynosi 4) a
nast pnie do (waga kraw dzi [3,4]=-2), długo ć drogi od do wynosi, wi c 4-2=2.
b). Podobnie jest tu, do wierzchołka mo emy doj ć przez , , lub . Wybieramy oczy-
wi cie drog o mniejszej długo ci:
' $ (ta warto ć jest najmniejsza)
' $
' $ (ta warto ć jest najwi ksza)
Wybieramy opcj z wierzchołkiem nr. .
c). Do wierzchołka mo emy doj ć przez, (do którego dochodzimy przez ) droga jest,
wi c nast puj ca: , , , a jej długo ć wynosi ' $
d). Jak wynika z punktu b, do wierzchołka mo emy doj ć tak e poprzez wierzchołek .
W poprzednim kroku poznali my odległo ć do wierzchołka i nie wynosi ona ju nie-
sko czono ć. Sprawd my, wi c jaka byłaby długo ć drogi do wierzchołka poprzez :
43
' $ . Jest to warto ć mniejsza ni aktualna (6), wi c znale li my krótsz
drog .
W kroku N nic si nie zmieniło od kroku N . Ko czymy obliczenia i mamy wektor
najkrótszych dróg od wierzchołka V do wszystkich pozostałych.
4.2.6. Maksymalizacja przepływów
Graf skierowany mo na interpretować jako  sieć przepływow " i wykorzystywać go
do znajdowania odpowiedzi na pytania dotycz ce przemieszczania si informacji w takiej
sieci. Przykładem mo e być informacja kr ca w pewnej sieci od ródła, w którym jest
wytwarzana, do uj cia, w którym jest zu ywana. ródło wytwarza informacj ze stał
szybko ci i z t sam szybko ci jest ona zu ywana w uj ciu. Intuicyjnie, w ka dym
punkcie tego systemu  przepływ" odpowiada szybko ci, z jak informacja przemieszcza
si przez ten punkt. Sieci przepływowe mog być u ywane do modelowania przepływu in-
formacji w sieciach komunikacyjnych.
Ka d kraw d skierowan w sieci mo emy interpretować jako kanał. Ka dy kanał ma
ustalon przepustowo ć, wyznaczaj c maksymaln szybko ć, z jak nast puje przepływ
informacji w tym kanale. Wierzchołki ró ne od ródła i uj cia s punktami, w których
zbiegaj si kanały. Przepływ odbywa si tylko przez takie wierzchołki i nie jest w nich za-
trzymywany. Szybko ć wpływania do wierzchołka musi być taka sama jak szybko ć wy-
pływania. Tak własno ć nazywamy własno ci  zachowania przepływu".
Algorytmy wyznaczania najwi kszego przepływu w sieci implementowane s przez
protokoły routingu stanu ł cza. Nale do nich min. OSPF, który opisujemy w dalszej cz -
ci pracy.
Problem maksymalnego przepływu jest najprostszym problemem pojawiaj cym si w
sieciach przepływowych. Nale y znale ć najwi ksz szybko ć, z jak mo e nast pować
przepływ ze ródła do uj cia bez naruszenia ogranicze na przepustowo ci kanałów. Jest
wiele efektywnych algorytmów słu cych do rozwi zania tego problemu. Ponadto podsta-
wowe metody stosowane w tych algorytmach mog być zaadaptowane do rozwi zywania
innych problemów sieciowych.
Wtej cz ci pracy przedstawiamy metody rozwi zywania problemu przepływu mak-
symalnego. Opisujemy równie klasyczn metod znajdowania maksymalnego przepływu,
z wykorzystaniem algorytmów Forda i Fulkersona.
44
4.2.6.1. Sieci przepływowe i przepływy
Sieci przepływow * 9 ( nazywamy graf skierowany, w którym ka da kra-
w d X Y ( ma nieujemn przepustowo ć F X Y ! . Je li X Y ( to przyjmuje-
my, e F X Y . W sieci wyró niamy dwa wierzchołki: ródło V i uj cie W Dla wygody
przyjmujemy, e ka dy wierzchołek sieci le y na pewnej cie ce ze ródła do uj cia.
Oznacza to, e dla ka dego wierzchołka Y 9 istnieje cie ka Vo\oW Graf * jest, wi c
spójny i st d _(_! _9_ [1] Na rysunku Rys. 4.22 jest przedstawiona przykładowa sieć.
Rys. 4.22 3U]\NáDGRZD VLHü * 9 ( PRGHOXM FD SUREOHP SU]HSá\ZX.
Mo emy teraz zdefiniować przepływ bardziej formalnie. Niech * 9 ( b dzie sie-
ci (z funkcj przepustowo ci F). Niech V b dzie ródłem w sieci, a W uj ciem. Przepływem
w sieci * nazywamy ka d funkcj o warto ciach rzeczywistych I 9 [ 9 o 5 spełniaj c
poni sze trzy warunki [1] :
" Warunek przepustowo ci: Dla wszystkich X Y 9 zachodzi I X Y <= F X Y
! Warunek sko nej symetryczno ci: Dla wszystkich X Y H 9 zachodzi I X Y I Y X .
" Warunek zachowania przepÅ‚ywu: Dla ka dego X 9 ² ^V W` zachodzi [1]:
(4.6)
Åšf (u, v) 0
Wielko ć I X Y , która mo e być dodatnia lub ujemna, nazywamy przepływem netto z
wierzchołka X do wierzchołka Y Warto ć przepływu I definiuje si jako [1]:
f (s, v) (4.7)
Åšf
45
Oznacza to, e warto ci przepływu jest ł czny przepływ netto opuszczaj cy ródło. W
problemie maksymalnego przepływu jest dana sieć * oraz ródło V i uj cie W. Nale y zna-
le ć przepływ o maksymalnej warto ci z V GR W
Istniej trzy wymienione warunki, jakie musi spełniać ka dy przepływ. Warunek
przepustowo ci oznacza, e przepływ netto z jednego wierzchołka do drugiego nie mo e
przekraczać przepustowo ci kraw dzi. Warunek sko nej symetryczno ci oznacza za , e
przepływ netto z wierzchołka X do wierzchołka Y ma warto ć przeciwn do przepływu net-
to w odwrotnym kierunku. Tak, wi c przepływ z X GR X wynosi 0, poniewa dla ka dego X
9 mamy I X X I X X , a st d I X X . Własno ć zachowania przepływu mówi, e
ł czny przepływ netto opuszczaj cy wierzchołek ró ny od ródła i uj cia jest zerowy. Ko-
rzystaj c z warunku sko nej symetryczno ci, mo emy zapisać warunek zachowania prze-
pływu [1]:
I (X,Y) 0 (4.8)
Åš
dla wszystkich Y H 9² ^V W`. Co oznacza, e Å‚ czny przepÅ‚yw na wej ciu do wierzchoÅ‚ka
jest zerowy.
Nie mo e istnieć przepływ netto ró ny od 0 mi dzy X i Y je li mi dzy tymi wierzchołkami
nie ma w sieci kraw dzi. Je li ani X Y ( ani Y X ( to F X Y F Y X St d i z
warunku przepustowo ci mamy I X Y <= i I Y X . Ale poniewa z warunku sko-
nej symetryczno ci I X Y I Y X WR I X Y I Y X Tak, wi c niezerowy prze-
pływ netto z wierzchołka X do wierzchołka Y implikuje, e X Y ( OXE Y X ( Ostat-
nia własno ć przepływu, która nas interesuje, dotyczy dodatnich przepływów netto. Do-
datni przepływ netto na wej ciu do wierzchołka Y definiujemy jako:
I (X,Y) (4.9)
Åš
Dodatni przepływ netto wypływaj cy z wierzchołka definiuje si symetrycznie. Jedna z in-
terpretacji własno ci zachowania przepływu mówi, e dodatni przepływ netto na wej ciu
do wierzchołka ró nego od ródła i uj cia jest równy dodatniemu przepływowi na wyj ciu
z tego wierzchołka [1].
46
4.2.6.2. Sieci z wieloma ródłami i uj ciami
W problemie maksymalnego przepływu zamiast jednego ródła i jednego uj cia, mo e
pojawić si wiele ródeł i wiele uj ć. Na rysunku Rys. 4.23a przedstawiona jest przykła-
dowa sieć z P ródłami ^V V V ` i Q odbiorcami ^W W W `
Problem maksymalnego przepływu w sieciach z wieloma ródłami i wieloma uj ciami
mo na sprowadzić do zwykłego problemu maksymalnego przepływu. Na Rys. 4.23b wi-
dać, w jaki sposób sieć z Rys. 4.23a mo na przekształcić w zwykł sieć z jednym ródłem
i jednym uj ciem. Do sieci dodajemy  super ródło V oraz kraw d skierowan V V R
przepustowo ci F V V  dla ka dego L P Tworzymy tak e nowe  super uj-
cie W i dodajemy kraw d W W R przepustowo ci F W W  dla ka dego L Q
Intuicyjnie, ka dy przepływ w sieci (a) odpowiada przepływowi w sieci (b) i odwrotnie. Z
pojedynczego  super ródła V wypływa tyle, ile potrzebuj rzeczywiste ródła, natomiast
 super uj cie W jest w stanie przyj ć tyle, ile ł cznie wypływa z rzeczywistych uj ć.
Rys. 4.23 Sprowadzanie problemu maksymalnego przepływu z wieloma ródłami i wieloma uj-
ciami do problemu z jednym ródłem i jednym uj ciem
47
4.2.6.3. Algorytm Forda-Fulkersona
Algorytm Forda-Fulkersona słu y najogólniej do wyznaczania najwi kszego prze-
pływu, jaki da si uzyskać w niecyklicznym grafie skierowanym. Funkcjonuje kilka wersji
algorytmu wymy lonego w latach 50-tych, w naszym, przypadku obiektem rozwa a jest
wersja, z zerowymi warunkami, pocz tkowymi. Mówi c o warunkach pocz tkowych ma-
my na my li istniej ce niezerowe przepływy w chwili rozpoczynania działania algorytmu.
Wobec takich zało e graf zdefiniowany jest jedynie przez macierz incydencji w złowych,
gdzie elementami macierzy nie s odległo ci pomi dzy w złami, jak Z przypadku algo-
rytmu, Dijkstry, lecz pojemno ci. Algorytm dysponuj c tak zadan macierz oraz maj c
wyszczególnione w zły traktowane jako ródło oraz dren oblicza najwi kszy przepływ, ja-
ki da si uzyskać pomi dzy tymi dwoma w złami na wszystkich mo liwych drogach.
ródło ma niesko czon wydajno ć, przepływ przez graf jest ograniczony jedynie przez
pojemno ci poszczególnych kraw dzi grafu.
4.2.6.3.1. Opis działania algorytmu
Działanie algorytmu opiera, si na znajdowaniu wszystkich istniej cych dróg od
ródła, V do drenu W przez penetracj grafu w gł b. Najłatwiej to zademonstrować przy
pomocy przykładu:
Mamy dany niecykliczny graf skierowany:
Rys. 4.24 Analizowany graf.
Jego macierz incydencji przedstawia Tabela 4.5
48
Tabela 4.5
a b c d s t
a 0 2 0 7 0 2
b 0 0 0 0 0 0
c 3 0 0 1 0 0
d 0 0 0 0 0 4
s 3 0 5 0 0 0
t 0 0 0 0 0 0
4.2.6.3.2. Wynajdowanie drogi
Ka da interesuj ca nas droga b dzie si zaczynała, w w le V, wi c w poszukiwa-
niu, w zła po nim nast puj cego przeszukujemy wiersz V macierzy Tabela 4.5. Z w zła V
mo emy si przemie cić do w złów oznaczonych D oraz F - w macierzy na przeci ciu
wiersza V oraz kolumn D oraz F wyst puj niezerowe warto ci. Wybieramy pierwszy w ko-
lejno ci i przemieszczamy si do w zła D. Z w zła D stosuj c t sam metod post powa-
nia mo emy Z analogiczny sposób przemie cić si do w złów E, G oraz W, wybieramy w -
zeł E jako pierwszy w kolejno ci:
Rys. 4.25 Graf po przeanalizowaniu dwóch pierwszych gał zi.
Z w zła E nie mo emy i ć dalej (same zera w wierszu b macierzy), wracamy si , wi c do
w zła D i idziemy do pierwszego po w le, E, czyli do G. Z G mo emy i ć ju tylko do W i to
ko czy nam pierwsz cz ć algorytmu.
49
Rys. 4.26 Graf po przeanalizowaniu drogi z s do t.
Wa n zasad w tej cz ci algorytmu jest to, e nawet, je eli wynika to z przyj tej zasady
post powania, nie przechodzimy do w zła, który wyst puje w przebytej ju drodze
4.2.6.3.3. Transformacja grafu
Przemieszczaj c si po drodze V D G W znajdujemy kraw d lub kraw dzie o
najmniejszej pojemno ci. W tym przypadku jest to kraw d V D o pojemno ci równej 3.
Tak, wi c po wcze niej zdefiniowanej drodze mo emy przesłać 3 jednostki i jest to mak-
symalny przepływ drogi. Kraw d V D si nasyca i nie uwzgl dnia si jej w dalszym po-
st powaniu. Na pozostałych kraw dziach odejmujemy od ich pojemno ci obliczony wcze-
niej maksymalny przepływ drogi. Po transformacji graf oraz jego macierz incydencji w -
złowych zawiera Tabela 4.6.
Rys. 4.27 Graf po pierwszej transformacji.
50
Tabela 4.6
a b c d s t
a 0 2 0 0 2
4
b 0 0 0 0 0 0
c 3 0 0 1 0 0
d 0 0 0 0 0
1
s 0 5 0 0 0
0
t 0 0 0 0 0 0
Wytłuszczona czcionka i zacieniowane pole oznacza zmodyfikowane warto ci.
Post puj c zgodnie z wy ej przedstawionym algorytmem, kolejn dost pn drog b dzie
V F D G W o przepływie 1:
Rys. 4.28 Analiza drogi (s,c,a,d,t).
Po transformacji otrzymujemy graf pokazany na Rys. 4.29, który obrazuje macierz incy-
dencji opisanych w Tabela 4.7.
Rys. 4.29 Graf po drugiej transformacji.
51
Tabela 4.7
a b c d s t
a 0 2 0 0 0
3
b 0 0 0 0 0 0
c 0 0 1 0 0
2
d 0 0 0 0 0
0
s 0 0 0 0 0
4
t 0 0 0 0 0 0
Powielaj c jeszcze raz znany ju schemat wynajdujemy drog V F D W o przepływie 2:
Rys. 4.30 Analiza drogi (s,c,a,t).
Graf po transformacji przedstawia Rys. 4.31, a jego macierz incydencji Tabela 4.8.
Rys. 4.31 Graf po trzeciej transformacji.
52
Tabela 4.8
a b c d s t
a 0 2 0 3 0
0
b 0 0 0 0 0 0
c 0 0 1 0 0
0
d 0 0 0 0 0 0
s 0 0 0 0 0
2
t 0 0 0 0 0 0
Po tej operacji zaka czamy algorytm, gdy nie ma ju mo liwo ci dotarcia do drenu W - po
wyj ciu z w zła V przechodzimy przez w zeł F do w zła G po czym nie maj c adnej mo -
liwo ci wydostania si z w zła G (same zera w rz dzie G macierzy) cofamy si do wi zła F,
w którym sytuacja si powtarza (nie przechodzimy do w zła G, w którym ju przecie byli-
my). Jedyne, co mo emy zrobić to cofn ć si jeszcze o jeden krok do V co oznacza, e nie
ma ju adnego poł czenie mi dzy ródłem i drenem.
Znajdowanie całkowitego przepływu pomi dzy rodłem a drenem:
Całkowity przepływ pomi dzy ródłem V a drenem, W b dzie sum przepływów na
wszystkich mo liwych drogach, czyli:
na drodze V D G W przepływ wynosi 3
na drodze V F D G W przepływ wynosi 1
na drodze V F D W przepływ wynosi 2
Całkowity przepływ pomi dzy s a t wynosi (3 + l + 2) = 6.
53
5. MINIMALIZACJA SIECI O STRUKTURZE DRZEWIASTEJ
W tej cz ci omawiana jest problematyka optymalizacji przepustowo ci kanałów oraz
optymalizacji topologii sieci, na podstawie optymalizacji sieci drzewiastych.
Je eli chodzi o ten rodzaj sieci, nie wyst puje tutaj problem doboru trasy i dzi ki temu, w
stosunkowo prosty sposób, mo na przedstawić wa ne aspekty metod optymalizacji, prze-
pustowo ci i topologii, które mog być pó niej uogólnione. Ma to wa ne znaczenie prak-
tyczne, sieci drzewiaste s , bowiem modelem sieci teleinformatycznych spływowo - roz-
pływowych. Tak nazywamy tu sieci, których zadaniem jest przesyłanie informacji, od wie-
lu jednostek do głównego w zła oraz w kierunkach przeciwnych [2].
Przybli enie zagadnieniami optymalizacji przepustowo ci kanałów sieci, pozwola na osza-
cowanie mo liwo ci, zwi kszania przepustowo ci istniej cych ju kanałów, oraz poznanie
problemu optymalizacji topologii sieci, wyst puj cego w sytuacjach, gdy w gr wchodzi
tworzenie nowych kanałów. Ogólnie rzecz bior c, istota problemów optymalizacji przepu-
stowo ci kanałów i topologii sieci polega na znajdowaniu kompromisu pomi dzy kosztem
tworzenia sieci, a jako ci jej pracy. Na koszt tworzenia sieci składa si koszt tworzenia
kanałów oraz koszt budowy w złów. Pomijamy tutaj, analiz kosztow urz dze w zło-
wych, koncentruj c si głównie na kosztach tworzenia kanałów.
Koszt tworzenia kanału jest rosn c funkcj przepustowo ci nale y, wi c znale ć taki
przedział przepustowo ci poszczególnych kanałów, aby przy zachowaniu wymaga sta-
wianych jako ci przesyłania informacji przez sieć koszt tworzenia kanałów wchodz cych
w skład sieci był mo liwie mały [2].
Optymalizacj sieci drzewiastej mo emy rozpatrywać w dwu aspektach:
x W sieci o ustalonej topologii - pod wzgl dem optymalizacji przepustowo ci
x Pod wzgl dem optymalizacji topologii pozwalaj cej na swobodn komunikacj
pomi dzy stacjami i w złem centralnym.
x Na ogół problemy optymalizacji formujemy w ten sposób, e jeden z parametrów
np. koszt bierzemy jako kryterium optymalizacji, natomiast jako ć przesyłania in-
formacji przyjmujemy jako warunek ustalony.
x Dodatkowo nale y uwzgl dnić nast puj ce warunki:
x A
czne nat enie strumieni dopływaj cych do w zła (po uwzgl dnieniu ewentual-
nego strumienia traconego) musi być równe redniemu nat eniu strumieni wypły-
waj cych z w zła - (warunek zachowania strumienia).
x Nat enie rednie w strumieni płyn cych w kanałach jest nieujemne.
54
x Dla ka dego z kanałów, przepustowo ć & Z Y musi być wi ksza lub równa nat -
eniu, przepływaj cego przez niego strumienia 6Z Z Y [2].
x
5.1. Doł czenie w zła o najmniejszym koszcie ł czenia
Istota tego algorytmu doł czenie w zła o najmniejszym koszcie ł czenia polega na po-
dziale zbioru w złów na dwa pomocnicze zbiory:
[(E, $) min{[( , DE )}
(5.1)
Element zbioru $, dla którego koszt ten jest osi gany, oznaczamy jako D E . Mamy,
wi c:
[[E, D * (E)] [( , $E )
(5.2)
Wka dym kroku do zbioru A przerzucamy element b zbioru, B którego koszt poł czenia
ze zbiorem A jest minimalny, a wi c taki, e
[(E*, $) min{[( , $E )}
(6.3)
a do zbioru wybranych kanałów doł czamy kanał E D E W zeł E znajdujemy two-
rz c tablice 7, która w ka dej kolumnie zawiera elementy E %, koszt poł czenia tego ele-
mentu [ E $ oraz element D E $, dla którego koszt ten jest osi gany. Algorytm ten,
który nazwiemy algorytmem doliczania w zła o najmniejszym koszcie ł czenia, mo na
sformułować nast puj co [2] :
Krok l. Do zbioru $^ ` zaliczamy w zeł centralny Z , a do zbioru %^ ` wszystkie w -
zły ko cowe.
Krok n-ty, Dla zbiorów $^Q ` oraz %^Q ą ` tworzymy tablic 7^Q`. Z tablicy tej wybie-
ramy w zeÅ‚ E Q któremu odpowiada minimalny koszt [ E Q $ Q ² O . WzeÅ‚ E Q
przenosimy ze zbioru B do A to znaczy tworzymy zbiory
$(Q) $(Q 1) 0 {E * (Q)}
%(Q) %(Q 1) {E * (Q)}
(5.4)
55
Jako kanał nale cy do poszukiwanego drzewa bierzemy kanał ł cz cy w zeł E Q z w -
złem okre lonym w trzecim wierszu kolumny tablicy 7 Q Algorytm ko czymy, gdy zbiór
B stanie si zbiorem pustym (ko czy si po : krokach).
5.1.1. Przykład doł czenie w zła o najmniejszym koszcie ł czenia
Bierzemy sieć z kosztami kanałów okre lonymi w poni szej macierzy
0 11 6 30 16
ª º
«11 0 15 17 13
«
«
X 6 15 0 21 7 (5.6)
«30 17 21 0 15
«
«16 13 7 15 0
Ź ź
Krok 1. Przyjmujemy
A(1) ={0}
B(1)={1,2,3,4}
Krok 2. Na podstawie macierzy X tworzymy Tabela 5.1:
Tabela 5.1
b 1 2 3 4
x[b,A(1)] 11 6 30 16
a*(b) 0 0 0 0
Z tabeli otrzymujemy b*(2) = 2, a*[b*(2)] = 0. Do zbioru kanałów doł czamy kanał (2,0)
oraz tworzymy zbiór:
A(2)={0,2} (5.7)
B(2) = {1,3,4} (5.8)
Krok 3. Tabela 5.2 ma nast puj c postać:
56
Tabela 5.2
b 1 3 4
x[b,A(1)] 11 21 7
a*(b) 0 2 2
Z tabeli otrzymujemy b*(3) = 4, a*[b(3)] = 2. Do sieci wł czamy kanał (4,2)
Przyjmujemy
A(1) = {0,2,4} (5.9)
B(1) = {1,3} (5.10)
Krok 4. Znajdujemy Tabela 5.3.
Tabela 5.3
b1 3
x[b,A(1)] 11 15
a*(b) 0 4
Z tabeli mamy b*(4) = 1, a*[b*(4)] = 0. Powi kszamy zbiór kanałów o kanał (1,4) i otrzy-
mujemy zbiór:
A(1) = {0,2,4,1} (5.11)
B(1) = {3} (5.12)
Krok 5. Tabela 5.4 ma nast puj c postać:
Tabela 5.4
b3
x[b,A(1)] 15
a*(b) 4
57
Do sieci wł czamy kanał (3,4)
Rys. 5.1 Sieć otrzymana w wyniku stosowania algorytmu
5.2. Metoda odwróconego drzewa
Poni ej przedstawimy opis algorytmu odwróconego drzewa słu cego do optymalizacji
topologii sieci drzewiastych przy danych kosztach kanałów i ograniczeniu przepustowo ci
kanałów.
Sieć charakteryzuje wiele parametrów. Na ogół posługujemy si jednak tylko dwoma pod-
stawowymi parametrami, a mianowicie parametrem charakteryzuj cym koszt tworzenia
sieci i parametrem charakteryzuj cym jako ć przesyłania informacji przez sieć.
Algorytm odwróconego drzewa ma za zadanie optymalnie poł czyć ze sob w zły ko -
cówkowe i w zeł centralny minimalizuj c przy tym koszt poł cze i uwzgl dniaj c ogra-
niczenia przepustowo ci.
Najpierw wybieramy w zeł Y , do którego mo na doj ć tylko najbardziej kosztownymi
kanałami, a nast pnie do w zła takiego doł czamy w zły ko cówkowe, które daj si po-
ł czyć z nim kanałami mo liwie tanimi. Je li w złów wybranych jest ju tyle, e zwi k-
szanie ich liczby prowadziłoby do tego, e suma strumieni pochodz cych od wybranych
w złów przekraczałaby przepustowo ć C ka dego z kanałów, post powanie ko czymy [2].
Oznaczmy symbolem $ tak otrzymany zbiór. Dla zbioru tego stosujemy algorytm doł -
czania najta szego kanału i znajdujemy kanał ł cz cy jeden z w złów ze zbioru $ z w -
złem centralnym. Je eli zbiór $ nie obejmuje wszystkich w złów ko cówkowych, to za-
czynaj c od nienale cego do zbioru $ w zła ko cówkowego, do którego mo na doj ć od
innych, nienale cych do zbioru $ w złów jedynie najbardziej kosztownymi kanałami,
konstruujemy w podobny sposób zbiór $ itd. a do wyczerpania wszystkich w złów ko -
58
cówkowych. W zeł, dla którego koszt poł czenia z wybranym ju zbiorem w złów jest
najmniejszy, powinien być poszukiwany w zbiorze, %, który powstaje po odrzuceniu ze
zbioru : (zbiór wszystkich w złów ko cówkowych) w złów zawartych w zbiorach : i $,
gdzie : jest zbiorem w złów ko cówkowych, takich, e po doł czeniu w zła u do zbioru
$ ł czne nat enie strumieni przekracza przepustowo ć & kanałów lub
[(X, $) ! (X[ ,0)
(5.13)
lub
[[X, D * (X)] ! [[ * (XD ),0]
(5.14)
W powy szych nierówno ciach D X oznacza w zeł nale cy do zbioru $, dla
którego koszt poł czenia z w złem u jest najmniejszy, a wi c równy kosztowi
[>X $ Q ą @ doł czenia w zła X do zbioru $ Q ą Omawiane post powanie mo emy
zrealizować za pomoc algorytmu składaj cego si z dwóch cz ci:
5.2.1. Algorytm odwróconego drzewa
Algorytmu składaj cego si z dwóch cz ci:
Cz ć I
Iteracja 1
Krok 1. Znajdujemy w zeł ko cówkowy Y taki, e
[(Y ,0) t [(Z,0)
(5.15)
dla wszystkich w złów ko cówkowych w W. Innymi słowy, v1,1 jest w złem,
którego koszt doł czenia bezpo rednio do w zła centralnego jest najwi kszy.
Bierzemy
$ (1) {Y }
(5.16)
59
Krok n-ty. Bior c w miejsce zbioru $ zbiór $ Q ą tworzymy zgodnie z podanymi po-
przednio zasadami zbiór %, który oznaczymy % Q ą . Znajdujemy w zeł Y Q % Q ą
taki, e koszt poł czenia tego w zła do zbioru A1(n  1) jest najmniejszy: [>Y $ Q @
[>Y $ Q @ dla wszystkich Y % Q Ä… Bierzemy $ Q $ Q 0 ^Y `. Pierwsz
iteracj ko czymy w kroku N1, dla którego zbiór B1(N1) staje si zbiorem pustym. Je eli
zbiór W  A1(N1) nie jest pusty, to rozpoczynamy drug iteracj ( k = 2). W przeciw-
nym razie przechodzimy do cz ci II algorytmu.
Iteracja k-ta
Post pujemy jak w iteracji 1, bior c w miejsce zbioru W zbiór
: : $ (1 )
(5.17)
Cz ć I algorytmu ko czymy po k-tej iteracji, po której zbiór Wk+1 staje si zbiorem pu-
stym.
Cz ć II
Do ka dego ze zbiorów $ 1 $ 1 0 ^ `, M . stosujemy algorytm doł cze-
nia w zła o najmniejszym koszcie ł czenia. Najpierw wybieramy w zeł o najmniejszym
koszcie poł czenia do w zła centralnego, a nast pnie podł czamy jak najmniejszym kosz-
tem wszystkie pozostałe w zbiorze w zły do tego wybranego.
5.3. Metoda Essau-Williamsa
Algorytm Essau-Williamsa słu y do rozwi zywania zadania optymalizacyjnego PO-
Tx|C, R, jakim jest znalezienie sieci drzewiastej o mo liwie małym koszcie budowy,
przy czym na kanały nało one jest ograniczenie C, e nat enie całkowitego strumienia
przepływaj cego przez kanał nie mo e przekraczać jego danej przepustowo ci [2].
Optymalizacja sieci na podło u drzewiastym polega na zamianie w zła bardzo
wykorzystywanego przez inny w zeł, likwidacji niepotrzebnych, czyli mało u ywanych
w złów, oraz na przebudowie sieci w taki sposób, aby kosz ostateczny sieci był jak naj-
mniejszy.
60
5.3.1. Algorytm optymalizacyjny wykorzystuj cy zasad najszybszego
przyrostu
Rodzin bardzo uniwersalnych, a przy tym skutecznych metod poszukiwania ekstre-
mum stanowi iteracyjne metody wykorzystuj ce zasad najszybszego spadku. Najbardziej
znanym ich reprezentantem s tzw. metody gradientowe. Omówimy tu bli ej podstawowy
algorytm tego typu, zwany algorytmem Essau Williamsa. W najprostszej swojej postaci
algorytm ten mo e być wykorzystywany do poszukiwania rozwi zywania problemu opty-
malizacyjnego 327[. Nieznacznie zmodyfikowany mo e być równie wykorzystany do
rozwi zania problemu 327[_& 5, jakim jest znalezienie sieci drzewiastej o mo liwie
małym koszcie budowy, przy czyn na kanały nało one jest ograniczenie &, e nat enie
całkowitego strumienia przepływaj cego przez kanał nie mo e przekraczać jego danej
przepustowo ci [2]. Ogromny post p technologii urz dze przetwarzania sygnałów, a
zwłaszcza urz dze impulsowych stosowanych w maszynach cyfrowych, stwarza du
swobod wyboru sposobów pracy urz dze odbiorczych i nadawczych. Powstaje, wi c
problem optymalizacji reguł odbioru oraz reguł nadawania. Jako ć optymalnej reguły od-
bioru po ustaleniu własno ci ródła informacji zale y od własno ci kanału, a w szczegól-
no ci od rozkładów warunkowych sygnału wyj ciowego, oraz od reguł i kosztów nadawa-
nia [2]. Równie przy projektowaniu sieci okazuje si , e głównym problemem s pono-
szone koszty, a optymalizacja sieci ma wła nie te koszty zminimalizować.
5.3.2. Koszt tworzenia sieci
Parametr charakteryzuj cy koszt sieci okre lamy na ogół na podstawie parametrów
charakteryzuj cych koszty tworzenia poszczególnych kanałów i w złów. Koszt tworzenia
jednego pojedynczego kanału zale y zarówno od ukształtowania geometrycznego kanału, a
w szczególno ci od jego długo ci, jak i od jego przepustowo ci.
Poza kanałami w skład sieci wchodz w zły. Koszt tworzenia w zła zale y zarówno od
funkcji realizowanych przez ten w zeł, jak i od przepustowo ci w zła &ś, zdefiniowanej
jako najwi ksze nat enie strumienia sygnałów, jakie w zeł mo e prawidłowo przetwa-
rzać. Koszt tworzenia w zła [ &ś ma na ogół własno ci podobne do własno ci kosztu two-
rzenia kanału. Je li wi c tworzenie w zła wliczyć w koszty tworzenia korzystaj cych z te-
go w zła kanałów, to tak uzupełniony koszt tworzenia kanału b dzie mieć własno ci po-
dobne do pierwotnego kosztu tworzenia samego kanału. Z tego wzgl du w dalszych roz-
wa aniach b dziemy zakładać, e koszt tworzenia w złów wliczany jest w koszt tworzenia
61
kanałów sieci. Rozwa my sieć [ , ł cz c w zły ko cówkowe z w złem centralnym.
Przyjmijmy nast puj ce oznaczenia [2] :
0 O - w zeł poł czony bezpo rednio z w złem centralnym w = 0;
'0 O - drzewo nale ce do sieci [, wychodz ce z w zła 0 O ;
[EO X Y - sieć powstaj ca przez usuni cie z sieci [ kanału bezpo redniego 0 O oraz doł -
czenie kanału X Y ł cz cego w zeł X ' 0 O z w złem Y ' 0 O
[ [  koszt utworzenia sieci [EO X Y
W takim wypadku całkowity koszt utworzenia poł czenia okre lony jest wzorem:
G[(E ,X,Y) [([ ) [([ )
(5.18)
gdzie [ [ jest kosztem sieci pierwotnej;
5.3.3. Algorytm Essau-Williamsa
Istota algorytmu polega na tym, e w sposób heurystyczny wybieramy pewn sieć po-
cz tkow [ , a nast pnie ulepszamy j , zast puj c kanał centralny E gdzie E jest
tym kanałem, dla którego osi gany jest maksymalny zysk '[ okre lony wzorem
'[ PLQG[ EO Kanałem X 0 Y 0 gdzie X 0 ' 0 Y 0 'W 0 s pa-
ry w złów, dla których osi gana jest warto ć minimalna G[ 0 okre lana wzorem [2].
G[(E ) minG[(E , ,YX )
(5.19)
Algorytm optymalizuj cy sieć drzewiast na podstawie algorytmu Essau-Williamsa rozpo-
czyna si od tego, e najpierw musimy podać poło enie, nazw i obci enie pierwszego
w zła jako w zła głównego, do którego zostan podł czone pozostałe w zły. Nast pnie
okre lamy przepływno ć. W ten sposób powstaje główny w zeł.
Kolejnym krokiem jest okre lenie poło enia, obci enia i podania nazwy nast pnych w -
złów, przy czym je li obci enie jest wi ksze ni przepływno ć, ł cze nie b dzie brane pod
uwag podczas optymalizacji.
62
5.3.4. Przykładowe rozwi zanie metod Essau-Williamsa
Krok 1. Bierzemy sieć gwia dzist [ .
Krok n-ty. Dla sieci [ Q znajdujemy zespół w złów, dla których osi gane jest minimum,
przy czym minimum tego szukamy w ród zespołów spełniaj cych narzucone ogranicze-
nia.
Algorytm ko czy, gdy '[ ! .
Przykład 1.
Zakładamy nast puj ce obci enia: dla w zła 1 obci enie wynosi 6, dla w zła 2 obci e-
nie wynosi 2, dla w zła 3 obci enie wynosi 5, dla w zła 4 obci enie wynosi 4, oraz
przyjmujemy, e przepustowo ć & [1].
Krok 1. Zakładamy sieć gwia dzist przedstawion na rysunku Rys. 5.2 o koszcie 63.
Rys. 5.2 Sieć pocz tkowa przed rozpocz ciem procesu optymalizacji
Poniewa obci enie wszystkich kanałów jest mniejsze od zadanej przepustowo ci, ka dy-
kanał b dzie brany pod uwag podczas optymalizacji.
Krok 2. Tworzymy nast puj ce tablice:
dla kanału (0,1)
Tabela 5.5
pary X Y (1,2) (1,3) (1,4)
87 10
[([ )
46 2
G[(E ,X,Y)
63
dla kanału (0,2)
Tabela 5.6
pary X Y (2,1) (2,3) (2,4)
8 7 6
[([ )
9 15 1
G[(E ,X,Y)
dla kanału (0,3)
Tabela 5.7
pary X Y (3,1) (3,2) (3,4)
11 7 9
[([ )
G[(E ,X,Y) -13 -9 -15
dla kanału (0,4)
Tabela 5.8
pary X Y (4,1) (4,2) (4,3)
10 6 9
[([ )
G[(E ,X,Y) -3 -9 -1
Po dokonaniu optymalizacji maksymalny zysk '[ osi gany jest dla w zła 3 oraz ka-
nału (3,4). Nowa sieć otrzymana za pomoc algorytmu przedstawiona jest na Rys. 5.3.
64
Rys. 5.3 Sieć ko cowa uzyskana w wyniku zastosowania algorytmu Essau-Williamsa
65
6. OPTYMALIZACJA TOPOLOGII SIECI
Najbardziej ogólnym problemem optymalizacyjnym jest problem optymalizacji topo-
logicznej. W problemie takim przyjmujemy pewne ogólne parametry charakteryzuj ce
sieć, jak np. koszt jej budowy czy te jako ć przesyłania informacji, nie narzucamy nato-
miast z góry struktury poł cze . W wypadku sieci o dowolnej strukturze nie s znane
ogólne metody rozwi zywania zada optymalizacji topologicznej. W naszym przypadku
rozwi emy problem optymalizacji sieci poprzez algorytm stopniowego odejmowania po-
szczególnych gał zi od innych w sieci oraz od niej samej. Je eli warto ć jakiej gał zi jest
zero to nic nie wykonujemy. W ten sposób otrzymana sieć jest zminimalizowana pod
wzgl dem kosztu przebiegu pakietu po wszystkich gał ziach danej sieci.
Podany poni ej algorytm powoduje przej cie z sieci pocz tkowej do zoptymalizowanej
pod wzgl dem przepustowo ci poprzez stopniowe odejmowanie od siebie sieci po rednich.
Istota algorytmu polega na tym, e z sieci wydzielamy kolejno mniejsze podsieci a doj-
dziemy do rezultatu ko cowego.
6.1. Problem optymalizacji topologicznej.
Rozwi zanie problemu optymalizacji topologicznej sieci wymaga w zasadzie rozwi za-
nia dla wielu wariantów topologicznych sieci problemu optymalizacji przepustowo ci, ten
za z kolei wymaga rozwi zania problemu optymalizacji przepływów.
Trudno ci te powoduj , e tylko przy bardzo ograniczaj cych zało eniach udało si roz-
wi zać problem optymalizacji topologicznej w sposób systematyczny [2].
6.2. Funkcja kryterialna optymalizacji.
Omówimy tu rozwi zanie tego problemu przyjmuj c funkcj kryterialn :
& Åš &(Z,Y)
(6.1)
66
Problem ma, wi c nast puj c postać:
Nale y znale ć sieć MR, która umo liwia zrealizowanie danej macierzy przepływów mi -
dzybiegunowych 5 w sytuacji, gdy w danej chwili sieć udost pniona jest tylko jednej parze
biegunowa przy tym minimalizuje przepustowo ć ł czn &6.
6.3. Realizacja sieci o danej symetrycznej macierzy przepusto-
wo ci.
Problem syntezy sieci o danej macierzy przepustowo ci jest w przypadku ogólnym pro-
blemem nader zło onym [2]. Zajmiemy si tu wpierw najprostszym przypadkiem, zakłada-
j c, e macierz przepustowo ci jest symetryczna, tj., e:
Cwv = Cvw (6.2)
Wykazano ju , e macierz przepustowo ci mo e być rozbita na podmacierze, przy czym
podmacierz w górnym prawym naro niku macierzy blokowej wy szego rz du zawiera ta-
kie same elementy, równe elementowi znajduj cemu si na pierwszej przek tnej nad prze-
k tn główn . Przykładem takiej macierzy jest macierz symetryczna.
f 5 5 3 3 1 1 1
5 f 6 3 3 1 1 1
5 6 f 3 3 1 1 1
3 3 3 f 7 1 1 1
&
3 3 3 7 f 1 1 1
1 1 1 1 1 f 8 8
1 1 1 1 1 8 f 10
1 1 1 1 1 8 10 f
(6.3)
Przyst puj c do problemu syntezy sieci maj cej macierz przepustowo ci o takiej struktu-
rze, we my pod uwag sieć pokazan na rysunku Rys. 6.1. Wobec zało enia o symetrii
macierzy przepustowo ci zakładamy, e kanały biegn ce w przeciwnych kierunkach maj
jednakowe przepustowo ci:
67
& &
(6.4)
Ka dy przekrój oddzielaj cy w zeł 1 od w zła 2 musi zawierać kanał (1,2). Zatem mini-
malna przepustowo ć przekroju & & Podobnie jest pomi dzy ka d par w złów
przyległych.
We my z kolei pod uwag dwa w zły nieprzyległe np. 1 i 4. Wszystkie przekroje mo emy
podzielić na trzy klasy, w zale no ci od tego czy zawieraj kanały (1,2), (2,3), czy te
(3,4). W obr bie ka dej z klas najmniejsz przepustowo ć ma przekrój zło ony tylko z
jednego spo ród tych trzech kanałów [2].
6.4. Realizacja sieci na podstawie sieci macierzy symetrycznej.
Rys. 6.1 Sieć realizuj ca symetryczn macierz przepustowo ci - przypadek ogólny
Rys. 6.2 Sieć realizuj ca symetryczn macierz przepustowo ci sieć odpowiadaj ca macierzy z
przykładu
Zatem dla naszej sieci & PLQ>& & & @ Mo emy, wi c ogólnie stwier-
dzić, e dla sieci pokazanej na Rys. 6.1 mamy &ZY & Z Y dla w złów w i v przyległych,
to jest takich, e Y Z . Dla w złów w i v nie przyległych, to jest takich, e Y!Z, mamy
&ZY PLQ & X X , przy czym minimum szukamy dla par X Z X Z ; X
Z X Z X Y X Y. Tak, wi c sieć pokazana na Rys. 6.1 ma symetryczn
macierz przepustowo ci, przy czym za przepustowo ci bezpo rednio ł cz ce w zły bie-
rzemy elementy macierzy z przek tnej pierwszej nad przek tn główn . W ten sposób jako
68
sieć realizuj c macierz z (6.3) otrzymujemy siec pokazan na Rys. 6.2. Macierz przepu-
stowo ci jest jednoznacznie okre lona za pomoc elementów &Z Z nad przek tn
główn oraz elementów &Z ,w pod przek tn główn . A
atwo zauwa yć, e sieci realizu-
j c tak macierz jest znowu sieć pokazana na rysunku 1 z tym, e &Z Z & Z Z
oraz &Z Z & Z Z natomiast kanały przenosz ce informacj w przeciwnych kie-
runkach nie musz mieć jednakowej przepustowo ci.
6.5. Optymalizacja sieci o danej symetrycznej macierzy prze-
pustowo ci.
Wybieraj c pokazan na Rys. 6.1 sieć realizuj c symetryczn macierz przepustowo ci,
nie brali my pod uwag funkcji kryterialnej &6 Obecnie poka emy, e dokonuj c mody-
fikacji tej sieci mo emy otrzymać optymaln , w sensie kryterium &6, sieć realizuj c dan
symetryczn macierz przepustowo ci. We my wpierw sieć o strukturze takiej jak sieć z
Rys. 6.2, z jednakowymi przepustowo ciami &. Jak łatwo zauwa yć, ka da z przepustowo-
ci pomi dzy dowoln par w złów jest jednakowa i wynosi &. A
czna przepustowo ć ka-
nałów wynosi, wi c 2WC, gdzie W jest liczb w złów. Wprowad my teraz dodatkow pa-
r kanałów pomi dzy kanałami skrajnymi, jak to pokazano na rysunku Rys. 6.4.
Rys. 6.3 Pomocnicza sieć do rozwi zywanie problemu minimalizacji ł cznej przepustowo ci ka-
nałów - sieć pierwotna
69
Rys. 6.4 Pomocnicza sieć do rozwi zywanie problemu minimalizacji ł cznej przepustowo ci ka-
nałów - sieć zmodyfikowana
Pomi dzy ka d par w złów mamy teraz dwie trasy jak to pokazano liniami przerywa-
nymi na Rys. 6.4, je li wi c wzi ć sieć z przepustowo ciami pokazanymi na Rys. 6.4, to
przepustowo ci pomi dzy dowoln par w złów b d takie same jak dla sieci z Rys. 6.1.
Jednak e ł czna przepustowo ć kanałów wynosi teraz tylko : & . A
atwo zauwa yć,
e jest to mo liwie najmniejsza ł czna przepustowo ć kanałów sieci, dla której
&Z Y & FRQVW. Podamy teraz algorytm przekształcenia podanej sieci 1, realizuj cej
symetryczn macierz przepustowo ci w taki sposób, e przekształcona sieć ma tak sam
macierz przepustowo ci, jak ma sieć pocz tkowa, a przy tym ł czna suma przepustowo ci
sieci przekształconej jest minimalna. Istota algorytmu polega na tym, e z sieci M wydzie-
lamy kolejno sieci o postaci takiej jak na Rys. 6.3 z jednakowymi przepustowo ciami ka-
nałów, a ka d z tych sieci zast pujemy now sieci o strukturze takiej jak na Rys. 6.4. Dla
ujednolicenia zapisów sieć M oznaczać b dziemy dalej symbolem M
6.6. Metoda  dziel i zwyci aj .
Wiele wa nych algorytmów ma struktur rekurencyjn : W celu rozwi zania danego pro-
blemu algorytm wywołuje sam siebie przy rozwi zywaniu podobnych podproblemów. W
algorytmach tych cz sto stosuje si metod  dziel i zwyci aj [2] (ang. divide-and-
conquer): problem jest dzielony na kilka mniejszych podproblemów podobnych do pocz t-
kowego problemu, problemy te s rozwi zywane rekurencyjnie, a nast pnie rozwi zania
70
wszystkich podproblemów s ł czone w celu utworzenia rozwi zania całego problemu.
Mo emy wyró nić trzy etapy:
Dziel: Dziel problemy na podproblemy.
Zwyci aj: Rozwi zujemy podproblemy rekurencyjnie, chyba, e s one małego rozmiaru
i ju nie wymagaj rekursji  u ywamy wtedy bezpo rednich metod.
Poł cz: A
czymy rozwi zania podproblemów, aby otrzymać rozwi zanie całego problemu.
Tabela 6.1
Krok Czynno ć
l
W Sieci I (pn znajdujemy par kanałów o najmniejszej przepusto-
wo ci np.C1.
2
I
Tworzymy pomocnicz sieć jak na rysunku 3, z jednakowymi
przepustowo ciami kanałów C=C1.
3
I
Od przepustowo ci kanałów sieci odejmujemy odpowiednie
I
przepustowo ci sieci . Kanały o przepustowo ci zerowej uwa-
I
amy za nie istniej ce Wobec tego sieć rozpada si na zespół
I
sieci ...I omawiana tu operacj nazywać b dziemy odejmo-
4
I
Do ka dej z sieci stosujemy post powanie takie jak do sieci
I w punktach 1-3; odpowiednie sieci pomocnicze oznaczymy
5 Otrzymujemy w wyniku post powania 4 wykonanego nad ka d z
I I
sieci ,gdzie j=1,2..,Mn-1. zespół zespołów sieci , j =
6 Post powanie ko czymy w kroku N, gdy przepustowo ci kanałów
we wszystkich sieciach I s równe zeru.
7
I
Ka d z sieci I zast pujemy sieci .
8
I
Nakładamy na siebie sieci sumuj c przepustowo ci ewentu-
alnych kanałów równoległych. Tak otrzymana sieć jest sieci prze-
71
6.6.1. Opis poszczególnych kroków minimalizacji
Poniewa zast puj c sieć M sieci M nie zmieniamy macierzy przepustowo ci
dla sieci MMQS, przeto nietrudno wykazać, e macierz przepustowo ci sieci przekształconej
M jest taka sama jak macierz przepustowo ci sieci pierwotnej M .
Przykład działania algorytmu.
Rys. 6.5 Sieć pierwotna
Rys. 6.6 Kolejne etapy optymalizacji sieci
Rys. 6.7 Sieć poszukiwana
72
Bierzemy pod uwag sieć pierwotn pokazana na Rys. 6.5. W lewej cz ci Rys. 6.6 poka-
zane s cz ci pomocnicze oraz sieci , które powstaj w wyniku odejmowania sieci po-
mocniczej od sieci M . Po prawej stronie rysunku okazano natomiast odpowiadaj ce sie-
ciom pomocniczym sieci F o minimalnej przepustowo ci Å‚ cznej. Poszukiwan sieci
jest pokazana na Rys. 6.7 sieć M , która powstaje przez nało enie sieci M [2].
73
7. METODA DOST PU DO A
CZA CSMA/CD
Technik lokalnych sieci komputerowych, która odniosła najwi kszy sukces w ci gu
ostatnich 20 lat, jest Ethernet. Rozwijana była ona w połowie lat siedemdziesi tych przez
naukowców z ;HUR[ 3DOR $OWR 5HVHDUFK &HQWHU 3$5& Ethernet jest działaj cym przy-
kładem zastosowania ogólniejszej metody dost pu w lokalnej sieci komputerowej, zwanej
metod wielodost pu do ł cza sieci, z badaniem stanu kanału i wykrywaniem kolizji DQJ
&DUULHU 6HQVH 0XOWLSOH $FFHVV ZLWK &ROOLVLRQ 'HWHFW , w skrócie CSMA/CD.
Jak wskazuje nazwa CSMA, Ethernet jest sieci wielodost pn (zbiór w złów nadaje i
odbiera ramki na ł czu współdzielonym). Dlatego mo emy wyobrazić sobie Ethernet jako
szyn , do której przył czono wiele stacji. Badanie stanu kanału DQJ FDUULHU VFQVH w na-
zwie CSMA/CD oznacza, e wszystkie w zły s w stanie rozró nić mi dzy ł czem nie-
czynnym a ł czem zaj tym, a wykrywanie kolizji DQJ FROOLVLRQ GHWHFW oznacza, e w zeł
nasłuchuje podczas nadawania i dlatego mo e wykryć, kiedy nadawana przez niego ramka
interferuje (koliduje) z ramk nadawan przez inny w zeł [8].
Zasada działania sieci Ethernet opiera si na idei dost pu rywalizacyjnego (random ac-
cess). Podstawowym zało eniem jest to, e ograniczenia na moment, w którym stacja mo-
e podj ć nadawanie, powinny być bardzo łagodne, a je li w zwi zku z tym wyst pi koli-
zja, to nadawanie zniekształconej ze wzgl du na ten fakt ramki nale y po pewnym czasie
powtórzyć.
Warto zauwa yć, e je li czas nadawania ramki jest dłu szy od czasu propagacji, to przed
wysłaniem warto si upewnić czy w ł czu nie odbywa si transmisja, Umo liwia to tzw.
funkcja nasłuchu (carrier sense). Przy u ywaniu takiej metody dost pu wyst pienie kolizji
staje si mo liwe jedynie w pocz tkowym odcinku czasowym nadawania ramki, nie dłu -
szym ni podwójny czas propagacji sygnału w ł czu. Odbiorniki maj zdolno ć wykrywa-
nia sygnału w ł czu i gdy to nast pi przerywaj transmisj (w rzeczywistych rozwi za-
niach transmisja jest podtrzymywana jeszcze przez pewien czas  po to, aby zwi kszyć
prawdopodobie stwo wykrycia kolizji.
7.1. Algorytm stacji nadaj cej
Protokół Ethernet po stronie odbiornika jest prosty. Znacznie bardziej skomplikowany
74
jest algorytm po stronie nadajnika. Algorytm stacji nadaj cej przedstawia Rys. 7.1.
Rys. 7.1 Algorytm stacji nadaj cej
Kiedy nadajnik ma ramk do nadania, a linia jest wolna, to nadaje ramk natychmiast. Nie
ma adnych negocjacji z innymi nadajnikami. Adapter mo e zajmować lini tylko przez
pewien ustalony czas, decyduje o tym górna granica 1500 bajtów. Adapter musi czekać
przynajmniej 9,6Ps zanim zacznie nadawać nast pn ramk . Daje to innym adapterom
szanse na nadawanie swoich ramek. Kiedy nadajnik ma ramk do nadania, a linia jest zaj -
ta to czeka, na zwolnienie medium i nast pnie natychmiast nadaje. O protokole Ethernetu
mówimy, e jest WUZDá\, poniewa adapter posiadaj cy ramk do nadania nadaje j z
prawdopodobie stwem 1 od momentu zwolnienia linii. W ogólno ci algorytm S WUZDá\
nadaje z prawdopodobie stwem 0 <= p <= 1  od chwili, gdy linia si zwolni. Przyczyna,
dla której wybrano p<1, jest taka e wiele adapterów mo e czekać a linia si zwolni. Tyl-
ko jeden z oczekuj cych adapterów mo e nadawać, po zwolnieniu medium.
Poniewa algorytm nie posiada scentralizowanego sterowania, mo liwe jest, e dwie stacje
(albo wi cej) rozpocznie nadawanie w tej samej chwili. Przyczyny tego mog być dwie.
Albo oba stwierdzaj , e linia jest wolna albo oba czekaj na zwolnienie linii. Kiedy zaj-
dzie takie zdarzenie mówimy, e dwie ramki koliduj ze sob . Ka dy nadajnik posługuj cy
si protokołem CSMA CD jest w stanie stwierdzić, e doszło do takiej kolizji. W momen-
cie, gdy nadajnik stwierdzi, e ramka pochodz ca od niego koliduje z inn , wtedy nadaje
32-bitow sekwencj zagłuszaj c , w ten sposób upewnia si , e pozostałe stacje te wy-
kryj kolizj i zako czy transmisj . Nadajnik w przypadku kolizji wy le co najmniej 96 bi-
75
tów tj. 64 bity preambuły i 32 bity sekwencji zagłuszaj cej. Aby mieć pewno ć, e ramka
która jest w tej chwili nadawana nie koliduje z inn ramk , nadajnik musi nadać a 512 bi-
tów. Jest to czas wystarczaj cy w sieci 10 Mb/s na transmisj 512 bitów, wynikaj cy z ilo-
czynu RSy QLHQLD [ V]HURNR ü SDVPD (WKHUQHW Minimalna ilo ć bitów, któr musi przesÅ‚ać
nadajnik jest zmienna w zale no ci od rodzaju topologii. Je eli nadajnik wykrył kolizj
wówczas wstrzymuje transmisj odczekuj c pewn ilo ć czasu przed ponowieniem próby.
Je li i ta próba si nie powiedzie wówczas podwaja czas oczekiwania, przed ka d prób
retransmisji. Technik t okre lamy jako Z\FRI\ZDQLH VL Z\NáDGQLF]H DQJ H[SRQHQWLDO
EHFN RII . Adapter rezygnuje po 16 próbach i powiadamia komputer o bł dzie nadawania.
76
8. POWI ZANIA MI DZY ROUTINGIEM A MODELEM OSI
Aby upro cić funkcje sieciowe, modele sieci wykorzystuj warstwy. Rozdzielenie
pełnionych funkcji przez sieć, nazywane jest podziałem na warstwy. Podział taki zastoso-
wany został w modelu OSI, który wykorzystuje warstwy, aby wdro yć komunikacj mi -
dzy komputerami i ułatwić jej zrozumienie. Ka da z warstw pełni pewn okre lon funk-
cj , co pozwala projektantowi sieci na wybór odpowiednich urz dze sieciowych i zada
przypisanych do konkretnej warstwy.
Zalety wynikaj ce z warstwowego podziału modelu sieci [4]:
x dziel aspekty funkcjonowania sieci na mniej zło one elementy
x okre laj standardowe interfejsy, zapewniaj ce kompatybilno ć z funkcj plug and
play, pozwalaj projektantom skupić wysiłki zwi zane z projektowaniem i rozwo-
jem sieci na poszczególnych, modularnych funkcjach
x standaryzuj poszczególne funkcje modularne, umo liwiaj c im współprac
x zapobiegaj wpływowi zmian w jednym obszarze na pozostałe, co pozwala ka de-
mu z obszarów szybciej si rozwijać
x dziel zło one funkcje sieciowe na odr bne, łatwiejsze do zrozumienia operacje.
8.1. Warstwowy model sieci OSI
Model OSI podzielony jest na siedem warstw. Ka da warstwa w modelu OSI pełni okre-
lona funkcj . Warstwowy model sieci przedstawia Tabela 8.1:
Tabela 8.1
7 Aplikacji - Sieciowe przetwarzanie aplikacji
6 Prezentacji - Prezentacja danych
5 Sesji  Komunikacja miedzy hostami
4 Transportu  Poł czenia mi dzy w złami
3 Siec  Adresy i najlepsze cie ki
2A
cza danych  Dost p do mediów
1 Fizyczna  Transmisja binarna
77
W dalszej cz ci naszej pracy opisane s pokrótce cechy ka dej z warstw. W sposób
bardziej szczegółowy zajmiemy si warstw trzeci , poniewa to wła nie na poziomie tej
warstwy realizowany jest routing.
Warstwa aplikacji (warstwa 7) udost pnia usługi sieciowe aplikacjom u ytkownika. Mo e
na przykład dostarczać usług przekazywania plików aplikacji przetwarzaj cej tekst.
Warstwa prezentacji (warstwa 6) zapewnia prezentacj danych i odpowiednie forma-
towanie oraz negocjowanie składni stosowanej podczas ich przekazywania. Gwarantuje, e
dane otrzymane z sieci b d nadawały si do wykorzystania przez aplikacj , a tak e, e
wysyłane przez program dane b d mogły zostać przesłane w sieci.
Warstwa sesji (warstwa 5) ustanawia, podtrzymuje i zarz dza sesjami mi dzy aplikacjami.
Warstwa transportu (warstwa 4) dzieli dane na segmenty i ponownie je składa. Gwarantuje
stabilno ć poł czenia i oferuje niezawodn transmisj .
Warstwa sieci (warstwa 3) okre la najlepszy sposób przemieszczenia danych z jednego
miejsca w drugie. Na poziomie tej warstwy działa router. Warstwa ta wykorzystuje sche-
maty adresowania logicznego zarz dzane przez administratora. Warstwa sieci korzysta ze
sposobu adresowania protokołu IP (Intemet Protocol) wraz ze schematami AppleTalk,
DECnet, VINES oraz IPX.
Warstwa Å‚ cza danych (warstwa 2) zapewnia fizyczn transmisj danych w medium. Ob-
sługuje powiadamianie o bł dach, topologi sieci i kontrol przepływu. Wykorzystuje ad-
resy MAC (Media Access Control), które okre lane s równie mianem adresów fizycz-
nych lub sprz towych.
Warstwa fizyczna (warstwa l) dostarcza elektrycznych, mechanicznych, proceduralnych i
funkcjonalnych rodków słu cych do nawi zania i utrzymania fizycznego poł czenia
mi dzy systemami. Wykorzystuje takie fizyczne media, jak skr tka, kabel koncentryczny
oraz wiatłowodowy [4].
8.1.1. Warstwa Å‚ cza danych
Dost p do medium sieciowego nast puje w warstwie Å‚ cza danych modelu odniesienia
OSI. Warstwa 2, w której znajduje si adres MAC, s siaduje z warstw fizyczn . Dwa ad-
resy MAC nigdy nie s identyczne. Tak, wi c w rodowisku sieciowym karta sieciowa
(NIC) stanowi miejsce, w którym urz dzenie ł czy si z medium, przy czym ka da karta
sieciowa ma unikatowy adres MAC.
78
Zanim ka da karta sieciowa opu ci fabryk , producent sprz tu przypisuje jej adres MAC.
Adres ten zapisany jest w układzie elektronicznym znajduj cym si na karcie NIC. Z tego
powodu, je eli w danym komputerze dokonuje si wymiany karty sieciowej, adres fizycz-
ny równie ulega zmianie: na adres MAC nowej karty sieciowej.
Adresy MAC przedstawiane s w postaci liczb szesnastkowych. Wyst puj dwa formaty
zapisu tych adresów: 0000.Oc12.3456 oraz 00-00-Oc-12-34-56.
Gdy jedno z urz dze w sieci Ethernet chce przestać dane do innego urz dzenia, mo e
otworzyć do niego kanał komunikacyjny, wykorzystuj c jego adres MAC. Kiedy dane wy-
syłane s do sieci przez ródło, nios ze sob adres MAC miejsca przeznaczenia.W miar
jak dane podró uj wzdłu medium sieciowego, karta sieciowa obecna w ka dym z urz -
dze sprawdza, czy jej adres MAC pasuje do fizycznego adresu przeznaczenia, niesionego
przez pakiet danych. Je eli nie nast pi dopasowanie, karta NIC ignoruje ten pakiet, który
pod a przez sieć w kierunku nast pnego urz dzenia. Gdy jednak nast pi dopasowanie,
karta sieciowa wykonuje kopi pakietu danych, któr umieszcza w warstwie ł cza danych
komputera, w którym si znajduje. Oryginalny pakiet podró uje dalej w sieci, pozwalaj c
pozostałym kartom sieciowym na prób dopasowania [4].
8.1.2. Warstwa sieci
Jedn z ró nic mi dzy warstw drug , a warstw trzeci jest to, e warstwa druga u y-
wa ramek natomiast warstwa trzecia u ywa pakietów. Pakiet składa si z jednej lub wi cej
ramek. Transfer pewnych pakietów mo e wymagać wi cej ni jednej ramki. Warstwa sie-
ciowa jest odpowiedzialna za ustanowienie poł czenia pomi dzy stacjami. Zwykle pomi -
dzy dwiema stacjami istnieje wi cej ni jedna droga i warstwa trzecia musi okre lić, która
z nich jest najlepsza. Dlatego synonimem działania w warstwie trzeciej jest routowanie.
Czasami trzeba poł czyć sieci u ywaj ce ró nych standardów MAC. Sieć mo e przykła-
dowo posiadać szkielet FDDI, ale do podł czania grup roboczych u ywać technologii Et-
hernet. W tym przypadku warstwa sieciowa dokonuje konwersji pomi dzy ró nymi forma-
tami ramek tych sieci. Mo na tego dokonać, zmieniaj c ramki z jednej sieci w pakiet, a na-
st pnie wysłać go w ramkach o formacie drugiej sieci [3].
79
8.1.3. Przykład działania modelu OSI
Model OSI opisuje sposób, w jaki informacja wychodz ca z programu komputerowego
(np. arkusz kalkulacyjny) podró uje przez medium transmisyjne (np. kable) do innej apli-
kacji w innym komputerze. W miar jak informacja przeznaczona do wysłania opada w
gł b poszczególnych warstw danego systemu, przestaje coraz bardziej przypominać zro-
zumiał dla człowieka form . Ka da z warstw wykorzystuje swój własny protokół w celu
porozumienia si z odpowiadaj c sobie warstw docelowego systemu. Protokół ka dej z
warstw wymienia informacje, zwane PDU (Protocol Data Units), z warstwami docelowego
systemu. Dokładniej wyja nia to rysunek Rys. 8.1. Przedstawiony jest na nim przykład
komunikacji według zasad OSI. Host A chce wysłać informacj do Hosta B. Aplikacja Ho-
sta A komunikuje si z warstw aplikacji, ta z kolei komunikuje si z warstw prezentacji
tego hosta a, nast pnie komunikuje si z warstw sesji i tak dalej, a zostanie osi gni ta
warstwa fizyczna Hosta A. Warstwa fizyczna wysyła (i odbiera) informacj przez fizyczne
medium stosowane w sieci. Po tym jak informacja przejdzie przez medium i zostanie ode-
brana przez Host B, przemieszcza si przez warstwy tego Hosta w odwrotnej kolejno ci,
a ostatecznie osi gnie warstw aplikacji Hosta B.
Rys. 8.1 Powi zania pomi dzy warstwami sieci
Głównym celem ka dej warstwy hosta A jest skomunikowanie si z odpowiadaj c jej
warstw Hosta B.
Stosowany w modelu OSI schemat podziału na warstwy wyklucza bezpo redni ko-
munikacj mi dzy odpowiadaj cymi sobie warstwami ró nych hostów. Ka da warstwa
Hosta A musi, wi c polegać na usługach dostarczanych przez s siednie warstwy tego ho-
sta, aby nawi zać komunikacj z odpowiadaj c jej warstw Hosta B. Wynika st d, e
80
segmenty TCP staj si cz ci pakietów warstwy sieci (nazywanych tak e datagramami),
wymienianych mi dzy hostami IP. Z kolei pakiety IP musz stać si cz ci ramek ł cza
danych, wymienianych mi dzy bezpo rednio poł czonymi urz dzeniami. Ramki te w cza-
sie przesyłania danych przez warstw fizyczn za pomoc odpowiedniego sprz tu, musz
ostatecznie stać si bitami [4].
8.2. Podstawowe poj cia na temat routingu
Routing jest czynno ci realizowan przez urz dzenia sieciowe zwane routerami. Jest to
urz dzenie, które działa w warstwie trzeciej. Jego głównym zadaniem jest ł czenie kilu
sieci ze sob . Sieci ł czone przez router posiadaj ró ne adresy, wi c stacja z jednej sieci
nie mo e bezpo rednio skomunikować si ze stacj z innej sieci. Router jest tutaj urz dze-
niem, które przekazuje adresowane pakiety z jedne sieci do innej. Zagadnienie routingu
jest, wi c kierowaniem informacji w taki sposób, aby dotarła do wła ciwego miejsca prze-
znaczenia. Oczywi cie przykład, w którym router słu y tylko do ł czenia sieci jest naj-
prostsz implementacj tego urz dzenia [4].
Prawdziwe problemy dotycz ce, routingu pojawiaj si wtedy, gdy mamy do czynienia z
du , rozproszona sieci , w której wyst puje wi ksza ilo ć urz dze routuj cych. Poj cie
routingu w takim przypadku rozrasta si do trudnego problemu przesłania informacji z
punktu pocz tkowego do punktu docelowego w taki sposób, aby informacja ta dotarła jak
najszybciej i jak najmniejszym kosztem. Do omówienia tego problemy wchodzi w gr bar-
dzo du o poj ć, które omówimy w dalszej cz ci pracy [4].
8.2.1. Funkcje routera
Routery generalnie przekazuj pakiety z jednego Å‚ cza danych do drugiego. Aby prze-
kazać pakiet, router korzysta zdwóch podstawowych funkcji: funkcji ustalania cie ki oraz
funkcji przeł czania. Rys. 8.2 pokazuje, w jaki sposób routery wykorzystuj adresowanie
do pełnienia funkcji routingu i przeł czania.
81
Rys. 8.2 Router przekazuje pakiet do kolejnej sieci wzdłu cie ki i wykorzystuje cz ć adresu
okre laj c sieć do dokonania wyboru cie ki
Funkcja przeł czania pozwala routerowi pobrać pakiet z jednego interfejsu i przekazać go
do innego. Ustalenie cie ki, pozwala routerowi wybrać najodpowiedniejszy interfejs, do
którego nale y przekazać pakiet. Cz ć adresu okre laj ca w zeł odnosi si do specyficz-
nego portu routera, prowadz cego w obranym kierunku do s siedniego routera.
Gdy aplikacja hosta chce wysłać pakiet do miejsca przeznaczenia znajduj cego si w innej
sieci, jeden z interfejsów routera odbiera ramk ł cza danych. W celu okre lenia sieci do-
celowej podczas przetwarzania w warstwie sieci badany jest nagłówek, po czym nast puje
odwołanie do tablicy routingu, kojarz cej sieci z odpowiednimi interfejsami wyj ciowymi.
Oryginalna ramka rozkładana jest na poszczególne elementy, a nast pnie porzucana. Pakiet
zostaje ponownie enkapsulowany w ramk Å‚ cza danych wybranego interfejsu oraz usta-
wiony w kolejk , gdzie oczekuje na wykonanie kolejnego skoku na cie ce.
Proces ten zachodzi za ka dym razem, gdy pakiet przeł czany jest przez kolejny router. Z
chwil , gdy pakiet osi gnie router pracuj cy w sieci zawieraj cej docelowego hosta, zosta-
je ponownie enkapsulowany w ramk takiego typu, jaki stosowany jest przez Å‚ cze danych
sieci docelowej. Nast pnie pakiet dostarczany jest do docelowego hosta [4].
8.2.2. Zasada działania routera
Routery s obecnie u ywane w ró nych miejscach sieci i tworz podstaw wielu sieci
du ej wielko ci.
82
Rys. 8.3 Diagram przepływu danych przez router
Router wykonuje nast puj ce funkcje:
Odebrana ramka jest zachowywana, zdejmowany jest nagłówek warstwy 2. Pole Dane
ramki zawiera pakiet warstwy 3. To oznacza, e router ignoruje adresy MAC pakietu.
Identyfikowany jest typ protokołu. Niektóre ramki Ethemet zawieraj t informacj wna-
główku, ale w ogólnym wypadku typ protokołu mo e zostać odczytany z pola danych
ramki. Router okre la, czy protokół jest routowalny. Je eli nie to przywracana jest orygi-
nalna ramka warstwy 2 i jest ona przeł czana. Je eli protokół jest routowalny (IP, IPX,
AppleTalk lub DECnet), router sprawdza, czy nie została przekroczona maksymalna ilo ć
skoków (typowo jest to 15). Je eli tak, to pakiet jest anulowany, co zapobiega nieko cz -
cym si w drówkom pakietów o nieistniej cych adresach docelowych. Ilo ć skoków pa-
kietu jest inkrementowana.
Router sprawdza adres docelowy w tablicy routing i identyfikuje odpowiedni port docelo-
wy. Je eli w zeł jest bezpo rednio przył czony do routera, to przywracany jest oryginalny
nagłówek warstwy 2 i ramka jest do tego portu wysyłana.
83
Je eli w zeł docelowy nie jest bezpo rednio przył czony z którymkolwiek portów routera
(konieczne jest przesłanie pakietu do innego routera), to do pakietu jest dodawany odpo-
wiedni adres IP. Nast pnie dodawany jest nagłówek z adresami MAC pochodz cymi z Ta-
blicy Routingu, a ramka jest wysyłana do odpowiedniego portu.
W ogólno ci działanie routera polega na przeszukiwaniu w tablicy routingu adresu doce-
lowego. Routery wymieniaj si tablicami routingu pomi dzy sob . Router jest cz ci
wi kszego organizmu routuj cego i zna dokładnie ka d drog przechodz c przez
wszystkie inne routery.
Z historycznego punktu widzenia routery były urz dzeniami zdalnego dost pu ł cz cymi
ró ne sieci lokalne. Internet jest wiatowym labiryntem poł czonych ze sob routerów.
Routery mog tłumaczyć pomi dzy ró nymi protokołami. Wraz ze zwi kszaniem si licz-
by protokołów router zmienił swoj rol z urz dzenia brzegowego i przeniósł si do cen-
trum sieci, tworz c jej szkielet.
Takie rozwi zanie posiada wiele zalet [14] :
x Punkt dost pu do sieci WAN jest poło ony centralnie.
x Tłumaczenie protokołów przebiega w najkorzystniejszym punkcie, czyli w centrum
sieci.
x Dzielenie du ej i płaskiej sieci, opartej na przeł czaniu w warstwie 2., na mniejsze
podsieci warstwy 3 zmniejsza ruch rozgłoszeniowy i podnosi wydajno ć.
x Konfiguracja z wieloma podsieciami jest bardziej odporna na sztormy rozgłosze-
niowe.
x Ró ne sieci wirtualne musz komunikować si przez router.
x Du e routery szkieletowe czyni sieć bardziej stabiln , niezawodn i łatwiejsz w
zarz dzaniu.
84
9. PROTOKOA
Y ROUTINGU
Aby router mógł kierować ruchem w sieci musi posiadać przepis, według którego b -
dzie tego dokonywał. Mo na wyró nić dwa podstawowe rodzaje routingu styczny i dyna-
miczny. Routing statyczny administrowany jest r cznie: administrator sieci musi wprowa-
dzić niezb dne informacje do konfiguracji routera tak, aby działał w po dany sposób. Za
ka dym razem, kiedy zmiana topologii sieci powoduje konieczno ć uaktualnienia informa-
cji wykorzystywanych przez statyczny routing, administrator musi zrobić to r cznie. Sta-
tyczny routing zmniejsza koszty routingu, poniewa nie s wysyłane uaktualnienia routin-
gu (na przykład w przypadku protokołu RIP ma to miejsce, co 30 sekund).
Natomiast routing statyczny nie jest dobrym wyj ciem, kiedy konfiguracja sieci zmienia
si dosyć cz sto lub, kiedy istnieje du e prawdopodobie stwo tego, e poł czenia w sieci
mog ulegać awarii. Awarie poł cze powoduj wymuszenie zmiany konfiguracji routera
tak, aby informacja wysłana do konkretnego odbiorcy mogła dotrzeć do niego inn drog .
Inn odmian routingu jest routing dynamiczny, który działa inaczej ni wy ej opisany ro-
uting statyczny. Po wydaniu przez administratora sieci polecenia konfiguracyjnego akty-
wuj cego dynamiczny routing, za ka dym razem, kiedy w procesie routingu z sieci otrzy-
mywane s nowe informacje, baza danych routingowych uaktualniana jest automatycznie.
Jako cz ć procesu aktualizacji, routery wymieniaj mi dzy sob informacje o zmianach
dynamicznego routingu. Statyczny routing znajduje wiele u ytecznych zastosowa . Po-
zwala administratorowi wskazać, co powinno być ogłaszane na temat zastrze onych party-
cji. Administrator mo e ukryć cz ć sieci ze wzgl dów bezpiecze stwa. Dynamiczny ro-
uting stara si pozyskać wszelkie informacje na temat sieci. Co wi cej, gdy sieć dost pna
jest za po rednictwem wył cznie jednej cie ki, statyczna trasa prowadz ca do sieci mo e
być wystarczaj ca. Taki rodzaj partycji nazywany jest sieci szkieletow [14].
W dalszej cz ci pracy opisujemy głównie routing dynamiczny, poniewa jest on znacznie
cz ciej stosowany i pozwala w pewnym sensie zautomatyzować proces routingu.
Głównymi funkcjami, jakie realizuje protokół routingu dynamicznego s [4] :
x utrzymania tablicy routingu
x regularnego dzielenia si wiedz z innymi routerami - w postaci uaktualnie ro-
utingu.
x Protokół routingu definiuje zbiór reguł stosowanych przez router w czasie komuni-
kacji z s siednimi routerami. Protokół routingu opisuje na przykład:
85
x sposób wysyłania uaktualnie
x rodzaj informacji zawartych w takich uaktualnieniach
x terminy wysyłania tych informacji
x sposób lokalizowania odbiorców uaktualnie .
Zewn trzne protokoły routingu wykorzystywane s przy komunikacji mi dzy systemami
autonomicznymi. Wewn trzne protokoły routingu wykorzystywane s w ramach poje-
dynczego, autonomicznego systemu.
9.1. Protokoły trasowane a protokoły routingu
Ró ne protokoły trasowalne wymagaj ró nych protokołów routingu. Przedstawimy te-
raz ró nic mi dzy tymi protokołami:
Protokół trasowany to dowolny protokół sieciowy, który dostarcza w swoim adresie war-
stwy danych wystarczaj co wiele informacji, aby w oparciu o schemat adresowania po-
zwolić na przekazanie pakietu z jednego hosta do drugiego. Protokoły trasowane, definiuj
format i sposób wykorzystania poszczególnych pól w ramach pakietu. Pakiety s general-
nie przekazywane mi dzy kra cowymi systemami. Przykładowymi protokołami trasowal-
nymi s IP, IPX [4].
Protokół routingu to protokół obsługuj cy protokół trasowany poprzez dostarczanie me-
chanizmów, pozwalaj cych na dzielenie si informacjami, o routingu. Komunikaty proto-
kołów routingu przemieszczaj si mi dzy routerami. Protokół routingu pozwala routerom
komunikować si ze sob w celu uaktualniania i utrzymywania tablic. Przykłady proto-
kołów routingu, ze stosu TCP/IP to Routing Information Protocol (RIP), Interior Gateway
Routing Protocol (IGRP), Enhanced Interior Gateway Routing Protocol (Enhanced IGRP)
oraz Open Shortest Path First (OSPF).
9.2. Routing wieloprotokołowy
Routery mog przeprowadzać routing wielu protokółów, co oznacza, e s one w stanie
obsługiwać równocze nie kilka, niezale nych protokołów routingu, takich jak RIP oraz
86
IGRP. Ta mo liwo ć pozwala routerom na przekazywanie przez te same ł cza pakietów,
pochodz cych z ró nych protokołów trasowanych, takich jak TCP/IP oraz IPX [4].
9.3. Klasy protokołów routingu
Wi kszo ć protokołów routingu mo e zostać zaklasyfikowana do jednego z dwóch pod-
stawowych typów:
x Protokołów wektora odległo ci
x Protokoły stanu ł cza.
Protokół routingu wektora odległo ci wyznacza kierunek (wektor) i odległo ć od dowolne-
go ł cza w sieci. Podej cie reprezentowane przez protokół routingu stanu ł cza (nazywany
równie protokołem Dijkstry [SPF]) polega na odtworzeniu dokładnej topologii całej sieci
(lub przynajmniej tej cz ci, w której znajduje si router). Istnieje jeszcze trzeci rodzaj pro-
tokołu, protokół hybrydowy, który ł czy cechy protokołów stanu ł cza i wektora odległo-
ci.
Za ka dym razem, gdy topologia sieci ulega zmianie z powodu rozwoju, rekonfiguracji lub
awarii, baza danych o sieci musi równie zostać zmieniona. Stan wiedzy musi stanowić
dokładny, spójny obraz nowej topologii. Posiadanie tego dokładnego, spójnego obrazu na-
zywane jest zbie no ci .
Kiedy wszystkie routery w sieci pracuj na podstawie tych samych informacji, mówimy,
e sieć osi gn ła zbie no ć. Szybkie uzyskanie zbie no ci jest po dan cech sieci, po-
niewa skraca to czas, w którym routery maj nieaktualne informacje wykorzystywane
przez nie do podejmowania decyzji dotycz cych routingu, przez co decyzje te mog być
bł dne i niewydajne [14].
9.3.1. Routing wektora odległo ci
Protokoły routingu wektora odległo ci przekazuj okresowe kopie tablic routingu po-
mi dzy routerami. Ka dy router otrzymuje tablic routingu od swojego najbli szego s -
siada. Sytuacj tak przedstawia Rys. 9.1. Router B otrzymuje informacje od Routera A.
Router B doł cza do niej warto ć wektora odległo ci (tak , jak liczba skoków), zwi ksza
wektor odległo ci, a nast pnie przekazuje tablic routingu swojemu najbli szemu s sia-
87
dowi, Routerowi C. Ten sam proces, krok po kroku, wyst puje we wszystkich kierunkach,
mi dzy bezpo rednio s siaduj cymi routerami [4].
Rys. 9.1 Regularne uaktualnienia mi dzy routerami oznajmiaj zmiany topologii
W ten sposób protokół gromadzi informacje o odległo ciach w sieci, co pozwala mu
utrzymywać baz z informacjami o topologii sieci. Protokoły routingu wektora odległo ci
nie pozwalaj routerowi poznać dokładnej topologii sieci, s podatna na p tle routingu ale
opieraj si na prostszych obliczeniach ni protokoły routingu stanu ł cza. Protokół ten jest
tak e nazywany protokołem routingu Bellmana-Forda.
9.3.2. Routing stanu Å‚ cza
Drugim podstawowym protokołem u ywanym przy routingu jest protokół stanu ł cza.
Protokoły routingu stanu ł cza utrzymuj zło one bazy danych z informacjami o topologii,
ma on pełn wiedz na temat odległych routerów i poł cze istniej cych mi dzy nimi.
Routing stanu ł cza wykorzystuje ogłoszenia o stanie ł czy (LSA) , baz topologii, proto-
kół SPF, wynikowe drzewo SPF i wreszcie tablic routingu, opisuj c cie ki i porty do
ka dej z sieci. Taka koncepcja stanu ł cza została zastosowana w routingu OSPF [4]. Pro-
tokół stanu ł cza jest protokołem, w który ka dy router zgłasza do wszystkich w złów sie-
ci zło onej, informacj o kosztach dotarcia do wszystkich s siaduj cych ze sob routerów.
Protokoły stanu ł cza tworz przejrzysty obraz sieci i nie s przez to podatne na p tle ro-
utingu. Jednak jest to osi gane kosztem bardziej skomplikowanych oblicze i wi kszego
ruchu rozgłoszeniowego, w porównaniu z protokołem routingu wektora odległo ci.
LSA  (Link  State Adverisment )  pakiet rozgłoszeniowy u ywany przez protokół stanu ł cza, który zawie-
ra informacje na temat s siadów oraz kosztów cie ki. U ywane s przez routery odbiorcze, aby utrzymywać
aktualne tablice routingu. Okre lany jest równie jako LSP (Link  State Packet)
88
9.3.3. Przedstawienie odległo ci za pomoc metryki
Podczas projektowania sieci bierzemy pod uwag takie zało enia jak [4]:
x niezawodno ć sieci - musi dostarczać rodki do wykrywania bł dów oraz oferować
mo liwo ć korelacji tych bł dów.
x otwarto ć sieci - musi umo liwiać wielu ró nym urz dzeniom i programom kom-
puterowym bezproblemow współprac .
x łatwo ć w u yciu - musi funkcjonować w taki sposób aby u ytkownicy nie musieli
przejmować si jej struktur oraz implementacj .
x łatwo ć sposobu rozbudowy sieci - musi ona móc ewoluować i przystosować si do
nowych potrzeb i nowych technologii.
W tej cz ci naszej pracy omówimy w jaki sposób wy ej wymienione zało enia realizuj
routery. Przedstawimy równie , w jaki sposób mo na wykorzystać, routery do ł czenia
kilku sieci ze sob [3]. Warstwa sieci modelu OSI, któr opisali my we wcze niejszej cz -
ci naszej pracy stanowi interfejs do sieci i zapewnia korzystaj cej z jej usług warstwie
transportu najwydajniejszy sposób przesyłania danych mi dzy dwoma punktami. Warstwa
sieci wysyła pakiety z sieci ródłowej do sieci docelowej. Aby mogło nast pić przesyłanie
danych ze ródła do miejsca przeznaczenia, na poziomie warstwy sieci musi być przepro-
wadzone ustalanie cie ki. Za t funkcj zazwyczaj odpowiedzialny jest router [3].
Funkcja ustalaniu cie ki pozwala routerowi ocenić dost pne cie ki, prowadz ce do miej-
sca przeznaczenia i zastosować dla przesyłanego pakietu najlepsz metod routingu.
Przedstawia to na poni szy rysunek.
Rys. 9.2 Przykładowa sieć do oceny dost pnych cie ek
89
Routing oznacza proces wybierania najlepszej cie ki, po której nale y przesłać pakiety
oraz najlepszej metody przekazywania danych przez wiele sieci fizycznych. Stanowi to
podstaw całej komunikacji w Internecie. Wi kszo ć protokołów routingu korzysta po pro-
stu zawsze z najkrótszej i najlepszej trasy, jednak stosuje one ró ne sposoby jej wyzna-
czania.
W sieciach IP router przekazuje pakiety z sieci ródłowej do sieci docelowej w oparciu o
tablic routingu IP. Po ustaleniu, której cie ki nale y u yć, router mo e kontynuować
przeł czanie pakietu, przyjmuje pakiet w jednym interfejsie i przekazuje go do kolejnego,
stanowi cego nast pny skok na najlepszej cie ce do miejsca przeznaczenia. Ka dy router
obsługuj cy pakiet musi wiedzieć, co ma z nim zrobić.
Tablice routingu przechowuj informacje o potencjalnych miejscach przeznaczenia i o me-
todach dotarcia do nich. Na potrzeby routingu tablice routingu musz przechowywać jedy-
nie te cz ci adresów IP, które opisuj sieć. Pozwala to na utrzymywanie małych rozmia-
rów tablic, przy jednoczesnej du ej wydajno ci.
Wpisy w tablicy routingu zawieraj adres IP nast pnego skoku na trasie do miejsca prze-
znaczenia. Ka dy wpis okre la tylko jeden skok i wskazuje na bezpo rednio przył czony
router, to znaczy na router, do którego mo na si dostać w ramach pojedynczej sieci. Pro-
tokoły routingu wypełniaj tablice routingu ró nymi informacjami. Router wykorzystuje
tablic routingu miejsc przeznaczenia, nast pnych skoków na przykład wówczas, gdy od-
bierze napływaj cy pakiet. Router sprawdza wówczas adres docelowy w swojej tablicy ro-
utingu i stara si dobrać dla niego wła ciwy kolejny skok. Tablica routingu miejsc prze-
znaczenia nast pnych skoków mówi routerowi, e do danego miejsca przeznaczenia najła-
twiej dotrzeć wysyłaj c pakiet do okre lonego routera, stanowi cego kolejny skok na dro-
dze do celu [4].
W celu budowania tablic routery musz porozumiewać si ze sob poprzez wykorzy-
stywanie protokołów routingu i przekazywanie ró nych komunikatów. Jednym z takich
komunikatów jest komunikat uaktualnienia routingu. Uaktualnienia routingu składaj si
zazwyczaj z cz ci lub z całej tablicy routingu. Dzi ki analizie uaktualnie routingu na-
pływaj cych ze wszystkich routerów, router mo e zbudować sobie dokładny obraz topolo-
gii sieci. Gdy routery znaj topologi sieci, mog wyznaczać najlepsze trasy do miejsc
przeznaczenia.
90
Wa n rzecz jest, eby tablica routingu była stale uaktualniana, poniewa jej głównym
zadaniem jest dostarczanie routerowi jak najdokładniejszych informacji. Ka dy protokół
routingu rozumie co innego pod poj ciem najlepszej cie ki. Dla ka dej cie ki w sieci
protokół generuje liczb , nazywan metryk . Im mniejsza metryka, tym zazwyczaj lepsza
cie ka. Tablice routingu mog tak e zawierać informacje o zaletach danej cie ki. Route-
ry wyznaczaj c najlepsze trasy porównuj metryki. Metryki ró ni si wzale no ci od sto-
sowanego protokołu routingu.
Przy wyznaczaniu najlepszej cie ki mo na opierać si na ró nych metrykach. Niektóre
protokoły routingu, takie jak RIP (Routing Information Potocol), wykorzystuj tylko jedn
metryk , podczas gdy inne, na przykład IGRP, korzystaj z kombinacji kilku metryk. Ta-
bela pokazuje najcz ciej wykorzystywane przez routery metryki.
Tabela 9.1 [4]
Typ metryki Opis
Liczba sko- Liczba routerów, przez które musie przej ć pakiet, zanim osi gnie miej-
ków sce przeznaczenia. Im mniejsza liczba skoków, tym lepsza cie ka.
Liczb skoków do miejsca przeznaczenia okre la si za pomoc długo-
ci cie ki
Pasmo Pojemno ć ł cza
Opó nienie Czas potrzebny na przemieszczenie pakietu ze ródła do miejsca prze-
znaczenia
Obci enie Stopie wykorzystania danego zasobu sieciowego, takiego jak router
lub Å‚ cze
Niezawod- Cz stotliwo ć wyst powania bł dów w poszczególnych ł czach sieci
no ć
Takty Opó nienie w warstwie ł cza danych, wyra one w taktach zegara IBM
PC (około 55 milisekund)
Koszt Arbitralna warto ć, okre lana przez administratora sieci, oparta na sze-
roko ci pasma, poniesionych nakładach finansowych lub innych czyn-
nikach.
Po zapoznaniu si z adresem protokołu miejsca przeznaczenia pakietu, router okre la, czy
potrafi ustalić, jak nale y przekazać pakiet do miejsca kolejnego skoku. Je eli router nie
wie, jak przekazać pakiet, zazwyczaj go porzuca. Je li natomiast router wie, jak przekazać
91
pakiet, zamienia fizyczny adres jego miejsca przeznaczenia na adres miejsca kolejnego
skoku i przesyła pakiet.
Miejsce nast pnego skoku mo e, ale nie musi być hostem docelowym. Je eli nie jest,
wówczas miejscem nast pnego skoku jest zazwyczaj kolejny router, który podejmuje takie
same decyzje dotycz ce przeł czania, jak jego poprzednik. Proces ten przedstawiony jest
na rysunku Rys. 9.3.
Rys. 9.3 Poruszaj cy si w sieci pakiet ma nadawane ró ne adresy fizyczne, ale jego adres pro-
tokołu pozostaje bez zmian
9.3.4. Podstawowe czynno ci zwi zane z wyszukiwaniem tras
Wyszukiwanie tras jest procedur , któr stosuj routery, gdy trasa (sieć) lub grupa tras
stała si niedost pna. Zdarzenie to ma miejsce, na skutek fizycznego przerwania poł cze-
nia lub strat bardzo du ej cz ci pakietów, przy przesyłaniu w ramach tego poł czenia.
Routery w przypadku, gdy zajdzie takie zdarzenie, wymazuj utracone trasy i nasłuchuj ,
aby stwierdzić czy dost pne s inne trasy. Przewa nie routery w swoich tabelach tras za-
pami tuj tylko najlepsz tras do sieci ignoruj c pozostałe [3].
92
Na wyszukiwanie tras składaj si cztery podstawowe funkcje: update, invalid, holddown i
flush. Krótki opis tych funkcji przedstawiony jest w tabeli Tabela 9.2.
Tabela 9.2 [3].
Funkcja Opis
Update Czas pomi dzy wysyłanymi przez router aktualizacjami tabeli tras
(Aktualizuj)
Invalid Termin ten opisuje zarówno stan, w jakim mo e znajdować si konkret-
(Niewa na) na trasa, jak i zegar wykorzystywany do kontrolowania jej stanu. Ter-
min invalid jest u ywany dla tras, którymi przez czas okre lony dla ze-
gara stanu invalid nie nadeszły adne dane. Na przykład, je li zegar sta-
nu invalid (ang. invalid timer) jest ustawiony na 60 sekund, a router,
który podał t tras , nie zgłosi jej w ci gu 61 sekund, czas zegara stanu
invalid upływa, a trasa jest uznawana za niewa n
Hold down Termin ten opisuje zarówno stan, w jakim mo e znajdować si konkret-
(Zatrzymana) na trasa, jak i zegar wykorzystywany do kontrolowania jej stanu. Ter-
min hold down jest u ywany dla tras, które zostały zaznaczone jako
niewa ne, ale których nie udało si zast pić innymi trasami o wy szej
metryce. Zegar stanu hold down okre la, jak długo trasa pozostaje w
tym stanie (chyba, e zegar stanu flush zadziała, zanim upłynie czas
ustawiony na zegarze stanu hold down)
Flush Termin ten oznacza zegar oraz czynno ć usuwania trasy z tabeli tras.
(Wyma ) Zegar flush jest uruchamiany od nowa za ka dym razem, gdy router,
który zgłosił t tras przesyła jej uaktualnienie. Wa ne jest, aby pami -
tać, e zegary stanu invalid i flush s uruchamiane w tym samym mo-
mencie i czas biegnie równolegle. Gdy upłynie czas ustawiony dla danej
trasy na zegarze stanu flush, trasa ta jest usuwana z tabeli tras. Dla RIP
czas ustawiony na zegarze stanu flush upływa przed czasem ustawio-
nym na zegarze hold down, tak, e zegar hold down nigdy nie przebiega
swojego pełnego cyklu
Sytuacje, kiedy nast piło przerwanie poł czenia i router musi wyszukać now tras do
osi gni cia po danej sieci docelowej przedstawia Rys. 9.2.
93
W czasie, gdy router A ma tras 168.71.8.0 w stanie hold down, nadal przekazuje wszyst-
kie otrzymane pakiety przenoszone dla podsieci 168.71.8.0 do routera C. Jest to typowe
zachowanie dla routera wykorzystuj cego protokół RIP oraz wielu innych protokołów ro-
utingu IP. Jednym z powodów, dla których protokoły routingu zachowuj si w taki spo-
sób jest nast puj ce zało enie: chwilowa utrata pakietów na skutek wykorzystywania tras
do sieci, które mog być niesprawne, jest lepsza ni natychmiastowa akceptacja mniej ko-
rzystnej trasy do sieci ko cowej.
Jak przedstawia Rys. 9.2 mniej korzystn tras dla routera A byłoby osi gni cie 168.71.8.0
poprzez router B. Gdyby trasa 168.71.8.0 na routerze A przeszła w stan hold down na sku-
tek przeci enia poł czenia mi dzy routerami A i C, co spowodowało utrat pakietów z
aktualizacjami tabeli tras. Zostałyby równie utracone pakiety z sesji pomi dzy hostami w
podsieciach 168.71.5.0 i 168.71.8.0 przechodz c przez to poł czenie. Pozwalaj c na utrat
pakietów zamiast przesyłania ich mniej korzystn tras routery A i C daj hostom szans
na zareagowanie na utrat pakietów przez wysyłanie mniejszej liczby pakietów, a tak e
przez wysyłanie pakietów o mniejszym rozmiarze. Wymaga to, aby u ywane aplikacje lub
wykorzystywane przez nie protokoły rejestrowały utrat pakietów i reagowały na ni w
sposób przyjazny dla sieci.
Gdyby router A natychmiast zaakceptował mniej korzystn tras do 168.71.8.0, gdy tylko
upłyn łby czas ustawiony na zegarze stanu invalid dla 168.71.8.0 i przekazał tam cały ruch
dla 168.71.8.0, zatłoczenie bardziej korzystnej trasy pomi dzy routerami A i C przestałoby
być problemem. Aktualizacja tabel tras, które były tracone z powodu zatłoczenia, zacz ło-
by przychodzić ponownie i ruter A natychmiast przeszedłby z powrotem do wykorzystania
swojego poł czenia z routerem C dla osi gni cia 168.71.8.0. W tym momencie problem
zacz łby pojawiać si na nowo. To zjawisko jest okre lane jako trzepotanie trasy i wyst -
puje, gdy trasa wci przeł cza si mi dzy dwoma ró nymi routerami nast pnego kroku,
czyli na naszym przykładzie mi dzy routerami B i C.
9.3.5. Wyszukiwanie tras
Wyszukiwanie tras opisane wcze niej obejmuje cztery podstawowe czynno ci: update,
invalid, hold down i flush.
Czynno ci te wykorzystywane s , za ka dym razem, gdy router dokonuje zmiany w swojej
tabeli tras, równie w moment uruchomienia. Poni ej opisujemy scenariusz pokazuj cy
94
proces wyszukiwania tras przez wymuszenie, by router C przestał przesyłać aktualizacje
tras routerowi A, jak równie tematyk tras równoległych [3].
9.3.5.1. Wyszukiwanie trasy krok po kroku
Poni ej przedstawimy przykład zastosowania protokoły RIP do wyszukiwania nowej
trasy do sieci 168.71.8.0 przedstawionej na rysunku Rys. 9.4.
Rys. 9.4 Zastosowania protokoły RIP do wyszukiwania nowej trasy
Poniewa RIP wysyła aktualizacje, co 30 sekund, czas do nadej cia nast pnej aktualizacji
od routera B, dla routera A, mógłby wynosić od 0,1 sekundy do 29,99 (zaokr glaj c do
najbli szej setnej sekundy).
Rys. 9.5 porz dkuje procesy zawarte w wyszukiwaniu trasy pokazuj c kolejne kroki na osi
czasu router C zaprzestaje zgłaszania 168.71.8.0 w chwili 0 sekund
router A oznacza 168.71.8.0 jako niewa n i przechodzi w stan KROGGRZQ w chwili 180 se-
kund router A wychodzi ze stanu KROGGRZQ, gdy upływa czas zegara stanu IOXVK i akceptu-
je now tras poprzez router B w chwili 240 sekund
95
Rys. 9.5 O czasu dla procesu wyszukiwania tras
.
9.3.5.2. cie ki równoległe
Gdy router ma dwie lub wi cej tras do tej samej sieci o tej samej metryce, trasy te
mog być uwa ane za maj ce równy koszt. Terminem cie ki równoległej, okre lamy po-
wszechny sposób wyst powania w tabeli, tras o jednakowych kosztach. Je li router ma
dwie lub wi cej cie ek (tras) o jednakowych kosztach prowadz cych do pewnej sieci,
mo e u ywać ich równolegle. Je li utraci on jedn lub wi cej z tych cie ek, mo e nadal
wysyłać dane, o ile którakolwiek z nich jest dost pna. Router A na Rys. 9.6 ma dwie
cie ki o równych kosztach do 168.71.7.0. Je li utraci tras prowadz c przez ł cze szere-
gowe S0, mo e nadal wykorzystywać tras przez ł cze szeregowe S1. W tej sytuacji, wy-
szukiwanie tras polega po prostu na usuni ciu z tabeli tras, odniesie do trasy, która prze-
stała istnieć [3].
Rys. 9.6. cie ki równoległe umo liwiaj routerowi korzystanie z którejkolwiek z dost pnych
cie ek, nawet gdy niektóre z poł cze zostały zerwane
96
Poza zapewnieniem nadmiarowo ci w przypadku przerwania obwodu, dost pno ć cie ek
równoległych umo liwia, routerowi równomierne obci anie pakietami dost pnych cie-
ek. Mo e to prowadzić do bardziej efektywnego wykorzystania dost pnego pasma.
Dwa sposoby, którym router mo e wyrównywać obci enia cie ek równoległych, s na-
st puj ce [3]:
x Cykliczne wysyłanie pakietów - oznacza, e router wysyła po jednym pakiecie
przez ka de z dost pnych poł cze równoległych.
x Cykliczne wykorzystanie sesji  oznacza, e ka dy pakiet do hosta docelowego
w druje przez to samo poł czenie.
adna z tych metod nie jest lepsza od drugiej, ka da ma swoje zalety i wady. Uwa a si , e
wyrównywanie obci e przez cykliczne wysyłanie pakietów jest korzystniejsze dla poł -
cze równoległych wolniejszych ni 64Kb/s. Jednak e metoda ta mo e dostarczać pakiety
nie po kolei, je li czas propagacji (czas potrzebny na przesłanie pakietu na drugi koniec
poł czenia) nie jest jednakowy dla obydwu cie ek. Jest to szczególnie niekorzystne dla
przekazów multimedialnych.
Na Rys. 9.7 komputer ma dost pne dwie cie ki równoległe do podsieci 168.71.7.0 dla
przesyłania pakietów do 168.71.7.1 (interfejs szeregowy routera B). Decyzje o wyborze
trasy s podejmowane najcz ciej na podstawie tylko cz ci sieciowej adresu miejsca
przeznaczenia.
Rys. 9.7 PC ma dwie cie ki, aby osi gn ć podsieć 168.71.7.0
97
Router A mo e wyrównywać obci enia przez cykliczne wysyłanie pakietów, przekazuj c
pakiet ping ze stacji o adresie IP 178.68.207.222 pod adres IP 168.71.7.1. W tym przypad-
ku jeden pakiet przechodzi bezpo rednio przez router C, a drugi po rednio przez router B.
Wa ne jest nast puj ce stwierdzenie, e z perspektywy jednego routera obie cie ki maj
ten sam koszt, nie oznacza, e zawieraj w sobie tyle samo routerów nawet, je li metryka
routingu (jednostka miary) wykorzystuje skoki routera.
Router A nie wie, e 168.71.7.1 jest przypisany do interfejsu szeregowego routera C. Wie
tylko, e zarówno router B, jak i router C s doł czone do podsieci 168.71.7.0. Router A
nasłuchuje zgłosze tras z routerów B i C, informuj cych, e ka dy z nich ma bezpo red-
nie poł czenie z sieci o IP 168.71.7.0. Router A dodał do ka dej z tras jeden skok, gdy z
jego perspektywy adres IP 168.71.7.0 jest dost pny przez dwa ró ne routery.
9.3.6. Rola podziału sieci
Podział sieci DQJ VSOLW KRUL]RQ jest funkcj , która zapobiega powstawaniu p tli ro-
utingu w sieci. Podział sieci zapobiega zgłaszaniu z tabeli tych tras, które zostały zgłoszo-
ne przez konkretny interfejs do tego samego interfejsu. Scenariusz ten wyja nia, w jaki
sposób wył czenie podziału sieci mo e prowadzić do powstawania p tli routingu [3].
Na Rys. 9.8 router A nie zgłasza dost pu do sieci o IP 168.71.8.0 routerowi C przez inter-
fejs S1, poniewa dowiedział si o tej podsieci od routera C przez ten wła nie interfejs.
Jednak e router A wysyła i odbiera aktualizacje dla 168.71.8.0 przez interfejs S0 poniewa
router B nie jest routerem, którego router A u ywa do osi gni cia 168.7l.8.0. Trasa routera
A do 168.71.8.0 nie jest zgłaszana poprzez t cie k .
Rys. 9.8 Podstawowa sieci
98
Podział sieci stosuje si równie do przył czonych tras. Trasa przył czona jest tras , do
której router jest bezpo rednio, fizycznie podł czony. Je li chodzi o router A. 168.71.6.0
jest zgłoszona przez interfejs S0. Router A nie zgłasza 168.71.6.0 przez S0, je li podział
sieci jest wł czony dla tego interfejsu. Trasa do 168.71.8.0 preferowana przez router A
prowadzi przez interfejs S1. Gdy router A ma wysłać aktualizacj do routera C, tworzy ko-
pi zawieraj c wszystkie trasy z tabeli tras, z wyj tkiem tras zgłoszonych przez interfejs
S1 [3]. W tym przypadku aktualizacja nie zawiera 168.71.9.0, 168.71.8.0 ani 168.71.7.0,
zawiera natomiast 168.71.5.0 i 168.71.6.0.
9.3.7. Poison reverse i aktualizacje wymuszone
Sytuacja okre lana jako SRLVRQ UHYHUVH ma miejsce wtedy, gdy router informuje inne
routery, e trasy osi galne poprzednio poprzez konkretny interfejs nie s ju osi galne,
gdy interfejs ten został wył czony.
Routery zwykle reaguj na komunikat o wyst pieniu poison reverse natychmiast umiesz-
czaj c Ä]DWUXWH WUDV\´ w stanie KROG GRZQ, zamiast oczekiwania na upÅ‚yw czasu zegara
stanu LQYDOLG. Oszcz dza to czasu wyszukiwania, a do 180 sekund (domy lna warto ć sta-
nu LQYDOLG), w zale no ci od tego jak szybko po normalnej aktualizacji nadejdzie aktualiza-
cja Ä]DWUXFLD´ Na Rys. 9.9. wyÅ‚ czony jest interfejs S1 routera A. Router ten nie mo e ju
osi gać 168.71.9.0 i 168.71.8.0 poprzez S1. Ä=DWUXZDM F´ te trasy przez interfejs S0, ro-
uter A informuje wszystkie routery w dół od interfejsu S0, e nie mo e ju osi gać tych
dwóch podsieci. Tym wÅ‚a nie jest zgÅ‚oszenie Ä]DWUXFLD DQJ SRLVRQ DGYHUWLVHPHQW .
Po otrzymaniu takiego zgłoszenia router B usuwa odniesienia do tych dwóch podsieci i
przestawia je w hold down. Zaoszcz dza mu to czekania na upływ czasu zegara stanu inva-
lid.
99
Rys. 9.9 Interfejs serial1 routera A został zamkni ty
9.4. Protokoły routingu IP
Routing jest procesem polegaj cym na ustaleniu, dok d nale y przestać pakiety danych
przeznaczone dla adresów docelowych znajduj cych si poza lokaln sieci . Aby mo na
było wysyłać i odbierać takie pakiety danych, routery przechowuj informacje routingowe.
Informacje te przybieraj postać wpisów w tablicy routingu, przy czym jednej znanej trasie
odpowiada jeden wpis. Protokoły routingu pozwalaj routerom na dynamiczne tworzenie
tablic routingu i dostosowywanie si do zmian zachodz cych w sieci [4].
Protokoły routingu ró ni si mi dzy sob kilkoma kluczowymi cechami:
funkcjonowanie danego protokołu routingu zale y od tego, jakie cele decydowały o jego
powstaniu jest wiele rodzajów protokołów routingu i ka dy z nich ma inny wpływ na za-
soby routerów i sieci protokoły routingu posługuj si przy wyznaczaniu najlepszych tras
ró nymi metrykami.
Protokoły routingu mo na z grubsza podzielić na dwie klasy [4]:
x protokoły wewn trzne
x protokoły zewn trzne.
Protokoły wewn trzne wykorzystywane s do trasowania wspólnie zarz dzanych sieci.
Zanim rozpocznie si proces routingu, wszystkie wewn trzne protokoły IP musz zostać
poinformowane o stowarzyszonych sieciach. W procesie routingu prowadzony jest nasłuch
transmisji rozgłoszeniowych, pochodz cych od innych routerów w tych sieciach i rozgła-
szane s do nich własne informacje routingowe. W naszej pracy wzorujemy si głównie
na routerach firmy cisco, w routerach tych do protokołów wewn trznych nale RIP oraz
IGRP. Protokoły zewn trzne wykorzystywane s do wymieniania informacji routingowych
100
mi dzy sieciami, które nie s wspólnie zarz dzane. Do zewn trznych protokołów routingu
zaliczamy EGP oraz BGP.
Przed rozpocz ciem procesu routingu zewn trznego wymagane jest podanie nast puj -
cych informacji:
lista s siednich routerów, z którymi b d wymieniane informacje routingowe.
lista sieci, uznawanych za bezpo rednio osi galne.
9.4.1. Optymalna trasa
Poj cie optymalnej trasy zwi zane jest z mo liwo ci wybrania przez protokół routin-
gu najlepszej trasy. To, która trasa uznana jest za najlepsz , zale y od metryki i od metody
u ytej do jej obliczenia [4]. Na przykład jaki protokół routingu mo e brać pod uwag za-
równo liczb skoków, jak i opó nienie, jednak w przeprowadzanych przez niego oblicze-
niach opó nienie mo e mieć wi ksze znaczenie.
9.4.2. Prostota i wydajno ć
Protokoły routingu s równie zaprojektowane tak, aby były jak najprostsze i jak naj-
bardziej wydajne. Wydajno ć jest szczególnie wa na wówczas, gdy oprogramowanie im-
plementuj ce dany protokół musi pracować na komputerze o ograniczonych zasobach fi-
zycznych [4].
9.4.3. Odporno ć
Protokoły routingu musz być odporne. Innymi słowy, musz zachowywać si po-
prawnie w niecodziennych i nieprzewidywalnych okoliczno ciach, takich jak awarie sprz -
tu, wysokie obci enie oraz niepoprawne implementacje. Poniewa routery rozmieszczane
s na styku sieci, ich awarie mog być ródłem powa nych problemów [4].
101
9.4.4. Nagła zbie no ć
Zbie no ć to szybko ć i umiej tno ć dostosowania si grupy urz dze pracuj cych w
sieci zło onej i korzystaj cych z okre lonego protokołu sieciowego, do zmiany topologii
sieci. Protokoły routingu musz zapewniać szybkie osi ganie zbie no ci. Kiedy jakie wy-
darzenie w sieci, przykładowo zmiana topologii, powoduje odł czenie lub dodanie routera,
wtedy routery rozsyłaj komunikaty o uaktualnieniach routingu. Komunikaty te rozsyłane
s do wszystkich sieci, co powoduje ponowne wyliczenie optymalnych tras i przyj cie ich
przez routery. Protokoły routingu, które cechuje powolne osi ganie zbie no ci, mog
przyczyniać si do powstawania p tli routingu oraz nieaktualnych informacji o sieci. P tla
routingu przedstawiona jest na Rys. 9.10. W tym przykładzie o czasie T1 do routera 1 na-
pływa pakiet. Router 1 otrzymał ju wcze niej uaktualnienie routingu, wi c wie, e najlep-
sza trasa do miejsca przeznaczenia prowadzi przez router 2. Dlatego te router 1 przekazu-
je pakiet routerowi 2. Router 2 nie otrzymał jeszcze uaktualnienia, w zwi zku z czym wie-
rzy, e najlepszym miejscem kolejnego skoku jest router 1. Z tego wzgl du router 2 prze-
kazuje pakiet z powrotem do routera 1. Pakiet b dzie wci odbijany przez oba routery do
czasu, a router 2 otrzyma uaktualnienie routingu lub gdy pakiet zostanie przeł czony
maksymaln dopuszczaln liczb razy [4].
Warto ci maksymalne s ró ne dla ró nych protokołów routingu; administrator sieci mo e
zazwyczaj je zmniejszyć. Na przykład maksimum dla IGRP wynosi 255, warto ci do-
my ln jest 100, natomiast zazwyczaj ustawia si 50 lub mniej.
Rys. 9.10. P tle routingu wyst puj do czasu nadej cia uaktualnienia routingu lub do chwili. gdy
pakiet zostanie przeł czony maksymalna dozwolon liczb razy
102
9.4.5. Elastyczno ć
Protokoły routingu powinny te być elastyczne. Mówi c inaczej, powinny szybko do-
stosowywać si do ró nych warunków panuj cych w sieci. Załó my, na przykład e w da-
nym segmencie sieci wyst piła awaria. Wiele protokołów sieciowych szybko okre li naj-
lepsze cie ki zast pcze dla wszystkich tras, które normalnie przebiegaj przez uszkodzo-
ny segment. Protokoły routingu mog być zaprogramowane tak, eby dostosowywały si
do zmian dotycz cych na przykład pasma sieci, rozmiarów kolejki routerów, opó nie
oraz innych zmiennych [4].
9.4.6. Routing statyczny
Statyczne protokoły routingu z trudem mo na w ogóle nazwać protokołami. Zanim
rozpocznie si routing administrator sieci ustanawia statyczne przyporz dkowania w tabli-
cy routingu. Przyporz dkowania te nie zmieniaj si do chwili ich ponownego r cznego
ustawienia. Protokoły wykorzystuj ce trasy statyczne s proste do zaprojektowania i do-
brze sprawdzaj si , w rodowiskach prostych sieci, w których ruch zachowuje si w spo-
sób przewidywalny. Poniewa systemy stosuj ce statyczny routing nie mog reagować na
zmiany w sieci, generalnie uwa a si je za nieodpowiednie dla dzisiejszych du ych, stale
zmieniaj cych si sieci. Tego rodzaju sieci wymagaj dynamicznych protokołów routingu
[4].
9.4.7. Routing dynamiczny
Dynamiczne protokoły routingu przystosowuj si do zmieniaj cych si warunków w
sieci. Osi gaj to dzi ki analizowaniu napływaj cych komunikatów z uaktualnieniami ro-
utingu. Je eli komunikat wskazuje na to, e w sieci nast piła zmiana, oprogramowanie tra-
suj ce wylicza nowe trasy i rozsyła naj wie sze komunikaty z uaktualnieniem routingu.
Komunikaty te penetruj sieć, ponaglaj c routery do wprowadzenia stosownych zmian w
ich tablicach routingu. W zale no ci od potrzeb, dynamiczne protokoły routingu mog być
wspomagane trasami statycznymi. Mo na na przykład wyznaczyć bram ostatniego ratun-
ku (to znaczy router, do którego przesyłane s wszystkie niedaj ce si trasować pakiety).
Taki router pełni rol centralnej przechowalni dla wszystkich nietrasowalnych pakietów,
co gwarantuje, e wszystkie komunikaty zostan , choć w pewnym stopniu obsłu one [4].
103
9.4.8. Metody routingu
Wi kszo ć wcze niej omówionych protokołów routingu wykorzystuje jedno z trzech
klas routingu:
x Routing wektora odległo ci wyznacza kierunek (wektor) i odległo ć od ka dego ł -
cza w sieci. Przykładami protokołów routingu wektora odległo ci s IGRP oraz.
RIP.
x Routing bazuj cy na stanie ł cza (nazywane tak e SPF) odtwarza dokładn topolo-
gi całej sieci (lub chocia tej cz ci, w której znajduje si router). Przykładami
protokołów routing stanu ł cza s OSPF, IS-IS oraz NLSP.
x Klasa hybrydowa ł czy cechy protokołów stanu ł cza i wektora odległo ci. Przy-
kładem hybrydowego protokołu routingu jest Enhanced IGRP.
9.4.9. Konfiguracja routingu IP
Ka dy protokół routingu musi być konfigurowany oddzielnie. Dla ka dego protokołu
routingu nale y wykonać dwa podstawowe kroki:
x utworzyć proces routingu za pomoc jednego z polece routera
x skonfigurować specyficzne cechy protokołu.
Zanim rozpocznie si routing, protokołom wewn trznym takim jak IGRP oraz RIP, musi
zostać przekazana lista sieci. W procesie routingu prowadzony jest nasłuch uaktualnie
pochodz cych z innych routerów z tych sieci, oraz rozgłaszane s do nich własne informa-
cje dotycz ce routingu. IGRP wymaga dodatkowo podania numeru AS .
Dla ka dego protokołu routingu IP nale y utworzyć proces routingu, skojarzyć z nim
sieci oraz dostosować go do potrzeb konkretnej sieci. Wybór protokołu routingu jest trud-
nym zadaniem. Podczas wybierania protokołu routingu nale y brać pod uwag :
x rozmiar i zło ono ć sieci
x poziom nat enia ruchu w sieci
x bezpiecze stwo
x niezawodno ć
AS  system autonomiczny
104
x charakterystyk opó nie w sieci
x polityk organizacyjn
x stosunek do zmian organizacyjnych.
9.4.10. Opis protokołu routingu IGRP
W celu dokładniejszego przybli enia zagadnie zwi zanych z konkretnym protokołem
routingu IP opiszemy przykładowo protokół IGRP. W chwili obecnej jest to najbardziej
popularny protokół dynamicznego routingu IP.
IGRP zaprojektowanym został jako nast pca RIP. Jest on wewn trznym protokołem ro-
utingu wektora odległo ci. Protokół routingu wektora odległo ci wymaga od ka dego ro-
utera regularnego przesyłania do wszystkich s siaduj cych routerów komunikatów o uak-
tualnieniach routingu, zawieraj cych cał tablic routingu lub jej cz ć. W miar jak in-
formacje routingowe rozchodz si po sieci, routery s w stanie wyliczać odległo ci do
wszystkich w złów w sieci.
IGRP wykorzystuje kombinacj kilku metryk. W podejmowaniu decyzji routingowych od-
grywaj rol takie parametry jak: opó nienie w sieci, pasmo, niezawodno ć oraz obci e-
nie. Administratorzy sieci mog zmieniać ustawienia dla wszystkich tych metryk. IGRP
korzysta z ustawie wprowadzonych przez administratora b d u ywa ustawie domy l-
nych, automatycznie wyliczaj c najlepsze trasy.
Metryki protokołu IGRP mog przyjmować szerokie zakresy warto ci. Na przykład nieza-
wodno ć i obci enie mog być wyra one dowoln liczb mi dzy 1 a 255, pasmo mo e
mieć warto ć odpowiadaj c pr dko ciom od 1200 b/s do 10 Gb/s, natomiast opó nienie
mo e przyjmować dowoln warto ć z zakresu od 1 do 224. Szerokie zakresy metryk po-
zwalaj na stosowanie ustawie metryk adekwatnych do sieci o zró nicowanej charaktery-
styce wydajno ci. W efekcie administratorzy mog w intuicyjny sposób wpływać na wybór
tras. Do tego dochodzi okre lanie znaczenia ka dej z czterech metryk, to znaczy informo-
wanie routera, jak wa n rol odgrywa dana metryka. Domy lne ustawienia znaczenia po-
szczególnych metryk protokołu IGRP za najwa niejsze uznane jest pasmo, co sprawia, e
IGRP jest lepszy od RIP. Dla porównania RIP nie warto ciuje metryk, poniewa u ywa
tylko jednej [4].
105
9.4.10.1. Porównanie wewn trznych i zewn trznych tras IGRP
Protokół IGRP opracowała firma Cisco. Głównym ich celem przy tworzeniu IGRP
było opracowanie silnego protokołu na potrzeby routingu w ramach systemu autonomicz-
nego (AS). System autonomiczny, pokazany na rysunku Rys. 9.11. jest zbiorem wspólnie
administrowanych sieci, w których stosuje si spójn strategi routingu.
Rys. 9.11 Systemy autonomiczne dzielone s według obszarów
IGRP wykorzystuj kombinacj konfigurowanych przez u ytkownika metryk, a w ród
nich opó nienie w sieci, pasmo, niezawodno ć oraz obci enie. IGRP ogłasza trzy rodzaje
tras: wewn trzne, systemowe i zewn trzne, co przedstawia Rys. 9.11. Trasy wewn trzne to
trasy mi dzy podsieciami w sieci przył czonej do interfejsu routera. Je eli sieć podł czona
do routera nie stosuje podziału na podsieci, wówczas IGRP nie ogłasza tras wewn trznych.
Dodatkowo, informacja o podsieciach nie jest uwzgl dniana w uaktualnieniach IGRP, co
stanowi problem dla nieci głych podsieci IP.
Trasy systemowe to trasy do sieci znajduj cych si w ramach systemu autonomicznego.
Router wyznacza trasy systemowe na podstawie bezpo rednio podł czonych interfejsów
sieciowych oraz informacji dostarczanych przez inne routery wykorzystuj ce IGRP. Trasy
systemowe nie zawieraj informacji o podziale na podsieci. Trasy zewn trzne to trasy
prowadz ce do sieci znajduj cych si poza systemem autonomicznym, brane pod uwag
przy wyznaczaniu bramy ostatniego ratunku. Router wybiera bram ostatniego ratunku z
dostarczanej przez IGRP listy tras zewn trznych. Router korzysta z bramy ostatniego ra-
tunku w sytuacjach, w których nie potrafi wyznaczyć dla pakietów lepszej trasy, a docelo-
we urz dzenie nie jest podł czone do sieci. Je eli system autonomiczny dysponuje wi cej
106
ni jednym poł czeniem z sieci zewn trzn , poszczególne routery mog wyznaczać na
bramy ostatniego ratunku ró ne routery wyj ciowe.
9.4.10.2. Zasada podzielonych sieci
O podzielonych sieciach mówimy wówczas, gdy router próbuje odesłać informacj o
trasie z powrotem w miejsce, z którego nadeszła. Rozwa my na przykład sytuacj przed-
stawion na Rys. 9.12 router 1 ogłasza na pocz tku, e ma wyznaczon tras do sieci A. W
efekcie nie ma potrzeby, eby router 2 uwzgl dniał informacj o tej trasie w uaktu-
alnieniach wysyłanych do, routera 1, poniewa router 1 i tak znajduje si bli ej sieci A.
Zasada podzielonych sieci mówi, e router, 2 powinien wykre lić t tras ze wszystkich
uaktualnie wysyłanych do routera 1.
Zasada podzielonych sieci pomaga zapobiegać powstawaniu p tli routingu. Rozwa my na
przykład sytuacj , w której uszkodzeniu ulega interfejs routera 1 do sieci A. Bez zasady
podzielonych sieci router 2 wysyłałby stale do routera 1 informacje, e ma poł czenie z
sieci A (za po rednictwem routera 1). Je eli router 1 nie byłby wystarczaj co inteligentny,
mógłby wybrać tras routera 2 jako alternatyw dla własnego uszkodzonego poł czenia,
powoduj c tym samym powstanie p tli routingu. Choć wstrzymania powinny zabezpieczać
przed takimi sytuacjami, w protokole IGRP zaimplementowano tak e obsług zasady po-
dzielonych sieci, poniewa gwarantuje ona jeszcze wi ksz stabilno ć [4].
Rys. 9.12 Poniewa router l znajduje si bli ej sieci A, router 2 nie powinien ju informować ro-
utera 1 o wyliczonej przez ten router trasie do sieci A
9.4.10.3. Uaktualnienia niepoprawnej odpowiedzi
Podczas gdy zasada podzielonych sieci powinna zabezpieczać przed powstawaniem
p tli routingu mi dzy s siaduj cymi routerami, uaktualnienia niepoprawnej odpowiedzi
maj stanowić ochron przed wi kszymi p tlami routingu. Wzrost warto ci metryk routin-
gu oznacza zazwyczaj powstanie p tli routingu. Wysyłane s wówczas uaktualnienia nie-
107
poprawnej odpowiedzi w celu usuni cia danej trasy i przeł czenia jej w stan wstrzymania.
Router  zatruwa" tras , wysyłaj c do routera, który pierwotnie ogłosił j w sieci, uaktual-
nienie podaj ce jako warto ć metryki niesko czono ć.  Zatrucie" trasy mo e przyspieszyć
osi gni cie zbie no ci [4].
9.4.10.4. Informacje dostarczane IGRP przez metryki
Protokół IGRP korzysta z ró nego rodzaju informacji dostarczanych przez metryki.
Dla ka dej cie ki wiod cej przez system autonomiczny IGRP zapisuje informacje o seg-
mencie z najw szym pasmem, sumarycznym opó nieniu, najmniejszej maksymalnej
wielko ci pakietu (MTD), a tak e niezawodno ci oraz obci eniu.
Do okre lania znaczenia ka dej metryki wykorzystuje si zmienne, a podczas wyliczania
najlepszej trasy domy lnie najwi ksz rol przypisuje si szeroko ci pasma. W sieciach o
pojedynczym medium (takich jak sieci stosuj ce w cało ci technologi Ethernet) metryka
ta zostaje ograniczona do liczby skoków. W przypadku sieci o mieszanych mediach (na
przykład poł czenie Ethernetu i linii szeregowych, pocz wszy od oferuj cych 9600 bodów,
a sko czywszy na liniach T1) najbardziej po dan cie k do miejsca przeznaczenia
okre la trasa o najni szej metryce [4].
9.4.10.5. Uaktualnienia IGRP
Router korzystaj cy z IGRP rozgłasza uaktualnienia IGRP co 90 sekund. Oznacza
tras jako niedost pn , je eli w ci gu trzech uaktualnie (270 sekund) nie otrzyma infor-
macji od pierwszego routera na trasie. Po okresie pi ciu uaktualnie (450 sekund) router
usuwa tras z tablicy routingu. IGRP stosuje uaktualnienia błyskowe i uaktualnienia nie-
poprawnej odpowiedzi w celu przyspieszenia osi gni cia zbie no ci przez protokół ro-
utingu. Uaktualnienie błyskowe jest to uaktualnienie wykonane wcze niej ni tradycyjne,
wysyłane co pewien ustalony czas uaktualnienia, informuj ce inne routery o zmianie me-
tryki. Uaktualnienia niepoprawnej odpowiedzi maj za zadanie chronić przed wi kszymi
p tlami routingu, powstaj cymi na skutek zwi kszania si warto ci metryk. Uaktualnienia
niepoprawnej odpowiedzi wysyłane s w celu usuni cia trasy i przeł czenia jej w stan
wstrzymania, co zapobiega przez pewien czasu wykorzystywaniu nowej informacji routin-
gowej [4].
108
9.4.10.6. Maksymalna liczba skoków
Maksymalna dopuszczalna dla IGRP liczba skoków wynosi 255. Wielko ć ta jest za-
zwyczaj ustawiana na warto ć ni sz ni domy lne 100. Poniewa IGRP wykorzystuje
powi zane uaktualnienia, liczenie do 100 nie musi trwać zbyt długo. Nale y jednak usta-
wiać mniejsz maksymaln liczb skoków chyba, e administruje si ogromn sieci . Po-
winna to być przynajmniej tak du a warto ć, jak maksymalna liczba routerów, przez któr
kiedykolwiek b dzie przebiegać w sieci dowolna trasa. Je eli protokół IGRP u ywany jest
równie w sieci zewn trznej, liczba skoków musi uwzgl dniać dan sieć plus sieć ze-
wn trzn [4].
109
10. ZASTOSOWANIE ROUTINGU W SIECI LAN
Wydajno ć sieci LAN wykorzystuj cej współdzielone medium mo e zostać zwi k-
szona za pomoc podziału sieci LAN na segmenty. W tej cz ci naszej pracy nie b dziemy
si zajmowali przedstawieniem wszystkich zagadnie zwi zaniem z segmentacj sieci
LAN, naszym celem jest wskazanie, jaki udział w segmentacji sieci LAN ma routing, oraz
jakie korzy ci wi si z zastosowaniem takiego rozwi zania.
Na pocz tku przedstawiony jest ogólny opis problematyki segmentacji sieci lokalnych, na-
st pnie pokazane zastosowanie routera w segmentacji sieci LAN. Ko cowa cz ć dotyczy
roli routingu w sieciach wirtualnych stosowanych w sieciach lokalnych. Sieci wirtualne s
równie jednym ze sposobów podziału sieci lokalnych, które zwi kszaj wydajno ć sieci
przez ograniczenie ilo ci ruchu rozgłoszeniwego, do stacji nale cych do konkretnych sie-
ci wirtualnych.
10.1. Ogólny opis problematyki segmentacja sieci LAN
Sieć mo e być podzielona na mniejsze jednostki zwane segmentami. Ka dy segment
u ywa metody dost pu CSMA/CD i utrzymuje w swoich ramach ruch mi dzy u ytkowni-
kami. Zaprezentowane jest to na Rys. 10.1.
Rys. 10.1 Przykładowy podział sieci na segmenty
110
Poprzez podzielenie sieci na trzy segmenty Rys. 10.1 zarz dzaj c sieci mo emy zmniej-
szyć zatory w ka dym z segmentów. Podczas przesyłania danych w ramach segmentu, pie
urz dze znajduj cych si w danym segmencie, dzieli przypadaj ce na ka dy z nich, pa-
smo o przepustowo ci 10Mb/s. W posegmentowanych sieciach lokalnych Ethernet, dane
przekazywane pomi dzy segmentami przesyłane s przez szkielet sieci przy u yciu mostu,
routera lub przeł cznika [4].
10.2. Segmentacja przy u yciu routerów
Podstawowym urz dzeniem słu cym do segmentacji sieci LAN jest most, ale routery s
bardziej zaawansowane ni typowe mosty. Most zachowuje si w sieci pasywnie i działa
na poziomie warstwy Å‚ cza danych. Router pracuje w warstwie sieci i opiera wszystkie
swoje decyzje o przekazywaniu danych mi dzy segmentami adresu protokół warstwy sieci.
Routery tworz najwy szy poziom segmentacji, co widać na Rys. 10.2 przekazuj c dane
do koncentratora, do którego podł czone s stacje robocze. Router podejmuje decyzje o
przekazywaniu danych do segmentów poprzez analizowanie adresu przeznaczenia pakietu
danych i zagl danie do swej tablicy routingu po instrukcje dotycz ce przekazywania.
Aby ustalić najlepsz cie k , po której nale y przekazać pakiet do miejsca przeznaczenia,
router musi zbadać zawarto ć pakietu. Ten proces pochłania czas. Protokoły wymagaj ce
od odbiorcy przesłania nadawcy potwierdzenia odebrania ka dego pakietu (znane jako pro-
tokoły zorientowane powiadomieniowo), charakteryzuj si 30-40% strat przepustowo ci.
Protokoły, które wymagaj jedynie niezb dnych potwierdze (protokoły z przesuwnym
oknem), wykazuj 20-30% utrat przepustowo ci. Dzieje si tak, poniewa mi dzy nadaw-
c a odbiorc przekazywany jest mniejszy ruch [4] (to znaczy, przesyłanych jest mniej po-
twierdze ).
111
Rys. 10.2 Routery ustalaj , do którego koncentratora i segmentu nale y przekazać pakiet danych
Routery implementowane s w sieciach lokalnych z kilku powodów:
x w celu utworzenia mi dzy segmentami sieci LAN cie k , filtruj c przepływ pa-
kietów danych
x odseparować transmisje rozgłoszeniowe protokołu ARP
x odseparować kolizje mi dzy segmentami
x wprowadzić miedzy segmentami filtrowanie usług warstwy 4.
Routery pozwalaj tak e sieciom lokalnym na nawi zywanie poł cze z sieciami rozle-
głymi (WAN), takimi jak Internet.
Pokazany na Rys. 10.3 routing, decyduje w oparciu o adresowanie warstwy 3, o przepły-
wie ruchu mi dzy niezale nymi segmentami sieci, takimi jak sieć IP i jej podsieć. Router
jest jednym z najbardziej wpływowych urz dze w topologii sieci.
112
Rys. 10.3 Routing warstwy 3 zajmuje si takimi zagadnieniami, jak zapotrzebowanie na fizycznie
niezale ne podsieci
Router przekazuje pakiety danych na podstawie ich adresów docelowych. Router nie prze-
kazuje transmisji rozgłoszeniowych, takich jak dania ARP. Z tego powodu interfejs ro-
utera traktowany jest jako punkt wej cia i wyj cia domeny rozgłoszeniowej i powstrzymu-
je transmisje rozgłoszeniowe przed przedostaniem si od innych segmentów sieci lokalnej
[4].
10.2.1. Zastosowanie routerów do budowy skalowalnych sieci
Jak pokazali my na Rys. 10.4 routery zapewniaj skalowalno ć, poniewa pełni funk-
cj cian ogniowych dla transmisji rozgłoszeniowych. Dodatkowo, co pokazuje Rys. 10.4,
routery s w stanie zapewnić zwi kszon skalowalno ć dzi ki dzieleniu sieci i podsieci.
Dzieje si tak, poniewa adresy warstwy 3 zazwyczaj maj pewn struktur , któr nadaj
im wła nie routery. Tabela 10.1 pokazuje rozwi zania, które mog zwi kszyć skalowalno-
ci sieci. Ostatnim krokiem przy dzieleniu sieci na podsieci jest opracowanie i opisanie
schematu adresowania IP do wykorzystania w sieci.
113
Rys. 10.4 Podział sieci na podsieci zrealizowana przez router .
Tabela 10.1 zawiera dresy logiczne przypisywane do fizycznej sieci
Tabela 10.1
Adres logiczny Fizyczne urz dzenia sieciowe
x.x.x.1-x.x.x.l0 Porty routera oraz porty sieci LAN i WAN
x.x.x.11-x.x.x.20 Przeł czniki sieci LAN
x.x.x.21-x.x.x.30 Serwery korporacyjne
x.x.x.31-x.x.x.80 Serwery grup roboczych
x.x.x.81-x.x.x.254 Hosty
Technologia routingu odfiltrowuje transmisje rozgłoszeniowe ł cza danych oraz transmisje
rozgłoszeniowe do grup. Poprzez dodawanie do routera portów, z dodatkowymi adresami
sieci lub podsieci, mo na w miar potrzeb dzielić zło on sieć na segmenty. Adresowanie
protokołu sieciowego oraz routing oferuj wbudowan skalowalnosć. Przy podejmowaniu
decyzji, czy nale y wykorzystać routery, czy przeł czniki, trzeba zadać sobie pytanie, jaki
problem chce si rozwi zać. Je eli dotyczy on bardziej protokołu ni rywalizacji o dost p,
to odpowiedniejszym rozwi zaniem b d routery. Routery rozwi zuj problemy z nad-
miernym ruchem rozgłoszeniowym, słabo skalowalnymi protokołami i kwestiami bezpie-
cze stwa oraz adresowaniem warstwy sieci. Jednak routery s bardziej kosztowne i trud-
niejsze w konfiguracji ni przeł czniki[4].
114
10.2.2. Wykorzystanie routerów do nadawania struktury logicznej
Jak pokazano na Rys. 10.4, dzi ki routerom mo na tworzyć podsieci IP, nadaj c struktu-
r adresom. Gdy wykorzystuje si mosty i przeł czniki, z ka dego portu musz być usuni -
te wszystkie nieznane adresy. Z wykorzystaniem routerów, hosty oparte na adresowaniu
warstwy sieci mog rozwi zać problem odnalezienia pozostałych hostów, bez konieczno-
ci usuwania adresów. Je eli adres docelowy jest adresem lokalnym, wówczas nadaj cy
host mo e dokonać enkapsulacji pakietu w nagłówek ł cza danych i przesłać pojedyncz
ramk transmisji bezpo rednio do stacji. Router nie zobaczy ramki i nie b dzie oczywi cie
musiał jej usuwać. Mo liwe, e nadaj cy host b dzie musiał wykorzystać ARP, co wywoła
transmisj rozgłoszeniow , jednak b dzie to jedynie lokalna transmisja rozgłoszeniow i
nie zostania przekazana przez router. Je eli adres docelowy nie jest adresem lokalnym,
wówczas nadaj ca stacja prze le pakiet do routera. Router prze le ramk w miejsce prze-
znaczenia lub w miejsce nast pnego skoku w oparciu o tablic routingu. Bior c pod uwag
tak funkcj routingu oczywiste jest, e du e, skalowalne sieci LAN, musza wykorzysty-
wać okre lon liczb routerów [4].
10.3. Zastosowanie routingu w sieciach wirtualnych
Sieć wirtualna jest domen rozgłoszeniow ustanowion według okre lonych zasad. Po-
jawia si jednak problem, kiedy zachodzi potrzeba skomunikowania si stacji z jednej sieci
VLAN ze stacj z inn sieci VLAN. Aby było to mo liwe musimy zastosować routing
mi dzy tymi sieciami wirtualnymi.
Zadanie to mo na wykonać na dwa sposoby albo za pomoc centralnego routera albo na
obrze u sieci (w le klienta lub serwerze). Routing scentralizowany mi dzy sieciami wir-
tualnymi jest stosowany o wiele cz ciej [14].
10.3.1. Scentralizowany routing w sieciach VLAN
Scentralizowany routing w sieciach VLAN wymaga umieszczonego w centralnym
punkcie routera, który b dzie ł czył sieci wirtualne. W tego typu routingu wykorzystujemy
router, który jest poł czony z przeł cznikiem VLAN tylko jednym poł czeniem, tzw.  jed-
115
nor ki router . Zwykle routery posiadaj przynajmniej dwa poł czenia mi dzy sieciami
LAN, lub sieciami LAN i WAN. Jednak w tym przypadku router otrzymuje pakiet, deko-
duje adres i oblicza drog . Nast pnie wysyła informacj z powrotem z odpowiednimi in-
formacjami o routingu, tak eby stacja docelowa mogła go otrzymać. Zasad działania tego
typu routingu przedstawia Rys. 10.5
Rys. 10.5 Zasada pracy  jednor kiego routera
10.3.2. Brzegowy routing w sieciach VLAN
W takim przypadku routing jest wykonywany na brzegu sieci , a nie w jej centrum. Na
przykład serwer routuj cy jest członkiem ró nych sieci wirtualnych. Serwery ró nych sys-
temów (Linux, NetWare, NT) potrafi wykonywać routing programowo. Taki serwer mo e
116
posiadać dedykowan kart VLAN ka dej z sieci, mi dzy którymi ma zapewniać routing.
Przykład routingu brzegowego przedstawia rysunek Rys. 10.6.
Rys. 10.6 Przykład sieci VLAN opartej na serwerze z dwoma kartami sieciowymi.
Rys. 10.7 Przykład sieci VLAN opartej na serwerze z jedn kart sieciow .
Routing brzegowy mo e być równie realizowany na serwerach maj cych jedno poł cze-
nie do przeł cznika VLAN. Jest to mo liwe wtedy, gdy serwer jest członkiem kilku sieci
wirtualnych opartych na protokole. Sposób poł czenia takiego routera przedstawia rysunek
Rys. 10.7.
117
10.3.3. Wykorzystanie sieci VLAN do zapewnienia bezpiecze stwa
Sieci VLAN mog być tak e wykorzystane do zapewnienia bezpiecze stwa poprzez
przydzielenie u ytkowników do grup VLAN, w zale no ci od pełnionych funkcji. Sytuacj
tak przedstawia rysunek Rys. 10.8.
Rys. 10.8 Sieci VLAN zapewniaj ochron rozgłaszania i bezpiecze stwo
Na rysunku Rys. 10.8 w celu zaimplementowania przypisania do sieci VLAN za-
stosowa przyporz dkowanie fizycznych portów. Porty P0, P1 i P4 zostały przypisane do
sieci VLAN1. Porty P2, P3 i P5 nale do sieci VLAN2. Komunikacja mi dzy sieciami
VLAN1 i VLAN2 mo e odbywać si tylko za po rednictwem routera. Dzi ki temu ograni-
cza si rozmiar domeny rozgłoszeniowej i wykorzystuje si router w celu ustalenia, czy
sieć VLAN1 mo e porozumieć si z sieci VLAN2. Oznacza to, e na podstawie przypisa
do konkretnych sieci VLAN mo na opracować polityk bezpiecze stwa [4].
118
11. PODSUMOWANIE
Proces projektowania sieci komputerowych, ze wzgl du na ilo ć, oraz ró norodno ć,
mo liwych do zastosowania protokołów i usług, jak równie rozwi za sprz towych jest
procesem niezwykle skomplikowanym. Niniejsza praca  Metody i rodki projektowania
sieci komputerowych , zawiera analiz niektórych z problemów, wyst puj cych przy pro-
jektowaniu sieci komputerowych. Omawiane s w niej kolejno :
1. Ogólne zasady projektowania, a w szczególno ci kolejne etapy projektowania.
2. Media stosowane przy budowie sieci komputerowych z podaniem ich klasyfikacji i
wła ciwo ci fizycznych.
3. Charakterystyki poszczególnych rodzajów topologii sieci komputerowych.
4. Reguły doboru tras, ich podział oraz algorytmy stosowane do optymalizacji topolo-
gii i maksymalizacji przepływów w sieci.
5. Protokół wielodost pu do ł cza CSMA/CD (do pracy doł czona jest multimedialna
prezentacja działania protokołu).
6. Poszczególne warstwy modelu OSI.
7. Routing, protokoły routingu, segmentacja sieci na podsieci przy wykorzystaniu ro-
uterów.
119
12. LITERATURA
[1] Tomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest  Wprowadzenie do al-
gorytmów  wydanie drugie,WNT Warszawa, 1998r.
[2] Jerzy Seidler  Analiza i synteza sieci ł czno ci dla systemów teleinformatycz-
nych ,PWN, Warszawa 1979r.
[3] Robert Wright  Elementarz routingu IP , Mikom, Warszawa 1999r.
[4] Cisco Systems Vito Amato  Akademia sieci Cisco drugi rok nauki , Mikom, War-
szawa 2001r.
[5] Larry L. Peterson, Bruce S. Davie  Sieci komputerowe  podej cie systemowe ,
Wydawnictwo Nakom, Pozna 2000r.
[6] Marian Marciniak  A
czno ć wiatłowodowa , Wydawnictwa Komunikacji i A
cz-
no ci, Warszawa 1998r.
[7] L. Banachowski, K.Diks, W. Rytter  Algorytmy i struktury danych , WNT, War-
szawa 1999r.
[8] Józef Wo niak, Krzysztof Nowicki  Sieci LAN, MAN i WAN  protokoły komu-
nikacyjne , Wydawnictwo Fundacji Post pu Telekomunikacji, Kraków 2000r.
[9] Praca zbiorowa pod redakcj Krzysztofa Wajdy,  Wybrane zagadnienia budowy i
eksploatacji sieci korporacyjnych , Wydawnictwo Fundacji Post pu Telekomunikacji,
Kraków 1999r.
[10] Douglas E. Comer  Sieci komputerowe i intersieci ,WNT, Warszawa 2001
[11] Adam Urbanek  Ilustrowany Leksykon Teleinformatyka , IDG Poland S.A., War-
szawa 2001r.
[12] Tim Parker, Mark Sportack  TCP/IP Ksi ga eksperta , Helion, Gliwice 2000
[13] Marc Sportack  Sieci komputerowe  Ksi ga eksperta , Helion, Gliwice 1999
[14] Robert Breyer Sean Rileyi  Switched, Fast i Gigabit Ethernen , Helion , Gli-
wice1999r.
[15] Buchanan Wiliam  Sieci komputerowe , Wydawnictwo komunikacji I A
czno ci,
Warszawa 1999r.
[16] Shafer Kevin  Wielka ksi ga sieci , Wydawnictwo PLJ, Warszawa 1999.
[17] Tanenbaun A. Sieci komputerowe , WNT, Warszawa 19998r.
[18] Frank J. Derfler  Poznaj sieci , Mikom, Warszawa 1999r.
[19] Paul E. Robichaux  zdalny dost p", Mikom, Warszawa 2000r.
[20] Józef Muszy ski  Planowanie i projektowanie sieci , NetWorld 2/2002, IDG Po-
land, Warszawa 2002r.
120
POLITECHNIKA RZESZOWSKA RZESZÓW 2002
IM. IGNACEGO A
UKASIEWICZA
WYDZIAA
ELEKTROTECHNIKI I INFORMATYKI
ZAKA
AD SYSTEMÓW ROZPROSZONYCH
STRESZCZENIE PRACY DYPLOMOWEJ IN YNIERSKIEJ
TYTUA

METODY I RODKI PROJEKTOWANIA SIECI KOMPUTEROWYCH
Autorzy: Mach SÅ‚awomir
Maci ga Jacek
Promotor dr hab in Georgy Loutsky prof. PRz
SÅ‚owa kluczowe:algorytm Prima, Kruskala, Dijkstry, Forda Bellmana, Forda Fulkersona,
routing, CSMA/CD
Celem niniejsze pracy jest przybli enie zagadnie zwi zanych z projektowaniem
sieci komputerowych. Omówione zostały rodzaje topologii oraz media stosowane przy bu-
dowie sieci komputerowych. Przedstawione zostały równie sposoby znajdowania tras
optymalnych przy u yciu algorytmów: Prima, Kruskala, Dijikstry, Forda Bellmana, Forda
Fulkersona oraz metod Essau-Williamsa. W pracy zawarty jest tak e opis działa protoko-
Å‚u CSMA/CD oraz routing w sieciach komputerowych.
RZESZOW RZESZOW 2002
UNIVERSITY OF TECHNOLOGY
FACULTY OF ELECTRICAL AND COMPUTER ENGINEERING
DISTRIBUTED SYSTEMSDEPARTMENT
MASTERS DIPLOMA THESIS
TITLE
METHOD AND MEANS DESIGNING COMPUTER NETWORK
Author s: Mach SÅ‚awomir
Maci ga Jacek
Supervisior: Dr Hab Eng. Georgy Loutsky Prof PRz
Key words : algorithms Prim s, Kruskal s, Dijkstry s, Ford Bellman s Ford Fulkerson s,
routing, CSMA/CD
The aim of thesis is making clear the issues, which are concerned with designing computer
network. There are presented different methods of algorithms: Prim s, Kruskal s,
Dijkstry s, Ford Belln s, Ford Fulkerson s, and Essau Wiliam s method. In thesis is in-
cluded the description of how the protocol CSMA/CD works, and routing in computer
networks.
121