63
ANALIZA ZMOGLJIVOSTI MEHANIZMA ZA KONTROLO PRETOKA V MREŽAH ZA PRENOS PODATKOV
INFORMATICA 3/91
Keywords: packet-switched data networks, window flow-control, queueing network, performance analysis
Marjeta Pučko Institut Jožef Stefan Jamova 39, 61111 Ljubljana
Povzetek
V prispevku je opisan strežni model virtualne zveze in mehanizem za kontrolo pretoka po metodi okna kot nadgradnja tega modela. Predstavljeni sta dve različici mehanizma za kontrolo pretoka po metodi okna. Poseben poudarek je na analizi zmogljivosti obeh različic mehanizma, izdelana pa je tudi primerjava med njima glede na najpomembnejša merila za zmogljivost.
Abstract
In this paper, a virtual circuit model, represented by the queueing network is described. On this model, the window control mechanism is superimposed. Two alternatives of the window flow-control mechanism are discussed. A central issue in this discussion is the performance analysis. As a result, both alternatives are compared in terms of the most important performance measures.
1 Uvod
Nalogi mrežnega nivoja v komunikacijski arhitekturi OSI sta poleg izvajanja drugih funkcij tudi usmerjanje in kontrola pretoka. Obe funkciji zagotavljata pravilno dostavo paketov od izvornega do ponornega vozlišča mreže za. prenos podatkov. Procedure za kontrolo pretoka, vključene v operacije na mrežnem nivoju, preprečujejo, da bi prišlo do nasičenja. V primeru, da bi do nasičenja prišlo, bi se to pokazalo na dva načina:
•	časovne zakasnitve bi se izrazito povečale,
•	propustnost, merjena v številu paketov na enoto časa, bi izrazito upadla.
Ob dovolj velikem povečanju bremena se napolnijo vsi izravnalniki, promet se ustavi in propustnost pade na ničlo. V takšnem primeru pride do smrtnega objema (deadlock). Če so mehanizmi za kontrolo pretoka zasnovani pravilno, do smrtnega objema ne more priti.
Pri izdelavi analize zmogljivosti mehanizma za kontrolo pretoka moramo najprej zgraditi model virtualne zveze. V strežnem modelu virtualne
zveze, ki je opisan v naslednjem razdelku, bomo uporabili neskončne izravnalnike, saj bi uporaba končnih (sicer realnih izravnalnikov) analizo zelo otežila. V nadaljevanju bomo model virtualne zveze nadgradili z modelom mehanizma za kontrolo pretoka po metodi okna in določili njegove značilnosti glede propustnosti in časovnih zakasnitev, ki predstavljata najpomembnejši standardni merili za zmogljivost mrež za. prenos podatkov.
2 Model virtualne zveze
Virtualna zveza (VC) pokriva M store-and-forivard vozlišč od izvora do ponora, v mreži s preklapljanjem paketov. V modelu takšno virtualno zvezo predstavimo z M čakalnimi vrstami. Parameter A pove povprečno hitrost prihajanja paketov v virtualno zvezo (porazdeljena je po Pois-sonu). Zaradi enostavnosti vsako vrsto servisira en sam strežnik.
Prehodno zakasnitev zanemarimo. Izvora zakasnitve sta čas čakanja v vrsti in oddajni čas, ki je odvisen od dolžine paketa in kapacitete oddajne linije. Za ¿-to čakalno vrsto v virtualni zvezi
64
M + 1
izstope iz čakalnih vrst, porazdeljene po Poissonu. Po Poissonu porazdeljeni prihodi v naslednjo vrsto pa zopet zagotavljajo M/M/l karakteristiko. Naš model virtualne zveze je ob uporabi naštetih predpostavk le poseben primer odprte mreže čukalnih vrst v produktni obliki, kar pomeni, da verjetnost stanja v celotni mreži čakalnih vrst lahko zapišemo kot produkt verjetnosti stanj za posamezne vrste.
3 Model s premičnim oknom
Slika 1: Zaprti sistem
(1 < i < M) je oddajna hitrost oz. kapaciteta enaka /i,- paketov/sek. Zanemarimo tudi vpliv ponovnih oddaj. Bolj splošen (veljavnejši) model celotne mreže bi dobili, če bi med seboj povezali čakalne vrste za posamezne virtualne zveze, vendar bi kompleksnost analize s tem ustrezno narasla.
Kljub enostavni obliki je model še vedno izredno težko analizirati, dokler ne sprejmemo še ene dodatne predpostavke. Količina 1 //i; v ¿-tem vozlišču predstavlja povprečni čas za oddajo paketa. Predpostavimo, da je dolžina paketa, ki potuje skozi kaskado čakalnih vrst, izbrana naključno in neodvisno vsakič, ko paket pride v novo čakalno vrsto. To predpostavko o neodvisnosti je prvi uporabil L. Kleinrock [KLEI 74]. Eden od razlogov za veljavnost predpostavke je tudi ta, da so "tokovi" paketov na dani izhodni povezavi pogosto multipleksirani, tako da je prispevek enega, toka paketov majhen v primerjavi z ostalimi. Če imajo dolžino vsi enako porazdeljeno, se lahko nek paket v katerikoli vrsti obnaša tako, kot da bi se njegova dolžina spreminjala naključno. Simulacije, izvedene za primerjavo zmogljivosti različnih kontrolnih mehanizmov za eno virtualno zvezo po metodi okna, so pokazale [SCI1VV 87], da ta predpostavka velja, če M ni prevelik. Za večje M(M > 6) se rezultati analize bistveno razlikujejo od rezultatov simulacije.
Če sprejmemo predpostavko o neodvisnosti in eksponentno porazdelitev dolžine paketov, analiza postane izvedljiva. Model ene virtualne zveze postane kaskada neodvisnih M/M/1 vrst. Eksponentna porazdelitev dolžine paketov pomeni tudi
Ko že imamo zgrajen model virtualne zveze, se pojavi vprašanje, kako na vrh tega modela postavimo še mehanizem za kontrolo pretoka.
Najprej določimo mehanizem - to je kontrola s premičnini oknom. Mehanizem deluje tako, da je vsak paket posebej potrjen takoj, ko doseže ponor. N predstavlja velikost okna. Če je bilo oddanih že vseh N paketov, do izvora pa še ni prispela nobena potrditev, oddajnik preneha z oddajanjem paketov. Ko potrditev doseže izvor, pomakne oddajno okno za 1 naprej in omogoči oddajo naslednjega paketa.
Predpostavimo, da se potrditve pošiljajo nazaj k izvoru z najvišjo prioriteto. Ta predpostavka za primer potrditev X.25 vmesnika DTE-DCE sicer ne velja, velja, pa za IBMovo SNA. Kadar to ne velja, je analiza izvedljiva tudi tako, da virtualno zvezo predstavimo kot zaporedje čakalnih vrst. Predpostavka o pošiljanju potrditev z najvišjo prioriteto zagotavlja najboljši primer glede zmogljivosti.
S to predpostavko zanemarimo tudi časovno zakasnitev pri potrditvah v smeri od ponora do izvora, kar nam omogoča, da zgradimo model s premičnim oknom, nadgrajen na modelu virtualne zveze, kot model zaprtega sistema. Izvor in ponor sta povezana z dodatno čakalno vrsto M + 1 s hitrostjo servisiranja A. Po zaprtem sistemu kroži fiksno število paketov N. Kadar je vseh N paketov na virtualni zvezi (v zgornjih M vrstah s slike 1, je vrsta M + 1 prazna. Takoj, ko en od iV-tili paketov doseže ponor, se pojavi v vrsti M -f 1 (zaradi predpostavke, da zakasnitve pri potrditvah ni). Izvor sedaj lahko pošilja pakete s hitrostjo A. Na podlagi tega. modela lahko določimo časovno zakasnitev od izvora do ponora in propustnost tega mehanizma za kontrolo pretoka.
Brez kakršnekoli nadaljnje analize lahko podamo oceno kvalitete mehanizma s premičnim
65
tonov teorem.
u(n)
Slika 2: Uporaba Nortonovega teorema, za računanje propustnosti
oknom. Pri naraščajoči hitrosti prihajanja paketov se bodo vrste v vozliščih vzdolž virtu-alne zveze začele polniti, časovne zakasnitve bodo naraščale in prišlo bo do nasičenja. Mehanizem za kontrolo pretoka preprečuje, da bi bilo na virtualni zvezi več kot N paketov hkrati. Čim manjši je N, tem manjše so tudi časovne zakasnitve. Cena, ki jo je treba plačati za to, pa je ustrezno manjša propustnost. Takšno razmerje se pojavlja v vseh mehanizmih, ki preprečujejo nasičenje. Najboljša je torej takšna kontrolna shema, ki pri dani propustnosti zagotavlja najmanjšo časovno zakasnitev oz. najvišjo propustnost pri dani časovni zakasnitvi. Jasno je, da sta oba parametra odvisna tudi od M (števila čakalnih vrst od izvora do ponora). S povečevanjem M narašča minimalna časovna zakasnitev, ker mora vsako vozlišče paket shraniti in poslati naprej, manjša pa se propustnost, ker narašča minimalni čas za prehod skozi mrežo.
Če N še naprej povečujemo, se povečevanje propustnosti ustavi pri neki maksimalni vrednosti, časovna zakasnitev pa še naprej narašča. Torej obstaja neka optimalna vrednost N, kjer se propustnost dovolj poveča, časovna zakasnitev pa se še ne poveča preveč. Takšna vrednost je N = M.
V nadaljevanju se moramo zateči h kvantitativni analizi, kar zahteva vpeljavo metod za analizo zaprtega sistema s slike 1. Ta zaprti sistem je le poseben primer zaprte mreže čakalnih vrst. Rešitve so zopet v produktni obliki - podobno kot za odprto mrežo čakalnih vrst. Določiti želimo zmogljivost mehanizma s premičnim oknom, ki jo predstavljata propustnost in časovna zakasnitev. Nanašata se na celotno virtualno zvezo. Časi čakanja v vrsti in dolžina vrst nas v tem primeru posebej ne zanimajo, zato lahko uporabimo Nor-
3.1 Nortonov teorem
Teorem je sicer imenovan tudi dekompozicijski teorem za mreže čakalnih vrst, prvi so ga dokazali K.M. Chandy, U. Ilerzog in L.S. Woo [SCHW 87]. Velja za mreže s produktno obliko, M-stopenjski model virtualne zveze z eksponentnimi strežniki je le poseben primer.
Če je mreža s čakalnimi vrstami produktne oblike, lahko celotno mrežo predstavimo z eno vrsto med dvema točkama. "Kratkostično" propustnost u(n) lahko določimo z rekurzivnimi metodami, ki jih bomo opisali pozneje. Nortonovemu modelu lahko določimo še bolj poenostavljen ekvivalentni model,kjer vrsta s hitrostjo servisiranja u(n) in stanjem vrste n (število žalitev v vrsti) nadomešča celotno mrežo med dvema točkama. Verjetnosti stanja sta v obeh primerih enaki.
N je celotno število paketov v zaprtem sistemu. Za stanje te vrste veljajo enačbe splošnega rojstno-smrtnega procesa z intenzivnostjo rojevanja zahtev A in intenzivnostjo umiranja zahtev oziroma hitrostjo servisiranja u(n). Verjetnost, daje vrsta v stanju n, je enaka.
p„ - p0\n/ nu(¿)
(1)
¿=i
Verjetnost, da je vrsta prazna p0, je določena z običajnim pogojem
N
X> = 1
(2)
n = 0
Preostane nam le še to, da povežemo uporabo Nortonovega teorema in mehanizma s premičnim oknom. Za začetek analizo še malo poenostavimo s tem, da določimo vsem hitrostim servisiranja f.ix, ...,j.iM isto vrednost. Za ta primer sedaj velja
u(n) = n
n + (M - 1)
(3)
n paketov je porazdeljenih v M vrstah (slika 2). Propustnost n(u) bo vedno enaka ali manjša od /i. Podana pa je s produktom
u(n) = ¡.t ■ verjetnost(vrsta ni prazna) (4)
66
Zaradi simetrije so vse vrste identične in verjetnost, da vrsta ni prazna, je enaka za vse vrste. S pomočjo enačbe 3 dobimo
(5)
kjer je izkoristek p = A//x, verjetnost p0 pa
7 = uin)p<>
(T
71 = 1
N
£(T) = £(n)/7 = £>„/7
71 = 1
7 = u(N)
Nfi
N + (M - 1) za časovno zakasnitev pa
začne naraščati počasneje kot raste N. Karakteristika je naslednja:
pE(T)
M
1 -(P/M)
A
oo
(H)
(6)
Propustnost 7 virtualne zveze s kontrolo pretoka s pomočjo okna je podana s povprečjem vseh N možnih hitrosti servisiranja:
Po Littlovi formuli [KLEI 74] je časovna zakasnitev E(T) na virtualni zvezi enaka razmerju med povprečnim številom paketov E(n) in propustnostjo 7.
(8)
V primeru A —> 00 lahko analizo zmogljivosti tega mehanizma za kontrolo pretoka tudi nekoliko poenostavimo. Za ta primer velja E{n) = za propustnost velja
, A ->■ 00 (9)
E[T) = N/j = [M - 1 + N]/fi (10)
Medsebojna odvisnost propustnosti in časovne zakasnitve pri kontroli pretoka s premičnim oknom je prikazana na sliki 3 (primerjava z drugim mehanizmom za kontrolo pretoka - potrjevanjem za celotno okno).
Minimalna časovna zakasnitev E(T) = M/p, se pojavlja pri N = 1 (na sliki je pE(T) = 3 za M = 3). S povečevanjem velikosti okna N časovna zakasnitev proporcionalno narašča, prav tako tudi propustnost 7. Ko propustnost doseže vrednost p,
Enačba je veljavna seveda samo za tiste N, ki so cela števila. Čim bolj se 7 približuje p, (s povečevanjem N), tem bolj imajo majhne spremembe 7 za posledico večje spremembe E(T).
Kakšna naj bi bila vrednost N ? Različni kriteriji vodijo k isti vrednosti, to je N = M — 1. Naraščajoči N se odraža v enakomernem naraščanju časovne zakasnitve in hitrem upadanju propustnosti. Ustrezen kriterij za iskanje "dobre" vrednosti N predstavlja iskanje maksimalne vrednosti razmerja 7/E(T) ali njegovega normalizi-ranega ekvivalenta 7/ p/pE{T), imenovanega tudi "moč" sistema. V primeru, ko je A = p, je bolje izbrati N = M.
Ni nujno, da mora biti mehanizem za kontrolo pretoka takšen, daje potrjen sprejem vsakega paketa posebej. Število potrditev je mogoče tudi zmanjšati tako, da sprejemnik pošlje potrditev za vse predhodne nepotrjene pakete iz enega okna hkrati.
4 Model s potrjevanjem za celotno okno
V primeru modela s potrjevanjem za celotno okno ni potrebno potrjevanje za vsak prispeli paket. Sprejemnik lahko zadrži potrjevanje, dokler ni pripravljen na sprejem paketov, nato pa z eno potrditvijo potrdi sprejem vseh prispelih paketov. Prednost takšnega načina potrjevanja je v možnosti usklajevanja hitrosti oddajnika in sprejemnika ter zmanjšanju števila, potrditev.
Pri primerjavi tega modela z modelom s premičnim oknom nas zanima propustnost v eks-tremnem primeru, ko sprejemnik potrjuje sprejem vseh paketov iz enega okna hkrati.
Ker so velikosti okna v različnih mehanizmih za kontrolo pretoka lahko različne, v tem primeru označimo velikost okna z w. Izravnalnik tu shrani w—l paketov. Ko prispe še to-ti paket, sproži potrditev za vseh w paketov in postavi števec paketov C (z vrednostjo 0) zopet na vrednost w. C pravzaprav predstavlja čakalno vrsto z intenzivnostjo prihajanja zahtev A. Izravnalnik w pomeni tudi
67
10
7-
ME(T)
6-
fiksno okno, potrditev no koncu
premično okno, potrditev za vsak paket
0.9
Slika 3: Odvisnost propustnosti in časovne zakasnitve, M = 3, A —► oo
edino razliko v primerjavi z modelom s premičnim oknom, ki pa analizo propustnosti zelo oteži. Vsebina izravnalnika w se namreč prestavi v čakalno vrsto naenkrat, zato lastnost produktne oblike za to mrežo ne velja več in uporaba Nortonovega teorema ne zagotavlja eksaktne rešitve. Če Nortonov teorem kljub temu uporabimo, pa lahko dobimo aproksimacijo [KURO 88].
Za predstavitev stanja strežne vrste C in izravnalnika w potrebujemo števili i in j, za kateri velja n = w - (i + j). Sedaj lahko zapišemo dvodimenzionalne ravnotežne enačbe za verjetnosti stanj p^. Sistem enačb (njihovo število je reda w2/2) rešujemo numerično.
V nekaterih primerih lahko računanje tudi poenostavimo, takšna primera sta posebni vrednosti A, A —> oo in A = p,. V primeru največjega prometa, A oo, dvodimenzionalne enačbe (odvisne od i in j) prevedemo na enodimenzionalne (odvisne samo od j). Računamo le verjetnosti stanj pj izravnalnika w oziroma zgornje vrste, pn = pw-j:
u(w)p0 = u( l)pw-! u(w - 1 )pi = u{w)p0
Za u(n) velja enako kot pri modelu s premičnini oknom (enačba 3)
u(n) = 7i-

n + (M - 1) Če rešimo enačbe za pj, dobimo
Pj/Po = u(w)/u(w - j) glede na vsa stanja pa
(w-j) + (M- 1)
P i =
(w - j)[w + (M - 1)TW] kjer je Tw končna vsota
^ = £7
j=i J
(12)
(13)
(14)
Enačbo 13 uporabimo pri računanju propustnosti 7 in povprečne zakasnitve E(T). Propustnost je podana z enačbo
7 =
pLW
[tu + (M - 1 )TW]
(15)

= u(2)pw_2
Ob primerjavi te enačbe z ustrezno enačbo za propustnost pri modelu s premičnim oknom
68
(enačba 9) lahko vidimo, da imata povsem enako obliko, le (M - 1 )/N je nadomeščen z (M -1 )Tw/w.
Pri določanju povprečne časovne zakasnitve zopet uporabimo Littlovo formulo. Naj bo p(n) verjetnost stanja Nortonovega ekvivalenta virtu-alne zveze. Potem je povprečna časovna zakasnitev enaka
ki jo je treba plačati za to, pa je nižja propustnost. Pojavi se vprašanje, ali je mogoče povečati propustnost do te mere, da bi bila skoraj enaka kot pri modelu s premičnim oknom, obenem pa bi obdržali prednost ene same potrditve za celotno okno. Kompromis med obema rešitvama je mogoče doseči, primer takšnega mehanizma je IBM SNA mehanizem za kontrolo pretoka.
E(n) = £ np(n) = 1
n = l	^
1 + W
+ (M- 1)
(16)
6 Viri
[KING 90]
kjer seveda velja n = w — j in p(n) = pw-„, njena normalizirana vrednost pa je podana z enačbo	[KLEI 74]
**<*■> " ^ - « ■«
1 +
1 -(- W
(17)
Če to enačbo zopet primerjamo z ustrezno enačbo pri modelu s premičnim oknom, ugotovimo, da smo velikost okna N nadomestili z (1 + w)j2. Ko primerjamo zmogljivost obeh mehanizmov (slika 3), lahko vidimo, da zmogljivost mehanizma s potrjevanjem za celotno okno močno zaostaja za zmogljivostjo mehanizma s premičnim oknom. Razlika med njima s povečevanjem okna postaja še večja. Pri primerjavi obeh mehanizmov bi podobne rezultate dobili tudi v primeru A = /.i. V primeru mehanizma s premičnim oknom predstavlja optimalno velikost okna N — M, v primeru mehanizma s potrjevanjem za celotno okno pa w = 2M — 1.
5 Zaključek
[KLEI 76]
[KONH 80]
[KURO 88]
[PUCK 90]
[SCHW 87]
[STAL 91]
Predstavitev virtualne zveze z mrežo čakalnih vrst in njena nadgradnja z modelom mehanizma za kontrolo pretoka po metodi okna nam omogočata učinkovito analizo zmogljivosti. Ob primerjavi najpomembnejših meril za zmogljivost vidimo, da zmogljivost mehanizma s potrjevanjem za celotno okno močno zaostaja za zmogljivostjo mehanizma [STUC 85] s premičnim oknom. Mehanizem s potrjevanjem za celotno okno ima sicer dve pomembni prednosti: manjše število potrditev in možnost usklajevanja hitrosti oddajnika in sprejemnika. Cena,
P.King: Computer and Communications Systems Performance Modeling, Prentice - Hall, 1990,
L.Kleinrock: Queueing Systems, Vol. I: Theory, John Wiley & Sons, 1974,
L.Kleinrock: Queueing Systems, Vol. II: Computer Applications, John Wiley & Sons, 1976,
A.G.Ivonheim:	A Queueing Analysis of Two ARQ Protocols, IEEE Trans, on Comm., COM-28, no. 7, July 1980, pp. 1004 - 1014,
J.F.Kurose, H.T.Mouftah: Computer- Aided Modeling, Analysis, and Design of Communication Networks, IEEE Journal on Selected Areas in Communications, vol. 6, no. 1, January 1988, pp. 130 - 145,
M.Pučko: Propustnost javnih X.25 mrež za prenos podatkov, IJS DP-5799, Ljubljana, marec 1990.
M. S chwar t z : Telecommun ication Networks: Protocols, Modeling and Analysis, Addison - Wesley, 1987,
W.Stallings: A practical guide to queueing analysis, Byte, February 1991, pp. 309 - 316,
B.W.Stuck,	E.Arthurs: Computer and Communications Systems Performance Modeling, Prentice - Hall, 1985.