Sažetak The work describes the design goals and methodology in creating a new model of optical telecommunication network used for studying network resilience. The model is implemented by discrete-event network simulator ns-3. The advantages of using the existing simulator core infrastructure provided by ns-3 are analyzed and compared to building own simulator from scratch, or selecting a tool among other existing simulators such as ns-2, OMNeT++, and commercial simulators. The requirements for feature functionality are outlined and high-level overview of the model architecture and its components are provided. The model is extended to support availability evaluation. Network availability is of paramount importance in optical telecommunication networks. Their rising connectivity and consequently their availability is compromised by link and node failures, usually due to physical force (e.g. digging, earthquake or fire). In optical networks a group of logically distinct links can unintentionally share a physical resource (e.g. a cable or a duct). Such a group, called shared risk link group (SRLG), introduces a situation where a single failure of common resource can cause multiple failures. Failure of common resource usually occurs due to physical force and causes failures of multiple links. Specifically, such a failure can cause both working and spare wavelength path of a logical connection between two edge nodes to fail at the same time, leaving them disconnected until a repair is done. The usual approach to solving this problem consists of introducing more spare capacity to the network and also using a routing algorithm that takes SRLGs into account when computing paths. Such a routing algorithm avoids creating working and spare path pairs that have links contained in the same SRLG, to minimize the negative impact of SRLG failure on logical connection availability. The number and length of SRLGs, as well as the characteristics of the underlying physical topology can significantly affect network availability. Especially, the physical topology can be represented by realistic synthetic graphs which are created by numerous geographic graph generators. The implementation and usage of six different physical topology models (Random Geometric, Gabriel, Relative Neighborhood, K-Nearest Neighbor, Waxman and Spatial Barabási-Albert) for investigation of the influence of the underlying topology on the optical telecommunication network availability is described. Network availability is estimated using Monte Carlo simulations based on a model of optical telecommunication network implemented by network simulator ns-3. Scenarios utilizing six topology models both in absence and presence of SRLGs are studied, and the optical network availability sensitivity to the underlying physical network topology is presented as the main result. Routing algorithms were proposed to ensure working and spare paths of a connection in a network are SRLG-disjoint to avoid such common cause failures. However, complete SRLG-disjointedness of working and spare path is not always possible due to limited number of links or limited capacity available in the network, so maximum SRLG-disjoint paths algorithm is taken instead. Maximum SRLG-disjoint path problem is in general NP-hard. In terms of solution quality greedy algorithms for maximum SRLG-disjoint path problem are as good as more complicated heuristics. To optimize maximum SRLG-disjoint path routing and wavelength assignment algorithm, a novel path weighting scheme was used. To improve the run-time performance of maximum SRLG-disjoint path greedy algorithm, it was implemented using NVIDIA CUDA heterogeneous parallel programming platform and executed on graphics processing unit.
Sažetak (hrvatski) Brzi porast količine prenesenog prometa putem interneta, podržan isto tako brzim povećanjem kapaciteta optičke transportne mreže čini otpornost mreže na kvarove zahtjevom koji je potrebno uključiti u procesu dizajna mreže. Kvar mrežnog elementa (primjerice, vlakna u kabelu ili prospojnika u čvoru) može uzrokovati prekid mnogih svjetlosnih puteva, što vodi gubitku podataka i prihoda. U slučaju kvara komponente puta koji koristi logički kanal u mreži, alternativni put (koji zovemo rezervnim) mora se koristiti sve dok sepopravak komponente osnovnog puta ne dogodi. Grupa veza s dijeljenim rizikom (shared risk link group, SRLG) je grupa veza u mreži koje dijele fizičku lokaciju. To može biti kabel, cijev ili izlaz na čvoru. Sve veze koje se nalaze u SRLG-u imaju mogućnost biti oštećene u slučaju kvara jedne veze koja se nalazi u SRLG-u. Takvo fizičkog oštećenje rezultira situacijom u kojoj višestruki logički kvarovi u mreži nastaju zbog jednog fizičkog kvara. SRLG uvodi zavisnost između kvarova veza, obzirom da se radi o skupu veza koje dijele zajednički fizički resurs kao što je prijelaz mosta, kabel ili cijev. č esta je pretpostavka da je korelacija između kvarova deterministička, što implicira da kvar pojedine veze u SRLG-u uvijek uzrokuje kvar svih ostalih veza koje on sadrži. U stvarnosti to nije nužno slučaj, pa su izučavani vjerojatnosni modeli u kojima veze sadržane u SRLG-u doživljavaju oštećenje s određenom vjerojatnosti. Zaključeno je da je utjecaj koreliranih kvarova (uključujući SRLGove) na raspoloživost mreže značajan. Brojni pristupi pružanja resursa putevima, specifično usmjeravanja i dodjele valnih duljina (routing and wavelength assignment, RWA) u optičkim mrežama koje sadrže SRLG-ove su razmatrani sa zajedničkim ciljem izbjegavanja istovremenog kvara osnovnog i rezervnog puta. RWA problem se može iskazati kao cjelobrojni linearni program. Obzirom da je općenito NP-težak, često se za rješavanje koriste heuristike. Uvodno poglavlje iznosi kontekst problema koji se u radu rješava, objašnjava motivaciju za istraživanjem i navodi sadržaj rada po poglavljima. Drugo poglavlje “Osnove optičkih telekomunikacijskih mreža” (Basics of Optical Telecommunication Networks) predstavlja temeljne pojmove područja optičkih mreža, počevši od optičkih kanala, preko čvorova u optičkoj mreži koji izvode obradu signala u električnoj domeni, sve do čvorova u mreži koji rade u sveoptičkoj domeni (tj. ne pretvaraju signal u električnu domenu). Poseban naglasak stavljen je na optičke prospojnike s mogućnošću rekonfiguracije, te s njima povezanu funkcionalnost za kontrolu i upravljanje mrežom. Treće poglavlje “Temelji simulacije mreža” (Fundamentals of Network Simulation) iznosi osnove područja simulacije mreža zasnovane na diskretnim događajima. Poseban naglasak stavljen je na simulaciju Monte Carlo koja je uzeta u razmatranje kao jedan od mogućih postupaka za rješavanje problema proračuna raspoloživosti optičke mreže. Navedeni su i opisani zahtjevi za model optičke mreže i simulator koji će ga koristiti. Zahtjevi uključuju podršku za kanale s većim brojem valnih duljina, model optičkog komutatora, granularnost komutacije, različite arhitekture komutatora, kontrolnu ravninu i mehanizme zaštite i obnavljanja u slučaju kvarova na komponentama mreže. Izneseni su razlozi zbog kojih nijedan od postojećih simulatora ne zadovoljava navedene zahtjeve. Zbog toga je u ovom poglavlju predložen i razvijen novi simulator zasnovan na mrežnom simulatoru ns-3. Četvrto poglavlje “Otpornost telekomunikacijskihmreža na kvarove” (Resilience of Telecommunication Networks) daje pregled područja otpornosti telekomunikacijskih mreža. Opravak nakon kvara u optičkoj telekomunikacijskoj mreži koji se koristi dalje u radu zasniva se na zaštiti puta i metodi zaštite s dodijeljenim kapacitetom. Također se definiraju metrike za proračun performansi raspoloživosti mreže, specifično raspoloživost. Peto poglavlje “Korelirani kvarovi veza u mreži” (Correlated Failures of Network Links) daje prikaz rezultata simulacije Monte Carlo zas mreže u prisustvu koreliranih kvarova na mrežnim vezama. Koristi se metoda zaštite puta s dodijeljenim kapacitetom. Opisani su modeli veza u mreži, modeli grupa veza s dijeljenim rizikom, modeli svjetlosnih putova i logičkih kanala. Svi opisani modeli implementirani su u u mrežnom simulatoru ns-3. U scenarijima gdje je to moguće izvesti, rezultati izračuna raspoloživost mreže dobiveni simulacijom Monte Carlo verificiraju se usporedbom s rezultatima dobivenim analitičkim putem. Rezultati izvođenja simulacije zasnovane na predloženom modelu pokazuju da fizička svojstva grupa veza s dijeljenim rizikom, specifično njihova duljina, značajno utječu na raspoloživost mreže. Šesto poglavlje “Utjecaj koreliranih kvarova na različite modele topologija” (Impact of Correlated Failures on Various Topology Models) analizira utjecaj grupa veza s dijeljenim izikom na raspoloživost mreže za šest različitih modela sintetičkih topologija (slučajni geometrijski, Gabrielov, model relativnog susjedstva, model k-najbližih susjeda, Waxmanov i Barabási-Albertov). Rezultati simulacije pokazuju da se utjecaji koreliranih kvarova grupe veza s dijeljenim rizikom znatno razlikuju među analiziranim modelima. Sedmo poglavlje “Optimizacija usmjeravanja i dodjele valnih duljina koja uzima u obzir grupe veza s dijeljenim rizikom” (Shared Risk Link Group-aware Optimization of Routing and Wavelength Assignmen) predstavlja postojeće pristupe usmjeravanju i dodjeli valnih duljina razvijene s ciljem maksimiziranja disjunktnosti grupa veza s dijeljenim rizikom. Predložen je i implementiran novi algoritam za rješavanje problema usmjeravanja i dodjele valnih duljijna. Predloženi algoritam koristi svojstva grupa veza s dijeljenim rizikom prilikom odabira rezervnih puteva. Cilj je poboljšati rezultirajuće raspoloživosti uspostavljenih svjetlosnih puteva. Verifikacija na studijskom primjeru mreže pokazuje da predloženi algoritam daje jednake ili bolje vrijednosti raspoloživosti mreže kod usporedbe rezultata s onima dobivenim izvođenjem postojećih algoritama. Predlažu se i raspravljaju, također, buduća poboljšanja predloženog algoritma. Osmo poglavlje “Optimizacija performansi korištenjem heterogenog paralelnog programiranja” (Performance Optimization Using Heterogeneous Parallel Programming) analizira vremensku složenost predloženog algoritama za usmjeravanje i dodjelu valnih duljina. Algoritam je implementiran korištenjem metoda heterogenog paralelnog programiranja i izvodi se na grafičkim procesorima NVIDIA s tehnologijom CUDA (Compute Unified Device Architecture). Rezultati pokazuju da paralelizacija korištenjem grafičkih procesora značajno smanjuje vrijeme izvođenja, čak do sedam puta. Dan je kratak pogled u budućnost računanja korištenjem grafičkih procesora te se navode smjerovi budućih istraživanja. Deveto, zaključno poglavlje rezimira iznesene rezultate i predlaže njihove primjene. Izvorni znanstveni doprinosi doktorskog rada sastoje se u sljedećem: * Model raspoloživosti optičke telekomunikacijske mreže koji uzima u obzir postojanje grupa veza s dijeljenim rizikom uz pretpostavku varijabilnih duljina koreliranih veza i proizvoljnih stupnjeva korelacije kvarova. * Metoda proračuna raspoloživosti primjenom simulacije Monte Carlo zasnovana na predloženom modelu raspoloživosti optičke telekomunikacijske mreže u prisustvu koreliranih kvarova. * Algoritam za usmjeravanje i dodjelu valnih duljina u optičkim mrežama s valnim multipleksiranjem koji optimira raspoloživost logičkih kanala obzirom na značajke grupa veza s dijeljenim rizikom, uz primjenu paralelizacije izvođenja korištenjem naprednih procesorskih arhitektura.
Ključne riječi (hrvatski)
optička telekomunikacijska mreža
pouzdanost mreže
raspoloživost mreže
modeliranje kvarova mreže
simulacija Monte Carlo
simulacija mreže
grupa veza s dijeljenim rizikom
usmjeravanje i dodjela valnih duljina
optimizacija algoritma
heterogeno paralelno programiranje