7

10. Optimizarea reelelor multipunct10.1. Baze teoretice

10.1.1. Formularea general a problemei

Se examineaz reelele de transfer date (RTD) centralizate specifice pentru reelele de abonat (fig. 8.1) i, de asemenea, pentru reelele centralizate de teleprelucrare a datelor. n asemenea reele mesajele se transmit de la staiile-terminale la un centru i invers (mesaje de rspuns). Centrul poate fi concentrator, nod de comunicaie al reelei de transfer date magistrale, staie-server de teleprelucrare a datelor etc.

n scopul reducerii costurilor cu canalele de comunicaie, pentru transferul datelor n asemenea reele se pot folosi, de rnd cu canalele de transfer date punct-la-punct, i canale multipunct. La un canal multipunct se pot conecta mai multe staii (fig. 8.1). Orice canal punct-la-punct poate fi considerat ca caz particular de canal multipunct - canal multipunct ce conecteaz doar dou noduri.

Problema optimizrii unei reele de transfer date centralizate din canale multipunct const, n linii mari, n urmtoarele. Este cunoscut amplasarea geografic a staiilor-terminale i, de asemenea, rata fluxului de date ntre fiecare staie-terminal i centru (fig. 10.1). Se cere determinarea schemei de conectare a staiilor-terminale prin canale, inclusiv multipunct, cu centrul, care ar asigura extremumul criteriului de optim stabilit.

La optimizarea reelelor de transfer date din canale multipunct, tind, de obicei, s minimizeze costul sumar al canalelor n reea, respectnd anumite restricii. Ca restricii frecvent servesc - durata reinerii pachetelor n reea i asigurarea fiabilitii de funcionare a reelei. n cazul unor probleme complexe, restricia privind durata reinerii pachetelor n reea se nlocuiete cu limitarea de sus a ratei fluxului sumar de pachete pe un canal. La capacitatea dat a canalului, restricia n cauz aduce la limitarea de sus a duratei reinerii pachetelor n reea.

Ca cerine ctre fiabilitatea reelei se folosesc:

asigurarea a dou ci independente de transfer date ntre orice pereche de noduri ale reelei;

numrul staiilor ce se deconecteaz la defectarea oricrui canal de transfer date s nu depeasc o mrime dat . a.

Prima din cele dou cerine de fiabilitate enumerate, se satisface pentru reelele de topologie inel i plas, inclusiv cea complet [2]. A doua cerin este caracteristic pentru reelele din canale de transfer date multipunct i reelele centralizate cu concentratoare de date (vezi p. 9).

O posibil soluie a problemei de optimizare, descrise n linii lari mai sus, este prezentat n figura 10.3.

10.1.2. Formularea matematic a problemei

Formalizat, problema de optimizare a reelelor de transfer date centralizate multipunct const n urmtoarele. Fie c exist n staii-terminale ce trebuie conectate la un centru dat 0 prin canale (n caz general multipunct) pentru transferul de date ntre acestea i sunt cunoscute caracteristicile:

rata a fluxului de date ntre fiecare staie-terminal a reelei i centrul 0;

costul al canalelor de transfer date ntre nodurile ale reelei (j = 0 este centrul reelei). Dac ntre nodurile k i l nu exist sau nu se permite de a avea un segment de canal de transfer date, atunci se consider ; rata maxim admis a fluxului de date pe un canal, fie i multipunct. Pentru a simplifica problema, se presupune c pot fi folosite doar canale de un singur tip (de o anumit capacitate).Se cere ca costul sumar al canalelor reelei s fie minim. Este cunoscut c soluia este o reea de topologie arbore.Unele aspecte ce in de soluionarea problemei de optimizare a reelelor centralizate din canale de transfer date multipunct sunt expuse n pp. 10.1.3 - 10.1.6.

10.1.3. Algoritmi de optimizare a reelelor multipunct

Sunt elaborai mai muli algoritmi de optimizare a reelelor din canale de transfer date multipunct. Acetia pot fi optimali - algoritmi ce asigur soluionarea exact a problemei, i euristici algoritmi ce nu garanteaz obinerea soluiei optime, dar realizeaz o cutare orientat a acesteia. Algoritmii optimali necesit, de regul, efectuarea unui volum mare de calcule i de aceea pot fi folosii pentru soluionarea unor probleme de optimizare de mici dimensiuni. Algoritmii euristici permit gsirea unor soluii, ce se deosebesc, de obicei, de cele optime cu cel mult 5-10% la un volum de calcule mult mai mic.

Dintre algoritmii optimali pentru reelele multipunct, este bine cunoscut algoritmul lui K.M.Chandy i R.A.Russel [1]. Acesta se bazeaz pe metoda ramuri i hotare i permite obinerea topologiei optime a reelei din punctul de vedere al minimizrii costului sumar al canalelor de transfer date ale acesteia. n algoritmul Chandy-Russel, hotarul de jos al criteriului de optimum pentru reea n ansamblu i, de asemenea, pentru subreele aparte la pai intermediari, se determin de arborele de lungime minim pentru cazurile particulare respective. n lucrare este descris mai nti algoritmul Kruskal de determinare a arborelui de lungimre minim (p. 10.1.4), iar apoi i algoritmul Chandy-Russel (p. 10.1.5). Cercetarea practic a acestora se efectueaz conform pp. 10.3, 10.4.

Dintre cei euristici, sunt bine cunoscui algoritmii [1]: al lui L.R.Esau i L.R.Williams, al lui R.C.Prim, al lui J.G.Kruskal. De menionat, c n lipsa restriciilor toi aceti algoritmi asigur obinerea soluiei optime a problemei un arbore de lungime minim (n sensul de cost sumar minim al canalelor reelei). De exemplu, la folosirea algoritmului Kruskal, conectarea segmentelor de canal se ncepe de la segmentele de cel mai mic cost i continu pn cnd toate nodurile vor fi conectate n reea, urmrind, totodat, ca fiecare segment nou ce se include n reea s nu formeze bucle cu segmentele deja incluse.

Dac de luat n consideraie restriciile, algoritmii euristici pot rezulta cu soluii neoptime, deseori chiar diferite de la un algoritm la altul. Experimentele au artat c folosirea algoritmului Esau-Williams asigur, de obicei, o soluie mai reuit [1]. Acest algoritm prevede determinarea celor mai ndeprtate de centru noduri (n sensul costului maxim al canalelor respective) i conectarea lor cu cele mai apropiate de ele noduri, urmrind minimizarea cheltuielilor cu segmentele de canale respective. Algoritmul lui R.C.Prim, din contra, prevede determinarea mai nti a celor mai apropiate de centru noduri (n sensul costului minim al canalelor respective) i conectarea la acestea a celor mai apropiate de ele noduri, apoi conectarea la ultimele a celor mai apropiate de ele noduri i tot aa pn la conectarea n reea a tuturor nodurilor. n ce privete algoritmul Kruskal, dup cum a fost menionat mai sus, n reea se introduc consecutiv cele mai ieftine segmente de canale. Pentru toi aceti algoritmi, un nou segment de canal se va introduce n reea doar dac se vor satisface restriciile acceptate.

n lucrarea de laborator este folosit algoritmul euristic generalizat Kershenbaum-Chou. Algoritmii euristici descrii n form general mai sus i muli ali algoritmi sunt cazuri particulare ale algoritmului Kershenbaum-Chou. Acesta este la rndul su o modificare a algoritmului Kruskal. Deosebirea const n aceea c introducerea consecutiv a segmentelor de canal n reea se efectueaz nu n ordinea creterii costului segmentelor de canale, ci n ordinea creterii diferenei dintre costul segmentelor de canale i ponderea nodurilor ce se conecteaz la acestea (vezi p. 10.1.6).

10.1.4. Determinarea arborelui de lungime minim

Se examineaz problema formulat n p. 10.1.2, dar fr restricii, adic nu se limiteaz rata sumar a fluxurilor de date pe un canal. Este cunoscut c soluia este un arbore de lungime minim (cost sumar minim al canalelor reelei).

Dup cum a fost menionat n p. 10.1.3, pentru determinarea arborelui de lungime minim la interconectarea mulimii date de noduri (staii etc.), pot fi folosii algoritmii Kruskal, Prim, Esau-Williams i Kershenbaum-Chou. Cel mai simplu dintre acetia, din punctul de vedere al laboriozitii calculelor, este algoritmul Kruskal. Acesta i se folosete n lucrare.

Algoritmul Kruskal prevede determinarea, dintre toate cele permise, a segmentului de canal de cea mai mic lungime (cel mai mic cost) i introducerea acestuia n reea, apoi determinarea, dintre cele nc neincluse n reea, a segmentului de canal de cea mai mic lungime i introducerea acestuia n reea i tot aa, pn cnd vor fi interconectate ntr-o reea de topologie arbore toate nodurile (centrul i toate staiile-terminale).

Formalizat, acest algoritm, numit n continuare i Lmin, const n urmtoarele:

Date iniiale: n; , .

Se determin . Dac , atunci se trece la p.

Se introduce canalul ntre nodurile i i j. De asemenea, i se trece la p.

Reeaua este format. Calculul caracteristicilor reelei. Se afieaz informaii viznd structura, caracteristicile canalelor i costul sumar al canalelor reelei.

10.1.5. Algoritmul Chandy-RusselAlgoritmul Chandy-Russel asigur obinerea soluiei optime. Conform acestuia, din mulimea de soluii admise - soluii ce satisfac restricia privind rata limit a fluxului sumar de date pe un canal, se selecteaz anumite submulimi de dimensiuni mai mici i se verific, dac una din acestea asigur atingerea hotarului de jos privind valoarea criteriului de optim, determinat de arborele de lungime minim. Dac hotarul de jos este atins, atunci soluia optim este obinut.

Algoritmul Chandy-Russel folosete i faptul c dac soluia problemei, obinut fr a ine cont de restricii, conine canale (segmente de canale) care conecteaz staii-terminale nemijlocit cu centrul, atunci aceste canale se conin i n soluia problemei obinut lund n consideraie restriciile n cauz. Soluia problemei fr a lua n consideraie restriciile poate fi obinut folosind, de exemplu, algoritmul Lmin (vezi p. 10.1.4).

Formalizat, algoritmul Chandy-Russel consta n urmtoarele:

Date iniiale: n; ; , ; , .

Folosind algoritmul Lmin, se va obine soluia problemei de optimizare a reelei centralizate multipunct fr a lua n consideraie restricia referitoare la rata limit a fluxului de date pe un canal soluia reprezint un arbore de lungime minim. Se nregistreaz valoarea C a criteriului de optim pentru aceasta. De asemenea, C0:=C. Dac soluia obinut satisface restricia problemei (soluia este admis), atunci aceasta este i soluia scontat i se trece la p.

k:=1. Mulimea tuturor variantelor posibile de reea se va diviza n dou submulimi A1 i B. Mulimea A1 include toate variantele posibile de reea ce conin toate conexiunile directe dintre staii-terminale i centrul 0 ale arborelui minim obinut la pasul Mulimea B include toate celelalte variante posibile de reea - variante ce nu intr n mulimea A1. Evident, soluia problemei aparine mulimii A1.

Mulimea Ak se divizeaz n dou submulimi: o nou mulime Ak i mulimea Ak+1. Noua mulime Ak se obine prin adugarea la mulimea de origine Ak a unui nou canal (segment de canal) admis ntre dou noduri, innd cont de respectarea restriciei referitoare la rata limit . Acest canal se specific ca interzis pentru mulimea Ak+1, ceea ce i deosebete aceast mulime de mulimea Ak. Folosind algoritmul Lmin, se calculeaz hotarele de jos Ck i Ck+1 pentru noile mulimi, respectiv Ak i Ak+1. De menionat, c la adugarea unor noi canale ntre noduri, deci odat cu creterea k, hotarul de jos Ck nu poate descrete el rmne neschimbat sau crete. Dintre mulimile , se determin mulimea Aj pentru care hotarul de jos Cj are valoarea cea mai mic C, deci

.

Dac soluia Cj pentru submulimea Aj este o soluie admis (satisface restricia privind ), atunci aceasta este i soluia scontat i se trece la p.

Se substituie reciproc indecii j i k+1, adic perechea se va nota , iar vechea pereche se va nota . De asemenea, k:=k+1 i se trece la p.

Reeaua este format. Se calculeaz caracteristicile reelei. Se afieaz informaii viznd structura, caracteristicile canalelor, costul sumar al canalelor reelei i C0 (costul sumar al canalelor reelei fr luarea n consideraie a restriciei privind ).

10.1.6. Algoritmul Kershenbaum-Chou

Algoritmul euristic generalizat Kershenbaum-Chou este destinat soluionrii problemei formulate n p. 10.1.2, dar necesit date iniiale suplimentare i anume: constatele a i b pentru calcularea ponderii wi a nodurilor ale reelei Folosind algoritmul generalizat Kershenbaum-Chou, se pot obine diferii algoritmi de optimizare a reelelor multipunct, prin stabilirea unei anumite proceduri de calculare a ponderilor ,. Corespondena ntre procedura de calculare a ponderii a nodurilor reelei i algoritmii Kruskal, Prim i Esau-Williams, dealtfel realizat n cadrul algoritmului concretizat descris mai jos, este dat n tabelul 10.1 [1].

n form concretizat, algoritmul generalizat Kershenbaum-Chou consta n urmtoarele:

Date iniiale: n; a; b; ; , ; , .

Se calculeaz valorile ponderii wi a nodurilor reelei

,

unde . Dac se emuleaz algoritmul lui R.C.Prim, atunci w0 := 0. Apoi se determin pentru toate perechile de noduri {i; j} pentru care cij exist ( ), iar restriciile nu se ncalc la stabilirea canalului (segmentului de canal) ntre nodurile i i j; n celelalte cazuri se stabilete . De menionat c, spre deosebire de matricea , matricea poate fi asimetric, deoarece de obicei sau/i .Tabelul 10.1. Corespondena ntre procedura de calculare a ponderii wi, valorile coeficienilor a i b i unii algoritmi de optimizare a reelelor multipunct

AlgoritmulValoarea pentru

Valorile pentru coeficienii a i b

iniialdup conectarea nodului i cu nodul jab

Kruskal0nu se modific0(0)

Primw0=0,

0

(1)

1

Esau-Williams

11

Se determin . Dac , se trece la p.

. Se verific respectarea restriciilor la introducerea canalului ntre nodurile i i j. Dac cel puin una din acestea nu se respect, atunci se trece la p.

Se introduce canalul ntre nodurile i i j.

Dac se emuleaz algoritmul lui R.C.Prim, atunci ; iar dac se emuleaz algoritmul Esau-Williams, atunci .

Se recalculeaz i se trece la p.

Reeaua este format. Calculul caracteristicilor reelei. Se afieaz informaii viznd structura, caracteristicile canalelor i costul sumar al canalelor reelei.

10.2. Scopul lucrrii

Scopul lucrrii const n studierea practic a algoritmilor de optimizare a reelelor de transfer date multipunct: Chandy-Russel, Kruskal, Prim, Esau-Williams i Kershenbaum-Chou.10.3. Coninutul lucrrii

Fie c sunt cunoscute caracteristicile: g, a, b, n, ; i cij pentru nodurile i, j ntre care se permite de a avea canal de transfer date (pentru celelalte perechi de noduri se stabilete cij = ). Aici g indic algoritmul folosit i are valoarea 0 pentru algoritmul Lmin (arbore de lungime minim) i valoarea 1 pentru algoritmul Chandy-Russel. Celelalte valori ale lui g indic algoritmul emulat de ctre algoritmul Kershenbaum-Chou i anume: 2 - pentru algoritmul lui R.C.Prim, 3 - pentru algoritmul Esau-Williams i 4 - pentru toate celelalte cazuri, inclusiv pentru algoritmul Kruskal.

Se cere determinarea structurii reelei centralizate multipunct de transfer date ntre staiile-terminale i centrul 0, care ar asigura minimumul costului sumar C al canalelor reelei, respectnd restricia privind rata limit a fluxului sumar de date pe un canal flux constituit din fluxurile generate de ctre staiile-terminale conectate la acest canal.

Datele iniiale pentru problema de optimizare n cauz sunt prezentate n tabelele 10.2 i 10.3. Pentru canalele (segmentele de canale) interzise, dup cum s-a convenit mai sus, valoarea elementelor respective ale matricei sunt nlocuite cu .Tabelul 10.2. Valorile mrimilor

Vari

antaNodul i al reelei i

12345678910

11,50,50,70,30,70,30,40,80,20,60,1

21,30,60,80,30,60,30,70,40,30,50,4

31,90,80,70,40,30,50,40,70,30,80,2

41,70,40,80,20,60,10,70,50,40,40,4

51,60,70,40,30,50,40,50,20,30,60,3

620,70,50,30,40,40,80,70,40,30,5

71,60,60,40,30,50,70,60,80,30,60,3

81,80,40,70,30,80,20,80,50,40,20,5

Tabelul 10.3. Costul cij al canalelor (segmentelor de canale) de transfer date ntre nodurile reelei

Vari

anta j

i12345678910

1 - 4

5 - 803

13

52

46

55

4

53

12

4

1 - 4

5 - 814

33

46

524

321

2

34

5

1 - 4

5 - 822

65

33

43

51

32

34

1 - 4

5 - 833

14

1

46

35

44

23

5

1 - 4

5 - 845

62

45

63

214

1 - 4

5 - 853

544

155

1 - 4

5 - 863

1

233

2

1 - 4

5 - 874

v54

6

1 - 4

5 - 882

34

1 - 4

5 - 892

3

De menionat, c n cazul unor probleme de mari dimensiuni, volumul calculelor poate fi redus considerabil fr nrutirea, de regul, a soluiei, dac pentru fiecare staie-terminal ca alternative posibile de conectare de indicat doar centrul i cele mai apropiate, n sensul costului minim al segmentelor de canale respective, 5-6 staii-terminale; pentru celelalte cazuri interconectarea nu se admite (segmentele de canale respective se specific ca interzise).Problema se soluioneaz conform algoritmului optimal Chandy-Russel (p. 10.1.5) i algoritmului Kershenbaum-Chou concretizat descris n p. 10.1.6. Cu ajutorul ultimului se emuleaz 7 alternative de algoritmi, inclusiv algoritmii: Kruskal, Prim i Esau-Williams. Cele 7 alternative de algoritmi se determin de valorile indicatorului g i cele ale coeficienilor a i b prezentate n tabelul 10.4.

Tabelul 10.4. Alternative de algoritmi determinate de valorile indicatorului g i a coeficienilor a i bAlternative de algoritmi

123456789

g014443442

a- - 00,7110,3-10-10

b- - 00,3110,711

10.4. Ordinea ndeplinirii lucrrii

ndeplinirea lucrrii prevede urmtoarele aciuni:

1. Studierea problemei de optimizare a reelelor de transfer date multipunct i a algoritmilor Chandy-Russel, Kruskal, Prim, Esau-Williams i Kershenbaum-Chou de soluionare a acesteia (p. 10.1).

2. Concretizarea problemei pentru varianta de date iniiale indicat de profesor din cele 8 variante ce se conin n tabelele 10.2 i 10.3. Dintre segmentele de canale de interconectare a fiecrei staii-terminale la alte noduri ale reelei (centru sau alte staii-terminale), de indicat ca interzise cele cu costuri mai mari, astfel ca permise s rmn doar segmentul de canal ctre centru i, de asemenea, segmentele ctre alte 5 staii-terminale.

3. Concretizarea celor 9 alternative de algoritmi, ce se propun pentru rezolvarea problemei, inclusiv a celor 7 cazuri particulare ale algoritmului Kershenbaum-Chou, determinate de valorile pentru indicatorul g i coeficienii a i b din tabelul 10.4.4. Folosind opiunea rilab10 a programului rilab ce realizeaz algoritmii Chandy-Russel i Kershenbaum-Chou, se vor obine soluiile problemei de optimizare a reelei de transfer date multipunct pentru varianta de date iniiale de la etapa 2 i fiecare din cele 9 alternative de algoritmi de rezolvare a problemei de la etapa 3. Astfel, n total pentru una i aceeai problem, dar folosind 9 alternative de algoritmi, se vor obine 9 soluii, o parte din care sau chiar toate pot s coincid. Una din soluii (cea pentru alternativa 0) este arborele de lungime minim i poate s nu fie admis, din cauza nerespectrii restriciei privind rata limit a fluxului sumar de date pe un canal.

5. Analiza soluiilor obinute, inclusiv:

5.1) construirea structurii topologice a reelei de transfer date obinute la etapa 4 pentru fiecare din cele 9 alternative de algoritmi;

5.2) compararea soluiilor obinute ntre ele dup valoarea costului sumar C al canalelor de transfer date ale reelei.

6. Perfectarea lucrrii n form de referat ce va include: foaia de titlu; formularea problemei; varianta de date iniiale n conformitate cu etapele 2 i 3 din aceast seciune; rezultatele calculelor (etapa 4), analiza acestora i concluziile de rigoare (etapa 5).

10.5. Prezentarea i susinerea lucrrii

Lucrarea se prezint profesorului i se susine la calculator n mod practic.

Referine

1. M.Schwartz. Computer communication networks. Design and analysis. Prentice-Hall Inc, 1987.2. I.Bolun. Macrosinteza reelelor de calculatoare. Chiinu: Editura ASEM, 1999. 265 p.

2

2

Figura 10.3. O posibil soluie pentru problema din figura 10.2.

Staii-terminale

0

Figura 10.1. Amplasarea geografic a staiilor-terminale i a centrului 0 ce trebuie interconectate printr-o reea de transfer date centralizat multipunct.

0

Cile de transfer date ntre dou noduri ale reelei se numesc independente, dac acestea nu conin elemente (canale, noduri) comune, cu excepia a nsui nodurilor marginale n cauz.

171

_1092094954.unknown

_1092255363.unknown

_1097783104.unknown

_1097786145.unknown

_1097798973.unknown

_1152706744.unknown

_1152706906.unknown

_1152707171.unknown

_1152706753.unknown

_1097904235.unknown

_1097786295.unknown

_1097786610.unknown

_1097786628.unknown

_1097786593.unknown

_1097786282.unknown

_1097785462.unknown

_1097785516.unknown

_1097784275.unknown

_1097784334.unknown

_1097784159.unknown

_1092399855.unknown

_1092400756.unknown

_1092400911.unknown

_1096889926.unknown

_1096691229.unknown

_1092400826.unknown

_1092400308.unknown

_1092400218.unknown

_1092400299.unknown

_1092400130.unknown

_1092255883.unknown

_1092341911.unknown

_1092255848.unknown

_1092255372.unknown

_1092253707.unknown

_1092254354.unknown

_1092254652.unknown

_1092255174.unknown

_1092255190.unknown

_1092255309.unknown

_1092255012.unknown

_1092255004.unknown

_1092254465.unknown

_1092254225.unknown

_1092254304.unknown

_1092254131.unknown

_1092142772.unknown

_1092142897.unknown

_1092142917.unknown

_1092143960.unknown

_1092142863.unknown

_1092095105.unknown

_1092095124.unknown

_1092076296.unknown

_1092076859.unknown

_1092083928.unknown

_1092083286.unknown

_1092076597.unknown

_1092075075.unknown

_1092075219.unknown

_1092074480.unknown

_1092074697.unknown

_1092074543.unknown

_1092074248.unknown