Politechnika Åšlaska

Wydzia Automatyki, Elektroniki i Informatyki
l
Instytut Informatyki
Praca dyplomowa
magisterska
Dynamiczny przydzia pasma użytkownika
l
sieci z wykorzystaniem us QoS w systemie
lugi
Linux
Autor: Krzysztof Wilk
Promotor: dr inż. Ryszard Maceluch
Gliwice 2002
Spis treści
1 Cel i zakres pracy 4
2 Zasady dzia mechanizmów Quality of Service 8
lania
2.1 Architektura QoS - Integrated Services . . . . . . . . . . . . . 10
2.2 Architektura QoS - Differentiated Services . . . . . . . . . . . 12
3 Stan aktualny implementacji QoS w systemie Linux 19
3.1 Algorytmy kolejkowania pakietów . . . . . . . . . . . . . . . . 21
3.1.1 Algorytmy kolejkowania FIFO . . . . . . . . . . . . . . 22
3.1.2 Algorytm kolejkowania PRIO (PRIOrities) . . . . . . . 24
3.1.3 Algorytm kolejkowania TBF (Token Bucket Filter) . . 25
3.1.4 Algorytm kolejkowania SFQ (Stochastic Fairness Qu-
eueing) . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.1.5 Algorytmy kolejkowania RED (Random Early Detection) 30
3.1.6 Algorytm kolejkowania CBQ (Classful Based Queueing) 33
3.1.7 Algorytm kolejkowania DSMARK (DiffServ Mark) . . 37
3.1.8 Algorytm kolejkowania CSZ (Clark-Shenker-Zhang) . . 38
3.2 Rodzaje filtrów . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.2.1 Filtr route . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.2.2 Filtr fw . . . . . . . . . . . . . . . . . . . . . . . . . . 42
1
3.2.3 Filtry rsvp i rsvp6 . . . . . . . . . . . . . . . . . . . . 43
3.2.4 Filtr tcindex . . . . . . . . . . . . . . . . . . . . . . . . 44
3.2.5 Filtr u32 . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.3 Zastosowanie algorytmów kolejkowania i filtrów . . . . . . . . 46
4 Możliwości rozbudowy implementacji QoS w systemie Linux 49
4.0.1 Opis ogólny . . . . . . . . . . . . . . . . . . . . . . . . 50
4.0.2 Opis implementacji algorytmów kolejkowania . . . . . . 52
4.0.3 Opis implementacji klas ruchu . . . . . . . . . . . . . . 55
4.0.4 Opis implementacji filtrów pakietów . . . . . . . . . . 56
5 Badania wykonane bez w aczonych mechanizmów QoS 58
l

5.1 Cel badań . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
5.2 Sprzet użyty w badaniach . . . . . . . . . . . . . . . . . . . . 59

5.3 Opis oprogramowania testujacego . . . . . . . . . . . . . . . . 60

5.3.1 Zasadność pomiarów w trybie użytkownika . . . . . . . 61
5.3.2 Zasadność pomiarów w trybie jadra . . . . . . . . . . . 62

5.3.3 Opis przyjetego rozwiazania . . . . . . . . . . . . . . . 63

5.4 Przewodnik po badaniach . . . . . . . . . . . . . . . . . . . . 64
5.4.1 Pomiar przepustowości acza . . . . . . . . . . . . . . . 64
l

5.4.2 Pomiar opóz
nienia przekazywania pakietów IP . . . . . 65
6 Badania wykonane z w aczonymi mechanizmami QoS 82
l

6.1 Cel badań . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
6.2 Badania z wykorzystaniem algorytmu PRIO . . . . . . . . . . 83
6.3 Badania wykonane z wykorzystaniem algorytmu TBF . . . . . 99
6.4 Badania wykonane z wykorzystaniem algorytmu RED . . . . . 105
7 Podsumowanie oraz wnioski 109
2
Bibliografia 112
Spis rysunków 115
Spis tabel 118
3
Rozdzia 1
l
Cel i zakres pracy
Predkość transferu danych w sieciach komputerowych zależy od aktual-

nego obcia żenia sieci (ilość przesy przez sieć danych). Podejście takie
lanych
zwiazane jest z historia powstawania sieci. Pierwsze aplikacje sieciowe oparte

w wiekszości o przesy znaków ASCII nie wymaga ani dużych przepusto-
l ly

wości, ani nie stawia ograniczeń na czas dostarczania pakietów do punktu
ly
przeznaczenia. Konwergencja sieci komputerowych, telefonicznych oraz tele-
wizyjnych jaka możemy obserwować stawia przed projektantami sieci nowe
zadania (przesy faksów, rozmowy telefoniczne). Aktualnie sieci kompute-
l
rowe jednak nie zapewniaja odpowiednich mechanizmów zaimplementowa-
nych w komputerach i urzadzeniach sieciowych sterujacych ruchem pakietów

w sieciach komputerowych, stad jakość obrazu i p
lynność dz
wieku zależy

w znacznym stopniu od nateżenia ruchu w sieciach komputerowych. Jedy-

nym typem sieci, gdzie realnie mechanizmy regulacji ruchu w sieci w za-
leżności od potrzeb użytkownika zosta zaimplementowane jest sieć ATM.
ly
Ze wzgledu na popularność protoko IP czyni sie starania stworzenia iden-
lu

tycznych możliwości w Internecie. Praca ta opisuje wykorzystanie protoko
lu
IP w wersji 4  IPv6, a protokó IP w wersji 6  IPv6 jest tylko cza-
l
4
sem wspominany. Jeśli nie podano numeru wersji protoko to omawiany
lu,
jest protokó IPv4. Jeśli przyjmiemy, że klienci p swym operatorom sieci
l laca
za dostep do takich us to dochodzimy do wniosku, że pewne aplikacje
lug,

wymagaja tego, aby pakiet zosta dostarczony w pewnym określonym cza-
l
sie. Rozwiazaniem tego zagadnienia mog być zwiekszenie przepustowości
loby

sieci. Doświadczenie pokazuje, że rozwiazanie tego problemu w taki sposób

jest niemożliwe na d mete. Rozwiazaniem może być dynamiczny przy-
luższa

dzia pasma użytkownikom.
l
Niniejsza praca opisuje problem dynamicznego przydzia pasma użyt-
lu
kownikowi sieci komputerowej w celu zapewnienia możliwości korzystania
z us sieciowych, przede wszystkim multimedialnych oraz interaktywnych.
lug
Dotycza one obrazu i dz
wieku przesy w sieciach komputerowych.
lanych

W tej pracy z powodów przedstawionych powyżej opisano problematyke

tylko dla sieci opartych na protokole IP. Jako dynamiczny przydzia pasma
l
przyjmuje sie przydzia pasma zależny od rodzaju us z jakiej użytkownik
l lugi

bedzie korzysta Nawiazujac do analogii z p dostepem, możemy sobie
l. latnym

wyobrazić, że klient który zap l operatorowi sieci za us wyższej jakości
laci luge

powinien mieć p
lynniejszy dostep do multimediów sieciowych

Jako obiekt badań wybrano system operacyjny Linux. S Linux ozna-
lowo
cza samo jadro systemu operacyjnego, natomiast system operacyjny dystry-

buowany razem z dodatkowymi programami narzedziowymi i użytkowymi

określa sie jako dystrybucje Linuksa. Przyk
ladowymi dystrybucjami Linuksa

sa Debian i RedHat. System ten znakomicie nadaje sie do wszelkich badań

sieci, ponieważ jest on dostepny wraz z pe kodem z
ród
lnym lowym. Liberalna

licencja, na której jest wydawany, pozwala oprócz czytania kodu z
ród
lowego
w celu zrozumienia dzia systemu operacyjnego również swobodna mody-
lania
fikacje tego kodu. W systemie Linux dynamiczny przydzia pasma jest realizo-
l

5
wany poprzez Gwarancje jakości us lug . Cześciej używa sie równoznacznego


określenia angielskiego Quality of Service (QoS ). W dalszej cześci pracy


używane bedzie bardziej popularne określenie anglojezyczne (patrz rozdz. 2).

Celem pracy dyplomowej jest analiza zagadnień zwiazanych z QoS

od strony teoretycznej, poznanie jej implementacji w Linuksie oraz zbadanie
czy ruter oparty na komputerze z systemem Linux może spe wymagania
lniać
stawiane ruterom QoS. Opis implementacji umieszczono w rozdz. 3. Prze-
prowadzenie badań dostepnych mechanizmów pozwoli na ocene jakościowa

implementacji oraz próbe optymalizacji jej dalszych ulepszeń .

W rozdziale drugim przybliżona jest ogólna idea QoS oraz wprowadzone
sa podstawowe pojecia z nia zwiazane. W tym celu podzielono QoS na dwa

podejścia do problemu: IntServ oraz DiffServ. Omówiony jest również skró-
towo protokó sygnalizacyjny RSVP, a także przedstawiony format nag ów-
l l
ków pakietów IPv4 oraz IPv6. Na koniec przedstawiona jest symbolicznie
droga pakietu w ruterze.
W rozdziale trzecim opisany jest aktualny stan rozwoju implementacji
QoS w Linuksie. W ramach tego opisane sa dostepne filtry (przydzielaja

przychodzace pakiety do konkretnych klas ruchu w których obowiazuja usta-

lone algorytmy kolejkowania) oraz algorytmy kolejkowania.
Rozdzia czwarty opisuje ogólny schemat implementacji mechanizmów
l
QoS używany w Linuksie. Korzystajac z tych wytycznych można zmodyfi-

kować dostepne już algorytmy oraz zaimplementować kolejne znane z innych

realizacji QoS niż linuksowa, przyk z ruterów Cisco.
ladowo
Rozdzia piaty przedstawia wykonane badania zachowania sie dostepnych
l

aktualnie mechanizmów realizacji QoS w Linuksie.
W rozdziale szóstym dokonana jest analiza ilościowa wyników badań, po
której nastepuje analiza ilościowa.

6
W ostatnim rozdziale znajduje sie podsumowanie przeprowadzonych ba-

dań. W rozdziale tym wysnuwa sie też wnioski z wyników ilościowych oraz

jakościowych dokonanych pomiarów.
7
Rozdzia 2
l
Zasady dzia
lania mechanizmów
Quality of Service
Przed laty nikt nie przewidywa że sieci komputerowe beda wykorzysty-
l,

wane do transmisji danych multimedialnych (transmisja dz
wieku i obrazu)

oraz konwergentnych (wspólne okablowanie dla po aczenia z Internetem i cen-
l

tralka telefoniczna) dlatego przy tworzeniu sieci Internet jednym z g ównych
l

za by prostota rozwiazań. Nie by wtedy dostepnych w sieci us
lożeń la lo lug

interaktywnych (np. WWW ), ani multimedialnych. Nikt również nie spo-
dziewa sie tak gwa
l ltownego rozwoju Internetu, zarówno ilości jego użyt-

kowników, jak i zapotrzebowania na coraz wieksze przepustowości. Należy

również pamietać, że w poczatkowym okresie sieci komputerowe by uży-
ly

wane g ównie w celach naukowych oraz edukacyjnych, a nie rozrywkowych
l
i handlowych, od użytkowników końcowych nie by pobierane op za do-
ly laty
step do Internetu, wiec wszyscy mieli dostep do sieci na tych samych pra-

wach. Dlatego też przyjeto wiele uproszczeń konstrukcyjnych. Jednym z nich

jest równouprawnienie wszystkich transmisji sieciowych. Internet jaki znamy
przekazuje pakiety w myśl zasady najlepszego wysi [4] (ang. best ef-
lku

8
fort). Oznacza to, że komputery lub wyspecjalizowane urzadzenia zajmujace

sie przekazywaniem pakietów nazywane ruterami (ogólnie nazywane wez
lami

sieci), sa zaprojektowane tak, aby jak najszybciej przekazywać dalej otrzy-
mane pakiety. W razie wystapienia przecia żenia ruchu, pakiety sa przez nie

odrzucane bez faworyzowania jakichkolwiek [28]. Innymi s przekazujac
lowy,

dalej pakiet wez biora pod uwage tylko jego przeznaczenie ( gdzie ).
ly


Jeśli chcielibyśmy zwiekszyć elastyczność dotychczasowego modelu sieci

i umożliwić faworyzowanie niektórych transmisji, to dochodzimy do wniosku,
ze oprócz przeznaczenia ( gdzie ) należy również przesy pakiety w odpo-
lać

wiednim momencie ( kiedy ). Można to osiagna ć stosujac mechanizmy QoS.


Przez QoS rozumie sie sta w ściśle wyznaczonych granicach nastepu-
lość

jacych parametrów transmisji [4] w sieciach komputerowych:

Przepustowość (ang. throughput) ilość danych przesy z jednego
lanych
miejsca do drugiego w określonym czasie. Przez ilość danych rozumie sie

ilość bitów. Ilość danych, która może zostać przes danym laczem,
lana

w praktyce jest niższa od maksymalnej z powodu opóz
nień w transmisji
danych. Jednostka przepustowości jest bps (bit na sekunde).

Opóz
nienie (ang. latency) zw w transmisji danych. W ruterze opóz
-
loka
nieniem jest czas up
lywajacy miedzy przyjściem pakietu, a jego prze-

s dalej. Dlatego nazywa sie go również czasem propagacji.
laniem

Zmienność opóz
nienia (ang. jitter) zniekszta taktowania sygna
lcenie lu
zachodzace w trakcie transmisji w sieci, prowadzace do transmisji pakie-

tów sieciowych w nieregularnych odstepach . W ruterze zmienność opóz
-

nienia transmisji pakietów wychodzacych zachodzi wtedy, gdy sprze-

towo nie nada ża on z obs ruchu sieciowego.
luga
9
Zgodnie z klasyfikacja IETF (ang. Internet Engineering Task Force) za-
leca sie implementować QoS na jeden ze sposobów:

1. Integrated Services [14]
2. Differentiated Services [12] [13]
2.1 Architektura QoS - Integrated Services
W architekturze Integrated Services (w skrócie IntServ) zasoby sieci sa
przydzielane dla danej aplikacji na żadanie po uprzedniej rezerwacji. Rezer-

wować je można dla pojedynczego strumienia danych lub agregacji strumieni
danych. W celu rezerwacji stosuje sie algorytm RSVP (ang. ReSerVation

Protocol) [7].
Protokó ten opiera sie na kilku za
l lożeniach [4]:

" W pe obs
lni lugiwane sa transmisje jeden-do-jednego (ang. unicast) oraz
jeden-do-wielu (ang. multicast). W tych drugich każdemu z odbiorców
może zostać przyznany inny poziom QoS.
" Protokó dzia jako rozszerzenie protoko IP, a nie jako jego substy-
l la lu
tut. Upraszcza to jego implementacje oraz u wspó zarówno
latwia lprace

z IPv4 jak i IPv6. Wymusza to jednak okresowe ponawianie sygnaliza-
cji (ang. soft-state signalling) jako warunek konieczny do utrzymywania
po aczenia.
l

" Sesje RSVP sa jednokierunkowe (ang. simplex). Upraszcza to synchro-
nizacje poprzez wstrzymanie rozpoczecia transmisji do czasu nadejścia

potwierdzenia od odbiorcy.
Przed rozpoczeciem w la
laściwej transmisji danych nadawca przesy wia-

domość PATH zawierajaca nastepujace informacje:

10
" minimalna i maksymalna przepustowość żadanego pasma

" minimalne i maksymalne opóz
nienie przekazu pakietów przez sieć
" minimalna i maksymalna zmienność opóz
nienia przekazu pakietów
" typ żadanej us (Guaranteed Service, Controlled Load Service, Best
lugi

Effort)
" identyfikacje pakietów należacych do danego strumienia danych (nu-

mery portów, rodzaj protoko transportowego itp.)
lu
Każdy ruter po drodze jeśli może dokonać żadanej rezerwacji, to prze-

kazuje dalej wiadomość PATH, w przeciwnym wypadku wysy wiadomość
la
odrzucenia zg
loszenia do nadawcy. Gdy wiadomość PATH dotrze do odbiorcy
informacji, to wysy on wiadomość RESV jako potwierdzenie. Dopiero po
la
dotarciu tej wiadomości do odbiorcy, zaczyna on transmisje danych. Rezer-

wacja musi być odnawiana okresowo. Dzia protoko sygnalizacyjnego
lanie lu
RSVP obrazuje rys. 2.1.
Rysunek 2.1: Protokó rezerwacji (RSVP)
l
W tej architekturze dostepne sa trzy typy us
lug:

" Guaranteed Service [19] - przeznaczona dla aplikacji wymagajacych nie-

zawodnej gwarancji parametrów jakości przekazu danych zwiazanych

11
z opóz
nieniami. Tak rygorystyczne wymagania parametrów transmisji
maja transmisje obrazu i dz
wieku w czasie rzeczywistym.

" Controlled Load Service [20] - przeznaczona dla aplikacji wymagajacych

bezstratnego przekazu danych i charakteryzujaca sie jakościa przekazu

lepsza niż Best Effort. Przyk lugi
ladowym zastosowaniem tego typu us
jest obs jednokierunkowych transmisji obrazu i dz
wieku.
luga

" Best Effort - przeznaczona dla aplikacji nie wymagajacych parametrów

transmisji w ściśle określonych granicach.
Model ten sprawdza sie jedynie w mniejszych sieciach, gdyż w wiekszych

sieciach pojawiaja sie problemy ze skalowalnościa (zbyt dużo komunikatów

sygnalizacyjnych w stosunku do ilości przesy danych). W ostatnich la-
lanych
tach opracowywane sa metody zwiekszania skalowalności protoko RSVP
lu

[4]. Pierwsze podejście proponuje zwiekszanie odstepów wysy pakietów
lania

sygnalizacyjnych w sytuacji, gdy charakterystyki sesji nie zmieniaja sie. Dru-

gie podejście proponuje aczenie wielu sesji RSVP dzia
l lajacych w tych sa-

mych sekcjach sieci i posiadajacych takie same charakterystyki w jedna sesje.

2.2 Architektura QoS - Differentiated Services
Architektura Differentiated Services (w skrócie DiffServ lub DS) przedsta-
wiona na rys. 2.2 rozwiazuje problem skalowalności obserwowalny w IntServ.

Wymaga ona definicji klas ruchu na etapie konfiguracji sieci. Pakiety sa przy-
pisywane do poszczególnych klas przez rutery brzegowe, a znajdujace sie w

obrebie domeny QoS rutery rdzeniowe zajmuja sie wy acznie przekazywa-
l

niem pakietów. Przez domene QoS (domene DiffServ) [28] rozumie sie te

12
cześć sieci w ramach której zagwarantowana jest żadana jakość us siecio-
lug

wych. Podzia pakietów na klasy ruchu dokonuje sie na podstawie[4]:
lu

" pola Type Of Service (TOS ) w nag ówku IPv4,
l
" pola Traffic Class (TC ) w nag ówku IPv6,
l
" wybranych pól nag ówka IP lub nag ówka protoko warstwy sieciowej
l l lu
(TCP).
Rysunek 2.2: Architektura DiffServ
Rysunek 2.3: Nag ówek pakietu IPv4
l
13
Na rys. 2.3 przedstawiony jest nag ówek pakietu IPv4. Klasyfikacja pakie-
l
tów może sie odbywać na podstawie zawartości pola TOS (ang. Type of Se-

rvice) o rozmiarze ośmiu bitów. Pierwsze trzy bity określaja pierwszeństwo

(ang. precedence) pakietu. Wykorzystywane to jest do ustalania wzglednych

priorytetów pakietów przekazywanych dalej przez rutery. Nastepne cztery

bity maja znaczenie jak nastepuje [4]:

" 1000  minimalizacja opóz
nienia przesy pakietu
lania
" 0100  maksymalizacja przepustowości
" 0010  maksymalna pewność przesy pakietu
lania
1
" 0001  minimalny koszt przesy pakietu
lania
" 0000  normalne przesy
lanie.
Ostatni bit pola TOS jest stale ustawiony na zero.
Można także przypisywać pakiety do poszczególnych klas ruchu na pod-
stawie wartości innych pól nag ówka. Szczególnie przydatne do tego sa [4]:
l
" protokó warstwy sieciowej
l
" adres z
ród
lowy
" adres docelowy
Na rys. 2.4 pokazany jest nag ówek pakietu IPv6. Pole TOS znane z
l
poprzedniej wersji protoko zosta zastapione ośmiobitowym polem klasy
lu lo


1
Celem jest ograniczenie kosztu przesy informacji. Przyk metoda osiagnie-
lania ladowa

cia celu jest przesy pakietów w chwilach kiedy sieć jest najmniej obcia żona. Można
lanie
to osiagna ć poprzez zerowanie bitu psh w nag ówku pakietu TCP. W ten sposób dystry-
l

buowane sa listy dyskusyjne oraz poczta hurtowa (ang. bulk mail) używana w celach

komercyjnych.
14
Rysunek 2.4: Nag ówek pakietu IPv6
l
ruchu (ang. traffic class). Na razie wykorzystywane jest sześć starszych bi-
tów. Bity te nazywane sa DiffServ Code Point (DSCP) i wykorzystywane sa
w architekturze DiffServ do oznaczania przynależności pakietów do konkret-
nych klas ruchu. Dwa najm bity wykorzystywane sa do przenoszenia
lodsze
informacji ECN (ang. Explicit Congestion Notification). Informacja ta po-
zwala ruterom obs
lugujacych ECN elastyczniej decydować o losie pakietów

w przypadku, gdy przydzielone danej klasie ruchu pasmo zosta przekro-
lo
czone. Ruter w takiej sytuacji może przepuścić pakiet z w aczonymi bitami
l

ECN, jeśli ca pasmo nie zosta zajete. Daje to możliwość pe
le lo lniejszego wy-

korzystania pasma niż w przypadku nie korzystania z bitów ECN.
Klasyfikacji pakietów można dokonywać również na podstawie pozosta-

lych pól [4]:
" etykieta strumienia (identyfikacja przynależności pakietu do konkret-
nego strumienia)
" adres z
ród (128-bitowy)
lowy
" adres docelowy (128-bitowy)
15
Rysunek 2.5: Nag ówek pakietu TCP
l
Na rys. 2.5 przedstawiony jest nag ówek pakietu TCP. Do klasyfikacji
l
pakietów wykorzystywane sa tylko dwa pola:
" port z
ród
lowy
" port docelowy
Klasy ruchu można inaczej przedstawić jako strumienie danych, z których
każdy ma przypisany profil ruchu określajacy jakie warunki musi spe pa-
lnić

kiet, aby zostać przypisanym do niego.
Zdefiniowane sa dwa algorytmy przekazywania pakietów wchodzacych

w sk agregacji pakietów. Ogólnie określane sa one jako zasady PHB (ang.
lad
Per Hop Behaviour) [15]:
1. Expedited Forwarding (EF) [17, 18] - wartość pola DSCP (ang. Diffe-
rentiated Services Codepoint) z nag ówka IPv6 określa żadana jakość
l

us pod katem opóz
nień przekazywania pakietów. Jeśli pakiet nie
lugi

zawiera sie w profilu ruchu danego strumienia, to zostanie odrzucony.

2. Assured Forwarding (AF) [16] - definiuje sie cztery klasy ruchu i trzy po-

ziomy odrzucania pakietów w każdej z nich. Czasem używa sie pojecia

16
kolorowanie pakietów . Pakiet może zostać przyjety do strumienia ru-


chu, odrzucony lub dopuszczony do ruchu warunkowo , tzn. nastepny


ruter brzegowy może go odrzucić jeśli ca dostepna przepustowość sieci
la

bedzie akurat zajeta.

Zasady PHB sa zwykle implementowane jako filtry, kolejki i algorytmy ko-
lejkowania.
Obecnie QoS jest realizowany na poziomie warstwy transportowej sieci
(TCP). Każdy system jest na tyle wydajny, na ile jest wydajne jego wa-

skie gard W przypadku sieci komputerowych newralgicznymi jej punk-
lo.
tami sa rutery, dlatego wiec g ówny cieżar realizacji QoS spoczywa na nich.
l

W uproszczeniu droga pakietu danych w ruterze wyglada tak jak na rys. 2.6.

Pakiety sa przyjmowane przez interfejs wejściowy, nastepnie podlegaja de-


multipleksacji , czyli odrzuceniu nag ówków warstwy fizycznej (np. Ether-
l
net). Pakiety zaadresowane do rutera sa przesy do warstwy sieciowej,
lane
a pozosta sa przekazywane dalej (ang. forwading). Nastepnie pakiety prze-
le


kazywane sa kolejkowane do klas ruchu (ang. traffic class). Każda z klas ruchu
jest inaczej traktowana i pakiety z niej sa przekazywane do interfejsu wyj-
ściowego, z którego z kolei przesy sa do nastepnego wez sieci.
lane la

17
Rysunek 2.6: Droga pakietu w ruterze
18
Rozdzia 3
l
Stan aktualny implementacji
QoS w systemie Linux
Opis stanu aktualnego dotyczy najnowszego jadra z ga ezi stabilnej do-
l

stepnego w okresie pisania pracy, czyli wersji2.4.18.

1
Linux może s jako ruter w sieci IntServ, korzystajac z demona
lużyć

RSVPd [8], ale wiekszy nacisk po w jadrze na umożliwienie realizacji
lożono

sieci typu DiffServ. Implementacja linuksowa QoS opiera sie na nastepujacych

elementach podstawowych, które można ze soba aczyć, tworzac rozbudowana
l

hierarchie klas ruchu. Elementy te rozumie sie w nastepujacy sposób:

Algorytm kolejkowania (ang. qdisc = queueing discipline)
pośredniczy w transmisji pakietów TCP miedzy jadrem a inter-

fejsem sieciowym. Pakiety wychodzace sa wstawiane do kolejki przez

ten algorytm, a pakiety wychodzace sa pobierane z kolejki (a w
laściwie

klasy) przez jadro i przekazywane sterownikowi karty sieciowej. Algo-

1
W Uniksie demonem określa sie program lub jego cześć, która nie jest uruchamiana


jawnie, ale oczekuje na wystapienie pewnego zdarzenia. Przyk
ladowym zdarzeniem może

być próba nawiazania przez zdalny proces po aczenia TCP z konkretnym portem lokalnym.
l

19
rytmy kolejkowania dziela sie na zawierajace dalsze klasy (np. CBQ)

i bezklasowe (np. TBF ).
Klasa to kolejka w której przechowywane sa pakiety kolejkowane przez po-
dany algorytm kolejkowania. Klasa jest identyfikowana na podstawie
32-bitowego identyfikatora klasy (ang. class ID) nadawanego przez ad-
ministratora. Wewnatrz jadra klasa jest identyfikowana z pomoca we-

wnetrznego identyfikatora klasy (ang. internal class ID) przydzielanego

automatycznie przez jadro przy tworzeniu klasy.

Filtr (ang. classifier) jest przyporzadkowany do konkretnego algorytmu

kolejkowania. Decyduje on w której klasie zostanie umieszczony przy-
chodzacy pakiet TCP. Pakiet jest sprawdzany sekwencyjnie przez

wszystkie filtry obs
lugujace dany algorytm kolejkowania aż do pierw-

szego dopasowania (analogicznie jak regu firewalla). Filtr jest identy-
ly
fikowany wewnatrz jadra z pomoca wewnetrznego identyfikatora filtra

(ang. internal filter ID) przyznawanego automatycznie przez jadro przy

tworzeniu filtra.
Sterowanie ruchem (ang. traffic control) polega na wykonywaniu jednej
lub kilku z poniższych operacji:
Kszta
ltowanie (ang. shaping) ruchu polega na regulowaniu przepusto-
wości strumienia pakietów wychodzacych. Poza ograniczaniem dostep-

nej dla danej klasy przepustowości pozwala również na wyg
ladzanie
chwilowych przecia żeń ruchu. Przyk
ladowymi algorytmami kolejkowa-
nia realizujacymi kszta
ltowanie ruchu sa TBF i HTB.

Szeregowanie (ang. scheduling) transmitowanych pakietów to sposób
na poprawe interaktywności ruchu pochodzacego z wymagajacych tego

20
klas przy jednoczesnym zagwarantowaniu dużej przepustowości klasom
realizujacym transfery masowe. Przyk
ladowe algorytmy kolejkowania

realizujace szeregowanie to CBQ, HTB oraz PRIO.

Regulowanie (ang. policing) ruchu [28] polega na monitorowaniu pakie-
tów wchodzacych w celu upewnienia sie, że nadawca nie lamie zasad


ustalonej wcześniej charakterystyki ruchu. Równocześnie kszta
ltowany
jest ruch wchodzacy. Dostepnym algorytmem kolejkowania regulujacym

ruch jest Ingress.
Odrzucanie (ang. dropping) pakietów polega na nie obs
lugiwaniu pakie-
tów przekraczajacych ustawione limity przepustowości. Dotyczy ono

zarówno ruchu wchodzacego jak i wychodzacego. Przyk
ladowym algo-

rytmem tak dzia
lajacym jest RED.

3.1 Algorytmy kolejkowania pakietów
Aktualnie dostepnych standardowo jest sześć algorytmów kolejkowania.

W razie potrzeby można napisać swój modu realizujacy inny algorytm ko-
l

lejkowania. Należa dodatkowo w tym celu zmodyfikować standardowe
loby
narzedzie s do konfiguracji klas ruchu tc lub też napisać w
lużace lasne.

Wszystkie algorytmy kolejkowania można podzielić na:
Algorytmy klasowe (ang. classful) moga zawierać w sobie kolejne klasy.
Jeśli klasom wewnetrznym zostana przypisane klasowe algorytmy kolej-

kowania, to również one moga zawierać klasy. Ca przybiera postać
lość
drzewa klas, a klasy z przypisanymi im algorytmami klasowymi sa we-

z w drzewie. Algorytmami klasowymi sa:
lami

1. PRIO
21
2. CBQ
Algorytmy bezklasowe (ang. classless) nie moga zawierać w sobie ko-
lejnych klas. Klasy z przypisanymi im algorytmami bezklasowymi sa
liśćmi w drzewie. Algorytmami bezklasowymi sa:

1. PFIFO FAST, PFIFO, BFIFO
2. TBF
3. SFQ
4. CSZ
5. DSMARK
6. RED, GRED
3.1.1 Algorytmy kolejkowania FIFO
Rysunek 3.1: Algorytmy kolejkowania FIFO
Najprostszy z dostepnych algorytmów kolejkowania to rozwiniecie idei

FIFO (First-In First-Out). W jadrze zaimplementowany jest w trzech wer-

sjach: pfifo fast, pfifo oraz bfifo.
Algorytm kolejkowania pfifo fast jest domyślnym algorytmem kolejkowa-
nia. Oznacza to, że jeśli nie powiazano nowo stworzonej klasy z żadnym

algorytmem kolejkowania, to zostanie użyty pfifo fast. Wia że sie to z nie-

dogodnościa braku prowadzonych statystyk ruchu pakietów. W tej odmianie
22
algorytmu FIFO do trzech podkolejek kierowane sa pakiety o różnych prio-
rytetach. Można sobie wyobrazić ten algorytm kolejkowania jako po aczenie
l

trzech klas, z których każda jest obs
lugiwana przez algorytm pfifo. Kryte-
rium klasyfikacji pakietów jest wartość pola TOS z nag ówka pakietu IP.
l
Pakiety w kolejce o wyższym priorytecie, przyk należace do konwersa-
ladowo

cji interaktywnej (np. telnet), moga być kierowane do kolejki o najwyższym
priorytecie. Pakiety wchodzace w sk transmisji masowych np. FTP kie-
lad

rowane sa do kolejki o najniższym priorytecie, a pozosta ruch pakietów
ly
do pośredniej. Dana kolejka obs l
lugiwana jest wy acznie wtedy, gdy nie ma

już pakietów w kolejkach o wyższych priorytetach. Jeżeli nie można dopuścić
nawet do chwilowego zag
lodzenia kolejek o niższych priorytetach przez ko-

lejki o wyższych priorytetach, to można zastosować zamiast tego algorytmu
kolejkowania algorytm TBF (podsekcja 3.1.3) lub inny kszta ruch pa-
ltujacy

kietów.
Wersje pfifo oraz bfifo to proste mechanizmy kolejkowania bez dodat-
kowych ulepszeń przydatne g ównie w celach statystycznych (domyślny al-
l
gorytm kolejkowania pfifo fast nie udostepnia statystyki ruchu pakietów).

Można zastosować te algorytmy kolejkowania, aby sprawdzić jaki jest gene-
rowanych ruch pakietów i na podstawie wyników obserwacji ustalić strukture

klas ruchu odpowiednia dla danego zastosowania. Algorytmy te przechowy-
wuja wszystkie pakiety w pojedynczej kolejce FIFO. Rozmiar tej kolejki po-
daje sie w pakietach (dla pfifo) lub w bajtach (dla bfifo). Domyślny roz-

miar kolejki jest ustawiany przy aktywacji interfejsu sieciowego (np. dla sieci
Ethernet wynosi 100 pakietów) i może być w każdej chwili odczytany z po-
moca narzedziaifconfig. Jeśli kolejka osiagne maksymalny dopuszczalny
la

rozmiar, to nastepne przychodzace pakiety sa odrzucane.

23
3.1.2 Algorytm kolejkowania PRIO (PRIOrities)
Omawiany algorytm kolejkowania jest uogólniona odmiana algorytmu
pfifo fast. Modyfikacja w stosunku do wspomnianego algorytmu jest zastoso-
wanie traktowanie podkolejek jako niezależnych klas, z których każda może
być skojarzona z innym algorytmem kolejkowania. Klasyfikacja pakietów do
konkretnych podkolejek (ang. bands) może odbywać sie na podstawie naste-

pujacych kryteriów:

" ustawionej opcji gniazdekSO_PRIORITY, która pozwala na ustawianie
bitów TOS w nag ówkach wszystkich pakietów IP wysy z danego
l lanych
gniazdka
" program administrujacy filtrem pakietów IP iptables potrafi ustawić

bity TOS manipulujac bezpośrednio nag ówkami pakietów IP
l

" filtr pakietów, stworzony narzedziem tc, umożliwia bezpośrednie skie-

rowanie wybranych pakietów do danej podkolejki
" odwzorowanie priorytetów (ang. priomap = priorities map) pozwala
na kierowanie pakietów IP na postawie bitów TOS do odpowiedniej
podkolejki
Równie ważnym ulepszeniem tego algorytmu w porównaniu do pfifo fast
jest to, że algorytm jest klasowy. Przek sie to na wieksza elastyczność,
lada

gdyż pozwala klasyfikować pakiety do podkolejek nie tylko na podstawie bi-
tów TOS, ale także z pomoca narzedzia tc. Domyślnie istnieja trzy podkolejki,

do których sa kierowane pakiety z ustawionymi nastepujaco bitami TOS :

0. minimalne opóz
nienie (najwyższy priorytet)
1. maksymalna wiarygodność
24
2. minimalny koszt lub maksymalna przepustowość (najniższy priorytet)
Jeśli ustawionych jest jednocześnie kilka wartości pola TOS, to pakiet kie-
rowany jest do kolejki o najwyższym możliwym priorytecie (np. minimalne
opóz
nienie w po aczeniu z maksymalna przepustowościa kieruje do podko-
l

lejki 0). Można zmienić ilość podkolejek, ale wymusza to również zmiane

odwzorowania priorytetów.
Analogicznie jak w algorytmie kolejkowania pfifo fast pakiety sa pobie-
rane z podkolejek o niższych priorytetach dopiero wtedy, gdy nie ma już
pakietów w podkolejkach o wyższych priorytetach. Może doprowadzić to do
zag
lodzenia kolejek o niższych priorytetach. Najprostszym sposobem unik-

niecia takiej sytuacji jest przyporzadkowanie podkolejkom o wyższych prio-

rytetach algorytmu kolejkowania, który kszta ruch (np. TBF ).
ltuje
3.1.3 Algorytm kolejkowania TBF (Token Bucket Filter)
Rysunek 3.2: Algorytm kolejkowania TBF
25
Opis algorytmu TBF
Algorytm TBF (ang. Token Bucket Filter) przedstawiony na rys. 3.2 na-
leży do klasy algorytmów kszta
ltujacych ruch. Można go opisać korzystajac

z analogii cieknacego kube (ang. leaky bucket). Ruch pakietów regulo-
lka


wany jest z pomoca żetonów (ang. tokens). Pojedynczy żeton odpowiada

pojedynczemu bajtowi, tak wiec ilość żetonów odpowiada rozmiarowi pakietu

w bajtach z uwzglednieniem tego, że najmniejszy pakiet odpowiada pewnej

ilości żetonów. Można tu wyt
lumaczyć faktem, że nawet pakiet nie zawiera-
jacy żadnych danych ma pewien rozmiar (np. w sieciach Ethernet minimalny

rozmiar datagramu zawierajacego pakiet TCP bez danych wynosi 64 bajty).

Żetony magazynowane sa w kube z którego wyciekaja razem z wycho-
lku,


dzacymi pakietami.

Poczatkowo kube jest w pe wype żetonami. Żetony sa genero-
lek lni lniony

wane ze sta a czestotliwościa i sa magazynowane w kube aż do jego ca
l lku, l-

kowitego wype lany
lnienia. Pakiet wychodzacy jest wysy do sieci tylko wtedy,

gdy w danej chwili dostepna jest liczba żetonów odpowiadajaca jego rozmia-

rowi. Jeśli w danej chwili nie jest dostepna wystarczajaca liczba żetonów, to

pakiety sa wstawiane do kolejki o ograniczonej d
lugości. Z chwila, gdy kolejka

pakietów sie wype nowe żetony nie sa przyjmowane do kube dopóki nie
lni, lka

zostanie wys do sieci pierwszy pakiet z kolejki. W sytuacji braku dostep-
lany

nej odpowiedniej ilości żetonów, co uniemożliwia wysy pakietów, urucha-
lanie
miany jest regulator czasowy (ang. watchdog timer), który wznowi transmisje

pakietów po nadejściu wystarczajacej liczby pakietów. Magazynowanie pa-

kietów w kolejce może prowadzić do wystapienia krótkotrwa przecia żeń
lych

ruchu w sieci. W celu zminimalizowania tych przecia żeń korzysta sie z do-

datkowego kube o pojemności jednego pakietu (dok MTU pakietu).
lka ladnie
Pakiety nie sa wypuszczane do sieci z maksymalna predkościa, ale pakiety sa

26
wypuszczane co kwant czasu jadra (ang. jiffie).

Na platformie sprzetowej PC kwant ten równa sie 10ms. Odwrotność

wspomnianego kwantu czasu określa ile kwantów zmieści sie w okresie 1s

i oznacza sie jako HZ. Przyjmujac wiec, że średni rozmiar pakietu wynosi

1000 bajtów, otrzymujemy dok kszta
ladne ltowaniu ruch dla przepustowości
nie przekraczajacych 1Mbit. Można kszta przepustowość na wyższym
ltować
s
poziomie, ale wtedy odbywa sie to kosztem dok
ladności. Korzystajac z ru-

tera programowego opartego o platforme Alpha, można osiagna ć dok
ladne

kszta
ltowanie przepustowości do 10Mbit, ponieważ kwant czasu jadra na tej
s
1
platformie wynosi s.
1024
Algorytm ten umożliwia w prosty sposób przycinanie pasma konkretnego
użytkownika lub grupy użytkowników (np. pod aczenie kilku sieci Fast Ether-
l

net o przepustowości 100Mbit każda do jednego lacza T1 o przepustowości

s
1.5Mbit). ozwala on także na zapobieżenie zag
lodzenia klas o niższych prio-
s
rytetach przez klasy o wyższych priorytetach generujace stale duży ruch.

Wystarczy w takiej sytuacji kszta ruch wychodzacy z klas o wysokich
ltować

priorytetach z pomoca algorytmu TBF.
Formalny opis algorytmu TBF
Niech R oznacza żadana przepustowość, B g ebokość kube a si roz-
l lka,

miary pakietów obs
lugiwanych w chwilach ti. Wtedy ruch pakietów jest
kszta
ltowany zgodnie z oczekiwaniami jeżeli
i=k
"i k i=1 si B + R " (tk - ti)
B
Niech wartość poczatkowa N(ti) wyniesie a przyrost N(t) w czasie
R
można przedstawić jako
N(t + ") = min(B , N(t) + ")
R
27
Jeżeli pierwszy pakiet w kolejce ma d S, to może być wys do sieci
lugość lany
S
jedynie w chwili t", gdy N(t". Wtedy wartość N(t) zmienia sie nastepu-
R
jaco

S
N(t" + 0) = N(t" - 0) -
R
Dodatkowy kube używany do kontrolowania szczytowej przepustowości
lek
(ang. peak rate) P powinien mieć g ebokość M. Można zauważyć, że
l
P > R )" B > M
Dla przypadku, gdy P " wystarczy użyć jeden kube zamiast dwóch.
lek
W trakcie kszta
ltowania ruchu opóz
nienie transmisji pakietów (ang. la-
tency) szacowane jest w sposób nastepujacy

L-M
lat = max(L-B , )
R P
W sytuacji braku żetonów transmisja jest wstrzymywana i uruchamiany
jest regulator czasowy na okres jednego kwantu czasu (zwykle 10ms). Ozna-
czajac czestotliwość odmierzania kwantów czasu przez procesor jako HZ,

a maksymalna przepustowość jako Rmax, można napisać
Rmax = B " HZ
a w konsekwencji można wyznaczyć minimalna wymagana g ebokość kube
l lka

dla zapewnienia żadanej przepustowości

Rmax
B =
HZ
Przyk zależność ta dla sieci Ethernet o przepustowości 100Mbit nak
ladowo lada
s
wymóg, aby kube mia rozmiar co najmniej 128 kilobajtów.
lek l
28
Rysunek 3.3: Algorytm kolejkowania SFQ
3.1.4 Algorytm kolejkowania SFQ (Stochastic Fairness
Queueing)
Ten algorytm kolejkowania jedyne co wykonuje, to szeregowanie pakietów
wychodzacych. W praktyce polega to na opóz
nianiu transmisji wybranych

strumieni pakietów. Strumień pakietów przeważnie jest tożsamy z pojedyn-
cza transmisja TCP. Celem nadrzednym jest zapewnienie sprawiedliwego


podzia dostepnej przepustowości miedzy wszystkie strumienie w sposób jak
lu

najmniej obcia żajacy procesor.

Do ograniczonej liczby kolejek przydzielane sa pakiety. Realizowane jest to
z pomoca funkcji haszujacej, która jest regularnie co ustalony wstepnie okres

czasu (przyk co 10 s) przeliczana w celu zminimalizowania prawdopo-
ladowo
dobieństwa kolizji. Funkcja haszujaca [1] wyznacza numer kube w którym
lka

umieścić pakiet na podstawie nastepujacych parametrów:

" adres z
ród (w postaci liczby 32-bitowej)
lowy
" adres docelowy (w postaci liczby 32-bitowej)
29
" numer protoko transportowego
lu
" wartość ca
lkowita zmieniajaca sie co określony odstep czasu

Pobieranie pakietów z kube opiera sie na algorytmie cyklicznym
lków

round-robin (rys. 3.3). Mechanizm ten może zapewnić równoprawna ob-

s wielu równoleg konwersacji interaktywnych lub zapobiec zdomino-
luge lych

waniu lacza przez jedna konwersacje generujaca duży ruch. Pakiety wysy
lane

sa cyklicznie po jednym z każdego kube dlatego konwersacje sk
lka, ladajace sie

z wiekszej ilości mniejszych pakietów sa wysy najszybciej. Efekty pracy
lane

algorytmu sa widoczne jedynie wtedy, gdy ruch wychodzacy zajmuje ca a
l

dostepna dla niego przepustowość.

Należy podkreślić, ze algorytm ten ma ograniczenia. Do najbardziej wi-
docznych należy ograniczenie ilości kube (1024) oraz pakietów w kube
lków lku
(128). Można to ograniczenie latwo usuna ć zmieniajac kilka sta w kodzie
lych

z
ród jadra [1]. Nastepne ograniczenie wynika z prostoty. Algorytm ten
lowym

nie jest na tyle sprawiedliwy w podziale przepustowości, aby móg zapew-
l

nić wysoka jakość us w domenie DiffServ. Wynika to z oczekiwań jakie
lug
nak sie na wspó lu
lada lczesne algorytmy sprawiedliwego podzia (np. We-


ighted Fair Queueing - WFQ), które dziela dynamicznie strumienie pakietów
do kolejek o zmiennym priorytecie, stosujac jako kryterium podzia ilość
lu

danych przesy danym strumieniem [28]. W ten sposób faworyzowane
lanych
sa krótsze transmisje mniejszych ilości danych.
3.1.5 Algorytmy kolejkowania RED (Random Early Detection)
Protokó transportowy TCP posiada mechanizmy wewnetrzne umożli-
l

wiajace regulowanie szybkości przyjmowania pakietów przychodzacych [11].

Odbywa sie to przez odrzucaniu pakietów, jeśli przychodzi ich za dużo i nie

30
można nada żyć z ich obs Nadawca powinien wtedy zmniejszyć okno
luga.


nadawania pakietów o po czyli nadawać dwa razy mniej pakietów jedno-
lowe,

razowo bez uzyskania potwierdzenia. Mechanizm ten jest prosty i skuteczny,
ale dzia swe zaczyna zbyt póz
no, gdy już dosz do przecia żenia ruchu
lanie lo
w sieci.
Alternatywnym rozwiazaniem problemu jest użycie algorytmów kolejko-

wania RED (ang. Random Early Detection) lub GRED (ang. Generalised
RED). Algorytmy te należa do szerszej rodziny algorytmów wczesnego od-

rzucania (ang. early discard). Pozwalaja one na kszta
ltowanie ruchu wycho-
dzacego poprzez oddzia
lywanie na ruch wchodzacy.

Na podstawie podanych niżej parametrów konfiguracyjnych decyduje sie

o losie pakietu:
" min  minimalna d kolejki przy której pakiet może zostać zna-
lugość
kowany,
" max  d kolejki dla której prawdopodobieństwo znakowania pa-
lugość
kietu jest maksymalne,
" avg  średnia d kolejki,
lugość
" len  bieżaca d kolejki,
lugość

" W  sta czasowa filtru (zmniejszajac ja dopuszcza sie wystepowanie
la

wiekszych przecia żeń w ruchu sieci),

" p  prawdopodobieństwo znakowania pakietów.
Dalszy los pakietu wyglada nastepujaco:

" avg < min : pakiet jest przepuszczany ,
31
" min <= avg < max : pakiet jest znakowany z prawdopodobieństwem
p,
" avg > max : pakiety jest znakowany.
Formalnie zapisuje sie to nastepujaco:

W = 2-n, n " N
maxP = 0.01..0.02
avg = (1 - W ) " avg + w " len
(avg-min)
p = maxP "
(max-min)
Znakowanie pakietu (inaczej kolorowanie pakietu) pozwala na warun-

2
kowe przes pakietu dalej. Jeśli ruter ma w aczona obs ECN , to
lanie l luge

wtedy pakiet jest znakowany i wysy dalej, a w przeciwnym razie pakiet
lany
jest od razu odrzucany. Znakowany pakiet bedzie przesy dalej dopóki
lany

przepustowość sieci bedzie wykorzystywana w niewielkim stopniu. Jeśli wy-

korzystanie przepustowości sieci osiagnie wysoki poziom, to pakiet zostanie

odrzucony.
Odmiana GRED (rys. 3.4) różni sie tym, że tworzy i obs wiek-
luguje

sza ilość kolejek, z których każda charakteryzuje sie innym prawdopodobień-

stwem odrzucenia pakietu. W celu zmniejszenia zapotrzebowania na zasoby
skorzystano z mechanizmu wirtualnych kolejek , polega to na tym, że kolejki

sa tworzone w razie potrzeby zgodnie z rozumowaniem, że kolejka powinna
istnieć jedynie wtedy, gdy znajduja sie w niej pakiety.

Jednym z możliwych zastosowań tego algorytmu kolejkowania jest realiza-
cja algorytmu przekazywania pakietów AF (opisany w rozdziale 2). Algorytm
ten zosta stworzony na potrzeby architektury DiffServ. Wymaga on trzech
l
różnych prawdopodobieństw odrzucania pakietów.
2
ECN (Explicit Congestion Notification) objaśnione w rozdziale 2
32
Rysunek 3.4: Algorytm kolejkowania GRED
Obydwa algorytmy pozwalaja na p
lynniejsza regulacje generacji pakietów

przez z
ród niż gdyby odpowiedzialny by za to jedynie mechanizm TCP.
lo l
Wynika to z tego, że algorytmy RED zaczynaja odrzucać pakiety wcześniej
niż zacznie to czynić protokó TCP. Druga zaleta stosowania tych algorytmów
l
na ruterach jest możliwość wykorzystania w wiekszym stopniu przepustowo-

ści sieci poprzez dopuszczanie do chwilowych przecia żeń. Kolejna zaleta jest
zwiekszenie interaktywności ruchu w sieci poprzez efektywne zmniejszenie


d kolejki.
lugości
3.1.6 Algorytm kolejkowania CBQ (Classful Based Queueing)
Algorytm kolejkowania CBQ to jeden z najbardziej elastycznych algoryt-
mów zawartych w linuksowej implementacji QoS. Elastyczność wynika bez-
pośrednio z jego klasowości (możliwości tworzenia klas wewnetrznych) i dużej

konfigurowalności. Algorytm ten może zarówno kszta ruch wychodzacy
ltować

jak i też szeregować pakiety wychodzace.

Struktura klas tworzona z wykorzystaniem CBQ ma postać odwróconego
drzewa. Na szczycie znajduje sie klasa g ówna (ang. root). Każda z pozo-
l

33
Rysunek 3.5: Algorytm kolejkowania CBQ
sta klas może być wez (ang. node) lub liściem (ang. leaf). Wez
lych lem ly

posiadaja zarówno rodzica jak i potomstwo, a liście posiadaja wy acznie ro-
l

dzica. Klasy majace wspólnego rodzica określane sa jako rodzeństwo (ang.

siblings). Rodzeństwo domyślnie wzajemnie pożycza sobie przepustowości,
ale można to zachowanie wy aczyć. Przeważnie każda klasa ma jawnie zdefi-
l

niowany uchwyt (ang. handle), dzieki któremu można odwo sie bezpo-
lywać

średnio do tej klasy (rodzic i rodzeństwo nie potrzebuja go znać, gdyż znaja
uchwyty generowane automatycznie przez algorytm kolejkowania). Z każda
klasa skojarzony jest algorytm kolejkowania, a jeśli nie zosta żaden jawnie
l
podany, to używany jest algorytm pfifo fast. Każdy weze może dodatkowo
l

posiadać filtr, który przekierowywuje pakiety do odpowiednich klas wśród
potomstwa.
34
Na rys. 3.5 pokazane sa wzajemne relacje miedzy klasami (wraz algoryt-

mami kolejkowania i filtrami), Linuksa oraz zewnetrzna siecia komputerowa.

Na uwage zas mechanizm umożliwiajacy bezpośrednie przesy pa-
luguje lanie

kietów do odpowiednich klas, podczas gdy pobieranie pakietów z klas wy-
maga już pośrednictwa rodziców.
Jadro komunikuje sie wy acznie z klasa g ówna. Pobieranie pakietów z
l l

klas może sie odbywać wy acznie z pośrednictwem rodziców, co jest warun-
l

kiem koniecznym dla dzia mechanizmu kszta
lania ltowania ruchu. Pobieranie
pakietów z klas wykonywane jest wed algorytmu WRR (Weighted Round-
lug
Robin). Algorytm WRR jest drobna modyfikacja algorytmu round-robin ,

polegajaca na przypisaniu różnych wag (priorytetów) każdej klasie. Klasy

o wyższych priorytetach sa sprawdzane w pierwszej kolejności. Wstawianie
pakietów do klas może sie odbywać z pominieciem ich bezpośrednich rodzi-

ców. Polega to na przekierowaniu przez jeden z filtrów po drodze pakietu
bezpośrednio do wybranej klasy. Przekierowywanie pakietów do wybranych
klas odbywa sie przeważnie z pomoca filtrów. Można również klasyfikować

pakiety bezpośrednio w klasach, nak
ladajac maske bitów TOS na pole TOS

z nag ówka pakiety IP.
l
Ogólny algorytm klasyfikowania (przekierowywania) pakietów do poszcze-
gólnych klas przedstawia sie nastepujaco [3]:

1. Sprawdz
filtry przy aczone do bieżacej klasy. Jeśli znajdujesz sie w li-
l

ściu, to skończ, a w przeciwnym wypadku wróć do kroku 1.
2. Na óż maske bitów na bity TOS. Jeśli zgadza sie i znajdujesz sie w wez
le
l

to skończ, a w przeciwnym razie wróć do kroku 1.
3. Wstaw pakiet do bieżacej klasy.

Poza szeregowaniem pakietów algorytm CBQ zajmuje sie również kszta
l-

35
towaniem ruchu wychodzacego. Mechanizm odpowiadajacy za to polega na

obliczaniu bezczynności i odpowiednim wstrzymywaniu ruchu pakietów. Ob-
liczenia przeprowadzane sa w oparciu o podany jako jeden z parametrów
algorytmu kolejkowania średni rozmiar pakietów (zwykle 1000 bajtów). Wy-
znacza sie sta a EWMA (ang. Exponential Weighted Moving Average), która
l

traktuje nowsze pakiety jako ważniejsze od starszych w stopniu wyk
ladni-
czym. Nastepnie od zmierzonego okresu bezczynności lacza sieciowego odej-


mowana jest bezczynność obliczona z użyciem EWMA, po czym jest ona
odejmowana od zmierzonej bezczynności, dajac w wyniku średnia bezczyn-

ność acza sieciowego. Średnia bezczynność lacza sieciowego może przyjmować
l

nastepujace wartości:

" ujemne  acze jest przecia żone ilościa danych (ang. overlimit)
l

" zerowa  acze jest idealnie zrównoważone
l

" dodatnia  lacze jest niedocia żone ilościa danych (ang. underlimit)


W przypadku przecia żenia lacza transmisja pakietów bedzie wstrzymy-


wana na taki okres czasu, aby doprowadzić do zrównoważenia lacza. Nie


można wykonać zrównoważenia obcia żenia lacza z dowolna dok
ladnościa,

gdyż nie jest możliwe ustalenie czasu oczekiwania na transmisje z rozdziel-

czościa wieksza niż pojedynczy kwant czasu zegara (na platformie PC 

10ms). W przypadku niedocia żenia lacza pakiety beda szybciej wysy aż
lane,

do momentu zrównoważenia obcia żenia lacza. W celu zapobieżenia możliwo-


ści wystapienia zbyt dużych chwilowych przecia żeń w ruchu w sieci w trakcie

wyrównywania obcia żenia definiowane jest maksymalna bezczynność acza
l

sieciowego, do którego jest obcinana w dó dowolnie wysoka wyliczona war-
l
tość bezczynności.
36
Przyk
ladowym zainteresowaniem CBQ jako algorytmu kolejkowania jest
architektura DiffServ korzystajaca z us o gwarantowanej jakości (opi-
lugi


sana jako Guaranteed Service w rozdz. 2).
3.1.7 Algorytm kolejkowania DSMARK (DiffServ Mark)
Rysunek 3.6: Algorytm kolejkowania DSMARK
Algorytm kolejkowania DSMARK jest wykorzystywany do realizacji ar-
chitektury DiffServ. Algorytm ten zajmuje sie znakowaniem pakietów wcho-

dzacych do domeny DS. Znakowanie odbywa sie z pośrednictwem filtra pa-

kietów tcindex.
Dzia tego algorytmu przedstawione jest na rys. 3.6. Algorytm opisu-
lanie
jacy jego dzia przedstawia sie nastepujaco:
lanie

1. punkt A: Jeśli ustawiona jest flagaset_tc_index, to odczytywana jest
wartość pola DS (TOS ) z nag ówka pakietu IP, a nastepnie zapisywana
l

jest w polutc_indexstruktury odzwierciedlajacej pakiet. W przeciw-

nym przypadku wpisywana jest do tego pola wartość domyślna uprzed-
nio zdefiniowana.
2. Filtrtcindexna podstawie polatc_indexprzekieruje pakiet do od-
powiedniej klasy
37
3. Pakiet dociera do wewnetrznej klasy, w której obowiazuje wewnetrzny

algorytm kolejkowania (np. pfifo).
4. punkt B: Poletc_indexużywane jest jako indeks umożliwiajacy do-

step do tablicy wartości (maska, wartość). Pierwotna wartość pola DS

mog zostać nadpisana przez wewnetrzny algorytm kolejkowania wiec
la

odtwarzana jest jego poprzednia wartość.
3.1.8 Algorytm kolejkowania CSZ (Clark-Shenker-Zhang)
Algorytm ten zosta opracowany przez trzech autorów, od których na-
l
zwisk wzia sie akronim: Clark-Shenker-Zhang [22]. Jest to najbardziej roz-
l

budowany z dostepnych aktualnie dla Linuksa algorytmów kolejkowania.

Opiera sie on na idei, że konwersacje z różnych klas ruchu sa umiesz-

czane w osobnych kolejkach FIFO+ [22]. Algorytm FIFO+ jest modyfikacja
algorytmu FIFO , uwzgledniajaca czas przyjścia pakietu. Przed wys
laniem

pakietu do nastepnego rutera obliczany jest i zapisywany w nag ówku IP spo-
l

dziewany czas przyjścia do niego. Po osiagnieciu tego rutera porównywany

jest on ze spodziewanymi czasami przyjścia pozosta pakietów z kolejki
lych
i pakiet jest wstawiany do kolejki w odpowiednie miejsce.
Wprowadza sie podzia konwersacji na: gwarantowanej jakości oraz
l


przewidywanej jakości . Pierwsza grupa to konwersacje aplikacji żadaja-


cych niezmiennych parametrów transmisji (nie adaptujacych sie do zmien-

nych parametrów transmisji), a druga to konwersacje aplikacji adaptujacych

sie do zmiennych parametrów transmisji. Do kolejek o wyższych priorytetach

wstawiane sa pakiety konwersacji o gwarantowanej jakości , a do kolejek

o niższych priorytetach pakiety konwersacji o przewidywanej jakości . Do

kolejki o najniższym priorytecie, dzia zgodnie z zasada najlepszego
lajacej


38
wysi trafiaja datagramy, które w ten sposób sa przesy minimalnym
lku , lane
kosztem. Należy jeszcze tylko zadbać o to, aby kolejki o wyższych priorytetach
nie zag ly kolejek o niższych priorytetach. Można w tym celu kszta
lodzi ltować
ruch wychodzacy z kolejek o najwyższych priorytetach z pomoca algorytmu

kolejkowania TBF (podsekcja 3.1.3).
Przyk konfiguracja oparta na algorytmie kolejkowania CSZ poka-
ladowa
zana jest na rys. 3.7.
Aktualnie implementacja tego algorytmu kolejkowania nie jest w pe
lni
funkcjonalna, a w przysz algorytm ten bedzie zastapiony zostanie algo-
lości

rytmem klasy HPFQ (ang. Hierarchical Packet Fairness Queueing). Algo-
rytmy takie potrafia równolegle obs
lugiwać klasy ruchu:
" Guaranteed Service [19]
" najlepszego wysi [4]
lku

" Controlled Load Service [20]
2
Przyk
ladowym algorytmem klasy HPFQ jest algorytm W F Q opisany
w [23].
Rysunek 3.7: Algorytm kolejkowania CSZ
39
3.2 Rodzaje filtrów
Szkielet (ang. framework) konstrukcji filtra pakietów umożliwia tworzenie
filtrów zawierajacych elementy wewnetrzne. Elementem takim przyk
ladowo

może być inny filtr pakietów. Sk filtru rozróżniane sa z pomoca uchwy-
ladowe
tów (ang. handle) 32-bitowych. Uchwyt o numerze 0 odnosi sie do filtru jako

ca Aktualnie żaden ze standardowych filtrów pakietów dostepnych w ja-
lości.

drze nie korzysta z tego mechanizmu zagnieżdżania filtrów.
Filtry pakietów dziela sie na:

" ogólne (ang. generic)  jeden filtr skojarzony z konkretnym algoryt-
mem kolejkowania klasyfikuje pakiety do wszystkich klas ruchu obs
lu-
giwanych przez dany algorytm kolejkowania.
" szczegó (ang. specific)  kilka filtrów skojarzonych z konkretnym
lowe
algorytmem kolejkowania klasyfikuje pakiety do klas ruchu obs
lugiwa-
nych przez dany algorytm kolejkowania.
3.2.1 Filtr route
Linux obs wiele tablic rutingu (domyślnie 256). Standardowo przy
luguje
wyborze trasy pakietów sprawdzane sa wpisy w nastepujacych tablicach

w podanej kolejności:
1. local - znajduja sie w niej trasy dodawane automatycznie przez jadro

przy podnoszeniu interfejsów oraz trasy broadcastowe;
2. main - znajduja sie w niej trasy dodawane przez administratora;

3. default - domyślnie jest pusta.
40
Administrator może dodawać trasy do każdej z wymienionych tablic.
Może także skasować wszystkie tablice z wyjatkiem tablicy local. Możliwe

jest również tworzenie nowych tablic rutingu i dodawanie do nich tras.
Dodatkowe możliwości stwarza użycie rutingu rozszerzonego (ang. po-

licy routing). Możliwe jest wtedy podejmowanie decyzji o rutingu na podsta-
wie nastepujacych parametrów:

" adresu z
ród
lowego
" protoko sieciowego (np. IP)
lu
" portu protoko transportowego (np. port 80 TCP)
lu
" wartości pola TOS z nag ówka IP
l
" wejściowego interfejsu sieciowego (np. ppp0)
" wartości pola ustawianego w pakiecie przez firewall
Ostatnie kryterium rutowania pakietów pozwala w praktyce na rutowanie
wg zawartości dowolnego pola nag ówków warstwy sieciowej lub transporto-
l
wej, a nawet zawartości pola danych pakietu. Wykorzystywany do tego jest
3
mechanizm znakowania pakietów przez narzedzie iptables . Znakowanie po-

lega na wpisywaniu dowolnej liczby sta
loprzecinkowej 32 bitowej bez znaku
do dodatkowego pola struktury reprezentujacej każdy pakiet IP.

Każda trasa w tablicy rutingu może mieć przypisana klase do której trafia

pakiety kierowane wzd tej trasy. Trase z klasa można skojarzyć na dwa
luż

sposoby. Można to osiagna ć przez wpisanie trasy do jednej z tablic rutingu

lub przez zdefiniowanie dziedziny rutujacej (ang. realm). Nastepnie przy de-

finiowaniu filtra można wskazać na wybrana tablice lub dziedzine rutujaca

jako na z
ród pakietów do filtrowania.
lo
3
Filtr fw (podsekcja 3.2.2) korzysta jawnie z tego mechanizmu
41
Poniższy przyk pokazuje zastosowanie filtra route. Wszystkie pakiety
lad
adresowane do podsieci192.168.10/24z pośrednictwem rutera o adresie
192.168.10.1wychodzace interfejsem sieciowymeth1sa kierowane do klasy

o identyfikatorze1:10. Elementem laczacym w tym przyk jest dziedzina
ladzie

rutujaca o identyfikatorze10.

# ip route add 192.168.10/24 via 192.168.10.1 dev eth1 realm 10
# tc filter add dev eth1 parent 1:0 protocol ip prio 100 \
route to 10 classid 1:10
Najwieksza zaleta tego filtra wynikajaca z jego prostoty jest duża szybkość

dzia
lania
3.2.2 Filtr fw
Kolejny rodzaj filtru korzysta z możliwości znakowania pakietów, stad

pochodzi jego nazwa fw (skrót terminu firewall). Filtr ten potrafi przekiero-
wać pakiety do zdefiniowanych klas na podstawie wartości 32 bitowej liczby
sta
loprzecinkowej bez znaku wpisanej uprzednio do struktury przedstawia-
jacej pakiet. Do wpisywania wspomnianej liczby s narzedzie konfiguracji
luży

firewalla  iptables.
Jako demonstracje możliwości tego elastycznego filtra pokazano niżej za-

bezpieczenie serwera przed atakiem DoS polegajacym na przesy do niego
laniu

dużej ilości pakietów z ustawiona flaga TCP SYN(rozpoczynajacych po acze-
l

nie TCP) w celu doprowadzenia do przecia żenia serwera, a w konsekwencji
unieruchomienia go.
Pakiet z ustawiona flaga TCP SYNma wielkość 40 bajtów (320 bitów), tak
wiec w przybliżeniu trzy takie pakiety maja lacznie wielkość 1 kb. Ustawiajac


limit przepustowości dla pakietów z ustawiona flaga TCP SYNna 1 kb, akcep-
tujemy nie wiecej niż trzy próby nawiazania po aczenia w każdej sekundzie.
l

42
W tym celu znaczymy każdym przychodzacy interesujacym nas interfejsem

sieciowyeth0pakiet wartościa 1. Nastepnie wszystkie uprzednio znaczone

pakiety podlegaja kszta
ltowaniu ruchu i nadmiarowe pakiety sa odrzucane.
# iptables -A PREROUTING -i eth0 -t mangle -p tcp --syn -j MARK \
--set-mark 1
# tc filter add dev eth0 parent ffff: protocol ip prio 50 \
handle 1 fw police rate 1kbit burst 40 mtu 9k drop flowid :1
G ówna zaleta tego filtra jest jego elastyczność polegajaca na możliwości
l

wykorzystania wszystkiego co oferuje architektura netfilter, z której korzysta
narzedzie konfiguracji firewalla iptables. Jednocześnie można uaktywnić 256

niezależnych filtrów fw.
3.2.3 Filtry rsvp i rsvp6
Filtr rsvp umożliwia klasyfikacje pakietów zgodnie z ich przynależnościa

do odpowiednich strumieni IntServ. Klasyfikacja jest przeprowadzana na pod-
stawie nastepujacych parametrów:

" protokó warstwy sieciowej (np. TCP)
l
" adres docelowy IP
4
" port docelowy TCP lub GPI
" adres z
ród IP lub maska adresów IP (opcjonalnie)
lowy
4
W przypadku korzystania z tunelów IP w celu szyfrowania przesy danych zacho-
lania
dzi potrzeba odczytania z nag ówka pakietu TCP numerów portu z
ród i docelowego.
l lowego
Nag ówek TCP zostaje póz
niej zaszyfrowany, wiec informacje te zapisuje sie w nag ówku
l l

GPI (ang. Generalised Port Identifier) [27], który dopisywany jest za nag ówkiem IP, a
l
przed nag ówkiem TCP.
l
43
" port z
ród IP lub etykieta przep (opcjonalnie i dozwolone tylko
lowy lywu
jeśli podano adres z
ród IP lub maske adresów)
lowy

W poniższym przyk wszystkie pakiety TCP przychodzace z adresu
ladzie

192.168.0.10i adresowane do192.168.0.1zostana przyporzadkowane do

klasy1:2. Zapewnieniem odpowiedniej jakości transmisji zajmie sie algorytm

kolejkowania z klasy1:2i nadrzedne.

# tc filter add dev eth0 parent 1:0 protocol ip prio 10 rsvp ipproto tcp \
sender 192.168.0.10 session 192.168.1.1 classid 1:2
Zastosowania filtru rsvp, podobnie jak protoko sygnalizacyjnego RSVP,
lu
nie sa ograniczone wy acznie do architektury IntServ. Protokó sygnaliza-
l l

cyjny RSVP nie jest zależny od konkretnego protoko sieciowego, dlatego
lu
też wspó
lpracuje zarówno z IPv4 jak i IPv6. W przypadku korzystania z pro-
toko IPv6 należy wywo ten filtr, podajac nazwe rsvp6. Jednocześnie
lu lywać

można uaktywnić 256 niezależnych filtrów rsvp.
3.2.4 Filtr tcindex
Nazwa tego filtru, sk
ladajaca sie z dwóch cześci tc (ang. Traffic Control)

oraz index, nawiazuje do architektury DiffServ. W architekturze DiffServ po-

dzia pakietów na klasy ruchu (w tej implementacji tożsamych z klasami)
l
dokonywany jest na podstawie wartości pola DS. Pole to tożsame jest z po-
lem TOS w nag ówku IPv4 oraz polem TC w nag ówku IPv6. Wartość tego
l l
pola przechowywana jest dodatkowo w polutcindexstruktury reprezentu-
jacej każdy pakiet.

W przypadku używania algorytmu kolejkowania dsmark wartość DS może
być automatycznie wczytana do zmiennejtcindex. Można też wymusić z po-
moca odpowiedniego parametru wywo wpisanie uprzednio zdefiniowanej
lania
44
domyślnej wartości do zmiennejtcindex. Jeśli nie skorzysta sie z żadnej z

wymienionych metod, należy przypisać wartość zmiennejtcindexw inny
sposób, aby unikna ć niejednoznaczności interpretacji.
W poniższym przyk opcjaset_tc_indexużyta w pierwszym po-
ladzie
leceniu nakazuje algorytmowi kolejkowania dsmark odczytać zawartość pola
TOS i wczytać ja do zmiennejtcindex. W drugim poleceniu na wartość
zmiennejtcindexnak jest maska logiczna0xfc, a nastepnie wynik
ladana

przesuwany jest o dwa bity w prawo. W ten sposób pomija sie bity ECN.

# tc qdisc add dev eth0 handle 1:0 root dsmark indices 64 \
set_tc_index
# tc filter add dev eth0 parent 1:0 protocol ip prio 1 \
tcindex mask 0xfc shift 2
Filtr może być wykorzystywany do różnych celów, nie tylko w po aczeniu
l

z algorytmem kolejkowania dsmark.
3.2.5 Filtr u32
Nazwa tego najbardziej elastycznego filtra pochodzi od formatu nag ów-
l
ków protoko ów warstw sieciowej i transportowej, które sk sie z wie-
l ladaja
lokrotności s 32 bitowego. Filtr ten może przyjmować jako kryterium
lowa
klasyfikacji pakietów do odpowiednich klas dowolne pola z nag ówków war-
l
stwy sieciowej (IPv4, IPv6 ) lub transportowej (TCP, UDP). Wartości wspo-
mnianych pól moga być sprawdzane zarówno z użyciem nazw symbolicznych
(np.ip dst 192.168.0.1) lub maskowania logicznego jednego, dwóch lub
czterech kolejnych bitów nag ówka (np.match u8 64 0xff at 8).
l
Pierwszy przyk prezentujacy możliwości omawianego filtra pokazuje
lad

przekierowanie do klasy1:0wszystkich pakietów posiadajacych pole TOS z

nag ówka IP ustawione na wartość0x10(minimalizacja opóz
nienia).
l
45
# tc filter add dev eth0 parent 1:0 protocol ip prio u32 \
match ip tos 0x10 0xff flowid 1:1
Nastepny przyk jest demonstracja filtrowania pakietów wzgledem war-
lad

tości pola TTL z nag ówka IP. Pakiety, których czas życia (TTL) wynosi
l

1, sa kierowane do oddzielnej klasy. W tym celu na dziewiaty bajt nag ówka
l

IP (przesuniecie o osiem bajtów) nak jest maska0xff, a wynik po-
ladana

równywany jest z oczekiwana wartościa TTL.
# tc filter add dev eth0 parent 1:0 protocol ip prio 10 u32 \
match u8 1 0xff at 8 flowid 1:1
Ostatni przyk zastosowania tego filtru sk sie z trzech selektorów.
lad lada

Selektorem nazywa sie pojedynczy warunek. Spe wszystkich na
lnienie lożo-

nych warunków (iloczyn logiczny) jest konieczne, aby filtr przekierowa pakiet
l
do odpowiedniej klasy. Pierwszy selektor sprawdza, czy pakiet przyszed z ad-
l
resu192.168.0.2. Nastepny selektor sprawdza, czy pakiet IP zawierajacy

ten pakiet ma wielkość dok
ladnie40bajtów. Ostatni z selektorów sprawdza,
czy w pakiecie jest ustawiona flagaTCP SYN.
# tc filter add dev eth0 parent 1:0 protocol ip prio 10 u32 \
match ip src 192.168.0.2 \
match u8 0x28 0xff at 3 \
match u8 0x10 0xff at nexthdr+13
3.3 Zastosowanie algorytmów kolejkowania i filtrów
W rzeczywistych zastosowaniach użycie pojedynczego algorytmu kolejko-
wania dla jednej klasy, do której parametry przydziela jeden filtr jest nie-
wystarczajace. Konstruuje sie wtedy hierarchie klas, korzystajac z różnych

algorytmów kolejkowania i filtrów.
46
Przyk rozbudowana struktura QoS przedstawiona jest na rys. 3.8.
ladowa
Na rysunku można zobaczyć zastosowanie filtrów pakietów u32 (podsekcja
3.2.5) oraz algorytmów kolejkowania SFQ (podsekcja 3.1.4), PRIO (podsek-
cja 3.1.2), TBF (podsekcja 3.1.3)oraz CBQ (podsekcja 3.1.6).
47
Rysunek 3.8: Przyk hierarchia klas
ladowa
48
Rozdzia 4
l
Możliwości rozbudowy
implementacji QoS w systemie
Linux
Dzieki elastycznej i modularnej budowie Linuksa można zmienić kod stan-

dardowych algorytmów kolejkowania lub filtrów adaptujac je do swych po-

trzeb. Można również napisać w filtry lub algorytmy kolejkowania, które
lasne
póz
niej można skompilować jako modu dynamiczne i w razie potrzeby za-
ly

ladować do jadra systemu Linux.

W rozdziale tym nacisk jest po na budowe wewnetrzna algorytmu
lożony

kolejkowania oraz filtru, co u potencjalnym zainteresowanym napisanie
latwi
w
lasnego algorytmu kolejkowania lub filtru, badz
też zaimplementowanie pod

system Linux algorytmu kolejkowania lub filtru już opracowanego teoretycz-
nie.
49
4.0.1 Opis ogólny
Implementacja sterowania ruchem (ang. traffic control) w z
ród Li-
lach
nuksa rozdzielona jest na kod elementów sterowania ruchem (pliki z
ród
lowe
w jezyku C) oraz na interfejs dostepu do tych elementów (pliki nag ów-
l

kowe w jezyku C). Jedynym wyjatkiem od tej zasady jest implementacja

filtrów rsvp wraz z rsvp6, która umiejscowiona jest w wiekszości w poje-

dynczym pliku nag ówkowym. Wszystkie wymienione niżej nazwy katalogów
l
i plików sa podawane wzgledem g ównego katalogu ze z
ród znajdujacego
l lami

sie w /usr/src/linuxchyba że jawnie napisano inaczej.

Komunikacja miedzy elementami sterowania ruchem dzia
lajacymi w try-

bie jadra a programami administracyjnymi dzia
lajacymi w trybie użyt-

kownika zapewnia mechanizm rtnetlink [3]. Mechanizm ten jest od-
miana ogólnego mechanizmu netlink wyspecjalizowana pod katem ob-

s protoko sieciowego IP. Implementacja obydwu wspomnianych me-
lugi lu
chanizmów znajduje sie odpowiednio w podkatalogu net/netlink oraz

pliku net/core/rtnetlink.c, z kolei interfejs jest umieszczony w na-
stepujacych plikach nag ówkowych: include/linux/netlink.horazinc-
l

lude/linux/rtnetlink.h.
Administrator systemu kontroluje sterowanie ruchem z pomoca zewnetrz-

nego programu tc. Program ten jest cześcia sk pakietu iproute, s
ladowa luża-

cego m. in. do sterowania rutingiem rozszerzonym. Cześć dotyczaca stero-

wania ruchem znajduje sie w podkataloguiproute2/tcz
róde [2]. Program
l

ten pozwala na manipulowanie wybranymi elementami sterowania ruchem.
Implementacja obs mechanizmów sterowania ruchem sk sie z dwóch
lugi lada

cześci:

" obs algorytmów kolejkowania i klas ruchu  pliki q_ np. plik
lugi
q_tbf.codpowiada za obs algorytmu kolejkowania TBF (podsek-
luge

50
cja 3.1.3),
" obs filtrów pakietów  plikif_np. plikf_u32.codpowiada za ob-
lugi
s filtru pakietów u32 (podsekcja 3.2.5).
luge

Jako komunikacje miedzy elementami sterowania ruchem a programami

dzia
lajacymi w trybie użytkownika traktuje sie komunikacje miedzy progra-

mem tc a konkretnymi klasami ruchu, algorytmami kolejkowania oraz filtrami
pakietów.
Implementacja mechanizmów sterowania ruchem w systemie Linux jest
integralna cześci obs sieci komputerowych. Sk sie ona z nastepujacych
lugi lada

cześci:

" plików z
ród
lowych (podkatalognet/sched) nastepujacych elementów

podstawowych:
 algorytmów kolejkowania i klas  pliki sch_ np. plik
sch_dsmark.czawiera kod z
ród implementacji algorytmu ko-
lowy
lejkowania DSMARK (podsekcja 3.1.7),
 filtrów pakietów  plikicls_np. plikcls_tcindexzawiera kod
z
ród implementacji filtra tcindex (podsekcja 3.2.4).
lowy
" plików nag ówkowych zawierajacych:
l

 interfejs pośredniczacy miedzy elementami sterowania ruchem

a programami dzia
lajacymi w trybie użytkownika  inc-

lude/net/pkt_sched.h(algorytmy kolejkowania i klasy) orazin-
clude/net/pkt_cls.h(filtry pakietów),
 deklaracje używane tylko wewnatrz jadra i programy dzia
lajace

w trybie jadra  include/linux/pkt_sched.h(algorytmy ko-

51
lejkowania i klasy) orazinclude/linux/pkt_cls.h(filtry pakie-
tów).
4.0.2 Opis implementacji algorytmów kolejkowania
Implementacja nowego algorytmu kolejkowania o przyk
ladowej nazwie foo
w uproszczeniu sk sie z nastepujacych kroków:
lada

1. Stworzenie plikufoo_sch.cw podkatalogunet/sched/.
2. Zdefiniowanie strukturyfoo_sched_dataprzechowywujacej informacje

pomocnicze dla dzia danego algorytmu kolejkowania (np. maksy-
lania
malne d kolejek wewnetrznych).
lugości

3. Zdefiniowanie strukturyfoo_schedprzechowujacej informacje wspó
l-

dzielone przez wszystkie równolegle wykorzystywane instancje danego
algorytmu kolejkowania oraz zawierajacej w sobie tablice, której ele-

menty maja postać strukturyfoo_sched_data.
4. Napisanie kodu nastepujacych funkcji:

foo_init inicjalizuje i wstepnie konfiguruje algorytm kolejko-

wania (na podstawie parametrów przekazanych programem tc)
foo_enqueue wstawia pakiet do kolejki w klasie. Jeśli wewnatrz

klasy znajduja sie kolejne klasy, to funkcja ta jest wywo
lywana ponow-

nie dla klasy wewnetrznej.

foo_dequeue zwraca oraz usuwa pakiet z kolejki do wys
lania.
Jeśli w kolejce nie ma pakietów lub nie można ich wys to zwracany
lać,
jest pusty wskaz
nikNULL.
foo_requeue wstawia z powrotem pakiet do kolejki po uprzed-
nim usunieciu go przez funkcjefoo_dequeue. Pakiet musi być wsta-

52
wiony z powrotem na to samo miejsce w kolejce, z którego zosta wcze-
l
śniej usuniety.

foo_drop usuwa jeden pakiet z końca kolejki.
foo_change zmienia konfiguracje algorytmu kolejkowania (na

podstawie parametrów przekazanych programem tc).
foo_dump zwraca informacje diagnostyczne przydatne dla ad-
ministratora. Zwyczajowo zwracane sa parametry konfiguracyjne oraz
wartości zmiennych stanu (np.foo_sched).
foo_reset przywraca poczatkowa konfiguracje algorytmu ko-

lejkowania. W tym celu wszystkie kolejki sa opróżniane, a regulatory
czasowe sterujace wysy pakietów sa zatrzymywane.
laniem

foo_destroy usuwa algorytm kolejkowania wraz ze wszystkimi
podrzednymi klasami ruchu wraz ze skojarzonymi algorytmami kolejko-

wania oraz filtrami, a wszystkie pakiety z tych kolejek sa odrzucane>.
Klasa zawierajaca ten algorytm kolejkowania pozostaje nienaruszona.

5. Wpisanie nazw wymienionych wyżej funkcji do strukturyQdisc_ops.
6. Jeśli nowy algorytm kolejkowania foo ma istnieć w postaci dynamicz-
nego modu jadra, to należy wykonać co nastepuje:
lu

(a) napisać funkcje inicjalizujaca modu (wykonywana po jego za
l la-

dowaniu przez jadro) i rejestrujaca go w jadrze  init_module

(b) napisać funkcje wywo ladowaniem modu
lywana tuż przed wy lu

przez jadro i wyrejestrowywujaca go z jadra  cleanup_module

(c) zapewnić inkrementacje licznika zabezpieczajacego przez wy-

lu
ladowaniem używanego modu z pomoca makrodefinicji
53
MOD_INC_USE_COUNT w funkcji foo_init, czasem również
wfoo_change
(d) zapewnić dekrementacje licznika zabezpieczeczajacego przed

wy lu
ladowaniem używanego modu z pomoca makrodefinicji
MOD_DEC_USE_COUNTw funkcjifoo_destroy
7. Jeśli nowy algorytm kolejkowania foo ma istnieć w postaci kodu wkom-
pilowanego statycznie w jadro, to należy wykonać co nastepuje:

(a) umieścić deklaracje dotyczace tego algorytmu kolejkowania do-

stepne tylko dla jadra w plikuinclude/net/pkt_sched.h

(b) umieścić interfejs pośredniczacy w komunikacji miedzy tym algo-

rytmem kolejkowania a programami dzia
lajacymi w trybie użyt-

kownika (np. tc) w plikuinclude/linux/pkt_sched.h
(c) umieścić kod z
ród algorytmu kolejkowania w pliku
lowy
net/sched/sch_foo.c
(d) zainicjować algorytm kolejkowania w funkcjipktsched_initznaj-
dujacej sie w plikunet/sched/sch_api.c

8. Należy zmodyfikować z
ród programu tc w sposób nastepujacy:
la

(a) stworzyć plikq_foo.c
(b) zdefiniować nastepujace funkcje:

" foo_parse_opt sprawdza poprawność podanych parame-
trów wywo a nastepnie przekazuje je algorytmowi kolej-
lania,

kowania
" foo_print_opt wypisuje aktualna konfiguracje algorytmu

kolejkowania
54
" foo_print_xstats wypisuje statystyki algorytmu kolejko-
wania
" explain wypisuje pomoc odnośnie parametrów przekazy-
wanych algorytmowi kolejkowania
(c) wpisać nazwy powyższych funkcji do strukturyqdisc_util
(d) skompilować poprawiona wersje programu tc

9. Kompilacji jadra, a nastepnie uruchomienia systemu operacyjnego pod

kontrola nowego jadra.

10. Jeśli algorytm kolejkowania istnieje w postaci modu to należy go
lu,
za
ladować do jadra z pomoca programu modprobe.

11. Skonfigurować sterowanie ruchem z pomoca programu tc.
4.0.3 Opis implementacji klas ruchu
Opis implementacji nowych klas w programie tc nie różni sie zasadni-

czo od implementacji nowych algorytmów kolejkowania, wiec w podsekcji tej

omówione zostana jedynie niezbedne zmiany w z
ród jadra.
lach

Implementacja nowej klasy o nazwie foo wyglada podobnie jak imple-

mentacja nowych algorytmów kolejkowania (podsekcja 4.0.2). Inne sa tylko
funkcje, które należy napisać i umieścić w plikufoo_sch.cznajdujacym sie

w podkatalogunet/sched. Wymagane sa nastepujace funkcje:

" foo_graft do acza nowy algorytm kolejkowania do klasy
l

" foo_get wyszukuje klase na podstawie jej identyfikatora i zwraca

jej wewnetrzny identyfikator. Jeśli klasa posiada w licznik odwo
lasny lań

do niej, to powinien zostać zwiekszony o jeden.

55
" foo_put zmniejsza licznik odwo do tej klasy, jeśli dana klasa go
lań
posiada. Jeśli licznik ten osiagnie zero, to klasa zostanie usunieta.

" foo_change_class zmienia konfiguracje bieżacej klasy (na podsta-

wie parametrów przekazanych programem tc).
" foo_delete usuwa bieżaca klase. Jeśli klasa posiada w licz-
lasny

nik odwo do niej, to jest on dekrementowany, a klasa jest usuwana
lań
wy acznie wtedy, gdy osiagnie on zero.
l

" foo_walk iteracyjnie wywo wszystkie funkcje zwrotne (ang. cal-
luje
lback) skojarzone z klasami wewnetrznymi. Przyk funkcje takie
ladowo

moga zwracać informacje diagnostyczne o klasach.
" foo_leaf zwraca wskaz
nik do klasy jeśli jest ona liściem drzewa
klas. W przeciwnym przypadku zwracany jest pusty wskaz
nikNULL.
" foo_dump zwraca dane diagnostyczne dotyczace bieżacej klasy.

Cześć implementacji dotyczaca zmian w programie tc jest dok taka
ladnie

sama jak w przypadku implementacji nowego algorytmu kolejkowania.
4.0.4 Opis implementacji filtrów pakietów
Proces implementacji nowego filtru o nazwie foo sk sie z nastepuja-
lada

cych kroków:
1. Napisanie poniższych funkcji:
" foo_init inicjalizuje filtr.
56
1
" foo_classify dokonuje klasyfikacji pakietu .
" foo_get szuka filtru o podanym identyfikatorze i zwraca jego
wewnetrzny identyfikator.

" foo_put sprawdza czy bieżacy filtr jest używany, a jeśli nie

jest, to usuwa go.
" foo_change zmienia konfiguracje filtra.

" foo_walk wywo funkcje zwrotne wszystkich elementów fil-
luje
tra.
" foo_dump zwraca informacje diagnostyczne dotyczace bieżacego

filtru.
" foo_delete usuwa wskazany element sk
ladowy filtra.
" foo_destroy usuwa filtr.
2. Wpisanie nazw tych funkcji do strukturytcf_proto_ops.
3. Należy zmodyfikować z
ród programu tc w sposób nastepujacy:
la

(a) stworzyć plikq_foo.c
(b) zdefiniować nastepujace funkcje:

" f_foo_parse_opt sprawdza poprawność podanych para-
metrów programu i przekazuje je filtrowi pakietów.
" f_foo_print_opt wyświetla aktualna konfiguracje filtra

pakietów.
(c) skompilować poprawiona wersje programu tc.

1
Dozwolonymi wynikami klasyfikacji sa: TC_POLICE_OK (pakiet zostanie przepusz-

czony), TC_POLICE_RECLASSIFY (pakiet bedzie powtórnie klasyfikowany, gdyż prze-

kroczy dopuszczalny limit przepustowości), TC_POLICE_SHOT (pakiet zostanie odrzu-
l
cony) oraz TC_POLICE_UNSPEC (pakiet zostanie odrzucony lub traktowany jako ruch
niskopriorytetowy)
57
Rozdzia 5
l
Badania wykonane bez
w aczonych mechanizmów QoS
l

5.1 Cel badań
Badania polega na zmierzeniu wp różnych czynników (pośrednic-
ly lywu
two rutera w transmisji danych, transmisje FTP wykonywane w tle, druga
transmisja interaktywna wykonywana w tle) na zmienność opóz
nienia w prze-
kazywaniu pakietów IP (ang. jitter). Sk ly sie z dwóch grup badań. Bada-
lada

nia z pierwszej grupy zosta wykonane bez w aczonych mechanizmów QoS.
ly l

W pierwszej grupie znalaz sie pomiary opóz
nień w transmisjach bezpośred-
ly

nich oraz w transmisjach przez nieobcia żony ruter. Na druga grupe z ly
loży

sie pomiary dokonane w sytuacjach, gdy ruter poza interesujaca transmisja

obcia żany by dodatkowymi transmisjami (transmisja interaktywna  echo
l
oraz transmisje FTP).
58
5.2 Sprzet użyty w badaniach

Stanowisko badawcze (rys. 5.1) sk lo sie z nastepujacych elementów:
lada

" ruter programowy (komputer PC oznaczony na rysunkach symbo-
lem R),
" cztery końcówki klienckie (komputery PC oznaczone cyframi
1, 2, 3 i 4).
Rysunek 5.1: Stanowisko badawcze
Jako ruter programowy wykorzystano komputer klasy PC wyposażony
w procesor Intel Pentium 75, pamieć operacyjna wielkości 48 MB oraz cztery

karty sieciowe Thick Ethernet (100 Mbit). Komputer pracowa pod kon-
l

trola systemu GNU/Linux Debian 3.0. Dodatkowo skompilowano specjalnie
pod posiadany sprzet jadro w wersji 2.4.18. Ruter z końcówkami klienckimi

po aczono okablowaniem sieciowym typu skretka kategorii 5.
l


Jako końcówki klienckie użyto cztery komputery klasy PC. Każdy z nich
posiada procesor Intel Pentium III 733, pamieć operacyjna wielkości 64 MB
l

oraz pojedyncza karte sieciowa o przepustowości 100 Mbit. Komputery pra-

cowa pod kontrola systemu RedHat Linux w wersji 7.2. Również dla nich
ly
specjalnie skompilowano jadro w wersji 2.4.18. Użycie tego samego jadra

59
na wszystkich komputerach oraz wy aczenie nieużywanych demonów siecio-
l

wych (np. serwera poczty) zniwelowa wp poszczególnych dystrybucji
lo lyw
na prowadzone pomiary.
5.3 Opis oprogramowania testujacego

W celu wykonania obliczeń niezbedne jest zmierzenie opóz
nienia (czasu)

przekazywania pakietów IP. Należy również dok zmierzyć chwilowe,
ladnie
średnia i krańcowe wartości przepustowości. Można to wykonać na wiele spo-
sobów. Ogólnie mówiac, można dokonać pomiarów w trybie użytkownika

(ang. user mode) lub w trybie jadra (ang. kernel mode).

W uproszczeniu można powiedzieć, że tryb jadra to uprzywilejowany tryb

dostepu do procesora. Proces dzia w tym trybie może uczynić wszystko
lajacy

co umożliwia architektura sprzetowa na której jest wykonywany. Proces dzia-


lajacy w tym trybie nie jest ograniczany przez prawa dostepu do plików oraz

może zarówno odczytywać jak i zapisywać dane do przestrzeni adresowej in-
nych procesów. Proces taki może być uruchomiony jedynie przez administra-
tora danego komputera. W tym trybie dzia watki jadra (ang. kernel
laja

threads) oraz dynamiczne modu jadra. Jako watki jadra określa sie frag-
ly

menty jadra pracujace niezależnie od siebie. Przyk
ladowym watkiem jadra

jest watek obs przerwań programowych. Natomiast dynamiczne modu
lugi ly

jadra to programy niezależne programy, które moga być w aczane i wy a-
l l

czane w trakcie pracy systemu operacyjnego. Moga one również przyjmować
parametry wywo Przyk zastosowanie dla modu ów to sterowniki
lania. ladowe l
urzadzeń zewnetrznych np. kart sieciowych w technologii Ethernet.

Z kolei trybem użytkownika określa sie nieuprzywilejowany tryb dostepu

do procesora. Proces dzia w tym trybie podlega restrykcjom dotyczacy
lajacy

60
dostepu jedynie do w przestrzeni adresowej pamieci oraz jedynie do
lasnej

tych plików, których prawa dostepu na to pozwalaja. Wszystkie programy

uruchamiane przez zwyk użytkowników oraz cześć programów urucha-
lych

miana przez użytkowników pracuje w tym trybie. Przyk edytor tekstu,
ladowo
w którym napisana zosta niniejsza praca, pracowa w trybie użytkownika.
la l
5.3.1 Zasadność pomiarów w trybie użytkownika
Przyk lajacym w trybie użytkownika jest wy-
ladowym rozwiazaniem dzia

korzystanie do pomiaru programu pods
luchujacego ruch w sieci komputero-

wej (ang. sniffer). Należy uruchomić kilka instancji takiego programu (np.
tcpdump), po jednej na każdy interesujacy nas interfejs sieciowy. Pojawia sie

wtedy poważny problem zwiazany z szeregowaniem procesów przez jadro, nie

można w latwy sposób zagwarantować, że pomiary czasu dokonywane przez

nas ladne.
luchujace programy beda bardzo dok Wynika to z tego, że jadro

przydziela każdemu procesowi przez który ma dostep do procesora i po up
ly-

wie jego proces zostaje wyw
laszczony, nie wiadomo wiec czy pakietowi A,

który pojawi sie w ruterze przed pakietem B, zostanie przypisany czas nadej-
l

ścia wcześniejszy niż pakietowi B. Problem można rozwiazać, uruchamiajac

system Linux na maszynie wieloprocesorowej tak, aby każda instancja pro-
gramu nas la
luchujacego pracowa na oddzielnym procesorze, co w dostepnych

warunkach laboratoryjnych by niemożliwe. Dodatkowym minusem podej-
lo
ścia opartego na programach uruchamianych przez użytkownika jest mniejsza
dok
ladność niż to możliwe w trybie jadra. Programy takie moga odczytać czas

systemowy z rozdzielczoÅ›cia 1µs(10-6), czyli znacznie mniej niż czestotliwość

taktowania wspó
lczesnych procesorów. Ograniczenie to narzucone jest przez
biblioteke standardowa jezyka C i zwiazane jest z postulatem przenośności

(na poziomie z
ród oprogramowania napisanego w jezyku C.
la)

61
5.3.2 Zasadność pomiarów w trybie jadra

Alternatywne podejście, czyli dokonanie pomiarów w trybie jadra, można

zrealizować na dwa sposoby. Pierwszym z nich jest zmodyfikowanie z
róde ja-
l

dra i zapisanie zmian w stosunku do orygina w pliku latce (ang. patch).
lu

Korzystajac póz
niej z tego pliku można szybko uzyskać zmodyfikowane jadra

z oryginalnego jadra. Drugim sposobem osiagniecia celu jest napisanie mo-

du jadra, który można za ladować dynamicznie w trakcie pracy
lu ladować i wy

systemu Linux. Modu taki może w trakcie ladowania przyjmować parametry
l
wywo podobnie jak zwyk program. Po za l
lania ly ladowaniu modu traktowany
jest jako integralna cześć jadra. Istotne jest również to, iż raz napisany mo-

du można używać z póz
niejszymi wersjami systemu Linux. W przypadku
l
poprawek bezpośrednio w jadrze, można spodziewać sie konieczności ich mo-

dyfikacji, aby dostosować zmiany do nowszych wersji jadra.

Mierzac czasy nadejścia pakietów z poziomu jadra można uzyskać po-

miary z dok
ladnościa do pojedynczego cykniecia zegara procesora. Przy-

k
ladowo posiadajac ruter z procesorem o czestotliwości 1GHz, osiagamy

rozdzielczość czasu 1ns(10-9). Negatywnymi stronami omawianego podej-
ścia sa nieprzenośność oraz potencjalna niestabilność. Nieprzenośność wia że
sie z faktem, że odczyt czasu nastepuje z rejestru TSC, który wystepuje

w procesorach Intela od modelu Pentium. Nie jest to dużym problemem,
gdyż wszystkie obecnie dostepne na rynku procesory klasy x86 posiadaja

ten rejestr (zak że nie korzysta sie z innych architektur procesorów
ladam,

np. Alphy). Znacznie poważniejszym problemem jest niestabilność, wynika-
jaca z tego, że proces dzia w trybie jadra nie jest przez nie kontrolowany
lajacy

i może poprzez zapis lub odczyt spod niew
laściwego adresu w pamieci spo-

wodować niestabilność ca systemu operacyjnego z jego zawieszeniem sie
lego

w acznie. Utrudnia to testowanie modu w trakcie jego tworzenia, ale po
l lu

62
jego stworzeniu i przetestowaniu już nie odgrywa roli.
5.3.3 Opis przyjetego rozwiazania

Badania wchodzace w sk niniejszej pracy zosta wykonane w try-
lad ly

bie jadra. Zdecydowano sie na napisanie modu jadra. Rozwiazanie to
lu

jest bardziej elastyczne niż dokonanie zmian bezpośrednio w jadrze. Mo-

du po za
l ladowaniu wypisuje komunikaty, które moga być zapisywane
do pliku (np. /var/log/kernel.log) lub przekazywane kolejki FIFO
(np. /dev/xconsole), z ktorej moga być odczytywane przez inny proces
dzia lokalnie na ruterze lub inny proces zdalny.
lajacy

Dla każdego pakietu wchodzacego do rutera lub wychodzacego z niego

każdy wiersz wyglada nastepujaco:

data nazwa rutera kernel: kierunek: czas adres z
ród > adres docelowy flagi rozmiarB
lowy
Znaczenie poszczególnych kolumn jest nastepujace:

" data: czas wpisywany przez jadro (np. Jul 28 15:59:22)

" nazwa rutera: nazwa komputera, który jest ruterem (np. o387)
" kierunek: określenie, czy jest to pakiet wchodzacy (coming) czy wycho-

dzacy (leaving)

" czas: dok czas nadejścia pakietu mierzony w cyklach zegara (np.
ladny
18019375715228
" adres z
ród adres IP nadawcy pakietu wraz z numerem portu (np.
lowy:
157.158.181.131:35078)
" adres docelowy: adres IP adresata pakietu wraz z numerem portu (np.
157.158.1.3:22)
63
" flagi: ustawione w nag ówku TCP flagi (np. PA oznacza psh+ack)
l
" rozmiar: rozmiar datagramu (np. 40B)
Ca badań zosta wykonana z pomoca standardowego powszechnie
lość la
dostepnego oprogramowania:

" tcpdump - program do pods
luchiwania ruchu w sieci
" ProFTPD - serwer FTP
" lftp - klient FTP
" inetd - demon sieciowy wywo inne us i programy (us echo
lujacy lugi luga

w wersji dla TCP)
Standardowe oprogramowanie nie spe lo wszystkich potrzeb, wiec do-
lni

datkowo napisano program w jezyku C do wysy co określony odstep
lania

czasu spreparowanych przeze mnie pakietów TCP. Analiza plików z logami
wraz z obliczeniami przeprowadzone zosta dedykowanymi programami na-
ly
pisanymi w jezyku Perl.

5.4 Przewodnik po badaniach
5.4.1 Pomiar przepustowości lacza


Wykonano pomiary szybkości transferów miedzy komputerami. Pomiary

przeprowadzono zarówno w transmisjach z pośrednictwem rutera (rys. 5.2),
jak i w po aczeniach bezpośrednich (rys. 5.3), aby ocenić wp rutera
l lyw

na transmisje.

Wykonano dziesieciokrotnie pomiary szybkości transferów przy przesy
la-

niu pliku o wielkości 1MB, 10MB i 100MB z pomoca protoko FTP miedzy
lu

dwoma komputerami. Uśrednione wyniki znajduja sie w tab. 5.1.

64
Rysunek 5.2: Transmisja FTP przy po aczeniu przez ruter
l

Rysunek 5.3: Transmisja FTP przy po aczeniu bezpośrednim
l

Jedynie przy przesy pliki o wielkości 1MB ruter nieznacznie (w gra-
laniu
nicach 1%) opóz
nia transmisje. Natomiast już przy transmisji pliku 10MB

oraz 100MB wp rutera na szybkość transmisji jest pozytywny. Przyspie-
lyw
szenie transmisji po wprowadzeniu rutera wynika stad, że ruter zmniejsza

chwilowe przecia żenia transferu poprzez odpowiednie buforowanie przecho-
dzacych przez niego pakietów sieciowych  wyg ruch w sieci.
ladza


5.4.2 Pomiar opóz
nienia przekazywania pakietów IP
Nastepnie przeprowadzono pomiary opóz
nień przekazywania pakietów IP

oraz ich zmienności (ang. jitter). Również te badania wykonano dla po aczeń
l

komputerów z pośrednictwem rutera i bez pośrednictwa rutera. Do celów
testowych wykorzystano us echo w wersji dla TCP udostepniana przez
luge

serwer sieciowy inetd. Us ta polega na odsy z powrotem tego samego
luga laniu
pakietu, który nadszed przed chwila. Jedynie adresy z
ród i docelowy
l lowy

65
Rozmiar pliku [MB] Po aczenie bezpośrednie [Bps] Po aczenie przez ruter [Bps]
l l

1 746956 742279
10 655519 754742
100 494265 633246
Tablica 5.1: Średnia przepustowość przy przesy plików FTP
laniu
zamieniane sa ze soba.

Pomiar polega na mierzeniu odstepów (interwa ów) czasowych pomiedzy
l l

wysy pakietami TCP o wielkości 1500B. Jako interwa czasowy rozu-
lanymi l
miany jest odstep czasu miedzy wys pakietu przez klienta (nadawca)
laniem

a odebraniem go przez serwer (odbiorca). Zosta on wykonany pieciusetkrot-
l

nie dla różnych po aczeń klienta z serwerem oraz rozmaitych zak óceń. Zak ó-
l l l

ceniami by dodatkowe transmisje FTP wielomegabajtowych ilości danych
ly
przechodzacych przez ten sam ruter oraz dodatkowe transmisje echo.

Transmisje bez dodatkowych zak óceń
l
Wykonano pomiary transmisji pakietów echo bez żadnych zak óceń przy
l
po aczeniu bezpośrednim (rys. 5.4) oraz przy po aczeniu przez ruter (rys. 5.5).
l l

Uśrednione wyniki znajduja sie w tab. 5.2 oraz 5.3.

Rysunek 5.4: Transmisja echo przy po aczeniu bezpośrednim
l

66
Rysunek 5.5: Transmisja echo przy po aczeniu przez ruter
l

Interwa czasowy wysy
l lania
Po aczenie [ms] [s] Minimum [s] Maximum [s] Åšredni [s]
l

1 0.001 0.014453 0.035257 0.019911
bezpośrednie 10 0.01 0.019675 0.038340 0.020025
100 0.1 0.105180 0.109024 0.108878
1000 1 0.996572 1.001076 1.000007
1 0.001 0.016039 0.019829 0.019761
przez ruter 10 0.01 0.017482 0.033624 0.019926
100 0.1 0.100863 0.108952 0.108834
1000 1 0.991690 1.000076 0.999958
Tablica 5.2: Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony klienta
Interwa czasowy wysy
l lania
Po aczenie [ms] [s] Minimum [s] Maximum [s] Åšredni [s]
l

1 0.001 0.000021 0.122739 0.011300
10 0.01 0.019648 0.038468 0.020027
bezpośrednie 100 0.1 0.105168 0.996607 0.117809
1000 1 0.999080 1.001169 1.000125
1 0.001 0.000051 0.019794 0.010154
10 0.01 0.017453 0.142897 0.021235
przez ruter 100 0.1 0.108858 0.991577 0.117936
1000 1 1.000063 1.000191 1.000125
Tablica 5.3: Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony serwera
67
Transmisje z dodatkowymi zak óceniami
l
Do dodatkowe zak ócenie w postaci pojedynczej transmisji FTP,
lożono l
po czym wykonano pomiary opóz
nień przekazywania pakietów. Sytuacja ta
przedstawiona jest na rys. 5.6. Uśrednione wyniki znajduja sie w tab. 5.4 oraz

5.5.
Rysunek 5.6: Transmisja echo przy po aczeniu przez ruter zak ócana przez
l l

pojedyncza transmisje FTP

68
Interwa czasowy wysy
l lania
[ms] [s] Minimum [s] Maximum [s] Åšredni [s]
10 0.01 0.000024 0.047132 0.019770
20 0.02 0.000023 0.109642 0.029816
30 0.03 0.007641 0.109497 0.040255
40 0.04 0.017919 0.081215 0.049482
50 0.05 0.021742 0.088609 0.059322
60 0.06 0.048739 0.092343 0.069495
70 0.07 0.075660 0.242671 0.080857
80 0.08 0.085501 0.090296 0.089076
90 0.09 0.08715 0.092508 0.089113
100 0.1 0.104528 0.113302 0.108887
1000 1 0.999641 1.000083 1.000038
Tablica 5.4: Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony klienta przy jednej transmisji FTP
Interwa czasowy wysy
l lania
[ms] [s] Minimum [s] Maximum [s] Åšredni [s]
10 0.01 0.001221 0.060525 0.020193
20 0.02 0.001208 0.092241 0.029742
30 0.03 0.002783 0.098029 0.039981
40 0.04 0.009262 0.087140 0.049608
50 0.05 0.006832 0.090942 0.059125
60 0.06 0.031493 0.093195 0.069320
70 0.07 0.040101 0.243162 0.080680
80 0.08 0.059644 0.130754 0.089336
90 0.09 0.058208 0.118759 0.089049
100 0.1 0.076205 0.146214 0.108689
1000 1 0.966067 1.036311 1.000078
Tablica 5.5: Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony serwera przy jednej transmisji FTP
69
Do kolejne zak ócenie w postaci drugiej transmisji FTP, po czym
lożono l
wykonano pomiary opóz
nień przekazywania pakietów. Sytuacja ta przedsta-
wiona jest na rys. 5.7. Uśrednione wyniki znajduja sie w tab. 5.6 oraz 5.7.

Rysunek 5.7: Transmisja echo przy po aczeniu przez ruter zak ócana przez
l l

dwie transmisje FTP
70
Interwa czasowy wysy
l lania
[ms] [s] Minimum [s] Maximum [s] Åšredni [s]
10 0.01 0.000020 0.135074 0.020964
20 0.02 0.000021 0.161962 0.030675
30 0.03 0.000021 0.186652 0.039930
40 0.04 0.000022 0.155015 0.049483
50 0.05 0.000023 0.130363 0.059711
60 0.06 0.000023 0.169308 0.069262
70 0.07 0.000023 0.211906 0.079205
80 0.08 0.072677 0.134711 0.089510
90 0.09 0.041039 0.148767 0.098977
100 0.1 0.048513 0.207868 0.109949
1000 1 0.995435 1.000142 0.999996
Tablica 5.6: Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony klienta przy dwóch transmisjach FTP
Interwa czasowy wysy
l lania
[ms] [s] Minimum [s] Maximum [s] Åšredni [s]
10 0.01 0.001219 0.132987 0.021038
20 0.02 0.001240 0.148864 0.030129
30 0.03 0.001046 0.187965 0.039930
40 0.04 0.001424 0.148929 0.048757
50 0.05 0.001376 0.129185 0.059427
60 0.06 0.001376 0.169068 0.069036
70 0.07 0.001363 0.193549 0.078719
80 0.08 0.043899 0.128606 0.089456
90 0.09 0.016620 0.149602 0.099032
100 0.1 0.012277 0.226049 0.109876
1000 1 0.925434 1.063195 1.000212
Tablica 5.7: Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony serwera przy dwóch transmisjach FTP
71
Do dodatkowe zak ócenie w postaci trzeciej transmisji FTP, po
lożono l
czym wykonano pomiary opóz
nień przekazywania pakietów. Sytuacja ta
przedstawiona jest na rys. 5.8. Uśrednione wyniki znajduja sie w tab. 5.8

oraz 5.9.
Rysunek 5.8: Transmisja echo przy po aczeniu przez ruter zak ócana przez
l l

trzy transmisje FTP
72
Interwa czasowy wysy
l lania
[ms] [s] Minimum [s] Maximum [s] Åšredni [s]
10 0.01 0.000022 0.232668 0.023340
20 0.02 0.000022 0.256349 0.033539
30 0.03 0.000022 0.199251 0.040567
40 0.04 0.000022 0.235794 0.049922
50 0.05 0.000023 0.119680 0.059364
60 0.06 0.000024 0.182089 0.069230
70 0.07 0.000023 0.255396 0.079957
80 0.08 0.000024 0.182322 0.089056
90 0.09 0.005904 0.191247 0.099005
100 0.1 0.000024 0.240286 0.109862
1000 1 0.991639 1.000129 0.999957
Tablica 5.8: Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony klienta przy trzech transmisjach FTP
Interwa czasowy wysy
l lania
[ms] [s] Minimum [s] Maximum [s] Åšredni [s]
10 0.01 0.001053 0.232879 0.023613
20 0.02 0.001208 0.249911 0.033465
30 0.03 0.001028 0.207301 0.040671
40 0.04 0.001044 0.228850 0.049883
50 0.05 0.001406 0.120586 0.059943
60 0.06 0.001206 0.185317 0.069109
70 0.07 0.001220 0.254266 0.079760
80 0.08 0.001220 0.187819 0.089140
90 0.09 0.004323 0.194543 0.099391
100 0.1 0.001392 0.240055 0.109731
1000 1 0.939382 1.053048 0.999843
Tablica 5.9: Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony serwera przy trzech transmisjach FTP
73
Do dodatkowe zak ócenie w postaci czwartej transmisji FTP, po
lożono l
czym wykonano pomiary opóz
nień przekazywania pakietów. Sytuacja ta
przedstawiona jest na rys. 5.9. Uśrednione wyniki znajduja sie w tab. 5.10

oraz 5.11.
Rysunek 5.9: Transmisja echo przy po aczeniu przez ruter zak ócana przez
l l

cztery transmisje FTP
74
Interwa czasowy wysy
l lania
[ms] [s] Minimum [s] Maximum [s] Åšredni [s]
10 0.01 0.000020 0.114798 0.006528
20 0.02 0.000021 0.114269 0.005555
30 0.03 0.000021 0.082949 0.003302
40 0.04 0.000020 0.082614 0.004843
50 0.05 0.000021 0.073251 0.008533
60 0.06 0.000021 0.072662 0.007106
70 0.07 0.000020 0.109462 0.004978
80 0.08 0.000020 0.143179 0.003893
90 0.09 0.000020 0.080411 0.004719
100 0.1 0.000020 4.911110 0.010326
1000 1 0.000020 0.087505 0.002912
Tablica 5.10: Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony klienta przy czterech transmisjach FTP
Interwa czasowy wysy
l lania
[ms] [s] Minimum [s] Maximum [s] Åšredni [s]
10 0.01 0.000022 0.178015 0.022632
20 0.02 0.000022 0.219057 0.032522
30 0.03 0.000023 0.206526 0.040703
40 0.04 0.000020 6.495322 0.162033
50 0.05 0.000021 5.386366 0.153751
60 0.06 0.000022 0.225404 0.068525
70 0.07 0.077640 0.238317 0.080825
80 0.08 0.000023 0.244727 0.089026
90 0.09 0.031520 0.164517 0.098994
100 0.1 0.000022 13.355381 0.231340
1000 1 0.997739 1.000608 1.000017
Tablica 5.11: Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony serwera przy czterech transmisjach FTP
75
Powrócono do sytuacji bez transmisji FTP, ale do dodatkowe za-
lożono
k ócenie w postaci dodatkowej transmisji echo, po czym wykonano pomiary
l
opóz
nień przekazywania pakietów. Sytuacja ta przedstawiona jest na rys.
5.10. Uśrednione wyniki znajduja sie w tab. 5.12 oraz 5.13.

Rysunek 5.10: Transmisja echo przy po aczeniu przez ruter zak ócana przez
l l

druga transmisje echo

76
Interwa czasowy wysy
l lania
[ms] [s] Minimum [s] Maximum [s] Åšredni [s]
10 0.01 0.017988 0.019940 0.019784
20 0.02 0.029138 0.029732 0.029698
30 0.03 0.000024 0.290135 0.039589
40 0.04 0.048844 0.049546 0.049500
50 0.05 0.058531 0.059437 0.059400
60 0.06 0.068518 0.069328 0.069302
70 0.07 0.078329 0.079287 0.079202
80 0.08 0.084922 0.093304 0.089106
90 0.09 0.098163 0.099035 0.099005
100 0.1 0.107975 0.115925 0.109006
1000 1 0.999263 1.000068 1.000034
Tablica 5.12: Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony klienta przy równoleg transmisji echo
lej
Interwa czasowy wysy
l lania
[ms] [s] Minimum [s] Maximum [s] Åšredni [s]
10 0.01 0.017645 0.020376 0.019781
20 0.02 0.029099 0.029778 0.029700
30 0.03 0.001015 0.290531 0.039591
40 0.04 0.048828 0.049568 0.049504
50 0.05 0.058532 0.059475 0.059404
60 0.06 0.068472 0.069381 0.069307
70 0.07 0.078316 0.079317 0.079208
80 0.08 0.083390 0.094833 0.089111
90 0.09 0.098124 0.099445 0.099013
100 0.1 0.107885 0.115580 0.109014
1000 1 0.999300 1.000188 1.000116
Tablica 5.13: Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony serwera przy równoleg transmisji echo
lej
77
Do dodatkowe zak ócenie w postaci czterech transmisji FTP, po
lożono l
czym wykonano pomiary opóz
nień przekazywania pakietów. Sytuacja ta
przedstawiona jest na rys. 5.11. Uśrednione wyniki znajduja sie w tab. 5.14

oraz 5.15.
Rysunek 5.11: Transmisja echo przy po aczeniu przez ruter zak ócana przez
l l

druga transmisje echo oraz cztery transmisje FTP

78
Interwa czasowy wysy
l lania
[ms] [s] Minimum [s] Maximum [s] Åšredni [s]
10 0.01 0.000022 0.107957 0.020479
20 0.02 0.000021 0.175317 0.030805
30 0.03 0.000023 0.234044 0.040552
40 0.04 0.000023 0.154487 0.049577
50 0.05 0.000023 0.142766 0.059421
60 0.06 0.000027 0.226315 0.069261
70 0.07 0.000029 0.168799 0.079191
80 0.08 0.000025 0.230867 0.089201
90 0.09 0.025794 0.171598 0.099111
100 0.1 0.083233 0.133768 0.108908
1000 1 0.991799 1.144377 1.001479
Tablica 5.14: Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony klienta przy pieciu równoleg transmisjach
lych

Interwa czasowy wysy
l lania
[ms] [s] Minimum [s] Maximum [s] Åšredni [s]
10 0.01 0.000018 0.122161 0.020952
20 0.02 0.000018 0.216222 0.030725
30 0.03 0.001189 0.224939 0.040922
40 0.04 0.001202 0.210858 0.050777
50 0.05 0.001306 0.153896 0.059945
60 0.06 0.001300 0.219455 0.069420
70 0.07 0.001204 0.166524 0.079882
80 0.08 0.001404 0.291819 0.090090
90 0.09 0.035026 0.205485 0.099737
100 0.1 0.038219 0.182717 0.109556
1000 1 0.932953 1.137455 1.001810
Tablica 5.15: Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony serwera przy pieciu równoleg transmisjach
lych

79
Do dodatkowe zak ócenie w postaci dodatkowej transmisji echo oraz
lożono l
sześciu transmisji FTP, a nastepnie wykonano pomiary opóz
nień przekazywa-

nia pakietów. Sytuacja ta przedstawiona jest na rys. 5.12. Uśrednione wyniki
znajduja sie w tab. 5.16 oraz 5.17.

Rysunek 5.12: Transmisja echo przy po aczeniu przez ruter zak ócana przez
l l

druga transmisje echo oraz sześć transmisji FTP

80
Interwa czasowy wysy
l lania
[ms] [s] Minimum [s] Maximum [s] Åšredni [s]
10 0.01 0.000023 0.193585 0.022773
20 0.02 0.000022 0.120375 0.021131
30 0.03 0.000023 0.185401 0.030935
40 0.04 0.000024 0.129402 0.039755
50 0.05 0.000026 0.141291 0.049530
60 0.06 0.000025 0.164876 0.059752
70 0.07 0.000025 0.152054 0.069258
80 0.08 0.029578 0.128873 0.079124
90 0.09 0.055432 0.120149 0.089086
100 0.1 0.095892 0.121997 0.108919
1000 1 0.991908 1.139237 1.001561
Tablica 5.16: Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony klienta przy siedmiu równoleg transmisjach
lych
Interwa czasowy wysy
l lania
[ms] [s] Minimum [s] Maximum [s] Åšredni [s]
10 0.01 0.000855 0.114927 0.021378
20 0.02 0.001040 0.199910 0.031439
30 0.03 0.000968 0.120478 0.040150
40 0.04 0.001206 0.154312 0.050262
50 0.05 0.001218 0.186794 0.061117
60 0.06 0.001221 0.186878 0.070839
70 0.07 0.021498 0.147259 0.080603
80 0.08 0.023551 0.153349 0.090087
90 0.09 0.001419 0.174340 0.099845
100 0.1 0.066775 0.162005 0.110097
1000 1 0.823181 1.133839 1.002453
Tablica 5.17: Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony serwera przy siedmiu równoleg transmisjach
lych
81
Rozdzia 6
l
Badania wykonane
z w aczonymi mechanizmami
l

QoS
6.1 Cel badań
Badania polega na zmierzeniu wp różnych czynników (pośrednic-
ly lywu
two rutera w transmisji danych, transmisje FTP wykonywane w tle, druga
transmisja interaktywna wykonywana w tle) na opóz
nienia w przekazywaniu
pakietów IP (ang. jitter). Badania zosta przeprowadzone z wykorzystaniem
ly
stanowiska opisanego w rozdz. 5. Na badania te sk ly sie pomiary transmi-
lada

sji danych przez obcia żony ruter dzia z wykorzystaniem mechanizmów
lajacy

QoS. Celem tych badań by sprawdzenie, czy mechanizmy QoS moga przy-
lo
bliżyć opóz
nienia przekazywania pakietów przez obcia żony ruter do sytuacji,
gdy ruter nie jest obcia żony (badania opisane w rozdz. 5).
82
6.2 Badania z wykorzystaniem algorytmu
PRIO
Zmierzono opóz
nienia przekazywania pakietów w trakcie transmisji z wy-
korzystaniem algorytmu PRIO (podsekcja 3.1.2. Dodatkowym obcia żeniem
by jedna transmisja FTP. Sytuacja ta przedstawiona jest na rys. 6.1. Uśred-
la
nione wyniku tego pomiaru znajduja sie w tab. 6.1 oraz 6.2.

Rysunek 6.1: Transmisja echo z wykorzystaniem algorytmu PRIO przy do-
datkowej transmisji FTP
83
Interwa czasowy wysy
l lania
[ms] [s] Minimum [s] Maximum [s] Åšredni [s]
10 0.01 0.000022 0.085218 0.019830
100 0.1 0.095642 0.118764 0.108861
1000 1 0.993492 1.000253 0.999976
Tablica 6.1: Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony klienta przy jednej równoleg transmisji FTP
lej
Interwa czasowy wysy
l lania
[ms] [s] Minimum [s] Maximum [s] Åšredni [s]
10 0.01 0.001048 0.080605 0.019849
100 0.1 0.068598 0.140607 0.108881
1000 1 0.964936 1.023353 0.999971
Tablica 6.2: Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony serwera przy jednej równoleg transmisji FTP
lej
84
Do dodatkowe zak ócenie w postaci dwóch transmisji FTP. Sytu-
lożono l
acja ta przedstawiona jest na rys. 6.2. Uśrednione wyniki pomiarów zamiesz-
czone sa w tab. 6.3 oraz 6.4.
Rysunek 6.2: Transmisja echo z wykorzystaniem algorytmu PRIO przy do-
datkowych dwóch transmisjach FTP
85
Interwa czasowy wysy
l lania
[ms] [s] Minimum [s] Maximum [s] Åšredni [s]
10 0.01 0.000022 0.104263 0.020269
100 0.1 0.098339 0.143924 0.109166
1000 1 0.997552 1.000081 1.000017
Tablica 6.3: Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony klienta przy dwóch transmisjach FTP
Interwa czasowy wysy
l lania
[ms] [s] Minimum [s] Maximum [s] Åšredni [s]
10 0.01 0.001161 0.099931 0.020403
100 0.1 0.059071 0.168140 0.109281
1000 1 0.926992 1.061800 1.000059
Tablica 6.4: Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony serwera przy dwóch transmisjach FTP
86
Do dodatkowe zak ócenie w postaci trzeciej transmisji FTP. Sytu-
lożono l
acja przedstawiona jest na rys. 6.3. Uśrednione wyniki znajduja sie w tab. 6.5

oraz 6.6.
Rysunek 6.3: Transmisja echo z wykorzystaniem algorytmu PRIO przy do-
datkowych trzech transmisjach FTP
87
Interwa czasowy wysy
l lania
[ms] [s] Minimum [s] Maximum [s] Åšredni [s]
10 0.01 0.000022 0.188033 0.022894
100 0.1 0.036477 0.185305 0.108958
1000 1 0.996380 1.000065 1.000005
Tablica 6.5: Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony klienta przy trzech transmisjach FTP
Interwa czasowy wysy
l lania
[ms] [s] Minimum [s] Maximum [s] Åšredni [s]
10 0.01 0.001134 0.185643 0.022971
100 0.1 0.028200 0.188852 0.109223
1000 1 0.903677 1.061431 1.000156
Tablica 6.6: Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony serwera przy trzech transmisjach FTP
88
Nastepnie do dodatkowe zak ócenie w postaci czwartej transmisji
lożone l

FTP. Sytuacja przedstawiona jest na rys. 6.4. Uśrednione wyniki znajduja
sie w tab. 6.7 oraz 6.8.

Rysunek 6.4: Transmisja echo z wykorzystaniem algorytmu PRIO przy do-
datkowych czterech transmisjach FTP
89
Interwa czasowy wysy
l lania
[ms] [s] Minimum [s] Maximum [s] Åšredni [s]
10 0.01 0.000021 0.218573 0.023747
100 0.1 0.013985 0.210690 0.108876
1000 1 0.680404 1.962631 0.997492
Tablica 6.7: Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony klienta przy czterech transmisjach FTP
Interwa czasowy wysy
l lania
[ms] [s] Minimum [s] Maximum [s] Åšredni [s]
10 0.01 0.001122 0.215318 0.024141
100 0.1 0.012561 0.208918 0.108853
1000 1 0.658787 2.084703 0.999470
Tablica 6.8: Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony serwera przy czterech transmisjach FTP
90
Do druga transmisje echo, a ilość transmisji FTP zmniejszono do
lożono

jednej, po czym zmierzono opóz
nienia przekazywania pakietów w trakcie
transmisji echo. Sytuacja ta przedstawiona jest na rys. 6.5. Uśrednione wy-
niku tego pomiaru znajduja sie w tab. 6.9 oraz 6.10.

Rysunek 6.5: Transmisja echo z wykorzystaniem algorytmu PRIO przy do-
datkowej transmisji echo oraz czterech transmisjach FTP
91
Interwa czasowy wysy
l lania
y wysy [ms] Minimum [s] Maximum [s] Åšredni [s]
lania
10 0.002110 0.079778 0.019891
100 0.101385 0.143802 0.109178
1000 0.993947 1.000080 0.999981
Tablica 6.9: Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony klienta przy równoleg transmisji echo i dodatkowej
lej
transmisji FTP
Interwa czasowy wysy
l lania
[ms] [s] Minimum [s] Maximum [s] Åšredni [s]
10 0.01 0.001178 0.088238 0.019891
100 0.1 0.082097 0.167983 0.109427
1000 1 0.962866 1.034299 1.000222
Tablica 6.10: Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony serwera przy przy równoleg transmisji echo oraz jednej
lej
transmisji FTP
92
Do druga transmisje FTP, po czym zmierzono opóz
nienia przekazy-
lożono

wania pakietów w trakcie transmisji echo. Sytuacja ta przedstawiona jest na
rys. 6.6. Uśrednione wyniku tego pomiaru znajduja sie w tab. 6.11 oraz 6.12.

Rysunek 6.6: Transmisja echo z wykorzystaniem algorytmu PRIO przy do-
datkowej transmisji echo oraz dwóch transmisjach FTP
93
Interwa czasowy wysy
l lania
[ms] [s] Minimum [s] Maximum [s] Åšredni [s]
10 0.01 0.000021 0.115227 0.020546
100 0.1 0.090363 0.151436 0.109167
1000 1 0.996179 1.000073 1.000003
Tablica 6.11: Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony klienta przy równoleg transmisji echo i dwóch trans-
lej
misjach FTP
Interwa czasowy wysy
l lania
[ms] [s] Minimum [s] Maximum [s] Åšredni [s]
10 0.01 0.001122 0.115419 0.020745
100 0.1 0.065040 0.161493 0.109154
1000 1 0.935454 1.043528 0.999929
Tablica 6.12: Pomiary transmisji dla us echo miedzy klientem i serwe-
lugi

rem mierzone od strony serwera przy równoleg transmisji echo i dwóch
lej
transmisjach FTP
94
Do trzecia transmisje FTP, po czym zmierzono opóz
nienia prze-
lożono

kazywania pakietów w trakcie transmisji echo. Sytuacja ta przedstawiona
jest na rys. 6.7. Uśrednione wyniku tego pomiaru znajduja sie w tab. 6.13

oraz 6.14.
Rysunek 6.7: Transmisja echo z wykorzystaniem algorytmu PRIO przy do-
datkowej transmisji echo oraz trzech transmisjach FTP
95
Interwa czasowy wysy
l lania
[ms] [s] Minimum [s] Maximum [s] Åšredni [s]
10 0.01 0.000022 0.206477 0.023548
100 0.1 0.046517 0.206947 0.109546
1000 1 0.995205 1.000082 0.999993
Tablica 6.13: Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony klienta przy równoleg transmisji echo i trzech transmi-
lej
sjach FTP
Interwa czasowy wysy
l lania
[ms] [s] Minimum [s] Maximum [s] Åšredni [s]
10 0.01 0.001143 0.208647 0.023670
100 0.1 0.029283 0.211722 0.109484
1000 1 0.914671 1.058482 1.000026
Tablica 6.14: Pomiary transmisji dla us echo miedzy klientem i serwe-
lugi

rem mierzone od strony serwera przy równoleg transmisji echo i trzech
lej
transmisjach FTP
96
Do czwarta transmisje echo, po czym zmierzono opóz
nienia prze-
lożono

kazywania pakietów w trakcie transmisji echo. Sytuacja ta przedstawiona
jest na rys. 6.8. Uśrednione wyniku tego pomiaru znajduja sie w tab. 6.15

oraz 6.16.
Rysunek 6.8: Transmisja echo z wykorzystaniem algorytmu PRIO przy do-
datkowej transmisji echo oraz czterech transmisjach FTP
97
Interwa czasowy wysy
l lania
[ms] [s] Minimum [s] Maximum [s] Åšredni [s]
10 0.01 0.000022 0.220649 0.024257
100 0.1 0.046553 0.179133 0.108981
1000 1 0.996028 1.000541 1.000002
Tablica 6.15: Pomiary transmisji dla us echo miedzy klientem i serwe-
lugi

rem mierzone od strony klienta przy równoleg transmisji echo i czterech
lej
transmisjach FTP
Interwa czasowy wysy
l lania
[ms] [s] Minimum [s] Maximum [s] Åšredni [s]
10 0.01 0.001087 0.221625 0.024353
100 0.1 0.019623 0.200774 0.108968
1000 1 0.917508 1.067277 0.999907
Tablica 6.16: Pomiary transmisji dla us echo miedzy klientem i serwe-
lugi

rem mierzone od strony serwera przy równoleg transmisji echo i czterech
lej
transmisjach FTP
98
6.3 Badania wykonane z wykorzystaniem al-
gorytmu TBF
Zmierzono opóz
nienia przekazywania pakietów w trakcie transmisji z
wykorzystaniem algorytmu kolejkowania TBF (podsekcja 3.1.3). Algorytm
ten wykorzystany by do kszta
l ltowania ruchu pakietów generowanego przez
transfery FTP.
Zaczeto od zak ócenia w postaci drugiej transmisji echo oraz jednej trans-
l

misji FTP. Sytuacja przedstawiona jest na rys. 6.9. Uśrednione wyniki zgro-
madzone sa w tab. 6.17 oraz 6.18
Rysunek 6.9: Transmisja echo z wykorzystaniem algorytmu TBF przy dodat-
kowej transmisji echo oraz jednej transmisji FTP
99
Interwa czasowy wysy
l lania
[ms] [s] Minimum [s] Maximum [s] Åšredni [s]
10 0.01 0.000021 0.105156 0.020503
100 0.1 0.098810 0.138890 0.109117
1000 1 0.994620 1.20087 1.002092
Tablica 6.17: Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony klienta przy równoleg transmisji echo i jednej transmisji
lej
FTP
Interwa czasowy wysy
l lania
[ms] [s] Minimum [s] Maximum [s] Åšredni [s]
10 0.01 0.001227 0.124556 0.024230
100 0.1 0.053717 0.202963 0.128995
1000 1 1.108759 1.475996 1.184452
Tablica 6.18: Pomiary transmisji dla us echo miedzy klientem i serwe-
lugi

rem mierzone od strony serwera przy równoleg transmisji echo i jednej
lej
transmisji FTP
100
Do zak ócenie w postaci drugiej transmisji FTP. Sytuacja ta przed-
lożono l
stawiona jest na rys. 6.10. Uśrednione wyniki zgromadzone sa w tab. 6.19
oraz 6.20
Rysunek 6.10: Transmisja echo z wykorzystaniem algorytmu TBF przy do-
datkowej transmisji echo oraz dwóch transmisjach FTP
101
Interwa czasowy wysy
l lania
[ms] [s] Minimum [s] Maximum [s] Åšredni [s]
10 0.01 0.000022 0.259524 0.025290
100 0.1 0.000023 0.292046 0.108864
1000 1 0.994255 1.000575 0.999985
Tablica 6.19: Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony klienta przy równoleg transmisji echo i dwóch trans-
lej
misjach FTP
Interwa czasowy wysy
l lania
[ms] [s] Minimum [s] Maximum [s] Åšredni [s]
10 0.01 0.001025 0.306166 0.029955
100 0.1 0.001168 0.343795 0.128711
1000 1 1.057435 1.291630 1.182050
Tablica 6.20: Pomiary transmisji dla us echo miedzy klientem i serwe-
lugi

rem mierzone od strony serwera przy równoleg transmisji echo i dwóch
lej
transmisjach FTP
102
Nastepnie do zak ócenia w postaci dodatkowych czterech transmisji
lożono l

FTP. Sytuacja przedstawiona jest na rys. 6.11. Uśrednione wyniki zgroma-
dzone sa w tab. 6.21 oraz 6.22
Rysunek 6.11: Transmisja echo z wykorzystaniem algorytmu TBF przy do-
datkowej transmisji echo oraz sześciu transmisjach FTP
103
Interwa czasowy wysy
l lania
[ms] [s] Minimum [s] Maximum [s] Åšredni [s]
10 0.01 0.000021 0.494902 0.047233
100 0.1 0.000023 1.177996 0.126182
1000 1 0.307809 1.970862 1.013642
Tablica 6.21: Pomiary transmisji dla us echo miedzy klientem i serwe-
lugi

rem mierzone od strony klienta przy równoleg transmisji echo i sześciu
lej
transmisjach FTP
Interwa czasowy wysy
l lania
[ms] [s] Minimum [s] Maximum [s] Åšredni [s]
10 0.01 0.000952 4.737959 0.656889
100 0.1 0.000462 4.982930 0.564265
1000 1 0.000026 4.809246 0.467232
Tablica 6.22: Pomiary transmisji dla us echo miedzy klientem i serwe-
lugi

rem mierzone od strony serwera przy równoleg transmisji echo i sześciu
lej
transmisjach FTP
104
6.4 Badania wykonane z wykorzystaniem al-
gorytmu RED
Zmierzono opóz
nienia przekazywania pakietów w trakcie transmisji z wy-
korzystaniem algorytmu kolejkowania RED (subsec 3.1.5). Algorytm ten wy-
korzystany by do regulowania ruchu pakietów generowany w trakcie trans-
l
misji FTP.
Zaczeto od zak ócenia w postaci drugiej transmisji echo oraz dwóch trans-
l

misji FTP. Sytuacja przedstawiona jest na rys. 6.12. Uśrednione wyniki
zgromadzone sa w tab. 6.23 oraz 6.24
Rysunek 6.12: Transmisja echo z wykorzystaniem algorytmu RED przy do-
datkowej transmisji echo oraz dwóch transmisjach FTP
105
Interwa czasowy wysy
l lania
[ms] [s] Minimum [s] Maximum [s] Åšredni [s]
10 0.01 0.002406 0.082508 0.020263
100 0.1 0.097322 0.218592 0.110006
1000 1 0.994988 1.000105 0.999991
Tablica 6.23: Pomiary transmisji dla us echo miedzy klientem i serwe-
lugi

rem mierzone od strony klienta przy równoleg transmisji echo oraz dwóch
lej
transmisjach FTP
Interwa czasowy wysy
l lania
[ms] [s] Minimum [s] Maximum [s] Åšredni [s]
10 0.01 0.001497 0.089278 0.020592
100 0.1 0.044788 0.224570 0.109986
1000 1 0.929579 1.060968 0.999865
Tablica 6.24: Pomiary transmisji dla us echo miedzy klientem i serwe-
lugi

rem mierzone od strony serwera przy równoleg transmisji echo oraz dwóch
lej
transmisjach FTP
106
Do zak ócenie w postaci dodatkowych czterech transmisji FTP. Sy-
lożono l
tuacja przedstawiona jest na rys. 6.13. Uśrednione wyniki zgromadzone sa w
tab. 6.25 oraz 6.26
Rysunek 6.13: Transmisja echo z wykorzystaniem algorytmu RED przy do-
datkowej transmisji echo oraz sześciu transmisjach FTP
107
Interwa czasowy wysy
l lania
[ms] [s] Minimum [s] Maximum [s] Åšredni [s]
10 0.01 0.000021 0.272974 0.025631
100 0.1 0.019175 0.239059 0.108855
1000 1 0.997353 1.000765 1.000016
Tablica 6.25: Pomiary transmisji dla us echo miedzy klientem i serwe-
lugi

rem mierzone od strony klienta przy równoleg transmisji echo oraz sześciu
lej
transmisjach FTP
Interwa czasowy wysy
l lania
[ms] [s] Minimum [s] Maximum [s] Åšredni [s]
10 0.01 0.001176 0.266241 0.025317
100 0.1 0.013522 0.254707 0.109323
1000 1 0.878032 1.104671 1.000324
Tablica 6.26: Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony serwera przy równoleg transmisji echo oraz sześciu
lej
transmisjach FTP
108
Rozdzia 7
l
Podsumowanie oraz wnioski
Analiza wyników
Na pierwszy rzut oka można już zauważyć, że wyniki badań opóz
nień
przekazywania pakietów IP przy wysy pakietów co 1ms (tab. 5.2) sa
laniu
bardzo zbliżone do wyników osiagnietych przez wysy pakietów co 10ms
lanie

(tab. 5.2). Wynika to z tego, że na potrzeby jadra Linuksa czas mierzony

jest w kwantach czasu (ang. jiffies). Na platformie Intela x86 jednostka ta
równa sie 10ms. Wynika z tego, że pakiety można wysy bez kontroli cza-
lać

sowej ( najlepszy wysi [4]) lub w odstepach 10ms, badz
wielokrotnościach
lek


10ms. Dlatego też w dalszych pomiarach zaniechano wysy pakietów co
lania
1ms. Dodatkowo można zauważyć, że podobnie jak w przypadku transferów
wiekszych ilości danych z pomoca FTP (tab. 5.1), nawet transmisje nie-

wielkich ilości danych przez ruter sa bardziej p niż te same transmisje
lynne
bezpośrednie (tab. 5.2 oraz 5.3).
Zmierzono opóz
nienia zachodzace w transmisji echo przy równoczesnym

transferze FTP przechodzacym przez ten sam ruter. Z wyników tych pomia-

rów można wyciagna ć nastepujace wnioski:

109
" Przy interwa czasowych wysy pakietów mniejszych od 100ms
lach lania
pojawiaja sie wartości mniejsze od zamierzonych. Wynika to ze spo-

sobu w jaki ruter obs pakiety TCP, tzn. jeśli pakiety nie zostaja
luguje
wys na czas z powodu przecia żenia, to póz
niej wysy sa szybciej,
lane lane
aby średnie opóz
nienie mieści sie w wymaganych granicach. Takie za-
lo

chowanie rutera można zaobserwować dla interwa ów od 10ms do 60ms
l
(tab. 5.4).
" Wyg
ladzanie ruchu (uśrednianie opóz
nień przekazywania pakietów)

można zaobserwować g ównie dla interwa ów czasowych 100ms 1s (tab.
l l
6.15. Wynika to z faktu, że jadro Linuksa na potrzeby w odmierza
lasne

czas jako wielokrotność jednostki równej 10ms.
" Prosty algorytm kolejkowania PRIO (opis w podsekcji 3.1.2 a wyniki w
tab. 6.15 i tab. 6.16) dla naszego przypadku okaza sie porównywalnie
l

skuteczny jak algorytmy TBF (opis w podsekcji 3.1.3 a wyniki w tab.
6.21 oraz 6.22) oraz RED (opis w podsekcji 3.1.5 a wyniki w tab. 6.25
i tab. 6.26).
Każdy z użytych algorytmów ma swoje mocne i s strony, dlatego też
labe
dla każdego istnieja zastosowania w których może sprawować sie lepiej od

pozosta
lych:
" Algorytm kolejkowania PRIO (podsekcja 3.1.2) nadaje sie do prostej

klasyfikacji ruchu na kilka klas ruchu wed priorytetów ważności (ruch
lug
o najwyższym priorytecie powinien być obs
lugiwany w pierwszej ko-
lejności). Jako kryterium klasyfikacji wystarczy zastosować bity pola
TOS.
" Algorytm kolejkowania TBF (podsekcja 3.1.3) sprawdza sie w roli czyn-

nika kszta lumiacego) ruch. Pozwala on na zapobieżenie za-
ltujacego (t


110
g
lodzenia klas ruchu o niższym priorytecie przez klasy ruchu o wyż-
szym priorytecie.
" Algorytm kolejkowania RED (podsekcja 3.1.5) umożliwia stopniowe re-
gulowanie ruchu wchodzacego. Wykonuje to bardziej elastycznie niż

standardowe mechanizmy protoko TCP. Umożliwia również bardziej
lu
efektywne wykorzystanie dostepnej przepustowości pasma, warunkowo

przepuszczajac cześć nadmiarowych pakietów IP zamiast ich bezwa-

runkowego odrzucania.
Linux stale sie rozwija i w przysz do oficjalnej wersji jadra moga
lości

wejść dwa opracowane i przetestowane algorytmy, które na razie dostepne sa

w postaci laty na jadro.


Pierwszym z nich jest algorytm kolejkowania HTB (ang. Hierarchical To-
ken Bucket). Jest to elastyczny algorytm klasowy o zastosowaniach zbieżnych
z zastosowaniami algorytmu kolejkowania CBQ (podsekcja 3.1.6). W porów-
naniu z algorytmem CBQ jest bardziej precyzyjny w podziale przepustowo-
ści na klasy ruchu. Poza tym konfiguracja tego algorytmu jest prostsza, gdyż
nie wymaga on ustawiania kilkunastu parametrów konfiguracyjnych tak jak
CBQ, a jedynie kilku.
Drugim algorytmem kolejkowania, który w przysz czasie może stać sie
lości

cześcia oficjalnej ga ezi jadra, jest WRR (ang. Weighted Round-Robin). Algo-
l

rytm ten jest uogólniona wersja klasycznego algorytmu cyklicznego round-

robin . Modyfikacja w stosunku do pierwowzoru polega na przypisaniu każdej
z klas ruchu, która algorytm ten obs innej wagi. W zależności od przy-
luguje,
pisanej klasie wagi, pakietu moga być cześciej pobierane do wys z tej
lania

klasy (wyższa waga klasy) lub rzadziej pobierane do wysy (niższa waga
lania
klasy). Algorytm ten umożliwia w prosty sposób faworyzowanie wybrany
transmisji pakietów (np. wed adresów IP nadawcy i adresata).
lug
111
Niniejsza praca obejmuje swym zakresem tylko cześć zagadnienia tytu-

lościowe odzwierciedlenie stanu implementacji mechani-
lowego. Bardziej ca
zmów QoS w systemie Linux wymaga
loby:
1. poszerzenia zestawu badań
2. powtórzenia wszystkich badań na innych platformach sprzetowych

Poszerzenie zestawu badań wymaga zdefiniowania dodatkowych
loby
transmisji po aczeń, które zosta zmierzone. Szczególnie ciekawe by
l lyby loby

bardziej rygorystyczne skonfigurowanie mechanizmów kszta
ltowania ruchu

równolegle ze stworzeniem rozbudowanej hierarchii klas ruchu . Wykorzy-
stane do tego moga być algorytmy TBF (podsekcja 3.1.3) oraz CBQ (pod-
sekcja 3.1.6). Ciekawe może być również sprawdzenie skalowalności rozwia-

zań QoS poprzez zwiekszenie ilości komputerów i po aczeń miedzy nimi, czyli
l

rozbudowe stanowiska badawczego.

Równie interesujace by powtórzenie wszystkich badań na ca
loby lkowicie

innym stanowisku badawczym. Należa w tym celu zmienić komputer pe
loby l-
niacy role rutera programowego na szybszy. Najwiekszy wp w tym przy-
lyw

padku da zmiana procesora na szybszy. W ten sposób obs wewnetrz-
laby luga

nych mechanizmów czasowych sterujacych QoS mog być szybsza [1]. Dla
laby

uzyskania pe obrazu wydajności implementacji QoS w systemie Linux
lnego
dobrze by jako ruter programowy użyć komputera zbudowanego w opar-
loby
cie o inna platforme sprzetowa niż Intel x86. Można w tym celu skorzystać z

1
platformy Alpha, na której kwant czasu jadra wynosi s (dla porównania
1024
1
na platformie Intel x86 wynosi s).
10
112
Bibliografia
[1] y
ród Linuksa w wersji2.4.18, 2002
la
[2] y
ród pakietu iproute w wersji z dnia24.8.2001, 2001
la
[3] Podreczniki systemowe dla Linuksa, 2002

[4] G. Armitage: Quality Of Service In IP Networks  Foundations for a

Multi-Service Internet , Macmillan Technical Publishing USA, 2000
[5] P. Krawczyk: Sterowanie przep danych w Linuxie 2.2 , 2001
lywem

[6] Linux Advanced Routing & Traffic Control HOWTO , 2001

[7] J. Wroclawski The Use of RSVP with IETF Integrated Services , RFC

2210, wrzesień 1997
[8] RSVP daemon , sierpień 1998

[9] Internet Protocol Darpa Internet Program Protocol Specification , STD

5, wrzesień 1981
[10] S. Deering, R. Hinden Internet Protocol, Version 6 (IPv6) Specifica-

tion , RFC 2460, grudzień 1998
[11] Transmission Control Protocol Darpa Internet Program Protocol Speci-

fication , STD 7, sierpień 1981
113
[12] Definition of the Differentiated Services Field (DS Field) in the IPv4

and IPv6 Headers , RFC 2474, grudzień 1998
[13] An Architecture for Differentiated Services , RFC 2475, grudzień 1998

[14] R. Braden, D. Clark, S. Shenker Integrated Services in the Internet

Architecture: and Overview , RFC 1633, czerwiec 1994
[15] Per Hop Behavior Identification Codes , RFC 3140, czerwiec 2001

[16] Assured Forwarding PHB Group , RFC 2597, czerwiec 1999

[17] An Expedited Forwarding PHB (Per-Hop Behavior , RFC 3246, marzec

2002
[18] Supplemental Information for the New Definition of the EF PHB

(Expedited Forwarding Per-Hop Behavior , RFC 3247, marzec 2002
[19] S. Shenker, C. Patridge, R. Guerin Specification of Guaranteed Quality

of Service , RFC 2212, wrzesień 1997
[20] J. Wroclawski Specification of the Controlled-Load Network Element

Service , RFC 2211, wrzesień 1997
[21] S. Floyd, V. Jacobson Random Early Detection Gateways for Conge-

stion Avoidance , sierpień 1993
[22] David D. Clark, Scott Shenker, L. Zhang Supporting Real-Time Ap-

plications in an Integrated Services Packet Network: Architecture and
Mechanism , 1992
[23] Jon C.R. Bennett, Hui Zhang Hierarchical Packet Fair Queueing Algo-

rithms , paz
dziernik 1996
114
[24] S. Floyd, V. Jacobson Link-sharing and Resource Management Models

for Packet Networks , sierpień 1995
[25] S. Floyd Notes on Class-Based Queuing: Setting Parameters , luty 1996

[26] S. Floyd Notes on CBQ and Guaranteed Service , lipiec 1995

[27] L. Berger, T. O Malley RSVP Extensions for IPSEC Data Flows , RFC

2207, wrzesień 1997
[28] V. Johnson Technology Backgrounder  Quality of Service  Glossary

of Terms , 1999
115
Spis rysunków
2.1 Protokó rezerwacji (RSVP) . . . . . . . . . . . . . . . . . . . 11
l
2.2 Architektura DiffServ . . . . . . . . . . . . . . . . . . . . . . . 13
2.3 Nag ówek pakietu IPv4 . . . . . . . . . . . . . . . . . . . . . . 13
l
2.4 Nag ówek pakietu IPv6 . . . . . . . . . . . . . . . . . . . . . . 15
l
2.5 Nag ówek pakietu TCP . . . . . . . . . . . . . . . . . . . . . . 16
l
2.6 Droga pakietu w ruterze . . . . . . . . . . . . . . . . . . . . . 18
3.1 Algorytmy kolejkowania FIFO . . . . . . . . . . . . . . . . . . 22
3.2 Algorytm kolejkowania TBF . . . . . . . . . . . . . . . . . . . 25
3.3 Algorytm kolejkowania SFQ . . . . . . . . . . . . . . . . . . . 29
3.4 Algorytm kolejkowania GRED . . . . . . . . . . . . . . . . . . 33
3.5 Algorytm kolejkowania CBQ . . . . . . . . . . . . . . . . . . . 34
3.6 Algorytm kolejkowania DSMARK . . . . . . . . . . . . . . . . 37
3.7 Algorytm kolejkowania CSZ . . . . . . . . . . . . . . . . . . . 39
3.8 Przyk hierarchia klas . . . . . . . . . . . . . . . . . . . 48
ladowa
5.1 Stanowisko badawcze . . . . . . . . . . . . . . . . . . . . . . . 59
5.2 Transmisja FTP przy po aczeniu przez ruter . . . . . . . . . . 65
l

5.3 Transmisja FTP przy po aczeniu bezpośrednim . . . . . . . . 65
l

5.4 Transmisja echo przy po aczeniu bezpośrednim . . . . . . . . . 66
l

5.5 Transmisja echo przy po aczeniu przez ruter . . . . . . . . . . 67
l

116
5.6 Transmisja echo przy po aczeniu przez ruter zak ócana przez
l l

pojedyncza transmisje FTP . . . . . . . . . . . . . . . . . . . 68

5.7 Transmisja echo przy po aczeniu przez ruter zak ócana przez
l l

dwie transmisje FTP . . . . . . . . . . . . . . . . . . . . . . . 70
5.8 Transmisja echo przy po aczeniu przez ruter zak ócana przez
l l

trzy transmisje FTP . . . . . . . . . . . . . . . . . . . . . . . 72
5.9 Transmisja echo przy po aczeniu przez ruter zak ócana przez
l l

cztery transmisje FTP . . . . . . . . . . . . . . . . . . . . . . 74
5.10 Transmisja echo przy po aczeniu przez ruter zak ócana przez
l l

druga transmisje echo . . . . . . . . . . . . . . . . . . . . . . . 76

5.11 Transmisja echo przy po aczeniu przez ruter zak ócana przez
l l

druga transmisje echo oraz cztery transmisje FTP . . . . . . . 78

5.12 Transmisja echo przy po aczeniu przez ruter zak ócana przez
l l

druga transmisje echo oraz sześć transmisji FTP . . . . . . . . 80

6.1 Transmisja echo z wykorzystaniem algorytmu PRIO przy do-
datkowej transmisji FTP . . . . . . . . . . . . . . . . . . . . . 83
6.2 Transmisja echo z wykorzystaniem algorytmu PRIO przy do-
datkowych dwóch transmisjach FTP . . . . . . . . . . . . . . 85
6.3 Transmisja echo z wykorzystaniem algorytmu PRIO przy do-
datkowych trzech transmisjach FTP . . . . . . . . . . . . . . . 87
6.4 Transmisja echo z wykorzystaniem algorytmu PRIO przy do-
datkowych czterech transmisjach FTP . . . . . . . . . . . . . 89
6.5 Transmisja echo z wykorzystaniem algorytmu PRIO przy do-
datkowej transmisji echo oraz czterech transmisjach FTP . . . 91
6.6 Transmisja echo z wykorzystaniem algorytmu PRIO przy do-
datkowej transmisji echo oraz dwóch transmisjach FTP . . . . 93
117
6.7 Transmisja echo z wykorzystaniem algorytmu PRIO przy do-
datkowej transmisji echo oraz trzech transmisjach FTP . . . . 95
6.8 Transmisja echo z wykorzystaniem algorytmu PRIO przy do-
datkowej transmisji echo oraz czterech transmisjach FTP . . . 97
6.9 Transmisja echo z wykorzystaniem algorytmu TBF przy do-
datkowej transmisji echo oraz jednej transmisji FTP . . . . . . 99
6.10 Transmisja echo z wykorzystaniem algorytmu TBF przy do-
datkowej transmisji echo oraz dwóch transmisjach FTP . . . . 101
6.11 Transmisja echo z wykorzystaniem algorytmu TBF przy do-
datkowej transmisji echo oraz sześciu transmisjach FTP . . . . 103
6.12 Transmisja echo z wykorzystaniem algorytmu RED przy do-
datkowej transmisji echo oraz dwóch transmisjach FTP . . . . 105
6.13 Transmisja echo z wykorzystaniem algorytmu RED przy do-
datkowej transmisji echo oraz sześciu transmisjach FTP . . . . 107
118
Spis tablic
5.1 Średnia przepustowość przy przesy plików FTP . . . . . . 66
laniu
5.2 Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony klienta . . . . . . . . . . . . . . . . . . . . 67
5.3 Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony serwera . . . . . . . . . . . . . . . . . . . . 67
5.4 Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony klienta przy jednej transmisji FTP . . . . 69
5.5 Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony serwera przy jednej transmisji FTP . . . . 69
5.6 Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony klienta przy dwóch transmisjach FTP . . . 71
5.7 Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony serwera przy dwóch transmisjach FTP . . 71
5.8 Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony klienta przy trzech transmisjach FTP . . . 73
5.9 Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony serwera przy trzech transmisjach FTP . . 73
5.10 Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony klienta przy czterech transmisjach FTP . . 75
119
5.11 Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony serwera przy czterech transmisjach FTP . 75
5.12 Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony klienta przy równoleg transmisji echo . . 77
lej
5.13 Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony serwera przy równoleg transmisji echo . 77
lej
5.14 Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony klienta przy pieciu równoleg transmisjach 79
lych

5.15 Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony serwera przy pieciu równoleg transmi-
lych

sjach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
5.16 Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony klienta przy siedmiu równoleg trans-
lych
misjach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
5.17 Pomiary transmisji dla us echo miedzy klientem i serwe-
lugi

rem mierzone od strony serwera przy siedmiu równoleg
lych
transmisjach . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
6.1 Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony klienta przy jednej równoleg transmisji
lej
FTP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
6.2 Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony serwera przy jednej równoleg transmisji
lej
FTP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
6.3 Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony klienta przy dwóch transmisjach FTP . . . 86
6.4 Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony serwera przy dwóch transmisjach FTP . . 86
120
6.5 Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony klienta przy trzech transmisjach FTP . . . 88
6.6 Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony serwera przy trzech transmisjach FTP . . 88
6.7 Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony klienta przy czterech transmisjach FTP . . 90
6.8 Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony serwera przy czterech transmisjach FTP . 90
6.9 Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony klienta przy równoleg transmisji echo i
lej
dodatkowej transmisji FTP . . . . . . . . . . . . . . . . . . . 92
6.10 Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony serwera przy przy równoleg transmisji
lej
echo oraz jednej transmisji FTP . . . . . . . . . . . . . . . . . 92
6.11 Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony klienta przy równoleg transmisji echo i
lej
dwóch transmisjach FTP . . . . . . . . . . . . . . . . . . . . . 94
6.12 Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony serwera przy równoleg transmisji echo i
lej
dwóch transmisjach FTP . . . . . . . . . . . . . . . . . . . . . 94
6.13 Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony klienta przy równoleg transmisji echo i
lej
trzech transmisjach FTP . . . . . . . . . . . . . . . . . . . . . 96
6.14 Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony serwera przy równoleg transmisji echo i
lej
trzech transmisjach FTP . . . . . . . . . . . . . . . . . . . . . 96
121
6.15 Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony klienta przy równoleg transmisji echo i
lej
czterech transmisjach FTP . . . . . . . . . . . . . . . . . . . . 98
6.16 Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony serwera przy równoleg transmisji echo i
lej
czterech transmisjach FTP . . . . . . . . . . . . . . . . . . . . 98
6.17 Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony klienta przy równoleg transmisji echo i
lej
jednej transmisji FTP . . . . . . . . . . . . . . . . . . . . . . 100
6.18 Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony serwera przy równoleg transmisji echo i
lej
jednej transmisji FTP . . . . . . . . . . . . . . . . . . . . . . 100
6.19 Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony klienta przy równoleg transmisji echo i
lej
dwóch transmisjach FTP . . . . . . . . . . . . . . . . . . . . . 102
6.20 Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony serwera przy równoleg transmisji echo i
lej
dwóch transmisjach FTP . . . . . . . . . . . . . . . . . . . . . 102
6.21 Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony klienta przy równoleg transmisji echo i
lej
sześciu transmisjach FTP . . . . . . . . . . . . . . . . . . . . 104
6.22 Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony serwera przy równoleg transmisji echo i
lej
sześciu transmisjach FTP . . . . . . . . . . . . . . . . . . . . 104
6.23 Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony klienta przy równoleg transmisji echo
lej
oraz dwóch transmisjach FTP . . . . . . . . . . . . . . . . . . 106
122
6.24 Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony serwera przy równoleg transmisji echo
lej
oraz dwóch transmisjach FTP . . . . . . . . . . . . . . . . . . 106
6.25 Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony klienta przy równoleg transmisji echo
lej
oraz sześciu transmisjach FTP . . . . . . . . . . . . . . . . . . 108
6.26 Pomiary transmisji dla us echo miedzy klientem i serwerem
lugi

mierzone od strony serwera przy równoleg transmisji echo
lej
oraz sześciu transmisjach FTP . . . . . . . . . . . . . . . . . . 108
123