Verkossa on N solmua, joista joidenkin valilla on kaari. Kaaret ovat
seuraavassa suunnattuja, mutta tarkastelemissamme topologioissa yhteydet ovat symmetrisia (kaari (v; v0) olemassa joss (v0; v) on).
Tehtavana on valittaa verkkoa pitkin joukko paketteja, joista jokaisella on annettu alkupiste ja osoite (jotka ovat verkon solmuja). Paketin reitti on sille valittu verkon polku haluttujen solmujen valilla.
Yhden aikayksikon aikana
kukin paketti voi edeta korkeintaan yhden kaaren verran ja
kutakin kaarta pitkin voidaan lahettaa korkeintaan yksi paketti.
Solmuissa on (riittavasti) puskuritilaa paketeille, jotka odottavat
Verkon toiminnan maaraamiseksi pitaa kiinnittaa,
miten reitti valitaan, kun lahto- ja maalisolmut on annettu ja
missa jarjestyksessa samaa kaarta tarvitsevat paketit paasevat eteenpain (jonotus).
Tassa esiteltavien tulosten kannalta ei ole tarkeaa, miten jonotus hoidetaan, kunhan vain kaarten ei anneta olla joutilaina.
Verkon ruuhkautuminen riippuu tietysti siita, minka solmujen valilla paketteja lahetetan. Tarkastelemme seuraavassa tilanteita, joita syntyy permutaatioreitityksesta: jokainen solmu on seka lahtosolmuna etta maalisolmuna tasan yhdelle paketille.
Reititysongelma on kiinnostava lahinna, jos verkko on harva (kaaria paljon alle N(N 1)). Tarkastelemme esimerkkitopologiana hyperkuutiota. Tassa N = 2n, ja samastamme solmut joukon f 0; 1 gn alkioiden kanssa.
Hyperkuutiossa solmujen (a1; : : : ; an) ja (b1; : : : ; bn) valilla on kaari, jos on tasan yksi indeksi i jolla ai 6= bi.
Hyperkuutiossa on siis 2N log2N kaarta, ja verkon halkaisija (pisin kahden solmun etaisyys) on log2 N.
Lahtokohta reititykseen hyperkuutiossa on bitinkorjausalgoritmi.
Tarkastellaan pakettia, jonka lahtosolmu on a = (a1; : : : ; an) ja maalisolmu b = (b1; : : : ; bn). Kun i = 1; : : : ; n + 1, maaritellaan
vi = (b1; : : : ; bi 1; ai; : : : ; an):
Paketin polku kulkee nyt solmujen a = v1; v2; : : : ; vn+1 = b kautta.
(Kyseisesta solmulistasta saadaan varsinainen polku jattamalla pois toistuvat solmut, joita esiintyy kun ai = bi.)
Siis paketin "osoite korjataan" bitti kerrallaan, vasemmalta alkaen.
Bitinkorjausalgoritmi toimii hyvin keskimaaraisessa tapauksessa, kun maalisolmut valitaan satunnaisesti. Osoittautuu kuitenkin, etta joissain tapauksissa se johtaa ruuhkautumiseen ja vaatii ajan (N1=2).
Bitinkorjauksen pahimpien tapausten valttamiseksi tarkastelemme satunnaistettua kaksivaiheista reititysta.
Vaihe I: Valitse jokaiselle paketille satunnainen solmu "valitavoitteeksi".
Reitita paketit valitavoitteisiinsa bitinkorjauksella.
Vaihe II: Reitita paketit valitavoitteista lopullisiin tavoitteisiinsa bitinkorjauksella.
Osoitamme, etta todennakoisyydella 1 O(N 1) kaksivaiheinen reititys onnistuu ajassa O(log N). Koska log2N on verkon halkaisija, tama on (jollain tarkkuudella) optimaalista.
Se, milloin jokin paketti ylittaa tietyn reitilleen kuuluvan kaaren, riippuu tietysti siita, missa jarjestyksessa jonoja puretaan.
Analyysin yksinkertaistamiseksi olkoon T (M) aika, joka paketilta M kuluu maalinsa saavuttamiseen. Jokainen naista T (M) aika-askelista kuluu
jompaan kumpaan seuraavista:
1. paketti M ylittaa jonkin kaaren reitillaan tai
2. paketti M odottaa jonossa kun jokin toinen paketti ylittaa sen tarvitsemaa kaarta.
Olkoon X(e) niiden pakettien lukumaara, joiden reittiin kaari e kuuluu.
Edellisen perusteella tehdaan
Havainto: Jos paketin M reitti koostuu kaarista e1; : : : ; em, niin T (M)
Xm
X(e ):
Edellinen havainto sallii meidan keskittya polkujen analysoimiseen ja unohtaa jonotuskayttaytyminen jne. Kun P on polku, joka koostuu kaarista
e1; : : : ; em, maaritellaan
T (P ) = Xm i=1
X(ei):
Edellisen havainnon perusteella minka tahansa reitityksen viema aika on korkeintaan maxP 2RT (P ), missa R on reititykseen kuuluvien polkujen joukko.
Huomaa, etta edellinen patee mihin tahansa reititystilanteeseen. Olkoot erityisesti T1 ja X1 suureet T ja X kun rajoitutaan satunnaisen
kaksivaihereitytyksen vaiheeseen I. Osoitamme, etta suurella todennakoisyydella T (P ) 30n kaikilla mahdollisilla reiteilla P .
Kiinnitetaan nyt jokin polku P = (v0; : : : ; vm), joka on mahdollinen paketin reitti bitinkorjausalgoritmia kaytettaessa.
Haluamme suurella todennakoisyydella patevan rajan summalle T1(P ) = Pm
i=1X1(ei). Koska satunnaismuuttujat X1(ei) eivat ole riippumattomia, Chernon rajoja ei voi suoraan soveltaa.
Ongelman ratkaisemiseksi arvioimme ensin todennakoisyytta, etta vahintaan 6n eri pakettia ylittaa jonkin polun P kaaren.
Taman jalkeen osoitetaan, etta suurella todennakoisyydella mikaan yksittainen paketti ei kayta kovin monta kaarta polulla P .
Olkoon vi 1 solmu polulla P , ja j se bitti jonka osalta vi 1 ja vi poikkeavat.
Sanomme, etta paketti k on aktiivinen solmussa vi 1, jos 1. paketti k kulkee solmun vi 1 kautta, ja
2. paketin k tullessa solmuun vi 1 sen bittia j ei ole viela "korjattu".
Kun k = 1; : : : ; N, merkitaan Hk = 1 jos paketti k on aktiivinen jossain polun P solmussa. Olkoon H = PN
k=1 Hk.
Olkoon
vi 1 = (b1; : : : ; bj 1; aj; aj+1; : : : ; an) vi = (b1; : : : ; bj 1; bj; aj+1; : : : ; an):
Ehdon 2 mukaan solmussa vi 1 aktiivisen paketin lahtosolmu on muotoa (; : : : ; ; aj; : : : ; an). Siis mahdollisia lahtosolmuja on 2j 1.
Ehdon 1 mukaan solmussa vi 1 aktiivisen paketin maalisolmu on muotoa (b1; : : : ; bj 1; ; : : : ; ). Siis mahdollisen lahtosolmun paketista tulee aktiivinen todennakoisyydella 2 j+1.
Siis solmussa vi 1 aktiivisten pakettien maaran osotusarvo on 1, joten E[H] m 1 n:
Koska satunnaismuuttujat Hk ovat riippumattomia, voimme soveltaa Chernon rajaa (lause 4.7):
Pr(H 6n) 2 6n: Valitsemme nyt B = f H 6n g arviossa
Pr(A) = Pr(A j B) Pr(B) + Pr(A j B) Pr(B) Pr(B) + Pr(A j B):
Siis
Pr(T1(P )) 30n) 2 6n + Pr(T1(P ) 30n j H < 6n):
Arvioidaan seuraavaksi jalkimmaista ehdollista todennakoisyytta.
Oletetaan, etta paketti k on aktiivinen solmussa vi 1.
Jotta k todella kulkisi kaarta (vi 1; vi), sen osoitteessa bitin j on oltava aj. Taman todennakoisyys on 1=2.
Lisaksi edellytetaan, etta paketin k ei enaa tarvitse korjata mitaan aiempaa bittia 1; : : : ; j 1. Siis kaikkiaan solmussa vi 1 aktiivisen paketin
todennakoisyys tehda siirtyma (vi 1; vi) on korkeintaan 1=2.
Yleisemmin, jos paketti on polulla viela solmussa vl 1, l > i, niin sen todennakoisyys paatya solmuun vl on korkeintaan 1=2.
Toisaalta jos paketti ei solmusta vl 1 mene solmuun vl, se ei
myohemminkaan palaa polulle P . Talloin nimittain jokin paketin kohdeosoitteen biteista 1; : : : ; l poikkeaa polun P maalista. Koska
bitinkorjausalgoritmi ei enaa palaa naihin aiempiin bittehin, reitit jaavat pysyvasti erilleen.
Olkoon polun P solmuissa aktiivisia paketteja kaikkiaan h kappaletta. Milla todennakoisyydella ne yhteensa tekevat ainakin 30n siirtymaa polkua P
pitkin?
Ajatellaan, etta yksittaisessa kokeessa jokin aktiivinen paketti on jossain polun P solmussa. Korkeintaan todennakoisyydella 1=2 tapahtuu
onnistuminen: paketti siirtyy eteenpain polulla P . Ainakin
todennakoisyydella 1=2 tapahtuu epaonnistuminen: paketti poistuu polulta (eika koskaan palaa). Epaonnistumisen sattuessa siirrymme tarkastelemaan seuraavaa aktiivista pakettia.
Siis jokainen onnistuminen tuo yhden lisasiirtyman, mutta jokainen
epaonnistuminen kuluttaa yhden paketin. Jotta saadaan 30n siirtymaa, saa 30n + h ensimmaisessa kokeessa tulla korkeintaan h epaonnistumista.
Haluttu ehdollinen todennakoisyys
Pr(T1(P ) 30n j H 6n)
on siis todennakoisyys, etta em. toistokokeessa 36n toistolla tulee korkeintaan 6n epaonnistumista.
Koska jokaisessa kokeessa onnistumistodennakoisyys on korkeintaan 1=2, on helppo nahda etta
Pr(T1(P ) 30n j H 6n) Pr(Z 6n);
missa Z B(36n; 1=2). Soveltamalla Chernon rajaa (lause 4.9) saadaan Pr(T1(P ) 30n j H 6n) Pr(Z (1 2=3)18n
exp( 18n(2=3)2=2) = e 4n 2 3n 1: Siis
Pr(T1(P )) 30n) 2 6n + Pr(T1(P ) 30n j H < 6n) 2 3n:
Koska mahdollisia polkuja on N2 = 22n, todennakoisyys etta T1(P ) jollekin polulle on korkeintaan 22n2 3n = 2 n. Siis jos vaihetta II ei aloiteta, ennen kuin vaihe I on loppu, niin vaihe I menee todennakoisyydella 1 O(N 1) ajassa O(log N).
Vaiheen II analyysi on taysin samanlainen. Polut vain "todellisuudessa"
kuljetaan takaperin.
Lopuksi todetaan, etta vaihe II voidaan hyvin aloittaa, vaikka vaihe I ei olisi loppunut. Edellinen analyysi on helppo yleistaa osoittamaan, etta talloin todennakoisyydella 1 O(N 1) minkaan polun kaaria ei kayteta yli 60n kertaa.