Technische Universiteit Delft

De opening van het collegejaar en alle intreeredes en promoties worden gehouden in de Aula van de TU Delft, Mekelweg 5, Delft

Routeren
14 september 2004 | 15.30 uur
F.A. Kuipers | elektrotechnisch ingenieur

Promotor | Prof.dr.ir. P. Van Mieghem (fac EWI)

Quality of service routing in the internet: Therory, Complexity and Algorithms
Het Internet bestaat uit vele netwerkelementen die als taak hebben om pakketjes het correcte pad naar hun bestemming te wijzen. Het vinden en volgen van het pad naar de bestemming wordt `routeren' genoemd. Het proces van routeren is niet feilloos, waardoor er pakketjes verloren kunnen gaan. Het huidige Internet kan geen kwaliteitsgaranties geven aan de pakketjes die het transporteert. Tegenwoordig zijn er echter vele nieuwe multimedia applicaties (b.v. VoIP), welke zonder dergelijke garanties niet goed kunnen functioneren. Het vinden van paden die verschillende garanties kunnen geven, leidt tot een nieuwe vorm van routeren: `Quality of Service (QoS)' routeren genoemd.
Dit proefschrift identificeert de concepten die aan QoS routeren ten grondslag liggen. Deze concepten zijn in ons SAMCRA algoritme verwerkt. Het eerste grootschalige onderzoek naar de prestaties van QoS algoritmes concludeert dat het SAMCRA algoritme het best presteert. Naast SAMCRA worden er in dit proefschrift ook algoritmes ontwikkeld voor multicast QoS routeren en voor QoS routeren middels gescheiden verbindingen.
QoS routeren is bewezen NP-compleet te zijn, hetgeen betekent dat exacte algoritmes in het ergste geval een complexiteit nodig hebben die niet kan worden begrensd door een polynomiale functie. Dit proefschrift beargumenteert dat de complexiteit van QoS routeren behapbaar is in de praktijk en dat dus geen heuristieken, maar exacte algoritmes zoals SAMCRA gebruikt moeten worden..
Tenslotte worden de dynamische aspecten in QoS routeren besproken en enkele nieuwe resultaten op dit gebied getoond. Wederom overtreft SAMCRA de andere algoritmes.

Voor verder lezen:

* Routing in the Internet by Christian Huitema, 2000

* Radio resource management for multimedia QoS support in wireless networks by Huan Chen... , 2004

* > Quality of service in multiservice IP networks: second international workshop, QoS-IP 2003, Milano, Italy, February 24-26, 2003, proceedings, ed. by Marco Ajmone Marsan... , 2003
* QoS in integrated 3G networks by Robert Lloyd-Evans, 2002