1. Uvod Sodobni internet je kompleksen sistem ogromnih razsežnosti. To velja tako za osnovni nivo usmerjevalnikov kot za višji nivo avtonomnih sistemov, to je omrežij, v katerih veljajo interna pravila usmerjanja in tipično pripadajo eni organizaciji. Študije globalnih komunikacijskih protokolov in arhitektur na obeh ravneh so velik izziv, pri čemer igra pomembno vlogo ustrezen topološki model omrežja. V preteklosti je bilo predlaganih veliko generatorjev omrežnih topologij. Cilj generatorjev so naključne topologije, ki po karakterističnih lastnostih čim bolj ustrezajo resničnemu internetu. Poudarek današnjih generatorjev je predvsem na topološki povezanosti vozlišč omrežja. Pri modeliranju na ravni avtonomnih sistemov povezava med vozliščema pomeni obstoj komunikacijske poti med sistemoma, kar pa ne zadošča za simulacijo dejanskega usmerjanja podatkovnih paketov med avtonomnimi sistemi [1]. Potek usmerjevalnih poti je namreč določen z različnimi tipi poslovnih relacij [2]. Metode prepoznavanja tipov poslovnih relacij v resničnem internetu so sicer dobro raziskane, ni pa bilo veliko poskusov prepoznano strukturo vključiti v generični model omrežja avtonomnih sistemov. V nadaljevanju najprej definiramo tipe poslovnih relacij in naštejemo nekaj najpomembnejših posledic neupoštevanja le-teh. Poglavje 3 vsebuje pregled metod za prepoznavanje poslovnih relacij v realnem omrežju, 4. poglavje pa pregled generatorjev naključnih omrežij, ki z izjemo enega ne upoštevajo relacij med avtonomnimi sistemi. Po identifikaciji pomanjkljivosti znanih generatorjev v 5. poglavju predlagamo ločeno reševanje problema tipa relacij in topološke povezanosti. Formalno definiramo problem tipa relacij v naključnih grafih in utemeljimo zahtevane lastnosti označenih grafov, ki so osnova za reševanje definiranega problema. 2. Pomen poznavanja poslovnih relacij 2.1 Tipi poslovnih relacij Pionirsko delo na področju analize poslovnih relacij je bilo objavljeno leta 2001 [2]. Delo prvič definira tri različne tipe relacij: ponudnik–stranka (provider-to- customer), enakovreden-z-enakovrednim (peer-to-peer) in soroden-s-sorodnim (sibling-to-sibling). Relacija ponudnik–stranka najpogosteje obstaja v smeri od večjega avtonomnega sistema proti manjšemu, pri čemer stranka plačuje ponudniku dostop do globalnega interneta. Ponudnik stranki prek protokola BGP izvaža celotno usmerjevalno tabelo, torej svoje lokalne zapise, zapise lastnih ponudnikov, strank, enakovrednih in sorodnih avtonomnih sistemov. Nasprotno, stranka ponudniku posreduje le lokalne zapise, zapise lastnih strank in sorodnih sosedov. Zapisov drugih ponudnikov in enakovrednih avtonomnih sistemov stranka ponudniku ne izvaža. Enake omejitve veljajo med enakovrednimi avtonomnimi sistemi. V tem primeru imata avtonomna sistema sklenjen vzajemen sporazum o medsebojni izmenjavi njunega prometa ter prometa njunih strank in sorodnih sistemov. Relacija soroden-s-sorodnim je ponavadi vzpostavljena med avtonomnima sistemoma, ki pripadata sorodni ali kar isti organizaciji. Sorodna avtonomna sistema brez omejitev izmenjujeta tako promet kakor tudi zapise usmerjevalnih tabel. Avtonomni sistem lahko pri sklepanju relacij z drugimi avtonomnimi sistemi nastopa v vseh naštetih vlogah hkrati. Relacije soroden-s-sorodnim so redke, ponavadi njihov delež znaša le približno 1% vseh relacij v internetu [2][3]. Poleg opisanih obstajajo tudi druge, kompleksnejše poslovne relacije, vendar v internetu nastopajo še redkeje [3][4]. 2.2 Usmerjevalne poti brez dolin Posledica doslednega upoštevanja zgoraj opisanih izvoznih politik je, da je potek usmerjevalnih poti podrejen določeni strukturi. Podatkovni paket ne more prečkati povezave stranka–ponudnik ali enakovreden-z- enakovrednim po prečkanju povezave ponudnik–stranka ali enakovreden-z-enakovrednim. Obstoj strukture je dokazala Gao [2] in poimenovala tovrstne poti kot usmerjevalne poti brez dolin. V literaturi najdemo tudi termin veljavne usmerjevalne poti [3][4][5]. Usmerjevalna pot brez dolin je torej sestavljena iz treh segmentov. Segment navkreber sestoji iz nič ali več povezav tipa stranka–ponudnik ali soroden-s-sorodnim. Sledi segment z največ eno povezavo enakovreden-z- enakovrednim. Zadnji segment je segment navzdol in vsebuje nič ali več povezav tipa ponudnik–stranka ali soroden-s-sorodnim. Na sliki 1 je prikazan primer omrežja avtonomnih sistemov s pripadajočimi poslovnimi relacijami. Usmerjevalne poti brez dolin v tem omrežju so na primer (D, B, E, H), (B, C, F, I) in (C, B, A, D), medtem ko usmerjevalne poti (D, G, H), (F, B, E, H) in (F, I, H) niso brez dolin. 2.3 Posledice neupoštevanja relacij Komunikacijski promet poteka samo po usmerjevalnih poteh brez dolin, kar omejuje možnosti usmerjanja. Poleg tega imajo avtonomni sistemi vedno možnost izbire, po kateri izmed razpoložljivih usmerjevalnih poti brez dolin bodo pošiljali promet. Tipično ima prednost usmerjanje prek strank [6]. Posledično so uporabljene usmerjevalne poti daljše od topološko najkrajših. Pojav imenujemo napihovanje poti (path inflation) [7]. V [6] so pokazali, da je zaradi napihovanja poti najmanj 45% usmerjevalnih poti daljših vsaj za eno povezavo in da podaljševanje lahko prinese do 9 dodatnih povezav. Vilhar, Novak, Kandus 140 Slika 1: Primer omrežja avtonomnih sistemov s pripadajočimi poslovnimi relacijami. Figure 1: Example of an autonomous system network with the pertaining business relationships. V primeru na sliki 1 je med vozliščema D in H topološko najkrajša usmerjevalna pot (D, G, H), vendar ni brez dolin, ker segmentu navzdol (D, G) sledi segment navkreber (G, H). Najkrajša usmerjevalna pot brez dolin med D in H je (D, B, E, H). Med vozliščema B in I je topološko najkrajša usmerjevalna pot (B, F, I) sicer brez dolin, vendar avtonomni sistem B izbere usmerjanje prek stranke C namesto prek enakovrednega avtonomnega sistema F, ker tako narekuje njegova politika usmerjanja. Posledično je uporabljena pot (B, C, F, I). Simulacije na modelu omrežja, ki ne vsebuje informacij o poslovnih relacijah, zanemarijo efekt napihovanja poti. Simulirane usmerjevalne poti so na splošno prekratke. Neupoštevanje tipov relacij vodi tudi k prevelikemu številu alternativnih poti in k manjšim prometnim obremenitvam na določenih povezavah [1]. Zato so rezultati simulacij izpostavljeni napakam. Neupoštevanje tipov poslovnih relacij ima tudi druge posledice. V nekaterih primerih komunikacijskih scenarijev je upoštevanje tipov relacij pogoj za zmožnost izvedbe simulacije. Primer takega scenarija je hierarhična razširitev protokola Mobile IPv6 [8]. Mobilne naprave prek signalizacijskih sporočil odkrivajo posebne entitete, imenovane sidrne točke (MAP – Mobility Anchor Points), ki igrajo vlogo začasnih domačih agentov. Poti razširjanja teh sporočil med avtonomnimi sistemi bodo potekale v smereh, ki so odvisne od poslovnih relacij. Na sliki 1 je sidrna točka v avtonomnem sistemu B vidna mobilnim napravam v avtonomnih sistemih B, A, D, G, C, F in I, medtem ko je sidrna točka v avtonomnem sistemu F vidna samo mobilnim napravam v avtonomnih sistemih F in I. Sklepanje o vidnosti sidrnih točk v sosednjih avtonomnih sistemih brez poznavanja tipov relacij ni mogoče. 3. Prepoznavanje tipov poslovnih relacij Upravitelji avtonomnih sistemov imajo na splošno podatke o poslovnih relacijah za zaupne. Zato je prepoznavanje tipov relacij v resničnem internetu velik izziv. Predlaganih je bilo več metod. Prvo metodo je predlagala avtorica tipizacije relacij v [2]. Informacije o usmerjevalnih poteh črpa iz javno dostopnih usmerjevalnih tabel na strežnikih RouteViews [9]. Metoda temelji na predpostavki, da je na meji med segmentom navkreber in segmentom navzdol najverjetneje tak avtonomni sistem, ki ima v grafu omrežja najvišjo stopnjo med vozlišči na dani poti. Avtonomni sistemi z višjo stopnjo so ponavadi večji, zato pogosteje nastopajo v vlogi ponudnika storitev manjšim avtonomnim sistemom. Avtorica tudi ugotavlja, da relacija soroden-s-sorodnim obstaja med sistemoma, ki drug drugemu zagotavljata prehod tranzitnega prometa, ter da relacijo enakovreden-z- enakovrednim ponavadi vzpostavijo avtonomni sistemi podobnih dimenzij. Ugotovitve upošteva predlagana hevristika, ki iz dejanskih usmerjevalnih tabel določi relacije med realnimi avtonomnimi sistemi. Naslednje pomembno delo [3] formalizira problem prepoznavanja poslovnih relacij kot optimizacijski problem v teoriji grafov. Rešitev problema ToR (Type- of-Relationship) pri danem grafu G(V,E) in naboru usmerjevalnih poti P je tak nabor relacij za povezave iz E, da je število usmerjevalnih poti brez dolin v P maksimalno. Avtorji so sklepali, da gre za NP-poln problem, vendar jim tega ni uspelo dokazati. Novost njihovega pristopa k reševanju problema je v uporabi več javno dostopnih BGP usmerjevalnih tabel. V nasprotju z [2] metoda ne uporablja informacije o stopnji avtonomnega sistema, temveč iz povprečnega položaja danega avtonomnega sistema v celotnem naboru usmerjevalnih poti sklepa o tem, kako blizu jedra interneta se sistem nahaja. Primerjava položajev dveh sosednjih avtonomnih sistemov je osnova predlagane hevristike za prepoznavanje tipa relacije med njima. Hevristika loči le med relacijami ponudnik– stranka in enakovreden-z-enakovrednim. NP-polnost problema ToR je pokazana v [5] in [10]. Avtorji neodvisno pridejo do sklepa, da rešitev problema ne določa natančnega položaja relacij enakovreden-z-enakovrednim. Predlagane hevristike so matematično najbolj eksaktne, dosegajo največje deleže usmerjevalnih poti brez dolin, a so omejene le na relacije tipa ponudnik–stranka. Vprašanje ujemanja relacij z dejanskimi ostane odprto. V [11] zgradijo delno rešitev problema z zbiranjem podatkov iz podatkovnih zbirk »BGP community« in »Internet Routing Registers« [12], v katerih nekateri avtonomni sistemi javno objavijo podatke o poslovnih relacijah. Z upoštevanjem pravil, izpeljanih iz lastnosti usmerjevalnih poti brez dolin, je mogoče določiti tudi relacije nekaterim sosednjim povezavam. Večkratna ponovitev postopka določi velik delež vseh relacij v omrežju. Avtorji za povezave, katerih algoritem ne zajame, uporabijo hevristiko iz [2]. Analiza pokaže, da tak pristop izboljša predvsem natančnost prepoznavanja relacij tipa enakovreden-z-enakovrednim. Modeliranje realnih omrežij avtonomnih sistemov 141 Članek [13] kritično analizira pravilnost pristopa k prepoznavanju relacij z reševanjem problema ToR. Avtorji navajajo, da lahko v nekaterih primerih povezavam pripišemo poljuben tip relacije, ne da bi pri tem spremenili število usmerjevalnih poti brez dolin. Ugotovijo tudi, da ignoriranje relacij tipa soroden-s- sorodnim vodi ne samo do zamegljene slike o realni strukturi interneta, temveč tudi do napačno prepoznanih relacij tipa ponudnik–stranka. S tem pokažejo, da zgolj hevristično izboljševanje rešitve problema ToR ne vodi k večji verodostojnosti prepoznanih relacij. Predlagajo razširitev problema z dodatnim optimizacijskim kriterijem, ki temelji na gradientu stopenj. Gradient stopenj za izbrano smer opazovane usmerjevalne poti pove, ali stopnja sosednjih avtonomnih sistemov narašča ali pada. Z upoštevanjem na novo vpeljanega kriterija postane avtonomni sistem z višjo stopnjo z večjo verjetnostjo ponudnik avtonomnemu sistemu z nižjo stopnjo. Ideja o gradientu stopenj je podobna filozofiji prve objavljene hevristike [2], vendar je to pot matematično izpopolnjena in nastopa v kombinaciji z reševanjem problema ToR. V zadnjem pomembnejšem delu [4] avtorji poudarijo pomanjkljivost algoritmov za reševanje problema ToR, da nekatere poznane usmerjevalne poti nepravilno razglasijo kot poti brez dolin in posledično vsaj eno relacijo na poti določijo napačno. Predlagana hevristika upošteva nove ugotovitve in ugotovitve predhodnikov ter določa vse tri tipe relacij. Relacije ponudnik–stranka in enakovreden-z-enakovrednim določi upoštevajoč gradient stopenj in maksimalno število usmerjevalnih poti brez dolin. Metoda presenetljivo dosega najboljše rezultate tedaj, ko ima gradient stopenj bistveno večjo težo kot maksimizacija števila usmerjevalnih poti brez dolin. Najugodnejše razmerje dosega vrednost 100:1. Za prepoznavanje relacij soroden-s-sorodnim se predlagani algoritem opira na podatkovne zbirke »Internet Routing Registers«. Pri evalvaciji svoje hevristike so se avtorji obrnili na upravitelje avtonomnih sistemov. Rezultati potrjujejo veliko natančnost prepoznanih relacij, ki dosega 94,2%. Pomemben prispevek avtorjev zadnje hevristike je tudi tedensko osvežena javno dostopna zbirka avtonomnih sistemov s pripadajočimi relacijami, kot jih določi njihov algoritem [14]. 4. Generiranje omrežij avtonomnih sistemov 4.1 Osnovni topološki generatorji Področje generiranja naključnih internetnih topologij je dokaj dobro raziskano, kar velja tako za topologije na ravni usmerjevalnikov kakor tudi za topologije povezovanja med avtonomnimi sistemi. Začetki segajo v leto 1988, ko je Waxman predlagal prvi generator, s katerim je poskušal imitirati povezovalne vzorce v takratnem internetu [15]. Osnova generatorja je naključni proces, odvisen le od evklidske razdalje med naključno porazdeljenimi vozlišči na ravnini. Za reprodukcijo čedalje bolj očitnih hierarhičnih vzorcev v internetu to ni zadostovalo, zato so v naslednji fazi nastali tako imenovani strukturni generatorji [16][17]. Striktno nivojska hierarhija teh generatorjev je odvisna od številnih vhodnih parametrov. Leta 1999 se je razumevanje strukture internetnih topologij korenito spremenilo z ugotovitvami bratov Faloutsos [18]. Na podlagi obsežnejših meritev so ugotovili, da se porazdelitev stopenj tako avtonomnih sistemov kakor tudi posameznih usmerjevalnikov podreja potenčnemu zakonu. Te lastnosti strukturni generatorji ne upoštevajo, zato je nastala povsem nova skupina tako imenovanih stopenjskih generatorjev [19][20][21][22][23]. Primarni cilj teh generatorjev je avtentična reprodukcija porazdelitve stopenj, medtem ko hierarhično strukturo omrežne topologije povsem ignorirajo. Kljub temu se pozneje izkaže, da stopenjski generatorji prekašajo strukturne generatorje tudi v tem pogledu [24]. Stopenjske generatorje imamo zato za zadnji dosežek pri verodostojnem modeliranju povezovalnih vzorcev internetnih topologij. 4.2 Relacijski generatorji Nam edini znani generator, ki modelira tudi tipe poslovnih relacij v omrežnih topologijah avtonomnih sistemov, je bil predlagan v [1]. Temelji na filozofiji stopenjskih generatorjev z razširitvijo stopenjske porazdelitvene funkcije na tipe relacij. Natančneje, razširjena porazdelitvena funkcija pove, koliko avtonomnih sistemov v omrežju ima določeno kombinacijo števila ponudnikov, strank in enakovrednih avtonomnih sistemov. Relacij soroden-s-sorodnim generator ne upošteva. Avtorji analizirajo porazdelitev relacij v grafih, ki jih pridobijo iz tabel BGP na strežnikih RouteViews [9] in z aplikacijo hevristik za prepoznavanje tipov relacij, opisanih v [13][4]. Pri modeliranju porazdelitvene funkcije uporabijo statistično orodje copulas [25]. Postopek generacije naključnega omrežja poteka v dveh korakih. V prvem se generira N trojic števil za N želenih avtonomnih sistemov. Posamezna trojka pomeni število relacij ponudnik–stranka, stranka–ponudnik in enakovreden-z-enakovrednim. V drugem koraku generator naključno poveže vozlišča tako, da zadovolji zahtevanemu številu relacij. Presežek relacij določenega tipa, ki nimajo ustreznega para, generator zanemari. Nazadnje odstrani še topološke nepravilnosti, kot so zanke in podvojene povezave med vozlišči. Avtorji ocenijo verodostojnost svojega modela na podlagi ujemanja stopenjske porazdelitvene funkcije po tipih relacij med izmerjenim realnim omrežjem in generiranim. Porazdelitve se po pričakovanju dobro ujemajo, saj generator reproducira porazdelitveno Vilhar, Novak, Kandus 142 funkcijo. Verodostojnosti naključne topologije iz vidika drugih kriterijev, kot je na primer ujemanje vsebovane hierarhije, avtorji ne ocenjujejo. Naključno povezovanje vozlišč v okviru predpisanih kvot za relacije je dvomljivo. Lahko nastanejo nepravilni hierarhični vzorci, kot je na primer relacija ponudnik–stranka, kjer majhen avtonomni sistem nastopa kot ponudnik velikemu. Poleg tega tak pristop ne zagotavlja usmerjevalne poti brez dolin za vsak par avtonomnih sistemov. Slabost generatorja je tudi hkratno reševanje dveh problemov: generiranje topologije in modeliranje tipov relacij. Stopenjsko metodo generacije lahko namreč nadomesti nova, izboljšana metoda. V tem primeru postane generator kot celota zastarel. 5. Problem določanja poslovnih relacij v naključnih grafih V nadaljevanju predlagamo ločitev modeliranja relacij med avtonomnimi sistemi od procesa naključnega generiranja omrežnih topologij. Menimo, da sta problema v veliki meri neodvisna in bolje rešljiva vsak zase. Razvoj osnovnih topoloških generatorjev, ki verodostojno reproducirajo bistvene lastnosti interneta, se tako lahko še naprej odvija ločeno. 5.1 Definicija problema Topologija omrežja avtonomnih sistemov je osnovni vhod algoritma, ki rešuje v nadaljevanju definirani problem. Iskanje najprimernejšega algoritma je aktivno področje naših raziskav. Cilj je določiti tip relacije vsem povezavam v grafu na način, ki zajame osnovne lastnosti komunikacij med avtonomnimi sistemi. Rezultat je označen graf. Identificirali smo pet potrebnih lastnosti označenega grafa. Če graf vsebuje te lastnosti, trdimo, da reproducira bistvene strukturne karakteristike realnega interneta. Zahtevane lastnosti formalno zapišemo v obliki definicije problema, ki ga imenujemo problem TRR (Type-of-Relationship problem in Random graphs). Definicija 1 (problema TRR). Pri danem neusmerjenem grafu G(V,E) z množico vozlišč V in množico povezav E poišči označen graf, tako da: 1. med vsakim parom vozlišč iz množice V obstaja vsaj ena pot brez dolin (lastnost povezanosti vozlišč); 2. označeni graf odraža hierarhično strukturo, primerljivo s hierarhično strukturo v merjenih grafih (lastnost hierarhične strukture); 3. v jedru označenega grafa obstoji klika1, ki vsebuje le povezave tipa enakovreden-z- 1 Klika je množica vozlišč V1 v grafu G(V,E), za katero velja, da med vsakim parom vozlišč v V1 obstoji povezava. enakovrednim (lastnost klike jedra); 4. usmerjenost povezav, ki pomenijo relacijo ponudnik–stranka, sledi padajočemu gradientu stopnje, pri čemer delež izjem ne presega vrednosti 0,5% (lastnost gradienta stopnje); 5. označeni graf ne vsebuje ciklov2, ki bi vsebovali urejeno zaporedje relacij ponudnik–stranka (lastnost odsotnosti ciklov ponudnik–stranka). 5.2 Utemeljitev zahtev Izpolnjevanje lastnosti povezanosti vozlišč zagotovi zmožnost komunikacije med poljubnima avtonomnima sistemoma v omrežju. Če med dvema avtonomnima sistemoma v omrežju ni usmerjevalnih poti brez dolin in se pravila izvažanja usmerjevalnih tabel dosledno upoštevajo, avtonomna sistema med seboj ne moreta komunicirati. Gre za nesprejemljiv pojav brez realne podlage, zato je povezanost vozlišč najpomembnejša lastnost označenega grafa. Obstoj hierarhične strukture v internetu je lastnost, ki je v raziskovalnih krogih široko sprejeta. Kaže se kot neenakomerna porazdelitev tranzitnega prometa med povezavami. Ker je eksaktno težko določljiva, jo je težko izpolniti, kot tudi preveriti. Primera hierarhične dekompozicije omrežij avtonomnih sistemov, ki upoštevata tipe relacij, najdemo v [26] in [3]. Dekompoziciji temeljita na različnih postopkih razvrščanja vozlišč v hierarhične nivoje. V [26] je razvrstitev vozlišč odvisna le od relacij ponudnik– stranka, pri čemer se upošteva oddaljenost vozlišča od jedra grafa v smislu omenjenih relacij. Metoda razlikuje še med čistimi strankami in ponudniki. Število hierarhičnih nivojev ni fiksno. V [3] razvrstijo vozlišča v pet nivojev. Končna razvrstitev, še posebej v višje nivoje, je močno odvisna od relacij enakovreden-z- enakovrednim. Oceno o primerljivosti hierarhične strukture označenega grafa z merjenim dobimo, če primerjamo deleže vozlišč po hierarhičnih nivojih. Od uporabljene metode dekompozicije je odvisno, ali bo ocena veljala za hierarhično strukturo relacij ponudnik- stranka ali predvsem za strukturo relacij enakovreden-z- enakovrednim. Če primerljivost hierarhične strukture modeliranega grafa z merjenim ni dosežena, obstoji večja verjetnost, da na splošno usmerjevalne poti v modeliranem omrežju ne odražajo realnih lastnosti. V merjenih omrežjih obstojijo avtonomni sistemi, ki so med seboj gosto povezani z relacijami enakovreden- z-enakovrednim in nimajo ponudnikov. Ti avtonomni sistemi so jedro omrežja, ki ima pomembno vlogo pri zagotavljanju povezljivosti in nosi znaten delež tranzitnega prometa. Klika tovrstnih sistemov je jedro v najožjem pomenu. Za verodostojno reprodukcijo karakteristik realnega omrežja bi moral tudi označeni graf vsebovati kliko, ki je po velikosti primerljiva z 2 Cikel je pot, za katero velja, da je začetno vozlišče hkrati tudi končno vozlišče. Modeliranje realnih omrežij avtonomnih sistemov 143 velikostjo klik v merjenih grafih. Če ta lastnost ni pravilno modelirana, obstoji večja verjetnost nepravilne porazdelitve globalnih prometnih tokov. Zaradi pomembne vloge jedra v hierarhiji celotnega omrežja se pričakuje tudi velik vpliv pravilne določitve klike na uspešnost reprodukcije lastnosti hierarhične strukture. Pri študiju tipov poslovnih relacij v merjenih omrežjih [14] smo ugotovili, da delež avtonomnih sistemov z nižjo stopnjo v vlogi ponudnika avtonomnemu sistemu z višjo stopnjo znaša le 0,2%. Upoštevajoč morebitne deviacije, v definiciji problema TRR zahtevamo delež 0,5%. Če doseženi delež presega zahtevanega, manjši avtonomni sistemi nastopajo v večjem številu usmerjevalnih poti brez dolin, zato nosijo več tranzitnega prometa kot v resničnem internetu. Cikel zaporedja relacij ponudnik–stranka pomeni, da avtonomni sistem posredno nastopa kot ponudnik samemu sebi. Gre za anomalijo, ki je v merjenih grafih ni, zato jo v zadnji lastnosti označenega grafa prepovemo. 6. Sklep V članku smo obravnavali problem verodostojnega modeliranja realnih omrežij avtonomnih sistemov. Analizirali smo posledice, ki izhajajo iz neupoštevanja poslovnih relacij, in pokazali, da je iskanje popolnejših modelov upravičeno. To področje je še slabo raziskano. Vsebinsko najbližji področji, ki smo ju podrobneje predstavili, sta prepoznavanje tipov relacij v resničnem internetu in generiranje topologij omrežij brez upoštevanja poslovnih relacij. Edini znani model, ki upošteva tipe poslovnih relacij, temelji na ideji stopenjskih generatorjev. Menimo, da predlagana metoda ne reproducira najbolje karakterističnih lastnosti omrežij. Predlagali smo nov pristop k reševanju problema, ki je neodvisen od konkretnega topološkega generatorja. V domeni matematičnih grafov smo definirali problem TRR. Problem zajema pet karakterističnih lastnosti interneta, ki smo jih določili na podlagi študije merjenih omrežij in izsledkov raziskav prepoznavanja tipov poslovnih relacij. Obstoječi model generacije označenih grafov eksplicitno ne upošteva nobene od petih lastnosti. Naše nadaljnje delo vključuje realizacijo metode, ki rešuje problem TRR in njeno verifikacijo. Proučiti nameravamo pomembnost vpliva upoštevanja redkejših tipov poslovnih relacij, pri čemer je treba nenehno spremljati izsledke prepoznavanja tipov relacij v resničnem internetu. 7. Literatura [1] X. Dimitropoulos and G. Riley, Modeling autonomous-system relationships, Proc. Int. Workshop on Principles of Advanced and Distributed Simulation PADS, Singapore, pp.143-149, 2006. [2] L. Gao, On inferring autonomous system relationships in the Internet, IEEE/ACM Transactions on Networking, vol.9, no.6, pp.733-745, 2001. [3] L. Subramanian, S. Agarwal, J. Rexford, and R. Katz, Characterizing the Internet hierarchy from multiple vantage points, Proc. IEEE INFOCOM, New York, USA, vol.2, pp.618- 627, 2002. [4] X. Dimitropoulos, D. Krioukov, M. Fomenkov, B. Huffaker, Y. Hyun, kc claffy, and G. Riley, AS relationships: Inference and validation, ACM SIGCOMM Computer Communication Review, vol.37, no.1, pp.29-40, 2007. [5] G. Battista, M. Patrignani, and M. Pizzonia, Computing the types of the relationships between autonomous systems, Proc. IEEE INFOCOM, San Francisco, California, USA, vol.1, pp.156-165, 2003. [6] L. Gao and F. Wang, The extent of AS path inflation by routing policies, Proc. IEEE GLOBECOM, Taipei, Taiwan, vol.3, pp.2180-2184, 2002. [7] H. Tangmunarunkit, R. Govindan, and S. Shenker, Internet path inflation due to policy routing, In SPIE ITCom, vol.4526, pp.188-195, 2001. [8] H. Soliman, C. Castelluccia, K.E. Malki, and L. Bellier, Hierarchical mobile IPv6 mobility management (HMIPv6), RFC 4140, 2005. [9] University of Oregon route views project, 2004. [10] T. Erlebach, A. Hall, and T. Schank, Classifying customer- provider relationships in the Internet, Proc. Int. Conf. on Communications and Computer Networks CCN, Cambridge, USA, pp.538-545, 2002. [11] J. Xia and L. Gao, On the evaluation of AS relationship inferences, Proc. IEEE GLOBECOM, Dallas, Texas, USA, vol.3, pp.1373-1377, 2004. [12] Internet Routing Registry, http://www.irr.net/docs/list.html. [13] X. Dimitropoulos, D. Krioukov, B. Huffaker, kc claffy, and G. Riley, Inferring AS relationships: Dead end or lively beginning?, Lecture Notes in Computer Science LNCS, vol.3503, pp.113-125, Springer-Verlag, 2005. [14] The CAIDA AS relationships dataset 2004-2006, http://www.caida.org/data/active/as-relationships/. [15] B.M. Waxman, Routing of multipoint connections, IEEE Journal of Selected Areas in Communications, vol.6, no.9, pp.1617-1622, 1988. [16] K.L. Calvert, M.B. Doar and E.W. Zegura, Modelling Internet topology, IEEE Communications Magazine, vol.35, no.6, pp.160-163, 1997. [17] M.B. Doar, A better model for generating test networks, Proc. IEEE GLOBECOM, London, UK, pp.86-93, 1996. [18] M. Faloutsos, P. Faloutsos, and C. Faloutsos, On power-law relationships of the Internet topology, ACM SIGCOMM Computer Communication Review, vol.29, no.4, pp.251-262, 1999. [19] A. Medina, A. Lakhina, I. Matta, and J. Byers, BRITE: An approach to universal topology generation, In Proceedings of MASCOTS 2001, Cincinnati, OH, pp.346-353, 2001. [20] D. Magoni and J.-J. Pansiot, Internet topology modeler based on map sampling, In Proc. 7th IEEE Symposium on Computers and Communications, Taormina, Italy, pp. 1021-1027, 2002. [21] J. Winick and S. Jamin, Inet-3.0: Internet topology generator, University of Michigan Technical Report CSE-TR-456-02, 2002. [22] W. Aiello, F. Chung, and L. Lu, A random graph model for massive graphs, Proc. Annual ACM Symposium on Theory of Computing STOC, Portland, Oregon, USA, pp.171-180, 2000. [23] Christopher R. Palmer and J. Gregory Steffan, Generating network topologies that obey power laws, In IEEE GLOBECOM, San Francisco, USA, vol.1, pp.434-438, 2000. [24] H. Tangmunarunkit, R. Govindan, S. Jamin, S. Shenker, W. Willinger, Network topology generators: Degree-based vs. structural, ACM SIGCOMM Computer Communication Review, vol.32, no.4, pp.147-159, 2002. [25] R. Nelson, An introduction to copulas, Lecture Notes in Statistics, vol.139, p.216, Springer-Verlag, 1999. Vilhar, Novak, Kandus 144 [26] Z. Ge, D. Figueiredo, S. Jaiswal, and L. Gao, On the hierarchical structure of the logical Internet graph, Proc. SPIE ITCom, Denver, Colorado, USA, pp.208-222, 2001. Andrej Vilhar je diplomiral leta 2004 na Fakulteti za elektrotehniko Univerze v Ljubljani. Na Odseku za komunikacijske sisteme na Institutu Jožef Stefan dela kot mladi raziskovalec. Je študent podiplomskega študija na Fakulteti za elektrotehniko Univerze v Ljubljani. Področje njegovega raziskovalnega dela so komunikacijski protokoli s poudarkom na usmerjevalnih algoritmih za upravljanje mobilnosti omrežij in omrežjih stratosferskih ploščadi. Roman Novak je diplomiral, magistriral in doktoriral v letih 1992, 1995 in 1998 na Fakulteti za računalništvo in informatiko Univerze v Ljubljani. Na Institutu Jožef Stefan dela kot raziskovalec na Odseku za komunikacijske sisteme od leta 1992. V preteklem obdobju je sodeloval in vodil številne znanstveno raziskovalne projekte s področij razvoja telekomunikacijskih omrežij, varnosti v komunikacijskih omrežjih, kriptografije, tehnologije pametnih kartic, in drugih. Trenutno področje njegovega raziskovalnega dela so mobilne komunikacije. Gorazd Kandus je diplomiral, magistriral in doktoriral v letih 1971, 1975 in 1991 na Fakulteti za elektrotehniko Univerze v Ljubljani. Na Institutu Jožef Stefan je vodja Odseka za komunikacijske sisteme. Njegovo raziskovalno področje obsega predvsem modeliranje in simulacijo prometa v satelitskih in prizemnih mobilnih omrežjih. Je koordinator več domačih in evropskih projektov ter soavtor številnih člankov. Na Univerzi v Mariboru je redni profesor ter aktivni predavatelj na dodiplomskem in podiplomskem študiju.