Geavanceerde peer-to-peer routeringprotocollen voor multimediadiensten op de Virtual Wall Mathias De Maré
Promotoren: prof. dr. ir. Filip De Turck, dr. Bart De Vleeschauwer Begeleiders: Jeroen Famaey, S teven L atré Masterproef ingediend tot het behalen van de academische graad van Master in de ingenieurswetenschappen: computerwetenschappen
Vakgroep Informatietechnologie Voorzitter: prof. dr. ir. Daniël De Zutter Faculteit Ingenieurswetenschappen Academiejaar 2009-2010
Geavanceerde peer-to-peer routeringprotocollen voor multimediadiensten op de Virtual Wall Mathias De Maré
Promotoren: prof. dr. ir. Filip De Turck, dr. Bart De Vleeschauwer Begeleiders: Jeroen Famaey, S teven L atré Masterproef ingediend tot het behalen van de academische graad van Master in de ingenieurswetenschappen: computerwetenschappen
Vakgroep Informatietechnologie Voorzitter: prof. dr. ir. Daniël De Zutter Faculteit Ingenieurswetenschappen Academiejaar 2009-2010
Voorwoord Computernetwerken in het algemeen hebben mijn interesse al jaren geleden gewekt. Als je kijkt naar de ongelooflijke schaal waarop het internet momenteel functioneert, hoe meer dan een miljard mensen communiceren bovenop een uitgebreid ecosysteem van netwerkprotocollen. De kans krijgen om rond een dergelijk geheel een scriptie te doen, sprak me dan ook sterk aan. Intussen ben ik aan het einde van de scriptie en mijn studies gekomen, en wens ik dan ook een aantal mensen te bedanken. Ik zou in de eerste plaats mijn promotoren, prof. dr. ir. Filip De Turck en dr. Bart De Vleeschauwer, evenals mijn begeleiders Jeroen Famaey en Steven Latr´e willen bedanken voor het opstellen van een zeer interessant scriptieonderwerp. Jeroen en Steven zou ik in het bijzonder ook nog willen bedanken voor de hulp die ik kreeg bij alle mogelijke vragen en problemen, ook als het even wat minder vlotte. Bedankt aan Joke Claeys en Maaike De Mar´e om mijn tekst door te nemen en te corrigeren. Bedankt aan Killian, voor de technische hulp bij video’s en RTP. Dank ook aan mijn vriendin Joke, die mij altijd gesteund heeft, en mij vol overtuiging liet weten ’dat het wel zou lukken’. Mijn familie heeft me de vorige 23 jaar altijd geholpen en mij de kans gegeven zo ver te raken. Bedankt!
Mathias De Mar´e, mei 2010
iv
Bruikleen De auteur geeft de toelating deze masterproef voor consultatie beschikbaar te stellen en delen van de masterproef te kopi¨eren voor persoonlijk gebruik. Elk ander gebruik valt onder de beperkingen van het auteursrecht, in het bijzonder met betrekking tot de verplichting de bron uitdrukkelijk te vermelden bij het aanhalen van resultaten uit deze masterproef.
Mathias De Mar´e, mei 2010
v
Geavanceerde peer-to-peer routeringprotocollen voor multimediadiensten op de Virtual Wall door Mathias De Mar´e Masterproef ingediend tot het behalen van de academische graad van M ASTER IN DE INGENIEURSWETENSCHAPPEN : COMPUTERWETENSCHAPPEN - OPTIE ICT Academiejaar 2009 - 2010 Promotoren: prof. dr. ir. Filip De Turck, dr. Bart De Vleeschauwer Begeleiders: Jeroen Famaey, Steven Latr´e Faculteit Ingenieurswetenschappen Universiteit Gent Vakgroep Informatietechnologie Voorzitter: prof. dr. ir. Dani¨el De Zutter
Samenvatting Een goede routering uitvoeren op internet, rekening houdend met kwaliteitsvereisten van gebruikers, is een zeer complexe materie. Op IP-niveau kan niet altijd voldaan worden aan de gestelde eisen. Routeringsalgoritmes met behulp van overlaynetwerken kunnen een alternatief bieden. In deze masterproef worden een aantal routeringsalgoritmes uitgewerkt. Een schaalbare architectuur voor het gebruik van deze algoritmes en het bieden van Quality of Service wordt voorgesteld. De kenmerken van een praktische implementatie van de architectuur worden onderzocht door middel van simulaties op de Virtual Wall.
Trefwoorden routering, overlay, peer-to-peer, detectie van falende verbindingen
Geavanceerde peer-to-peer routeringprotocollen voor multimediadiensten op de Virtual Wall Mathias De Mar´e Supervisor(s): Filip De Turck, Bart De Vleeschauwer, Jeroen Famaey, Steven Latr´e Abstract— In this article, we try to eliminate the lack of Quality of Service in Internet Protocol routing using an architecture built on overlay networks and peer-to-peer routing algorithms. The techniques were tested by simulating networks on an Emulab testbed. Keywords—Quality of Service, overlay network, peer-to-peer, routing algorithms
O
I. I NTRODUCTION
NE of the major problems with IP routing is the lack of Quality of Service (QoS) that can be offered. Existing techniques like IntServ [1] and DiffServ [2] try to tackle this problem, but they suffer from scalability or compatibility problems. In addition, IP routing protocols do not always manage to resolve networking issues quickly. The internet is divided into a large number of Autonomous Systems (ASs), that use different routing algorithms for internal routing and routing to other ASs. One of the major algorithms used for inter-AS routing is BGP, and it can suffer from convergence problems [3]. Because of this, solving network issues can take up to multiple minutes. In this article, we propose an alternative method to solve these issues using overlay networks., This does not require any major changes to existing infrastructure. The techniques have been tested on an Emulab testbed. II. OVERLAY NETWORKS Overlay networks form an additional, virtual network layer on the application level. A link between two network elements (nodes) on the overlay level translates to a full connection on the IP level. This way, by building on a number of IP connections, routing problems can be avoided, as shown in Figure 1.
III. A RCHITECTURE A. Overview To provide a flexible system supporting a number of overlay networks and routing algorithms, we set up an architecture separated into three major components. The data component stores the necessary data, like measurements of packetloss and previous settings. The second major part is the routing component. Different routing algorithms, as well as multiple overlay systems can be used. The implementation uses two routing algorithms and a single overlay system. Finally, the analysis component uses the data to determine how well current the currently used routing algorithm functions. Should performance be suboptimal, a different routing algorithm can be chosen. In order to allow flexible decisions, a rules engine was used. This makes it possible to easily develop new evaluation rules without having to create a new binary. Besides rules to evaluate routing quality, aggregation of network flows was also studied. Combining a number of flows allows a reduction in bandwidth, resulting in a more efficient network usage. B. Algorithms The CYCLON algorithm [4] was used to form a basic overlay network. A large number of routing algorithms have been developed to offer QoS on top of overlays. We have used an existing algorithm called One-hop Source routing [5] to provide routing around network problems with very limited overhead. In addition, we developed a more advanced algorithm called N Hop Routing. This system uses active probing to find high-performance alternative paths consisting of multiple overlay nodes. These algorithms were all implemented using the Click Modular Routing project. IV. E VALUATION To evaluate the implemented architecture, we ran several tests on a simulated network. A. Experimental setup
Fig. 1. Direct IP routing encounters problems. Overlay routing can avoid the problems by forming an alternative path.
The experiments were executed on an Emulab test platform. This consists of a large number of servers and allows building virtual topologies. In addition, we use Click Modular Router to simulate packet loss, delay and bandwidth limitations. For these experiments, a test setup was created. It consists of two clients and seven overlay routers. The experiment is displayed in Figure 2. The displayed overlay routers all execute IP routing as well, to simulate the underlying physical network. Each connection has a delay of 20 ms.
During the tests, a video stream was sent from the first client to the second client, through the overlay network.
header adds a certain percentage of overhead to each useful packet sent. In addition, extra overlay packets are sent to maintain information on the overlay network itself. We want to study the effect of the overhead on the amount of packet loss detected. To this end, we use the network shown in Figure 2 and send a video stream with a constant bitrate of 2500 Kbps from one client to another through the network. For each test, only a single routing algorithm is used. We vary the allowed bandwidth using Click Modular Router. The results of the experiment are shown in Figure 4.
Fig. 2. The basic testing occurred on a network consisting of two clients and 7 overlay routers.
B. Routing convergence speed A first element in the performance of overlay routing, is the amount of time it takes to converge to a connection satisfying the required QoS. We have tested this using a number of different decision rules. The rules will cause the routing algorithm to change when packet loss levels reach a certain threshold or do not manage to reach a specified minimum. The evaluation of packet loss can happen over specific intervals. The tests were run on evaluation intervals from 5 to 20 seconds and use a variable bitrate video stream. The results of the tests are shown in Figure 3.
Fig. 4. In general, a larger amount of packetloss is detected when using overlay routing.
In most of the measurements, we observe a higher packet loss using the overlay routing systems. The overhead can usually be detected, so it should be possible to write evaluation rules that prefer IP routing in this case. V. C ONCLUSION
Fig. 3. It’s possible to react quickly when a single network disruption is encountered.
It is clear that evaluating packet loss levels over a shorter interval allows faster response times. This is partially because One-hop Source routing manages to solve the packet loss issue immediately be routing through another overlay router. We have also run more advanced tests with multiple network disruptions. In this case, the higher intervals continue to perform at the same level, but the shorter intervals result in much higher response times. There is clearly a trade-off to make between speed and stability. C. Overhead Overlay routing introduces a certain amount of overhead due to two factors. Encapsulation of data packets with an overlay
The overlay routing algorithms presented in this article allow resolving network issues when IP routing fails. In addition, the architecture can switch to a more desired routing algorithm upon detecting a problem with one of the algorithms. This allows providing QoS, which gives a clear advantage over using purely IP routing. Unfortunately overlay routing causes a certain amount of overhead. This can cause issues on networks that are almost used to their full capacity. Also, overlay routing does not always manage to find an alternative path in a short time. As such, further research is certainly needed, and optimisations could be find be aggregating a number of network flows. R EFERENCES [1] R. Braden, D. Clark, and S. Shenker, “Integrated Services in the Internet Architecture: an Overview,” RFC 1633 (Informational), June 1994. [2] S. Blake, D. Black, M. Carlson, E. Davies, Z. Wang, and W. Weiss, “An Architecture for Differentiated Service,” RFC 2475 (Informational), Dec. 1998, Updated by RFC 3260. [3] Craig Labovitz, Abha Ahuja, Abhijit Bose, and Farnam Jahanian, “Delayed internet routing convergence,” in in Proc. ACM SIGCOMM, 2000, pp. 175– 187. [4] Spyros Voulgaris, Daniela Gavidia, and Maarten van Steen, “CYCLON: inexpensive membership management for unstructured P2P overlays,” Journal of Network and Systems Management, vol. 13, no. 2, pp. 197–217, June 2005. [5] Krishna P. Gummadi, Harsha V. Madhyastha, Steven D. Gribble, Henry M. Levy, and David Wetherall, “Improving the reliability of Internet paths with One-hop Source Routing,” in In OSDI, 2004, pp. 183–198.
Inhoudsopgave Voorwoord
iv
Bruikleen
v
Overzicht
vi
Extended abstract
vii
Lijst van begrippen
xi
1
Inleiding 1.1 De complexiteit van het internet . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Kwaliteit in een onzeker netwerk . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Doelstellingen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
Literatuurstudie 2.1 Routering op het internet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 QoS via het Internet Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Overlayroutering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.1 Resilient Overlay Network . . . . . . . . . . . . . . . . . . . . . . . 2.3.2 One-hop Source routing . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.3 Kwaliteitsgevoelige routeringsprotocollen voor overlaynetwerken 2.3.4 Overlay Peer Utility Service . . . . . . . . . . . . . . . . . . . . . . . 2.4 Vergelijking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5 Distributed Hash Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.6 Artifici¨ele Intelligentie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.7 Alternatieve concepten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.8 Conclusie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
Architectuur 3.1 Vereisten . . . . . . . . . . . . . . . . 3.1.1 Niet-functionele eisen . . . . 3.1.2 Functionele eisen . . . . . . . 3.2 Scenario’s . . . . . . . . . . . . . . . 3.2.1 Nieuwe applicatie . . . . . . 3.2.2 Applicatie vereist nieuw pad
. . . . . .
ix
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . . . . . . . .
. . . . . .
1 1 2 2
. . . . . . . . . . . .
4 4 5 5 6 7 7 8 9 9 10 11 11
. . . . . .
12 12 12 13 15 15 15
. . . . .
16 17 17 17 18
. . . . . . .
22 22 22 24 26 28 28 28
. . . . . . .
32 32 32 32 34 42 42 43
. . . . . .
46 46 47 48 50 51 52
7
Conclusie 7.1 Toekomstig werk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
54 54
8
Click Router implementatie
56
9
Overzicht CD-ROM 9.1 Implementatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.2 Experimenten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
60 60 60
3.3
4
5
6
3.2.3 Verandering in applicatie eisen . . . . . 3.2.4 Policywijziging . . . . . . . . . . . . . . Opgestelde architectuur op basis van vereisten 3.3.1 Situering . . . . . . . . . . . . . . . . . . 3.3.2 Detailbeeld . . . . . . . . . . . . . . . .
Algoritmes 4.1 Routeringscomponent . . . . . 4.1.1 Overlaynetwerk . . . . . 4.1.2 Routering . . . . . . . . 4.2 Monitoring . . . . . . . . . . . . 4.3 Analysecomponent . . . . . . . 4.3.1 Algemene beslissingen . 4.3.2 Beperken van overhead
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
Implementatie 5.1 Routeringscomponent . . . . . . . . . . . . 5.1.1 Click Modular Router . . . . . . . . 5.1.2 Pad doorheen de router . . . . . . . 5.1.3 Ge¨ımplementeerde Clickelementen 5.2 Logische component . . . . . . . . . . . . . 5.2.1 Regelgebaseerd systeem . . . . . . . 5.2.2 Voorbeelden van regels . . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . .
. . . . . . .
. . . . . . .
. . . . .
. . . . . . .
. . . . . . .
. . . . .
. . . . . . .
. . . . . . .
. . . . .
. . . . . . .
. . . . . . .
. . . . .
. . . . . . .
. . . . . . .
. . . . .
. . . . . . .
. . . . . . .
. . . . .
. . . . . . .
. . . . . . .
. . . . .
. . . . . . .
. . . . . . .
. . . . .
. . . . . . .
. . . . . . .
. . . . .
. . . . . . .
. . . . . . .
. . . . .
. . . . . . .
. . . . . . .
. . . . .
. . . . . . .
. . . . . . .
. . . . .
. . . . . . .
. . . . . . .
. . . . .
. . . . . . .
. . . . . . .
. . . . .
. . . . . . .
. . . . . . .
. . . . .
. . . . . . .
. . . . . . .
Testmethodiek en Resultaten 6.1 Opstelling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 Gecombineerde routerings- en snelheidstest . . . . . . . . . . . . . . . . . . 6.2.1 Netwerk met een slecht functionerende verbinding . . . . . . . . . 6.2.2 Netwerk met een groot aantal slecht functionerende verbindingen 6.3 Routeringsgedrag bij verzadigd netwerk . . . . . . . . . . . . . . . . . . . 6.4 Aggregatie van verbindingen . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . .
. . . . . . .
. . . . . . .
. . . . . .
Bibliografie
62
Lijst van figuren
63
Lijst van tabellen
65
Lijst van begrippen AI AS BGP CBR CPN DHT IETF IP OPUS OSPF P2P QoS QRON RON RTP VBR VoIP
Artifici¨ele Intelligentie Autonoom Systeem Border Gateway Protocol Constant BitRate Cognitive Packet Network Distributed Hash Table Internet Engineering Task Force Internet Protocol Overlay Peer Utility Service Open Shortest Path First Peer-to-peer Quality of Service Quality-of-Service-aware routing protocols for Overlay Networks Resilient Overlay Network Real-Time Protocol Variable BitRate Voice over Internet Protocol
xi
Hoofdstuk 1
Inleiding 1.1
De complexiteit van het internet
Het internet is een zeer grote verzameling van onderling verbonden netwerken, die vaak op complexe manieren data doorgeven. Dit zorgt ervoor dat het moeilijk is om altijd snel en correct te reageren op problemen, of om garanties te geven op gebied van Quality of Service (QoS). Er wordt steeds vaker gebruik gemaakt van interactieve diensten, telefonie, software voor videoconferenties, enz. Voor online telefonie mag de vertragingstijd bijvoorbeeld niet te groot zijn om een vlot gesprek te kunnen voeren. Bovendien mag die vertragingstijd ook niet te sterk vari¨eren. Videoconferenties verliezen hun nut als het beeld te sterk gedegradeerd is door pakketten die onderweg verloren gaan. Het Internet Protocol (IP) probeert problemen wel te omzeilen, maar houdt daarbij niet noodzakelijk rekening met pakketverlies of vertragingstijd. IP bevat onder andere routeringsprotocollen, om data te versturen tussen verschillende netwerkapparaten. Het internet is opgebouwd uit een heleboel Autonome Systemen (AS’en) van verschillende netwerkoperatoren. De routeringsprotocollen op IP-niveau moeten dan ook in twee delen bekeken worden. Binnen AS’en heeft de netwerkoperator een globaal overzicht. De communicatie tussen AS’en geeft netwerkoperatoren slechts informatie over een deel van het netwerk. De twee gevallen worden weergegeven in Figuur 1.1. Voor routering binnen een AS wordt gebruik gemaakt van Open Shortest Path First (OSPF) routering [1], terwijl men de communicatie tussen AS’en regelt met het Border Gateway Protocol (BGP) [2]. Deze routeringsalgoritmes kunnen echter langdurige routeringsproblemen ondervinden (tientallen seconden tot zelfs meerdere minuten [3]).
1
Figuur 1.1: Routering in het internet gebeurt met verschillende algoritmes binnen Autonome Systemen en tussen Autonome Systemen.
1.2
Kwaliteit in een onzeker netwerk
Overlaynetwerken kunnen een oplossing bieden voor enerzijds de QoS-beperkingen op IPniveau, en anderzijds de soms langdurige routeringsproblemen. Dit werd ook bestudeerd in een aantal papers [4][5][6]. Een overlay is een bijkomende, virtuele netwerklaag op applicatieniveau. Een link tussen 2 knopen op dit overlayniveau vertaalt zich naar een volledig pad op IP-niveau. Routeren via een overlay zal de paden die op IP-niveau gevormd zijn niet aanpassen, maar zal er dus bovenop proberen een alternatief pad te vormen. Dit wordt ook weergegeven in Figuur 1.2. Een voorbeeld van een overlaynetwerk bovenop IP is Resilient Overlay Routing [4] (RON). Alle netwerkelementen (meestal wordt naar de netwerkelementen in een overlaynetwerk verwezen als ’knopen’) in dit netwerk sturen elkaar regelmatig berichten, om te controleren of de andere knopen nog bereikbaar zijn. Als een knoop niet meer rechtstreeks bereikt kan worden, worden pakketten via een andere tussenliggende knoop gestuurd. Een alternatief pad wordt dus bepaald via de overlay. Een dergelijk overlaynetwerk kan dus pakketten via een tussenliggende computer sturen, om een betere verbinding te krijgen. Zo kan men pakketten routeren langs snellere paden, of pakketverlies vermijden, om zo QoS te kunnen voorzien.
1.3
Doelstellingen
Het doel van deze scriptie is een systeem te ontwikkelen voor overlayroutering. Dit systeem omvat een aantal punten. Het is de bedoeling om een zekere QoS aan te bieden, ondanks mogelijke netwerkproble-
Figuur 1.2: Rechtstreekse routering ondervindt problemen. Overlayroutering kan de netwerkproblemen omzeilen.
men. Bepaalde eisen moeten dus gesteld kunnen worden op vlak van pakketverlies, vertragingstijd of variatie van vertragingstijd. Bovendien moet het mogelijk zijn om deze vereisten te vari¨eren van gebruiker tot gebruiker. Men kan de gebruikers opsplitsen in groepen volgens hoeveel zij betalen voor netwerktoegang. Gebruikers die meer betalen kunnen dan bijvoorbeeld een QoS verkrijgen die een lager pakketverlies inhoudt. Een verder punt dat in de thesis bestudeerd wordt, is het nut van het wisselen tussen routeringsalgoritmes. Alle netwerkalgoritmes hebben bepaalde nadelen, waardoor ze soms minder goed presteren. In hoeverre zou het bijvoorbeeld haalbaar zijn om een alternatief algoritme te gebruiken als BGP zich onstabiel gedraagt? Dezelfde vraag kan gesteld worden over het gebruik van overlayroutering. Het is dus belangrijk hier dieper op in te gaan. De rest van deze thesis is als volgt gestructureerd. De voor- en nadelen van een aantal routeringsalgoritmes worden beschreven in Hoofdstuk 2. In Hoofdstuk 3 wordt een architectuur voorgesteld die de verschillende doelstellingen mogelijk maakt. In Hoofdstuk 4 worden de gebruikte algoritmes overlopen, zowel op vlak van routering als voor het bekomen van de nodige meetgegevens. Hoofdstuk 5 handelt vervolgens over de verschillende onderdelen die ge¨ımplementeerd werden.
Hoofdstuk 2
Literatuurstudie Eerst overlopen we in Sectie 2.1 hoe routering op het niveau van het Internet Protocol (IP) verloopt. Sectie 2.2 handelt over de bestaande methodes om op IP-niveau Quality of Service (QoS) te bieden. In Sectie 2.3 worden verschillende types overlaynetwerken besproken. De voor- en nadelen van de routeringstechnieken worden hierbij bestudeerd. Distributed Hash Tables (DHT’s) bieden een mogelijke oplossing voor schaalbaarheidsproblemen. Deze bekijken we in Sectie 2.5. Een mogelijk alternatief voor traditionele overlayroutering wordt geboden door technieken die gebruik maken van Artifici¨ele Intelligentie (AI). Dit wordt beschreven in Sectie 2.6.
2.1
Routering op het internet
Het internet is opgedeeld in Autonome Systemen (AS) van verschillende netwerkoperatoren. Binnen een Autonoom Systeem (AS) wordt vaak gebruik gemaakt van Open Shortest Path First routering (OSPF) [1]. OSPF heeft een globaal overzicht en wordt gebruikt binnen kleinere netwerken. Dit zorgt ervoor dat de juiste routering binnen enkele tientallen seconden gevonden kan worden [7]. Deze routering houdt echter niet noodzakelijk rekening met de kwaliteit van het pad. OSPF kan bijvoorbeeld paden kiezen op basis van het aantal tussenliggende routers. Voor routering tussen AS’en wordt gebruik gemaakt van het Border Gateway Protocol(BGP) [2]. Dit complexe protocol laat communicatie toe tussen een zeer groot aantal netwerkoperatoren. Wijzigingen in de topologie (een router van een bepaalde AS die faalt) kunnen echter langdurige routeringsproblemen tot gevolg hebben (enkele minuten [3]). Kwaad opzet is ook een mogelijkheid. Zo kan een BGP-router aankondigen dat bepaalde netwerkadressen via die router bereikbaar zijn, om verkeer af te luisteren of te blokkeren.
4
2.2
QoS via het Internet Protocol
Oorspronkelijk was voor QoS geen functionaliteit voorzien binnen IP. De Internet Engineering Task Force IETF) werkte onder andere IntServ [8] en DiffServ [9] uit om dit probleem aan te pakken. IntServ is een architectuur die probeert een zekere QoS aan te bieden door middel van reservaties. Als een gebruiker een nieuwe verbinding probeert op te zetten, zal IntServ aan de tussenliggende routers vragen om het vereiste verkeer te reserveren voor de gebruiker. Elke netwerkverbinding vereist dus een aparte reservatie. Als een aanvraag tot reservatie niet goedgekeurd wordt, wordt dit verkeer als ’best effort’ verstuurd. Dit houdt in dat de router het verkeer wel zal proberen toe te laten, maar er zijn geen garanties. DiffServ werkt minder gedetailleerd. Dit protocol definieert een aantal klassen verkeer, die elk verschillende kenmerken en prioriteiten hebben. Alle verkeer krijgt automatisch een klasse toegewezen (bijvoorbeeld op basis van het IP-adres of de netwerkpoort). Alle routers houden dan rekening met de toegewezen klasse om bepaalde QoS te leveren. Op deze manier kan men bijvoorbeeld telefonieverkeer voorrang geven. Deze implementaties van QoS hebben echter ook een aantal nadelen. Zo is IntServ zeer weinig schaalbaar [10]. DiffServ is wel schaalbaar, maar heeft een onvoorspelbaar end-toend-gedrag (door het gebrek aan vaste regels in meerdere AS’en) en vereist bovendien een implementatie op alle tussenliggende knopen.
2.3
Overlayroutering
Overlaynetwerken vormen een bijkomende netwerklaag op applicatieniveau. Verschillende knopen van de overlay zijn op IP-niveau te bereiken via een volledig pad. Een dergelijk pad is slechts een link op het overlayniveau. Knopen op dit overlayniveau kunnen dus een pad vormen via meerdere links, en bijgevolg via meerdere paden op IP-niveau. Overlays worden gebruikt om extra functionaliteit te geven aan een netwerk door middel van deze extra netwerklaag. In het geval van overlayroutering wordt dit onder andere gebruikt om alternatieve paden te zoeken bij netwerkproblemen. Algemeen kan men zeggen dat via overlays de routering aangepast kan worden door op applicatieniveau andere routeringspaden te volgen. Het gebruik van deze alternatieve routeringspaden, zorgt ervoor dat ook een zekere QoS aangeboden kan worden. Via het overlaynetwerk kan namelijk een beter pad gezocht worden. Deze overlays bieden naast het omzeilen van netwerkproblemen nog heel wat mogelijkheden. Elke knoop in een overlay kan bijvoorbeeld een beperkte hoeveelheid gegevens bijhouden. Dit wordt onder andere bij Distributed Hash Tables (zie Sectie 2.5) gebruikt om opzoekingen te doen. De combinatie van opzoekingen en overlayroutering kan bijvoor-
beeld gebruikt worden bij Peer-to-Peer-communicatie (P2P-communicatie) voor telefonie en televisie.
2.3.1
Resilient Overlay Network
Resilient Overlay Network [4] (RON) implementeert een overlay netwerk waarbij de verschillende elementen (knopen) volledig geconnecteerd zijn (een ’full mesh’ vormen). Iedere knoop stuurt regelmatig (ongeveer elke 10 seconden) een pakket naar elke andere knoop. Op deze manier kan gecontroleerd worden welke knopen rechtstreeks bereikbaar zijn. Als de versturende knoop geen reactie krijgt, wordt vervolgens aan een hogere frequentie een aantal extra pakketten verstuurd. Als geen van deze pakketten een reactie oplevert, wordt de ontvangende knoop als onbereikbaar beschouwd. Komt er echter minimaal e´ e´ n reactie, dan houdt het zenden van bijkomende pakketten op. De teruggestuurde pakketten leveren informatie op over verliezen op een bepaalde verbinding, over vertragingstijd (’latency’) en over de variatie in vertragingstijd (’jitter’). Op basis van de pakketten kan dus met een rekenkundig of exponentieel gemiddelde een benaderende waarde voor deze kwaliteitsmetrieken bepaald worden. Hieruit kunnen de ’beste’ (afhankelijk van de metriek) overlayroutes bepaald worden. Men kan bijvoorbeeld voor een lage vertragingstijd kiezen, of voor een combinatie van lage variatie in vertragingstijd en lage verliezen, afhankelijk van de vereisten. Voor Voice over IP (VoIP) is een lage vertragingstijd bijvoorbeeld veel belangrijker dan bij het doorsturen van grote bestanden. Op basis van de vereisten en de beschikbare gegevens over de kwaliteit van de verbindingen, kan dan een tussenliggende knoop uitgekozen worden, waarlangs de data gerouteerd wordt. RON biedt een voordeel op vlak van robuustheid, en slaagt er in een lager pakketverlies, en in sommige gevallen ook lagere vertragingstijd op te leveren. Het grote nadeel is de schaalbaarheid van RON. De topologie is volledig geconnecteerd. Elke knoop vraagt regelmatig gegevens op aan elke andere knoop, wat het systeem een complexiteit van O n2 geeft. Hierdoor is het systeem slechts bruikbaar voor een beperkt aantal knopen. Het bandbreedtegebruik wordt ook in Figuur 2.1 weergegeven. Hiervoor worden dezelfde waarden gebruikt als in de oorspronkelijke paper over RON [4]. Elke knoop controleert elke 12 seconden welke andere knopen nog bereikbaar zijn. Dit vereist het sturen van N pakketten met elk een constante lengte. Elke knoop stuurt bovendien om de 14 seconden een routeringsbericht naar elke andere knoop, met informatie over welke knopen bereikbaar zijn. Dit vereist het sturen van N pakketten met een lengte die lineair is in het aantal knopen.
Figuur 2.1: Resilient Overlay Networking zorgt voor veel overhead op vlak van bandbreedtegebruik.
2.3.2
One-hop Source routing
One-hop Source routing [5] doet wat denken aan RON, maar laat het continu controleren van verbindingen weg. Als geen rechtstreekse verbinding met een knoop te verkrijgen is, wordt willekeurig een andere knoop uitgekozen om als tussenliggende overlayknoop te functioneren. De simpliciteit vermijdt schaalbaarheidsproblemen. De werking van Onehop Source routing biedt echter veel minder garanties voor QoS. Er is namelijk veel minder controle op de kwaliteit van de paden.
2.3.3
Kwaliteitsgevoelige routeringsprotocollen voor overlaynetwerken
Quality-of-Service-aware routing protocols for Overlay Networks [6] (QRON) lost het schaalbaarheidsprobleem van RON op door een hi¨erarchische werking te implementeren. Het systeem maakt gebruik van Overlay Brokers (OB’s), die verspreid zijn over de verschillende Autonome Systemen (AS’en) in het internet. Deze OB’s zijn binnen een AS volledig geconnecteerd, en tussen AS’en zijn ze verbonden volgens de fysieke verbindingen tussen AS’en. De OB’s worden volgens deze fysieke verbindingen geclusterd, waardoor een hi¨erarchisch netwerk opgebouwd wordt. Dit wordt ook weergegeven in Figuur 2.2, waar een aantal clusters gevormd worden. Een gebruiker die het QRON-netwerk wenst te gebruiken, maakt eerst verbinding met een van de OB’s, die vervolgens bepaalt (gelijkaardig aan RON) langs welke OB’s best gerouteerd wordt. Hierbij geldt wel de belangrijke beperking dat enkel tussen OB’s die rechtstreeks verbonden zijn, gerouteerd kan worden. Het grote nadeel bij QRON is dus de ineffici¨entie van het routeren via de verschillende niveau’s. Men zit vast aan de hi¨erarchische structuur, waardoor onnodig veel tussenliggende OB’s ge¨ıntroduceerd worden. Dit levert een grotere vertragingstijd op, waardoor QRON
Figuur 2.2: QRON gebruikt een aantal Overlay Brokers die een hi¨erarchisch netwerk vormen.
voornamelijk geschikt blijkt voor applicaties die zich op bandbreedte concentreren. Vanwege deze hi¨erarchische structuur moet de fysieke topologie ook gekend zijn om de OB’s te positioneren. Samenwerking met de netwerkoperatoren is dus vereist, wat ervoor zorgt dat het overlaysysteem niet meer puur op de applicatielaag functioneert.
2.3.4
Overlay Peer Utility Service
Overlay Peer Utility Service [11] (OPUS) is ook een overlaynetwerk dat het schaalbaarheidsprobleem van RON probeert te vermijden. Het maakt hier echter bijkomend gebruik van probabilistische methodes en een beperkte lokale netwerkkennis, om op die manier de vereiste communicatie binnen de perken te kunnen houden. OPUS introduceert echter nog een interessant concept, genaamd ’restricted flooding’. De data wordt redundant over meerdere paden verstuurd. Op deze manier bekomt men een betere betrouwbaarheid. Dit is een nuttig concept, dat we kunnen gebruiken om een hogere QoS op vlak van pakketverlies te verkrijgen, maar uiteraard zorgt dit wel voor een sterk verhoogd bandbreedtegebruik, met een hoger risico op overbelasting van het netwerk. Dit concept kan ook uitgebreid worden naar het opsplitsen van de data in twee paden zonder duplicatie [12], om op die manier sneller de gegevens te kunnen versturen. Hierbij verdwijnt het bandbreedtenadeel van het versturen van redundante gegevens, maar kan de gebruiker door de hogere snelheid wel andere verbindingen en knopen overbelasten.
2.4
Vergelijking
In Tabel 2.1 worden de algoritmes op een aantal punten met elkaar vergeleken. Dit is geen exact en exhaustief overzicht, maar geeft aan dat elk algoritme een aantal positieve en negatieve punten heeft. Routering RON One-hop Source QRON OPUS
Schaalbaarheid
QoS
Beperking netwerkoverhead
Reactiesnelheid
+ ++ +++ +++
+++ + ++ ++
+ +++ ++ ++
+++ + + +
Tabel 2.1: We kunnen in een algemeen overzicht de voor- en nadelen van verschillende algoritmes naast elkaar leggen.
2.5
Distributed Hash Tables
Zowel het schaalbaarheidsprobleem bij RON als het topologieprobleem bij QRON (enkel routeren via bepaalde paden, bepaald door de hi¨erarchie) kunnen opgelost worden door te werken met Distributed Hash Tables (DHT’s). Deze vormen een netwerk waarbij iedere knoop een unieke hash toegewezen krijgt ter identificatie. Elke knoop kent slechts een klein deel van het netwerk, waarvan vooral knopen die een gelijkaardige hash hebben. Als een knoop een andere hash zoekt, vraagt hij info aan de buren die zich zo dicht mogelijk bij die andere hash bevinden (die dus een gelijkaardige hashfunctie hebben). Deze vragen op hun beurt ook info aan hun eigen buren. DHT’s zoals Kademlia [13] laten op deze manier toe een bepaalde knoop te vinden met complexiteit O (log(n)). Hermes [14] implementeert een overlayroutering met behulp van een DHT. Het doel van Hermes is om een schaalbaar ’publish/subscribe’-systeem op te zetten. IndiQoS [15] bouwt hierop verder, en voegt bovendien de mogelijkheid tot QoS toe. Hiertoe houden knopen in het netwerk de kwaliteit bij van de links met hun directe buren (gelijkaardig aan RON). Als men doorheen het netwerk een verbinding opbouwt, weet elke knoop welke kwaliteit ondersteund wordt door de verbinding met de volgende knoop. Dergelijke systemen bieden het voordeel van schaalbaarheid en onafhankelijkheid van de fysieke topologie. Netwerken van honderdduizenden knopen zullen een tiental tussenliggende knopen meer hebben bij opgezette verbindingen in vergelijking met netwerken van een duizendtal knopen. De vertragingstijd zal hierdoor dus vrij hoog liggen.
2.6
Artifici¨ele Intelligentie
Routering via Artifici¨ele Intelligentie (AI-routering) selecteert adaptief routeringspaden aan de hand van technieken zoals ondersteunend leren(reinforcement learning) of mierenkolonieoptimalisatie (ant colony optimisation). Zo is er het Cognitive Packet Network [16] (CPN) dat paden selecteert voor een bepaalde QoS aan de hand van ondersteunend leren [17]. Hiervoor worden intelligente pakketten rondgestuurd. Deze worden gerouteerd met een algoritme op basis van ondersteunend leren, met als doel een bepaalde QoS te bereiken. Eenmaal verschillende paden werden gevolgd, worden deze gecombineerd en gemuteerd aan de hand van een genetisch algoritme. Als een intelligent pakket zijn bestemming bereikt, wordt in omgekeerde richting een reactie gestuurd, met als inhoud het gevolgde pad. Zowel de intelligente pakketten als de reacties erop worden enkel voor de routering gebruikt. Gewone datapakketten volgen gewoon de best bekende route naar de bestemming. Het voordeel aan deze aanpak is dat geen perfecte kennis van het netwerk vereist is zoals bij RON. Dit zorgt voor een betere schaalbaarheid van het netwerk. De extra pakketten die in het netwerk worden toegevoegd, zorgen wel voor slechtere resultaten als het netwerk zwaar belast wordt. Een bijkomend nadeel is de tijd die vereist is om aan nieuwe netwerkomstandigheden aan te passen. De genetische algoritmes gebruiken ook oudere gegevens, waardoor het even duurt voor een probleem merkbaar wordt. Een alternatief routeringsalgoritme, mierenkolonieoptimalisatie (ant colony optimisation) [18], is gebaseerd op idee¨en uit de biologie. Het concept houdt in dat een aantal pakketten (de mieren) door het netwerk worden gestuurd met een bepaalde bestemming. Bij elke knoop waar ze arriveren, wordt een keuze gemaakt over de volgende routeringsstap. Als de mieren de uiteindelijke bestemming bereiken, keren ze terug via hetzelfde pad, en laten bij elke tussenliggende knoop ’feromonen’ achter. Deze feromonen zijn bevestigende signalen die aan later bezoekende mieren aanraden hetzelfde pad te gebruiken. Routes die korter zijn, krijgen dus vaker feromonen, omdat het minder lang duurt de route af te leggen. Het kiezen van de volgende knoop gebeurt op basis van de feromonen, die een voorkeur aangeven. Daarnaast is er nog een kleine kans op een willekeurige beslissing. Dit zorgt ervoor dat niet-bezochte paden die een goede kwaliteit leveren, uiteindelijk ook gebruikt zullen worden. Dit routeringsalgoritme convergeert dus ook naar de kortste route, en kan op die manier voor een kleinere vertragingstijd zorgen. De overhead kan bovendien beperkt worden, door routeringspakketten te bevestigen aan datapakketten. Ook hier is er wel wat convergentietijd nodig bij de initi¨ele opbouw van de routes. Dit is noodzakelijk om extreem lange routes te vermijden.
2.7
Alternatieve concepten
Men kan nog alternatieve methodes gebruiken om routeringsproblemen en beperkingen bij QoS van de IP-laag op te lossen. Zo is het mogelijk bij video om I-frames te prioritiseren [19]. Op deze manier kan men ondanks pakketverlies nog een behoorlijke kwaliteit bekomen. Het nadeel hierbij is dat het werkelijke probleem niet aangepakt wordt. Men krijgt dus enkel een goede kwaliteit bij protocollen waar men bepaalde elementen een hogere prioriteit kan geven aan een deel van de data. Een andere mogelijkheid is een tussenliggende provider, die bandbreedte koopt bij de ISP’s en deze doorverkoopt aan klanten, waarbij voldaan is aan een bepaalde QoS [20].
2.8
Conclusie
Er zijn heel wat technieken om een alternatieve routering op te zetten, met elk hun voor- en nadelen. Technieken zoals Artifici¨ele Intelligentie kunnen een heel effici¨ente route vinden, maar wegens de hoge convergentietijd zullen we die in de masterproef niet behandelen. One-hop Source routing biedt een eenvoudige techniek die, in tegenstelling tot RON, routeringsoverhead beperkt houdt. Het nadeel van One-hop Source routing is de beperkte garantie op routeringskwaliteit. Om dit probleem aan te pakken, wordt in sectie 4.1.2 een algoritme uitgewerkt dat het lage bandbreedtegebruik van One-hop Source routing probeert te combineren met de mogelijkheid tot een betere QoS. Dit algoritme vormt een hybride tussen verschillende algoritmes in sectie 2.3 en maakt routering via meerdere tussenliggende knopen mogelijk.
Hoofdstuk 3
Architectuur We wensen een architectuur te implementeren die de mogelijkheid biedt bovenop een overlaynetwerk meerdere routeringsprotocollen te gebruiken. Er wordt gebruik gemaakt van het overlaynetwerk om alternatieve routering mogelijk te maken. Dit laat toe om onder andere oplossingen uit te werken voor netwerkproblemen. Deze architectuur wordt uitgewerkt als een bijkomende netwerklaag, net onder de applicatielaag. De implementatie van meerdere routeringsprotocollen is nodig omdat elk protocol voor- en nadelen heeft, zoals ook bestudeerd in de literatuurstudie in Sectie 2.3. Het gebruik van meerdere protocollen laat toe over te schakelen tussen deze protocollen bij veranderende vereisten of netwerkomstandigheden. Als deze overschakeling effici¨ent en op de juiste tijdstippen gebeurt, kan hiermee Quality of Service (QoS) ondersteund worden.
3.1
Vereisten
De architectuur heeft een aantal vereisten. Enerzijds zijn er bepaalde functies of taken die mogelijk moeten worden door het gebruik van de vooropgestelde architectuur. Dit zijn functionele vereisten. Anderzijds moet het ook mogelijk zijn bij de architectuur zekere kwaliteitseisen te stellen, die echter geen functies realiseren. Dit zijn niet-functionele vereisten.
3.1.1
Niet-functionele eisen
Afhandelingssnelheid Een eerste eis waaraan de architectuur moet voldoen, is dat deze snel moet zijn. De middlewarelaag moet zo snel mogelijk verzoeken afhandelen. Op deze manier wordt vermeden dat pakketten extra vertraging ondervinden. Een lage afhandelingssnelheid zou er ook voor zorgen dat niet alle pakketten verwerkt kunnen worden, waardoor een deel verloren gaat. 12
De afhandelingssnelheid is dus cruciaal om een goede QoS te behouden.
Transparantie We willen de middleware isoleren van de applicaties. Zo kunnen we vermijden dat applicaties wijzigingen moeten ondergaan om gebruik te maken van de architectuur.
Generieke opbouw De architectuur moet generiek zijn. Dit wil zeggen dat het systeem zoveel mogelijk verschillende applicatietypes ondersteunt, waarbij de middlewarelaag zich aanpast aan verschillende vereisten. Zo kan een niet-voorzien applicatietype zoals een online spel toegevoegd worden. Dit is perfect te gebruiken, door de parameters op een lage vertragingstijd en weinig pakketverlies in te stellen.
Veiligheid De architectuur moet veilig zijn. Dit houdt in dat het bijvoorbeeld niet mogelijk mag zijn voor niet-geauthoriseerde personen om het beleid in het netwerk in te stellen. We willen ook vermijden dat een ’Man-in-the-middle’-aanval uitgevoerd kan worden om data die tussen knopen verstuurd wordt te bemachtigen. Degelijke beveiliging is cruciaal binnen een re¨ele implementatie van de architectuur. Het valt echter buiten het doel van deze thesis en werd dus niet ge¨ımplementeerd.
3.1.2
Functionele eisen
Pluginarchitectuur voor routeringsprotocollen Het moet mogelijk zijn meerdere routeringsprotocollen te gebruiken binnen de middleware. Bovendien is het belangrijk eenvoudig tussen deze protocollen te kunnen overschakelen als dit voordelen biedt. Netwerkprotocollen hebben verschillende prestaties onder andere netwerkomstandigheden. Sommige protocollen zullen bijvoorbeeld betere resultaten geven bij pakketverlies.
Dynamische routeringskeuze De keuze van routeringsprotocol moet te bepalen zijn per stroom, per IP of per groep IP’s. Bovendien moet het mogelijk zijn tijdens het gebruik te wisselen van protocol, ook binnen een bepaalde stroom. Hierbij moet een afweging gemaakt worden tussen heel gedetailleerd routeren en het verkrijgen van schaalbaarheid. Als we per stroom een aparte routering opstellen, zal er veel overhead zijn, zowel op vlak van bandbreedte, als voor het nemen van beslissingen. In een grote router kan er sprake zijn van honderdduizenden stromen, waardoor gedetailleerde routering totaal onhaalbaar is. Bij een dergelijke router kan men bijvoorbeeld routeren per hub, om dan in kleinere routers gedetailleerder te werken.
Gebruik van policies Policies zijn vooropgestelde regels om beslissingen te nemen op basis van bepaalde gebeurtenissen en voorwaarden.[21] Een voorbeeld van een policy is om video op zo hoog mogelijke kwaliteit weer te geven. Bij het gebruik van een televisiescherm vertaalt dit zich bijvoorbeeld naar het weergeven van een 1080p-video. Op het scherm van een mobiele telefoon levert dit echter een veel kleinere resolutie op. Het moet mogelijk zijn gebruik te maken van policies op een hoog en een laag niveau (zowel bij het instellen ervan als bij het toepassen ervan) en aan de hand hiervan het gebruik van bepaalde routeringsprotocollen toe te laten, evenals de maximale bandbreedte in te stellen. Binnen de thesis werd niet specifiek op dit onderwerp geconcentreerd.
Instellen en controleren van QoS Controlemechanismes moeten aanwezig zijn om te controleren welke QoS de verschillende routeringsprotocollen op bepaalde momenten kunnen aanbieden, en om te bepalen welke QoS ze moeten proberen te bereiken. QoS moet ook instelbaar zijn op basis van gebruikers- en policyvereisten. Dit kan er bijvoorbeeld voor zorgen dat een live videostream minder pakketverlies ondervindt, omdat vanwege QoS-eisen een andere route gekozen wordt. Het bezoeken van gewone websites vereist geen specifieke QoS, waardoor het zoeken van een alternatieve route niet noodzakelijk is.
3.2
Scenario’s
Het is belangrijk een overzicht te krijgen van een aantal scenario’s waarbij gebruik gemaakt wordt van de architectuur. Op deze manier kunnen we inschatten in hoeverre de architectuur kan voldoen aan de vereisten.
3.2.1
Nieuwe applicatie
Een gebruiker start een applicatie voor videostreaming. De applicatie verstuurt gegevens die een lage vertragingstijd vereisen, evenals weinig pakketverlies. De middlewarelaag vangt de pakketten op en stuurt deze langs andere computers die ook gebruik maken van de middlewarelaag, met als doel om te voldoen aan de QoS-vereisten.
Hoofdscenario 1. De applicatie stuurt pakketten uit naar de streamingserver. 2. De middlewarelaag laat eerst pakketten rechtstreeks naar de server sturen (en vervolgens terug). 3. Op basis van de pakketten (de poort van de server waarnaar gestuurd wordt) wordt een QoS gekozen met weinig variatie in vertragingstijd, om te vermijden dat een te grote buffer ingesteld moet worden. Er wordt meteen ook monitoring gedaan, om te controleren of de directe verbinding performant genoeg is. 4. De directe verbinding blijkt niet performant genoeg. 5. Pakketten worden vervolgens via overlayroutering verstuurd.
Varianten Er wordt niet meteen gedetecteerd welk type applicatie opgestart werd. In dit geval wordt een standaard QoS gekozen. Een mogelijkheid hierbij is ook dat standaard geen QoS gegeven wordt. Op deze manier wordt vermeden dat extra middelen toegewezen worden terwijl deze onnodig zijn. De verdere stappen kunnen uitgevoerd worden zoals in het hoofdscenario.
3.2.2
Applicatie vereist nieuw pad
Een applicatie (streaming video) maakt gebruik van overlayroutering om te communiceren met de server. De applicatie verstuurt en ontvangt gegevens, en heeft een bepaalde QoS
nodig. Het overlaypad voldoet oorspronkelijk aan deze QoS, maar de kwaliteit van het pad verandert.
Hoofdscenario 1. Het routeringsprogramma vraagt regelmatig om monitoring. Het probleem wordt op deze manier gedetecteerd. 2. Het routeringsprogramma vraagt vervolgens om bijkomende knopen met welbepaalde QoS-eisen. 3. Een aantal knopen worden geselecteerd, waarna een nieuw pad opgebouwd wordt (het oude pad wordt intussen nog gebruikt). 4. Het nieuwe pad wordt gemonitord, om zeker te zijn dat dit wel voldoet aan de vereiste QoS. 5. Het nieuwe pad voldoet aan de gevraagde QoS. 6. Nieuwe pakketten worden verstuurd via het nieuwe pad.
Varianten Een pad met de vereiste QoS kan niet gevonden worden. In dit geval wordt regelmatig een andere routering uitgeprobeerd. Er kan dan gecontroleerd worden of de andere routering op een later tijdstip wel kan voldoen aan de vereiste QoS.
3.2.3
Verandering in applicatie eisen
Een applicatie maakt gebruik van overlayroutering en heeft bepaalde QoS-eisen. Dit kan bijvoorbeeld een applicatie voor videostreaming zijn. De bandbreedte van streaming video is variabel, en deze stijgt op een bepaald moment sterk. De paden waarlangs gerouteerd wordt, leveren hierdoor niet de ge¨eiste QoS.
Hoofdscenario 1. Monitoring zorgt ervoor dat een probleem in het pad gedetecteerd wordt. 2. Het routeringsprogramma vraagt om andere geschikte knopen, disjunct van de knopen van het oorspronkelijke pad. 3. Een nieuw overlaypad wordt opgebouwd en het oude pad wordt behouden. 4. Pakketten worden over beide paden gerouteerd, waardoor aan de QoS wordt voldaan.
Varianten Het probleem wordt niet correct gedetecteerd. Het is mogelijk dat monitoring van het systeem een verkeerd probleem detecteert, en dus een ander pad selecteert dat de problemen niet oplost. Bij hogere eisen op vlak van bandbreedte kan de vertragingstijd bijvoorbeeld ook sterk stijgen. Het nieuwe pad zal dus niet voldoen aan de vereisten. Op basis van de gegevens over de eerdere problemen kan dan afgeleid worden dat het probleem niet met vertragingstijden te maken heeft. Op deze manier kan men het oorspronkelijke probleem vinden en oplossen.
3.2.4
Policywijziging
Een policywijziging wordt doorgestuurd naar de middleware. De toegelaten bandbreedte voor niet-betalende gebruikers kan bijvoorbeeld verhoogd worden van 5 Mbit naar 10 Mbit.
Hoofdscenario 1. De policy wordt gewijzigd. 2. De middlewarelaag merkt een wijziging in de policy op, en controleert of de huidige routes voldoen aan de policy. 3. De routes voldoen aan de nieuwe vereisten, er is voldoende bandbreedte beschikbaar. 4. De policy wordt correct gevolgd.
Varianten Het is mogelijk dat een opgestelde route niet voldoet aan de eisen van de nieuwe policy. In dit geval zal een nieuwe route worden opgesteld, rekening houdend met de eisen.
3.3 3.3.1
Opgestelde architectuur op basis van vereisten Situering
De middlewarelaag waarin onze architectuur ge¨ımplementeerd is, situeert zich tussen de applicaties en de transportlaag. Op deze manier zorgen we meteen voor transparantie ten opzichte van de applicaties. De middlewarelaag ontvangt enerzijds de pakketten van verschillende applicaties, en anderszijds de pakketten die van het netwerk afkomstig zijn.
(a) Rechtstreekse routering ondervindt problemen.
(b) Door gebruik van de middlewarelaag wordt het probleem omzeild.
Figuur 3.1: Een netwerkprobleem zorgt ervoor dat de rechtstreekse IP-verbinding niet meer functioneert. Overlayroutering laat toe toch een verbinding te maken.
Deze middlewarelaag hoeft niet noodzakelijk aanwezig te zijn op de toestellen van de gebruiker, deze kunnen ook als een externe proxy functioneren. Op deze manier kan een netwerkprovider bijkomende routering implementeren en QoS mogelijk maken zonder dat hiervoor nieuwe toestellen vereist zijn bij de gebruiker. Er is dus ook een transparantie ten opzichte van de onderliggende netwerkprotocollen. Bij het gebruik van deze architectuur op een deel van de netwerkapparaten is het dus mogelijk om slechts een klein deel van het netwerk deze functionaliteit te geven. De andere netwerkapparaten zullen nog steeds correct functioneren. In Figuur 3.1a wordt een netwerk weergegeven waar Gebruiker1 verbinding probeert te maken met een server. De rechtstreekse routering faalt. Met behulp van de middlewarelaag kan dit probleem aangepakt worden, zoals weergegeven in Figuur 3.1b. Gebruiker1 stuurt in dit geval een pakket naar de middlewarelaag, waar een tussenliggende knoop (de Overlayrouter) uitgekozen wordt. Het pakket wordt dan ge¨encapsuleerd in een IP-pakket naar deze tussenliggende knoop. De verdere keuzes van de Overlayrouter hangen van de implementatie af. Een mogelijkheid is dat de encapsulatie verwijderd wordt, en het pakket rechtstreeks doorgestuurd wordt naar de Server. Een andere mogelijkheid is dat een volgende knoop wordt uitgekozen om het pakket verder langs te sturen. In dit geval blijkt dat echter onnodig.
3.3.2
Detailbeeld
Om scheiding van functionaliteit te bekomen, kunnen we de middlewarelaag opsplitsen in een drieledige architectuur, zoals weergegeven in Figuur 3.2. Het afscheiden van de ver-
Figuur 3.2: De opbouw van de middlewarelaag in meer detail, met de verschillende onderdelen weergegeven.
schillende elementen laat toe deze quasi volledig onafhankelijk uit te werken. Zo kan gekozen worden om een router met de middlewarelaag te implementeren, puur om data verder te sturen. In dit geval kan een deel van de functionaliteit verwijderd worden. Zo is de link met de applicatielaag hierbij onnodig, en kan mogelijk ook een deel van de beslissingsalgoritmes verwijderd worden. Op deze manier is het mogelijk de middlewarelaag ook te implementeren op netwerkelementen die niet krachtig zijn. Het eerste deel van de architectuur is de datacomponent. Deze omvat onder andere de gegevens over de kwaliteit van verbindingen met andere netwerkknopen. Dergelijke gegevens kunnen gedurende lange tijd bijgehouden worden, om onder andere trends over het netwerkverkeer af te leiden, waardoor netwerkproblemen beter aangepakt kunnen worden. De kwaliteitsgegevens worden verzameld door middel van een monitoringsysteem. Dit kan een aantal gegevens onderzoeken, waaronder pakketverlies, de vertragingstijd voor bepaalde verbindingen en de variatie in vertragingstijd van deze verbindingen. De hoeveelheid monitoring die uitgevoerd wordt, evenals de duur van het bijhouden van de bekomen gegevens, veroorzaken een zekere overhead. Daarom zou een netwerkknoop met beperkte hardware gegevens bijvoorbeeld slechts gedurende een korte tijdsspanne kunnen bijhouden, of de monitoring beperken tot enkel noodzakelijke gegevens. Deze keuze vereist een zekere afweging tussen de hoeveelheid overhead die toegelaten is, en de kwaliteit die geleverd moet worden. Op een hoog niveau is een dergelijke keuze te defini¨eren als
een policy. Een dergelijke policy kan bijvoorbeeld zijn dat de kwaliteit bijzonder belangrijk is. In dat geval zal een apparaat met beperkte hardware minder netwerkstromen kunnen behandelen. De kwaliteit van de netwerkstromen zal dan wel hoger liggen. Een andere mogelijke policy is dat het aantal netwerkstromen dat verwerkt kan worden ook belangrijk is. Deze policy kan op een minder krachtig apparaat ge¨ınterpreteerd worden als een keuze om minder monitoring te doen. Op een krachtiger toestel kan op basis van de policy en de beschikbare rekenkracht gekozen worden om de monitoring toch uitgebreid te houden. Policies worden ook bijgehouden in de datacomponent. In beperkte mate kan een gebruiker ook gedeeltelijke toegang krijgen tot zijn eigen netwerkknoop en bepaalde instellingen kiezen. Hiervoor is een beheersinterface vereist. Daarop werd niet geconcentreerd tijdens de implementatie van de thesis, maar voor een gebruiksvriendelijke implementatie zou dit wel vereist zijn. Een dergelijke interface zou ook goed beveiligd moeten zijn, om mogelijk misbruik tegen te gaan. Verder is er nog een algemene kennisdatabank. Deze kan bijkomende gegevens over routeringsalgoritmes en overlays bijhouden. Het datagedeelte staat in verbinding met de analysecomponent, die van de datacomponent gegevens kan opvragen. De precieze verbindingen worden weergegeven in Figuur 3.2. De policies worden doorgegeven aan de redeneerstappen, om er rekening mee te houden bij de nodige routeringswijzigingen. Naar de kennisdatabank en monitoringgegevens staat een dubbele pijl, omdat de analysecomponent bepaalde gegevens kan opslaan, en op geregelde tijdstippen de gegevens ophaalt om conclusies uit te trekken. De gegevens worden in een volgende stap bekeken om de kwaliteit van de gebruikte routering te evalueren. Een mogelijke kwaliteitscontrole is het bestuderen van pakketverlies via de routering gedurende de laatste 10 seconden. Deze controles kunnen ge¨ınterpreteerd worden als een stel regels, waaruit kennis afgeleid kan worden. Op basis van de bekomen resultaten van de kwaliteitscontrole kunnen beslissingen genomen worden over de routeringsprotocollen of de overlaysystemen. Een ander routeringsprotocol kan gekozen worden voor een bepaalde netwerkstroom, of er kan een wijziging gebeuren bij een protocol dat in gebruik blijft. Een mogelijkheid is bijvoorbeeld het zoeken van een nieuw pad met hetzelfde protocol. Binnen de implementatie gebeurt dit momenteel gedeeltelijk, bij een van de protocollen. Als overgeschakeld wordt van dit protocol naar een andere routering en even later teruggeschakeld wordt, zoekt het systeem een nieuw pad. De routering en overlays vormen de routeringscomponent. Dit gedeelte haalt pakketten binnen en stuurt pakketten uit. Deze wordt gebruikt voor communicatie met de applicaties (via een proxy) en met externe partijen (andere knopen in een overlaynetwerk of een rechtstreekse verbinding met een server). Als pakketten arriveren van een externe partij, worden deze doorgestuurd naar een van de
overlayprotocollen (of rechtstreeks naar een applicatie, als het pakket rechtstreeks van de server komt). Het overlayprotocol haalt bijkomende gegevens uit het pakket en geeft het vervolgens door aan het juiste routeringsalgoritme, dat opnieuw informatie verzamelt en het pakket naar de applicatie stuurt. Hierop bestaan een aantal uitzonderingen. Een deel van de pakketten zijn bedoeld om verder te sturen naar een andere, onafhankelijke netwerkknoop, deze worden dan ook verder gerouteerd. Een tweede uitzondering zijn pakketten die rechtstreeks van een server afkomstig zijn. Deze worden meteen doorgestuurd naar de applicatie. Als laatste uitzondering zijn er de pakketten die puur voor monitoring zijn. Deze worden doorgegeven aan de monitoringalgoritmes. Bij het versturen van data gaan pakketten van de applicatie via een proxy naar een routeringsalgoritme. Dat algoritme bepaalt dan een pad door het overlaynetwerk, dat dan de pakketten uitstuurt naar een andere knoop in het netwerk. Zowel voor routering als voor een overlay en de analysecomponent werden een aantal algoritmes uitgekozen en ge¨ımplementeerd. Deze overlopen we in Hoofdstuk 4. In Hoofdstuk 5 wordt vervolgens het ge¨ımplementeerde deel van de theoretische architectuur besproken.
Hoofdstuk 4
Algoritmes In dit hoofdstuk wordt dieper ingegaan op de verschillende algoritmes die gebruikt zijn bij de implementatie van de thesisarchitectuur. Een eerste onderdeel gaat in op het routeringsgedeelte van de architectuur, waarbij zowel een overlay als een aantal routeringsalgoritmes bekeken worden. Vervolgens wordt ook het gebruikte monitoringsalgoritme bestudeerd. De laatste sectie van dit hoofdstuk behandelt de analysecomponent en het maken van beslissingen over de routering.
4.1 4.1.1
Routeringscomponent Overlaynetwerk
Als overlaynetwerk werd gekozen voor het bestaande CYCLON [22] netwerk. Deze keuze ging enerzijds uit vanwege de beperkte overhead die door dit netwerk geproduceerd wordt, en anderzijds vanwege de mogelijkheid om snel te herstellen van mogelijke netwerkproblemen. Het netwerkprotocol van CYCLON bevat twee belangrijke onderdelen: uitwisseling van knopen en introduceren van nieuwe knopen. Elke knoop in het CYCLON netwerk houdt een lijst bij van andere gekende knopen. Deze knopenlijst is gerangschikt van oud naar nieuw, volgens het tijdstip van het laatst gekende contact. Op geregelde tijdstippen voert elke knoop P een zogenaamde ’enhanced shuffle’ uit (zie Figuur 4.1), die uit de volgende stappen bestaat:
1. De oudste knoop Q in de knopenlijst wordt uitgekozen als doelknoop. 2. Knoop P stelt een deellijst op met maximaal K willekeurige knopen uit de knopenlijst. 3. Knoop Q wordt verwijderd uit de knopenlijst, en de deellijst wordt verstuurd naar Q. 22
Figuur 4.1: Knopen P en Q wisselen gekende knopen uit. De pijlen tonen welke knopen gekend zijn door P en Q. Merk op dat de richtingspijl tussen P en Q gewisseld wordt.
4. Knoop Q ontvangt de deellijst en voegt de knopen toe aan haar eigen knopenlijst. Vervolgens stuurt knoop Q zelf een deellijst naar P terug. 5. Knoop P voegt de ontvangen knopen toe aan de knopenlijst. Als de knopenlijst vol zit, worden de oudste elementen verwijderd uit de lijst om plaats te maken.
Nieuwe knopen kunnen op verschillende manieren ge¨ıntroduceerd worden in het CYCLON netwerk. Een eerste basisstap is het zoeken van een introductieknoop. Dit kan bijvoorbeeld gebeuren door een aantal ’introductieknopen’ mee te geven in de code van het algoritme, of door broadcastberichten te versturen in het netwerk. In Spyros Voulgaris et al. [22] waarin het netwerk omschreven wordt, wordt deze eerste introductiestap niet beschreven. De volgende stap is het communiceren met deze introductieknoop. Er wordt gebruik gemaakt van een ’willekeurige wandeling’. Hierbij stapt men door het netwerk tot men bij een willekeurige knoop arriveert, en voegt men deze knoop toe aan de knopenlijst. In de implementatie voor de scriptie zijn een aantal andere keuzes gemaakt. Het oorspronkelijke algoritme levert namelijk vrij veel overhead toe bij het toevoegen van de nieuwe knopen. Daarnaast proberen we te vermijden dat het netwerk disjunct wordt, door enkele extra technieken voor betrouwbaarheid toe te voegen. Door het netwerk stappen voor het toevoegen van een nieuwe knoop, levert redelijk wat netwerkoverhead op. Daarom is er voor gekozen een andere methode te gebruiken. De nieuwe knoop voert in deze andere methode ook een shuffle uit met de introductieknoop, en ontvangt zo een nieuwe lijst met buren. Deze methode heeft het nadeel dat de nieuwe knoop niet meteen verbonden is met willekeurige knopen in het netwerk. De nieuwe knoop zal echter ook op regelmatige tijdstippen een ’enhanced shuffle’ uitvoeren, waardoor het netwerk snel weer gebalanceerd raakt. Bij grote netwerken met duizenden knopen zijn hier
echter meer iteraties voor nodig. Het netwerk zou dus ongebalanceerd kunnen raken als veel knopen gebruik maken van dezelfde introductieknoop. In dat geval levert het gebruik van een ’willekeurige wandeling’ dus een voordeel op voor het netwerk. Het netwerk bestaat uit een aantal knopen die verbonden zijn via onbetrouwbare connecties. Daarom worden nog een aantal bijkomende maatregelen genomen om de betrouwbaarheid van het netwerk te verhogen. Als eerste maatregel wordt een minimaal aantal knopen bijgehouden. Als de knopenlijst te klein is, verwijderen we geen knopen bij het uitvoeren van de ’enhanced shuffle’. Dit vermijdt dat bij veel pakketverlies het aantal buren steeds vermindert, tot het netwerk opbreekt in disjuncte stukken. Een tweede maatregel die we nemen vanwege dezelfde reden, is het behouden van de knopenlijst van Q in de tweede stap van de shuffle. Deze maatregel zorgt er ook voor dat het aantal knopen voldoende hoog blijft.
4.1.2
Routering
Naast directe routering werden nog twee bijkomende routeringsalgoritmes gekozen om voldoende routeringskeuzes mogelijk te maken. One-hop Source routing [5] stuurt alle pakketten via een extra tussenliggende knoop om problemen te omzeilen. N Hop Routing, een zelf ge¨ımplementeerd algoritme, laat ook meerdere tussenliggende knopen toe.
One-hop Source routing One-hop Source routing [5] is een zeer eenvoudige methode om netwerkproblemen te omzeilen. De basis van het systeem is dat netwerkproblemen vaak slechts lokaal optreden. Slechts een deel van het netwerk ondervindt dus beperkingen op vlak van connectiviteit. Als we ons verkeer kunnen omleiden via een andere knoop, vermijden we mogelijk de netwerkproblemen, met als resultaat een betere verbinding. In Figuur 4.2 wordt dit concept getoond. Het algoritme om een goede route te bepalen is zeer eenvoudig. Als gevraagd wordt om een verbinding naar een bepaalde bestemming, worden een aantal overlayknopen uitgekozen, en worden testpakketten naar elk van de overlayknopen gestuurd. Vervolgens wordt gekeken naar het aantal pakketten dat teruggestuurd wordt en naar hoe lang dit terugsturen duurt. Op basis van deze kwaliteitsgegevens wordt een knoop uitgekozen. Als vervolgens pakketten via het algoritme verstuurd worden, worden ze ge¨encapsuleerd in een overlaypakket dat ze verder stuurt via de tussenliggende knoop. Die verwijdert de extra overlaygegevens en stuurt het pakket via IP-routering naar het uiteindelijke doel.
Figuur 4.2: De bron (src) slaagt er niet in een rechtstreekse verbinding op te zetten met het doel (dst). Routeren via een tussenliggende knoop (hop1) is wel mogelijk.
N Hop Routing N Hop Routing is een zelf ontwikkelde uitbreiding van One-hop Source routing. Het biedt de mogelijkheid om te routeren via meerdere tussenliggende knopen. Dit laat toe complexere paden te gebruiken om mogelijke problemen te omzeilen. Als een pakket met een onbekend (bron,doel)-paar arriveert, worden een aantal stappen uitgevoerd om een goede route te bepalen. 1. Het N Hop Routing-algoritme vraagt knopen aan het overlaynetwerk. 2. Het N Hop Routing-algoritme stuurt naar elk van de opgevraagde knopen een vast aantal ’PING’-pakketten. Dit zijn geen ICMP-pings, maar pakketten op overlayniveau. Ze zijn dus ge¨encapsuleerd in een IP-pakket. 3. Elk van de knopen stuurt de ’PING’-pakketten verder naar andere knopen, met zijn eigen adres toegevoegd. Elk van de knopen probeert de pakketten ook via directe routering verder te sturen naar het doel. 4. Als de limiet van het aantal tussenliggende knopen bereikt is, stuurt de laatste knoop een ’PONG’-pakket terug, met het tijdstip van ontvangst toegevoegd aan het pakket. Het pakket gaat via alle tussenliggende knopen terug naar de oorspronkelijke zender. 5. De oorspronkelijke zender kiest de beste combinatie van tussenliggende knopen uit (op basis van het aantal pakketten dat terug wordt gestuurd en de tijd om een pakket via een bepaald pad te sturen). 6. De zender stuurt een ’SET’-bericht naar de eerste tussenliggende knoop, die de routering instelt en het pakket verder stuurt. 7. Als het ’SET’-bericht bij de laatste knoop komt, wordt een ’HAVE SET’ teruggestuurd. 8. Als de ’HAVE SET’ niet binnen een bepaalde tijd arriveert, wordt een nieuwe ’SET’ gestuurd.
Figuur 4.3: De bron (src) slaagt er niet in een rechtstreekse verbinding op te zetten met het doel (dst). Routeren via een aantal tussenliggende knopen is wel mogelijk.
Latere pakketten worden langs deze opgegeven route gestuurd. De keuze van een optimale route wordt weergegeven in Figuur 4.3, waar een aantal paden wegens netwerkproblemen niet functioneel zijn.
4.2
Monitoring
Om de kwaliteit van routering correct te kunnen inschatten, is het noodzakelijk controlemechanismen toe te voegen. We kunnen dan ook een aantal algoritmes uitwerken voor monitoring. Pakketverlies kan actief opgemeten worden door pakketten te injecteren en te controleren hoeveel van deze pakketten arriveren. Het nadeel hierbij is dat deze methode bijkomende netwerkoverhead oplevert. Er zijn dan ook een aantal passieve algoritmes ontwikkeld om pakketverlies op te meten, vooral voor het Transmission Control Protocol.[23]. Deze algoritmes controleren hiervoor wanneer pakketten met bepaalde volgnummers arriveren. Als een pakket later dan verwacht arriveert, is mogelijk sprake van pakketverlies. In het kader van de scriptie werd een gelijkaardig algoritme ontwikkeld, aangepast voor algemene IPcommunicatie. In dit geval moet geen rekening gehouden worden met vertragingstijden, enkel met volgnummers. Pakketverlies kan bij de ontvanger volledig passief opgemeten worden. Daarna moeten de bekomen gegevens wel teruggestuurd worden naar de zender van de pakketten. Het verzamelen van gegevens omtrent pakketverlies vereist dus een actieve stap. Het opmeten van dit pakketverlies vereist het bekomen van de correcte volgorde van de verstuurde pakketten. Hiervoor bestaande verschillende mogelijkheden: • IP-pakketten bevatten een identificatieveld. Dit veld kan op 0 gelaten worden, maar
Figuur 4.4: Opeenvolgende pakketten arriveren bij een router. Het pakketverlies wordt berekend aan de hand van de middelste pakketten.
het kan ook gebruikt worden om sequentienummers in op te slaan. • Men kan op een hogere protocollaag kijken en bijvoorbeeld bij het Real-Time Protocol (RTP) een volgnummer bepalen. In het algemeen kan men, als volgnummers beschikbaar zijn, pakketverlies bepalen met volgende methode (zoals ook weergegeven in Figuur 4.4): 1. Men houdt de meest recent geziene N volgnummers bij (vb. 100-200 volgnummers). 2. Een bufferlengte B (vb. 20-50) wordt gekozen, zodat men de middelste N − 2B pakketten kan bekijken. Deze bufferlengte wordt gebruikt om, als men controleert welke pakketten verloren gegaan zijn, enkel echt pakketverlies te bekijken. Door een buffer in te bouwen vermijdt men pakketten mee te rekenen die een hogere vertragingstijd hebben, maar toch nog arriveren op hun bestemming. 3. Het hoogste en laagste volgnummer Vmax en Vmin van de middelste N − 2B pakketten wordt gezocht door ze te overlopen. 4. Alle N pakketten worden overlopen en een teller T houdt bij hoeveel gevonden pakketten een volgnummer tussen Vmin en Vmax hebben. Het aantal verloren gegane pakketten is N − 2B − T . De volledige monitoring gaat dus als volgt. Bij de zender wordt genoteerd waar de data naar verstuurd wordt en waar de data vandaan komt. Bij de ontvanger wordt bijgehouden wat het pakketverlies is voor een bepaalde zender en ontvanger. De zender laat weten aan de ontvanger dat pakketverliesinfo voor een (zender, ontvanger)-paar doorgestuurd moet worden. Op regelmatige tijdstippen (bijvoorbeeld elke 5 of 10 seconden) stuurt de ontvanger de informatie over het pakketverlies door naar de zender.
4.3 4.3.1
Analysecomponent Algemene beslissingen
Op basis van gegevens van monitoringalgoritmes nemen we beslissingen over de beste routeringsalgoritmes op een welbepaald moment. Om een dergelijke systeem eenvoudig implementeerbaar en aanpasbaar te maken, kunnen we hiervoor gebruik maken van een regelgebaseerd systeem. Dit laat toe regels te defini¨eren zoals hieronder weergegeven in pseudocode. rule "Check recent packet loss" salience 10 when routing_type : (type) total_packetloss : sum( packetloss_measurement : (source, destination, type), range: (20,seconds) ) total_packetloss > 20 then routing_type.change_routing() end Deze regel controleert het pakketverlies in de laatste 20 seconden en verandert de routering als deze een bepaalde waarde overschrijdt. Een combinatie van dergelijke regels laat toe de nodige beslissingen te nemen over routering. De parameter ’salience’ geeft aan hoe belangrijk de regel is. Belangrijkere regels krijgen voorrang bij uitvoering. Het wijzigen van de routering zelf, kan ook in regels gegoten worden. Bovenstaande regel is slechts een voorbeeld. Een aantal regels die gebruikt worden in de implementatie, zijn te vinden in Sectie 5.2.2.
4.3.2
Beperken van overhead
Het maken van beslissingen voor elke mogelijke netwerkstroom kan heel wat overhead met zich meebrengen. Er zijn een aantal punten waar we op moeten letten. • De netwerkoverhead voor het bepalen van optimale routes per stroom. Bij N Hop Routing vereist dit bijvoorbeeld het uitsturen van een aantal pakketten om mogelijke routes te controleren. • Het bepalen van pakketverlies zorgt ook voor een hoeveelheid overhead. Enerzijds is er het versturen van pakketten met informatie over pakketverlies. Anderzijds is er het
controleren van elk pakket om het volgnummer te bepalen, en het bijhouden van een hoeveelheid van deze volgnummers. • Het uitvoeren van de regels van het regelgebaseerd systeem om te bepalen of een route wel goede resultaten oplevert, veroorzaak ook overhead. Een aantal berekeningen moeten hiervoor uitgevoerd worden. Twee algoritmes worden gebruikt om de overhead beperkt te houden. Enerzijds wordt gebruik gemaakt van aggregatie. Als een aantal netwerkelementen via dezelfde overlayknoop pakketten versturen naar een bepaalde bestemming, kan een goede route bepaald worden met behulp van slechts 1 routebepaling. Een eerste stap bij het bepalen van deze goede route is eenvoudigweg het ophalen van de juiste groep van een bronadres, zoals weergegeven in onderstaande pseudocode. Het opvragen zorgt voor wat extra werk, maar dit kan beperkt worden. Als de groepen in een hashtabel worden opgeslaan, gaat het hierbij over een operatie met complexiteit O(1).
uint32_t source = p->source; uint32_t destination = p->destination; //Zoek op tot welke groep het bronadres behoort. uint32_t group = get_group(source); //Indien nog geen groep toegewezen is: wijs een groep toe. if(!group) { group = create_new_group(src); }
Vervolgens kunnen we op basis van de gekozen groep bepalen waar het pakket naartoe gestuurd moet worden. Als deze gegevens al beschikbaar zijn, kunnen we deze ook uit een bestaande datastructuur ophalen. Dit zal onder andere het geval zijn als een andere netwerkknoop uit dezelfde groep al een verbinding heeft opgezet. De routebepaling moet dus slechts voor een van de netwerkknopen uitgevoerd worden, wat bandbreedte bespaart. uint32_t next_hop = 0; //Zoek op wat de routering is voor deze groep, //dus wat de volgende knoop in de overlay is. next_hop = get_next_hop(group, destination); if(next_hop) { //Stuur het pakket via de overlay, //dus via de tussenliggende knoop next_hop send_packet_overlay(p, next_hop); return;
} else { //Bepaal de tussenliggende knoop determine_next_hop(source, group, next_hop); send_packet_direct(p); } Een mogelijk probleem bij het vormen van dergelijke netwerkgroepen is het aggregeren van te veel netwerkelementen. Als een aantal zware netwerkstromen langs hetzelfde pad gestuurd worden, kan dit er bijvoorbeeld voor zorgen dat het gekozen netwerkpad overbelast raakt. Dit kan niet noodzakelijk opgelost worden door een nieuw pad te kiezen, omdat de bandbreedte bijzonder hoog blijft. Het is dus noodzakelijk om bij het regelgebaseerd systeem regels toe te voegen om de groepen op te splitsen bij netwerkproblemen. Aggregatie kan ook ge¨ımplementeerd worden door op de ontvanger te concentreren. In de implementatie wordt gerouteerd naar de ontvanger langs een aantal overlayknopen. Aggregatie zou uitgevoerd kunnen worden door bepaalde ontvangers te groeperen. Vervolgens kan men een gedeeltelijk pad bepalen dat gemeenschappelijk is. Aan het eind van dit pad kan dan ofwel een overlayroute voor de aparte ontvangers bepaald worden, ofwel rechtstreeks gerouteerd worden. Het probleem van aggregatie bij ontvangers is complex. Men moet namelijk ontvangers groeperen, zonder dat een fysieke topologie beschikbaar is. Hierdoor kunnen suboptimale keuzes gemaakt worden. Een andere manier om netwerkoverhead te beperken is door de routeringsalgoritmes bepaalde grenzen op te leggen. Bij N Hop Routing worden ’PING’-pakketten uitgestuurd, die na elke link opnieuw verstuurd worden naar een aantal netwerkknopen. Dit gebeurt tot een maximum aantal stappen is bereikt. Als de maximale diepte (het maximaal aantal stappen) N is, en de maximale breedte (de opsplitsingsgraad) B is, kunnen we de complexiteit van de overhead berekenen. Een eerste deel van de netwerkoverhead wordt geleverd door een constante factor bij de ’PING’-pakketten. Elk pakket bevat een overlayheader van K byte. Bij elke link die bereikt wordt, wordt het aantal pakketten met B vermenigvuldigd. We krijgen dus een overhead van K + BK + B 2 K + B 3 K + ... + B N K of K(1 + B + B 2 + B 3 + ... + B N ). De complexiteit is dus O(B N ). Het tweede deel van de netwerkoverhead wordt veroorzaakt door de niet-constante factor bij de pakketten. Elk pakket moet bijhouden welke knopen het gepasseerd is, om de route te herconstrueren als deze optimaal blijkt. Dit veroorzaakt dus een overhead van K + 2BK + 3B 2 K +4B 3 K +...+(N +1)B N K of K(1+2B +3B 2 +4B 3 +...+(N +1)B N ). De complexiteit is dus O(N B N ).
Met behulp van policies kunnen we opleggen dat de netwerkoverhead beperkt wordt. Hierdoor kan de beslissing genomen worden dat routeringsalgoritmes beperkingen opgelegd krijgen bij het zoeken naar andere routes; Bij N Hop Routing resulteert dit bijvoorbeeld in het verlagen van de factoren N en B.
Hoofdstuk 5
Implementatie De implementatie van de netwerkgedeeltes werd uitgevoerd met behulp van Click. Eerst zal een overzicht van de Click implementatie overlopen worden. Een volgende sectie bespreekt de verschillende netwerkalgoritmes die binnen Click ge¨ımplementeerd zijn. Vervolgens wordt gekeken naar de logische laag, waarvoor gebruik is gemaakt van het regelgebaseerd systeem Drools1 . Tot slot volgen nog enkele regels die gebruikt zijn in de implementatie.
5.1 5.1.1
Routeringscomponent Click Modular Router
Voor het implementeren van de netwerklaag werd gekeken naar het Click Modular Router project. Click is een softwarearchitectuur bovenop Linux die aan de hand van modules de mogelijkheid biedt netwerkpakketten op te vangen. Deze pakketten kunnen vervolgens gewijzigd worden en doorgestuurd naar het gewenste doel. Click bevat zelf al een groot aantal netwerkelementen, om onder andere scheduling, ARPfunctionaliteit en IP-routering mogelijk te maken. In Figuur 5.1 wordt een vereenvoudigd overzicht van de gebruikte structuur getoond die in Click ge¨ımplementeerd werd. Dit correspondeert met de netwerklaag binnen de architectuur, gecombineerd met een IP router.
5.1.2
Pad doorheen de router
We kunnen, ter verduidelijking van Figuur 5.1 het pad van een pakket door de router volgen. We nemen hier aan dat het om een gewoon datapakket gaat, en dus het pad volgt dat 1
http://www.jboss.org/drools/
32
Figuur 5.1: Ontwerp router in Click
de meeste pakketten volgen door de router. Het datapakket komt binnen in de router via een van de netwerkinterfaces. Het doeladres op ethernetniveau bepaalt of het pakket afgehandeld moet worden door deze router. Vervolgens wordt het pakket doorgestuurd volgens het exacte type op ethernetniveau. ARPpakketten worden apart afgehandeld. Het datapakket is een IP-pakket en ondergaat een aantal stappen om de nodige gegevens te bepalen. De ethernetheader wordt verwijderd en de IP-header wordt gecontroleerd. Dit zorgt er ook voor dat een aantal datastructuren aangemaakt worden om het verwerken eenvoudiger te maken. Daarna wordt het pakket doorgestuurd naar de juiste Click elementen, bepaald door het te classificeren onder de juiste categorie. Er zijn drie belangrijke categori¨een van pakketten. Enerzijds zijn er de pakketten van interne gebruikers. Deze interne gebruikers vallen onder de verantwoordelijkheid van de Click router. Dit kunnen bijvoorbeeld de klanten zijn van de netwerkoperator die de Click router beheert. De pakketten van deze gebruikers worden eerst langs het pakketverlieselement gestuurd om de bron- en doeladressen te noteren. Op deze manier kan afgeleid worden van welke verbindingen de hoeveelheid pakketverlies opgevolgd moet worden. Vervolgens wordt een routeringstype bepaald voor de pakketten. Bij directe routering kan meteen opgezocht worden waar het pakket naartoe gestuurd moet worden. Bij andere routering wordt aan het pakket de nodige routeringsinformatie toegevoegd, waarna het ge¨encapsuleerd wordt in een overlaypakket. Daarna wordt ook opgezocht waar het pakket naartoe gestuurd moet worden. Als tweede groep zijn er de pakketten afkomstig van externe gebruikers met als doel een interne gebruiker. Bij deze pakketten wordt de omgekeerde weg gevolgd. Eerst wordt de encapsulatie in het overlaypakket verwijderd, om vervolgens de routeringsinformatie te verwijderen. Hierdoor wordt een normaal datapakket bekomen, dat naar de pakketverliescontrole gestuurd wordt. Bij deze pakketverliescontrole wordt het volgnummer van het pakket bijgehouden, om indien nodig voor andere routers de hoeveelheid pakketverlies te bepalen. Daarna wordt ook voor dit pakket opgezocht waar het precies naartoe gestuurd
moet worden. Voor de pakketten van externe naar interne gebruikers bestaat nog een alternatief pad. Als het pakket niet ge¨encapsuleerd is, kan het rechtstreeks naar de pakketverliescontrole. Ten derde zijn er de pakketten van externe gebruikers die ook voor externe gebruikers bedoeld zijn. Dit betreft onder andere de pakketten die onze router als tussenstation bij de overlayroutering gebruiken. Hierbij wordt de overlayencapsulatie verwijderd. Het routeringsalgoritme gebruikt dan de toegevoegde routeringinformatie om het pakket verder te sturen. In dit geval wordt het pakket daarna weer ge¨encapsuleerd door het overlaysysteem. Hieronder worden ook de pakketten gerekend waarvoor de Click router puur als IP router gebruikt wordt. Deze functionaliteit wordt ook door gewone routers geleverd. In dit geval wordt het pakket na classificatie meteen doorgestuurd naar de IP opzoeking en naar een andere router gezonden. Pakketten die bedoeld zijn voor de machine waar de Click router op ge¨ınstalleerd is, worden rechtstreeks doorgestuurd. Dit rechtstreeks doorsturen wordt niet op de figuur weergegeven. Het opzoeken van het doeladres gebeurt via een routeringstabel, zoals bij gewone IP routers. Tot slot worden zowel ARP- als IP-pakketten verstuurd via de verschillende netwerkinterfaces. Om de mogelijkheid te bieden de netwerkimplementatie te testen, worden bij deze stap pakketverlies en vertragingstijd gesimuleerd. Een aantal standaard Click elementen (RandomSample en DelayUnqueue) laten toe een bepaalde hoeveelheid pakketverlies of vertragingstijd in te stellen. Naast gewone datapakketten zijn er ook nog een aantal controlepakketten die verstuurd worden. Deze volgen dezelfde paden doorheen de router als datapakketten. Het verschil is dat ze aangemaakt worden en verwijderd worden in de loop van het pad. Zo worden controlepakketten voor routering bij het routeringselement aangemaakt en verwijderd. Hoe de verschillende elementen in detail functioneren, wordt besproken in Sectie 5.1.3.
5.1.3
Ge¨ımplementeerde Clickelementen
Om de nodige functionaliteit te bieden die in de architectuur besproken werd, zijn een aantal elementen voor deze thesis ge¨ımplementeerd. Hierbij was het ook noodzakelijk om externe communicatie mogelijk te maken. Daarom hebben een aantal elementen afhandelmethodes, bijvoorbeeld om de hoeveelheid pakketverlies te bekomen of om een ander routeringsalgoritme te selecteren.
Figuur 5.2: Pakketten arriveren via 3 verschillende ingangen. Pakketten van een interne of externe bron worden apart behandeld, evenals pakketten van andere PacketLossCheckerelementen.
PacketLossChecker De PacketLossChecker voert de monitoring uit. Deze meet dus het aantal pakketten dat verloren gaat op een bepaalde verbinding. Daarnaast vraagt het element ook pakketverlies op aan andere netwerkknopen. Als pakketten arriveren van een externe bron en bedoeld zijn voor PC’s die onder de verantwoordelijkheid van de router vallen, wordt van deze arriverende pakketten het pakketverlies bijgehouden. Dit kan volledig passief gebeuren, er moeten geen bijkomende pakketten verstuurd worden om de gegevens te verzamelen. Hiervoor worden de identificatienummers van de meest recente IP-pakketten bijgehouden. We houden hiervoor 150 identificatienummers bij. We kunnen enkel de middelste identificatienummers gebruiken om het pakketverlies te bepalen. In het begin en einde van de reeks kunnen namelijk identificatienummers ontbreken door een vari¨erende vertragingstijd. Als we bij deze reeks de eerste 13 en de laatste 13 weglaten om fouten door vertragingstijd te vermijden, behouden we nog 50 pakketten. We kunnen dus met een precisie van 2% het pakketverlies bepalen. Netwerkelementen onder verantwoordelijkheid van de router kunnen zelf ook pakketten sturen naar de rest van het netwerk. Als dit gebeurt, voert de PacketLossChecker een actieve rol uit. Dan willen we namelijk weten hoeveel van de pakketten werkelijk op de bestemming raken. Hiervoor sturen we periodiek een verzoek om pakketverliesinformatie naar de router die verantwoordelijk is voor het doel van de pakketten. Deze zal dan het pakketverlies berekenen en terugsturen naar de oorspronkelijke router. De pakketverliesinformatie kan dan ook lokaal opgevraagd worden (door de logische laag), omdat de pakketverliescontrole ook een afhandelmethode bevat die deze informatie doorgeeft. Bij het aanroepen van deze handler geeft de PacketLossChecker door welke pakketverliesinformatie deze zelf opgevraagd heeft van andere knopen. De verschillende taken van de PacketLossChecker zijn ook duidelijk zichtbaar op Figuur 5.2. Daarop wordt een diagram met de verschillende in- en outputs weergegeven. Pakketten die afkomstig zijn van externe netwerkelementen (netwerkelementen waar de router niet voor verantwoordelijk is), worden gebruikt om pakketverlies op te meten. Dit gebeurt aan de
(a) Een algemeen CYCLON pakket.
(b) Een REQUEST-pakket bevat een knopenlijst en een maximum aantal om zelf te ontvangen.
(c) Een RESPONSE-pakket bevat een knopenlijst.
(d) Een datapakket bevat enkel data.
Figuur 5.3: Er zijn 3 pakkettypes ge¨ımplementeerd bij de CYCLON overlay.
hand van de identificatienummers. Bij pakketten van interne netwerkelementen wordt enkel gecontroleerd of we al pakketverliesinformatie over de verbinding ontvangen. Infopakketten tot slot laten ons toe gegevens te ontvangen van andere PacketLossCheckerelementen.
CyclonOverlay Het CYCLON algoritme is heel eenvoudig. Elke netwerkknoop houdt een lijst bij van andere netwerkknopen. Op geregelde tijdstippen wisselt elke knoop informatie uit met de anderen met behulp van een ’enhanced shuffle’. Deze wordt in detail besproken in Sectie 4.1.1. De algemene structuur van een CYCLON pakket legt de eerste 2 bytes vast. De eerste byte is het overlay ID. Dit geeft aan dat het CYCLON overlaynetwerk gebruikt wordt. Door het gebruik van dit ID wordt het mogelijk om in latere implementaties meerdere overlaynetwerken te gebruiken. De tweede byte in de structuur geeft aan wat het type is van het overlaypakket. Het CYCLON algoritme definieert 3 verschillende types pakketten. Om een enhanced shuffle uit te voeren, werden 2 pakkettypes ge¨ımplementeerd, dit zijn een REQUEST-pakket en een RESPONSE-pakket. De structuur van deze pakketten wordt weergegeven in Figuur 5.3b en Figuur 5.3c. Beide types pakketten bevatten een lijst met andere knopen van het CYCLON netwerk, die ze doorgeven als deel van de enhanced shuffle. Het REQUEST-pakket bevat daarnaast ook nog 1 byte extra met de parameter MAX. Deze geeft het maximum aantal knopen aan dat de zender van het bericht wenst te ontvangen. Een derde pakkettype, het DATA-pakket, wordt gebruikt als encapsulatie van nuttige gegevens. Bij dit pakkettype wordt ook de standaard pakketstructuur van Figuur 5.3a gevolgd. Het overlay ID geeft aan dat het CYCLON netwerk gebruikt wordt, het type geeft aan wat voor pakkettype gebruikt wordt. In dit geval krijgen we als type DATA, en de rest van het
Figuur 5.4: Pakketten van een interne of een externe bron worden anders behandeld.
pakket wordt uitgemaakt door de nuttige gegevens. Alle CYCLON pakketten worden dan nog omvat door een IP-pakket, om te zorgen dat ze gerouteerd kunnen worden naar bepaalde bestemmingen. Deze IP-encapsulatie wordt ook uitgevoerd binnen het OverlayCyclon Click element. Er zijn twee mogelijke paden door het OverlayCyclon element, zoals weergegeven in Figuur 5.4. Pakketten van een element waar de Click router verantwoordelijk voor is (interne netwerkelementen) komen het OverlayCyclon element binnen via een van de routeringselementen. Deze stellen op voorhand in een extra datastructuur het doeladres voor het pakket in. Op deze manier kan dan binnen het OverlayCyclon element het juiste doeladres uitgekozen worden voor de IP-header. Pakketten afkomstig van een extern netwerkelement zullen altijd al ge¨encapsuleerd zijn. Als het een REQUEST-pakket betreft, zullen de knopen in dit pakket toegevoegd worden aan de knopenlijst en wordt een RESPONSE-pakket teruggestuurd naar de externe uitgang. Bij een RESPONSE-pakket, worden de knopen ook toegevoegd. Bij een DATA-pakket wordt de volledige encapsulatie verwijderd, en wordt het pakket doorgestuurd naar de interne ingang. Het is dan mogelijk dat het pakket bij een intern netwerkelement terechtkomt, of dat een routeringsalgoritme beslist het verder te sturen. In dit tweede geval zal het weer ge¨encapsuleerd worden in het OverlayCyclon element.
PakketFilter Het PakketFilter element wordt gebruikt om pakketten met een bepaalde bron en doel naar het juiste routeringselement te sturen. Het wordt gebruikt voor pakketten afkomstig van een intern netwerkelement. Als een pakket arriveert van een bron waarvoor de routering nog niet gekend is, wordt het pakket doorgestuurd op de standaarduitgang. Dit is in de implementatie directe routering. Het pakket zal echter ook langs het pakketverlieselement passeren. Dit element zal het pakketverlies rapporteren aan de logische laag. Op basis van de gegevens wordt in de logische laag een routering geselecteerd. Deze routering wordt in het PakketFilter ingesteld met een afhandelmethode. Pakketten waarvoor wel een routering bekend is, worden naar het geschikte routeringselement gestuurd.
Het PakketFilter kan dus op twee verschillende manieren werken. Als de logische laag niet functioneert en dus geen routeringsbeslissingen doorstuurt, zal het PakketFilter altijd voor directe routering kiezen. Bijgevolg zal het routeringssysteem een IP-router vormen. Als de logische laag wel functioneert, wordt mogelijk voor overlayroutering gekozen. Er is dus een gereduceerde functionaliteit en een standaardfunctionaliteit. Sowieso zullen pakketten altijd gerouteerd worden.
OneHopRouting One-hop Source routing wordt in de implementatie uitgewerkt in het OneHopRouting Click element. Als een pakket arriveert van een intern netwerkelement waarvoor nog geen routering ingesteld is, worden een aantal stappen uitgevoerd om een goede route te bepalen. Het netwerkelement vraagt eerst aan het CyclonOverlay element via een afhandelmethode om een aantal netwerkknopen. Naar elk van deze knopen worden telkens 20 PINGpakketten gestuurd, om de verbindingskwaliteit te controleren. Om dit versturen uit te voeren, wordt in een extra datastructuur het doeladres (telkens een van de knopen van het CYCLON netwerk) ingesteld. Vervolgens wordt het PING-pakket via de externe uitgang van het OneHopRouting element verder gestuurd. Het CyclonOverlay element zal dan een encapsulatie toevoegen. Als een PING-pakket arriveert bij een knoop, zal deze een PONGpakket terugsturen. Nadat alle PING-pakketten verstuurd zijn, wordt na een bepaalde tijd het aantal gearriveerde PONG-pakketten van elke knoop geteld. De voorkeur wordt gegeven aan de knoop waarvan het meest pakketten gearriveerd zijn. Bij een gelijk aantal gearriveerde pakketten, wordt uit de beste knopen een willekeurige knoop gekozen. Een alternatief hiervoor is het kiezen van de knoop op basis van vertragingstijden. Het risico hierbij is dat een nabijgelegen knoop uitgekozen wordt, die het netwerkprobleem niet goed genoeg kan omzeilen. De uitgekozen knoop wordt opgeslaan in een routeringstabel, en wordt vervolgens gebruikt voor pakketten met hetzelfde (bron, doel)-paar. Het oorspronkelijke pakket kan men niet bijhouden tot een goede tussenliggende knoop gevonden is. Dit zou een te grote vertragingstijd tot gevolg hebben. Dit pakket wordt dus via een willekeurige knoop verdergestuurd. Dezelfde actie wordt ook ondernomen voor pakketten die bij het OneHopRouting element arriveren terwijl de bepaling van de beste tussenliggende knoop nog bezig is. Als een OneHopRouting element een extern datapakket ontvangt, zal het dit pakket via IP-routering rechtstreeks naar de doelknoop sturen, zoals ook uitgelegd in Sectie 4.1.2.
NHopRouting Het zelf ontwikkelde N Hop Routing algoritme baseert zich op dezelfde principes als Onehop source routing, maar voegt extra complexiteit toe om een betere routeringskwaliteit te bieden. Als een pakket van een intern netwerkelement arriveert, wordt de volgende knoop gelezen uit de routeringstabel. Als voor het (bron,doel)-paar van het pakket nog geen routering bekend is, worden een aantal stappen gevolgd om een optimale route te bepalen. Eerst worden een aantal PING-pakketten verstuurd naar andere knopen in het netwerk. Aan de hand van de terugkerende PONG-pakketten, wordt een goede route bepaald. Vervolgens worden SET-pakketten gestuurd naar de tussenliggende knopen om de route in te stellen. Deze knopen sturen daarna een HAVESET-pakket terug om te laten weten dat het instellen gelukt is. Na het instellen van de routering, worden pakketten naar de eerstvolgende knoop gestuurd als DATA-pakket. We bekijken nu deze stappen in detail.
(a) Het PING-pakket houdt een knopenlijst bij en het tijdstip van verzenden.
(b) Het PONG-pakket houdt een knopenlijst, het tijdstip van verzenden en van ontvangst bij.
Figuur 5.5: De PING- en PONG-pakketten zijn vrij gelijkaardig, en houden timinginformatie en tussenliggende knopen bij.
Eerst wordt aan het CyclonOverlay element om netwerkknopen gevraagd. Voor elk van deze knopen wordt vervolgens een aantal PING-pakketten opgesteld. Bij deze implementatie wordt met 50 pakketten gewerkt. Om nauwkeuriger of minder nauwkeurig pakketverlies te detecteren, kan een ander aantal ook gebruikt worden. Deze pakketten worden in een wachtlijn geplaatst en 1 per 1 verstuurd. Wegens beperkingen van Click is het niet mogelijk deze PING-pakketten meteen allemaal naar het volgende Click element te sturen. Dit zou
ervoor zorgen dat een aantal pakketten verloren gaan. De structuur van een PING-pakket wordt weergegeven in Figuur 5.5a. Als het PING-pakket verstuurd wordt vanaf het eerste netwerkelement, staat er nog geen knopenlijst in het pakket. Deze wordt tijdens de beweging door het netwerk toegevoegd. Verder zijn ook de waarden B (breedte) en D (diepte) van belang. De breedte geeft aan naar hoeveel andere knopen een ontvangen PING-pakket verstuurd mag worden, de diepte geeft aan hoeveel knopen maximaal in een PING-pakket mogen. Eenmaal een PING-pakket de knoop bereikt die verantwoordelijk is voor het doeladres, wordt een PONG-pakket teruggestuurd. Dit pakket, weergegeven in Figuur 5.5b, bevat naast de knopenlijst en de andere gegevens van het PING-pakket ook het tijdstip waarop de laatste knoop bereikt werd. Op deze manier kan bepaald worden hoe lang het pakket onderweg is, en kan op basis hiervan een kortere route gekozen worden. Na het versturen van de PING-pakketten wordt een bepaalde periode gewacht op de binnenkomende PONG-pakketten. In deze implementatie is gekozen voor 4 seconden. Dit zou voldoende tijd moeten bieden om alle PONG-pakketten te ontvangen. Enkel routes met heel veel vertragingstijd zullen hierbij problemen ondervinden, maar deze routes zijn (door de vertragingstijd) toch niet optimaal. Eenmaal de vereiste wachttijd verstreken is, kan de beste route uitgekozen worden. Hiervoor wordt in eerste instantie gekeken welke route het meest PONG-pakketten oplevert. Daarnaast wordt normaal gezien ook met de vertragingstijd rekening gehouden. Wegens de beperkingen van Click die eerder in deze sectie vermeld werden, klopt de timing van de PONG-pakketten niet helemaal. Omwille van deze reden wordt in de implementatie geen rekening met de vertragingstijd. De route wordt vervolgens ingesteld door het sturen van SET-pakketten. Deze bevatten een volledige lijst van de tussenliggende knopen, zodat elke knoop weet waar de pakketten verdergestuurd moeten worden. Als de laatste knoop het SET-pakket ontvangt, wordt een HAVESET-pakket teruggestuurd. Dit zorgt ervoor dat de oorspronkelijke knoop weet dat de route volledig ingesteld is. De SET- en HAVESET-pakketten hebben dezelfde structuur, zoals weergegeven in Figuur 5.1.3. Zolang geen HAVESET-pakket ontvangen werd, verstuurt de eerste knoop elke seconde opnieuw een SET-pakket verstuurd. Eenmaal de route volledig ingesteld is, worden pakketten via deze weg verstuurd. Datapakketten zijn heel eenvoudig gestructureerd. Enkel het type routering en het type pakket (datapakket) moeten bijgehouden worden. Dit wordt getoond in Figuur 5.7b. Tijdens het instellen van de route, stuurt het NHopRouting element de pakketten verder via directe IP-routering. Een andere mogelijkheid zou zijn om een willekeurige netwerkknoop uit te kiezen en via deze te sturen. Als NHopRouting echter gebruikt wordt, wil dat zeggen dat de poging om One-hop Source routing te gebruiken niet gelukt is. Via een willekeurige netwerkknoop routeren zal dus waarschijnlijk ook niet lukken. De routering wordt behouden tot tijdens een bepaalde periode (vb. 10 tot 20 seconden) geen
(a) Het SET-pakket bevat een knopenlijst.
(b) Het HAVESET-pakket bevat een knopenlijst.
Figuur 5.6: SET-pakketten houden een lijst bij van tussenliggende knopen, om te weten welk pad ingesteld moet worden.
(a) Bij de algemene structuur liggen slechts 2 byte vast.
(b) Datapakketten geven geen bijkomende overhead in de structuur.
Figuur 5.7: De standaard structuur van een pakket is bijna volledig vrij (op de eerste 2 byte na).
pakketten verstuurd worden via het NHopRouting element. Dit kan zijn omdat geen communicatie meer gevoerd wordt, of omdat de routering niet aan de nodige kwaliteit voldoet. In dit geval wordt een ander routeringsalgoritme uitgekozen. Als NHopRouting daarna weer geselecteerd wordt, kan een ander (mogelijk beter) pad gezocht worden.
5.2
Logische component
De logische laag werd ge¨ımplementeerd in Java met behulp van het regelgebaseerd systeem Drools2 . Dit systeem biedt de mogelijkheid om in Java de nodige gegevens te verzamelen (met behulp van de afhandelmethodes van de verschillende Click elementen). Vervolgens kunnen met een aantal regels uit een tekstbestand of xmlconfiguratie beslissingen genomen worden over het kiezen van de routering. Deze beslissingen worden daarna opnieuw weggeschreven met behulp van de afhandelmethodes van de Click elementen. Het voordeel van deze implementatie is dat het zeer eenvoudig is om regels te wijzigen, zonder dat hiervoor code aangepast en gehercompileerd worden. De afhandelmethodes worden ook meegegeven in een JSON-configuratiebestand3 . Op deze manier moet de code enkel aangepast worden bij grote veranderingen in de Click router.
5.2.1
Regelgebaseerd systeem
Het inlezen van de instellingen van het regelgebaseerd systeem is de eerste stap die bij het opstarten uitgevoerd wordt. Deze instellingen bevatten onder andere de juiste locatie van de afhandelmethodes van de Click elementen. Daarnaast kunnen ook groepen gebruikers opgegeven worden om prioriteiten mee te geven. Op deze manier kan men bijvoorbeeld een groep opgeven als betalende klanten (hoge prioriteit) en een aantal niet-betalende klanten (lage prioriteit). Verder worden ook de verschillende routeringstypes ingesteld, aan de hand van de naam van hun Click element. Het regelgebaseerd systeem is dus onafhankelijk van de precieze implementatie van de routeringsalgoritmes. Tot slot bevatten de instellingen ook de juiste elementen om pakketverlies en (in theorie) andere kwaliteitskenmerken op te meten. Eenmaal de nodige instellingen geladen zijn, worden de regels ingelezen en de programmalus gestart. De eerste stap in het uitvoeren van de lus is het ophalen van kwaliteitskenmerken. Om effectieve regels te kunnen implementeren, moeten bij deze kwaliteitskenmerken een aantal gegevens bijgehouden worden: • Bron- en doeladres waarvoor de kwaliteit werd opgemeten. 2 3
http://www.jboss.org/drools/ http://www.json.org/
• Kwaliteitstype: dit kan gebruikt worden om bepaalde regels enkel van toepassing te maken op 1 kwaliteitskenmerk (bijvoorbeeld pakketverlies). • Kwaliteitswaarde: bij pakketverlies kan dit het percentage pakketverlies zijn, bij vertragingstijd het aantal milliseconden vertraging. Omdat de mogelijkheid wordt geboden om verschillende regels te gebruiken voor verschillende kwaliteitstypes, levert dit geen problemen op bij de evaluatie van kwaliteitskenmerken. • Routeringstype: dit geeft aan welk routeringsalgoritme gebruikt wordt. • Tijdstip: dit laat ons toe te redeneren over een bepaalde periode meetresultaten. De kwaliteitskenmerken worden vervolgens geladen in het regelgebaseerd systeem. Dit systeem voert daarna de verschillende regels uit. Het is de bedoeling dat deze een aantal routeringskeuzes genereren. De verschillende keuzes worden tot slot weggeschreven naar de afhandelmethodes van de verschillende Click elementen. Na ongeveer 5 seconden wordt de lus opnieuw uitgevoerd.
5.2.2
Voorbeelden van regels
Met een beperkt aantal regels kan al heel wat functionaliteit geboden worden. De volgende regel zorgt ervoor dat routeringsalgoritmes gewijzigd worden bij te veel pakketverlies. Voor een routeringskeuze voor een welbepaald doel- en bronadres en een bepaalde routering wordt het totale pakketverlies in de laatste 20 seconden bepaald. Als deze waarde te groot is, wordt overgeschakeld op een volgende routering. Een bijkomende voorwaarde is dat de routering niet veranderd mag zijn in de laatste 20 seconden. Op deze manier vermijden we dat algoritmes die een langere opstarttijd vereisen de kans niet krijgen om een goede route bepalen.
rule "Check packet loss in the last 20 seconds on each connection" when //$routing: het type routering //$lastUpdate: de laatste keer dat het type //van de routering gewijzigd werd. $rc : RoutingChoice($src : srcAddr, $dst : dstAddr, $routing : routing, $lastUpdate : lastUpdate); $packetloss_sum : Number() from accumulate( QualityUpdate( srcAddr == $src, dstAddr == $dst, measurementType == "PacketLossChecker", $quality : quality,
routingType == $routing) over window:time(20s), sum($quality)); eval($lastUpdate < (currentTime - 20000)); eval($packetloss_sum.doubleValue() > 20); then //Verander het type van de routering $rc.setPort($rc.getPort() + 1); //Informeer het regelgebaseerd systeem over de wijziging update($rc); end Enkele varianten op bovenstaande regel zijn mogelijk. Bij de testen van de routeringsalgoritmes wordt gekeken naar het minimale pakketverlies in de laatste 20 seconden. Als een van de pakketverlieswaarden 0 is, wordt de routering goedgekeurd. Een andere strategie om het volgende routeringsalgoritme te kiezen, zou ook mogelijk zijn. Zo zou gekozen kunnen worden voor het routeringsalgoritme dat in de totale routeringstijd het minst pakketverlies ondervond. Een volgende mogelijke regel is voor het vormen van groepen. Als twee bronadressen vaak naar dezelfde doeladressen pakketten versturen, kan het voordelig zijn de adressen te aggregeren. Op deze manier moet voor een bepaald doeladres slechts 1 keer een optimale route gezocht worden. We kunnen deze groepen vormen op basis van het percentage gelijkaardige doeladressen. Als dit percentage een bepaalde grens overschrijdt, vormen we een groep. rule "Try to merge groups" salience 35 when $a : Group(); $b : Group(); eval($a != $b); eval(Group.compareSimilarity($a, $b) > 50); then insert(Group.merge($a, $b)); retract($a); retract($b); end Om het vergelijken van de doeladressen tussen verschillende groepen eenvoudiger te maken, kunnen we verbindinginformatie opslaan in de groepen zelf. Dit vereist een regel die recente informatie toevoegt en gedateerde informatie verwijdert. rule "Update connection information for groups"
salience 40 when $number_of_updates : Number() from accumulate( QualityUpdate( srcAddr == $src, dstAddr == $dst) over window:time(60s), count($quality)); $qu : QualityUpdate($src : srcAddr, $dst : dstAddr); $group : Group(); eval($group.hasMember($src)); eval(!$group.wasUpdated($src, $dst)); then $group.updateConnection($src, $dst); $group.purgeConnections(); update($group); end
Regelgebaseerde systemen bieden duidelijk heel wat mogelijkheden om keuzes te maken over routeringsalgoritmes. Bovenstaande regels vormen een basissysteem, maar het is mogelijk om heel wat bijkomende regels toe te voegen. Op deze manier kunnen complexe beslissingen genomen worden.
Hoofdstuk 6
Testmethodiek en Resultaten Het is mogelijk om een groot deel van de ge¨ımplementeerde algoritmes uit te testen en te evalueren. Op deze manier kunnen we controleren op welke vlakken de implementatie voldoet aan bepaalde vereisten, en waar verbetering mogelijk is. We kunnen ook afleiden wat mogelijke problemen kunnen zijn binnen de opgestelde architectuur.
6.1
Opstelling
De verschillende testen werden uitgevoerd op de Virtual Wall, in de Zuiderpoort in Gent. De Virtual Wall is een van de installaties van Emulab, een netwerksimulator die toelaat honderden servers (knopen) aan elkaar te koppelen en op die manier allerlei topologi¨een op te bouwen. Hierbij kunnen ook pakketverlies en de vertragingstijd tussen verschillende knopen ingesteld worden. Deze mogelijkheden werden echter niet gebruikt, omdat dit extra knopen vereist en Click router ook toelaat pakketverlies en vertragingstijden te simuleren. De Click elementen die hiervoor gebruikt werden zijn respectievelijk RandomSample en DelayUnqueue. Het limiteren van de toegelaten bandbreedte is mogelijk met BandwidthRatedSplitter. De servers van de Virtual Wall hebben volgende kenmerken: • Processor: Dual-Core AMD Opteron(tm) Processor 2212, 2GHz • RAM-geheugen: 4 GB geheugen Op de gebruikte servers werden 2 verschillende installaties opgezet. De servers die ingesteld werden als Click router hebben volgende configuratie: • Besturingssysteem: Debian 4.0 GNU/Linux met kernel 2.6.19.2
46
• Wijzigingen: de kernel werd gepatcht met de patches voor kernel 2.6.19.2. Hiervoor werd uit het git-versiecontrolesysteem van Click router de versie van 10 februari 2010 gebruikt 1 . Een tweede installatie wordt gebruikt om gebruikers voor te stellen. Hiervoor wordt volgende configuratie gebruikt: • Besturingssysteem: Ubuntu 9.04 • Wijzigingen: VLC media player werd ge¨ınstalleerd. Dit programma laat toe om als server video te leveren en om als gebruiker video te ontvangen. In de experimenten wordt gebruik gemaakt van de 480p-versie van de video Big Buck Bunny. Deze video is beschikbaar onder de Creative Commons Attribution 3.0 licentie en online verkrijgbaar2 . Voor gebruik binnen de experimenten werd een conversie uitgevoerd naar mpeg2 met het openbronprogramma Mencoder3 . Een eerste versie van de video heeft een variabele bandbreedte (Variable BitRate of VBR). De gemiddelde bitrate is ongeveer 3600 Kbps. Een tweede versie werd met een constante bandbreedte (Constant BitRate of CBR) ge¨encodeerd. Hiervoor werd de encodering uitgevoerd aan een bitrate van 2500 Kbps.
6.2
Gecombineerde routerings- en snelheidstest
Als algemene routeringstest wordt bij een klein netwerk gecontroleerd of het overschakelen naar een correct routeringsalgoritme betrouwbaar werkt. Daarnaast wordt ook gecontroleerd hoe snel deze overschakeling gebeurt. Dit soort testen kan uitgevoerd worden op een klein netwerk. Het is echter belangrijk dat dit netwerk toch complex genoeg is om de kenmerken van de verschillende algoritmes te kunnen testen. In Figuur 6.1 wordt de structuur weergegeven van het netwerk dat gebruik werd voor het uitvoeren van deze testen. Client0 en client1 zijn twee gebruikers van het netwerk, dat opgebouwd is uit verschillende Click routers. In een re¨ele situatie bevinden zich tussen deze Click routers nog heel wat IP-routers. We kunnen het netwerk echter puur met Click routers simuleren door IP-routering toe te voegen met een aantal Click elementen. De ingestelde routering voor 1 van deze routers (click0) wordt weergegeven in Tabel 6.1 als voorbeeld. De volledige routeringstabel is te vinden op de bijgevoegde CD-ROM. De vertragingstijd tussen de verschillende routers is in dit geval bij rechtstreekse verbindingen telkens ingesteld als 20 ms. 1
Verdere info omtrent het verkrijgen van de broncode is beschikbaar op de website: http://read.cs.ucla.edu/click/git 2 De website is http://www.bigbuckbunny.org. 3 Mencoder wordt ontwikkeld binnen het Mplayerproject en is te verkrijgen op http://www.mplayerhq.hu
Figuur 6.1: Het netwerk bestaat uit 2 gebruikers en 7 overlayrouters.
Router
Doel
Routering via
click0 click0 click0 click0 click0 click0 click0 click0 click0
click1-click6 click2-click3 click2-click4 click3-click4 click3-click5 click4-click5 click4-click6 click5-click6 click6-client1
click1 click2 click2 click2 click2 click2 click2 click2 click1
Tabel 6.1: De routeringstabel voor click0 geeft de knoop waar langs gerouteerd wordt om een bepaald subnet te bereiken.
In dit experiment bekijken we wat het effect is van problematische verbindingen op de routering. We beschouwen een netwerkverbinding als gestabiliseerd en functioneel als deze bij de laatste 7 metingen geen pakketverlies ondervindt. Het beginpunt van deze 7 metingen wordt dan beschouwd als het punt waarop de routering correct begon te functioneren.
6.2.1
Netwerk met een slecht functionerende verbinding
We bekijken eerst het geval van een enkel netwerkprobleem dat de kwaliteit van een verbinding vermindert. De netwerkverbinding verliest in beide richtingen 5% van de verstuurde pakketten bij het passeren van router click1. De onderbroken verbinding wordt in Figuur 6.2 weergegeven. We bestuderen de snelheid waarmee een overlayroutering gevonden wordt die geen pakketverlies ondervindt. IP-routering van click0 naar click6 verloopt via click1. Overlayroutering is dus noodzakelijk. Hiervoor gebruiken we een gewijzigde versie van de routeringsregel in Sectie 4.3.2. Een routering wordt als acceptabel beschouwt als recent een periode geweest is zonder pakketverlies. We vari¨eren de lengte van deze periode van 5 tot 20 seconden met stappen van 5 seconden in de experimenten om een goede keuze af te leiden. Voor elke mogelijke periode
Figuur 6.2: 1 netwerkonderbreking kan makkelijk omzeild worden.
Figuur 6.3: Een netwerkonderbreking omzeilen gaat snel.
worden 10 metingen uitgevoerd. Bij een korte periode bestaat de mogelijkheid dat een complex routeringsalgoritme nog niet gestabiliseerd is, maar al afgekeurd wordt. Bij een lange periode is de kans op een trage overschakeling tussen routeringsalgoritmes een nadeel. Het analyseren van de opgemeten waarden toont duidelijk dat sneller een juiste routering gekozen wordt bij beoordelingsperiodes van slechts 5 seconden. In dit geval is de vereiste tijd om tot een juiste routeringskeuze te komen vrij laag. De meeste meetwaarden schommelen rond de 10 tot 15 seconden. Meerdere waarden vallen hier ook samen, op een enkele uitloper rond 20 seconden na. De meetwaarden bij langere beoordelingsperiodes liggen beduidend hoger, tot zelfs 60 seconden. Een periode van 20 seconden om te beoordelingen heeft tot gevolg dat sowieso pas na 20 seconden een routeringswijziging mogelijk is. De ondergrens voor de metingen zien we dan ook lineair stijgen.
Figuur 6.4: Meerdere netwerkonderbrekingen vereisen een geavanceerd routeringsalgoritme om te omzeilen.
6.2.2
Netwerk met een groot aantal slecht functionerende verbindingen
Het is ook mogelijk dat in een netwerk heel wat meer verbindingen falen. Dit kan bijvoorbeeld gebeuren omdat een belangrijke router verkeerde gegevens rondstuurt. In Figuur 6.4 wordt het netwerk weergegeven dat gebruikt wordt om een groot aantal falende verbindingen te testen. Een correcte routering is enkel mogelijk via de routers click2, click3 en click5. Bovendien is de routeringstabel van click2 ingesteld om click5 te bereiken via click4. De routeringstabel van click3 is ingesteld om via click4 naar click6 te routeren. De enige correcte routeringen vereisen dus sowieso click3 en click5 als tussenliggende knopen. Rechtstreekse IP-routering loopt via click1 en zal dus niet voldoen. One-hop Source routing kan ook niet voldoen, aangezien deze slechts 1 tussenliggende knoop kan selecteren. N Hop Routing kan het probleem wel omzeilen. Hiervoor moet het routeringsalgoritme een van de volgende twee routeringskeuzes selecteren in click1: • click2 - click3 - click5 • click3 - click5 Beide keuzes leveren exact hetzelfde fysieke pad op. De overlaytopologie is echter anders. Bij de tweede keuze functioneert click2 enkel als IP-router. Bij de analyse van de resultaten weergegeven in Figuur 6.5 zien we een grote verandering ten opzichte van het herstellen van 1 netwerkonderbreking. Vooral de performantie bij een beoordelingsperiode van 5 seconden verslechtert duidelijk. De maximale tijd om een correcte routering te vinden bij deze beoordelingsperiode verdubbelt zelfs. Bij grotere periodes is er veel minder verandering. De minimale tijd om het correcte routeringsalgoritme te bepalen, ligt wel hoger. Dit komt omdat in de implementatie eerst One-hop Source routing uitgeprobeerd wordt. De sterke stijging van de tijd voor het zoeken van een correct pad bij een beoordelingstijd van 5 seconden is niet geheel onverwacht. Enkel N Hop Routing kan het routeringsprobleem oplossen. Het duurt echter een aantal seconden voordat N Hop Routing een correct
Figuur 6.5: Een complexer probleem duurt langer om te omzeilen.
pad geselecteerd heeft. Met een beoordelingstijd van slechts 5 seconden kan dit ervoor zorgen dat overgeschakeld wordt naar het volgende algoritme. Hierdoor gaat heel wat tijd verloren. Als routeringsoverhead sterk ongewenst is, is de keuze voor een hogere beoordelingstijd dus voordelig.
6.3
Routeringsgedrag bij verzadigd netwerk
Overlayroutering zorgt voor een zekere overhead op vlak van bandbreedte. Bij een overbelast netwerk kan dit de problemen verergeren. Het is dus belangrijk dat we dergelijke problemen duidelijk kunnen opmerken met behulp van de monitoring. Een video met constant bandbreedtegebruik wordt verstuurd van client0 naar client1, in het testnetwerk dat in Figuur 6.1 wordt weergegeven. Net als bij de eerdere experimenten wordt het percentage pakketverlies opgemeten. Ditmaal wordt telkens slechts 1 routeringsalgoritme toegelaten, om te verschillen in pakketverlies op te meten. Om een overbelast netwerk te simuleren, wordt de maximale bandbreedte in het netwerk beperkt. Hiervoor gebruiken we het Click element BandwidthRatedSplitter. De bandbreedte van de video is ongeveer 312 kBps. De metingen zijn dan ook rond dit punt geconcentreerd. Voor elke combinatie van bandbreedte en routeringsalgoritme worden telkens 5 metingen uitgevoerd. In Figuur 6.6 is zichtbaar dat directe routering meestal iets betere resultaten oplevert. De hoeveelheid pakketverlies varieert echter zeer sterk. De figuur geeft voor directe routering ook de minimale en maximale waarden voor pakketverlies. Vanwege deze variaties is het vrij moeilijk harde conclusies te trekken. Er is overhead door overlayroutering bij video,
Figuur 6.6: Het pakketverlies bij overlayroutering ligt bij de meeste testen hoger.
maar deze lijkt niet altijd even zwaar door te wegen. De overhead zorgt wel voor wat bijkomend pakketverlies. Het is dus mogelijk om regels op te stellen die de voorkeur geven aan een algoritme met een iets lager pakketverlies, maar nog steeds vrij hoog. Dit kan een alternatief vormen voor het systeem waarbij gealterneerd wordt tussen routingsalgoritmes tot werkelijk voldaan is aan een vaste vereiste voor pakketverlies. Een andere aanpak bij deze test zou kunnen zijn om telkens een ander routeringsalgoritme als eerste te laten routeren. Bij constante bandbreedte zou rechtstreekse routering in dat geval aan de buurt blijven als de beschikbare bandbreedte iets hoger ligt dan de bandbreedte gebruikt door de video. Deze aanpak gebruiken was echter niet mogelijk. Pakketverlies bleef ook bij rechtstreekse routering optreden. Vermoedelijk is er dus toch sprake van variaties in bandbreedtegebruik, ondanks het instellen van een constant bandbreedtegebruik.
6.4
Aggregatie van verbindingen
Het combineren van verschillende verbindingen kan de netwerkoverhead die veroorzaakt wordt door overlaynetwerken enigszins verminderen, zoals besproken in Sectie 4.3.2. We zouden dan ook op het netwerk van Figuur 6.1 een aantal videostromen kunnen opzetten die een verbinding maken met de dezelfde gebruiker. In Sectie 6.3 werd echter reeds het pakketverlies bekeken bij een verzadigde verbinding. Gedurende de eerste seconden werd bij alle metingen geen pakketverlies opgemeten. Aangezien aggregatie bij One Hop Routing en N Hop Routing enkel het netwerkverkeer gedurende de eerste seconden zal verminderen, bleek het dus niet nuttig op dit experiment
aggregatie uit te voeren. Vanwege dezelfde reden werd ook niet dieper ingegaan op het vari¨eren van de parameters bij N Hop Routing, zoals ook besproken in Sectie 4.3.2.
Hoofdstuk 7
Conclusie Op basis van de uitgevoerde testen kunnen we duidelijk besluiten dat overlayroutering er in slaagt om netwerkproblemen te omzeilen om een bepaalde Quality of Service aan te bieden. Bovendien merken we de meerwaarde van de architectuur die gebruik maakt van meerdere routeringsalgoritmes. Op deze manier kunnen we de nadelen van sommige routeringsalgoritmes vermijden en snel tot een goede oplossing komen. Een aantal nadelen aan de architectuur werden ook duidelijk. In Sectie 6.2.2 was duidelijk een langere tijd nodig om het juiste routeringsalgoritme te vinden, voornamelijk omdat de eerste keuze niet optimaal was. Het gebruik van overlays leidt dus niet in alle gevallen tot een snelle oplossing. In huidige netwerksystemen wordt enkel gebruik gemaakt van IP-routering. Als men daarnaast nog overlayroutering gebruikt, kunnen we de nadelen van zowel IP-routering als van overlayroutering vermijden.
7.1
Toekomstig werk
Naar de toekomst toe lijkt het onder andere belangrijk om de mogelijke nadelen van overlayroutering in het algemeen weg te werken. Specifiek kan ook op een aantal punten van de voorgestelde architectuur geconcentreerd worden. Een van de nadelen bij overlayroutering is de veroorzaakte overhead. Het was niet mogelijk om hier binnen deze masterproef specifiek op te concentreren, maar de mogelijkheden van het aggregeren van netwerkstromen lijken in elk geval groot. Vooral bij routeringsalgoritmes die uitgebreide netwerkcontroles uitvoeren, kan dit van belang zijn. Binnen de ge¨ımplementeerde architectuur wordt overgeschakeld tussen een aantal routeringsalgoritmes. Voor deze overschakeling worden momenteel nog geen intelligente keuzes gemaakt. Het uitwerken van geavanceerdere regels om sneller tot een correcte routering te 54
komen, kan naar alle waarschijnlijkheid nog heel wat verbetering opleveren. Verder onderzoek is dus aangewezen.
Hoofdstuk 8
Click Router implementatie Een voorbeeld van de Clickconfiguratie bij een van de experimenten wordt weergegeven in Figuur 8.1, Figuur 8.2 en Figuur 8.3. Deze configuratie is voor een router met 3 netwerkpoorten. In Figuur 8.1 wordt weergegeven hoe ARP- en IP-pakketten apart worden geclassificeerd. Bij IP-pakketten wordt de header nog gecontroleerd en verwijdert men de Ethernetencapsulatie. In Figuur 8.2 worden de verschillende stappen van de architectuur uitgevoerd, zoals uitgelegd in Sectie 5.1. De configuratie wordt geladen op een server waarop geen andere software vereist is. Voor het gemak worden pakketten die gericht zijn aan de server dan ook doorgestuurd naar een PingResponder. Dit element stuurt ICMP PONG-pakketten terug. Andere pakketten worden naar het overlayelement of pakketverliescontrole gestuurd, zoals ook weergegeven in Figuur 5.1. Omdat de server in de experimentele configuraties ook pakketten als IP-router verder moet sturen, worden passerende pakketten naar de IP-opzoeking gestuurd. In Figuur 8.3 worden de stappen weergegeven die door vertrekkende pakketten doorlopen worden. Het ARPQuerier element ontvangt zowel IP-pakketten als ARP responses. Als dit element een IP-pakket ontvangt waarvoor nog niet bekend is naar welk Ethernetadres het gestuurd moet worden, kan dit element ARP queries versturen om het adres te bepalen. Verder is enkel het ToDevice element vereist. Dit verstuurt de pakketten via de netwerkkaart. De tussenliggende stappen worden uitgevoerd om vertraging en pakketverlies te simuleren.
56
Figuur 8.1: Pakketten arriveren en worden geclassificeerd volgens type.
Figuur 8.2: De verschillende types IP-pakketten doorlopen pakketverliescontrole, routering en overlay.
Figuur 8.3: Pakketten worden verdergestuurd. Voor de experimenten wordt hier pakketverlies en vertraging gesimuleerd.
Hoofdstuk 9
Overzicht CD-ROM De CD-ROM die bij deze masterproef werd gevoegd, bevat de ge¨ımplementeerde sofware, the testresultaten van de uitgevoerde experimenten en de instellingen van deze experimenten. De inhoud is als volgt opgebouwd.
9.1
Implementatie
De hoofdmap Implementatie bevat de verschillende ge¨ımplementeerde softwarecomponenten. Enerzijds zijn dit de netwerkelementen die in Click werden gemaakt met de programmeertaal C++. De map Netwerkelementen Click bevat de code voor deze elementen en een README-bestand dat de nodige instructies bevat om deze elementen met Click Modular Router te gebruiken. Anderzijds is er het programma dat de functies van de logische component in de architectuur uitvoert. Dit werd ge¨ımplementeerd in Java. De map Logisch Systeem bevat de code voor deze component. Daarnaast werd ook een README-bestand bijgevoegd dat de nodige instructies bevat om het programma te gebruiken.
9.2
Experimenten
De hoofdmap Experimenten bevat de gebruikte scripts om de experimenten op te zetten en de resultaten die bekomen werden met de experimenten. Er zijn drie verschillende mappen met dezelfde structuur. De map van het eerste experiment (Sectie 6.2.1) is switching eval 1error. Het tweede experiment (Sectie 6.2.2) bevindt zich in de map switching eval. Het laatste experiment (Sectie 6.3) bevindt zich in de map overhead eval. Elk van deze mappen zijn op een gelijkaardige manier opgebouwd. 60
• Een deelmap results bevat de testresultaten en een pythonscript en een gnuplotscript om de resultaten op een overzichtelijke manier weer te geven.. • Een tweede deelmap, generate click configuration bevat de Clickinstellingen in het bestand settings.json en een aantal templatebestanden. Het script set addresses.py kan op een Click router uitgevoerd worden als alle andere bestanden van de deelmap aanwezig en genereert dan automatisch een juiste Clickconfiguratie. • Een laatste deelmap generate vw configuration bevat de nodige templatebestanden en een script om een configuratie voor de opstelling voor de Virtual Wall te genereren.
Bibliografie [1] J. Moy, “OSPF Version 2.” RFC 2328 (Standard), Apr. 1998. Updated by RFC 5709. [2] Y. Rekhter, T. Li, and S. Hares, “A Border Gateway Protocol 4 (BGP-4).” RFC 4271 (Draft Standard), Jan. 2006. [3] C. Labovitz, A. Ahuja, A. Bose, and F. Jahanian, “Delayed internet routing convergence,” in in Proc. ACM SIGCOMM, pp. 175–187, 2000. [4] D. Andersen, H. Balakrishnan, F. Kaashoek, and R. Morris, “Resilient Overlay Networks,” tech. rep., 2001. [5] K. P. Gummadi, H. V. Madhyastha, S. D. Gribble, H. M. Levy, and D. Wetherall, “Improving the reliability of Internet paths with One-hop Source Routing,” in In OSDI, pp. 183–198, 2004. [6] Z. Li, S. Member, P. Mohapatra, and S. Member, “QRON: QoS-aware routing in overlay networks,” IEEE Journal on Selected Areas in Communications, vol. 22, pp. 29–40, 2004. [7] A. Basu and J. Riecke, “Stability issues in OSPF routing,” SIGCOMM Comput. Commun. Rev., vol. 31, no. 4, pp. 225–236, 2001. [8] R. Braden, D. Clark, and S. Shenker, “Integrated Services in the Internet Architecture: an Overview.” RFC 1633 (Informational), June 1994. [9] S. Blake, D. Black, M. Carlson, E. Davies, Z. Wang, and W. Weiss, “An Architecture for Differentiated Service.” RFC 2475 (Informational), Dec. 1998. Updated by RFC 3260. [10] I. Stoica and H. Zhang, “Providing guaranteed services without per flow management,” pp. 81–94, 1999. [11] R. Braynard, D. Kostic, A. Rodriguez, J. Chase, and A. Vahdat, “Opus: an Overlay Peer Utility Service,” in In Proceedings of the 5th International Conference on Open Architectures and Network Programming, 2002. [12] R. Karrer and T. Grass, “Multipath streaming in best-effort networks,” 2003. [13] P. Maymounkov and D. Mazi`eres, “Kademlia: A peer-to-peer information system based on the xor metric,” 2002.
62
[14] P. R. Pietzuch and J. M. Bacon, “Hermes: A distributed event-based middleware architecture,” pp. 611–618, 2002. [15] F. Araujo, L. Rodrigues, N. Carvalho, and N. Carvalho, “Scalable QoS-Based Event Routing in Publish-Subscribe Systems,” in In Proc. of NCA’05, 2005. [16] E. Gelenbe, R. Lent, A. Montuori, and Z. Xu, “Cognitive Packet Networks: QoS and Performance,” Proceedings of the 10th IEEE Int’l Symp. on Modeling, Analysis, & Simulation of Computer & Telecommunications Systems (MASCOTS’02), 2002. [17] E. Gelenbe, M. Gellman, R. Lent, P. Liu, and P. Su, “Autonomous smart routing for network QoS,” 2004. [18] D. Subramanian, P. Druschel, and J. Chen, “Ants and Reinforcement Learning: A Case Study in Routing in Dynamic Networks,” pp. 832–838, 1998. [19] L. Subramanian, I. Stoica, H. Balakrishnan, R. H. Katz, and Y. H. Katz, “OverQoS: An Overlay based Architecture for Enhancing Internet QoS,” 2004. [20] K. Lakshminarayanan, I. Stoica, and S. Shenker, “Routing as a service,” tech. rep., 2004. [21] S. Davy, B. Jennings, and J. Strassner, “The policy continuum - a formal model,” Proceedings of the 2nd IEEE International Workshop on Modelling Autonomic Communications Environments, 2007. [22] S. Voulgaris, D. Gavidia, and M. van Steen, “CYCLON: inexpensive membership management for unstructured P2P overlays,” Journal of Network and Systems Management, vol. 13, pp. 197–217, June 2005. [23] P. Benko and A. Veres, “A Passive Method for Estimating End-to-End TCP Packet Loss,” 2002.
Lijst van figuren 1.1
1.2
2.1
2.2
3.1
3.2
4.1
4.2
Routering in het internet gebeurt met verschillende algoritmes binnen Autonome Systemen en tussen Autonome Systemen. . . . . . . . . . . . . . . . . .
2
Rechtstreekse routering ondervindt problemen. Overlayroutering kan de netwerkproblemen omzeilen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
Resilient Overlay Networking zorgt voor veel overhead op vlak van bandbreedtegebruik. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
QRON gebruikt een aantal Overlay Brokers die een hi¨erarchisch netwerk vormen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
Een netwerkprobleem zorgt ervoor dat de rechtstreekse IP-verbinding niet meer functioneert. Overlayroutering laat toe toch een verbinding te maken. .
18
De opbouw van de middlewarelaag in meer detail, met de verschillende onderdelen weergegeven. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
Knopen P en Q wisselen gekende knopen uit. De pijlen tonen welke knopen gekend zijn door P en Q. Merk op dat de richtingspijl tussen P en Q gewisseld wordt. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
De bron (src) slaagt er niet in een rechtstreekse verbinding op te zetten met het doel (dst). Routeren via een tussenliggende knoop (hop1) is wel mogelijk.
25
4.3
De bron (src) slaagt er niet in een rechtstreekse verbinding op te zetten met het doel (dst). Routeren via een aantal tussenliggende knopen is wel mogelijk. 26
4.4
Opeenvolgende pakketten arriveren bij een router. Het pakketverlies wordt berekend aan de hand van de middelste pakketten. . . . . . . . . . . . . . . .
27
Ontwerp router in Click . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
5.1
64
5.2
Pakketten arriveren via 3 verschillende ingangen. Pakketten van een interne of externe bron worden apart behandeld, evenals pakketten van andere PacketLossCheckerelementen. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35
5.3
Er zijn 3 pakkettypes ge¨ımplementeerd bij de CYCLON overlay. . . . . . . . .
36
5.4
Pakketten van een interne of een externe bron worden anders behandeld. . .
37
5.5
De PING- en PONG-pakketten zijn vrij gelijkaardig, en houden timinginformatie en tussenliggende knopen bij. . . . . . . . . . . . . . . . . . . . . . . . .
39
SET-pakketten houden een lijst bij van tussenliggende knopen, om te weten welk pad ingesteld moet worden. . . . . . . . . . . . . . . . . . . . . . . . . . .
41
De standaard structuur van een pakket is bijna volledig vrij (op de eerste 2 byte na). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
41
6.1
Het netwerk bestaat uit 2 gebruikers en 7 overlayrouters. . . . . . . . . . . . .
48
6.2
1 netwerkonderbreking kan makkelijk omzeild worden. . . . . . . . . . . . . .
49
6.3
Een netwerkonderbreking omzeilen gaat snel. . . . . . . . . . . . . . . . . . .
49
6.4
Meerdere netwerkonderbrekingen vereisen een geavanceerd routeringsalgoritme om te omzeilen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
50
6.5
Een complexer probleem duurt langer om te omzeilen. . . . . . . . . . . . . .
51
6.6
Het pakketverlies bij overlayroutering ligt bij de meeste testen hoger. . . . . .
52
8.1
Pakketten arriveren en worden geclassificeerd volgens type. . . . . . . . . . .
57
8.2
De verschillende types IP-pakketten doorlopen pakketverliescontrole, routering en overlay. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
58
Pakketten worden verdergestuurd. Voor de experimenten wordt hier pakketverlies en vertraging gesimuleerd. . . . . . . . . . . . . . . . . . . . . . . . . .
59
5.6
5.7
8.3
Lijst van tabellen 2.1
6.1
We kunnen in een algemeen overzicht de voor- en nadelen van verschillende algoritmes naast elkaar leggen. . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
De routeringstabel voor click0 geeft de knoop waar langs gerouteerd wordt om een bepaald subnet te bereiken. . . . . . . . . . . . . . . . . . . . . . . . . .
48
66
