Thesis (MSc)--Stellenbosch University, 2003. / ENGLISH ABSTRACT: Routing policies for packet-switched communication networks must be able to adapt to changing traffic patterns and topologies. We study the feasibility of implementing an adaptive routing policy using the Q-Learning algorithm which learns sequences of actions from delayed rewards. The Q-Routing algorithm adapts a network's routing policy based on local information alone and converges toward an optimal solution. We demonstrate that Q-Routing is a viable alternative to other adaptive routing methods such as Bellman-Ford. We also study variations of Q-Routing designed to better explore possible routes and to take into consideration limited buffer size and optimize multiple objectives. / AFRIKAANSE OPSOMMING:Die roetering in kommunikasienetwerke moet kan aanpas by veranderings in netwerktopologie en verkeersverspreidings. Ons bestudeer die bruikbaarheid van 'n aanpasbare roeteringsalgoritme gebaseer op die "Q-Learning"-algoritme wat dit moontlik maak om 'n reeks besluite te kan neem gebaseer op vertraagde vergoedings. Die roeteringsalgoritme gebruik slegs nabygelee inligting om roeteringsbesluite te maak en konvergeer na 'n optimale oplossing. Ons demonstreer dat die roeteringsalgoritme 'n goeie alternatief vir aanpasbare roetering is, aangesien dit in baie opsigte beter vaar as die Bellman-Ford algoritme. Ons bestudeer ook variasies van die roeteringsalgoritme wat beter paaie kan ontdek, minder geheue gebruik by netwerkelemente, en wat meer as een doelfunksie kan optimeer.

Routing policies are now represented by RPSL and by its evolutionary extension called RPSLng. These languages can be used for describing unique routing policy of each autonomous system. Experience shows that even though there are translation tools from RPSL and RPSLng to configuration formats of commonly used routers, the actual network configuration is rarely generated from RPSL sources and routing policy is then perceived as marginal paperwork, which often does not reflect the real network settings. There will be most likely a need for RPSL format change in order to remedy the discrepancies. To support this I present long-term measurements of inaccuracies in routing policies compared to real paths in the Internet. I also present a list of the most frequent problems, and I offer suggestions, how to reform RPSL to improve situation in the long term. Powered by TCPDF (www.tcpdf.org)

Routing policies are now represented by RPSL and by its evolutionary extension called RPSLng. These languages can be used for describing unique routing policy of each autonomous system. Experience shows that even though there are translation tools from RPSL and RPSLng to configuration formats of commonly used routers, the actual network configuration is rarely generated from RPSL sources and routing policy is then perceived as marginal paperwork, which often does not reflect the real network settings. There will be most likely a need for RPSL format change in order to remedy the discrepancies. To support this I present long-term measurements of inaccuracies in routing policies compared to real paths in the Internet. I also present a list of the most frequent problems, and I offer suggestions, how to reform RPSL to improve situation in the long term. Powered by TCPDF (www.tcpdf.org)