simularea retelelor - staff.cs.upt.ro

51
Simularea retelelor

Upload: others

Post on 08-Dec-2021

14 views

Category:

Documents


0 download

TRANSCRIPT

Page 1: Simularea retelelor - staff.cs.upt.ro

Simularea retelelor

Page 2: Simularea retelelor - staff.cs.upt.ro

Emulare vs. simulare

• Emulare: reproducerea cit mai exacta a functionarii unui dispozitiv sau sistem– In principiu sistemul emulat poate fi inlocuit cu sistemul care il emuleaza

• Sistemul real este in general mai rapid decit sistemul care il emuleaza

• Exemplu: emularea unui microprocesor

– Emularea retelelor • se realizeaza in general prin descrierea (intr-un limbaj formal sau alt

formalism) a protocoalelor componente, conform cu specificatiile care descriu acele protocoale

• Simulare: descrierea functionarii unui sistem sau dispozitiv la un nivel de reprezentare mai abstract si mai putin precis– Se pun in evidenta anumite proprietati ale sistemului

– Se neglijeaza alte proprietati, care nu par sa prezinte importanta sau sa influenteze aspectele de performanta investigate

• Exemplu: daca ne intereseaza performanta unor algoritmi (de ex de scheduling) la nivel de legatura de date, se pot ignora unele protocoale de nivel superior (transport, aplicatie) sau mobilitatea utilizatorilor unei retele mobile

• Totusi, partile pe care le ignoram in modelul de simulare pot influenta functionarea in cazul real (de ex la retelele mobile protocolul de transport TCP interactioneaza, nu intotdeauna fericit, cu protocoalele de nivel inferior

Page 3: Simularea retelelor - staff.cs.upt.ro

Exemplu de emulator: GPRSimGPRSim: emulator de

GPRS dezvoltat la Univ

din Aachen de-a lungul

mai multor ani.

Protocoalele de GPRS

specificate in SDL

Utilizeaza o biblioteca pt

a translata specificatiile

SDL in C++

Are facilitati de a genera

diverse tipuri de trafic

Are facilitati de

vizualizare si prelucrare

a datelor

Performantele sale au

fost comparate cu

primele retele GPRS

reale.Figura preluata din [Stuckmann_ICN01]

Page 4: Simularea retelelor - staff.cs.upt.ro

Simulatoare de retele

• Permit dezvoltarea de modele de simulare in domeniul retelelor si nu numai– Se pot studia si performantele unor linii de productie

(de automobile sau hamburgheri ☺)

– La un model de simulare se pune problema cit de detaliat trebuie sa fie

– Raspunsul difera si in functie de scopul modelului:• Academic: de obicei mai putin detaliat (lucreaza echipe mai

mici sau un singur om), axat pe problema/problemele studiata/studiate

• Industrial: gradul de complexitate creste pe masura ce sistemul modelat se apropie de utilizarea comerciala, ajungindu-se la emulare si prototip.

Page 5: Simularea retelelor - staff.cs.upt.ro

Simulatoare comerciale vs

necomerciale• Comerciale

– Dezvoltate de firme pentru a fi vindute (de obicei sint scumpe)

– Ofera:• garantii de performanta

• Eventual generarea de cod (C, C++, VHDL, etc) din model

• Exemple: SES/Workbench (de la Hyperformix), OPNET

• Pot avea versiuni academice ieftine sau gratuite (de ex OPNET)

• Cursuri de utilizare (uneori documentatia care le insoteste e greu de utilizat fara astfel de cursuri !)

• Gratuite (Free)– De obicei dezvoltate de cercetatori sau la universitati in scop de

cercetare

– Apoi se formeaza o comunitate de utilizatori / dezvoltatori• De obicei o comunitate mare inseamna un simulator de succes !

– Pot fi : • Comparabile ca performanta cu cele comerciale

• Foarte populare si acceptate de comunitatea academica (de ex pt publicarea rezultatelor simularii la diverse conferinte)

• Exemple: ns2, NS3, cnet, OMNeT++,

• Pot avea versiuni comerciale ! (de ex OMNeT++)

Page 6: Simularea retelelor - staff.cs.upt.ro

Simulatoare: utilizare

• Exista simulatoare care ofera module cu functii predefinite, care se pot parametriza.– Exemple:

• module surse (generatoare) de date– Se parametrizeaza rata de generare a datelor (distributie de

probabilitate, valori medii, etc)

• Module server:– Se parametrizeaza rata de servire (distributie de probabilitate, valori

medii, etc)

– Sint usor de utilizat, mai ales pt modele simple sau de catre “nespecialisti”

– De obicei sint foarte “grafice” (iconuri ce se pot parametriza)

– Daca se doreste modificarea functionarii, acest lucru poate deveni extrem de complicat si dificil:

• De ex e nevoie sa se modifice anumite functii interne, nu neaparat bine documentate !

• Exemplu: SES/Workbench

• De obicei situatia apare la simulatoare comerciale

Page 7: Simularea retelelor - staff.cs.upt.ro

Simulatoare: utilizare• Alte simulatoare sint “open source”:

– De obicei sint mai putin “grafice”, desi au si o parte grafica • Utilizatorul trebuie sa scrie cod, nu doar sa modifice cu mouse-ul niste valori /setari

• De obicei codul e intr-un limbaj de uz general (C++, Java)

• Uneori si legarea modulelor se face in mod “text”

• Se adreseaza mai degraba unor utilizatori ‘de specialitate’, dispusi si capabili sa programeze

• La nevoie se pot modifica si functiile de baza (de ex nucleul de simulare), dar poate fi o actiune laborioasa si riscanta

• De obicei exista exemple de module (generator, server, sink, etc), al caror cod serveste drept exemplu si poate fi modificat si extins.

• Exemplu: OMNeT++

• Simulatoare apropiate de emulatoare (ns2, NS3 ):– Implementeaza protocoale reale (ex. TCP, IP, UDP, etc) intr-un format intern,

modelul de simulare urmind sa “asambleze” protocoalele respective

– Pot produce simulari lungi, dar foarte precise, ale caror rezultate pot fi mai usor acceptate de comunitatea stiintifica

– Pot introduce limitari (nu e implementat un anumit protocol, modul, extensie de protocol sau modul, etc).

– OMNeT++ are framework-uri ce implementeaza protocoale (MANET, INET)

• Simulatoare didactice (cnet): simplificate, greu de extins, programare greoaie.

Page 8: Simularea retelelor - staff.cs.upt.ro

Numere aleatoare

• Simulatoarele includ generatoare de numere

aleatoare conform cu diferite distributii de

probabilitate (uniforma, exponentiala, etc)

– De obicei se genereaza nr. pseudo-aleatoare

– Daca se repeta simularea se genereaza aceleasi

numere “aleatoare”!

• E util pt a putea compara rezultatele mai multor simulari

• Daca se doreste schimbarea setului de nr aleatoare

generate, acest lucru trebuie specificat explicit (se alege un

alt “seed” pt algoritmul de generare a numerelor aleatoare

Page 9: Simularea retelelor - staff.cs.upt.ro

Rezultatele simularii

• De obicei simulatoarele au tool-uri pentru prelucrarea rezultatelor simularii– Se pot face calcule statistice pt diverse marimi (valori medii,

minime, maxime, deviatia standard)

– Se pot face “trace”-uri: adica se colecteaza valorile unei anumite marimi (intirziere, nr de pachete pierdute, etc) pe parcursul simularii sau intre anumite momente de simulare

• Aceste trace-uri se vor reprezenta apoi grafic de tool-uri atasate simulatorului sau de tool-uri de uz general

• Fisierele obtinute pot deveni foarte mari !

– Formatul fisierelor cu rezultate (trace-uri, statistici) sint specifice simulatorului (chiar daca sint de tip text in general) si pot necesita post-procesare (cu Pearl, etc)

• Poate fi mai convenabil ca utilizatorul sa isi colecteze rezultatele simularii in formatul dorit de el, urmind a fi prelucrate apoi cu programe gen Gnuplot, Excel, etc.

Page 10: Simularea retelelor - staff.cs.upt.ro

Validarea rezultatelor• Are loc intii o faza de punere la punct a modelului de simulare

– Se foloseste mult interfata grafica

– Se urmaresc diverse marimi

– E bine sa se afiseze cit mai multe mesaje de genul (“am ajuns in modulul X, valoarea parametrului Y este…”)

– La inceput e bine sa se lucreze determinist, evitind numerele aleatoare

– Se construiesc si se verifica diverse scenarii de simulare, cazuri limita, etc

– Se elimina erorile, pina cind modelul pare a functiona asa cum ne dorim

• Se trece la culegerea rezultatelor– De obicei se lucreaza in mod “batch”, nu grafic

– Se elimina mesajele inutile, care doar incetinesc simularea

– Se fac simulari lungi, pt a vedea daca modelul este stabil

– Se interpreteaza datele culese ca sa vedem daca nu apar contradictii care ar sugera prezenta unor erori in model

– Se elimina erorile, daca apar (de obicei apar !!!)

– Se testeaza modelul pt situatii limita (de ex o incarcare mare a retelei), avindu-se totusi grija sa fie stabil

• Ex de sistem instabil: daca un server avind o coada infinita primeste date generate cu o rata de generare mai mare decit rata de servire, atunci intirtzierile pachetelor din coada vor creste pe masura ce simularea se lungeste.

Page 11: Simularea retelelor - staff.cs.upt.ro

Increderea in rezultatele simularilor

• Se pune problema daca un rezultat de genul “valoarea medie a intirzierii pachetelor este x” e “de incredere”

• Adica daca simularea este “suficient de lunga”– Metoda empirica, dar nu foarte fiabila: se ruleaza o simulare pt o durata T si apoi

pt 2T si daca rezultatele sint “apropiate”, atunci probabil ca simularea e suficient de lunga (T e timp de simulare, conventional, nu timp real).

– E de dorit sa se calculeze intervale de incredere

– Sau cel putin sa se faca un nr mare de simulari (> 10 sau de ordinul zecilor, daca se poate) si sa se foloseasca seturi diferite de nr aleatoare, avind grija ca numerele aleatoare generate sa nu se suprapuna.

• E important sa se foloseasca distributii de probabilitate adecvate fenomenelor modelate sau chiar seturi de date reale

– Exista tipuri de trafic (de exemplu video streaming) ce nu pot fi practic modelate prin distributii de probabiltate

• Daca apar anomalii (de ex un grafic are o tendinta crescatoare, dar are o zona unde scade, e bine sa se incerce explicarea lor. Anomaliile pot fi cauzate de erori in model, dar nu neaparat, de ex cauzele pot si si anumite relatii intre numerele folosite in model:

– Poate conta daca numerele sint prime intre ele sau nu, de exemplu la algoritmi de scheduling de tip round robin sau in general cind se lucreaza cu numere intregi.

Page 12: Simularea retelelor - staff.cs.upt.ro

OMNeT++

• Poate fi descarcat de la adresa: www.omnetpp.org

• A fost dezvoltat de Andras Varga, apoi si de alti cercetatori/ programatori, initial pt sisteme Linux, apoi si pt Windows si alte OS

• E gratuit, dar are si varianta comerciala

• A ajuns la versiunea 5.

• De multe ori apar probleme de compatibilitate cu versiunile anterioare– => migrarea programelor poate fi anevoioasa si poate necesita modificari

importante in cod

– Cauze:• nu mai sint suportate anumite facilitati sau instructiuni

• Sau apar modificari importante:– De exemplu, de la versiunea 4.0 timpul de simulare e de tip intreg (extins),cu unitati de masura

(similar tipurilor fizice in VHDL)

– Inainte timpul de simulare era de tip double

• Pt invatarea simulatorului– recomand sa se inceapa cu tutorialul inclus

– Apoi cu intelegerea si modificarea unor exemple din directorul samples, de exemplu cu fifo.

– Manualul de utilizare e util, dar nu toate capitolele sint la fel de importante

• Urmatoarele slide-uri contin text si figuri preluate din manualele de utilizare ale OMNeT++, diverse versiuni [omnet].

Page 13: Simularea retelelor - staff.cs.upt.ro

OMNeT++

• OMNeT++ is an object-oriented modular discrete event network simulator. The simulator can be used for:

• • traffic modeling of telecommunication networks

• • protocol modeling

• • modeling queueing networks

• • modeling multiprocessors and other distributed hardware systems

• • validating hardware architectures

• • evaluating performance aspects of complex software systems

• • . . . modeling any other system where the discrete event approach is suitable.

Page 14: Simularea retelelor - staff.cs.upt.ro

Descriere generala

• An OMNeT++ model consists of hierarchically nested modules. The depth of module nesting is not limited, which allows the user to reflect the logical structure of the actual system in the model structure.

• Modules communicate through message passing. Messages can contain arbitrarily complex data structures.

• Modules can send messages – either directly to their destination

– or along a predefined path, through gates and connections (de preferat).

• Modules can have their own parameters. Parameters can be used to– customize module behaviour (de ex rata de generare a datelor, rata de servire,

etc)

– and to parameterize the model’s topology (de ex dimensiunea unei porti, nr de submodule de un anumit tip).

• Modules at the lowest level of the module hierarchy encapsulate behaviour. These modules are termed simple modules, and they are programmed in C++ using the simulation library.

Page 15: Simularea retelelor - staff.cs.upt.ro

Interfete

• OMNeT++ simulations can feature varying user interfaces for different purposes: – debugging, demonstration (Tkenv) – interfata grafica

– and batch execution (Cmdenv) - interfata de tip text.

• Advanced user interfaces make the inside of the model visible to the user, allow control over simulation execution and to intervene by changing variables/objects inside the model.

• This is very useful in the development/debugging phase of the simulation project.

• User interfaces also facilitate demonstration of how a model works.

• The simulator as well as user interfaces and tools are portable: they are known to work on Windows and on several Unix flavours, using various C++ compilers.

Page 16: Simularea retelelor - staff.cs.upt.ro

Modeling concepts

• OMNeT++ provides efficient tools for the user to describe the structure of the actual system. Some of the main features are:

• • hierarchically nested modules

• • modules are instances of module types

• • modules communicate with messages through channels

• • flexible module parameters

• • topology description language

Page 17: Simularea retelelor - staff.cs.upt.ro

Hierarchical modules

• An OMNeT++ model consists of hierarchically nested modules, which communicate by passing messages to each another.

• OMNeT++ models are often referred to as networks.

• The top level module is the system module. The system module contains submodules, which can also contain submodules themselves

• The depth of module nesting is not limited; this allows the user to reflect the logical structure of the actual system in the model structure. – See figure:

• Model structure is described in OMNeT++’s NED language.

Page 18: Simularea retelelor - staff.cs.upt.ro

Module simple si compuse

Figura preluata din [omnet]

Page 19: Simularea retelelor - staff.cs.upt.ro

Simple modules in OMNeT++

• In OMNeT++, events occur inside simple modules. Simple modules encapsulate C++ code that generates events and reacts to events, in other words, implements the behaviour of the model.

• The user creates simple module types by subclassing the cSimpleModule class, which is part of the OMNeT++ class library.

• cSimpleModule, just as cCompoundModule, is derived from a common base class, cModule.

• cSimpleModule, although packed with simulation-related functionality, doesn’t do anything useful by itself – you have to redefine some virtual member functions to make it do useful work.

• These member functions are the following:

• • void initialize()

• • void handleMessage(cMessage *msg)

• • void activity()

• • void finish()

Page 20: Simularea retelelor - staff.cs.upt.ro

Functii

• In the initialization step, OMNeT++ builds the network: it creates the necessary simple and compound modules and connects them according to the NED definitions. OMNeT++ also calls the initialize() functions of all modules.

• The handleMessage() and activity() functions are called during event processing.

• This means that the user will implement the model’s behavior in these functions.

• handleMessage() and activity() implement different event processing strategies: for each simple module, the user has to redefine exactly one of these functions. (nu ambele !)

Page 21: Simularea retelelor - staff.cs.upt.ro

Functii (continuare)

• handleMessage() is a method that is called by the simulation kernel when the module receives a message.

• activity() is a coroutine-based solution which implements the process interaction approach

• coroutines are non-preemptive (i.e. cooperative) threads.

• Generally, it is recommended that you prefer handleMessage() to activity() – mainly because activity() doesn’t scale well (you have to reserve

stack for each module that uses activity()).

• Modules written with activity() and handleMessage() can be freely mixed within a simulation model.

• The finish() functions are called when the simulation terminates successfully.

• The most typical use of finish() is the recording of statistics collected during simulation.

Page 22: Simularea retelelor - staff.cs.upt.ro

Comunicarea intre module

• De multe ori apare necesitatea ca intr-un modul sa fie citite (si eventual modificate) informatii din alte module

– De ex un modul scheduler doreste sa afle lungimea cozilor din modulele “user”

• In principiu se poate face in 3 moduri:

1. Prin variabile globale

2. Prin mesaje ale OMNeT++

3. Prin parametrii modulelor

Page 23: Simularea retelelor - staff.cs.upt.ro

Comunicarea intre module

• 1. Prin variable globale– Avantaje: e eficienta din punct de vedere al duratei simularii

– Dezavantaje:• Se pot face usor erori de sincronizare a accesului la variabilele

globale

• Rezulta un cod “urit”

• 2. Prin mesaje– Avantaje: e oarecum mai naturala

– Dezavantaje:• Incarca simulatorul si creste durata simularii

• Apar prea multe “tipuri” de mesaje:– Mesaje care reprezinta date intr-un sistem real (pachete, blocuri de

date, etc)

– Mesaje care reprezinta semnalizari importante intr-un sistem real (ex comanda data de scheduler ca din buffer-ul unui user sa se transmita un nr de blocuri de date)

– Mesaje care reprezinta citirea unor informatii (citirea lungimii unei cozi, etc)

Page 24: Simularea retelelor - staff.cs.upt.ro

Comunicarea intre module

• 3. Prin parametri

– Avantaje:

• Se distinge clar intre schimbul de date si comunicarea de

informatii intre module

• E mai sigura decit cu variabile globale

– Dezavantaje: cod mai lung:

• Se modifica prin cod valoarea unui parametru al unui modul

• Noua valoare i se transmite parametrului modulului (in

descrierea structurala)

• Aceasta noua valoare e citita de alt modul, eventual

modificata si retransmisa modulului initial

Page 25: Simularea retelelor - staff.cs.upt.ro

Exemple de modele de simulare

• 1. Model de simulare pentru studiul

handover-ului vertical

• 2. Model de simulare utilizat pentru studiul

alocarii resurselor intr-o retea de tip

GPRS/EGPRS

Page 26: Simularea retelelor - staff.cs.upt.ro

Vertical handover. Introducere• Celulele:

– Celulele stau la baza organizarii retelelor mobile (celulare)

– O celula este o suprafata deservita de o statie de baza (Base Station – BS)

– Celulele asigura reutilizarea frecventelor (sau a codurilor, in retele CDMA), ceea ce permite acoperirea unei suprafete oricit de mari (de ex o tara) cu un numar limitat de resurse radio (de ex nr limitat de frecvente).

• Se bazeaza pe faptul ca puterea semnalului radio scade proportional cu patratul distantei de la sursa la destinatie

• Alocarea resurselor radio se face la nivel de celula, de catre BS.

• Atunci cind utilizatorul mobil (Mobile Station : MS) se deplaseaza, el trece dintr-o celula in alta.

• Handover (HO): procedeul prin care un MS trece dintr-o celula in alta fara sa se deconecteze de la retea.

• Tipuri de handover:– Hard vs soft HO

• Hard HO: daca mobilul intii se deconecteaza de la BS-ul celulei vechi si apoi se contecteaza la BS-ul celulei noi (de ex in GSM si GPRS)

• Soft HO: MS se contecteaza la noul BS inainte de a se deconecta de la cel vechi, fiind pt o perioada de timp conectat la ambele BS-uri (de ex in UMTS)

– HO orizontal vs HO vertical (VHO - Vertical Handover):• HO e orizontal atunci cind celulele apartin aceleasi retele (aceeasi tehnologie si acelasi

operator) si e vertical atunci cind MS schimba nu doar celula, ci si tehnologia sau operatorul (de ex trece de la UMTS la GPRS)

Page 27: Simularea retelelor - staff.cs.upt.ro

Procesul de VHO

• Importanta VHO va creste in viitor, deoarece se estimeaza ca retelele viitorului (numite Next Generation Networks – NGN sau retele de generatia a 4-a: 4G si mai ales 5G) vor fi eterogene, adica vor consta din mai multe subretele, in tehnologii diferite (LTE, UMTS, GSM/GPRS, WLAN, chiar si retele de senzori in 5G...)

• Se urmareste ca utilizatorul sa beneficieze de cea mai buna (adica potrivita) conexiune, existind notiunea de Always Best Connected (ABC)

• Criteriile de alegere a subretelei sint (pot fi):– Calitatea semnalului receptionat

– Acoperirea retelei (de ex la WLAN e foarte mica)

– Performanta (viteza de transfer)

– Cost

– Consumul bateriei

– Tipul de trafic:• Background: SMS, MMS, e-mail, FTP

• Interactiv: WWW

• Streaming: adio sau video-streaming

• Conversational: VoIP, telenet, banking, jocuri

– Preferintele utilizatorului, etc

Page 28: Simularea retelelor - staff.cs.upt.ro

Procesul de VHO

• Algoritmii de VHO sint in general complecsi, implicind eventual tehnici de AI (logica fuzzy, retele neuronale, etc), algortimi de decizie cu critetrii sau obiective multiple, etc.

• Exista opinii diferite asupra– modelului de retea eterogena:

• Acelasi operator are subretele in tehnologii diferite (exista deja aceasta situatie: 3G si 2G, adica UMTS si GSM/GPRS)

• MS se poate conecta la retele ale unor operatori diferiti (numiti over the top) – model tot mai utilizat in viitor, de ex la 5G

– De ex MS are contract cu o firma care furnizeaza TV pe mobil, iar aceasta firma alege cel mai potrivit operator (cost, performanta), chiar in cadrul aceleiasi tehnologii

– elementului de decizie: MS sau reteaua (fiecare situatie are avantaje si dezavantaje)

– gradului de implicare a utilizatorului uman (de ex sa isi seteze niste preferine, de ex de retea, sa ceara optimizarea costului, etc)

Page 29: Simularea retelelor - staff.cs.upt.ro

Modelarea procesului de VHO

• Problema principala care apare la modelare e granularitatea de timp diferita a evenimentelor:– Scheduling-ul intr-o retea mobila se face la intervale de ordinul

ms (1 ms in LTE, 10ms in UMTS, 20ms in GPRS)

– Pachetele de date (de ex pachete IP) sint generate la intervale de secunde

– Selectarea unei alte celule (eventual din alta sub-retea) are loc la zeci de secunde sau minute

• Daca s-ar modela la nivel de ms, atunci ar rezulta simulari foarte lungi

• O posibilitate ar fi modelarea la nivel de pachet IP, cu lungimea de ordinul 1000 – 1500 Bytes si de estimat/calculat durata transmiterii unui pachet IP in diverse retele.

• Ar rezulta urmatorul model de simulare:

Page 30: Simularea retelelor - staff.cs.upt.ro

Modelul unei retele eterogene

Page 31: Simularea retelelor - staff.cs.upt.ro

Modelul unei retele eterogene

• Explicatii:– gen: e generatorul de date, care genereaza la anumite inervale

mesaje OMNeT, mesaje ce reprezinta fisiere, de anumite lungimi, in functie de aplicatie

– svr: server• Stocheaza in cozi fisierele create de generator

• Cozile pot fi per user (pt downlink DL) sau tipuri de trafic (DL sau UL – uplink), clase de utilizatori (DL)

• Transmite un fisier in reteaua aleasa de modulul alg.

– alg: algoritmul de selectie a subretelei

– dest: destinatia • nod de tip sink, culege statistici si sterge mesajele

• Informeaza serverul cind un fisier a fost complet transmis si se poate trimite urmatorul fisier

– Network1, Network2: doua sub-retele, de ex una de tip UMTS si una de tip GPRS. Modelul unei astfel de subretele e detaliat pe urmatorul slide:

Page 32: Simularea retelelor - staff.cs.upt.ro

Exemplu: modelul unei sub-retele

Page 33: Simularea retelelor - staff.cs.upt.ro

Modelul unei subretele

• Explicatii:– Datbuffer (databuffer): un buffer de date in subretea, ce

stocheaza fisierul ce urneaza a fi transmis prin acea subretea

– Dlay (delay):

• modeleaza intirzierea suferita de un pachet IP in subreteaua respectiva: delay_IP=dimensiune_IP/(1000* transfer_rate)

• Intirzierea e in functie de incarcarea subretelei si de calitatea legaturii radio intre MS si BS.

– Loop: nod de buclare

• fiecare fisier trece prin modulul loop

• La fiecare trecere lungimea fisierului scade cu un lungimea unui pachet IP

• Daca lungimea fisierului a devenit zero, atunci inseamna ca fisierul a fost transmis complet si mesajul OMNeT reprezentind fisierul e trimis la nodul dest.

Page 34: Simularea retelelor - staff.cs.upt.ro

Modelul unei subretele

• Explicatii (continuare):– genLoadCond: generatorul conditiilor de incarcare

• modeleaza incarcarea subretelei (de fap a celulei din subretea)

• Se considera ca la intervale aleatoare de citeva zeci de secunde scade sau creste cu 1 numarul utilizatorilor (MS) din celula

• Depinde de tipul subretelei (UMTS, GPRS,...)

– genRadioCond: generatorul de conditii radio:• Modeleaza calitatea legaturii radio intre MS si BS, doar

pentru utilizatorul pe care il urmarim (modelam)

• In principiu, intr-o retea mobila, in functie de calitatea legaturii radio, datele utilizatorului se codifica mai tare sau mai putin, rezultind o rata de transfer mai mica sau mai mare.

• Depinde de asemenea de tipul subretelei.

Page 35: Simularea retelelor - staff.cs.upt.ro

Modelul unei celule UMTS

• Se considera ca o celula are capacitatea maxima de 1Mb/s (megabiti pe secunda)

• Un MS poate transmite cu una din ratele de transfer (in kb/s):– {32,48,64,80,96,112,128,192,256,320,384}

• Se pleaca de la o incarcare initiala a celulei (de ex 512 kb/s)

• La intervale de citeva zeci de secunde se considera ca un utilizator intra in celula sau paraseste celula=>

– Incarcarea celulei creste, respectiv scade, cu una din valorile de mai sus, neputind depasi capacitatea maxima.

• Capacitatea ramasa a celulei i se poate aloca MS modelat, pina la limita de 384 kb/s, conform conditiilor radio

• Generatorul de conditii radio genereaza aleator una din valorile de mai sus, care limiteaza rata de transfer (transfer_rate) a MS modelat.

• Exemplu numeric: daca in urma modelarii incarcarii celulei, pt MS ramine o capacitate maxima de 256 kb/s,

– atunci daca genRadioCond genereaza o valoare de 32kb/s, MS va avea transfer_rate = 32kb/s

– Daca genRadioCond genereaza o valoare de 320kb/s, atunci MS va avea transfer_rate=256kb/s

Page 36: Simularea retelelor - staff.cs.upt.ro

Modelul unei celule (E)GPRS

• Se considera ca una din frecventele din celula e alocate pt EGPRS => 8 TS (time-slots) alocati ptr EGPRS in celula.

• Exista limitarea ca nu pot fi mai mult de 5 MS multiplexate pe un TS => vom avea in celula 8*5=40 “parti de time slot” (Parts_of_TS)

• Unei MS i se pot aloca intre 1 si 4 TS in DL (downlink), intre 1 si 2 TS in UL (uplink)

• Se porneste de la o incarcare initiala a celulei, in Parts_of_TS.

• Aparitia /plecarea unei MS in/din celula inseamna cresterea /scaderea numarului de Parts_of_TS_in_use (ocupate) cu un numar intre 1 si 4, fara a depasi valorile de 0, respectiv 40 Parts_of_TS.

• Rezulta nr de parti de TS disponibile: Nb_of_Parts_available

• MS primeste un nr de Nb_of_parts_of_TS =4 TS, cu conditia ca Nb_of_Parts_available >=4.

• Rezulta noua valoare pentru Parts_of_TS_in_use.

• Se calculeaza nr de MS per TS (Nb_of_MS_per_TS) ca fiind– Ceil(Parts_of_TS_in_use/8), unde ceil() reprezinta valoarea unui nr real rotunjit “in sus” la

intreg, de ex ceil(2.1) = 3.

• Rata de transfer a MS se calculeaza cu formula:– Transfer_rate= Nb_of_parts_of_TS * Thr_per_TS / Nb_of_MS_per_TS, unde Thr_per_TS

(throughput per time slot) e dat de schema de modulare si codare, numita MCS

– In EGPRS exista 9 MCS, avind Thr_per_TS intre 8.8kb/s la MCS1 si 59.2 kb/s la MCS9.

Page 37: Simularea retelelor - staff.cs.upt.ro

PDA Wireless system

Laptop Mobile phone

Base Station

Different equipments in a cell communicate with the Base

Station (BS)

Resource allocation in cellular data

networks (e.g. GPRS). The problem

description

Page 38: Simularea retelelor - staff.cs.upt.ro

Parameters of the Resource

Allocation problem

• N users in a cell which can send (or receive) data

• Bandwidth: B<=8 Packet Data Traffic Channels (PDTCH’s) available every controller cycle (20ms)

• P levels of precedence and/or priority

• K active users (send or receive data)

• Algorithms for:– Admission control (AC): decision to admit or not a user in the

system

– Transmission control (TC): sharing the B channels among the

active users

• Packet Control Unit (PCU), part of BSS, performs the TC algorithms

Page 39: Simularea retelelor - staff.cs.upt.ro

K

active

users

user[1]

user[0]

user[2]

user[K]

user[N-1]

B=8

PDTCHs

every

20ms

user[K-1]

N-K

in-

active

users

N

users

in a

cell

Page 40: Simularea retelelor - staff.cs.upt.ro

Transmission control

• Level: Medium Access Control (MAC), Radio Link Control (RLC)

• Information available for each user: – The number of waiting data blocks

– Priority/precedence level

• Requirements for resource allocation algorithms:– Simple, fast, easy to implement (the TC algorithms are

implemented in hardware, i.e. in the PCU)

– Low delay, high throughput

– Possibility to implement priority and/or precedence

Page 41: Simularea retelelor - staff.cs.upt.ro

Admission control

• Users can have different: – Precedence levels (high, normal, low)

– Priority levels

– Coding schemes

– Types of data (FTP, WWW, streaming, etc)

– Mobility characteristics

• More complex than the problem of transmission control: AI algorithms or heuristics

• Goals (TC+AC): – QoS over GPRS

– Congestion alleviation

Page 42: Simularea retelelor - staff.cs.upt.ro

Modelul de simulare pentru TC

• Se considera cei K useri activi intr-o celula

• Resursele retelei constau in B=8 canale radio

• Pachet Control Unit (PCU), adica scheduler-ul, are o perioada de 20ms (ciclu de scheduling)

• La fiecare 20ms cele B canale se impart intre cei K useri conform unui algoritm de scheduling– De ex WRR (Weighted Round Robin):

• fiecare user are o pondere Wi, nr intreg, iar la fiecare ciclu de simulare user-ul i primeste Wi canale radio, daca mai sint atitea disponibile

• Evident, nu toti cei K useri sint serviti in fiecare ciclu de scheduling

• Posibile valori: K 3 pina la 10 useri, Wi pot fi 1, 2, 4 sau 8.

• Se considera 3 tipuri de useri, e.g. W=1 clasa economy, W=2, clasa standard si W=4 sau 8 clasa premium.

Page 43: Simularea retelelor - staff.cs.upt.ro

Modelul de simulare pt un user

• Un user are un modul generator de date si un modul buffer (o coada)

• Generatorul de date:– Creaza la anumite intervale un nr de blocuri de date

• Se poate considera ca toate blocurile de date au lungime =1

• Nr de blocuri de date generat odata poate fi fix sau variabil (aleator)

– Se poate considera ca un astfel de grup de blocuri de date este un fisier, sau un pachet (IP)

• Intervalele de generare a datelor se iau pseudo-aleatoare, conform unor distributii de probabilitate.

• Trebuie avut grija ca userii sa nu genereze mai multe date decit pot fi servite de catre retea

Page 44: Simularea retelelor - staff.cs.upt.ro

Modelul pt un user: buffer-ul

• Utilizeaza structura de coada din omnet

• La sosirea unor blocuri de date de la generator le insereaza in coada si actualizeaza lungimea cozii

• Scheduler-ul (PCU) citeste lungimea cozilor

• Primeste comenzi de la scheduler: – Un mesaj de comanda de la scheduler contine nr de

blocuri de date ce vor fi transmise de catre buffer in ciclul de scheduling curent

– Buffer-ul va transmite acel nr de blocuri de date spre destinatie (un modul omnet de tip sink) si isi va actualiza lungimea cozii

Page 45: Simularea retelelor - staff.cs.upt.ro

Modelul de simulare: PCU

• PCU implementeaza algoritmul de scheduling

• Functioneaza periodic cu o perioada T=20ms

• La fiecare ciclu de scheduling (T= 20ms) PCU

afla lungimea cozilor fiecarui user si apoi

calculeaza o alocare a resurselor conform

algoritmului de scheduling implementat (de ex

WRR, dar nu neaparat)

• Anunta fiecare user (buffer) cite blocuri de date

va transmite

Page 46: Simularea retelelor - staff.cs.upt.ro

Modelul de simulare: sink

• Modulul sink reprezinta destinatia datelor: culege statistici si sterge mesajele omnet.

• Teoretic ar trebui sa existe cite un modul sink pt fiecare user

• Dar e mai eficient sa existe un singur modul sink, deoarece– Modulul sink culege statisticile (valori medii, maxime, minime,

etc) despre rezultatele simularii si acestea sunt mai usor de procesat daca sunt impreuna

– Va avea cite o intrare pt fiecare user

– Va trebui sa identifice fiecare pachet de date si sa calculeze intirzierile de transmiere a datelor respective

– Statisticile pot fi per user, pt fiecare clasa de useri, etc.

– Poate colecta si trace-uri pt (anumiti) useri: de ex evolutia in timp a intirzierilor pachetelor unui user (intr-o anumita peroada de timp)

Page 47: Simularea retelelor - staff.cs.upt.ro

Modelul de simulare

• Poate contine si alte module:– de ex un modul pt a modela conditiile radio: cind

conditiile radio sint proaste anumite blocuri de date se pot pierde si trebuiesc retransmise

– Un modul care sa modeleze traficul de voce (modifica B in mod aleator ca sa modeleze canalele alocate traficului de voce)

• Modelul este evident simplificat fata de o retea GPRS reala, dar este totusi suficient de realist.

• Partea de AC nu e inclusa in model, deoarece complexitatea ar creste prea mult.

Page 48: Simularea retelelor - staff.cs.upt.ro

Scheduling algorithms

• Another possibility to implement

scheduling algorithms (used e.g., for LTE):

– each resource block (RB) is allocated to a

user, according to an auction

– A parameter p[i] is considered for each user,

the user with the biggest p[i] wins the auction

and receives the RB

– The number of RBs allocated to a user in a

scheduling cycle can be limited

Page 49: Simularea retelelor - staff.cs.upt.ro

Scheduling algorithms

• The parameter p[i] can be:

– The quality of the radio link between the BS and the

user equipment (UE) for DL scheduling, or from the

UE to BS for UL sched

– For Round Robin: The (simulation) time elapsed since

the user i was served last time

• tnow – tlast_time_served_user[i](1)

– For WRR: he same parameter like for RR, multiplied with a weighting factor W[i]>0 (usually ≥ 1)

– For proportional fair: the product between the parameter from WRR and the quality of the radio link

Page 50: Simularea retelelor - staff.cs.upt.ro

Scheduling algorithm

• Exercise: we can implement RR by

condidering only the parameter

tlast_time_served_user[i] and allocating the RB to

the user with the smallest value of this

parameter. Is this ok ? Explain why !

Page 51: Simularea retelelor - staff.cs.upt.ro

Bibliografie

• [omnet] OMNeT++ User Manual, Version 4.1.

Andras Varga and OpenSim Ltd, 2010. [Online].

Available: http://www.omnetpp.org/

• [Stuckmann_ICN01] Stuckmann, Peter, and

Frank Müller. "Quality of service management in

GPRS networks." Networking—ICN 2001.

Springer Berlin Heidelberg, 2001. 276-285.