home/Publications/H98

E. Hyytiä, Optimaalinen reititys ja aallonpituuksien jako täysoptisessa WDM-järjestelmässä, diplomityö, Teknillinen korkeakoulu, 1998.

Abstract: Tässä työssä tarkastellaan reitityksen ja aallonpituusjaon ongelmaa täysoptisessa WDM-järjestelmässä. Mikäli verkon solmupisteissä ei ole mahdollista suorittaa aallonpituuskonversiota, käytetty reititys asettaa lisärajoituksia aallonpituusallokaatiolle. Tällaisen verkon optimaalinen konfigurointi on siten hankalampi tehtävä kuin esimerkiksi perinteisen puhelinverkon, jossa ainoana rajoituksena on jokaisen yhteysvälin maksimikapasiteetti. Aallonpituuksien jako annetulla reitityksellä on olennaisesti graafin solmujen väritystehtävä, mikä on NP-hankala ongelma. Työssä esitetään joukko heuristisia menetelmiä solmujen värittämiseksi. Menetelmistä laadittiin C-kieliset toteutukset, joilla niiden toimintaa verrattiin. Lisäksi työssä esitetään algoritmi, joka pyrkii hakemaan sekä optimaalisen reitityksen että aallonpituusallokaation annetulle verkolle. Algoritmin toimintaa testattiin esimerkkiverkkojen tapauksissa. Kokeilluista heuristisista algoritmeista sopivina tähän ongelmaan voidaan pitää ahneita algoritmeja ja tabu-hakua. Ahne algoritmi on hyvin nopea ja robusti menetelmä. Tabu-haku taas antaa parhaita värityksiä, mutta ajoaika on huomattavasti suurempi kuin ahneilla algoritmeilla. Reitityksen ja aallonpituusallokaation ratkaiseva algoritmi toimii hyvin, kunhan verkossa vain on riittävästi fyysisiä yhteyksiä verrattuna haluttuihin päästä päähän -yhteyksiin.

BibTeX entry:

@mastersthesis{hyytia-thesis-1998,
  author = {Esa Hyyti{\"a}},
  title = {Optimaalinen reititys ja aallonpituuksien jako t{\"a}ysoptisessa {WDM}-j{\"a}rjestelm{\"a}ss{\"a}},
  type = {diplomity{\"o}},
  year = {1998},
  school = {Teknillinen korkeakoulu},
}