Maršrutų paieškos metodai pagal kokybės parametrą (Constraint Based Routing)

KAUNO TECHNOLOGIJOS UNIVERSITETAS INFORMATIKOS FAKULTETAS KOMPIUTERIŲ TINKLŲ KATEDRA Referatas Maršrutų paieškos metodai pagal kokybės parametrą (Constraint Based Routing) Tikrino: Ingrida Lagzdinytė Atliko: IFK-3 grupės studentai Evaldas Vėlavičius Aurimas Garuolis KAUNAS, 2006 Įžanga 3 Keliami tikslai 4 Modelis 5 QoS ribojami ištekliai 7 Problematika 8 QoS maršrutizavimo problematika „Unicast“ 8 QoS maršrutizavimo problematika „Multicast“ 10 Išvados 11 Naudota literatūra 11 Įžanga Daugėjant daugialypių terpių paslaugų ir privačiais virtualiais tinklais sujungtų bendrų vietų internete, vis labiau imama vertinti lanksčius interneto maršrutizavimo protokolus. Dabartinis interneto paketų persiuntimas yra paremtas galinio gavėjo adresu. Paprastų maršrutizavimo algoritmų, kurie apibrėžia persiuntimo kelius minimaliu žingsnių skaičiumi arba vėlinimu, nebepakanka. Skirtingų apkrovų palaikymo poreikis, programos reikalaujančios aukštos kokybės iššaukia naujus reikalavimus interneto maršrutizavime. Nauji maršrutizavimo pavyzdžiai taip pat reikalingi tam, kad būtų galima realizuoti paslaugų sutartis tarp paslaugų tiekėjų bei vartotojų. Administravimo strategijos, našumo reikalavimas, apkrovų balansavimas ir išplėčiamumas tampa vis didesnės svarbos faktoriais interneto maršrutizavime. Pagrindinis to motyvas – intelektualaus maršruto parinkimas, paremtas daugybiniais apribojimais arba duomenų paketų turiniu. Apribojimais paremto maršrutizavimas (Constraint Based Routing) nurodo maršrutizavimo algoritmų klasę, kur pagrindinis kelias išrenkamas atsižvelgiant į reikalavimų ar apribojimų aibę. Šiuos apribojimus gali iššaukti administravimo strategijos arba paslaugos kokybės (Quality of Service) reikalavimai. Strategijų įvesti apribojimai vadinami strategijų apribojimais, o susietas maršrutizavimas – strategijų maršrutizavimas, atitinkamai paslaugos kokybės reikalavimų, tokių kaip pralaidumas, vėlinimas, nuostoliai, įvesti apribojimai vadinami paslaugos kokybės parametro apribojimai, o susietas maršrutizavimas – paslaugos kokybės maršrutizavimas. Keliami tikslai Apribojimais paremtas maršrutizavimas (CRB- Constraint Based Routing) sumažina neautomatinę konfigūraciją ir reikalauja vis mažiau įsikišimo realizuojant apkrovos projektavimo tikslus. Pagrindinis CRB tikslas įgalinti naują maršrutizavimo pavyzdį su specialiomis savybėmis, kuris būtų sulietas su esamais maršrutizavimo protokolais. Išteklių prieinamumo informacijo, reikalinga priimti CRB sprendimus, mainai vyksta per maršrutizavimo protokolo plėtinius. Signalizuojantys protokolai gali nustatyti reikiamas būsenas apskaičiuotame kelyje. Galiausiais, detalus maršruto parinkimas paskaičiuotame kelyje gali būti atliktas per komutavimo technologiją, tokia kaip Asinchroninis persiuntimo rėžimas (Asynchronous Transfer Mode (ATM)) arba daugiaprotokolis žymių komutavimas (Multi-Protocol Label Switching (MPLS)) arba tiesiog naudojant kelius, laikomus paketo antraštėje. CBR paprastai nagrinėja srauto sankaupą (dar žinoma kaip makro srautai arba magistralės), o ne individualius mikro srautus (pvz. paprastas HTTP ryšys). CBR nagrinėja srautą tarp šaltinio ir paskirties adreso. Naudojant tinko jungiamumą ir resursų prieinamumą kaip įvestį, perspektyvus yra maršrutų skaičius. Jei iškeliami tam tikri apribojimai, kai kurie maršrutai gali neišlikti tinkamais. CBR veikimo principe dominuoja du persidengiantys maršrutai: strategijos maršrutas, ir paslaugos kokybės (QoS) maršrutas. Šis persidengimas yra dėl to, kad kai kurie maršrutai gali atitikti užslėptas maršrutizavimo strategijas ir taip pat tenkinti paslaugos kokybės reikalavimus. Modelis QoS maršrutizavimas parenka kelius priklausomai nuo QoS srauto reikalavimų ir tinklo išteklių pasiekiamumo. QoS maršrutizavimas nustato galimus kelius, patenkinančius QoS reikalavimus, kartu optimizuodamas resursų išnaudojimą ir sumažindamas tinklo apkrovimą. Pasirinkti keliai paprastai yra prisegami („pinned“), tai reiškia, kad srautai yra orientuojami priklausomai nuo susijungimo krypties. Resursai žymimi ant susijungimų ir reiškia kiekvieno susijungimo kainą bei vėlavimą. QoS maršrutizavimo tikslas yra kainų minimizavimas priklausantis nuo vėlavimo. Tarkime pasirinktas kelias į „p“ einantis iš „s“ į „d“ s->3->2->d, kurio kaina yra 12, o vėlavimas 37ms. Jeigu kainos taisyklę pakeisime į „cost 1->2->d taps galimu pasirinkimu. Kelių taisyklių tvarka yra svarbi vykdant daug masinės optimizacijos taisyklių. Tarkime, turime dvi optimizacijos taisykles, kurios reiškia šuolių skaičių ir galimą srautą. Algoritmas gali suteikti didesnę svarbą pasirinkimui kelio, kuris turi mažiausiai šuolių arba tam keliui, kurio pralaidumas didžiausias. Kelio turinčio didžiausią pralaidumą ir mažiausią šuolių skaičių, pasirinkimas suteikia bazinį apkrovimo tinklo keliuose balansavimą ir paprastai yra vadinamas „plačiausiu trumpiausiu keliu“. „Plačiausio trumpiausio kelio“ alternatyva – pasirinkimas trumpiausio kelio tarp kelių turinčių vienodą („didžiausia“) pralaidumo lygį. QoS ribojami ištekliai QoS ištekliaus pavadinimas Tipas Aprašymas Galimas ryšio pralaidumas Min/Max Šis išteklius aprašo kokia pralaidumo dalis bus rezervuota QoS srautui. Tai min/max resursas, kurio minimumas yra lygus kelio pralaidumui (end-to-end) Sklidimo vėlavimas Adityvus Nurodo gaišties laiką su kuriuo susiduriama tinkluose. Vėlavimo nepastovumas Adityvus Nurodo vėlavimo nepastovumą Šuolių skaičius Adityvus Šis išteklius nurodo šuolių skaičių. Minimalų šių šuolių skaičių turintis kelias yra naudojamas daugumos algoritmų tam, kad nustatytų trumpiausią kelią (mažiausiai „kainuojantį“ kelią). Kaina Adityvus Nurodo abstraktų tinklo resursų išnaudojimo matą. Gali būt išreikšta doleriais arba buferio ar pralaidumo utilizacijos funkcija. Praradimo tikimybė arba klaidų dažnis Dažninis Nurodomas toleruojamas duomenų praradimo kiekis. Nauji QoS maršrutizavimo tyrimai vykdomi dviem pagrindimėm kryptimis. Pradžioje jei buvo sukoncentruoti tam, kad būtų galima išspręsti maršrutizavimo problemas kylančias dėl skirtingų QoS apribojimų ir jų kombinacijų, o nesenai tyrėjai sutelkė dėmesį ties optimizavimu ir praktinėmis problemomis. Problematika QoS maršrutizavimo problematika „Unicast“ Pralaidumą ribojantis maršrutizavimas Šiai problemai buvo pasiūlyti keli sprendimai. Vienas iš įdomesnių tiria vienų išteklių priklausomybes nuo kitų, kaip, tarkim, galimą pralaidumą, vėlavimą, buferio dydį, tam, kad supaprastintų problemą. Čia gali būti naudojamas Belmano-Fordo algoritmas. Vėlavimą ribojantis maršrutizavimas Ši problema dažniausiai formuluojama, kaip kelio, turinčio didžiausia galimybę patenkinti vėlavimo ribą, radimas. Ši problema sumažinta nuo globalaus iki lokalaus sprendimo ieškojimo. Taškas-į-tašką („end-to-end“) vėlavimo ribojimas yra padalinamas tarp susijungimų, taigi kiekvienas susijungimas turi vienoda galimybę patenkinti jo vietinį apribojimą. Pasirenkamas kelias turintis didžiausia dalinimosi galimybę. Vėlavimą ir pralaidumą ribojantis maršrutizavimas Vienas iš būdų patenkinti ir pralaidumo ir vėlavimo ribas yra pirmiausia sumažinti visus susijungimus nepatenkinančius pralaidumo reikalavimo. Dijkstros trumpiausio kelio algoritmas panaudojamas rasti tinkamiausiam keliui, jeigu toks yra, tenkinančiam vėlavimo reikalavimą. Vėlavimui ir pralaidumui optimizuotas maršrutizavimas Ši problema gali būti išsprendžiama taip, kaip plačiausio trumpiausio kelio problema arba trumpiausio plačiausio kelio problema. Pralaidumą ir kainą ribojantis maršrutizavimas Šios problemos sprendimai dažniausiai pažymi kainą arba pralaidumą, kaip tam tikrą apribotą reikšmę ir tada sprendžia šią problemą naudojant išplėstinį Belmano-Fordo (EBF) arba išplėstinį Dijkstros trumpiausio kelio (EDSP) algoritmą. Ribojamo vėlavimo ir optimizuotos kainos maršrutizavimas Ši problema susilaukė itin daug dėmesio ir sprendimų algoritmų. Lagranžo relaksacija pagrįstas kainos surinkimas (LARAC) naudoja algoritmus, kurie suteikia galimybę kontroliuoti mainus tarp algoritmo vykdymo laiko ir apskaičiuotų kelių kokybės. Maršrutizavimas su daug apribojimų Šio maršrutizavimo uždavinio tikslas yra patenkinti tam tikrų apribojimų rinkinį. Jam spręsti buvo pasiūlytas euristinis daug apribojimų turinčio optimalaus kelio ieškojimo uždavinio sprendimas, kuris optimizuoja ne linijinę funkciją (įvykdomumui) ir pagrindinę funkciją (optimaliam rezultatui). Tačiau ši sistema dar tiriama, nes yra nemažai netikslumų dėl kurių nukenčia algoritmo charakteristikos. QoS maršrutizavimo problematika „Multicast“ Multicast (paketai siunčiami tam tikrai grupei gavėjų) QoS maršrutizavimas yra gerokai sudėtingesnis už unicast maršrutizavimą. Papildomas sudėtingumas susidaro iš poreikio palaikyti paketų rezervavimo ir globalaus priėmimo kontrolę kartu su tipinio QoS maršrutizavimo reikalavimais, kaip lankstumas ir tvirtumas. Naujausi multicast maršrutizavimo algoritmai yra sukurti patenkinti tokius tinklo ribojimus, kaip pralaidumas, vėlinimas, trūkčiojimas ir kaina. Vėlinimo arba pralaidumo atžvilgiu optimizuotas maršrutizavimas Algoritmai siūlomi šiai optimizavimo problemai naudoja šaltinio maršrutizavimą ir palaiko globalią būklę. Tarkim MOSFPF yra multicast OSPF versija. Kai kurie sprendimai naudoja Steinerio medžio formuluotę. Vėlinimo ribojimo, optimiziuotos kainos maršrutizavimas Ši problema gali būti suformuluota, kaip Steinerio medžio uždavinys. Įdomus jos sprendimas: QoS multicast maršrutizavimo protokolas QMRP stebi tinklo būklę ir prisitaikydamas vykdo perjungimus tarp vieno kelio maršrutizavimo ir keleto kelių maršrutizavimo. Vėlinimo ir trūkčiojimo ribojimo maršrutizavimas Vėlinimą ir jo trūkčiojimą ribojantis multicast QoS maršrutizavimas gali būti išsprendžiamas naudojant ribojantį Steinerio medį. Neseni tyrimai koncentruoti į QoS multicast maršrutizavimo tvirtumą, stabilumą ir išplėčiamumą. Išvados Ribojimais paremtas maršrutizavimas susidaro ir iš strategijos ir iš QoS maršrutizavimo. Strateginis maršrutizavimas yra svarbus tam, kad suteiktų gerenę ir lankstesnę paslaugą. Literatūroje QoS maršrutizavimas yra nagrinėjimas daugiau už strateginį maršrutizavimą, o paskutinės studijos parodė galimybę panaudoti QoS maršrutizavimą su ne itin tikslia informacija arba panaudoti surinkimo technologijas, norint pagerinti praplečiamumą, neprarandant daug našumo ir kokybės. Protingas QoS algoritmo parametrų parinkimas gali ženkliai pagerinti paslaugos kokybę stabilumo ir apkrovos balanso aspektais. Naudota literatūra 1. http://www.linktionary.com/c/constraint_routing.html 2. http://www.cs.purdue.edu/homes/fahmy/papers/routing.pdf 3. http://en.wikipedia.org/wiki/Constraint-based_Routing_Label_Distribution_Protocol

Daugiau informacijos...

★ Klientai rekomenduoja

Šį rašto darbą rekomenduoja mūsų klientai. Ką tai reiškia?

Mūsų svetainėje pateikiama dešimtys tūkstančių skirtingų rašto darbų, kuriuos įkėlė daugybė moksleivių ir studentų su skirtingais gabumais. Būtent šis rašto darbas yra patikrintas specialistų ir rekomenduojamas kitų klientų, kurie po atsisiuntimo įvertino šį mokslo darbą teigiamai. Todėl galite būti tikri, kad šis pasirinkimas geriausias!