Home

LTU - EX - - 04/228 - - SE - Luleå tekniska universitet

1. Split Horizon BGP Compare Fail Down Multi 3500 3000 no BGP4 no GhostFlushing 2500 no GhostBuster 20 o no GhostBuster 30 g 2000 4 no GhostBuster 50 8 1500 Bara a GhostFlushing 1000 GhostBuster 20 GhostBuster 30 500 GhostBuster 50 0 Nodes Figure 5 54 Comparing between having or not Split Horizon 5 5 Simulation Results Split horizon Enabled Jitter Activated 5 5 1 Clique Topology Clique Initial SetUp Time 140 120 RT 100 i BGP4 3 804 GhostFlushing 8 GhostBuster 20 604 B GhostBuster 30 GhostBuster 50 40 20 4 5 6 7 8 9 1011 12 13 14 15 16 17 18 19 20 Size Figure 5 55 Clique Set Up time Jitter Split horizon Clique Initial SetUp Num Messages 16000 14000 12000 10000 BGP4 7 GhostFlushing GhostBuster 20 Messages 8000 s GhostBuster 30 6000 gt GhostBuster 50 4000 rud 2000 ma 0 45 6 7 8 9 10111213 14 15 16 17 18 19 20 Size Figure 5 56 Clique Set Up Messages no Jitter Split horizon 5 5 Simulation Results Split horizon Enabled Jitter Activated Clique Fail Down Time BGP4 GhostFlushing GhostBuster 20 GhostBuster 30 GhostBuster 50 4 5 6 7 8 9 1011 12 13 14 15 16 17 18 19 20 Size Figure 5 57 Clique
2. BGP4 3 300 GhostFlushing 8 250 GhostBuster 20 GhostBuster 30 GhostBuster 50 amp 200 150 100 50 0 v vk E E Size Figure 5 12 AltPath Fail Over time no Jitter No Split horizon AltPath Fail Down Num Messages 25000 20000 4 BGP4 n 4 3 15000 GhostFlushing 5 GhostBuster 20 E GhostBuster 30 10000 1000 gt GhostBuster 50 5000 W 0 Ser ex ed Pe oe P P Size Figure 5 13 AltPath Fail Over messages no Jitter No Split horizon ghost buster with the delta timer value of 50 that grows worse from 24 nodes size In this case the early elimination of ghost information makes the rules to behave better than the traditional BGP However the delta timer is a big drawback even without the ghost information update messages are needed in this scenario Fail over scenario and they are conseguence of other updates About the messages on the fail over eliminating the ghost information obviously eliminates the reproduction of it in more ghost information reducing the number of messages The performance of all the rules is the same Not considering the glitch 54 Chapter 5 BGP4 Cases Simulation Multi Set Up Time 6000 5000 4000 BGPi GhostFlushing GhostBuster 20 GhostBuster 30 GhostBuster 50 Seconds w S o S 2000
3. Read packet from socket stream Packet health checks Extract withdrawals from update Extract attributes Extract New NLRIs bgp_process DECISION PROCESS Check Attributes Process new routes if anY Figure 6 5 Zebra s bgpd handling an incoming update message bgp_route c old_route new_route bgp_process Look in al the RIB_INs for the best route for this NLRI if old_route null gt set it as not selected if new_route nullset it as selected Withdrawal bgp_advertise c bgp_adj_out_set if new_route null Send Update else Send Withdrawal bgp_adj_out_unset gt For each neighboring peer Clean previous messages Creates Withdrawal Puts thread into FIFO Clean previous messages Creates Update Puts thread into FIFO FIFO processed messages sent Update Kernel Messages to Zebra Figure 6 6 Zebra s bgpd decision process Simplified 6 3 Architecture of bgpd 85 6 3 6 The VTY interface New functionalities are going to be implemented so also a way to activate and deactivate them has to be included The daemons configuration is done through the VT Y interface Here we ll try to illustrate how it works In the first place commands in the VTY are organized in a tree structure There are two kinds of nodes environments The ones c
4. Ghost Flushing together with BGP4 4 Nodes 5 Nodes 6 Nodes 7 Nodes 8 Nodes 9 Nodes 10 Nodes 11 Nodes 12 Nodes 13 Nodes 14 Nodes 15 Nodes N Jlittttnt How worse Co o ps NS 1 2 3 456 7 8 9 10 11 12 13 14 15 Active ghost nodes Figura 5 2 Mezclando BGP4 tradicional con ghost flushing M s es peor La fig 5 2 indica el resultado de nuestro experimento El contenido de la figura es confuso as que vamos a explicarlo Cada l nea representa la evoluci n de cada clique empezado izquierda con ning n nodo usando ghost flushing e incrementando el n mero de nodos despu s Como es natural cada serie termina con el caso en que todos los nodos usan ghost flushing El valor How worse significa cuantas veces mayor es Fgown con ese n mero de nodos usando ghost flushing comparado con el mejor Edown posible todos con ghost flushing dado en ese clique Como podemos ver en la figura hay una reducci n lineal de Egown al aumentar el n mero de nodos usando ghost flushing Alcanzando el punto donde solo el 2096 de los nodos no usan ghost flushing y el resultado se acerca al ptimo Esto es una buena noticia de cara a la implementaci n de este protocolo en Internet Podemos ver que hay una mejora en el rendimiento incluso si todos los nodos no utilizan esta regla 5 3 Conclusiones Estas conclusiones son un resumen de los resultados obtenidos en el cap tulo compl
5. 1000 29 110 208 409 Nodes Figure 5 14 Multi Set Up time no Jitter No Split horizon Multi Set Up Messages 3500000 3000000 2500000 BGP4 2000000 GhostFlushing GhostBuster 20 1500000 4 GhostBuster 30 gt GhostBuster 50 1000000 4 500000 0 T 7 y 29 110 208 409 Nodes Messages Figure 5 15 Multi Set Up Messages no Jitter No Split horizon Multi Fail Down Time 3500 3000 L 2500 m BGP4 k 2000 GhostFlushing 8 GhostBuster 20 8 1500 L GhostBuster 30 GhostBuster 50 1000 500 gt 0 29 110 208 409 Size Figure 5 16 Multi Fail time no Jitter No Split horizon 5 2 3 Multi Topology Set Up Looking at the results in this charts we first notice that the values cross when we pass to extremely big networks From the 200 nodes value If we look to the smaller values 29 110 Ghost flushing and traditional BGP behave better than the ghost buster Less messages and less time But when we switch to the bigger values it x crosses and the Ghost buster technique starts to behave better and the bigger the delta the better It looks like conservative approach in extremely big networks works The time and messages used spreading paths that won t be used in the end is less when we use a much more conservative approach of ghost buster 5 2 Simulation Re
6. GhostBuster 20 60000 4 GhostBuster 30 GhostBuster 50 messages 40000 4 20000 LE 0 29 110 208 409 nodes Figure 5 66 Multi Fail messages Jitter Split horizon Convergence We see similar results to the previously obtained The same tendency crossing appears again Still if we compare with previous measurements we can find a general improvement in all the BGP versions if we use the split horizon and the jitter on the timers 5 6 Comparing all the techniques All Techniques Compared BGP4 SH Jitter GF SH Jitter GB 20 SH Jitter 4000 GB 30 SH Jitter GB 50 SH Jitter 3500 4 BGP4 SH GF SH 3000 GB 20 SH GB 30 SH g 2500 y GB 50 SH 3 2000 BGP4 Jitter GF Jitter GB 20 Jitter GB 30 Jitter GB 50 Jitter BGP4 GF GB 20 GB 30 GB 50 4500 1500 4 1000 500 Figure 5 67 Multi Baown In previous chapters we went through comparing the different techniques with the traditional BGP in many different situations We repeated the experiments changing the settings of some features inside the BGP4 jitter applied to timers and split horizon So in this section we will compare all the techniques with this settings activated and deactivated The idea is to see which is the best combination of settings In fig 5 67 we can see the result of this comp
7. Convergence Time 174610 lt 1829 Figure 5 24 Bad Fail over time no Jitter No Split horizon Fail over Time Again we limit the number of histograms to this two cases traditional and ghost flushing bgp In this case we didn t consider the total stabilization of the system but when the node 1 can access the destination The result is as show the MRAI timer of difference being the traditional BGP a winner in this category 5 3 Simulation Results Split horizon disabled Jitter Activated 5 3 1 Clique Topology 140 120 100 80 60 Seconds 40 20 Clique Initial SetUp Time BGP4 GhostFlushing GhostBuster 20 GhostBuster 30 GhostBuster 50 4 5 6 7 8 9 1011 12 13 14 15 16 17 18 19 20 Size Figure 5 25 Clique Set Up time Jitter No Split horizon 5 3 Simulation Results Split horizon disabled Jitter Activated 59 Clique Initial SetUp Num Messages 16000 14000 A 12000 10000 4 BGP4 gt GhostFlushing 2 8000 4 GhostBuster 20 3 5 GhostBuster 30 6000 GhostBuster 50 4000 4 2000 4 0 4 5 6 7 8 9 101112 13 14 15 16 17 18 19 20 Size Figure 5 26 Clique Set Up Messages no Jitter No Split horizon Clique Fail Down Time 450 400 zn 350 2007 BGP4 3 250 GhostFlushing 5 GhostBuster 20 8 200 G
8. Daemon mode Others Start FSM Calling main Thread Figure 6 4 bgpd daemon initialization process 6 3 5 From an Update Arrival to an Update Departure This section will show a small schema of the update handling emission system A part of the BGP implementation critical for future modifications done in this work In fig 6 5 we find the first stage of it how bgpd handles a new update message finishing in the moment when the decision process is run The decision process fig 6 6 is really important since that s the place where we will have to do the modifications Also it shows how to send a withdrawal something we have to learn to do to implement the ghost flushing rule We see that withdrawal sending is done by the function bgp adj out unset 8A Chapter 6 Applying the Ghost Flushing Rule to Zebra Routing Software pr Attrib NULL et bgp nlri parse peer Attrib nlris V Packet Health Check Il attrib null ibl attib null bgp_route c V bgp update General Checks Loop Detection IBGP Stuff Rout Ref Next Hop Check If implicit Withdrawal substitue else Create new info put inside tables UPDATE ARRIVES bgp packet c bgp read gt bgp_withdraw Checks Lookup route s in tables Eliminate from tables V bgp rib withdraw V Mark the info as not valid bgp_process Message Type bgp_update_receive
9. FN ISP ISP FN 1 Level 1 Level 1 EUN ISP EUN 2 JA tee Level 2 E EU E Figure 2 8 Chaotic example of Internet providers interconnection 2 4 History In this chapter we will try to make a small summary of the Internet time line highlighting those events related with the evolution of routing protocols Based on Hobbes Internet Timeline 37 Connected an Internet Encyclopedia 2 The Wikipedia 11 and various RFCs 28 29 19 24 21 22 32 35 27 21 1969 ARPANET is born Very few nodes First Dynamic routing protocols used in flow distribution 70s ARPANET keeps growing IP is not invented yet So routing protocols are not standard access level class or static manual definitions 12 Chapter 2 BGP4 Routing Protocol and its Environment 1982 TCP IP is defined and applied to Internet Internet as an interconnection between networks is born EGP RFC 827 29 specified and used for gateways between networks 1983 DNS is born and started up 1986 NSFNET the first back bone 56 kbits is born 1988 First specification of RIP established RFC 1058 19 1989 100 000 hosts barrier broken OSPF Defined RFC 1131 24 BGP defined RFC 1105 21 1991 BGP 3 Definition RFC 1267 22 1992 Topology related IP addressing Supernetting proposed RFC 1338 32 1994 CIDR begins to be deployed BGP 4 Definition RFC 1654 35 1995 NSFNET reverts back to a research network Commercial interconnected netw
10. B hire datus tea ee hat Se Pod ld alin Ss oak de Min Gee ae d ae Sd nin S eed 5 3 White topology 2 4 are Era Pe oe en ee ae ae S b 4 Bad topology tic zu Mean er ex We er ee mur ie A oe eee d 5 5 29 nodes structure Image Generated by RaceWay network visualization tool 5 6 Clique Set Up time no Jitter No Splithorizon o o 5 7 Clique Set Up Messages no Jitter No Split horizon k 5 8 Clique Fail Down time no Jitter No Split horizon onen 5 9 Clique Fail Down messages no Jitter No Split horizon ss 5 10 AltPath Set Up time no Jitter No Split horizon se 5 11 AltPath Set Up Messages no Jitter No Split horizon 5 12 AltPath Fail Over time no Jitter No Split horizon e 5 13 AltPath Fail Over messages no Jitter No Split horizon 5 14 Multi Set Up time no Jitter No Split horizon e xiii xiv LIST OF FIGURES 5 15 Multi Set Up Messages no Jitter No Split horizon 2m nn nn 5 16 Multi Fail time no Jitter No Split horizon o ooa 5 17 Multi Fail messages no Jitter No Split horizon e 5 18 White Fail down time no Jitter No Split horizon lt 22 2 2m nn nn 5 19 White Fail down time no Jitter No Split horizon s 5 20 White Fail down time no Jitter No Split horizon lt s 5 21 White Fail down time no Jitter No Split horizon 2 2 2 2 nn nn 5 22 White Fail time down no
11. L Gao On inferring autonomous system relationships on the internet 2000 C Hedrick Routing information protocol RFC 1058 Internet Engineering Task Force Jun 1988 C Huitema Routing in the Internet Prentice Hall 1995 Y R K Lougheed Border gateway protocol bgp RFC 1105 Internet Engineering Task Force Jun 1989 Y R K Lougheed Border gateway protocol 3 bgp 3 RFC 1267 Internet Engineering Task Force Oct 1991 153 154 BIBLIOGRAPHY 23 A D S J Michael Feng Roy Leung Summer report 1999 Linux network Technical report Network Architecture Lab Electrical and Computer Engineering University of Toronto 24 J Moy Ospf specification RFC 1131 Internet Engineering Task Force Oct 1989 25 J S P Traina D McPherson Autonomous system confederations for bgp RFC 3065 Internet Engineering Task Force February 2001 26 B Premore Multi AS topologies from BGP routing tables http www ssfnet org Exchange gallery asgraph index html 27 E R Hinden S Deering Ip version 6 addressing architecture RFC 1884 Internet Engineering Task Force December 1995 28 Y Rekhter A border gateway protocol 4 bgp 4 RFC 1771 Internet Engineering Task Force March 1995 29 E Rosen Exterior gateway protocol RFC 827 Internet Engineering Task Force Oct 1982 30 E C T Bates R Chandra Bgp route reflection an alternative to full mesh ibgp RFC 2796 Internet Engineering Task Force April 20
12. hg dd 21 44 1 NS2 and BGPFE ag 2 un ee SHAE eva 21 41 2 SSBENGUAIO jatta aset de bao apes b eese bbe Pee Ru uou eue d 22 4 2 Simulation Environment 24 4 2 1 Simulation Parameters and Method Ke 24 4 2 2 Simulating means programming kk e 25 vii viii CONTENTS 42 32 The Hardware e tas a efe bbb deas ee eek Ye eee dd deor de 31 4 3 Analysis of SSFNet s BGP4 Implementation es 32 4 3 1 Source Structure zs ues ede e ue ee DEN en s Done e Re e yc 32 4 3 2 BGPSession Class x md Yu RASSE EMO VM a de R 33 4 9 9 The Update Process c 22 8 22 Wr 3 a pen ae EEE 36 4 4 Modifications to SSFNet s BGP4 for the Ghost Flushing Rule 37 4 4 1 Activating The Ghost Flushing feature from the DMLfile 37 4 4 2 Modification Schema iv s sov 288 ro PUE EY Y do UR A 3T 4 4 3 Deeper Inside the Modification Pseudocode llle 37 4 5 Modifications to SSFNet s BGP4 for the Ghost Buster Rule Al 4 5 1 Activating The Ghost Buster feature from the DML file 41 4 5 2 The main idea for the modification lees 41 4 5 3 Making this complex schema work ee 41 4 5 4 Deep inside the code Pseudocode en 42 4 5 5 Data structures needed to make all this work se 44 4 5 0 Class chema a a ee ee ERDE EE ER Aes 45 5 BGP4 Cases Simulation 47 5 17 Simulated Cases manta AR 4 AAA AS AAA dde TAS 47 SLI Clique a das es RIS e e RE a TT e RT HUIUS AT
13. s BGPA for the Ghost Buster Rule 45 4 5 6 Class Schema This schema pretends to show the interconnection between the classes mentioned It just reflects how the classes point each other ListBusterRoutes PEER PEERClass NN BusterRoute 3 van ETE Figure 4 11 Ghost Buster modification Classes interaction 46 Chapter 4 BGP4 Simulation Environment Chapter 5 BGP4 Cases Simulation 5 1 Simulated Cases In this chapter we will show each of the topologies used to analyze the performance of the BGP4 and the rules proposed to modify it 5 1 1 Clique Clique topology is the worst case scenario in the convergence problem that we are studying The more the nodes are interconnected the more ghost information that will be created This topology has a big theoretical interest as a worst case scenario The tests done are just about how it sets up and how it reacts to the failure of one of the nodes The node that goes down is one of the nodes of the alternate path that connects to the clique Sizes from 4 to 20 nodes Convergence Times studied Edown and Eup Interest Theoretical Figure 5 1 Full connected 5 nodes clique 5 1 2 Alternate Path AltPath This topology is meant to test the capabilities of Ghost Flushing and Ghost Buster in a Fail over situation This topology complies with this property Given n as the total number of nodes there is an alternate path of size 5 connecting two n
14. 3 1 EI Problema de la Convergencia e e 3 1 1 Algunas Ideas Iniciales o o 3 1 2 Tiempo de Convergencia Elevado y la Informaci n Fantasma 3 2 Regla Ghost Flushing ida a 22 ER ED e Rte a RU 3 2 1 Como Funcion iem E AA Er Er Bari 3 2 2 Tiempo de convergencia e 3 9 Regla Ghost Busterz canta a Sean an aa ALA EP RE RW see Ree Ie EA 3 9 1 Como B nci nas xu ug ra RS aeu ee ege elei mode UE ja 3 3 2 Tiempo de Convergencia 3 42 Otras Solutiones us use uA REED Rok ge A ee didi iuto ne de e deme JA X 3 4 1 Reglas de Reseti x 4s duo A Xx OY dox ow o a RO UU 3 4 2 Otros enfoques sobre el mismo problema L 4 Entorno de Simulaci n BGP4 4 1 Simulador y casos Simulados e 4 2 Modificaciones a la implementaci n para la regla Ghost Flushing 4 2 1 Activando la regla Ghost Flushing desde el archivo DML 4 2 2 Esquema de modificaci n Modification ke 4 3 Modificaciones al la Implementaci n regla Ghost Buster o o 4 3 1 Activando la regla Ghost Buster desde el archivo DML 4 3 2 La idea detr s dela modificaci n Ke 4 3 3 Como funciona todo este lio e 5 Simulaci n de Casos de BGP4 5 1 Comparando todas las t cnicas 5 2 Combinando nodos con y sin ghost flushing e 5 3 Conclusiones ae ri ee ee 5l GhostsElushi 2 o o O a de da war 5 3 27 Ghost Buster 230 sn ass eg a en de A MKI 6 Aplicando la regla Ghost Fl
15. 6 5 Tests 6 5 1 Testing and Developing Environment Setting a proper environment to work with the Zebra daemon modify it and test it afterwards was really important thing We considered that spending some extra time in this issue would save time later while test running Computers and Network equipment To do this part of the project a pool of seven computers and a ethernet switch were assigned in the basement These are the specs General of the computers e Processor 80x86 based ranging from Pentium to Pentium II e Memory Ranging from 64 to 128 Mb e Network Adapters All of them had two ethernet network cards e Operating System FreeBSD 5 2 All of them have the same operating system because we wanted to have only one compiled copy of the bgpd to be execute from all the machines To recompile the code in all the machines was just not an option From now on we will refer to them as bgp1 bgp2 bgp3 bgp4 bgp5 bgp6 and bpg7 The switch was a hp procurve switch 2524 Some of the main features relevant to this project were e 9 6 Gbps switch fabric integrated on chip e HP Auto MDIX e Stacking capability e VLAN support and tagging support up to 30 port based VLANs e Web and telnet terminal configuration environments Network Layout The configuration that we established had the a double intention first we wanted everything connected to the internet so everything could be managed remotely via telnet or ssh The sec
16. But this model is not scalable When the Internet began growing manual configuration was ruled out 4 Chapter 2 BGP4 Routing Protocol and its Environment Network C Router 2 Network A etwor z 130 240 0 0 8 Router Network B Network C wo Router E Router 4 Network D L Figure 2 2 Routers communicating reachabillity information This was the moment where routing protocols were born The main idea regardless how is this achieved is that routers communicate between them propagating the information about the networks they know how to reach them Let s picture an small example a situation like the one on fig 2 2 Router 1 is manually configured with the IP range of Network A 130 240 0 0 8 Then router 1 will contact routers 2 and 3 to tell them that through 1 the IP range 130 240 0 0 8 can be reached Then Router 2 and 3 will inform all the routers they know Except for Router 1 about the new IP range they learnt For example router 3 will communicate router 4 that it knows how to reach Network A Apart from network B This way the reachability information will be spread automatically Due to the different network topologies and situations Technical and political on the Internet routing protocols are not so simple There are other characteristics that are needed for them to work Loop detection fail detection subnetworks policies Filtering
17. Messages o o E x EZ o ize Figure 5 49 AltPath Fail Over messages No Jitter Split horizon Fail Over We notice small differences from the case where the split horizon was activated About the Egown until the size of 20 nodes the ghost buster rule with a delta of 20 performs the same and sometimes better than the ghost flushing But from that point on the ghost flushing is the winner About the number of messages the more conservative policy of the ghost buster rule is noticed in extremely big cliques but this small differences are anecdotic 5 4 5 Multi Topology Multi Set Up Time 4000 3500 3000 y 2500 BGP4 y GhostFlushing GhostBuster 20 GhostBuster 30 1500 gt GhostBuster 50 Seconds N 3 o S 1000 500 9 110 208 409 Nodes Figure 5 50 Multi Set Up time no Jitter Split horizon Multi Set Up Messages 3000000 BGP4 2500000 7 2000000 GhostFlushing 1500000 4 GhostBuster 20 GhostBuster 30 GhostBuster 50 Messages 1000000 500000 0 29 110 208 409 Nodes Figure 5 51 Multi Set Up Messages no Jitter Split horizon 5 4 Simulation Results Split horizon Enabled No Jitter 69 Multi Fail Down Time 1400 1200 1000 gt BGP4 g 800 GhostFlushing
18. route instability 16 33 strange behaviors due to misconfigurations 12 bad interactions between internal and external BGP 33 or too high convergence time 12 13 15 in certain situations In this work we are analyzing a small set of the problems related with the high convergence time This chapter will define precisely the scope of this work and present the solutions proposed to solve this set of problems Besides an analysis of the theory behind them will be done 3 1 The Convergence Problem 3 1 1 Some initial concepts Before getting inside the problem a set of common concepts related to the problem have to be fixed Networks will be seen as graphs formed by nodes BGP4 speakers and arcs linking them BGP4 session between two speakers Event Whatever can happen in the network i e a link down up a node down up that would alter the network I e Fail down fail over system up shorter path Fail down A destination is not reachable anymore Fail over A destination is now reachable through a longer path than before System up A destination that was unavailable is now reachable Shorter Path A destination now is reachable through a shorter path than before Convergence Time Time since an event happens on the network Fail down fail over system up shorter path until the configuration of the network stabilizes and the routing tables of all the nodes reach a final state It won t change until another event happens Eup Converg
19. while withdrawals work as a cleaning the updates could be delayed even more so the ghost information is blocked completely This more aggressive approach stopping the ghost information stems from two reasons In the first place some implementations don t include the MRAI limitation so this way we make sure the timer is used The second reason is to try to model the interaction between the ghost flushing and some route oscillation strategies like routing damping mechanism 16 that can mean bigger delays to the spread of update messages than the original BGP A router announces the preferred new ASpath j peering iff it receiv ouncement about th at least delta otherwise it suppres announcement until delta time passes ase Figure 3 6 Ghost Buster rule The delta value can be set with any value however as the simulations will show if it s less than the MRAI value no effect of this rule is noticed Most cases Again a more complex definition and mathematical descriptions can be found in 15 3 4 Other Solutions 19 3 3 2 Convergence time Fail Down situation delta h Being K SUE K Edown hd 3 3 xu 3 3 The idea behind this formula is that according to the ghost buster rule the ghost AS path in the network can increase only once every delta 4 h time The maximum length of an AS Path is d then the equation for t The convergence time is t t E delta h h 3 4 By definition of K we
20. 3 6 Regla Ghost Buster en su enunciado original en ingl s t t A J delta h h 05 Por definici n de K podemos reemplazar delta h Kh y entonces t t dec SS 3 5 Kh h 1 y entonces eng 3 6 down K 1 4 Otras situaciones Esta regla reguiere gue todos los anuncios deben ser retrasados esto debe cumplirse sean o no sobre informaci n fantasma Las implicaciones incluyen un impacto negativo en otras situaciones como start up shorter path or fail over El inter s de esta regla es doble por un lado entender las propiedades de convergencia del BGP y ver las posibles interacciones de ghost flushing con otras t cnicas de control de oscilaci n de ruta 3 4 Otras Soluciones 3 4 1 Reglas de Reset Las reglas de reset 15 extienden a la regla ghost buster aplicando el temporizador delta a todo tipo de actualizaci n sea anuncio o retirada No tiene un inter s aplicado al mundo real as que no fue analizada 3 4 2 Otros enfoques sobre el mismo problema Reverse Poisoning IGRP Es una soluci n no escalable primero limpia todas las rutas de los routers y empieza de nuevo Es funcional en encaminado interno pero definitivamente no para externo Aserciones de Consistencia sobre Rutas para poder identificar totalmente a la informaci n fan tasma requerir an un tiempo de computaci n extra que podr a da ar al rendimiento de los routers Tambi n lleva a problemas en caso de partir las AS 13 Detecci n A
21. 4 1 Choosing a Simulator 23 engine that can be used to simulate many different things Also there are different implementations of the same model There are C and Java implementations for this work the one developed over Java was chosen The main reason was the possibility of running the same copy of the simulator over different machines at the same time This was a great advantage over a theoretical better performance of a C implementation History and features The chosen implementation was the Raceway SSFnet 2 0 because it was the most recent one others can be found on the SSFNet site 9 Between the most notable features of this simulation suite we can highlight From 9 Scalable high performance Java simulation platforms often distributed at no cost for research purposes The best of these are stable compact and can execute either serially on a single pro cessor or in parallel on multiprocessor machines Parallel execution under Linux Solaris and Windows NT using JDK1 2 and higher Other platforms may support parallelism as well A simple standardized syntax for high level model description the Domain Modeling Language DML A DML has helped SSFNet users create complex topology Internet models with 100 000 multi protocol hosts and routers DML specifies a hierarchy of attributes with inline attribute substitution and multiple inheritance DML is simple and easy to read and write directly by mod elers is used in gr
22. 4 2 Modifying the VTY configuration environment 2 se 86 6 5 M TP 89 6 5 1 Testing and Developing Environment eee 89 6 5 2 Testing means Programming 2 2 2 2 2 2 5 91 6 5 3 Tests nd results ta RISE eqq uu ve uw sette 91 6 6 CONCUSIOAS svo ero e dex oot ud AR E bU PEN Ed 3 ADR K 92 6 6 1 General Conclusions 2l ss 92 6 6 2 Odd things about GNU Zebra K Ae 92 7 Conclusions and Discussions 93 7 1 Quality of the Simulation Results 2 2 en 93 1 2 The Ghost Flushing Rule zz um 2 a2 2 2 2 dex RA Havu RENE NERA 93 7 3 The GNU Zebra Routing Software e 94 8 Future Work 95 8 1 Interaction of Ghost Flushing with other features ke 95 8 2 Testing Zebra to its limits Sa KK none 95 II Resumen en Espanol 97 1 Introducci n 99 1 1 Motivaci n prop sito y objetivos 99 1 2 Estructura y m todo de este trabajo Ke 100 2 Protocolo de encaminamiento BGP4 y su entorno 101 2 1 Descripci n del Protocolo BGP4 Protocol lt KK 101 2 1 1 Vectores de Ruta y Detecci ndeciclos KL 101 2 L 2 Atributos d ruta a Er NN sue wee 101 21235 El Protocolo 22 2 2 Be REGIA SUE VERRE RS 102 2 1 4 Soporte CIDR Zr NK ache eee A oe ee WR E EUN 104 2 1 5 BGP Interno IBGP e 105 2 2 Relaciones entre Sistemas Aut nomos es 106 2 2 1 Clasificaci n de Relaciones y Disposici n en Internet ss 107 x CONTENTS 3 Ghost Flushing y Otras Propuestas
23. 5 IP classes distribution ss dad mmm eR 2 6 Example of a Route Reflector Configuration inside the same AS ln 256 WEilterPolieies seenen dae 24 ng hie Aa ERG 2 8 Chaotic example of Internet providers interconnection ss 3 1 Example of Ghost Information spreading in a clique topology and high Edown 3 2 Example of Ghost Information spreading in a fail over scenario 3 3 Ghost Flushing Ruler 45154 eur Me a U AASIASSA E ELSE ES 3 4 Step by step Ghost Flushing Rule in action e 3 5 Bad situation for ghost flushing e 3 6 Ghost Buster Tule 49 44 Wow owe we eme em SIENEN KSS dob d b oA 4 l SSH Net logo 20s 2 2223 Rad a wa a sie 4 2 Two extremes between reality and theory se 43 Simulation schema aos a iL ed VV Emu RN ue ues 4 4 Interaction between Sigmas and a local account lee 4 5 LTU s Dator Hall the Sigmas are the purple machines in the middle top Photo by courtesy of Johan Hallb ck CC none 4 6 SSFNet s BGP4 code structure ll ess 4 7 Update Process in SSFNet s BGP Schema e 4 8 Ghost Flushed Update Process in SSFNet s BGP Schema L 4 9 Route arrives and the protocol tries to send if but delta timer is not expired 4710 Delta Tamer Expires iu Reo RUE mot rupe ee T 4 11 Ghost Buster modification Classes interaction ke 5 1 Full connected 5 nodes clique a 5 2 Alternate Path scenario of 11 nodes The alternate path has 5 nodes
24. A Ww 10 11 12 13 14 15 16 17 18 19 20 21 22 Bibliography C Implementation of BGP over ns 2 http www isi edu nsnam ns Connected An Internet Encyclpedia volume Internet History chapter http www freesoft org CIE Topics 57 htm The GateD consortium http www gated org GNU Zebra http www zebra org J Sim http www j sim org Marc Greis Tutorial for the UCB LBNL VINT Netork Simulator ns http www isi edu nsnam ns tutorial The Network Simulator ns 2 http www isi edu nsnam ns Quagga Software Routing Suite http www quagga net Scalable Simulation Framework http www ssfnet org Sun Fire V480 Server Brochure http www sun com servers entry v480 The Wikipedia volume Routing Chapter http en wikipedia org The impact of internet policy and topology on delayed routing convergence ACM SIGCOMM 30 175 187 October 2000 S S Anat Bremler Barr Yehuda Afek Improved bgp convergence via ghost flushing IEEE Infocom 2003 N Bhatnagar and H Dara The architecture of zebra Technical report http wiki cs uiuc edu cs427 Software Architecture of Zebra A B C Labovitz A Ahuja and F Jahanian Delayed internet routing convergence ACM SIG COMM August 2000 R G C Villamizar R Chandra Bgp route flap damping RFC 2439 Internet Engineering Task Force November 1998 U P de Madrid VNUML homepage http jungla dit upm es vnuml documentation
25. Activates this rule for all the nodes Ghost Buster True false Activates this rule for all the nodes Delta time Sets the timer of the delta value for the nodes if the Ghost buster rule is activated 3 Execution example tcl genCliqueTop tcl 5 5 5000 true false 0 Clique with 5 nodes node 5 will die at second 5000 of simulation They run ghost flushing but not ghost buster 4 Space used None 5 Response On the standard output will write a topology file of the structure before specified genPath tcl 1 Function Creation of the topology file similar to the one in fig 3 2 2 Parameters Network size Value Natural number The model generated will have an alternate path of this value divided integer division by two The rest will be the size of the clique Time of death Simulation time in seconds in which the dead node should die The node that dies is the one connecting the alternate path with node 2 Ghost Flushing True false Activates this rule for all the nodes Ghost Buster True false Activates this rule for all the nodes 4 2 Simulation Environment 29 e Delta time Sets the timer of the delta value for the nodes if the Ghost buster rule is activated 3 Execution example tcl genPath tcl 11 5000 true true 50 Clique with 11 nodes altpath of 5 nodes and clique of 6 node will die at second 5000 of simulation They run ghost flushing and ghost buster with a delta timer of 50 4 Spac
26. An example make file can be found in the appendix Testing samples Again we tried to create the studied five clique scenario in fig 3 1 and compare the simulation output with the theoretical results We created a DML file with that layout and run the simulation The results were similar to reality but still it didn t exactly look like the example Looking deeper in the log file something was noticed When a node would chose other node as the next hop to a destination it would send an advertisement to all the neighbors However to the one who was going to be next hop it would send a withdrawal This is called split horizon for BGP4 and it is an active loop detection technique that has a good impact in the behavior As It will be shown in the next chapter of BGP4 but to try to validate this simulator we deactivated it So after deactivating it we simulated the example again and finally we got a result that looked exactly like the validation example So after this results the features explained before and the problems with ns 2 we chose SSFNet as the simulator to keep working on this thesis 4 2 Simulation Environment 4 2 1 Simulation Parameters and Method First a simulation method has to be established It includes a series of elements that will be shown here Pool of topologies After looking for topology resources we chose the following models clique 4 20 nodes Alternative path model from fig 3 2 10 30 nodes a bad case for g
27. BGP4 se ha convertido en el pegamento que mantiene a Internet junta por lo tanto cualquier modificaci n que pueda mejorar su comportamiento tendr un efecto positivo en toda la Internet Este proyecto trata sobre una serie de propuestas que pretenden mejorar el rendimiento del BGP4 en ciertas situaciones Esta parte de la memoria pretende ser un pequeno resumen de la memoria completa Aunque incluye parte de las ideas m s importantes de este proyecto no podemos dejar de recomendar la lectura de toda la memoria para alcanzar una visi n completa y detallada del trabajo desarrollado 1 1 Motivaci n prop sito y objetivos BGP4 es el protocolo de encaminamiento externo EGP m s utilizado en estos momentos Su com portamiento es crucial para la estabilidad de Internet haciendo que cualquier defecto o problema que pueda sufrir tenga un impacto muy serio en las comunicaciones mundiales 12 13 15 De hecho algunas problemas han sido descritos relacionados con el rendimiento de BGP4 afectando el tiempo de respuesta y retrasos en las comunicaciones a trav s de Internet Esto lleva a que servicios de tiempo real como el de video conferencia o voz sobre IP y que actualmente se intentan implementar sobre Internet no puedan competir con servicios sobre la fiable r pida y de baja latencia red telef nica digital Como algunos estudios han descrito el rendimiento de BGP4 puede disminuir dependiendo de la topologia de red 12 En casos en lo
28. Route Reflector y Confederaciones 30 25 y control de oscilaci n de ruta 16 e IPv6 aware e Soporta FreeBSD NetBSD OpenBSD GNU Linux sobre IPv4 y IPv6 Aunque elegimos usarlo FreeBSD por su buen rendimiento en sistemas de redes e El sistema de configuraci n es un clon de la notaci n de los routers Cisco e Como desventajas debemos decir que aunque es un buen software no puede competir con un router empotrado con hardware dedicado y preparado para ejecutar el software de encaminado 125 126 Cap tulo 6 Aplicando la regla Ghost Flushing a GNU Zebra 6 2 Arquitectura de GNU Zebra Este cap tulo intenta dar una idea de como est estructurado Zebra para detalles sobre la arquitectura de bgpd recurrir a la memoria principal Estos contenidos est n basado en 14 y nuestra experiencia con GNU Zebra 6 2 1 M dulos Demonios y Sockets Como hemos indicado antes Zebra es un software extremadamente modularizado Cada tarea es ejecutado por un demonio diferente Cada protocolo de encaminado es implementado por un demonio diferente Adem s la funci n de intercambiar informaci n con las tablas del kernel y entre los protocolos es ejecutada por otro demonio el demonio Zebra Esto ayuda a dividir el c digo seg n la funci n que desempene La comunicaci n entre todos los demonios se realiza sobre sockets y usando el protocolo Zebra Veamos un pequeno ejemplo En emphfig 6 1 tenemos al Zebra trabajando con 3 demonios u
29. Superior de Zaragoza Espana y la Lule Tekniska Universitet Suecia durante el curso 2003 2004 Quiero agradecer a mi directora de proyecto en Suecia Lenka Carr Motyckov por su ayuda durante esta tesis y por darme la oportunidad de trabajar en el interesante mundo de los protocolos de encami namiento Tambi n quiero agradecer a mi ponente en Espa a Jes s Alastruey Bened por sus consejos a la hora de hacer que este proyecto se ajuste a los est ndares de la Universidad de Zaragoza No debo olvidar a mis padres Gonzalo y Nieves sin los cuales ni existir a ni podr a haber estudiado o accedido a este programa de intercambio Muchas Gracias Una menci n especial para la gente de soporte inform tico en especial Johan Hallb ck que sopor taron y sufrieron mis intentos de sobrecarga de los computadores sigma Me ayudaron adem s en todo momento con cualquier problema o necesidad alrededor de mis equipos o la red Finalmente quiero saludar y agradecer a mis amigos en Lule y Espa a por ayudarme a que disfrutar de este a o en una universidad extranjera Incluida la gente del LURC A todos ellos gracias Gonzalo Agosto de 2004 xvii Preface Part I Complete Report Chapter 1 Introduction In the beginning networks existed but they were isolated not connected between them Then the need of exchanging information between machines connected to different networks appeared And so routers were invented to make
30. The numbers on the sides are the last AS path announced by each node about the destination to node 0 The numbers inside the squares are the AS paths that will be announced in next round a w means a withdrawal The AS path that is using in that moment by each node is the ASpath indicator We presume that the network is synchronous where events happen in 1 second rounds If something is sent from one node to the other it will arrive in the next round 1 second later Now analyzing what happens in this example In t 0 all nodes can reach node 0 directly but then this nodes goes down In the next round all nodes choose a differen path and want to announce it Let s look to a single node as an example Node 1 In t 1 Node 1 knows that the other nodes can access 0 so it chooses de best one Since all paths are the same Quality it chooses the one with the lowest id 2 Then node 1 will announce the new path it is using 1 2 0 This is the first example of ghost 3 2 Ghost Flushing Rule 15 information Node 1 doesn t know that node 2 cannot access 0 either so it s making assumptions over information no longer valid Now let s keep looking at what happens later Meanwhile the rest of the nodes have done the same but choosing 1 as the next hop to reach 0 Node 1 will learn about this in t 2 and send an immediate withdrawal to everyone However it is too late in t 3 all nodes realize that 1 cannot reach 0 and choose another AS path
31. aceptar este mensaje y dar la sesi n por establecida el otro nodo solo ha de mandar un mensajes de keepalive Actualizaci n una vez que la sesi n est establecida la informaci n de encaminamiento es inter cambiada usando los mensajes de actualizaci n Un mensaje de actualizaci n solamente contiene informaci n sobre un destino Dicha informaci n incluye e Redes alcanzables por este camino tambi n conocido como NLRI Network Layer Recheability Information e Camino de ASs ASs atravesadas por esta informaci n de encaminamiento e Origen de la informaci n e Vecino que est mandando este mensaje e M tricas entre ASs informaci n utilizada en parte de la elecci n de ruta e Inalcanzable indicando que los destinos indicados ya no son alcanzables Cuando un mensajes de actualizaci n es recibido la informaci n es procesada por el protocolo Primero se comprueba el camino de ASs si nuestro n mero de AS ya aparece entonces existe un ciclo y la ruta es descartada Si no es descartada y anuncia una nueva ruta esta ruta es insertada en una tabla llamada RIB IN habiendo una RIB In por cada vecino con el que el router ha establecido una sesi n BGP4 Si el mensaje es de retirada de una ruta toda informaci n sobre ese os destino s en el RIB In correspondiente al vecino que env a el mensaje es eliminada Despu s de hacer cambios en los RIB in se ejecuta el proceso de decisi n este proceso eval a las r
32. and GB D20 sigma3 GB D30 GB D50 e Topology Can take the values clique altpath Alternate path white Small topology bad Bad case for ghost flushing multi Models from the internet e Simulation Parameters Can take the values sim1 No Random no jitter sim2 Random No jitter sim3 No Random Jitter sim4 Random Jitter sim2SH Random no jitter Split horizon activated sim4SH Random Jitter Split horizon activated e Sizes List of naturals with the sizes of the models ie 5 45 6 7 8 9 3 Execution example sh multiSim sh 0 100 NORMAL GF GB D20 GB D30 GB D50 clique sim2 4 5 6 7 8 9 10 11 4 2 Simulation Environment 27 Initial Iteration final iteration BGP versions to be simulated topology Simulation Paramters Sizes Time date machine tmp gt SSFNet Simulator Part gt ask choice depending on machine p hie DML fich Generaion B c et Va gt Concurrent V V topology file generation Load control routines Bath internet models US tier DML fich adapation Concurrent execution of simulation Relevant Data extraction Final Results gt Number of concurrent simulations specified by load control routines genCliqueTop tcl genPath tcl genWhite tcl topology Depending on genBad tcl account Internet Models V adaptDml tcl V
33. and internal routing protocols IGP for the routers inside de ASs The most used external routing protocol has been BGP and BGP4 is its current standard version We will proceed to study the basis of this protocol And thus of external routing protocols in the next chapter We can see now the advantages of the new distribution e Failure control and administration became easier Each AS can deal with its own problems without affecting the rest of the network 2 2 BGP4 Protocol Description 5 Border R Figure 2 3 New picture of the AS divided Internet e Each network can be owned by different companies so internally to their AS they can have their own protocols and policies The only remaining standard is the external routing protocol e General software updates of the routers can be done AS by AS making changes and evolution on the internet easier and thus cheaper 2 2 BGP4 Protocol Description BGP4 is the standard version of the most used external routing protocol used on the internet The first version was published in June 1989 as RFC 1105 The last version deployed is BGP4 defined in RFC 1771 28 and is the one studied in the thesis As shown along this chapter BGP4 has some features like loop detection path vector CIDR or propagation policies that allows it to work proper
34. can replace delta h Kh and get t t A 3 5 oe Kh h eal and then pm dq 3 6 Pdown K 1 s Other situations This rule reguires all advertisements to be delayed this means a negative impact on other situations like start up shorter path or fail over The interest of this rule is double to clearly understand the convergence properties of the BGP and to see the possible interaction of Ghost Flushing and some path oscillation control technigues 3 4 Other Solutions 3 4 1 Reset Rules The reset rules 15 extend the ghost buster rule by applying the delta timer from any kind of update advertisement or withdrawal It doesn t have any applied interest in the real world so it wasn t further analyzed 3 4 2 Other Approaches to the same problem Reverse Poisoning IGRP It sa non scalable situation it first cleans al the routes and then it begins again It is suitable for internal routing but definitely not for external Route Consistency Assertions to truly identify the ghost information requires extra computational time that would harm the general performance of the router Also show heavy problems over AS partitioning 13 Active loop detection on sender 15 Reduces the convergence time but as simulations will show ghost flushing behaves better Proposal on 12 means adding extra information to the withdrawal messages And the message sys tem was something we didn t want to modify 20 Chapter 3 Ghost Flushing and
35. de AS est en la lista y en caso positivo descartar tal ruta En caso negativo puede aceptar la ruta y retransmitirla anadiendo su n mero de AS al principio del camino de Ass Esta t cnica tambi n tiene inconvenientes El principal es que la lista de ASs atravesadas por una ruta es almacenada en la memoria de los routers y enviada en los mensajes de actualizaci n Considerando la cantidad de redes que existen esto puede significar un gran coste en memoria y sobrecarga de mensajes Algunos estudios 20 afirman que con BGP3 para 100 000 redes una longitud media por camino de 20 ASs y unas 3 000 ASs el coste en ancho de banda de transmitir una tabla completa de encaminado ser a de unos 500 000 bytes Si miramos a como las rutas son almacenadas en los routers esta cifra es sobradamente excedida f cilmente Sin embargo este problema ser a solucionado aplicado CIDR y agregaci n de rutas en BGP4 2 1 2 Atributos de ruta Los mensajes de actualizaci n portan la informaci n encaminamiento como atributos Estos atributos pueden ser clasificados seg n dos criterios Transitivos no transitivos si un atributo debe ser incluido en caso de que un ruta sea retransmitida y obligatorios opcionales Obligatorios son aquellos que todos los routers deben entender y obligatorios son aquellos implementados en versiones del protocolo que no son est ndar Los principales atributos obligatorios Camino de ASs Lista de ASs atravesadas por la ruta Or
36. decision process to implement the Ghost Flushing rule So here we did the same the strike target was the decision process bgp_process at bgp_route c bap processo HL bgp_route c Look in al the RIB_INs as N E for the best route for this NLRI OR route new route T else V If old rotel null and new routel null and if old route null set it as not selected old routel new route and if new route nullset it as selected new route is longer than old route GHOST FLUSHING WITHDRAWALS GHOST CODE bgp adj out set For each neighboring peer if new routet null Send Update Update gt else Send Withdrawal For each neighborin nee Clean previous messages Creates Update Puts thread into FIFO WITHDRAWAL SENDING ZEBRA UPDATE Update Kernel Messages to Zebra Figure 6 10 Inserting the Ghost Flushing code in the decission process Here we can see the C code that does the work as it is inserted inside the bgp_process function decisions process in bgp route c GHOSTMODIF We put it here the other one is withdrawal anyway Conditions GF activated we substitue a route the new one is longer and MRAI is not expired mi thread peer gt t routeadv if bgp gt ghost flushing amp amp old select amp amp new select amp amp old select new select amp amp new select gt attr gt aspath gt count
37. e 5 Nodes Edown with ghost flushing 1 3 seconds Edown without ghost flushing 50 60 seconds e 7 Nodes Edown with ghost flushing 2 4 seconds Edown without ghost flushing 110 120 seconds Looking at the logs we see again Both with and without the ghost flushing rule the convergence behavior described in the simulation chapter Bigger tests with different topologies could be done but more nodes computers would be needed 6 6 Conclusions 6 6 1 General Conclusions In the first place we could get the odd convergence behavior out of the simulation environment and reproduce it in the real world This shows that the problem studied during this project exists out of the theory About the capacity of GNU Zebra as a routing software our experience working with the software From the inside to the outside shows this software as a reliable inexpensive option to set routers running over conventional hardware Also this opinion is supported by articles from the routing community 34 and our experience with the Zebra mailing list 4 showing that the number of users of this software is big and growing Also the possibility to customize this software gives extra points to it About the ghost flushing rule it shows the same properties observed on the simulation We can state that our customized version of GNU Zebra implements the ghost flushing rule as defined on 13 The results show that it works as expected and with
38. eo w S e A BGP4 E GhostFlushing GhostBuster 20 zs 2 GhostBuster 30 gt GhostBuster 50 m a eo Seconds N S S a eo 100 4 50 4 5 6 7 8 9 1011 12 13 14 15 16 17 18 19 20 Size Figure 5 44 Clique Fail Down time No Jitter Split horizon 66 Chapter 5 BGP4 Cases Simulation Clique Initial Fail Down Num Messages 5000 4 BGP4 GhostFlushing GhostBuster 20 2 GhostBuster 30 3000 4 gt GhostBuster 50 Messages gt S S S 4567 8 9 1011 12 13 14 15 16 17 18 19 20 Size Figure 5 45 Clique Fail Down messages No Jitter Split horizon Set Up We get exactly the same results as in the case that we didn t activate the Split Horizon Fail Down About Edown Something interesting happens In a 4 nodes clique activating Split horizon and using ghost flushing is the same Let s explain this Imagine we have 4 nodes node number 4 goes down we have 3 left Na Node 2 and Na chooses N as next hop Nj chooses Na as next hop That means a withdrawal from Na and N3 to Nj and from N to Na That triggers that e N Has no more routes e N Has only N3 as next hop that means a withdrawal to N3 e N3 Has only Na as next hop that means a withdrawal to N So there is a general withdrawal because of the split horizon However from the 5 nodes clique things come to normal Ghost information reappea
39. found four main tasks Creation and initialization of the Delta timer associated to a route when it is received by the protocol modification of the sending method so we respect the delta handling of the event delta timer expiration Also it was needed to implement timers messages and other classes needed to make all this work For the creation and initialization of the delta timer associated to a route It was thought that the best place to implement it was inside the code of the AdjRIBIn class We modified the code of that class so every time a route was added to an AdjRIBIn a Delta Timer was created and associated to the route It works the same way if the route was eliminated from the AdjRIBIn the timer associated was eliminated About the sending method We altered the method try send update so if the delta timer for this route is not expired yet it won t be sent or put inside the waiting lists The part that manages the expiration of the delta timer will do it later Handling the expiration of the delta timer for this we created a new event inside the BGP4 The idea is quite simple we added an entry inside the method handle event that manages every route that has its delta timer expired If the route is in the LocRIB it uses the try send update method but with the info about the route whose delta timer just expired It tries to send it according to the classical limitations of BGP4 MRAI etc like delta timer never existed Messages Ti
40. horizon ke 5 45 Clique Fail Down messages No Jitter Split horizon 2 o 5 46 AltPath Set Up time No Jitter Split horizon e 5 47 AltPath Set Up Messages No Jitter Split horizon se 5 48 AltPath Fail Over time No Jitter Split horizon se 5 49 AltPath Fail Over messages No Jitter Split horizon e 5 50 Multi Set Up time no Jitter Split horizon ooo 5 51 Multi Set Up Messages no Jitter Split horizon se 5 52 Multi Fail time no Jitter Split horizon 5 53 Multi Fail messages no Jitter Split horizon sk 5 54 Comparing between having or not Split Horizon lt se 5 55 Clique Set Up time Jitter Split horizon kse 5 56 Clique Set Up Messages no Jitter Split horizon e 5 57 Clique Fail Down time Jitter Split horizon a a 5 58 Clique Fail Down messages Jitter Split horizon nn 5 59 AltPath Set Up time Jitter Split horizon sk 5 60 AltPath Set Up Messages no Jitter Split horizon se 5 61 AltPath Fail Over time Jitter Split horizon sooo 5 62 AltPath Fail Over messages Jitter Split horizon se 5 63 Multi Set Up time Jitter Split horizon e 5 64 Multi Set Up Messages Jitter Split horizon 2 2 2 2 nn nn nn 5 65 Multi Fail time Jitter Split horizon 5 66 Multi Fail messages Jitter Split horizon e 5 67 Multi Pommin th n ad BRAS BAD t
41. identifies which machine has it been executed on and starts bgpd with parameters f and the configuration file corresponding to this machine Para sh kills all the instances of bgpd running 6 5 3 Tests and results During the testing we intended two objectives e Test if the ghost flushing implementation done on Zebra behave as it was supposed to Correctness e Do small performance tests in clique topologies to see the impact of the ghost flushing rule in a real routing software 92 Chapter 6 Applying the Ghost Flushing Rule to Zebra Routing Software Correctness of the Implementation To do this we set up a 5 nodes clique where number 5 was the only one advertising an IP range We activate the logging option for the ghost flushing and message sending We start up all the nodes wait until the set up process finishes and then from the switch management tool we virtual unplugged the bgp network interface from node 5 After this we checked the log files Checking the logs we try to find the log messages and the withdrawals proper of triggering the ghost flushing rule In the case the MRAI timer was expired the corresponding withdrawal message had to be sent After some tests the correctness of the implementation was accepted System Performance In this situation we tested two scenarios 5 nodes and 7 nodes clique We repeated the tests in the previous section and then measured how long did it take until the network stabilized
42. machine tmp A F 3 Figure 4 3 Simulation schema It will simulate cliques of sizes 4 to 11 with the traditional BGP4 with ghost flushing with ghost buster delta 20 with ghost buster delta 30 with ghost buster delta 50 repeating each case 100 times 4 Space used e tmp gonrod 3 simulation parameters name topology files e tmp gonrod 3 simulation parameters name DML files e tmp gonrod 3 simulation parameters name simulation log files e tmp simulation parameters name extracted results machine sh 28 Chapter 4 BGP4 Simulation Environment 1 Function Looks up which machine is running this process 2 Parameters None 3 Execution example sh machine sh 4 Space used None 5 Response Machine host name numproc sh 1 Function Depending on the date and time it calculates how many simulations there should be at the same time 2 Parameters None 3 Execution example sh numproc sh 4 Space used None 5 Response Number between 1 and 4 In office hours 8 20h 2 rest of the day and weekends Sat Sun 4 genCliqueTop tcl 1 Function Creation of the topology file of a clique structure with the parameters specified on the command line 2 Parameters Clique size Value Natural number Dead node Can take values os Between 0 Size If 0 no node dies Time of death Simulation time Seconds in which the dead node should die Ghost Flushing True false
43. o el supernetting esta es la gran diferencia que existe entre ambas versiones BGP4 es capaz de agregar rutas que comparten partes de su direcci n de red Desde la implementaci n de BGP4 en Internet los problemas antes descritos anteriormente fueron aliviados Adem s como BGP4 sabe a trav s de que ASs una ruta pasa puede calcular si merece la pena agregar destinos bajo una red mayor De hecho existe un atributo definido en el RFC 1771 28 para indicar si una ruta puede ser agregada o no 2 1 5 BGP Interno IBGP Aunque este trabajo trata sobre temas relacionados con la parte externa the BGP4 no podemos seguir sin mencionar su papel como protocolo interno BGP4 puede ser usado entre routers dentro de una AS sustituyendo otros protocolos como OSPF o RIP Incluso aunque BGP4 y estos protocolos pueden coexistir La idea inicial es establecer un red BGP totalmente interconectada entre los routers del borde de la AS y los routers internos De esta manera las rutas son diseminadas por toda la AS aunque el sistema parece del todo ineficiente Otras opciones han sido propuestas algunos ejemplos son las t cnicas de Route Reflector 30 o Confederaciones Tambi n aplicado a BGP externo 25 Intentan reducir el n mero de sesiones establecidas entre routers En Route Reflector 30 el enfoque se fundamenta en la idea de que podemos dividir una AS en sectores e internamente a los sectores hay una red BGP totalmente interconectada Las rutas so
44. on the RFC 1771 to specify if a route can be aggregated or not 2 2 5 Internal BGP IBGP Although this work has to do with issues related to the external BGP4 we cannot keep going without mentioning the internal part of the protocol BGP4 can also be used between routers inside the AS instead of using other possibilities like OSPF or RIP Even if BGP4 and this protocols can co exist The initial idea was to establish a full meshed BGP4 network between the routers inside the AS and the border routers This way the routes are disseminated all over the AS but in a quite inefficient way So other options were proposed some examples are the Router Reflector 30 or the Confederations Also applied to external BGP 25 approaches They try to reduce the number of BGP sessions established between routers The Route Reflector 30 approach is based on the idea that we can divide an AS in clusters internally the clusters are full meshed The routes are provided by a route reflector to the whole cluster This route reflector is just another BGP4 router that is connected to the border routers Can be a border router itself and other route reflectors Other possibility are the Confederations 25 The idea is to group various ASs in a virtual bigger one or to divide a big AS in smaller virtual ones The external or the Internal BGP approach This way we avoid the connections derived from a full meshed model ASs 10 Chapter 2 BGP4 Routing Protocol
45. para alcanzar solo una serie de destinos 104 Cap tulo 2 Protocolo de encaminamiento BGP4 y su entorno Mensaje de Actualizaci n handle event Eliminar rutas retiradas del Mensaje AdjRIBIn A adir Reemplazar rutas enel AdjRIBIn Ejectuar proceso de decisi n Si es necesario Rttas nuevas eliminadas y reemplazadas decission_process_2 Calcula grado preferencia de las rutas Cambios en LocRIB 1 Si una ruta alterada no es v lida encontrar una nueva para sustituirla Si una ruta alterada is v lida sustituir toda referencia a su NLRI en el LocRIB con ella decission process 3 Indicar que todas las rutas que han sido eliminadas del LocRIB para ser retiradas Si no hay impl cita Indicar todas las nuevas rutas del LocRIB para ser enviadas exteral update con todos los anuncios actualizaciones Anuncios y retiradas external update Crear un nuevo UpdateMessage Poner retiradas y la primera ruta a enviar en l try send update it Par cada ruta gue guede crear un nuevo UpdateMessage y try send update it UpdateMessage Si MRAI no ha expirado Si MRAI expirado try send update Elminar withdrawals sobre routas que va a ser enviadas Implicit Send el mensaje si gueda algo Elimina withdrawals sobre ruts a enviar Imp cito Actualizar lista de esp
46. redes crecieron m s y m s hasta el momento en el que nuevos problemas comenzaron a aparecer Configurar manualmente todos los routers para que supieran alcanzar todas las redes se convirti en algo demasiado complicado La soluci n escribir nuevos protocolos Protocolos de enrutado para que estos routers pudieran comunicarse e intercambiar informaci n de conectividad de manera autom tica Sin embargo el tamano de Internet Todas las redes conectadas no par de crecer llegando el mo mento en el que aquellos protocolos de encaminado ya no fueron adecuados para las nuevas circunstancias Como soluci n apareci una nueva idea los Sistemas Aut nomos AS en ingl s Internet fue dividida en Sistemas Aut nomos AS y dos tipos de protocolos fueron escritos externos e internos Los proto colos de encaminamiento internos eran utilizados para intercambiar rutas dentro de los ASs y consist an en versiones de los protocolos de enrutado utilizados anteriormente Los protocolos exteriores ten an una misi n diferente intercambiar rutas entre los routers que estaban en los bordes de ASs diferentes Eran los 80 y el momento en el que Border Gateway Protocol BGP fue inventado el protocolo que se convertir a en un est ndar en Internet De nuevo tras algun tiempo nuevos problemas aparecieron Como consecuencia nuevas versiones de BGP fueron desarrolladas A principios de los 90 la ultima versi n BGP4 fue publica e implantada en Internet
47. s BGP4 code structure The behavior of the protocol is implemented in the BGPSession class that means that for the Ghost Flushing rule all the modifications needed were made over this class So now we are going to show the structure of this class 4 3 2 BGPSession Class This class implements the core of the BGP4 so first we are going to list the most relevant methods Explaining their function and after we ll show the structure of the most important ones concerning our modifications In this chapter we are doing a simplified schema of the code We have eliminated some parts Not relevant to the modifications to make easier the understanding of the code Methods void config com renesys raceway DML Configuration cfg Sets configurable values for BGP Here we can add the code needed for the new configuration options related to the GhostFlushing Buste rules void decision process 1 java util ArrayList infolist Runs Phase 1 of the Decision Process which is responsible for calculating the degree of preference of newly added or updated routes 34 Chapter 4 BGP4 Simulation Environment java util ArrayList decision_process_2 java util ArrayList changedroutes boolean dampReuse Runs Phase 2 of the Decision Process which is responsible for selecting which routes from Adj RIBs In should be installed in Loc RIB void decision_process_3 java util ArrayList locribchanges Runs Phase 3 of the Decision Pro cess which is responsibl
48. the actual structure of the internet But then a new strategy of provider addressing was imposed From the top levels the network providers owned a range of IPs and their customers would have to be in the IP range of the providers This means a great advantage to routing Let s compare the old scenario with the new one In the old system we have two destinations with IP range IP1 and IP2 They both connect to the internet through the same provider but their IP ranges didn t have to have anything in common Than meant two entries in a routing table to locate them But in the new system if both are under the IP range of the provider a router only has to learn how to reach the provider Then the provider s routers will redirect the connections to the proper network Considering that a provider has many more than two customers we can see the positive impact in the routing tables all over the Internet What has this to do with BGP4 BGP3 the previous version of BGP4 didn t support the CIDR or the supernetting this is probably the most noticeable difference between both versions BGP4 has the capacity of aggregating routes that share parts of their addresses Since the deployment of BGP4 on the Internet both problems were greatly relieved Also since BGP4 knows which ASs the paths go by it can do special calculations to consider if it s worth to aggregate destinations under a bigger network Actually there is an attribute defined
49. the customer provider or peering relationships of Autonomous Systems extracted from the BGP routing tables They were built following this process 26 1 Generate a topology from a BGP table dump such as RouteViews 2 Prune a given percent of links from the topology and take the largest remaining connected com ponent 3 Merge nodes together choosing nodes with smallest degrees first until topology is reduced to 1000 nodes 50 Chapter 5 BGP4 Cases Simulation 4 Don t merge if nodes share any peers and if degree of both nodes is greater than 2 This models are extremely interesting since they show the effect that the deployment of Ghost Flushing or Ghost Buster techniques would have over typical internet provider structures We had network models of sizes until more than 800 nodes but they turn out too heavy to be simulated so we stopped at the size of 409 nodes To create images showing the structure of this models we used the RaceWay Viewer class included in the SSFNet package In this section we include fig E 1 showing the structure of the smallest net In the appendix images of all the networks can be found Size 29 110 208 and 409 nodes Convergence Times studied Stabilization and Eup Interest Practical Figure 5 5 29 nodes structure Image Generated by RaceWay network visualization tool 5 2 Simulation Results Split horizon disabled No jitter The results on this section is divided depending o
50. the tutorial We reinstalled the software and tested the example without the BGP patch and the problem disappeared Since everything else worked finely Seeemed so and for the BGP simulations we didn t need the elements we applied again the patch Painfully again and started the testing part To create the simulation scenarios And trying to look into the future some small programs were developed in tcl to create clique scenarios of different sizes They intended to reduce the time of simu lations set up Even if this simulator wasn t used in the end this software was revamped to create the configuration files for the GNU Zebra bgpd so it will be described in further chapters Testing examples The first test that we decided to do was to simulate the five node clique situation on fig 3 1 and evaluate how close to the reality were the results After setting up the network scenario starting the simulation and getting the log files of each node we first noticed that against what 13 says the situation converged in 1 or 2 seconds Looking deeper into the code a series of strange behavior for the BGP4 were found The most disturbing one was that it didn t respect the MRAI limitation imposed by the BGPs RFC 28 We got in contact with the developers of BGP and they sent us a patch for the module After recompiling all the software together the simulations started again Still the simulations showed that the simulated case fig 3 1 converg
51. this possible After some time the interconnected network became bigger and another problem appeared it was too complicated to manually configure all the routers so they knew how to reach all the networks As a consequence some routing protocols were written for the routers to talk between them and exchange reachability information about the networks the knew However the size of the Internet All these networks connected didn t stop growing so the time came when this routing protocols were not suitable for the Internet anymore To solve this a new idea appeared the Autonomous System They divided the Internet in Autonomous Systems AS and two kinds of new routing protocols were written external and internal routing protocols The internal routing protocols were used to exchange routing information inside the ASs and they were like the old ones used before The external routing protocols had a different mission to exchange routing information between the routers on the borders of the ASs It was the 80s and the moment when the Border Gateway Protocol BGP was born BGP is the external routing protocol that became an standard in the Internet After some time new problems came up so new versions of BGP were developed In the early 90s the last version BGP4 was released and established on the Internet BGP4 has become the so called glue that holds the Internet together thus any modification that could improve its behavior will have a p
52. try send update 1 Function Tries to send a message If it s not possible protocol limitation it takes the proper actions 2 When when ever a message is needed to be sent 3 Data Input UpdateMessage to be sent the address of the advertisers of the route and to which peer we want to send the message 4 PseudoCode msg UpdateMessage to sent Senders Addresses of the original advertisers of each route on the message Peer peer to whom we want to send the message Code initialising Timers when this method is run for the first time if MRAI not expired yet then Eliminate withdrawals about nlri that is referenced by the routes on the updatemessage Implicit withdrawal Update Waiting lists If a route is going to be withdrawn eliminate it from the waiting lists Put the routes from the message in the waiting list MRAI is not expired yet Eliminate those routes from the UpdateMessage Send UpdateMessage Return end if Eliminate withdrawals about nlri that is refered by the routes on the updatemessage Implicit withdrawal Update Waiting lists If a route is going to be withdrawn eliminate it from the waiting lists Send UpdateMessage 36 Chapter 4 BGP4 Simulation Environment 4 3 3 The Update Process After showing the internals of the main methods that take part in the BGP protocol behavior we are going to try to show how they work together from the moment and Update Message is received to the moment new rout
53. un vecino al que bgp est conectado usamos la clase ListBuster Route Consiste en una tabla hash indexada por los NLRIs de las rutas y tiene varios m todos para hacernos la vida un poco m s f cil 4 3 3 Como funciona todo este lio Vamos a intentar mostrar la vida de una ruta desde que es recibida hasta que es es enviada a otros vecinos El nuevo ciclo de vida de una ruta Considerando la complejidad de la modificaci n solamente incluimos lo que es diferente de la regla ghost flushing Ruta llega y el protocolo intentan enviarla pero el temporizador delta no ha expirado Este esquema puede ser encontrado en fig 4 2 Temporizador Delta Expira Suponemos que la ruta est en el LocRIB Por lo tanto queremos enviarla Este esquema puede ser encontrado en fig 4 3 120 Cap tulo 4 Entorno de Simulaci n BGP4 UpdateMessage PEER Class Poner Ruta handle event message Crear enfrada nueva Esto cred el temporizados delta asopiado handle update Nuevas Rutas decission process 1 ListBusterRoute Nuevas Reemplazadas y eliminadas rutas decission process 2 cambios en LocRIB decission process 3 Actualizaciones anuncios y retiradas external update UpdateMessage Si una ruta no tiene el temporizador delta expirado es sacada de la lista de espera pero no enviada Figura 4 2 Un ruta llega y el protocolo intenta e
54. una serie de conclusiones generales Parece the depen diendo del punto de vista la regla ghost buster se comporta mejor o peor Si miramos al tiempo que cuesta que toda la red se estabilice ghost buster se comporta bastante bien Sin embargo si miramos al aspecto m s local a peguenas partes de red Modelos menores la regla ghost buster se comporta peor No simulamos ning n caso de como se comportaban los modelos de 400 nodos si reducimos el n mero de nodos con ghost buster en a red Es simplemente un tema de tiempo Simular una vez un escenario de 400 nodos cuesta casi una hora necesitar amos ejecutar 400 simulaciones m s de una vez para conseguir resultados estables y eso cuesta mucho tiempo Algo importante sobre esta regla es que necesita mucha CPU y memoria Cualquier camino recibido necesita un temporizador que ocupa memoria y produce un evento cuando expira Aunque no sea necesario Esto puede tener un impacto negativo en el rendimiento del router Mirando a todas estas conclusiones vemos ventajas y desventajas Vemos un mal rendimiento en escenarios medianos y pequenos escenarios menos de 200 nodos para la situaci n de set up y fail down Esto junto con la complicada y pesada implementaci n nos lleva a tomar la decisi n de no implementar esta regla 124 Cap tulo 5 Simulaci n de Casos de BGP4 Cap tulo 6 Aplicando la regla Ghost Flushing a GNU Zebra Despu s del an lisis de la simulaci n de las diferentes modif
55. we arrive to the network where the destination host is connected and finally reachable This is a summary of the routing strategy used on the Internet hop by hop routing Network C Router Router Origin Host ae D Destination Host Network B LJ Network Y Router E Router 111 E Router 111 Network A Network Z Figure 2 1 Example of hop by hop routing between two hosts By doing this we simplify the design and configuration of networks For one network to work and be able to connect to the rest of the world two thing are needed Firstly a properly configured router connecting the network to other s network s and secondly all the hosts having the router as their gateway 2 1 2 Mapping the Internet The next issue is the configuration of the routers Let s imagine a network that is connected to three other ones by three different routers If we want to connect to a host on a remote network through which one should the connection be established And even more each router is connected to our network and three other ones but originally they don t know what are those networks connected to At the beginning when the Internet was really small this was configured statically System administrators would manually configure each router with the list the networks it could reach by contacting other routers from the networks it had direct connection to
56. were too small for most companies and there were only 256 A class networks so a real danger of address exhaustion appeared Also the number of networks connected increased constantly making the routing tables bigger inside de routers This had a negative impact on memory usage and processing time Storing and searching in 2 2 BGP4 Protocol Description 9 Class Network Bits Host Bits Hosts per network A 8 24 16 777 214 B 16 16 65 534 C 24 8 254 Figure 2 5 IP classes distribution bigger tables This could affect performance of routers and response time to failure This appeared as another risk to the integrity of the internet Classless Addressing Route Aggregation and BGP4 as a Interdomain Routing protocol Classless addresses have a characteristic they are composed by the whole IP number and a network mask The network mask indicates which bits from the IP address belong to the network address and which ones belong to the host address Using this we can divide A networks in smaller ones and group contiguous C networks to make bigger ones Also you can define networks adjusting the size to the demandes of the customers who contract the IP ranges This way the IPv4 address problem was patched until the coming of the long delayed IPv6 Exchanging routing information between different domains that are not class abiding is the so called CIDR Until 1992 there was no relationship between the IP numbering and
57. y redes est n f sicamente conectadas El otro factor son las pol ticas de intercambio establecidas entre las ASs debido a relaciones comerciales o econ micas entre las instituciones que poseen las ASs Las pol ticas de intercambio se manifiestan en los filtros que alteran el intercambio de rutas entre routers de borde Le Dos ASs han contratado acceso a internet a trav s del mismo proveedor pero adem s est n conectadas entre s fig 2 7 Una de ellas podr a querer acceder a la otra pero no permitir que la otra utilice su conexi n a Internet Este un ejemplo de causas comerciales 2 2 1 Clasificaci n de Relaciones y Disposici n en Internet Exportando a un proveedor Intercambiando informaci n con un proveedor una AS puede exportar sus rutas y las rutas de sus clientes pero normalmente no exporta las de su proveedor o las de sus iguales peers Exportando a un cliente Intercambiado informaci n de ruta con un cliente una AS puede exportar sus rutas las de sus clientes sus iguales y su proveedor Exportando a un igual peer Intercambiando con un igual una AS puede exportar sus rutas y las de sus clientes aunque usualmente no exporta las de sus iguales o proveedores Exportando a un Hermano Intercambiando con un hermano una AS puede exportar sus rutas las de sus proveedores clientes e iguales B sicamente Internet es una conjunto de nodos estructurado en forma de rbol pir mide pero con conexiones entre nodos en
58. 0 10000 GhostBuster 50 5000 os Swe LP 0095050 Size Figure 5 62 AltPath Fail Over messages Jitter Split horizon Fail Over In this case we see that applying both rules to the ghost Buster rule has a negative effect on its Egown Ghost flushing keeps been the best option in this scenario Later on we will do a general comparison between all the versions of the protocols 5 5 Simulation Results Split horizon Enabled Jitter Activated 73 5 5 3 Multi Topology Multi Set Up Time 4500 4000 3500 3000 o 2 2500 K 3 2000 1500 BGP4 GhostFlushing GhostBuster 20 gt GhostBuster 30 GhostBuster 50 1000 500 Nodes Figure 5 63 Multi Set Up time Jitter Split horizon Multi Set Up Messages 3500000 3000000 2500000 2000000 Ey 8 1500000 BGP4 GhostFlushing GhostBuster 20 GhostBuster 30 GhostBuster 50 1000000 500000 0 29 110 208 409 Nodes Figure 5 64 Multi Set Up Messages Jitter Split horizon Multi Fail Down Time 1600 1400 1200 1000 800 Seconds 600 Size BGP4 GhostFlushing GhostBuster 20 GhostBuster 30 GhostBuster 50 Figure 5 65 Multi Fail time Jitter Split horizon 74 Chapter 5 BGP4 Cases Simulation Multi Fail Down Messages 140000 120000 100000 BGP4 80000 5 GhostFlushing
59. 00 31 P Traina Experience with the bgp 4 protocol RFC 1773 Internet Engineering Task Force March 1995 32 J Y V Fuller T Li Supernetting an address assignment and aggregation strategy RFC 1338 Internet Engineering Task Force June 1992 33 A R V Gill D Walton Border gateway protocol bgp persistent route oscillation condition RFC 3345 Internet Engineering Task Force August 2002 34 I van Beijnum Running zebra on a unix machine O REILLY ONLamp com 7 2002 http www onlamp com pub a onlamp 2002 11 07 zebra html 35 E Y Rekhter T Li A border gateway protocol 4 bgp 4 RFC 1654 Internet Engineering Task Force July 1994 36 yon uriarte Zebra hacking how to Technical report http www quagga net zhh html 37 R Zakon Hobbes internet timeline RFC 2235 Internet Engineering Task Force November 1997
60. 07 21 2004 07 21 2004 07 21 2004 07 21 2004 07 21 2004 07 21 23 23 23 23 23 23 path 3 6 2004 07 21 2004 07 21 23 23 path 4 5 2004 07 21 2004 07 21 2004 07 21 2004 07 21 2004 07 21 2004 07 21 2004 07 21 2004 07 21 23 23 23 23 23 23 23 23 path 5 2 2004 07 21 23 11 11 11 11 11 11 11 11 12 7 12 12 12 12 12 12 12 7 12 20 20 39 42 42 47 12 12 67 46 46 47 47 47 47 47 48 12 12 12 12 12 12 12 12 12 12 12 12 12 48 48 49 49 ST 51 52 52 09 09 09 09 12 12 12 12 12 16 17 18 18 42 46 417 12 48 BGP BGP BGP BGP BGP BGP BGP BGP BGP BGP BGP BGP BGP BGP BGP BGP BGP BGP BGP BGP BGP BGP BGP BGP BGP BGP BGP BGP BGP BGP BGP BGP BGP BGP BGP 192 192 192 192 192 192 192 192 192 192 192 192 192 192 192 192 192 192 192 192 192 192 192 192 192 192 192 192 192 192 192 192 192 192 192 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 o W o NN O COCCO Co o o DN PP 0 0 0 0 N O CO O 0 o W W N 0 N O COCCO oO oooo 0 0 5 W W W NM N N Y c
61. 2 When an update message arrives 3 Data Input Update message that just arrived 4 PseudoCode peer peer from which we received the message rcvd rtes routes extracted from the UpdateMessage rcvd wds nlris to be withdrawn extracted from the UpdateMessage Boolean rundp false indicates if decision process must be run Check feasibility of rcvd rtes Check AS path loops in rcvd rtes Changedinfo gt array of routes info Stores withdrawn and replaced routes newinfo list gt array of routes info Stores new routes For each nlri in rcvd wds loop Create routeinfo with withdrawn nlri Mark routeinfo as not feasible Put routeinfo in changedinfo If there is a route about nlri in the RIBIn of peer then Remove route from RIBIn 4 3 Analysis of SSFNet s BGP4 Implementation 35 Mark removed route as not feasible ChangedInfo add removed route Rundp true Remove this route from all the waiting lists to be sent because of mrai limitation associated with al peers End if End loop For each route in rcvd rtes loop Rundp true Put route in RIBIn Oldinfo replaced route if any from RIBIn Newinfo_list add route If oldinfo null then Mark oldinfo as not feasible implicitly withdrawn Mark newinfo as implicit withdrawal Changedinfo add oldinfo End if End loop If rundp then Decision process 1 newinfo list Changes in loc RIB Decision process 2 changedinfo Decision process 3 Changes in loc RIB End if
62. 2 Structure and method of this work BGPA is a critical protocol on the internet before applying any modifications to the standard deep work has to be done A faulty modification can lead to an unaffordable mass failure This work is the 1 2 Chapter 1 Introduction study analysis of some proposals to improve this protocol As a consequence it was required a proper work structure for the results to be as coherent and correct as possible Every step is taken after the previous one validates the work done The steps followed were 1 Basic Protocol and environment study 2 Problem study and analysis of the theory behind the solutions 3 Simulation and comparison of the original and modified versions of the protocol 4 Implementation of the approved solutions on a real routing software 1 3 Chapters Overview This is the organization of this thesis Chapter 2 tries to show a picture of how BGP4 works It summarizes all the aspects about routing and BGP4 Defined in RFC 1771 28 that may be needed to understand the work on this thesis Chapter 3 contains the definition of the convergence problem studied in this thesis The rules Ghost Flushing and Ghost Buster defined in Bremler Barr et al 13 are here shown and analyzed Chapter 4 shows how the simulation environment was set It includes the analysis of the candidate network simulators for this task Facts setting up and validation a small schema of the internal structure of t
63. 2004 228 CIV EXAMENSARBETE Convergence Time Redution in the BGP4 Routing Protocol Using the Ghost Flushing Technique and Other Proposals Gonzalo P Rodrigo Alvarez MASTER OF SCIENCE PROGRAMME Department of Computer Science and Electrical Engineering Division of Computer Science 2004 228 CIV ISSN 1402 1617 ISRN LTU EX 04 228 SE Convergence Time Reduction in the BGP4 Routing Protocol Using the Ghost Flushing Technique and Other Proposals Gonzalo P Rodrigo lvarez Lule July 2004 Soy un ciudadano del mundo entero I am a citizen of the whole world Erasmo de Rotterdam humanista holand s del siglo XV Erasmo of Rotterdam Dutch humanist from the 15 Century Abstract BGP4 Border Gateway Protocol is the language that makes possible to keep up to date the road maps in the internet This routing protocol is the one used by the big networks to exchange routing information Thus its performance is critical for the internet In some situations the behavior of this protocol is not the desired one This thesis Or project intends to analyze one of this problems together with some proposed solutions This analysis will involve a review of the theory behind the proposals and a later simulation to test the performance of them After the analysis is done the proposals considered as useful will be implemented over an open source free routing software GNU Zebra This work began as
64. 4 the same situation as in fig 3 1 is shown the five nodes clique Until t 2 every nodes does the same as with the traditional BGP But then all the nodes But node 1 updates their path to go to 0 for a longer one but they cannot send a new update because in t 1 they already sent one and MRAI is not expired yet So the ghost flushing rule comes into action and a general withdrawal is sent because ghost information has been detected As a consequence in t 3 all the nodes empty their routing tables and they stop taking any action Just in 3 seconds Looking to this example we identify two phases Ghost Information spread is born because of the first implicit withdrawal But this longer routers trigger the ghost flushing rule in all the nodes in the example it would happen between t 1 and t 2 General Flushing because of the ghost information detected All nodes clean the ghost information they hold in their tables Happens in t 3 ASpath 0 ASpath 0 ASpath 20 ASpath 10 ASpath ASpath 310 10 4 2 20 10 2 20 120 i 120 210 W a 310 410 W 30 Y 14 40 30 64 40 31065 E A IM Io ASpath 10 e E A ASpath 0 ASpath 0 pat ASpath 10 ASpath 120 ASpath 120 b t 1 c t 2 ASpath ASpath w Oi 4 ASpath ASpath d t 3 Figure 3 4 Step by step Ghost Flushing Rule in action 3 2 2 Convergence time In 13 there is a deep mathem
65. 5 1 2 Alternate Path AltPath n AT 513 White models o ina did ara oo Rea b 20 ed 48 bd Bad model 2a er RN ee 48 5 15 Multi Collection uy 4 25 e er 5 A ete e Me a e e eee N 49 5 2 Simulation Results Split horizon disabled No jitter s 50 5 2 1 Glique Topology an sae ee ck UM esee deque E ede we ee is 51 5 2 2 AltPath Topology xx 9c Re A eS 52 5 2 3 Multi Topology sa 727 2 52 Gore x RR a ep de Y 54 5 2 4 White Topology 32 00 er a baai E ES A E a ee d 55 5 2 9 Bad 388 2 2 AAA 57 5 3 Simulation Results Split horizon disabled Jitter Activated 58 53 1 Clique Topology 41 5153 cech etw A eo p RO ele ee EUN 58 5 32 AltPath Topology a oo se eR ee n one e em A A AAR Y 60 5 3 3 Multi Topology i 4 4 x 885 2 222 anne e ee m en 61 5 374 White Topology L 435a me dale ee obese o e y pr S ure ee 62 543 97 Bad Case tos oso E DE Oa ee d Aum wur PIT RR Y RIA d 63 5 8 6 Comparing between jitter enabled and disabled se 64 5 4 Simulation Results Split horizon Enabled No Jitter k 65 5431 1 Clique Topology v5 0 ach eum e A ERR eed ur RR 65 5 52 AltPath Topology B area eve oy ee a aa je RA AUR da 67 5 4 3 Multi Topology 2 un a ew an AJAT RS ee e 68 5 4 4 Comparing between having or not Split Horizon nennen 69 5 5 Simulation Results Split horizon Enabled Jitter Activated 70 5 54 Clique Topology x dou ese AES Deb E Retina ale a Boe 00 70 5 5 2 Al
66. 8 GhostBuster 20 A 600 GhostBuster 30 GhostBuster 50 400 4 200 4 29 110 208 409 Size Figure 5 52 Multi Fail time no Jitter Split horizon Multi Fail Down Messages 120000 100000 80000 nara GhostFlushing 60000 GhostBuster 20 GhostBuster 30 40000 gt GhostBuster 50 20000 messages 0 29 110 208 409 nodes Figure 5 53 Multi Fail messages no Jitter Split horizon Fail Down Looking at the results on the graph we want to highlight two noticeable facts About Edown we see a general better behavior of the rules against the traditional BGP Also we can remark that the combination of the split horizon with the ghost buster rules behaves better in the intermediate cases than the ghost flushing Still the difference is not that big Also the number of messages has that tendency but even bigger It looks like the split horizon boosts the fail over case Increasing the number of messages in the ghost flushing rule It looks like the conservative approach of the ghost buster reduces the number of messages 5 4 4 Comparing between having or not Split Horizon In the first place we notice a general improvement in all the rules Specially in the traditional BGP4 Still the other rules behave much better using the split horizon Gaining even a nice 3096 in the biggest topology 70 Chapter 5 BGP4 Cases Simulation
67. All routing information has to pass through the Zebra daemon Something really interesting about this approach is that there is no need for all the daemons to be in the same machine We can have a machine that makes the function of BGP speaker it would have bgpd 80 Chapter 6 Applying the Ghost Flushing Rule to Zebra Routing Software running But the Zebra daemon can be in a different machine which routing tables we want to be up to date Both daemons can connect remotely by sockets This can slow down the route spread but can divide the load derived from the different functions here shown For example we may want a machine to do the gateway function between our network and the internet So it would run the Zebra keeping its routing table in good state but leave the BGP transactions to other machine s Also we can have machines with different hardware settings more close to the function they have to do in our network 6 2 2 Zebra Code Structure r E ospfd Zebra a zebra vtysh Figure 6 2 Here we find the directory structure for the code of Zebra In fig 6 2 we can see the code tree in Zebra In bgpd ospfd ospf6d ripd and ripngd we can found all the code related to the daemons managing the respective routing protocol We will deeply analyze the bgpd later Something important for this work is that Zebra is completely written in C that s good and bad As an application with a big interaction with operating
68. At the begining at leat of its CEO Kunihiro Ishiguro 6 1 1 History From GNU Zebra page 4 The Zebra project began in 1996 The idea for Zebra originally came from Kunihiro Ishiguro who had been working at NIS an ISP joint venture between British Telecom and Marubeni Working for an ISP Ishiguro had realized a great need for a new type of quality routing software It was at this time that Ishiguro met Yoshinari Yoshikawa Yoshikawa shared Ishiguro s vision for a new routing engine and they decided to combine resources to create the world s first routing engine software based on the GNU General Public License This entity called the Zebra Project consists of the business expertise of IP Infusion combined with the technical skills of the world s top networking engineers and a commitment to offer top quality free software routing engine 77 78 Chapter 6 Applying the Ghost Flushing Rule to Zebra Routing Software Today Zebra is nearing completion and the release of version 1 0 The vision of a free routing software that can respond quickly to changes in technology and offer functionality that users require is now even more critical As internet use explodes no longer can one company or proprietary software provide all the answers In the case of Zebra the mailing list and comments of users and engineers have evolved the software into the form it has today 6 1 2 Features The strongest feature is it s modularity each routing proto
69. BGP4 FSM 2 When Always an event arrives or is triggered inside the BGP 3 Data Input Event Happened 4 PseudoCode old code In state ESTABLISHED Case event is Expiration of a Delta Timer If route associated to timer is in LocRIB then Create announcements for all the neighbor about the route Send those announcements using external update End if old code 4 5 5 Data structures needed to make all this work e DeltaTimer Class General Description This is a timer initialized with a Delta value seconds When it expires it sends a DeltaTimeoutMessage message on the FSM of the BPG4 using method push Location src SSF OS BGP4 Timing DeltaTimer java e DeltaTimeoutMessage class General Description it is the message generated by the DeltaTimer It contains the nlri of the route that triggers this message and a reference to the peer where the route is stored Location src SSF OS BGP4 Timing DeltaTimeoutMessage java e BusterRoute class General Description this class interconnects the route and the Timer It has methods helping creating the timer and managing it Location src SSF OS BGP4 ListBusterRoutes java e ListBusterRoutes class General Description Holds all the BusterRoute instances associated to the routes of a peer In deep it s composed by a hash table hashed by the nlri and some methods helping to manage the BusterRoutes Location src SSF OS BGP4 ListBusterRoutes java 4 5 Modifications to SSFNet
70. Buster activated Over Ghost Flushing Also the Ghost Buster option is to be used with 3 different delta values used 20 30 and 50 seconds Values under equal and over the MRAI timer initial value because the interaction of this two timers MRAI and delta seems to be critical to the performance of this proposal Compatibility with Traditional BGP4 Some simulations will be also run to test the impact of mix ing nodes with ghost flushing activated and deactivated 4 2 Simulation Environment 25 Sampling the results was also important The rule that we followed is to repeat all the different simulations We understand one simulation as one topology with one reality setting and one of the versions of BGP4 at least 100 times to be able to calculate average values For a single model the average values of every size can be compared For models with only one side an histogram will be used to show the results Simulation Output SSFNet can be configured to generate different outputs about the events happen ing on the simulations For the interest of this project only the messages emission was logged We can count the convergence time and number of messages Meaning of one simulation The case that we will always analyze is triggered by the sudden failure of a node We will measure 4 values Number of messages and time of set up of the simulated environment and Number of messages and convergence time of the system since the failure to the
71. But all they sent an update a second ago so they have to wait MRAI 30 seconds until they can send a new update After 30 seconds the process repeats itself but this time node 2 will be chose as the jump point Another 30 seconds In this example we can clearly show how the combination of a highly interconnected topology clique MRAI limitation and ghost information have as a consequence a extremely high conver gence time 60 seconds A time far too high for some real time services that run over the internet So this is the problem this work studies from all the high convergence situations that BGP4 suffers this is the one we will analyze and try to correct following the Ghost Flushing article 13 Another case worth examining is the ghost information and the fail over situation Let s show an example As we can see in fig 3 2 the ghost information is not flushed until the new path traverses all the nodes of the alternate path 3 2 O 3 2 D YU 1 ZO 0 a t 0 4 5 2 3 p 2 1 1 L 20 d t261 e t 91 f t 121 Figure 3 2 Example of Ghost Information spreading in a fail over scenario 3 2 Ghost Flushing Rule 3 2 1 How it works The idea behind the ghost flushing rule is to try to eliminate all the ghost information as soon as possible This modification of the BGP4 protocol wants to avoid any changes to the messages used by the protocol May cause incompatibilities or any high cpu memory operations t
72. Fail Down time Jitter Split horizon Clique Initial Fail Down Num Messages 9000 8000 7000 2009 BGP4 8 5000 GhostFlushing 2 GhostBuster 20 2 4000 GhostBuster 30 3000 gt GhostBuster 50 2000 1000 o 456 7 8 9 101112 13 14 15 16 17 18 19 20 Size Figure 5 58 Clique Fail Down messages Jitter Split horizon In both scenarios we get similar results to the ones found before 5 5 2 AltPath Topology AltPath Initial SetUp Time 700 600 500 BGP4 400 GhostFlushing S GhostBuster 20 3 300 GhostBuster 30 GhostBuster 50 200 100 0 A Size Figure 5 59 AltPath Set Up time Jitter Split horizon 72 Chapter 5 BGP4 Cases Simulation AltPath Initial SetUp Num Messages 14000 12000 10000 BGP4 8 8000 GhostFlushing 2 GhostBuster 20 3 6000 GhostBuster 30 gt GhostBuster 50 4000 2000 QS vw CPP ee EP Size Figure 5 60 AltPath Set Up Messages no Jitter Split horizon AltPath Fail Down Time 450 400 350 200 BGP4 3 250 GhostFlushing 8 GhostBuster 20 8 200 GhostBuster 30 150 gt GhostBuster 50 100 50 4 0 Swe ee B 4 750 Size Figure 5 61 AltPath Fail Over time Jitter Split horizon AltPath Fail Down Num Messages 25000 20000 BGP4 3 15000 GhostFlushing 2 GhostBuster 20 o GhostBuster 3
73. GP4 In the standard configuration per peer one node cannot send more than one update message with a new route advertisement per neighbor per MRAI It can be also configured per destination Then the limitation is not to send more that one advertisement per NLRI to a neighbor per MRAI The general recommendation specified by the RFC says that this timer should be initialized to 30 seconds Jitter Al timers keep alive MRAI start up should apply a random jitter to avoid problems due to synchronization i e open messages collision or other situations due to the network disposition Decision Processes In the RFC 1771 28 three different decision processes are defined The first one is the one which evaluates the update message just received and will modify the corresponding RIB in if needed The second decision process is in charge of reviewing the content of the RIB INs and modify the LOC RIB if needed There can be three reasons why this can happen Because all the references to a certain destination have been removed from the RIB INs so the route on the LOC RIB must be removed Other cause is that there is a better route in the RIB IN that the one in the LOC RIB about a certain destination Finally if a neighbor which announced a route that was put in the LOC RIB makes another announce about the same destination Implicit withdrawal then the new route must be put on the LOC RIB All this processes have to execute in mutual exclusion Impl
74. Jitter No Split horizon sens 5 23 Bad Fail over time no Jitter No Split horizon 2 2 2 2 Cm m nn 5 24 Bad Fail over time no Jitter No Split horizon es 5 25 Clique Set Up time Jitter No Split horizon o 5 26 Clique Set Up Messages no Jitter No Split horizon k 5 27 Clique Fail Down time Jitter No Split horizon oaoa a 5 28 Clique Fail Down messages Jitter No Split horizon lt s 5 29 AltPath Set Up time Jitter No Split horizon e 5 30 AltPath Set Up Messages no Jitter No Split horizon se 5 31 AltPath Fail Over time Jitter No Split horizon ke 5 32 AltPath Fail Over messages Jitter No Split horizon e 5 33 Multi Set Up time Jitter No Split horizon 2 2 2 2 on nn nn 5 34 Multi Set Up Messages Jitter No Split horizon ke 5 35 Multi Fail time Jitter No Split horizon 5 36 Multi Fail messages Jitter No Split horizon ees 5 37 White Fail down time Jitter No Split horizon ees 5 38 White Fail down time Jitter No Split horizon ooa oaa 5 39 Bad Fail over time Jitter No Split horizon Cm nn nn 5 40 Bad Fail over time Jitter No Split horizon ooa a 5 41 Comparing the advantage of using jitter on timers eee 5 42 Clique Set Up time No Jitter Split horizon o aooaa a 5 43 Clique Set Up Messages No Jitter Split horizon oaoa 5 44 Clique Fail Down time No Jitter Split
75. Jitter No Jitter Compare Multi Fail 4500 4000 4 3500 4 BGP4 2 3000 GhostFlushing 5 2500 7 GhostBuster 50 9 2000 no BGP4 e 1500 no GhostFlushing no GhostBuster 50 1000 500 0 T T T 1 2 3 4 Nodes Figure 5 41 Comparing the advantage of using jitter on timers We can notice a dramatic improvement en each version of the protocol The Convergence time in this multi scenario improves in a 1096 So it seems that there are not negative of side effects in using jittered timers on ghost flushing or other of the rules 5 4 Simulation Results Split horizon Enabled No Jitter 5 4 Simulation Results Split horizon Enabled No Jitter 5 4 1 Clique Topology Clique Initial SetUp Time 140 120 4 ee 100 4 ee BGPA 3 80 4 GhostFlushing S GhostBuster 20 A 60 2 GhostBuster 30 gt GhostBuster 50 40 20 0 q PLE E Zu CE EZ EEE Ze EE M EE NE u 456 7 8 9 1011 12 13 14 15 16 17 18 19 20 Size Figure 5 42 Clique Set Up time No Jitter Split horizon Clique Initial SetUp Num Messages 16000 14000 A 12000 4 10000 4 BGP4 gt GhostFlushing 2 8000 4 GhostBuster 20 3 g GhostBuster 30 6000 4 gt GhostBuster 50 4000 4 2000 4 oona 4 567 8 9 101112 13 14 15 16 17 18 19 20 Size Figure 5 43 Clique Set Up Messages No Jitter Split horizon Clique Fail Down Time IN S e c a
76. Path Topology AltPath Initial SetUp Time a o N o O lt o 6 6 BGP4 Ec GhostFlushing GhostBuster 20 ee GhostBuster 30 300 GhostBuster 50 WW sa Vv vr ez PT PT P P Size Seconds EN S S Figure 5 10 AltPath Set Up time no Jitter No Split horizon Set Up Again like in the previous case traditional BGP and Ghost Flushing behave in the same way On the other hand the side effect of the delta timer is highly noticeable in this graphics You can notice performance disadvantage proportional to the value of the delta delay we can see parallel performances The number of messages is the same even if there are delays So no differences in the number of messages Fail Over All the versions show a similar style of convergence polynomial But the difference is the degree while the ghost flushing shows a lower degree the traditional BGP shows the highest of all in a tie with the 5 2 Simulation Results Split horizon disabled No jitter 53 AltPath Initial SetUp Num Messages 16000 14000 4 12000 4 10000 BGP4 gt ra GhostFlushing p 8000 GhostBuster 20 3 d GhostBuster 30 6000 GhostBuster 50 4000 2000 0 SY ooo Pod PR Size Figure 5 11 AltPath Set Up Messages no Jitter No Split horizon AltPath Fail Down Time 500 4 450 400 350
77. RUNTIME echo Max Memory MAXMEM megabytes echo OutPut File NOMFICH JAVAC java rm f NOMFICH test out JAVA Xmx MAXMEM m SSF Net Net RUNTIME DMLFICH V DICTIONARY SCHEMAS gt NOMFICH 2 gt amp 1 less NOMFICH grep v SYN from gt NOMFICH copy mv NOMFICH copy NOMFICH echo date sh machine sh Sim DMLFICH gt gt simulation log view JAVA RacewayViewer DMLFICH 143 144 Appendix D SSFNet Simulation execution Makefile Appendix E Multi Network Models KA PX We NN VAI NI M i x a NSN Figure E 2 110 nodes structure 145 146 Appendix E Multi Network Models Figure E 3 208 nodes structure SN NS SINN N NY NY SSS Figure E 4 409 nodes structure Appendix F Zebra Testing Lab Figure F 1 Zebra testing Lab A1203 Figure F 2 Hp procurve switch 2524 used during the tests 147 148 Appendix F Zebra Testing Lab Log file excerpt from Node 1 in a 7 nodes clique deactivated 2004 07 21 2004 07 21 2004 07 21 2004 07 21 2004 07 21 2004 07 21 2004 07 21 2004 07 21 2004 07 21 23 23 23 23 23 23 23 23 23 path 2 3 2004 07 21 2004 07 21 2004 07 21 2004 07 21 2004 07 21 2004 07 21 2004 07 21 2004 07 21 2004 07 21 23 23 23 23 23 path 3 4 7 23 23 23 23 path 5 6 2004
78. Routes Changes in LocRIB decission process 3 announcements routes and withdrawals external update If Delta timer not expired route is taken out of the waiting list but not sent PEER Class AdjRIBIn Create entry for new route This creates timer ListBusterRoute decission process 2 Figure 4 9 Route arrives and the protocol tries to send if but delta timer is not expired Delta Timer Expires We suppose that the route is in the LocRIB So we want to sent it The schema can be found in fig 4 10 4 5 4 Deep inside the code Pseudocode We are going to show some modifications to the code on the BGPSession class Other classes have been also modified RIBIn Peer but they are minor modifications that don t need to be shown Modifications highlighted with bold letters try send update 1 Function Tries to send a message If it s not possible protocol limitation it takes the proper actions Now it also considers the delta timer limitation associated to each route that is going to be sent 2 When when ever a message is needed to be sent 3 Data Input UpdateMessage to be sent the address of the advertisers of the route and to which peer we want to send the message 4 PseudoCode 4 5 Modifications to SSFNet s BGPA for the Ghost Buster Rule 43 DeltaTimerExpired DeltaTimeoutMessage Route PEER Class handle event AdjRIBIn Delta Timer It receives the route whose ass
79. a llegar a un destino lo hab a anunci ado antes pero el temporizador MRAI no est expirado en vez de enviar un mensaje de retirada esperar hasta que dicho temporizador expire y enviar un mensaje de anuncio con el nuevo camino Esto se llama retirada impl cita Elegir la mejor ruta para cada destino se hace en el segundo proceso de destino Depende de la implementaci n del protocolo y las pol ticas de la instituci n que controla la AS Ejemplos de los criterios a seguir a la hora de elegir un camino Por orden de importancia e Longitud del camino de ASs e M trica de los diferentes caminos e Preferencia local Si hay diferentes maneras de entrar en una AS esta AS puede preferir ser alcanzada por un camino u otro e Otras que los administradores quieran implementar Las pol ticas de distribuci n son tambi n algo importante a tener en cuenta Incluso aunque difer entes ASs est n f sicamente conectadas red y hay sesiones entre sus BGP routers no implica que intercambien toda la informaci n de encaminamiento que conocen Esto es lo que se conoce como relaciones entre ASs 18 Internet es una red que pertenece a una serie de compa as con intereses econ micos las compan as cobran por transportar tr fico y dar conectividad a otras redes Esto puede significar que una AS podr a permitir un cierto tr fico desde un vecino a un destino pero no a otro Quiz s porque el vecino ha contratado a la compa a due a de la AS
80. aciones Para m s detalle acudir a la memoria principal Durante los experimentos repetimos las simulaciones cambiando algunas funcionalidades dentro de BGP4 aplicaci n de jitter a los temporizadores y split horizon En esta secci n compararemos todas las t cnicas con estas funcionalidades activadas y desactivadas La idea es ver cual es la mejor combinaci n En fig 5 1 podemos ver el resultado de todas las configu raciones Para cualquier versi n el mejor rendimiento aparece con split horizon y jitter activado No ha aparecido ning n comportamiento peor al combinar las reglas Es seguro entonces utilizarlas todas juntas 5 2 Combinando nodos con y sin ghost flushing Un punto interesante en este trabajo de investigaci n era ver que ocurrir a si combinamos routers BGP que usan ghost flushing con nodos que no lo utilizan Teniendo en cuenta que los routers y redes en Internet pertenecen a diferentes instituciones y cada una puede utilizar diferentes marcas de routers es dif cil que todos pudieran aplicar la regla ghost flushing a la vez Este experimento consiste en coger el escenario m s efectivo para la regla ghost flushing el clique y empezar a desactivar la regla en los nodos Elegimos cliques entre 4 y 15 nodos El experimento es el mismo que antes Ahora comienza con todos los nodos usando ghost flushing is es repetido reduciendo cada vez el n mero de nodos usando la regla 121 122 Cap tulo 5 Simulaci n de Casos de BGP4
81. alsa ser eliminada de la red Flushed pero costar atin m s mensajes m s anuncios Actualizaciones con nuevas rutas y mucho m s tiempo Si a todo esto le anadimos la limitaci n del MRAI es f cil ver que ste puede ser el origen de una situaci n de tiempo de convergencia alto Despu s de este ejemplo podemos definir la idea de Informaci n Fantasma contenido de tablas de encaminamiento suposiciones o mensajes generados a partir de informaci n que ya no es v lida Si seguimos el cl sico modelo de BGP4 podemos ver que esta informaci n fantasma engendrar m s informaci n fantasma y as hasta el final Mostremos un pequeno ejemplo del impacto de la informaci n fantasma en un escenario fail down 13 ASpath 0 ASpath 0 ASpath 20 ASpath 10 ASpath ASpath 310 1017 20 10 Q 220 1200 2 210 i 120 7 210 w d 310 aid 30 31940 30 Gi X 40 31085 14 410 ASpath 0 ASpath 0 ASpath 10 ASpath 10 ASpath 120 ASpath 120 MC j b t 1 c t 2 ASpath ASpath 310 ASpath ASpath 310 VO 2 210 1 2 210 2310 dst 3210 4210 a t 0 3108 9410 310 G 410 ASpath 210 ASpath 210 ASpath 210 ASpath 210 d t 3 e t 31 ASpath ASpath ASpath ASpath ASpath ASpath Q 2 2310 O T A N 34210 4321 321031 Xp 4210 321057 Xa 4210 3210 G Y3 4210 ASpath 4210 ASpath 2310 ASpath 4210 ASpath 3210 ASpat
82. alse show id data true show AS number and prefix for each BGP router show rcv update true show when Update msgs are rcvd show snd update true show when Update msgs are sent ghostdebug false proc_delay_model uniform_random max_proc_time 0 25 min_proc_time 0 0 Net id 1 AS status boundary router id 1 graph ProtocolSession name bgp use SSF 0S BGP4 BGPSession autoconfig false connretry time 120 min as orig time 15 ghostflushing true reflector false neighbor as 2 address 1 1 use return address 1 2 _extends basic ebgp neighbor neighbor as 3 address 1 1 use return address 1 3 _extends basic ebgp neighbor neighbor as 4 address 1 1 use return address 1 4 _extends basic ebgp neighbor neighbor as 5 address 1 1 use return address 1 5 _extends basic ebgp neighbor ProtocolSession name socket use SSF 0S Socket socketMaster ProtocolSession name tcp use SSF OS TCP tcpSessionMaster 139 140 Appendix C DML 5 nodes clique scenario ProtocolSession name ip use SSF OS IP interface virtual true interface interface interface ma mo eo er rr H 22 2 2020 0 P W N O interface Net id 2 AS status boundary router id 1 graph ProtocolSession name bgp use SSF 0S BGP4 BGPSession autoconfig false connretry time 120 min as orig time 15 ghostflushing true reflector false neighbor as 1 address 1 2 use return address 1 1 _exten
83. alue 0000 Observations 8310 92 to lt 176 lt 101 3 Convergence Time Figure 5 38 White Fail down time Jitter No Split horizon Fail Down time Looking to this Histograms about Egown we can see a more stable response with the Ghost Flushing rule convergence times vary less Also they gather around a much smaller time 5 3 5 Bad Case Normal Distribution Mean 44 859 Sid Dev 18 169 Bad Normal Fail Down Time KS Test p value 0001 Observations 25 7 to lt 35 2 to lt 44710 lt 54 310 lt 111 410 121 to lt 352 44 7 543 63 8 lt 121 130 5 Convergence Time Figure 5 39 Bad Fail over time Jitter No Split horizon 64 Chapter 5 BGP4 Cases Simulation Normal Distribution Mean 84 244 Std Dev 30 312 Bad GhostFlushing Fail Down Time KS Test p value 0000 Observations 54710 66110 77 410 88 7 to 145310 156 610 167910 lt 1566 lt 167 9 lt 179 2 lt 66 1 774 lt 88 7 lt 100 Convergence Time Figure 5 40 Bad Fail over time Jitter No Split horizon Fail over Time From a stability point of view the results are similar but still the delay for the ghost flushing due to the unnecessary flushing of the path is noticeable This path has a incorrect AS Path info but a correct Next hop attribute what makes it valid 5 3 6 Comparing between jitter enabled and disabled
84. and its Environment Router Client zu Router Client o o Router m Client N Figure 2 6 Example of a Route Reflector Configuration inside the same AS 2 3 Autonomous System Relationships This work is about the problems of the BGP4 in some topological situations so in this chapter we will try to show some examples of the most typical BGP4 relationships that found on the internet As showed on the article Inferring Autonomous System Relationships 18 This chapter highlights parts form that article relevant for this work In the next chapters we will relate this examples with the problematic situation Provider a Router Forbbiden Traffic Router Router Router Allowed Traffic Figure 2 7 Filter Policies This relationships exist due to various reasons first the topology of the network how the different ASs and networks are physically connected The other factor are the peering policies established between the ASs due to economic and commercial relationships between the institutions owning the The peering policies take effect in the filters set over a BGP session Le two ASs have hired 2 4 History 11 access to the Internet through the same provider but they are also connected directly fig 2 7 One of them would like to access the other but not to allow the access the internet throw itself These are the commercial
85. anuncio podr an ser retrasados atin mas de lo obli gatorio De este modo la informaci n fantasma es totalmente bloqueada ste es un enfoque todav a m s agresivo para detener la informaci n fantasma respondiendo a dos situaciones En primer lugar algunas implementaciones de BGP4 no incluyen la limitaci n de MRAI de esta manera nos aseguramos de ello La segunda situaci n es intentar modelar el escenario en el que se producen interacciones entre la regla ghost flushing y algunas estrategias de control de oscilaci n de ruta 16 provocando retrasos en la retransmisi n de rutas Delta puede tomar cualquier valor sin embargo como las simulaciones mostrar n m s adelante si es menor que el valor MRAI no se percibir ning n efecto derivado de esta regla De nuevo una definici n m s compleja y una descripci n matem tica completa pueden ser encontradas en 15 3 3 2 Tiempo de Convergencia Situaci n Fail Down delta h Siendo K Edown ES hd 3 3 La idea detr s de esta f rmula es que de acuerdo con la regla ghost buster el camino AS fantasma solamente puede crecer una vez cada delta h La m xima dimensi n de un camino AS es d entonces la ecuaci n para t Tiempo de convergencia es 3 4 Otras Soluciones 115 A router announces the preferred new ASpath Om peering iff it receivg pouncement about thg at least delta otherwise it suppres announcement until delta time passes GhosfBuster Figura
86. aphical network design and validation tools and serves as a machine independent model exchange format suitable for storage in databases The latest SSFNet distribution a collection of DML configurable Java components for Internet modeling and simulation The distribution includes source code for 1 Two derivative frameworks SSF OS for modeling of the host and operating system compo nents especially protocols and SSF Net for modeling network connectivity creating node and link configurations 2 Core Internet protocol models IP BGP4 OSPF TCP UDP Sockets and various workload generating client and server application models 3 Protocol validation tests are included Topological network component addressing and auto mated IP address allocation CIDR compliant 4 Management of global traffic patterns 5 Management of parallel random number streams employing a suite of strong random number generators and statistics from the CERN Colt package Tutorials explaining step by step how to create DML network models and how to write con figurable protocol models using SSF OS in x kernel style BGP4 Features Specifications of BGP4 RFC 1771 28 EBGP IBGP with all timers Route Reflection 30 route Flap Damping 16 and no aggregation 28 It includes a validation suite to test modifications of the implementation Opposing to NS 2 this simulator uses a different model It chooses only one language to implement the simu
87. arison For every version the best performance is found when both split horizon and jitter are used We have not seen any worse behavior of any of the versions if combined with this settings It is safe then to use them all together 5 7 Combining nodes with and without ghost flushing One interesting side of this research was to compare what would happen in we combine BGP nodes that use ghost flushing with nodes that doesn t Since routers and networks belong to different vendors and institutions it s hard that all start using ghost flushing at the same time This experiment consists to take the scenario where ghost flushing is more effective the clique and start to deactivate the ghost flushing rule in the nodes 5 8 Conclusions 75 Cliques between 4 and 15 nodes were taken The experiment is the same as before Now it will be begin with all the nodes applying ghost flushing and then repeated reducing by one each time the number of nodes using the ghost flushing rule Ghost Flushing together with BGP4 4 Nodes 5 Nodes 6 Nodes 7 Nodes 8 Nodes 9 Nodes 10 Nodes 11 Nodes 12 Nodes 13 Nodes 14 Nodes 15 Nodes How worse 12 3 4 5 6 7 8 9 10 11 12 13 14 15 Active ghost nodes Figure 5 68 Mixing BGP4 with ghost flushing More is worse The fig 5 68 shows the results of out experiment The content of the figure is confusing so l
88. as del LocRIB para ser enviadas exteral update con todos los anuncios Si MRAI no expirado todav a Forzamos el env o de mensajes Siuna ruta alterada no es v lida encontrar una nueva para Si encontramos un reemplazo y su longitud es mayot que el de la antigua ahadimos este NLRI y la longitud de las rutas a GhostData Si una ruta alterada is v lida sustituir toda referencia a su NLRI en el LocRIB con ella Identifying Ghost Info Si la ruta reemplazada pequefia comprobamos si la hay una entrada en GhostData Si la hay actualizamos la entrada si no creamosuna nueva de retirada a todos los nodos incluyendo todos los NLRIS en la estructura GhosData Envio de Retiradas actualizaciones anuncios y retiradas external_update Figura 4 1 Tratamiento de actualizaciones con Ghost Flushing en el esquema BGP de SSFNet 4 3 Modificaciones al la Implementaci n regla Ghost Buster 4 3 1 Activando la regla Ghost Buster desde el archivo DML El sistema de lectura del archivo de configuraci n tambi n fue modificado Dos entornos de configuraci n fueron modificados el global y el local Las aserciones locales son utilizadas por cada uno de los nodos Las globales afectan a todos y cada uno de los nodos definidos ste ltimo es especialmente til cuando se trabaja con ficheros DML pregenerados En esos casos modificar todos los nodos puede ser costoso Las aserciones definidas son bgpop
89. ath 1 longPath lastPath return isGhost public boolean isGhost i return lastPath gt oldPath decision process 2 1 4 Function takes the result from the first phase of the decision process and chooses which routes must be installed on the LocRIB Also identifies ghost information that can have been installed on the LOCRib When After handling an update if the decision process is needed Data Input All the routes that have changed New Routes Withdrawn routes and routes that are replaced Implicit withdrawal Pseudocode for every changed Route New Replaced and Withdrawn loop if route is not feasible then if route was inside the LocRIB then Remove route from LocRIB Try find a new route for the removed nlri in the RIBIns from other neighbours and put it in the LocRIB GHOST CODE If new Route is longer than the old route then GhostData add NLRI old path length new path length End if GHOST CODE END end if else route is feasible if there is no route in the LocRIB for this NLRI then Add route to the LocRIB Else if route is better than the one in LocRIB then Remove the current route in LocRIB for this NLRI if it exists Check if what we replaced was already a replacement because of a withdrawal and if it was the withdrawal that caused the previous replacement does exist Put route in the LocRIB We check if there is an entry in GhostData for
90. atical analysis and complete demonstrations of the results that are going to be shown in this chapter Here we will show the results of this analysis and summarize the idea behind them The notation used must be specified 3 2 Ghost Flushing Rule 17 h link latency n number of nodes E number of links minRouteAdver minimum route advertisement interval MRAI Now we will show all the convergence times relevant to this work Fail Down situation Edown n h 3 1 2hnE min Route Adver 32 For the Egown the idea is simple After k rounds all AS paths shorter or k long have been flushed At the beginning the closer nodes to the failure will flush their routes and this flush will propagate eliminating longer paths that farder nodes hold In the worst case the fardest node is n hops away h seconds every hop so it finishes being n x h We can see that the complexity is much better than the one on the traditional BGP with min Router Adverx messages O n Fail Over situation Analytically is not possible to prove that the ghost flushing is always better that the traditional BGP in the Fail Over case As pointed in 15 the convergence time will depend on how long it takes until the ghost information vanishes and how long the new path propagates We will see in further chapters that the case showed in 3 2 improves using the ghost flushing rule However there are extreme cases where the ghost flushing BGP behaves worse than
91. by DARPA through the VINT project at LBL Xerox PARC UCB and USC ISI Currently ns development is support through DARPA with SAMAN and through NSF with CONSER both in collaboration with other researchers including ACIRI Ns has always included substantal contributions from other researchers including wireless code from the UCB Daedelus and CMU Monarch projects and Sun Microsystems NS 2 is a event driven object oriented simulator It has two differentiated parts the simulator engine and the model definition interface The simulator engine is developed in C trying to achieve a high performance but at the same time keep an easy to understand and modify structure Meanwhile the simulation interface is implemented in OTcl Object Tcl therefore the simulations are configured in OTCL This is also a strong point favoring this simulator Tcl is a good scripting language to develop programs to run the simulations and configure them Since the configuration interface is a suite of tcl commands that manipulate the internal simulating classes all the simulating process can be written and developed fully in TCL BGP 4 is quite similar to Zebra Configuring the BGP nodes is done like in real Zebra nodes You can write configuration files that would run on the Zebra software It actually uses a notation cloned from Cisco and feed them to the simulator After it generates a log file per each BGP node which content is fully configurable from state machine l
92. ce time situation After this example we can then define the idea of Ghost Information 13 route table contents assumptions or messages generated based on not valid anymore information According to the classical model of BGP4 this ghost information would generate more ghost information and then on and on Let s picture an example to show the impact of the ghost information in a fail down situation 13 ASpath 0 ASpath 0 ASpath 20 ASpath 10 ASpath ASpath 310 2 9 10 D 2 20 1200 O 210 1120 Rd m 310 410 Auer 40 30 G 4 40 3103 14 410 ASpath a a ASpath 0 ASpath 10 pate 10 ASpath 120 ASpath 120 b t 1 c t 2 ASpath ASpath 310 Aspe 0 ASpath 310 dst a t 0 AD DT ASpath 210 ASpath 210 ASpath 210 ASpath 210 d t 3 e t 31 ASpath ASpath ASpath ASpath ASpath ASpath 20 2310 a 5 a 5 34210 43210 3210Gf Ya 4210 32106 4210 3210 amp r 4210 ASpath 4210 ASpath 2310 ASpath 4210 ASpath 3210 ASpath 4210 ASpath 3210 Dt 32 g t 33 h t 61 ASpath ASpath D w 342 E 4 43210 ASpath ASpath f t 62 Figure 3 1 Example of Ghost Information spreading in a clique topology and high E654 In fig 3 1 we can see a clique topology network 5 nodes full connected To understand the notation the numbers inside the nodes are the AS numbers they belongs to
93. ci n a tomar La primera opci n es enviar inmediatamente un nuevo anuncio con el nuevo camino Retirada impl cita Pero esto puede no ser posible por la limitaci n del MRAI Sin embargo podemos enviar una retirada expl cita que eliminar flush la informaci n fantasma generada por nosotros que ya no es v lida El significado de los mensajes de retirada cambia respecto al que el BGP4 tradicional le daba Antes un mensaje de retirada significaba que un nodo no conoc a ning n camino al destino referido Ahora bajo la regla ghost flushing un mensaje de retirada significa que el camino de ASs antes anunciado ya no es v lido Un router puede tener caminos a un destino y enviar retiradas sobre ese destino When the distance to destination dst is updated to a worse ASpath AND a minRouteAdver time did hot elapse since the last announcement then send withdrawal dst to GhostFl shing all neighboring BGP peers Rule Figura 3 3 Regla ghost flushing en su enunciado original en ingl s Mostremos un ejemplo gr fico de como funciona En fig 3 4 podemos ver la misma situaci n que en fig 3 1 el clique de cinco nodos Hasta t 2 todos los nodos hacen lo mismo que con BGP4 tradicional Pero entonces todos los nodos Menos el nodo 1 cambian su camino para llegar a 0 por un m s largo pero no pueden enviar un nuevo anuncio porque en t 1 ya enviaron uno Aqu es donde entra la regla ghost flushing y una retirada general de la ruta es enviada
94. col is implemented in different daemons this includes some of the various advantages of this software package e Easy to modify In our case we wanted to modify just the BGP4 part of this software The modular approach allowed us to do it without touching any code related to other routing protocols or the interaction between the suite and the operating system As a result the range of code to be analyzed was extremely reduced e Asymmetric Load support An overload or heavy traffic in one of the routing protocols doesn t have the same impact in the rest of protocols as there would be in a monolithic approach e Reliability In case of a problem with one of the protocols or its daemon the fault will be limited to that protocol not affecting the rest of the daemons Also this fault can be analyzed and corrected without taking the whole router off line e Free and Open Source Obvious and compulsory feature for this thesis since our intention is to modify the behavior of routing suite Also we have to consider that a network situation can require special routing capabilities This suite is perfect since it can be easily modified and it s free In some cases a router build with a conventional computer and Zebra can be a inexpensive alternative to the well known embebed solutions 34 Fully upgradable and customizable About what routing RFCs it supports Concerning BGP4 it fully supports the RFC 1771 28 However it also implements functio
95. connectivity to a destination D 5 1 Simulated Cases 49 From node A there are many paths to D There has to be at least three paths Pi Po P3 e P P share a part of their ASPaths e P must not include the common part of P4 Po e P must be longer e The fault must happen in the common part of P4 Pa Size 12 nodes Convergence Times studied E and Eup Interest Practical and slightly theoretical P3 Figure 5 4 Bad topology The reason that makes this a bad case is when node 12 goes down Node 2 changes from Pj to P and advertises it to 1 The Node realizes that Pa is not valid either and then chooses Pg longer than Pa that triggers the ghost flushing so it sends a withdrawal about D to node 1 so node 1 doesn t have a path to D Until MRAI time 30 seconds later it won t be able to send the new path to node 1 The problem is that even if the AS Path info that node 1 would have was wrong with the traditional BGP4 during those 30 seconds node 1 would have node 2 as next hop to D And node 2 has the correct path But with Ghost flushing the withdrawal triggered by the second path change and the first path change for 30 seconds node 1 cannot reach D 5 1 5 Multi Collection This collection of models have been constructed from tables dumps of real BGP4 routers on the internet They come from the Internet Provider topologies and they were found at 26 They are multi AS router level topologies approximating
96. ctiva de Ciclos Envio recepci n 15 Reduce el tiempo de convergencia pero como veremos en la fase de simulaci n ghost flushing funciona mejor Propuestas en 12 implican informaci n extra en los mensajes de retirada En este trabajo queremos evitar cualquier modificaci n en los mensajes del protocolo 116 Cap tulo 3 Ghost Flushing y Otras Propuestas Cap tulo 4 Entorno de Simulaci n BGP4 4 1 Simulador y casos Simulados Tal y como se indica en la memoria principal utilizamos el simulador SSFNet 2 0 Este simulador utiliza un formato de definici n de redes llamado DML Para generar los ficheros DML se desarrollaron una serie de programas que le an formatos propios m s sencillos Durante las simulaciones se utilizaron varios escenarios en diferentes condiciones Los escenarios Descritos m s ampliamente en la memoria completa son clique clique con camino alternativo caso malo para ghost flushing un caso extra do de un art culo y una serie de modelos extra dos de tablas de encaminado reales de Internet Adem s estos escenarios se simularon en varias condiciones seg n si se usaban o no 2 funcionalidades propias de BGP4 split horizon y aplicaci n de jitter a los temporizadores Para m s detalles acudir a la memoria principal 4 2 Modificaciones a la implementaci n para la regla Ghost Flushing Para implementar esta regla dentro del simulador tuvimos que analizar el proceso de actualizaci n Desde la llegada
97. curve switch 2524 used during the tests CC on non nn 147 xvi LIST OF FIGURES Preface This project Master s Thesis Depending on the country was developed during a Erasmus Exchange Program between the Centro Polit cnico Superior of Zaragoza Spain and the Lule Tekniska Universitet Sweden during the 2003 2004 course I want to thank my thesis director in Sweden Lenka Carr Motyckov for her help during this project and for giving me the possibility to work in the interesting world of routing protocols Also i would like to thank Jes s Alastruey Bened my project representant in Spain for his advice making possible this project to adjust to my home s university standard I must not forget my parents Gonzalo and Nieves without whom I wouldn t have the chance to exist study and go on this exchange program Thank you A special point about the people of the computer support Specially Johan Hallb ck who sup ported and suffered my attempts of killing the sigma sun machines They were also very helpful with any problem or need I had with my computers Finally I want to greet and thank my friends here in Lulea and back home that helped me to enjoy this great year in a foreign university Including the guys in the LURC thanks To all them thank you Gonzalo August 2004 Este proyecto Master s Thesis Depende del pais fue llevado a cabo durante un programa de in tercambio Erasmus entre el Centro Polit cnico
98. de una actualizaci n hasta el env o de una nueva Llegamos a la conclusi n de que para hacer al protocolo cumplir la regla ghost flushing ten as que implementar dos funciones Identificar la informaci n fantasma y enviar nuevos mensajes de retirada cuando fuesen necesarios Para identificar la informaci n fantasma decidimos que el mejor momento en el c digo del BGP era dentro de la segunda fase del proceso de decisi n decision process 2 En ese momento tenemos acceso al LocRIB Ruta utilizada hasta ahora y la nueva ruta que va a ser elegida Y que puede ser informaci n fantasma Si descubrimos que la antigua ruta va a ser sustituida por una ruta peor hemos creado informaci n fantasma anteriormente Para mantener un control de la informaci n tambi n usaremos una estructura de datos almacenando los nlris sobre los que hemos recibido informaci n fantasma Para cada NLRI almacenaremos la longitud del ltimo camino AS que hemos puesto en la LocRIB Puede haber muchos reemplazos en poco tiempo y la longitud que estaba en el LocRIB antes de cualquier modificaci n El lugar para insertar el env o de nuevos mensajes de retirada era f cil de encontrar Se decidi que el mejor lugar era durante la tercera fase del proceso de decisi n decision process 3 In ese momento el protocolo decide como enviar las rutas y las retiradas Si la nueva ruta sobre un NLRI en la LocRINB es m s larga que la que ten amos antes enviaremos un mensaje de re
99. ds basic ebgp neighbor neighbor as 3 address 1 2 use return address 1 3 _extends basic ebgp neighbor neighbor as 4 address 1 2 use return address 1 4 _extends basic ebgp neighbor neighbor as 5 address 1 2 use return address 1 5 _extends basic ebgp neighbor ProtocolSession name socket use SSF 0S Socket socketMaster ProtocolSession name tcp use SSF OS TCP tcpSessionMaster ProtocolSession name ip use SSF OS IP interface p A virtual true p A interface interface interface ma mnm rr H H H ga a oP W H O LJ LJ LJ LJ interface Net id 3 AS status boundary router id 1 graph ProtocolSession name bgp use SSF 0S BGP4 BGPSession autoconfig false connretry_time 120 min_as_orig_time 15 ghostflushing true reflector false neighbor as 1 address 1 3 use_return_address 1 1 _extends basic_ebgp_neighbor neighbor as 2 address 1 3 use_return_address 1 2 141 _extends basic ebgp neighbor neighbor as 4 address 1 3 use return address 1 4 _extends basic ebgp neighbor neighbor as 5 address 1 3 use return address 1 5 _extends basic ebgp neighbor ProtocolSession name socket use SSF 0S Socket socketMaster ProtocolSession name tcp use SSF OS TCP tcpSessionMaster ProtocolSession name ip use SSF OS IP interface id O virtual true interface id 1 interface id 2 interface id 4 i
100. e Figure 4 7 Update Process in SSFNet s BGP Schema 4 4 Modifications to SSFNet s BGP4 for the Ghost Flushing Rule 37 4 4 Modifications to SSFNet s BGP4 for the Ghost Flushing Rule To implement this rule inside the simulator we had to take a deep look at the Update Process From the UpdateMessage arrival to the generation of a new one We found that to make the protocol to behave according to the Ghost Flushing rule we had to implement two tasks Identifying the Ghost Information and Sending the new withdrawals when needed To identify the Ghost Information we decided that the best point in the BGP code was inside the second phase of the decision process decision process 2 In that moment we have access to the LocRIB Route we were using until now and the new route that is going to be put inside the LocRIB and which can be ghost information If we find that and old route is going to be replaced by a worse route we can say that according to the ghost flushing rule there is ghost information To keep account of the ghost information we also use a data structure storing the nlris that we received ghost information about Associated to it also last ASPath length that we have put on the LocRIB there can be many replacements in a short time and the length of the ASPath of the route that was on the LocRIB before any replacement Using this we can decide later to send or not withdrawals according to the rule The last rep
101. e On the other hand here we start to notice the drawbacks of the ghost buster technique since it delays any update from the time the last update was received having a negative impact in the E The number of messages is the same since even it updates have to be delayed the same updates are needed 52 Chapter 5 BGP4 Cases Simulation Clique Initial Fail Down Num Messages 5000 4 BGP4 gt GhostFlushing P1 4000 4 GhostBuster 20 3 p GhostBuster 30 3000 GhostBuster 50 4567 8 9 1011 12 13 14 15 16 17 18 19 20 Size Figure 5 9 Clique Fail Down messages no Jitter No Split horizon Fail Down About the fail down situation The ghost flushing starts to show its advantages While traditional BGP4 seems to have a linear convergence On the size of the clique of Edown the ghost flushing version seems to be constant and keeping a really low value The ghost buster technique runs over the ghost flushing rules and since the flushing rules eliminate any possibility By General withdrawal of a second update blast after the first updates triggering the ghost flushing rule About the number of messages The traditional shows a exponential behavior On the other hand the ghost flushing shows a linear behavior due to the fact that the number of messages sent are just general withdrawals sent by all nodes n 1 n 1 n 1 messages sent by n 1 nodes 5 2 2 Alt
102. e camino tampoco es bueno Entonces ahora elige uno a trav s de Y que es m s largo e EI ultimo evento dispara la regla ghost flushing enviando un mensaje de retirada a S 114 Cap tulo 3 Ghost Flushing y Otras Propuestas e X env a la nueva ruta nueva a S despu s del temporizados MRAI Con la regla ghost flushing este caso resulta en un peor comportamiento porque S siempre deber a encaminar a trav s de X para alcanzar Dst Pero durante MRAI segundos no tendr esa ruta por el mensaje de retirada generado por la regla ghost flushing en X Podemos afirmar que esto ocurrir siempre y cuando desde un solo nodo el camino AS se divida en m s de dos caminos alternativos y al menos dos de ellos fallan a la vez quedando un tercero m s largo A Dst Figura 3 5 Un mal caso para la regla Ghost Flushing Start up y Shorter Path Para estos casos no existe un cambio a un camino m s largo en las tablas de encaminamiento Esto significa que la regla ghost flushing no se activar por lo tanto no hay diferencia alguna con el BGP tradicional 3 3 Regla Ghost Buster 3 3 1 Como Funciona En el articulo 15 otra regla era definida para mejorar el comportamiento de BGP en los casos estu diados Es la regla Ghost Buster Esta regla funciona suponiendo que la regla ghost flushing esta tambi n siendo aplicada La idea que origina esta regla es que mientras las retiradas funcionan como limpieza de informaci n fantasma los mensajes de
103. e for disseminating routes to peers int dop Route rte Calculates the degree of preference for a route void external update java util HashMap wds table java util HashMap ads table Tries to send update messages to each external peer if there is any new route information in Adj RIBs Out to be shared with them void force send Message msg PeerEntry peer Overloaded Sends a message immediately with out incurring any CPU delay boolean handle event This process handles both externally and internally generated BGP events void handle mrai exp TimeoutMessage tmsg PeerEntry peer Handles an MRAI Timer expi ration void handle update UpdateMessage msg This method takes all necessary action when an update message is received boolean push ProtocolMessage message ProtocolSession fromSession This process option ally imposes a processing delay for certain BGP events then passes them on to the receive method to be handled void send Message msg PeerEntry peer Overloaded Generic procedure to take any kind of BGP message and push it onto the protocols below in the stack void try send update UpdateMessage msg java util ArrayList senders PeerEntry peer Han dles the sending of an update message This method takes into account the expiration of MRAI timer and management Adding Routes of the waiting list associated with that timer decision process 2 1 Function Takes all necessary action when an update message is received
104. e modificar el c digo del router a nuestro gusto y seg n nuestras necesidades hace de GNU Zebra una buena opci n Sobre la regla ghost flushing muestra las mismas propiedades encontradas durante la simulaci n Los resultados muestran la mejora supuesta a la regla 128 Cap tulo 6 Aplicando la regla Ghost Flushing a GNU Zebra Cap tulo 7 Conclusiones Y Discusiones 7 1 Calidad de los resultados de Simulaci n Cu l es la calidad de los resultados obtenidos de las simulaciones realizadas sobre SSFNet Mirando las caracter sticas del simulador intenta emular todas las capas desde el protocolo de encaminado y los diferentes niveles de la pila de red Suponiendo que todo est bien implementado y que el motor de simulado es correcto podemos confiar el los resultados A principio de este trabajo intentamos realizar la nica prueba de validaci n que nos fue posible Memoria completa La prueba consist a en simular un caso en el que conoc amos todo lo que ten a que ocurrir y comparar con los resultados del simulador El resultado fue positivo as que no descartamos este simulador como ocurri con ns 2 Otras fuentes de confianza en el simulador pueden venir de su reputaci n en la comunidad de encam inado Parece ser que al menos la parte exterior del BGP4 funciona correctamente La nica nota anadir es que por problema derivados de la implementaci n de la m quina virtual de Java no puede simular modelos de m s de 500 n
105. e number of ghost busters in the network It is just a matter of real time Simulate once the 400 nodes scenario takes almost an hour we would need to run 400 simulations more than once to get stable results and thats a lot of time Something important about this rule is that it has high needs of cpu and memory Every new path received needs a timer that allocates memory and produces and event when expired Even if no effect needed This can have a bad impact in the router performance Looking to all this conclusions we see good points and bad points We see a bad performance in medium small scenarios less than 200 nodes for the set up and fail situations This makes us to take the decision of not implementing this rule Chapter 6 Applying the Ghost Flushing Rule to Zebra Routing Software After the analysis of simulations from the different modifications proposed for BGP4 we came with a clear winner the ghost flushing Then it was a moment to do an implementation over a real routing software So an open source free software was needed we looked at the market and we saw a few options Zebra Quagga GateD and OpenBSD s bgpd GateD was discarded when we checked out its web site 3 and found out that it wasn t an open source project anymore and becoming commercial software Ouaggal8 is a spin off from Zebra routing software a new community has been born trying to implicate more people in the development of this software However w
106. e preferred to stick to the original version since it s been running for a longer time and more documentation was available Not much though We learnt about OpenBSD s bgpd after we started working with Zebra The main problem we had is that we had to set up an OpenBSD environment to make it work Also the portability was in issue we were not sure about how this software could be deployed over other operating systems if possible Finally GNU Zebra 4 was the strongest remaining option Strongly modular and with a long run ning life Since 1996 it looked like a good option and quite used From our experience in the development mailing list from Zebra There were also positive opinions about the bgp module in zebra by the routing community 34 23 6 1 Zebra as a Routing Software GNU Zebra is a free software that implements a set of TCP IP routing protocols It includes the most used ones like BGP4 RIP v1 and v2 or OSPFv2 In the case of BGP4 it follows the RFC 1771 28 implementing most of its features One of its most attractive characteristics is its modular approach Every routing protocol is implemented in a different daemon being the Zebra daemon their link to the kernel routing table This made the modification of bgpd an issue that didn t imply interfering with the code related to all the rest of routing protocols On its background the company IP Infusion Inc is supporting this project hosting since it s the personal creation
107. e quite surprising Initially when we were running the first simulations we found the expected results a performance between the traditional BGP and the ghost flushing rule However when we started to simulate big models and to apply the split horizon rule or the jitter on the timers the performance of the ghost buster boosted Let s begin with the Fail down There are cases where the ghost buster with the biggest delta timer 50 seconds outperforms the rest of the configurations The model where this effect appeared is the multi topologies When we test over the biggest models the ghost buster rule performs better than the ghost flushing in both time and messages It looks like the conservative approach in high interconnected situations when long and numerous paths exist ghost buster performs better Similar situation appears in the set up scenario Again in extremely big scenarios the ghost buster rule performs quite well in number of messages and time Looking to this results we can try to extract some general conclusions It looks like that depending on the point of view the ghost buster performs better or worse If we take in account the time that takes to stabilize the whole network the ghost buster performs quite well However if we look the small picture if we look to small parts of this networks Smaller models the ghost buster performs worse We didn t run any simulation of how the big models 400 nodes perform when we reduce th
108. e text files and TCL because of its powerful programming structure and file management Facts to be considered by this software Topology files To generate easily simulation models a small piece of software was written to generate DML files from a simple topology file it has this structure Number of nodes Triangular connection matrix ghostflushing true false ghostbuster true false busterdelta value of delta timer in seconds dead number of node to die 5 time of death in second Concurrency Some code was written to generate some topology files of the models in different sizes However some of the models like the Internet models are pre generated DML files thus some software was needed to modify this files according to the simulation parameters Programs developed In this section we will show all the software written to make the simulations run To understand how they interact the schema on fig 4 3 can be consulted multiSim sh 1 Function General simulation launcher It runs 2 10 simulations concurrently depending on the time and date 2 Parameters e Initial Iteration final iteration Two natural numbers the simulation will be repeated final initial times e BGP versions Can take the values NORMAL GF GB D value or NADA It can be used as a list i e NORMAL GF If NADA is specified the program will assign the version depending on the machine the program runs on sigmal NORMAL sigma2 GF
109. e used None 5 Response On the standard output will write a topology file of the structure before specified genWhite tcl 1 Function Creation of the topology file similar to the one in 13 representing a part of the internet 2 Parameters e Time of death Simulation time in seconds in which the dead node should die The node that dies is fixed e Ghost Flushing True false Activates this rule for all the nodes e Ghost Buster True false Activates this rule for all the nodes e Delta time Sets the timer of the delta value for the nodes if the Ghost buster rule is activated 3 Execution example tcl genWhite tcl 5000 true true 50 Fixed node will die at second 5000 of simulation They run ghost flushing and ghost buster with a delta timer of 50 4 Space used None 5 Response On the standard output will write a topology file of the structure before specified genBad tcl 1 Function Creation of the topology file similar to the one in fig 3 5 representing a bad case for ghost flushing 2 Parameters e Time of death Simulation time in seconds in which the dead node should die The node that dies is fixed e Ghost Flushing True false Activates this rule for all the nodes e Ghost Buster True false Activates this rule for all the nodes e Delta time Sets the timer of the delta value for the nodes if the Ghost buster rule is activated 3 Execution example tcl genBad tcl 5000 true true 50 Fixed N
110. ebra Also we will study in detail the code related with the BGP functions relevant to the modifications needed to implement Ghost Flushing This chapter is mostly based on 36 14 6 3 1 A Thread s life All events in Zebra are managed by threads They are cooperatively multitasking threads To create and event or to set a event in the future every daemon has a collection of FIFOs where threads can be placed with the function to execute when the event is handled To do this functions there is a collection Thread Add thread_add_read thread_add_read thread_add_read Read Queue Write Queue Timer Queue Unuse Queue a Move to event Move to event Threads whose timer queue queue has expired move to event queue gt Event Oueue t Thread fetch Thread Execution Figure 6 3 Thread life cycle inside of any of the Zebra Daemons of functions e thread_make_master to create the master thread that will manage everything e thread_add_read creates a thread that wants to read from a socket to the out world e thread_add_write creates a thread that wants to write on a socket to the out world e thread add timer creates a thread that wants to be executed in a time set when this function is called e thread_add_event creates a thread associated to an event 82 Chapter 6 Applying the Ghost Flushing Rule to Zebra Routing Software e thread cancel event destroys a
111. ed in a much shorter time that it was supposed to Again a deeper analysis of the logs was done And another strange behavior came to our attention it looked like after a node would receive a withdrawal about the information it used to make its last updates it would send also a withdrawal This behavior was far too different from the one specified on the RFC 28 After all this problems this network simulator was discarded A difficult set up the lack of possibility to run the same compilation in different machines at the same time C 4 based and this final problems of not standard behavior in the BGP model pushed this simulation suite out of the project 4 1 2 SSFNet 2 0 As it is stated on its web page 9 the SSFNet project has two components research and development of scalable modeling and simulation tools and using these tools research on the dynamic behavior of very large networks The software research has been focused on scalability This includes modeling scalability with number of nodes traffic flows bandwidth system heterogeneity as well as performance scalability with number of processors Modeling scalability is a prerequisite for constructing global scale network models performance scalability is a prerequisite for their efficient simulation SSFNet uses and O Figure 4 1 SSFNet logo 2On the digital media accompanying this report there are examples of the configuration files and logs showing this situation
112. ed to behave as a router will always over perform a conventional hardware with a software running on it However it s cheap About the ghost flushing implementation it was easy to implement Not to know where or how mapping the code and it seems to work The tests we drove showed a good performance about it One extra comment about Zebra is about the documentation related to it There is a lot of documen tation about the general architecture but not about how the protocols were implemented It s relatively easy to develop new modules for Zebra However to look inside of the code C code to analyze how the functions of each protocol are done can be quite hard A documentation about this work would be needed for contributors to be able to do real work about Zebra Fortunately the Quagga project tries to do this Parts of this document try to be a small map of how some of the BGP4 functions are implemented in bgpd Chapter 8 Future Work 8 1 Interaction of Ghost Flushing with other features BGP4 has many features that can interact with the ghost flushing rule We took into account some of them Split horizon jitter but not all In the first place a further working line would be to do a theoretical analysis of the interaction between the ghost flushing and the split horizon Maybe to try to combine them in one rule sine both seem to work well together and create a even more powerful rule What about the rest of BGP4 For example
113. edes que se ajusten a las necesidades de un cliente que contrate un rango de IPs De este modo el problema de sobre ocupaci n de direcciones IP se hab a solucionado temporalmente hasta la llegada del IPv6 El intercambio de informaci n de encaminado entre diferentes dominios que no siguen la estructura de clases es el llamado CIDR Hasta 1992 no hab a relaci n entre las asignaci n de IPs y la estructura f sica de Internet Pero entonces una nueva estrategia direccionamiento por proveedor se impuso Desde los niveles m s altos los proveedores de red pose an un rango de IPs y sus clientes deber an estar dentro del rango de IPs de sus proveedores Esto implica una gran ventaja para el encaminado Comparemos el antiguo escenario con el nuevo En el antiguo tenemos dos destinos de rango IP IP1 e IP2 Ambos se conectan a Internet por medio del mismo proveedor pero sus IPs no ten a nada que ver En una tabla de encaminado deber a haber dos entradas sobre como alcanzarlos Sin embargo en el sistema nuevo si ambos est n bajo el mismo rango de IPs la nica entrada necesaria en una tabla de encaminado es al rango del proveedor y ya se encargar n los routers del proveedor de enviar el tr fico al lugar correspondiente Como se puede ver un impacto positivo en todos los routers de Internet se da gracias a esta nueva pol tica de supernetting Pero Qu tiene que ver todo esto con BGP4 BGP3 la versi n previa a BGP4 no soportaba CIDR
114. ee ar ee 5 68 Mixing BGP4 with ghost flushing More is worse ke 6 1 Zebra modular structure All routing information has to pass through the Zebra daemon LIST OF FIGURES xv 3 1 3 2 3 3 3 4 3 5 3 6 4 1 4 2 4 3 5 1 5 2 6 1 A 1 B 1 E 1 E 2 E 3 E 4 FA F 2 Here we find the directory structure for the code of Zebra ss 80 Thread life cycle inside of any of the Zebra Daemons o o 81 bgpd daemon initialization process 22 Cm on nn es 83 Zebra s bgpd handling an incoming update message se 84 Zebra s bgpd decision process Simplified se 84 Small part of the bgpds VTY tree Ke 85 Defining a command 2 o a a A pd se ec AT a dc te 85 Installing the command in a node 85 Inserting the Ghost Flushing code in the decission process a 86 This is the VTY node tree with the new commands se 88 Two LANs one for the BGP4 traffic y the control Traffic se 90 Exporting files o s 2 02 o RU ee gru E dE tg muse ue oe dede dod ds 90 Esquema Simplificado de el procesado de un anuncio en la implementaci n de BGP4 en SO E tt ar a rn ci de a ADA ADA T he Gel amp 104 Distribuci n de clases IP o om eds ded ad ne 105 Ejemplo de una configuraci n de Router Reflectors nn nn 106 Biltr s aplicadoss 2 2 asa aa er a Da AR Ra JR A 106 Ca tico ejemplo de proveedores de Internet 2 2 o nn nn 107 Ejemplo de informaci n fantasma creciendo en un
115. emporizador asociado es eliminado Para el m todo de env o Alteramos el m todo try send update para que el temporizador delta para una ruta que cuyo temporizador no est expirado no sea enviado o puesto en la lista de espera Tratando la expiraci n del temporizador delta para esto se creo un nuevo evento interno dentro de BGP4 La idea es bastante simple anadimos una entrada dentro de m todo handle event que trata cada ruta cuyo temporizador expira Si la ruta est en Loc RIB se intenta enviar de acuerdo con las limitaciones cl sicas de BGP4 MRAI filtros etc como si el temporizador delta nunca hubiera existido Mensajes Temporizadores y cintas de video Para que todo esto funcione necesitamos varias clases nuevas Necesitamos un nuevo tipo de temporizador que disparase el evento apropiado dentro de la m quina de estados finitos Delta Timer Es creado y asociado a una ruta cuando esta llega Cuando expira produce un mensaje que tambi n tuvo que ser definido Otra clase DeltaTimeoutMessage El contenido de este mensaje incluye un referencia a la ruta que ha disparado el evento de ese modo han dle event sabe lo que tiene que hacer Para mantener en una estructura de datos todos los temporizadores junto con la referencias cruzadas entre ellos y las rutas asociadas creamos la clase BusterRoute que ayuda a manejar la creaci n y destrucci n de los temporizadores Para indexar todos las instancias de BusterRoute en la clase que representa
116. en algunas situaciones son solo algunos ejemplos de los varios problemas que adolecen BGP4 En este trabajo analizaremos un pequeno subconjunto del ltimo problema indicado el tiempo de convergencia Este cap tulo definir el mbito abarcado por este trabajo y presentar Y analizar las soluciones propuestas para solucionar dicho problema 3 1 El Problema de la Convergencia 3 1 1 Algunas Ideas Iniciales Antes de entrar dentro del problema es necesario que definamos una serie de conceptos comunes rela ciones con el problema a tratar Redes ser n vistas como grafos formados por nodos Routers BGP4 y arcos conect ndolos Sesi n BGP4 entre dos routers Evento Cualquier cosa que pueda ocurrirle a la red un arco que aparece o desaparece o nodos que fallan o comiencen a funcionar I e Fail down fail over system up shorter path Fail down Un destino deja de ser alcanzable Fail over Un destino es alcanzable por un camino m s largo que antes System up Un destino que no estaba disponible ahora es alcanzable Shorter Path Un destino es alcanzable por un camino m s corto que antes Tiempo de Convergencia Tiempo que transcurre desde que se produce un evento en la red Fail down fail over system up shorter path hasta que la configuraci n de la red se estabiliza y las tablas de encaminado alcanzan un estado final No cambiar n hasta que otro evento ocurra Eup Tiempo de convergencia si un evento system up ocurre Edown T
117. en bgpd de GNU Zebra Cap tulo 8 Trabajo Futuro 8 1 Interacci n de Ghost Flushing con otras reglas BGP4 tiene muchas funcionalidades que pueden interactuar con la regla ghost flushing Hemos tenido en cuenta algunas de ellas Split horizon jitter pero no todas En primer lugar una linea de investigaci n podr a ser el an lisis te rico de la interacci n entre ghost flushing y split horizon Quiz s fusionarlas en una sola soluci n podr a llevar a una regla todav a m s efectiva Otras funcionalidades de BGP4 que tienen que ver con el caso de la convergencia como las pol ticas de filtrado 12 podr an ser analizadas en interacci n con ghost flushing Aunque esto se podr a hacer durante la fase de despliegue ya que ocurrir n en la realidad de Internet 8 2 Probando Zebra hasta su L mites Para probar totalmente la implementaci n de ghost flushing y las capacidades de Zebra podr amos necesitar m s equipos para crear mayores y m s complejas redes Sin embargo cuando este proyecto estaba casi terminado conocimos de la existencia de una aplicaci n de simulaci n de entornos de red para Linux Unix desarrollado por la Universidad Polit cnica de Madrid Este software es conocido como VNUML Virtual Network User Mode Linux 17 Es un sistema para simular en un solo equipo entornos de red totalmente independientes pudiendo hacer creer a varias instancias de una aplicaci n que est n en diferentes m quinas Esto permi
118. ence time if system up event happened Edown Convergence time if fail down event happened Elonger Convergence time if fail over event happened Eshorter Convergence time if shorter path event happened 3 1 2 High Convergence Time and The Ghost Information As shown in some articles 12 13 15 there is a strong relationship between the network topology and the convergence time Also one factor that is critical in the convergence time is the MRAI timer After any change in the network there is always the limitation for MRAI seconds between two 13 14 Chapter 3 Ghost Flushing and other Proposals updates sent from one BGP speaker to same one If many updates are needed this time accumulates being the convergence time the result of this waits for the MRAI timer The proposals studied in this work and extracted from Bremler Barr et all 13 are based also in another idea One lie makes many and in networking it continues recursively This means that if a node makes a decision based on information that is no longer valid the updates sent by this node can contain information won t valid either Afterwards other nodes will make decisions based on false information and then on and on Some time after this false information will be flushed from the network but it will take more messages more updates and more time If we add the delay between updates due to the MRAI limitation it s easy to see that this can be the origin of a high convergen
119. er 20 3 1500000 GhostBuster 30 gt GhostBuster 50 1000000 4 500000 4 0 T T T i 29 110 208 409 Nodes Figure 5 34 Multi Set Up Messages Jitter No Split horizon 62 Chapter 5 BGP4 Cases Simulation Multi Fail Down Time 4500 4000 3500 n 2000 BGP4 2500 GhostFlushing 8 GhostBuster 20 B 2000 GhostBuster 30 1500 GhostBuster 50 1000 500 0 Size Figure 5 35 Multi Fail time Jitter No Split horizon Multi Fail Down Messages 4000000 3500000 3000000 g 2500000 BGP4 o GhostFlushing 2000000 GhostBuster 20 2 GhostBuster 30 1500000 GhostBuster 50 1000000 500000 0 29 110 208 409 nodes Figure 5 36 Multi Fail messages Jitter No Split horizon Fail Down Again we see and improvement of the traditional BGP4 and the GhostBuster Rules The ghost flushing doesn t appear to change after using jitter 5 3 4 White Topology Normal Distribution Std Dev 20 99 White Normal Fail Down Time KS Test p value 0000 50 32510 43 6 to lt 54610 lt 65710 lt 76 7 to lt 120 9 to 143 to lt 4 857 767 87 8 lt 132 154 1 Convergence Time Figure 5 37 White Fail down time Jitter No Split horizon 5 3 Simulation Results Split horizon disabled Jitter Activated 63 Normal Distribution Mean 19 06 Std Dev 26 857 White GhostFlushing Fail Down Time KS Test p v
120. era con las A en l rutas a ser anunciadas cuando MRAI expire Eliminar esa rutas del mensaje Send el mensaje si queda algo enel UpdateMessage Figura 2 1 Esquema Simplificado de el procesado de un anuncio en la implementaci n de BGP4 en SSFNet 2 1 4 Soporte a CIDR Internet se comporta a veces como un ser vivo intentando crecer lo m ximo posible en el menor tiempo posible Como consecuencia los posibles problemas de escalabilidad aparecen antes de los esperado y amenazan con llevar la red a un caos total Este fue el caso del sistema de asignaci n de IPs a principio de los 90 Cuando TCP IP fue dise ado en los 80 32 bits parec an suficientes para todos los equipos conectados Internet siendo los 8 primeros bits la direcci n para la red y los 24 restantes para el equipo Poco despu s las tres clases de redes A B C fueron anadidos para ajustarse a las diferentes necesidades en tamanos de red Sin embargo en los 90 el nuevo sistema empez a tener problemas En primer lugar las redes de tipo B estaban a punto de acabarse y las tablas de encaminamiento estaban creciendo demasiado A parche al dise o del encaminado IP fue aplicado entonces dando tiempo hasta la soluci n definitiva IPv6 Este parche es conocido como Classless Inter Domain Routing CIDR Ocupaci n de redes Clase B y Crecimiento en las Tablas de encaminamiento Como podemos ver en la figura 2 5 las redes de clase A eran demasiad
121. es or withdrawals are widespread The schema can be found in fig 4 7 decission process 1 Put all the routes that are not anymore in the LocRIB to be withdrawn if there is not impicit withdrawal Put all the newroutes on the LocRIB to be sent external update with this announcements If MRAI not expired Eliminate withdrawals about routes to be sent Implicit Update Waiting list with routes to be announced when MRAI expires Eliminate those routes from the message Send the messag If anything left on it UpdateMessage handle event handle update New Routes Remove withdrawn routes from AdjRIBIn Add Replace new routes to AdjRIBIn Run Decission Process If needed New Removed and Replaced Routes decission process 2 Changes in LocRIB decission process 3 If a changed route is not feasible any more find a new one to replace it If a changed route is feasible replace with it any reference to its nlri on the LocRIB announcements routes and withdrawals external update Create new UpdateMessage Put the withdrawals and the first route to be sent in it if any try send update it For each route left to be sent create a new UpdateMessage and try send update it UpdateMessage try send update If MRAI expired Eliminate withdrawals about routes to be sent Implicit Send the messages If anything left on it UpdateMessag
122. escenario de fail down con un alto Egown 110 Informaci n fantasma extendi ndose en el escenarion fail over 111 Regla ghost flushing en su enunciado original en ingl s se 112 Paso a paso la regla ghost flushing en acci n ee 113 Un mal caso para la regla Ghost Flushing lt ooa 114 Regla Ghost Buster en su enunciado original en ingl s e 115 Tratamiento de actualizaciones con Ghost Flushing en el esquema BGP de SSFNet 118 Un ruta llega y el protocolo intenta enviarla aunque el temporizador delta no ha expirado 120 Temporizador Delta Timer Expira CL nn nn nn 120 Mu Hanns 225 2328 212554 987 ete ode et eh x iet Start rc ae e vyt yeast MSA Ge e Root te Y 121 Mezclando BGP4 tradicional con ghost flushing M s es peor o 122 Estructura modular de GNU Zebra Todo acaba pasando por el demonio Zebra 126 Pseudocode implementation of Ghost Flushing over BGP 2 2 135 Example configuration file for a zebra node Its IP ID is 192 168 0 2 It has 5 neighbors It uses Ghost Flushing and it shows the debugging messages about it n 137 29 nodes structure Image Generated by RaceWay network visualization tool 145 4 110 nodes struet re4 0 a ne Bu d mo pU ob Ro laete quede he REY Y e Rd 145 208 nodes str et re rn a AAA a Meee nee 146 409 nodes sbr ct re 2 votos soy ER uere eb rum euius ss 146 Zebra testing Lab A1208 e 147 Hp pro
123. et s explain it Each line represents the evolution of each clique beginning left with no ghost flushing nodes and then increasing the number of nodes As it s natural each series finishes when the number of active nodes reach the total number of nodes in the clique The value on How worse means how many times bigger is Egown with that number of ghost flushers than the Egown got on that clique with all the nodes applying the rule As we can see in the figure there is a linear reduction of the Egown as we increase the number of flushers Reaching the point where only 2096 of the nodes doesn t use the rule the convergence time is really close to the full ghost flushed clique This is really good news if we think of the deployment of BGP4 ghost flushing on the internet We won t need all the nodes to use it to start noticing improvement in the performance 5 8 Conclusions After all this graphics it is time to summarize a general idea after all the simulations 5 8 1 Ghost Flushing As expected the behavior of ghost flushing has been quite good Compared with the traditional BGP4 it has improved in all aspects Convergence time and number of messages no matter the scenario Only in some situations applying the split horizon and the jitter the traditional BGP4 approached the ghost flushing performance However this only happened in cases of reduced sizes when the number of nodes was increased the ghost flushing overtook again the traditi
124. eto de simulaci n en la memoria principal 5 3 1 Ghost Flushing Como era esperado el comportamiento de la regla ghost flushing ha sido bastante bueno Comparado con el BGP4 tradicional ha mejorado en todos los aspectos Tiempo de Convergencia y n mero de mensajes sin importar el escenario Solamente en algunas situaciones aplicando split horizon y jitter el BGP4 se acercaba al rendimiento de la regla ghost flushing Sin embargo esto solo se daba en escenarios de reducidas dimensiones en cuanto la topolog a de red crec a la regla ghost flusher volv a a distanciarse del BGP4 tradicional En las situaci n de Set Up no hay diferencia con el BGP4 tradicional En las situaciones de fail over y fail down hay una gran diferencia La complejidad de la convergencia cambia de lineal a constante en el caso m s simple dependiendo esta de la conectividad Parece como si cuanto m s conectados est n los nodos mejor funciona la regla ghost flushing Y pero BGP4 tradicional Adem s los experimentos mezclando ghost flushing con BGP4 tradicional son alentadores Incluso si no todos los nodos usan la regla el rendimiento del sistema mejora Hay una relaci n lineal entre el n mero de nodos que usan la regla y la mejora en el sistema Es un gran resultado de cara al despliegue de este protocolo en Internet Sobre la implementaci n Resulta sencilla no implica complicados algoritmos que usen extra cpu o cantidades de memoria Revisando todos esto
125. ets the usage of this rule 4 4 2 Modification Schema In fig 4 8 we can find a reduced schema of the Update Message schema with the modifications in bold letters 4 4 3 Deeper Inside the Modification Pseudocode We are going to show how this modifications impact on the pseudocode described in previous chapters We had to modify to methods decision process 2 and decision process 3 Modifications in bold letters GhostData Structure 1 General Description This Data structure holds the Ghost Information list that has been found during the decision_process_2 It is initialised at the beginning of the decision process Currently it s formed by an array of the type GhostNLRI This type stores nlri from the GhostInfo the length of the old path and the length of the path that was put the last on the loc rib In the future this GhostData structure will be a hash map indexed by the nlri 38 Chapter 4 BGP4 Simulation Environment New Routes decission process 1 New Removed and eplaced Routes on process 2 hanges in LocRIB decission process 3 Put all the routes that are not If a changed route is not feasible anymore in the LocRIB to be any more find a new one Pn withdrawn if there is not impicit to A it Identifying Ghost Info withdrawal If we found a replacement and its Put all the newroutes on the length is longer than the old one FA Y pias m we add this NLRI and the routes ANA POA OMI length t
126. f validation tests This tests use the simulator and compare the results with what they are supposed to be Actually when the implementation of ghost flushing and ghost buster was finished we used this validations tests to see if they would affect the BGP4 normal functioning However we also run our own tests They consisted in trying to reproduce the odd convergence behavior described in 13 It worked to discard ns 2 so we used it again with SSFNet and it passed it Other sources of trust on the simulator may come from the opinion on the routing community and it looks that at least for the external part of BGP it works properly so we can trust the results Only note to add is that the simulator begins to be unstable when we simulate bigger models than 500 bgp nodes This problem is due to a faulty implementation of some of the classes defined in the Java virtual machine version we used 7 2 The Ghost Flushing Rule Well as the simulations and the later tests run on Zebra show it s quite effective It has many good points e Low CPU consuming there are no special mathematical operations or complicated algorithms that need a lot of CPU on the router e Low memory usage Actually no extra memory usage is needed No extra information is needed to be stored On the case of the ghost buster this was a problem We needed to set timers each update received just in case that update information could be later chosen to be advertised a
127. g left on it UpdateMessage Figure 2 4 Schema Simplified of the Update handling by SSFNet BGP4 Implementation 2 2 4 CIDR support and BGP4 The Internet behaves sometimes like a living being it tries to grow as much as possible and as fast as possible As a consequence scalability problems show themselves sooner than expected threatening to lead the whole network into a chaos This was the case of the IP system in the early 90s When IP was designed in the 80s 32 bits looked enough for all the hosts on the Internet being the first 8 bits the identifier of the network and the las 24 bits the address for the host However after some time the three classes for the IP addresses were added A B C IP range was split between those classes and the number of bit belonging to the network and the host depended on the class But in the early 90s this design started to show problems In the first place the B addresses were about to exhaust and also the routing tables where growing too much A patch to the IP design was developed in that moment Giving time until the next version of IP IPv6 the Classless Inter Domain Routing CIDR Class B Exhaustion and Routing Table Explosion As we can see in the figure A class networks were too big and C classes too small so B class networks became quite popular too popular in fact The moment came when almost all the B class networks were assigned still more were demanded C classes
128. g u 4 3i Sal dd Pe GA aan MO Ye UR 3 4 2 3 BGPA Protocol Description pao manalaa 28 2 2 1 un a ee 18 k a 5 2 2 1 Path Vectors and Loop Detection lt KL 5 23232 Path Attmibutesma o aa ere med daa EVE E n ecu ur va m e UE e A LA 6 22213 D he Protocol amm eue Ix a erem neen dedi are 6 2 24 CIDR support and BGP4 e 8 22 5 Internal BGP ABGP a kee ee bl beth eke eee eee 9 2 3 Autonomous System Relationships es 10 2 3 1 Relationship Classification and Internet Disposition 11 DAS ISOIN pe A omes etos Bot e db a SPD N R erent f A Ix e x 11 3 Ghost Flushing and other Proposals 13 3 1 The Convergence Problem e e 13 311 1 Some initial concepts sr ace 2 2 22 2 ld bid wo 44e o BE Red 13 3 1 2 High Convergence Time and The Ghost Information len 13 3 2 Ghost Flushing Rule 4 0 ERR eed dE S 15 3 241 How at works 58 rn ed aan WWE LLL AXXs 15 3 2 2 Convergence time uuu ate te een ad mod ed eve 16 3 3 Ghost Buster Rule u uu decuit AA E ka da 4 8 18 339 1 How it works Lando RA See ood da desee eim odd oe k 18 3 3 2 Convergence time con d XS Sd ues SEU ROG AULA XS A e 19 3 4 Other Solutions uma US Xue Fr AED ee T Ri eum T 19 3 41 lt Reset Rules 4 uu Rob bo RUE woe he E mx S Ure e S RI mom doen EEE N 19 3 4 2 Other Approaches to the same problem Ke 19 4 BGP4 Simulation Environment 21 4 hoosing a Sumulator s 2 2 A x VERIS Eds P rte
129. gain This meant extra memory and cpu something ghost flushing doesn t need e No extra information on the messages or incompatibility with the traditional BGP4 There are no bad side effects due to combining ghost flushers and old BGP4 e General good performance as seen on the simulation chapter e Good deployment Looking at the results of mixing normal and ghost flusher nodes we notice improvement with a low number of active flushers On the whole we can say that ghost flushing rule is a great and easy modification for BGP4 From our humble position we would recommend router vendors to add to their software as we did with GNU Zebra 93 94 Chapter 7 Conclusions and Discussions 7 3 The GNU Zebra Routing Software Is GNU Zebra and option as a real routing software Well if we look to our experience during this project the opinion of some experts 34 and the community of users we can say yes if you need a cheap router It implements all the main RFCs related with BGP4 and the most important internal routing protocols It s modular features makes it reliable and easy to diagnose in case of fault Also the possibility to modify and customize the behavior of the software makes it appealing in research environments where testing new features can be interesting They only problem it suffers from is that even if the software is nice It won t ever beat an embebed router a combination of hardware and software all creat
130. gt old select gt attr gt aspath gt count amp amp int thread timer remain second mi thread gt 1 1 if bm gt ghost debug 1 zlog info As GF Route Changed for a longer one and MRAI Timer d Not expired peer gt host int thread timer remain second mi thread zlog info s GF Sending withdrawal for s d peer gt host inet ntop rn gt p family amp rn gt p u prefix buf BUFSIZ rn gt p prefixlen bgp_adj_out_unset rn peer p afi safi GHOSTMODIF END 6 4 2 Modifying the VTY configuration environment Modifying the bgp protocol is not enough it has to be possible to enable and disable the new mod ifications also and option to show the debugging information has to be added To do this we have to 6 4 Modifications to the code of bgpd 87 do a small modification to the VTY code as we showed in previous chapters we just have to define the new commands and install them in the corresponding node First we will define two new commands in bgp_vty c one to activate bgp ghost flushing the ghost flushing rule and another to deactivate no bgp ghost flushing it GHOSTMODIF DEFUN bgp_router_GF bgp_router_GF_cmd bgp ghost flushing BGP_STR Enables Ghost Flushing Technique n char ret struct bgp bgp bgp vty gt index vty out vty 4 Ghost Flushing Enabled s VTY NEWLINE bgp gt ghost_flushing 1 return CMD SUCCESS DEFUN no_bgp_router_GF no_bgp_r
131. h 4210 ASpath 3210 Dt 32 g t 33 h t 61 ASpath ASpath W 342103 9 43210 ASpath ASpath f t 62 Figura 3 1 Ejemplo de informaci n fantasma creciendo en un escenario de fail down con un alto Egown En fig 3 1 podemos ver una topolog a de red clique con 5 nodos totalmente conectados Para entender la notaci n el n mero dentro del nodo es el n mero de AS al que pertenece El n mero a su 3 1 El Problema de la Convergencia 111 lado es el ltimo camino AS hasta el nodo 0 que ha anunciado El n mero dentro del cuadro es el camino AS que ser anunciado en el siguiente turno una w significa una mensaje de retirada El camino AS que est siendo usado en ese momento es el indicador ASpath Asumimos que es una red s ncrona en la que los eventos ocurren en turnos de 1 segundo Si un mensaje ese enviado de un nodo a otro llegar en el siguiente turno Ahora analizando lo ocurrido en este ejemplo En t 0 todos los nodos puede alcanzar al nodo 0 directamente pero entonces este nodo cae En el siguiente turno todos los nodos eligen un nuevo camino y quieren anunciarlo Miremos a lo que ocurre a uno de los nodos como ejemplo En t 1 el nodo 1 cree que otros nodos pueden acceder al nodo 0 por lo que elige al mejor Como todos tienen un camino de caracter sticas similares elige el de identificador menor 2 Entonces el nodo 1 los anunciar como nuevo camino usando 1 2 0 com
132. hdrawal end if end loop end loop GHOST CODE if GhostData is not empty then create UpdateMessage for each entry in GhostData loop if old path length gt last path length then add nlri to withdrawals in message end if end loop if withdrawals in message is not empty force send UpdateMessage to all peers end if end if GHOST CODE END Check if all the peers are still connected Execute external update with the list of withdrawals and advertisements generated 4 5 Modifications to SSFNet s BGPA for the Ghost Buster Rule 41 4 5 Modifications to SSFNet s BGP4 for the Ghost Buster Rule 4 5 1 Activating The Ghost Buster feature from the DML file The configuration file reading system was also modified Two configuration environments were modified the global configuration environment and the local configuration environment Assertions defined bgpoptions environment Overrides local setting e forceghostbuster true false forces the usage of this rule by all nodes e ghostdebug true false sets the debugging of messages of the ghost rule BGPSession environment e ghostbuster true false sets the usage of this rule 4 5 2 The main idea for the modification In this case modifying the protocol to make it comply with the Ghost Buster rule wasn t as easy as for the Ghost Flushing rule Following the strategy to implement the previous rule we tried to identify the main tasks needed for the Ghost Buster rule We
133. hdrawn rcvd UPDATE w attr nexthop 0 0 0 0 origin i rcvd UPDATE about 213 98 0 0 16 withdrawn send UPDATE 213 98 0 0 16 unreachable O COCCO CC o o W D N WO W 0 0 0 W Appendix H Digital Media Contents This report attaches a CD containing the software used modified and created in this project Also it includes this very same report altogether with the two presentations done for it So this are the contents src report show ssfnet ghost tar gz Raceways SSFNet 2 0 Simulator with the ghost flushing and ghost buster modifications on the BGP4 module ssfnet sim tools tar gz Programs developed to create run and analyze the simulations zebra 0 94 ghost tar gz GNU Zebra version 0 94 modified to use the ghost flushing rule zebra tools tar gz Collection of tools to generate configuration files for GNU Zebra and run them examplesBGP tar gz Example and log files of the anomalous behavior of NS 2 with BGP as it was sent to the developers e proyecto gf pdf The complete report of this Master s Thesis e proyecto gf eng ppt Powerpoint English presentation about this Master s Thesis e proyecto gf esp ppt Powerpoint Spanish presentation about this Master s Thesis RFCs Collection of RFCs related with this Master s Thesis RelatedDoc Articles Related with this Master s Thesis README txt Data media contents description 151 152 Appendix H Digital Media Contents O o
134. he chosen simulator SSFNet and finally the details about the modification of the BGP4 implementation of SSFNet Chapter 5 is a log of the simulations run about the BGP4 Parameters strategy cases Topologies simulated the results and their analysis in this section Chapter 6 summarizes the implementation procedure Choosing the routing software to be modified Zebra a schema of its architecture and a small analysis of the code and its modifications Also the testing procedures of the modified software are included Chapter 7 contains some reflections about the results of this thesis and their quality Chapter 8 shows what further work can be done about this project Chapter 2 BGP4 Routing Protocol and its Environment 2 1 Network Routing 2 1 1 Hop by hop Routing Nowadays and in the past many kind of networks have existed To make possible the exchange of data between them the Network Layer of the Network Stack Model was designed The standard Network level protocol used on the Internet is IP where each network owns a range of IPs and one IP identifies one host Then the role of the routers is to interconnect different networks if a host wants to connect to another one out of his network it ll do it through one router that connects the networks This router will see if it can directly reach the network where the destination is hosted If not it ll try to contact another router and then the process is repeated again until
135. host Flushing a small case that shows the convergence properties and models from small photographs of the Internet 29 110 208 409 nodes They show all the situations BGP4 has to deal with extreme theoretical cases Good and bad to examples extracted from the real world This cases will be detailed and shown in the next chapters Simulation Parameters The simulator can be configured to behave closer to reality or closer to the theory Both types of results are interesting The theoretical configuration can be used to confirm or deny the theory statements behind the proposed modifications to BGP4 The realistic setting obviously is needed before the modifications to be deployed A real scenario is always harder than the theoretical one But how can this be controlled SSFNet BGP4 implementation provides the following options e Random seed algorithm of every simulation The seed has to be different in each simulation so we get a good number os samples to be compared e The Jitter applied to all the timers used by the BGP4 protocol Activated when we want a more realistic simulation Deactivated otherwise e Split Horizon This technique is used by many real routing softwares Including Zebra To do tests showing how the modification proposals would work on existing routing softwares this feature has to be activated Applying proposals The versions of BGP4 that are going to be tested are Traditional BGP4 Ghost Flushing activated Ghost
136. hostBuster 30 150 Pd GhostBuster 50 100 50 4 pd 0 456 7 8 9 1011 12 13 14 15 16 17 18 19 20 Size Figure 5 27 Clique Fail Down time Jitter No Split horizon Clique Initial Fail Down Num Messages 9000 8000 7000 249000 7 BGP4 S 5000 GhostFlushing 8 GhostBuster 20 3 4000 GhostBuster 30 3000 gt GhostBuster 50 2000 1000 04 Te 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Size Figure 5 28 Clique Fail Down messages Jitter No Split horizon Set Up Since we get the same results as without using the jitter we won t make any more comment Fail Down The only big difference in the case of activating the jitter is that initially the distance between the rules and the traditional is smaller However the convergence tendency is the same For Egown is polynomial for the traditional BGP and constant for the rules 60 Chapter 5 BGP4 Cases Simulation 5 3 2 AltPath Topology 700 600 500 3 400 3 amp 300 v X Ra AltPath Initial SetUp Time KS BGP4 GhostFlushing GhostBuster 20 GhostBuster 30 gt GhostBuster 50 Figure 5 29 AltPath Set Up time Jitter No Split horizon 16000 14000 12000 10000 8000 Messages 6000 4000 2000 o Qd AltPath Initial SetUp Num Messages vd 2 amp BGP4 GhostFlushing Gho
137. i n con nueva informaci n de ruta Anuncio por tiempo de MRAI El valor recomendado para este temporizador es de 30 segundos Puede tambi n configurarse per destination En tal caso la limitaci n es no mandar m s de un mensaje sobre una NLRI en concreto a un vecino El valor recomendado en el RFC para este temporizador es de 30 segundos Jitter Todos los timers keep alive MRAI o inicializaci n deben aplicar un jitter aleatorio para evitar problemas por sincronizaci n i e colisi n de los mensajes de apertura u otras situaciones debidas a la disposici n de red Procesos de decisi n en el RFC 1771 28 tres diferentes procesos de decisi n son especificados El primero eval a los mensajes de actualizaci n y modifica si es necesario los RIB INs El segundo proceso de decisi n revisa los RIB INs y modifica el LOC RIB si es necesario Esto puede ocurrir por tres razones porque todas las referencias a un destino han sido eliminados de los RIB INs por lo que la ruta en el LOC RIB ya no es valida y debe ser eliminada Otra causa es que ahora hay una nueva ruta mejor en los RIB INs que sustituye a la existente en el LOC RIB Finalmente puede ser que un vecino haga un segundo anuncio sobre una mismo destino Retirada impl cita en tal caso la nueva ruta puede ser colocada en el LOC RIB Si es mejor que otras que ten amos Todos estos procesos se ejecutan en exclusi n mutua Retirada impl cita si un nodo cambia el camino que usaba par
138. ial name initialmessages name final name finalmessages corresponding to the four values calculated 3 Execution example sh multiextract sh a log output txt 4 Space used It uses the program buscafail tcl this program searches in a log file for all the values needed multimerge sh 1 Function Puts together all the data generated by the simulation in only one file 2 Parameters Name of the output Simulation name Topology e Versions of the protocols 3 Execution example sh multimerge sh report sim28H clique NORMAL GF 4 Space used It reads the files in tmp simulation Makefile 1 Function Run the simulation file creating a output file during the running time and using a memory limit specified to it 2 Parameters e DMLFICH Name of the origin DML fich NOMFICH Name of the output log file RUNTIME number of seconds to run the simulation In simulation time e MAXMEM number of memory megabytes at most to be used 3 Execution example make DMLFICH a dml NOMFICH tmp log txt RUNTIME 10000 MAXMEM 4000 It will run the SSFNet simulator with the a dml file The output will be written to temp log txt At Second 10000 of simulation it will stop even if there are events to happen and the Java machine only will be able to use 4Gb of memory 4 2 3 The Hardware A factor that made us decide for SSFNet was the hardware environment To our disposition were two personal computers Full dispositi
139. icaciones propuestas para BGP4 obtuvimos un claro ganador la regla ghost flushing Entonces era momentos de hacer una implementaci n sobre un software de encaminado real Necesit bamos un software gratuito y de c digo abierto mirando al mercado encontramos GNU Zebra Quagga GateD y OpenBSD s bgp Por diferentes motivos Memoria principal elegimos GNU Zebra como nuestro software de encaminado 6 1 Zebra como Software de Encaminado GNU Zebra es software libre y de c digo abierto que implemente una serie de protocols de encaminado Incluye los m s utilizado como BGP4 RIP v1 and v2 y OSPFv2 En el caso de BGP4 sigue las especificaciones en el RFC 1771 28 Una de sus caracter sticas m s atractivas es su enfoque modular Cada protocolo de encaminado es implementado en un demonio diferente siendo el demonio Zebra su uni n con la tabla de encaminado del kernel Esto hizo que modificar el demonio bgpd no implicase alterar nada m s en el software de encaminado que no tuviera que ver con el propio protocolo no interfiriendo para nada con otras funciones o protocolos 6 1 1 Funcionalidades Su caracteristicas m s importante es la modularidad cada protocolo es implementado en un demonio diferente esto implica parte de las varias ventajas de este paquete e F cil de modificar e Reparto de carga asim trico e Fiabilidad e Software gratuito y abierto item Totalmente adaptable Otros Detalles e Implementa los RFCs RFC 1771 28
140. icit withdrawal if one node learns a new path about a destination that substitutes the last one it announced and the MRAI timer is not expired it won t send a withdrawal Instead it will wait until it can send the new path This is called implicit withdrawal Choosing the best route for a destination is done in the second decision process It depends on the implementation and the policy of the institution administrating the AS but an example of the choosing criteria can be By importance order e AS Path Length e Metrics of the different Paths e The Local preference If there are many ways to reach a destination the destination can prefer to be accessed by one path instead of other e Other ones the administrators would want to implement Policies are also something to be considered Even if different ASs are physically connected and there are sessions between their BGP routers that doesn t mean they will exchange the routing information about all known destinations This is what is called the AS relationships 18 The Internet is a network owned by companies with economical interests Companies charge for carrying traffic or provide connection to other networks For example One AS would like to allow traffic from a neighbor to a certain destination but ban it to other Maybe because this neighbor has hired the company owning this AS to provide connection only to a set of destinations 8 Chapter 2 BGP4 Routing Protocol and its Envir
141. iempo de convergencia si un evento fail down ocurre Elonger Tiempo de convergencia si un evento fail over ocurre Eshorter Tiempo de convergencia si un evento shorter path ocurre 109 110 Cap tulo 3 Ghost Flushing y Otras Propuestas 3 1 2 Tiempo de Convergencia Elevado y la Informaci n Fantasma Como se muestra en algunos art culos 12 13 15 hay una fuerte relaci n entre la topolog a de red y el tiempo de convergencia Pero adem s otro factor cr tico en el fen meno del tiempo de convergencia elevado es el uso de temporizadores MRAI Despu s de cualquier cambio en la red siempre aparece la limitaci n de que un router BGP no puede mandar m s de dos anuncios Nueva ruta al mismo router en MRAI segundos Si son necesarios muchos anuncios el tiempo derivado de las esperas por el temporizador MRAI se acumula dando lugar a la mayor tiempo necesario para la convergencia Las propuestas tratadas en este trabajo y extra das de Bremler Barr et all 13 est n basadas tambi n en otra idea Una mentira es la ra z de otras muchas y en el mundo de las redes esto continua de manera recursiva Esto significa que si un nodo emite un anuncio basado en informaci n que ya no es v lida Aunque no lo sepa la actualizaci n enviada por dicho nodo contendr informaci n que tampoco es v lida Entonces otros nodos enviar n actualizaciones bas ndose en dicha informaci n y as hasta el final Despu s de alg n tiempo la informaci n f
142. igen si la ruta es interna a la AS o si ha sido recibida desde otra AS 101 102 Cap tulo 2 Protocolo de encaminamiento BGP4 y su entorno Inalcanzable si activa significa que el destino sobre el que este mensaje trata no puede ser alcanzado M trica entre ASs Siguiente Nodo el nodo donde empieza la ruta hasta el destino 2 1 3 El Protocolo Este protocolo utiliza conexiones TCP entre los nodos BGP4 para enviar los mensajes asociados El puerto utilizado por defecto es el 169 La raz n para utilizar TCP es simplificar todas las funciones de control de errores o env o de paquetes que complicar an en demasia BGP Esta decisi n fue inicialmente criticada por la poca consistencia de TCP en situaciones de congesti n de red Sin embargo las nuevas implementaciones de TCP incluyen funcionalidades que corrigen este problema Los mensajes enviados por este protocolo son de cuatro clases inicializaci n actualizaci n noti ficaci n y keepalive Las funciones de los mensajes son las siguientes Inicializaci n estos mensajes son usados en el establecimiento de sesi n entre dos nodos Es el primer mensaje enviado en dicha sesi n e incluye informaci n como e N mero de AS del router que env a el mensaje e Tiempo de hold utilizado para la funci n de keep alive e Un identificador la IP del interfaz desde el que se establece la comunicaci n e Informaci n de autenticaci n e Versi n de BGP utilizada Para
143. ink link link link link link mm TM ri TM m m m m rn 7 77017217 H attach attach attach attach attach attach attach attach attach attach P W W NDNDD RP SSF 0S BGP4 BGPSession basic ebgp neighbor as 2 address 1 5 use return address 1 2 basic ebgp neighbor as 3 address 1 5 use return address 1 3 basic ebgp neighbor as 4 address 1 5 use return address 1 4 basic ebgp neighbor SSF OS BGP4 Widgets BGPKiller name socket use SSF 0S Socket socketMaster name tcp use SSF OS TCP tcpSessionMaster use SSF OS IP name ip 0 virtual true 1 2 3 4 1 2 attach 2 1 1 1 3 attach 3 1 1 1 4 attach 4 1 1 1 5 attach 5 1 1 1 3 attach 3 1 2 1 4 attach 4 1 2 1 5 attach 5 1 2 1 4 attach 4 1 3 1 5 attach 5 1 3 1 5 attach 5 1 4 delay delay delay delay delay delay delay delay delay delay H H H H H H H H H 1 L LL O O O I LJ L3 L3 Appendix D SSFNet Simulation execution Makefile SHELL bin sh TOPDIR home gonrod 3 ssfnet include Makefile common JAVAC javac classpath SSFNET_TEST_CLASSPATH JAVA nice 19 java classpath SSFNET_TEST_CLASSPATH JAVANOTNICE java classpath SSFNET_TEST_CLASSPATH SCHEMAS TOPDIR examples net dml DICTIONARY home gonrod 3 ssfnet src SSF 0S BGP4 test dictionary dml MAXMEM 3900 TESTNAME withdrawals RUNTIME 10000 echo Simulation Time
144. l make an analysis of relevant parts of the BGP module implementation This analysis intends to be a guideline to future modifications to this module 4 3 1 Source Structure All the code concerning the BGP4 can be seen in fig 4 6 4 3 Analysis of SSFNet s BGP4 Implementation 33 src SSF OS BGP4 LocRIB java Abstract class implementing RIB data structure AdjRIBIn java AdjRIBOut java RIBElement java Damplnfo java InBuffer java Monitor java Route java Representation of route as it s received Routelnfo java All information about a route that BGP uses RouteInfoOOC java RoutelnfoIC java Debug java PeerEntry java Class representing the data used by a BGP instance referring to a BGP Peer WeightedInBuffer java BGPSession java Main class Implementing the BGP4 protocol algorithm Global java BGP Global configuration options src SSF OS BGP4 Comm BGP Messages Classes src SSF OS BGP4 Path Path Attributes Classes src SSF OS BGP4 Players Binary Data Treatment src SSF OS BGP4 Policy BGP Policy Implementation src SSF OS BGP4 Timing BGP timers and timed events src SSF OS BGP4 Util Internal Data Representation src SSF OS BGP4 Widgets Classes Used to implement simulation scenarios Session killers src SSF OS BGP4 doc Documentation src SSF OS BGP4 test Pre generated simulation scenarios used to verify the correct behaviour of the simulator Figure 4 6 SSFNet
145. l set up time failure number of messages and failure convergence time 4 Load control this simulations were run over department machines used by other university per sonnel The simulation launcher had to be modified to use more or less cpus from the system Concurrent simulations depending of the time of the day During office hours the load was lower than during nights or weekends 5 Machine job distribution the launch software would evaluate which machine was executing it and depending on that some tasks were executed This was done so the initial launch of the simulations was machine independent but the results were different in each machine 26 Chapter 4 BGP4 Simulation Environment The initial problems form simulating a big number of models And sometimes individually large were not always foreseen so a big part of this software Specially load control and post processing was developed from problems that appeared during this stage Software developed In this section we will show how the previous tasks were done Many versions of this software have existed and the evolution comes from problems and new needs that appeared during the simulations This chapter has the double function of listing the software developed an being a user manual for future users of it To develop this software two scripting languages were chosen Bourne Shell and Tcl The first one because of the pipe functionality really useful to modify and creat
146. lacement was kept because there can be more than one replacement on the locRib before the decision process phase 3 We have to take into account the length from the old route before any replacement and the length of the route that is in the LocRIB after all the decision process The place to insert the new withdrawals sending was easy We decided the best place was the third phase of the decision process decision process 3 In that moment the protocol decides how to spread the routes and withdrawals so we had just to modify a little bit If the old route was shorter than the one now on the LocRIB we send a withdrawal to all peers about the NLRI of those routes 4 4 1 Activating The Ghost Flushing feature from the DML file The configuration file reading system was also modified Two configuration environments were modified the global configuration environment and the local configuration environment The local assertions are used when we are generating the models from scratch So we generate the parts for each BGP4 node The global environment assertions will affect all the nodes and they are useful when working with pregenerated DML files In those cases modifying all the nodes can be long Assertions defined bgpoptions environment Overrides local setting e forceghostflushing true false sets the usage of this rule e ghostdebug true false sets the debugging of messages of the ghost rule BGPSession environment e ghostflushing true false s
147. lator Although this language can change depending on your needs but it also uses a special language to define the simulations situations DML This language allows to specify a complete network in all its parameters network layers and events It uses an object approach so dictionaries can be defined allowing to design extremely big networks easily so general network situations can be simulated on an Internet scale Also the BGP4 source code was revised and it was well structured and highly commented The presence of the JavaDoc was also considered as it represents an extremely useful tool to get to understand any java based implementation Again talking about the Java implementation it was seen as an advantage The department has 3 Sun machines and we were provided with a remote storage space Half a Gigabyte to keep our work We also had two slower PCs PIII and PII to use on the project So everything was connected It will be later described and we wanted to be able to run the same copy of the SSFNet in all the machines and Java was just perfect for that task 24 Chapter 4 BGP4 Simulation Environment Set up and usage If we compare this simulator with Ns 2 this step was much easier Independently of the machine it is only needed to uncompress the files and configure some environment variables to make it work The easiest way is to create a make file that sets the local environment variables and loads the corresponding DML file
148. low number of IPs CIDR support metrics links quality etc are only examples of things that routing protocols have to support and deal with Examples of this protocols are RIP OSPF IGRP EGP or BGP 2 1 3 Exterior Interior routing At the beginning of the 80s all the routers in the Internet shared their reachability information between them At the same time the size of the network kept growing unstoppable This led to the following problems 20 e Overhead due to the exchange of routing information between all the routers Any moment a link would go down that could trigger a ripple of routing messages flying all around the network e Many routers meant many different softwares making sometimes fault control impossible e Changing versions of the routing softwares was difficult because it would affect the whole network the model was rigid and inflexible So at this point it was decided that to split the internet into parts Autonomous Systems AS that would comprise a set of networks administrated by the same institution Also two kind of relationships between routers was defined depending on their situation Between routers on the borders of different ASs external routing Between routers of the same AS internal routing Routers that were not border routers but in different ASs wouldn t exchange information From this point routing protocols were also divided in external routing protocols EGP for the border routers
149. ly Or almost in today s Internet This chapter is mostly based on the BGP description on Routing on the Internet 20 and the RFC 1771 28 2 2 1 Path Vectors and Loop Detection The approach to the path vector idea in BGP4 is quite radical Each update message about a route includes a list of all the ASs which that information has traversed through When this information will be repeated to other routers the number of the emitting router s AS will be added at the beginning of this AS list This is the way this path vector is constructed This list of ASs is known as AS Path The path vector has a clear function loop detection One of the main problem of other routing protocols are the loops in network topology For example for RIP However with the AS paths a router can check if its AS number is on the list If it is it will discard the router if not it will accept it put its AS number and retransmit it This technique has also drawbacks The main problem is that the complete list of crossed ASs about a destination is stored in the memory of all routers and sent on every update message This means memory cost and message overhead Some studies 20 state that with BGP3 100 000 networks an average path length of 20 ASs and a total number of 3000 ASs transmitting a complete routing table would mean 520 000 bytes of bandwidth Talking about memory occupation for a router this figures can be exceeded by far However this problem
150. mal Distribution ee White GhostBuster Delta20 Fail Down Time KS Test p value 0000 100 80 60 Observations 40 20 o 8 310 lt 26 7 to 91 to lt 175 lt 359 100 2 Convergence Time Figure 5 20 White Fail down time no Jitter No Split horizon Normal Distribution A AUS White GhostBuster Delta30 Fail Down Time KS Test p value 0000 100 80 jo 3 o Convergence Time Figure 5 21 White Fail down time no Jitter No Split horizon 5 2 Simulation Results Split horizon disabled No jitter 57 Normal Distribution Mean 20 005 i i i SUD SE dig White GhostBuster Delta50 Fail Down Time KS Test p value 0000 100 E 2 5 60 E i E 40 20 0 IEEE EN 8300 50 0 58410 91710 16 7 58 4 667 100 1 Convergence Time Figure 5 22 White Fail time down no Jitter No Split horizon Fail Down time Since showing the histogram result of all the values studied would be too long we will just show the values about the Egown As we noticed the rules behave much better than the original BGP4 The values that appear the most are much lower 5 2 5 Bad Case Bad Normal Fail Over Time 100 Observations 40 62 to 148 to lt 69 6 lt 153 8 Figure 5 23 Bad Fail over time no Jitter No Split horizon 58 Chapter 5 BGP4 Cases Simulation 100 Bad Ghost Flushing Fail Over Time 92 to lt 100 8
151. mers and video tapes To make all this work we needed some new classes including a new type of timer that triggered the appropriated event inside the FSM DeltaTimer It is created and associated to a route when the route arrives When it expires produces a message that we had also to write Another class DeltaTimeout Message This message carries a reference to the route triggering the event so the handle_event knows what to do To keep in a data structure all the timers together with the cross references between them and their routes we created the BusterRoute class It helps managing the creation and manipulation of the timers Finally to index all the BusterRoute instances in the class representing every peer there is a instance of the ListBusterRoute class It consists of a hash table indexed by the NLRI of the route and some methods to make our life a little bit easier 4 5 3 Making this complex schema work Now we are going to try to show how is the life of a route since its received until it is sent to other peers the new route lifecycle Considering the complexity of this modification we ll only include what is different from the Ghost Flushing rule Route arrives and the protocol tries to send if but delta timer is not expired This schema can be found in fig 4 9 42 Chapter 4 BGP4 Simulation Environment UpdateMessage handle event Put Route handle update decission process 1 New Removed and Replaced
152. messages n bm gt ghost debug 0 vty out vty BGP Ghost Flushing debugging disabled s VTY_NEWLINE return CMD SUCCESS ALIAS no debug bgp gf undebug bgp gf cmd undebug bgp ghost flushing UNDEBUG STR DEBUG_STR BGP_STR Ghost Flushing messages n GHOSTMODIF END Now again we have to alter the function installing the nodes so the commands are installed in the proper nodes GHOSTMODIF install_element ENABLE_NODE amp debug_bgp_gf_cmd install_element CONFIG_NODE amp debug_bgp_gf_cmd install_element ENABLE_NODE amp no_debug_bgp_gf_cmd install_element CONFIG_NODE amp no_debug_bgp_gf_cmd install element ENABLE NODE amp undebug bgp gf cmd GHOSTMODIF END Looking to fig 6 11 we can see where the commands have been placed and how to reach them to activate the ghost flushing rule When we are witting the configuration file for the bgpd daemon to activate the ghost flushing we just have to add bgp ghost flushing after the router command To activate the debugging just debug bgp ghost flushing Adding no at the beginning of any of this commands will cancel their effect router bgp ASnumb bgp ghost flushing configure terminal no bgp ghost flushing SS Ss bgp ghost flushing undebug bgp ghost flushing no debug bgp ghost flushing enable Master Environment Figure 6 11 This is the VTY node tree with the new commands 6 5 Tests 89
153. mmand line parameters passed when the daemon is invoked are processed Then memory allocation for the future initializations Following the creation of the bgpd structure bgp init it includes the invocation of the configuration VTY environment After that the main function continues The most important points For this work are two First the configuration file is read an passed through the VTY interface It means that the configuration file are just VI Y commands feeded to the terminal system here This also means that modifying the configuration system for the file and the terminal are the same thing The second important point is the end of the main function It s the starting of the FSM and the eternal execution of the main thread Start finite state machine here we go while thread fetch master amp thread 281 thread call amp thread This piece of code is executing all the time the threads associated with all the events inside bgpd bgp_main c main gt bgp_master_init V struct bgp_master inicialization Command line parameter process gt bgp init V bgp vty init V General struct bgpd Inicializations signal init cmd init 1 vty init memory init bgp vty c sort node gt VTY nodes ordenation vty read config gt Reads the configuration file and passes the assertions on it through the VTY interface
154. n provistas por route reflector para todo el sector Este route reflector es simplemente otro router BGP4 qu est conectado a los routers del borde Puede ser un router de borde l mismo y otros route reflectors 106 Cap tulo 2 Protocolo de encaminamiento BGP4 y su entorno Router Cliente a Router Cliente o Router Er Cliente Figura 2 3 Ejemplo de una configuraci n de Router Reflectors Otra posibilidad son las Confederaciones 25 La idea es o bien agrupar varias ASs en una AS virtual mayor o dividir una en otras menores En caso de BGP externo o interno De esta manera evitamos las excesivas conexiones de un modelo totalmente interconectado 2 2 Relaciones entre Sistemas Aut nomos Este trabajo trata sobre los problemas de BGP4 en algunas topolog as de red en este cap tulo intentare mos mostrar algunos ejemplos de la relaciones BGP m s t picas que se pueden entontar tal y como son descritas en 18 Este cap tulo resena partes de este art culo importantes para este trabajo En cap tulos posteriores relacionaremos estos ejemplos con la situaci n problem tica Provider n Router Forbbiden Router Traffic a Router AMM Allowed Traffic Figura 2 4 Filtros aplicados 2 2 Relaciones entre Sistemas Aut nomos 107 Estas relaciones existen por una serie de razones en primer lugar la topolog a de red como las diferentes ASs
155. n aspecto atractivo El nico problema es que por muy bueno que sea el software nunca superar a 129 130 Cap tulo 7 Conclusiones Y Discusiones un router empotrado Es decir una colecci n de hardware y software espec ficamente disenada para encaminar informaci n Sin embargo GNU Zebra siempre ser m s barato Sobre la implementaci n de ghost flushing fue f cil de hacer Aunque no de saber como hacerla y parece funcionar Nuestros tests adem s muestran un buen rendimiento Un comentario adicional sobre GNU Zebra gira alrededor de la documentaci n existente Hay mucha documentaci n sobre su estructura general sin embargo no existe nada disponible sobre como han sido implementadas las diferentes funcionalidades de los protocolos Teniendo en cuenta que el paquete est desarrollado en C analizar el c digo para averiguar como funcionar no es la operaci n m s sencilla del mundo GNU Zebra comparte un problema que muchos paquetes de c digo abierto sufren suelen estar bien comentados pero aunque el c digo se publique la documentaci n de desarrollo asociada se mantiene en privado Esto limita en muchos casos la posible colaboraci n de muchos desarrolladores ante el problema de emplear m s tiempo analizando el c digo hecho que desarrollando Como fue el caso en este proyecto Por ello la documentaci n de este proyecto Memoria completa intenta ser un pequeno mapa de como algunas de las funciones de BGP4 est n implementadas
156. n the appendix F pictures of the lab and the switch can be found 90 Chapter 6 Applying the Ghost Flushing Rule to Zebra Routing Software office A3019 lab A1203 130 240 x x 192 168 0 1 Office computer 130 240 x x 192 168 0 2 Control Traffic 130 240 x x 192 168 0 7 VLAN1 P sun vin Figure 6 12 Two LANs one for the BGP4 traffic y the control Traffic The system was set in this way Zebra files were stored in a University managed remote file system This allowed us not to worry about security copies or hard drive faults that would mean critical data lose Since our machines were administrated by ourselves we could not mount NFS exports from this server University policy However It was also exported using SAMBA so we remotely mounted this files in every computer using SAMBA clients Configuration files All the scripts needed to set up the samba mounting were stored in one machine bgpl This one would export them by NFS to all the other machines Compiling was always done by bgpl The most powerfull of the machines All the files source and binaries were stored in the remote SAMBA file system Exports NFS root usr local etc rc d Compiling bgp1 G bart sm luth se bgp2 SAMBA GNU Zebra Source bgp7 Binaries ecc
157. n the simulation options Split horizon and Jitter and the topology I To use it the way is using the same make file that with the simulations but with the view method 5 2 Simulation Results Split horizon disabled No jitter 51 5 2 1 Clique Topology Clique Initial SetUp Time 140 120 100 2a BGP4 80 4 GhostFlushing GhostBuster 20 60 4 2 GhostBuster 30 gt GhostBuster 50 40 Seconds 20 4 5 6 7 8 9 1011 12 13 14 15 16 17 18 19 20 Size Figure 5 6 Clique Set Up time no Jitter No Split horizon Clique Initial SetUp Num Messages 16000 14000 JA 12000 7 10000 BGP4 gt E GhostFlushing 2 8000 GhostBuster 20 3 S K GhostBuster 30 6000 gt GhostBuster 50 4000 2000 04 45 6 7 8 9 10111213 14 15 16 17 18 19 20 Size Figure 5 7 Clique Set Up Messages no Jitter No Split horizon Clique Fail Down Time 600 500 400 4 BGP4 GhostFlushing 9 300 GhostBuster 20 n Pd E GhostBuster 30 200 gt GhostBuster 50 100 4 456 7 8 9 1011 12 13 14 15 16 17 18 19 20 Size Figure 5 8 Clique Fail Down time no Jitter No Split horizon Set Up Since the ghost flushing technique doesn t alter the setup situation in a clique No update to longer paths the results are the same for messages and tim
158. nalities included in other RFCs like Route Reflection and Confederations 30 25 and route damping 16 It is also IPv6 aware it can work in both ways IPv4 and IPv6 About the operating system it supports FreeBSD NetBSD OpenBSD GNU Linux over IPv4 and IPv6 There are plan to support also Solaris Also the list of routing protocols included is BGP 4 RIPv1 RIPv2 OSPFv2 and OSPFv6 The configuration system tries to clone the notation used on the Cisco routers This is an advantage in case of previous experience with that brand It can be configured in a terminal way and it includes and shell interpreter vtySh that makes possible writing configuration scripts for the Zebra software since we can write the terminal commands in a text file and send them directly to the zebra daemons Also it shows some disadvantages Obviously if not Cisco would be out of business In the first place its modular architecture doesn t allow a communication between its routing protocols as fast as in a monolithic approach The communication functions rely on sockets This problem also extends to the kernel routing table it cannot compete with other options like embebed routers 6 1 3 Setting Up a Zebra BGP speaker In this section we will try to create a small guide line of how to build a BGP speaker with a personal computer First we chose the operating system FreeBSD is commonly accepted as one of the strongest free Unix Linux option for networking work so
159. no para BGP otro para OSPF y otro para RIP bgpd aprende la ruta A a trav s de sus sesi n BGP Despu s de realizar sus funciones y elegirla como ruta env a dicha ruta al demonio Zebra usando el protocolo Zebra Entonces este demonio actualiza las tablas de encaminado del kernel y env a la ruta a los dem s demonios Internal Routing Daemon Kernel Routing Tables Figura 6 1 Estructura modular de GNU Zebra Todo acaba pasando por el demonio Zebra Algo muy interesante sobre este enfoque es que no hay necesidad de que todos los demonios est n en la misma m quina repartiendo as la carga Una m quina podr a hacer de router BGP4 pero no de encaminador para la red Otra m quina tendr a el demonio Zebra por lo tanto sus tablas estar an actualizadas A trav s de los sockets ambos demonios se comunicar an a trav s de la red Dividimos la carga de las funciones de BGP y de encaminado a diferentes m quinas Que pueden tener diferentes configuraciones de software hardware 6 3 Tests 127 6 3 Tests 6 3 1 Tests y resultados Durante esta fase ten amos dos objetivos e Comprobar si la implementaci n de ghost flushing realizada sobre Zebra se comportaba como deb a Correcci n e healizar pequenas pruebas de rendimiento para ver si la mejora te rica aparec a en la realidad Correcci n de la Implementaci n Para este prop sito utilizamos la topolog a de clique de 5 nodos del mismo modo que la usamos para
160. nterface id 5 Net id 4 AS status boundary router id 1 graph ProtocolSession name bgp use SSF 0S BGP4 BGPSession autoconfig false connretry time 120 min as orig time 15 ghostflushing true reflector false neighbor as 1 address 1 4 use return address 1 1 _extends basic ebgp neighbor neighbor as 2 address 1 4 use return address 1 2 _extends basic ebgp neighbor neighbor as 3 address 1 4 use return address 1 3 _extends basic ebgp neighbor neighbor as 5 address 1 4 use return address 1 5 _extends basic ebgp neighbor ProtocolSession name socket use SSF 0S Socket socketMaster ProtocolSession name tcp use SSF OS TCP tcpSessionMaster ProtocolSession name ip use SSF OS IP interface id O virtual true interface id 1 interface id 2 interface id 3 id 5 r3 r3 m m m aaa uu uuu interface Net id 5 AS status boundary router id 1 graph ProtocolSession 142 Appendix C DML 5 nodes clique scenario name bgpkiller use kill 5000 ProtocolSession name bgp use autoconfig false connretry time 120 min as orig time 15 ghostflushing true reflector false neighbor as 1 address 1 5 use return address 1 1 extends neighbor extends neighbor extends neighbor extends ProtocolSession ProtocolSession ProtocolSession interface interface interface interface interface link link link link l
161. nviarla aunque el temporizador delta no ha expirado DeltaTimerExpired DeltaTimeoutMessage Route PEER Class handle event F 1 AdjRIBIn Delta Timer associated to route It receives the route whose timer triggered the event Creates a list of announcements 1 with the route ListBusterRoute If the route was in LocRIB it executes external update announcements routes with delta timer expired external update UpdateMessage Ty send update e OQ NM of this Figura 4 3 Temporizador Delta Timer Expira Cap tulo 5 Simulaci n de Casos de BGP4 Este cap tulo es un resumen de su hom logo en la memoria principal Para m s detalles sobre el m todo de simulaci n escenarios y resultados m s detallados acudir a dicha memoria 5 1 Comparando todas las t cnicas All Techniques Compared BGP4 SH Jitter GF SH Jitter 4500 GB 20 SH Jitter 4600 GB 30 SH Jitter GB 50 SH Jitter 3500 BGP4 SH GF SH 3000 GB 20 SH GB 30 SH E 2500 4 GB 50 SH i sio pa BGP4 Jitter GF Jitter GB 20 Jitter GB 30 Jitter GB 50 Jitter BGP4 GF GB 20 GB 30 GB 50 1500 1000 500 Figura 5 1 Multi Egown En la memoria completa comparamos todas las t cnicas junto con el protocolo BGP tradicional en muy diferentes situ
162. o de convergencia las relacionadas cono medios muy interconectados Intentaremos corregir el problema siguiendo las propuestas del art culos sobre Ghost Flushing 13 Otra situaci n que merece la pena ser estudiada es qu ocurre con la informaci n fantasma y el caso fail over Miremos el ejemplo como podemos ver en fig 3 2 la informaci n fantasma no es eliminada del sistema hasta que el nuevo camino atraviesa todos los nodos del camino alternativo Como podemos ver en este ejemplo es un tiempo elevado 3 2 4 3 4 4 A RL d i 3 N 3d A I 2 p 1 2 31 x 1 0 1 0 c t 31 d t 61 e t 91 f t 121 Figura 3 2 Informaci n fantasma extendi ndose en el escenarion fail over 112 Cap tulo 3 Ghost Flushing y Otras Propuestas 3 2 Regla Ghost Flushing 3 2 1 Como Funciona La idea detr s de la regla ghost flushing es intentar eliminar la informaci n fantasma lo antes posible Esta modificaci n del protocolo BGP4 quiere evitar cualquier alteraci n de los mensajes utilizados hasta ahora por el protocolo o cualquier medida que implica un alto consumo de CPU memoria en los routers Qu podemos hacer entonces Identificaci n de la informaci n fantasma Si cambiamos el camino elegido para alcanzar un cierto NLRI a un camino peor significa que el camino antiguo ya no es v lido es informaci n fantasma Pudimos haber anunciado este camino antes as que hemos creado informaci n ahora fantasma Ac
163. o 000000 0o OI BB W W O R p send send rcvd rcvd rcvd rcvd rcvd rcvd rcvd rcvd send send send rcvd rcvd send send rcvd rcvd rcvd rcvd send send rcvd rcvd rcvd rcvd send send rcvd rcvd rcvd rcvd rcvd rcvd Appendix G GNU Zebra log file example after node 7 has gone down Ghost flushing rule was UPDATE UPDATE UPDATE UPDATE UPDATE UPDATE UPDATE UPDATE UPDATE 213 98 UPDATE UPDATE UPDATE UPDATE 213 98 UPDATE UPDATE UPDATE 213 98 UPDATE UPDATE UPDATE UPDATE UPDATE 213 98 UPDATE 213 98 UPDATE UPDATE UPDATE UPDATE UPDATE UPDATE UPDATE UPDATE 149 213 98 0 213 98 0 w attr about 213 98 0 0 16 w attr about 213 98 0 0 16 w attr about 213 98 0 0 16 w attr 0 0 16 213 98 0 213 98 0 213 98 0 w attr 0 0 16 213 98 0 213 98 0 w attr 0 0 16 w attr 0 16 unreachable 0 16 nexthop 0 0 0 0 origin i withdrawn nexthop 0 0 0 0 origin i withdrawn nexthop 0 0 0 0 origin i withdrawn nexthop 192 168 0 2 origin 0 16 unreachable 0 16 0 16 nexthop 192 168 0 3 origin 0 16 0 16 nexthop 192 168 0 5 origin nexthop 0 0 0 0 origin i about 213 98 0 0 16 withdrawn 213 98 0 213 98 0 w attr 0 0 16 w attr 0 0 16 213 98 0 213 98 0 w attr 0 16 0 16 nexthop 192 168 0 3 origin nexthop 192 168 0 4 origin 0 16 0 16 nexthop 0 0 0 0 origin i ab
164. o 110 0 Computer Office Editting Connected to all the machies Figure 6 13 Exporting files 6 5 Tests 91 6 5 2 Testing means Programming To save time during the creation of the configuration files for all the nodes some small programs were written We defined a file format that would allow us to define all the bgp configuration for all the nodes Then a program would read the file and generate the configuration files for all the machines Then the script that starts the bgpd would identify which machine was running the script and feed bgpd the corresponding to the bgpd Configuration File Format Here we can see the file format Number of nodes n Triangular half square matrix indicating the BGP connection between the nodes Size n N entries with IP of the BGP4 interface GF if ghost flushing activated N entries with Number of networks exported Network address Network address An example of a 5 nodes clique all the nodes with ghost flushing Node 5 exports the network IP range 213 98 0 0 16 5 0 10 110 1110 11110 192 168 0 1 GF 192 168 0 2 GF 192 168 0 3 GF 192 168 0 4 GF 192 168 0 5 GF 0 10 0 0 1 24 0 0 0 1 213 98 0 0 16 GenConfZ tcl 1 Function Creates the configuration files for the nodes The name for the files will be bgpd conf number of node 2 Parameters Name of the topology file to be read Arranca sh Para sh The first script
165. o be done So it relies on simple rules to work In fig 3 3 the enunciate of the rule can be found In the functioning of this proposal two clear tasks can be found Identifying Ghost information If the path to a NLRI is updated to a worse destination it means that the old path is no longer valid it is ghost information We may have announced this path before so ghost information exists Action to be taken The first option is to send immediately a new update containing the new path Implicit withdrawal But this may be not possible because of the MRAI limitation however a withdrawal still can be sent flushing the ghost information generated by us that is not longer valid The withdrawal messages have a different meaning from the one that classic BGP4 gives Before a withdrawal message meant that a node doesn t have any path the withdrawn destination Now 16 Chapter 3 Ghost Flushing and other Proposals under the ghost flushing rule a withdrawal message means that the previous AS path advertised about a certain destination is no longer valid A router may have a route to a destination and still send a withdrawal about it When the distance to destination dst is updated to a worse ASpath AND a minRouteAdver time did fot elapse since the last annOuncement then send withdrawal dst to GhostFl shing all neighboring BGP peers Rule Figure 3 3 Ghost Flushing Rule Now let s show in an graphical example how it works In fig 3
166. o camino AS Este es el primer ejemplo de informaci n fantasma nacida de otra informaci n fantasma El nodo 1 no sabe que el nodo 2 no puede acceder al nodo 0 tampoco por lo tanto est tomando decisiones fundament ndose en informaci n ya no v lida Pero sigamos observando lo que ocurre despu s El resto de los nodos han hecho lo mismo pero eligiendo al nodo 1 como siguiente salto para alcanzar 0 El nodo 1 se dar cuenta de esto en t 2 y enviar inmediatamente un mensaje de retirada a todos los nodos Sin embargo es demasiado tarde en t 3 todos los nodos conocer n que el nodo 1 no puede alcazar a 0 y elegir n otro camino Pero ya habr n enviado una ruta fantasma un segundo antes y no podr n enviar un nuevo anuncio hasta que el temporizador MRAI no expire Casi 30 segundos Cuando pase ese tiempo volver n a anunciar una nueva ruta esta vez eligiendo 2 como pr ximo salto es decir m s informaci n fantasma El proceso se repite y la espera de 30 segundos reaparece As sucesivamente hasta que toda la informaci n termina por desaparecer En este ejemplo se puede apreciar como la combinaci n de una topolog a altamente interconectada la limitaci n MRAI y la informaci n fantasma tiene como consecuencia un alto tiempo de convergencia 60 segundos Un tiempo demasiado alto para algunos servicios de tiempo real que funcionan sobre la red de redes ste es el problema a estudiar por este trabajo de todas las situaciones de alto tiemp
167. o grandes y las de clase C demasiado peque as as que las redes de clase B se convirtieron en una soluci n muy popular para toda clase de organizaciones conectadas a internet Demasiado popular de hecho Llego un momento en el que casi todas las direcciones de red de clase B hab as sido asignadas pero se demandaban m s Las direcci n de 2 1 Descripci n del Protocolo BGP4 Protocol 105 clase C eran demasiado pequenas y solo hab a 256 redes de tipo A Un peligro real de sobreocupaci n de direcciones apareci Clase Bits de Red Bits de Host Hosts por Red A 8 24 16 777 214 B 16 16 65 534 C 24 8 254 Figura 2 2 Distribuci n de clases IP Adem s como el n mero de rutas conectadas se incrementaba constantemente las tablas de encam inado se hicieron m s y m s grandes dentro de los routers Esto ten a un doble efecto de incrementar tanto el uso de memoria como la carga en CPU para manejar tablar mayores Este problema podr a afectar al tiempo de respuesta en caso de fallo en Internet Classless Addressing Route Aggregation y BGP4 como un Protocolo de Encaminado entre Dominios Las direcciones sin clase se componen de una IP completa y una m scara de red Dicha m scara indica que bits de la IP pertenecen a la direcci n red y cuales al host De este modo podemos dividir redes A en redes m s pequenas y unificar redes C contiguas para formar otras m s grandes Del mismo modo podemos definir r
168. o the GhostData data structure announcements n N If the MRAI timer is not expired n n yet we forcefully send a l nlri on the LocRIB withdrawal to all peers including If the replaced route was shorter we all the NLRIs that are inside check if there was an entry in the the GhostData structure GhostData structure If there was we Sending Witdrawals update the length for the new route if not we add a new entry to Ghost Data announcements routes and withdrawals external_update Figure 4 8 Ghost Flushed Update Process in SSFNet s BGP Schema 2 Code for the GhostNLRI type class GhostNLRI Domain the ghost info is about public IPaddress NLRI Length of the first AS path for the NLRI public int oldPath Length of the longest AS path fot the NLRI public int longPath Length of the path that actually will remain on the loc rin public int lastPath Method GhostNLRI It creates an instance of the Class public GhostNLRI IPaddress IP int length 1 NLRI IP oldPath length longPath length lastPath length Method NewPath It takes in consideration that a new path about this NLRI is being treated in the update process Decission process It returns if the lastPath would be worse thant the first one public boolean newPath int length 4 4 Modifications to SSFNet s BGP4 for the Ghost Flushing Rule 39 1 lastPath length if lastPath gt longP
169. ociated to route timer triggered the event Creates a list of announcements with the route ListBusterRoute If the route was in LocRIB it executes external update announcements routes with delta timer expired external update UpdateMessage TY send update TIN of this Figure 4 10 Delta Timer Expires msg UpdateMessage to sent Senders Addresses of the original advertisers of each route on the message Peer peer to whom we want to send the message GHOST CODE if route to be sent in message has not its delta timer expired then extract route from UpdateMessage end if GHOST CODE END Code initializing Timers when this method is run for the first time if MRAI not expired yet then Eliminate withdrawals about nlri that is refernced by the routes on the updatemessage Implicit withdrawal Update Waiting lists If a route is going to be withdrawn eliminate it from the waiting lists Put the routes from the message in the waiting list MRAI is not expired yet Eliminate those routes from the UpdateMessage Send UpdateMessage Return end if Eliminate withdrawals about nlri that is refered by the routes on the updatemessage Implicit withdrawal Update Waiting lists If a route is going to be withdrawn eliminate it from the waiting lists Send UpdateMessage 44 Chapter 4 BGP4 Simulation Environment handle event 1 Function Handle both external and internal events Modelates the
170. ode will die at second 5000 of simulation They run ghost flushing and ghost buster with a delta timer of 50 4 Space used None 5 Response On the standard output will write a topology file of the structure before specified creaDML tcl 30 Chapter 4 BGP4 Simulation Environment 5 Function Converts a topology file specified before into a DML file to be used by SSFNet simulator Parameters e Topology File Name File name to read the topology information from e Random seed Random seed used by SSFNet simulator to be included on the DML file e Type of simulation It can take the values of sim1 No Random no jitter sim2 Random No jitter sim3 No Random Jitter sim4 Random Jitter sim2SH Random no jitter Split horizon activated sim4SH Random Jitter Split horizon activated Execution example tcl creaDML tcl topology txt lacasito seed sim2SH gt file dml DML file with the topology and ghost rules options on topology txt Simulation options Random activated jitter deactivated and split horizon activared Space used e bgpOptions txt simulation parameters name Containing DML commands to specify the type of simulation Response On the standard output the out dml file will be listed adaptDML tcl 1 5 Function Adapts a DML file to use the options specified in the parameters The death time and the dying node are specified in the original file It may depend on each case and on
171. odes of a clique of size n 5 It has a big theoretical interest however such situations appear on the internet parts of the network highly interconnected that also have a long alternate path Nomad paths 12 connecting two nodes Sizes from 10 to 30 nodes Convergence Times studied E and Eup Interest Theoretical and slightly practical 4T 48 Chapter 5 BGP4 Cases Simulation o x Figure 5 2 Alternate Path scenario of 11 nodes The alternate path has 5 nodes 5 and the cligue 6 n 2 5 1 3 White model This topology is taken from 13 It is a simplified model of a network configuration found on the internet It is more practical than previous examples but still simplified so it s still slightly theoretical It is also similar to a topology found on 12 Since we don t have similar models to this one from different sizes the data will be shown in an histogram style Size 8 nodes Convergence Times studied Edown and Eup Interest Practical and slightly theoretical Figure 5 3 White topology 5 1 4 Bad model This topology is the bad extreme case for the ghost flushing rule The idea of simulating this case is to see how bad is actually compared with the traditional BGP4 It was also extracted from 13 As in the white model we will show the data in a histogram style The property a topology has to comply to be similar to this is e There is a node A that provides to a node B
172. odifications of GNU Zebra 6 2 1 Modules Daemons and Sockets As we have pointed out before Zebra is a extremely modularized software Every task is run by a different daemon Routing tasks are owned by one different daemon per routing protocol Also the function of exchanging routing information with kernel routing tables and the protocols is also done by an exclusive daemon This helps to divide the code depending on the functions it has to do on complete different modules The communication between daemons runs over sockets and the protocol used is called Zebra Protocol Let s make a small example In fig 6 1 we have a zebra working with three daemons one for BGP other for OSPF and another for RIP bgpd learns Route A through its BGP session with other router After doing the BGP procedures around this route it chooses it and wants to use it So bgpd daemons sends it through a socket to the Zebra daemon bgpd all the routing daemons and Zebra talk a common language Zebra Protocol So bgpd uses the Zebra Protocol to transmit Route A to the Zebra Daemon Then the Zebra daemon will put the route in the kernel routing table and distribute between the other routing daemons for example ripd the one for RIP Again to do this the Zebra daemons uses the Zebra Protocol Then ripd can spread the learnt route between the hosts it can reach using RIP Internal Routing Daemon Kernel Routing Tables Figure 6 1 Zebra modular structure
173. odos 7 2 La regla Ghost Flushing Como las simulaciones y los tests sobre Zebra muestran es bastante efectiva Tine varios puntos positivos e Bajo Consumo de CPU no hay algoritmos complejos en esta regla esto tiene un impacto casi nulo en la CPU e Bajo uso de memoria De hecho no hay ningtin uso extra Para la regla ghost buster esto era un problema porque necesitaba crear temporizadores con su memoria asociada para cada ruta recibida e No informaci n extra en los mensajes que pueda llevar a incompatibilidades con el BGP4 convencional e Buen rendimiento como se ve en el cap tulo de simulaci n y test de GNU Zebra En total podemos decir que la regla ghost flushing es bastante efectiva y una f cil modificaci n de BPG4 Desde nuestra humilde posici n recomendar amos la implementaci n de esta regla en los actuales softwares de encaminado al igual que nosotros hicimos con GNU Zebra 7 3 Software de Encaminado GNU Zebra Es GNU Zebra una opci n real como software de encaminado Mirando a nuestra propia experiencia la opini n de algunos expertos 34 y la comunidad de usuarios que posee podr amos decir que s siempre y cuando necesites un router barato Implementa todas las RFCs relacionadas con BGP4 y los protocolos principales de encaminado Su estructura modular lo hace fiable y f cil de diagnosticar en caso de fallo La posibilidad de poder modificar su c digo para ajustarlo a nuestras necesidades le da u
174. ogging to table dumps after every update 1 An example of the Zebra BGP configuration files can be found in the Appendix 21 22 Chapter 4 BGP4 Simulation Environment Setting NS 2 and BGP The TCL C combo is also one of its weaknesses Since this simulator runs over C it has to be compiled in the machine it is going to run on Also it only works properly with a set of versions of the applications it needs TCL between them We tried to make this program run on a department time shared Sun machines but the version of Tcl that came with Solaris 9 was not compatible Changing the TCL version wasn t an option It is a department administrated machine So we had to set up a stand alone machine just for ns 2 A much slower one and with much less memory After successfully compiling the ns 2 it was moment to add the BGP 4 module The installation included to apply a patch to the NS 2 simulator and then the first problems appeared It wasn t compatible with the latest version of NS 2 so we had to jump back to an older version of ns 2 and start again After applying the path Ns 2 had to be recompiled but it took some extra time due to some problems between the patch and the simulator After many unsuccessful compilations we made them work together Then it was the moment to learn how to use the simulator We found a good tutorial 6 and the first thing noticed was that there were some bugs in a ftp transfer simulation It was part of
175. on and three department machines Really careful disposition All of them mounting a remote file system where the simulator and results were stored The department machines were faster and had much more memory so we chose these ones to run our simulations on They were three machines with the same features here are the some of the specs Names sigmal sm luth se sigma2 sm luth se sigma3 sm luth se Model name Sun Fire V480 Server 10 CPU Four CPUs 1 2 GHz UltraSPARC III Cu RAM Memory 16 Gigabytes 32 Chapter 4 BGP4 Simulation Environment Operating System Sun Solaris 9 This simulations were stored in a department store server named claudius sm luth se All the machines had the same account mounted so they all stored their results in the same space while they used their own tmp directory to store the enormous temporary log files generated by the simulations In fig 4 4 we can see a schema of the system Also in fig 4 5 we can see a actual photo of the servers sigma1 Te ha 17 2 ge i s sigma2 gt L oc I Account Amp O 512 Mb A O a 27 os _ E sigma3 o Max output 1 12 concurrent simulations Figure 4 5 LTU s Dator Hall the Sigmas are the purple machines in the middle top Photo by courtesy of Johan Hallback 4 3 Analysis of SSFNet s BGP4 Implementation In this section we l
176. onal BGP4 In the Set up situation there is no difference from the traditional BGP In the fail over situation and the fail down there is a great difference the convergence tendency changes from exponential in the case of the traditional to linear or constant depending on the connectivity It feels like the more connected are the nodes the more effective is the ghost flushing rule Or the worse traditional BGP4 works Concerning the effect of this rule depending on the topology it is clearly noticed that the more connected the nodes are the more effective it is We can find highly connected situations in scenarios related to ISP interaction where many ASs connect between them as shown in 18 Also the tests of mixing ghost flushing nodes and traditional BGP4 shows a great result Even if not all the nodes uses the rule the performance of the systems improves There is a linear relationship between number of nodes and the improvement of the performance This is a great result for the future deployment of the rule About the implementation It turns out to be extremely easy and it doesn t look to need extra cpu time noticeable or memory usage 76 Chapter 5 BGP4 Cases Simulation Looking to all the results and conclusions we can say that it s worth it to implement this rule later on GNU Zebra The results are quite good and the drawbacks look small enough to do it 5 8 2 Ghost Buster The results about the ghost buster rule ar
177. ond is that all the BGP4 traffic should be in a isolated network so there wouldn t be any interference from to external entities So this is what we did we defined two VLANs in the switch VLAN 1 connected one of the network cards of each computer to the university network so all the machines would be accessible VLAN 2 connected all the second network cards There was no connection between the two LANs Then we had to configure all the network interfaces For all the interfaces connected to LAN 1 we activated the DCHP client so they would automatically get an Internet IP and gateway configuration For the interfaces connected to the VLAN 2 we assigned manually private IPs in the range 192 168 0 1 192 168 0 7 numbering all the computers from bgp1 to bgp7 This way we could control all the computers from a remote location Office use the switch manage ment tool to simulate link failures for the BGP connections VLAN2 but at the same time not loosing the remote connection to any of the machines In fig 6 12 we can see a small schema of the network layout Exporting files Another concern was to centralize the files from GNU Zebra and the configuration scripts that would run on each machine The working environment would be automatically set even if hardware faults happened and the machines rebooted Something that actually happened in bgp3 all the time In fig 6 13 we see a small schema of how the files are exported between machines M
178. onment UpdateMessage handle event Remove withdrawn routes from AdjRIBIn Add Replace new routes 77 to AdjRIBIn Run Decission Process If needed New Removed and Replaced Routes Calculate grade of decission process 2 preference for new routes Changes in LocRIB J 10000000 decission process 3 If a changed route is not feasible any more find a new one to replace it If a changed route is feasible replace with it any reference to its nlri on the LocRIB Put all the routes that are not anymore in the LocRIB to be withdrawn if there is not impicit withdrawal Put all the newroutes on the s LocRIB to be sent announcements routes and withdrawals external update with this announcements external_update Create new UpdateMessage Put the withdrawals and the first route to be sent in it if any try_send_update it For each route left to be sent create a new UpdateMessage and try_send_update it UpdateMessage If MRAI not expired If MRAI expired AAA a E s try send update 1 Eliminate withdrawals about routes to be sent Implicit Send the messages If anything left on it Eliminate withdrawals about routes to be sent Implicit Update Waiting list with routes to be announced when MRAI expires Eliminate those routes from the message Send the messag If anythin
179. onnected to and from other nodes and commands Leaves of the tree Master Environment Figure 6 7 Small part of the bgpds VTY tree This tree is defined in bgp_vty c There both nodes and leaves are defined Each command is inserted into its environment This is done using the function install element Node command A command is defined by a tuple of name help message string parameters and explanation followed by the code to execute when invoked figs 6 8 and 6 9 how a command is defined and installed DEFUN show ip bgp ipv4 paths show ip bgp ipv4 paths cmd show ip bgp ipv4 unicast multicast paths SHOW STR IP STR BGP STR Address family n Address Family modifier n Address Family modifier n Path information Vn vty out vty Address Refcnt Path r n aspath print all vty vty return CMD SUCCESS Figure 6 8 Defining a command show ip bgp paths commands install element VIEW NODE amp show ip bgp paths cmd install element VIEW NODE amp show ip bgp ipv4 paths cmd install element ENABLE NODE amp show ip bgp paths cmd install element ENABLE NODE amp show ip bgp ipv4 paths cmd Figure 6 9 Installing the command in a node 86 Chapter 6 Applying the Ghost Flushing Rule to Zebra Routing Software 6 4 Modifications to the code of bgpd 6 4 1 Implementing ghost flushing over GNU Zebra When the SSFNet simulator was modified we had to modify the
180. orks become the backbone of the Internet Proprietary protocols are developed by companies like Cisco or Juniper networks Last BGP 4 standard released RFC 1771 28 Also first standard for IPv6 released RFC 1884 27 RFC 1884 End of the 90s to now The breathing space given by CIDR supernetting and BGP4 is running out IPv6 is started to be deployed but it doesn t reach all the internet 2006 Supposed date for IPv6 final stages of deployment in some asian countries Korea Japan 11 In summary everything began with isolated networks that didn t exchange information Then in end of the 70s exchange began being the establishment of TCP IP in 1982 the big first step to stan dardization From that point the routing protocols as we know them were born Many have appeared but all of them were scientific initiatives or industry products that imposed themselves on the network The 90s are marked by the urgent need of solving the problems derived of the IPv4 structure CIDR Supernetting and BGP 4 were born then When IPv6 is finally deployed new changes in the Internet routing schema are expected Chapter 3 Ghost Flushing and other Proposals As we have stated before BGP4 is a routing protocol that has solved many problems over the Inter net But it suffers from various problems derived of the many different environments Topological and political in which it runs A too open standard that allows too different implementations 31
181. os 4 Implementaci n de las soluciones validadas en un software real de encaminamiento GNU Zebra Cap tulo 2 Protocolo de encaminamiento BGP4 y su entorno 2 1 Descripci n del Protocolo BGP4 Protocol BGP4 es la versi n est ndar de el protocolo de encaminamiento externo m s usado en Internet La primera versi n fue publicada en Junio de 1989 en el RFC 1105 aunque la ltima versi n es BGP4 y est descrita en RFC 1771 28 y es la estudiada en este trabajo Como se ver a lo largo de este cap tulo BGP4 implementa t cnicas como detecci n de ciclos mediante vector de ruta CIDR o pol ticas de propagaci n que le permiten funcionar correctamente O casi en Internet 2 1 1 Vectores de Ruta y Detecci n de ciclos El enfoque de BGP4 hacia la idea del vector de ruta es bastante radical Cada mensaje de actualizaci n sobre una ruta incluye una lista de todas las ASs a trav s de las cuales la informaci n ha pasado Cuando un router quiere retransmitir informaci n que ha recibido incluir su n mero de AS al principio de esa lista de ASs de este modo es como el vector de ruta de va construyendo Esta lista de ASs es conocido como Camino de ASs Este vector de ruta tiene una funci n muy clara permitir la detecci n de ciclos Uno de los principales problemas de otros protocolos de encaminamiento son los ciclos en la topolog a de red Por ejemplo el RIP Sin embargo con el camino de ASs un router puede comprobar si su n mero
182. ositive effect in whole internet This project runs around improving the behavior and performance of the BGP4 in certain situations 1 1 Motivation Purpose and Goal BGP4 is the external routing protocol EGP most used this days This makes its behavior a crucial issue to the stability of the Internet Any flaws or problems that could exist in the protocol would have a critical impact in the world wide communications system 12 13 15 Actually some problems have been found related to the performance of BGP4 The performance and reaction time of the internet are crucial for it to compete with the reliable fast and low latency phone digital network Real time services are more and more common these days over the internet and they require a reliable fast reacting internet As some studies have shown the performance of BGP4 can decrease depending on the topology of the network 12 In cases when parts of the network were down it could even take minutes for the rest of the nodes to reconfigure according to the new situation This is called convergence problem the time that it takes until the network stabilizes after am event happened to it Many solutions have been proposed and between them we have chosen to study the Ghost Flushing described in Bremler Barr et al 13 Analyzing its theory base simulating the BGP4 with this new rule and depending on the results implementing it over a routing software are the main goals of this project 1
183. other Proposals Chapter 4 BGP4 Simulation Environment The simulation part of this thesis meant much more work than just running a set of scenarios In the first place a simulator had to be chosen that included looking for a list of available simulators with BGPA functionalities analyzing them learning how to use them creating some examples and testing the results After that a proper simulation environment was needed programs to automatically generate the configuration files run the simulations and analyze and store properly the results In this chapter we will try to show how all this was done 4 1 Choosing a Simulator Of all the network simulating suites available we chose to test two NS 2 7 and SSFNet 9 There were other options like J Sim 5 Formerly know as JavaSim but due to time limitations we had to stick to testing the two more well known simulators With the best reputation 4 1 1 NS 2 and BGP The first option was NS 2 NS 2 by itself doesn t include BGP4 capabilities But there is an extra module called BGP 1 that is an adaptation of the C code from Zebra 4 routing software Its Zebra relationship was the strongest point for this option because Once the implementation of BGP was known modifying Zebra would be much easier History and characteristics Ns began as a variant of the REAL network simulator in 1989 and has evolved substantially over the past few years In 1995 ns development was supported
184. out 213 98 0 0 16 withdrawn w attr nexthop 0 0 0 0 origin i about 213 98 0 0 16 withdrawn w attr nexthop 192 168 0 5 origin i about 213 98 0 0 16 150 Appendix G GNU Zebra log file example DENIED due to as path contains our own AS 2004 07 21 23 12 48 BGP 192 168 0 2 send UPDATE 213 98 0 0 16 unreachable 2004 07 21 23 12 48 BGP 192 168 send UPDATE 213 98 0 0 16 unreachable 2004 07 21 23 12 48 BGP 192 168 send UPDATE 213 98 0 0 16 unreachable 2004 07 21 23 12 48 BGP 192 168 send UPDATE 213 98 0 0 16 unreachable 2004 07 21 23 13 09 BGP 192 168 rcvd UPDATE w attr nexthop 192 168 0 2 origin i path 236 4 7 2004 07 21 23 13 09 BGP 192 168 2004 07 21 23 13 12 BGP 192 168 2004 07 21 23 13 12 BGP 192 168 origin i path 3 5 6 4 7 2004 07 21 23 13 12 BGP 192 168 2004 07 21 23 13 14 BGP 192 168 2004 07 21 23 13 14 BGP 192 168 2004 07 21 23 13 14 BGP 192 168 2004 07 21 23 13 14 BGP 192 168 2004 07 21 23 13 14 BGP 192 168 2004 07 21 23 13 14 BGP 192 168 2004 07 21 23 13 14 BGP 192 168 2004 07 21 23 13 14 BGP 192 168 O OGOGO NO P U N oo w N rcvd 213 98 0 0 16 send UPDATE 213 98 0 0 16 rcvd UPDATE w attr nexthop 192 168 0 3 o W rcvd 213 98 0 0 16 rcvd UPDATE w attr nexthop 0 0 0 0 origin i rcvd UPDATE about 213 98 0 0 16 withdrawn Can t find the route 213 98 0 0 16 rcvd UPDATE w attr nexthop 0 0 0 0 origin i rcvd UPDATE about 213 98 0 0 16 wit
185. outer_GF_cmd no bgp ghost flushing BGP_STR Disables Ghost Flushing Technique n char ret struct bgp bgp bgp vty gt index vty_out vty Ghost Flushing Disabled s VTY_NEWLINE bgp gt ghost_flushing 0 return CMD_SUCCESS GHOSTMODIF END Then we have to add this two new commands to the code that installs the commands in the VTY environment The node we want to install it is in the router node inside the bgp configuration GHOSTMODIF GHOSTFLUSHING COMMANDS install element BGP NODE amp bgp router GF cmd install element BGP NODE amp no bgp router GF cmd GHOSTMODIF END Now we have to add two new more commands to activate and deactivate the debugging messages associated to the ghost flushing rule This time the modifications have to be done in the bgp debug c file Here all the vty commands associated with debugging are coded These are the new two commands debug bgp ghost fluhsing no debug bgp ghost flushing undebug bgp ghost flushing GHOSTMODIF DEFUN debug bgp gf debug bgp gf cmd debug bgp ghost flushing DEBUG STR BGP STR BGP Ghost Flushing messages Mn 88 Chapter 6 Applying the Ghost Flushing Rule to Zebra Routing Software bm gt ghost debug 1 vty out vty BGP Ghost Flushing debugging enabled s VTY NEWLINE return CMD SUCCESS DEFUN no debug bgp gf no debug bgp gf cmd no debug bgp ghost flushing DEBUG STR BGP STR BGP Ghost Flushing
186. por todos los nodos Porque informaci n fantasma ha sido detectada Como consecuencia en t 3 todos los nodos han vaciado sus tablas de encaminamiento y dejan de hacer nada m s Solamente en 3 segundos un resultado mucho mejor que en fig 3 4 Analizando el ejemplo podemos distinguir dos fases Distribuci n de Informaci n Fantasma aparece por la primera retirada impl cita Esta informaci n activa la regla ghost flushing en todos los nodos En el ejemplo esto ocurre entre t 1 y t 2 General Flushing Eliminaci n general por los mensajes de retirada producidos al detectar la in formaci n fantasma Todos los nodos limpian la informaci n fantasma en sus tablas Esto ocurre en t 3 3 2 Regla Ghost Flushing 113 ASpath 0 ASpath 0 ASpath 20 ASpath 10 ASpath ASpath 310 10 Q 2 20 10 1 3 20 120 Do i 120 210 w TS wW Y 310 410 wW w dar 30 3 4 40 310 85 410 CU STA ASpath 10 ASpath 10 E ASpath 0 P pa ASpath 120 ASpath 120 b t 1 c t 2 ASpath ASpath w 33 N w ASpath ASpath d t 3 Figura 3 4 Paso a paso la regla ghost flushing en acci n 3 2 2 Tiempo de convergencia En 13 hay un an lisis matem tico profundo con demostraciones completas de los resultados que vamos a mostrar en esta secci n En la notaci n que usaremos debemos definir h latencia de las conexiones n n me
187. reasons we are talking about 2 3 1 Relationship Classification and Internet Disposition Exporting to a Provider in exchanging routing information with a provider an AS can export its routes and its customers routes but usually does not export its provider or peer routes Exporting to a Client In exchanging routing information with a customer an AS can export its routes and its customer routes and as well as its provider or peer routes Exporting to a Peer In exchanging routing information with a peer an AS can export its routes and its customer routes but usually does not export its providers or peer routes Exporting to a Sibling In exchanging routing information with a sibling an AS can export its routes and routes of its customers and as well as its providers os peer routers Basically the internet is a collection of nodes structured in pyramidal levels but with a collection of links between nodes cross jumping levels Some ASs are part of the backbone structure this ones provide other ASs with interconnection This other ones are also providers to smaller networks and then it repeats itself until reaching the access host in the edge of the network BGP4 is the exterior routing protocol that exchanges routes between this levels Actually all the ASs can be highly interconnected and this relationships are used to control the traffic between them This high interconnection has a high impact on the problem studied on this work
188. ro de nodos E n mero de arcos minRouteAdver intervalo m nimo de anuncio de rutas Mostraremos ahora todos los tiempos de convergencia relevantes para este trabajo Situaci n Fail Down Edown n h 3 1 2hnE min RouteAdver 3 2 La idea sobre Egown es simple Despu s de k turnos todos los caminos AS menores que o iguales a k han sido eliminados Al principio los nodos m s cercanos eliminar n sus rutas y esta eliminaci n Flush se ir propagando eliminando caminos m s largos en nodos m s lejanos En el peor caso el nodo m s lejano est n a n saltos de distancia h segundos cada salto por lo que acaba en n h segundos Podemos ver que la complejidad es mucho mejor que con el BGP tradicional con min Router Adverxn mensajes O Situaci n Fail Over Analiticamente no es posible probar que la regla ghost flushing es siempre mejor que el BGP tradicional Como se indicaba en 15 el tiempo de convergencia en este caso depende de cuanto cuesta hasta que la informaci n fantasma desaparece del sistema y ademas el nuevo camino se propague Como veremos en otros cap tulos el caso mostrado en 3 2 mejora utilizando la regla ghost flushing Sin embargo hay casos en los que la regla se comporta peor que el BGP tradicional Un ejemplo puede verse en fig 3 5 La cadena de eventos que ah ocurre es la siguiente e El Nodo X cambia el camino a trav s de K al camino por M Lo anuncia a S e Entonces X se da cuenta de que es
189. rs It s the first message in the session and it contains information like e The AS number of the sending router e Hold time used by the keep alive procedure e An identifier the IP of one of the interfaces of the sending router e Authentication information and code specificating the authentication method and keying information e The version of the BGP An acceptance of this message is done by sending a keep alive message back Updates once the session is established the routing information is exchanged using update messages One update message only contains information about one path That information is e Networks reachable with this path also known as NLRI Network Layer Recheability Infor mation e AS Path the ASs traversed by this path e Origin of the information internal to this AS or an external AS e Neighbor who is sending this message e Inter AS metrics information used to the route choice e Unreachable indication if the pointed networks are not reachable anymore procedure When an update message is received the information is processed by the protocol First the AS path is checked if the our AS number is in the path this update is discarded because it contains a loop If everything is ok about the update and it announces a new route the information is inserted in a table called RIB in There is one RIB in per neighbor the local node has established a BGP4 session with If the update is a
190. rs and the situation that we found in fig 5 8 a linear convergence for the traditional BGP and constant for ghost flushing and other rules About the number of messages a parallel case to the convergence time In the 4 nodes clique same number of messages as the rules but then the ghost information appears reproducing the exponential convergence for the traditional BGP 5 4 Simulation Results Split horizon Enabled No Jitter 5 4 2 AltPath Topology AltPath Initial SetUp Time BGP4 GhostFlushing GhostBuster 20 GhostBuster 30 gt GhostBuster 50 Seconds See CLP Hoe P P Size Figure 5 46 AltPath Set Up time No Jitter Split horizon AltPath Initial SetUp Num Messages 14000 12000 10000 BGP4 8 8000 GhostFlushing 2 GhostBuster 20 3 6000 GhostBuster 30 GhostBuster 50 4000 2000 0 Str LO PP PP P Size Figure 5 47 AltPath Set Up Messages No Jitter Split horizon AltPath Fail Down Time BGP4 GhostFlushing GhostBuster 20 GhostBuster 30 GhostBuster 50 v Xe oH eM PP Size Figure 5 48 AltPath Fail Over time No Jitter Split horizon 68 Chapter 5 BGP4 Cases Simulation AltPath Fail Down Num Messages 25000 20000 24 BGP4 19980 GhostFlushing GhostBuster 20 10000 y GhostBuster 30 m GhostBuster 50 5000 v VY mw
191. s cuales partes de la red est n ca das podr a costar incluso minutos hasta que el resto de los nodos se reconfigurasen seg n la nueva situaci n de red Es es llamado el problema de convergencia Tiempo que cuesta hasta que la red se establece despu s de que un evento haya alterado su situaci n Muchas soluciones ha sido propuestas pero entre ellas hemos elegido estudiar las t cnicas descritas en Bremler Barr et al 13 Analizar su base te rica simular BGP4 aplicando las propuestas y dependiendo del resultado implementarlas sobre un software de encaminamiento son los objetivos de este proyecto 99 100 Cap tulo 1 Introducci n 1 2 Estructura y m todo de este trabajo BGP4 es un protocolo cr tico para Internet previamente a aplicar cualquier modificaci n al est ndar una serie de pasos deben ser llevados Una modificaci n erronea o inconsistente del protocolo podr a llevar a un inadmisible fallo en masa Este trabajo es el estudio an lisis de una serie de propuestas para mejorar BGP4 por lo tanto quisimos darle una estructura que permitiese que el resultado fuese todo lo coherente y correcta posible Cada paso implica que el anterior valida el trabajo ya hecho Dichos pasos han sido 1 Estudio del Protocolo BGP4 tradicional y su entorno 2 An lisis del problema y la teor a detr s de las soluciones 3 Simulaci n de las version tradicional junto con las modificadas de BGP4 comparando los resultados obtenid
192. s resultados y conclusiones podemos decir que merece la pena implementar esta regla en GNU Zebra Los resultados son buenos y los inconvenientes suficientemente pequenos como para hacerlo 5 3 Conclusiones 123 5 3 2 Ghost Buster Los resultados sobre la regla ghost buster son bastante sorprendentes Inicialmente cuando ejecutamos las primeras simulaciones encontramos los resultados esperados un rendimiento entre el BGP4 tradi cional y la regla ghost flushing O peor Sin embargo cuando comenzamos a simular modelos m s grandes y aplicar la regla split horizon y jitter en los temporizadores el rendimiento de la regla ghost buster sufre un salto espectacular Empecemos con la situaci n de Fail down Hay casos donde la regla ghost buster con el mayor valor para el temporizador delta 50 segundos sobrepasa en rendimiento al resto de las reglas El modelo donde este efecto se da m s es en la topolog a multi Cuando los modelos de mayores dimensions son probados encontramos casos en los que la regla ghost buster se comporta mejor en tiempo y mensajes que ghost flushing Parece que el enfoque conservador a la hora de mandar anuncios es mejor en situaciones de alta interconectividad donde hay muchos caminos posibles y muy largos Lo mismo ocurre en el escenario de set up De nuevo en un escenario extremadamente grande la regla ghost buster se comporta mejor tanto en n mero de mensajes como tiempo Mirando a los resultados podemos extraer
193. stBuster 20 GhostBuster 30 GhostBuster 50 Figure 5 30 AltPath Set Up Messages no Jitter No Split horizon v L Ra KS AltPath Fail Down Time BGP4 GhostFlushing GhostBuster 20 GhostBuster 30 GhostBuster 50 P Figure 5 31 AltPath Fail Over time Jitter No Split horizon 5 3 Simulation Results Split horizon disabled Jitter Activated 61 AltPath Fail Down Num Messages 25000 20000 Y 15000 L Rona gt GhostFlushing 5 E GhostBuster 20 o 5 GhostBuster 30 z 10000 Ns GhostBuster 50 5000 Te S wy ed PPP FP P Size Figure 5 32 AltPath Fail Over messages Jitter No Split horizon Fail Over Again using the jitter seems to be an improvement of the traditional BGP4 compared with the rule applied version In further chapters a deeper comparison between using the protocol with or without the jitter will be done 5 3 3 Multi Topology Multi Set Up Time 7000 6000 5000 4 BGP4 4000 4 GhostFlushing GhostBuster 20 GhostBuster 30 3000 gt GhostBuster 50 Seconds 2000 1000 29 110 208 409 Nodes Figure 5 33 Multi Set Up time Jitter No Split horizon Multi Set Up Messages 3500000 3000000 4 2500000 li P BGP4 amp 2000000 GhostFlushing EI GhostBust
194. stabilization This are the values that we will use to compare the performance of the different versions of BGP4 Depending on the topology this values represent the converge on set up fail down or fail over situation As we can see there is always a double point of view looking from the theory and from the real world Reality Clique No Jitter No Split Horizon Topology models Parameters US Tier Model Jitter Act Split Horizon Atc Figure 4 2 T wo extremes between reality and theory 4 2 2 Simulating means programming Running a high number of simulations can be done in different ways Since this is an engineering work it was decided to spend some extra time in developing a small application that would simplify all the functions needed to run a simulation The main functions to be implemented were 1 Generating the simulation configuration files Given a topology the name and size and reality parameters a the dml file used by the simulation had to be generated 2 Launching the simulations A group of simulations were run all together Specifying the topologies and different simulation parameters the dml file generator is used and then the simulator launched 3 Output processing The output of each simulation can be large Hundreds of megabytes so it has to be automatically processed after it is finished This means extracting the four values mentioned before Initial number of messages initia
195. sults Split horizon disabled No jitter 55 Multi Fail Down Messages 350000 300000 250000 JA le BGP4 200000 GhostFlushing 3 GhostBuster 20 E 150000 4 GhostBuster 30 GhostBuster 50 100000 4 50000 0 T T T 29 110 208 409 nodes Figure 5 17 Multi Fail messages no Jitter No Split horizon Fail Down Again we see the same crossing effect In the smaller node sizes ghost flushing is the best version while ghost buster was worse than ghost flushing and BGP4 the worst by far But in the biggest value 408 Ghost buster behaves much better minutes better Again it looks that in extremely big networks the conservative approaches wins again Parallel results are seen in the number of messages 5 2 4 White Topology St bi White Normal Fail Down Time KS Test p value 0000 so 40 Observations 20 MK n 596 68 1 93 7 153 3 178 8 10 lt to lt to lt to lt to lt 68 1 766 1022 161 8 1874 Convergence Time Figure 5 18 White Fail down time no Jitter No Split horizon Chapter 5 BGP4 Cases Simulation Normal Distribution pepe White GhostFlushing Fail Down Time KS Test p value 0000 100 80 60 Observations 40 20 8 310 lt 91510 166 lt 99 8 Convergence Time Figure 5 19 White Fail down time no Jitter No Split horizon Nor
196. systems C looks like an adequate language However considering there is no a precise documentation of the code There is about the architecture but not about the code C is not the best language to analyze and to find out what it does In lib all the code related with Connecting to the zebra daemon zclient h VTY management access method telnet terminal mangling and cli control Command registration Access lists commands and functionality filter h Prefix lists commands and functionality plist h Route maps For becoming a daemon Logging Linked lists vectors and hashes Memory management including cli Cooperative multithreading using select 2 FSF getopt amp regexs MD5 6 3 Architecture of bgpd 81 e Interface structs and functions including zebra protocol functions if h e Socket mangling sockunion h and sockopt h e IP v4 amp 6 route tables And some internally used functions like serialization support routines for the zebra protocol This all functions are common to all the protocol daemons so here they are coded If we wanted to implement a new routing protocol then a big part of the functions needed for such a task are included here Zebra directory includes the code about the Zebra daemon vtySH includes the code for the shell interface that can be used against the console terminal of the Zebra software 6 3 Architecture of bgpd In this chapter we will try to show how a daemon works in Z
197. t AnnouncedTimegs minRouteAdver 21 SendAnnouncemnt dst 22 If Last AnnouncedASpathas ASpathast 23 send message announcement ASpathas dst to each peer 24 Last AnnouncedASpathast ASpathast 25 Last AnnouncedTimeast currentTimeStamp Figure A 1 Pseudocode implementation of Ghost Flushing over BGP 135 136 Appendix A BGP with Ghost Flushing Pseudocode Zebra bgpd node Router ID and IP hostname bgpd password lacasito router bgp 1 bgp router id 192 168 0 1 bgp ghost flushing bgp enforce first as Network Prefixes network 130 240 0 0 16 neighbor Routers neighbor 192 168 0 2 remote as neighbor 192 168 0 3 remote as neighbor 192 168 0 4 remote as neighbor 192 168 0 5 remote as Debug Info debug bgp 0 P OU N debug bgp fsm debug bgp filters debug bgp keepalives debug bgp events debug bgp updates debug bgp ghost flushing log file bgpd log 1 Appendix B configuration file example Figure B 1 Example configuration file for a zebra node Its IP ID is 192 168 0 2 It has 5 neighbors It uses Ghost Flushing and it shows the debugging messages about it 137 138 Appendix B Zebra bgpd node configuration file example Appendix C DML 5 nodes clique scenario _schema _find schemas Net Net randomstream generator MersenneTwister Stream seed lacasito reproducibility level timeline freguency 1000000000 bgpoptions split horizon false jitter mrai f
198. tPath Topology m ee 71 5 5 3 Multi Topology a nen E Dio RBS AG qu ble eee d a e RA 73 5 6 Comparing all the techniques 74 5 7 Combining nodes with and without ghost flushing se 74 9 8 Conclusions 16 2 5 04 wy eee lee RR E RR Rena uw ORO SOR UR EUR OR bd d 75 5 81 Ghost Fl shing 5 23214 64 Rb Y b ARR deed 75 58 2 Ghosts Buster 2 ai fete heus Gee Gade eas a ere eue uu udo e State X 76 CONTENTS ix 6 Applying the Ghost Flushing Rule to Zebra Routing Software 77 6 1 Zebras a Routing Softwares a voce vA a t REESE Rae 77 64 1 History ta Eau See oa xum BRA Aaa v ae tg feed esr eat E 77 6 1 25 Heatures c Sake eet BOCA ooo aie at tup ota naro PSS e aa X 78 6 1 3 Setting Up a Zebra BGP speaker 2 Ke 78 6 2 Architecture of Zebra Routing Software ee 79 6 2 1 Modules Daemons and Sockets KL 79 6 2 2 Zebra Code Structure 2 2m nn nen 80 6 3 Architecture of bgpd sim i mimma Den SO e oS A ee 81 6 3 1 A Threads lifes morisien a 2 222 ERU us NA 81 6 3 2 Good Daemons speak Zebra Protocol nn 82 6 3 3 bepd source files a u he Qe ae x cr X UR Bae ee RA 82 6 3 4 A bgpd Daemon is born gt o vde lees 83 6 3 5 From an Update Arrival to an Update Departure 83 0 3 0 The VT Y interface 4 Lon kom A eee OG EGO UR m m m m UR TRU 85 6 4 Modifications to the code of bgpd a 86 6 4 1 Implementing ghost flushing over GNU Zebra leen 86 6
199. the size of the topology Parameters Topology File Name File name to read partial DML file Random seed Random seed used by SSFNet simulator to be included on the DML file Type of simulation It can take the values of sim1 No Random no jitter sim2 Random No jitter sim3 No Random Jitter sim4 Random Jitter sim2SH Random no jitter Split horizon activated sim4SH Random Jitter Split horizon activated Ghost Flushing True false Activates this rule for all the nodes Ghost Buster True false Activates this rule for all the nodes Delta time Sets the timer of the delta value for the nodes if the Ghost buster rule is activated Execution example tcl adaptDML tcl multi29 dml lacasito seed sim2SH false false 0 gt file dml DML file with the topology on multi29 txt Simulation options Random activated jitter deactivated and split horizon activared All nodes will run traditional BPG Space used e bgpOptions txt simulation parameters name Containing DML commands to specify the type of simulation Response On the standard output the dml file will be listed multiextract sh 1 2 Function Analyzes the result in a simulation log file It generates the values Set up time set up messages failure convergence time and failure number of messages It removes the log file after Parameters e Log file name 4 2 Simulation Environment 31 e Output file name It generates 4 files name init
200. the analysis of the main proposal the Ghost Flushing rule BGP4 Border Gateway Protocol es el idioma que hace posible que los mapas de carretera de internet est n siempre actualizados Este protocolo es utilizado por las redes corporativas para intercambiar informaci n de enrutado por lo tanto su comportamiento es cr tico para el buen funcionamiento de Internet En algunos casos el comportamiento de este protocolo no es el deseado Este proyecto pretende analizar uno de estos problemas junto con una serie de propuestas para solucionarlo Todo esto implicar revisar la teor a que sustenta estas propuestas y m s tarde realizar una serie de simulaciones para evaluar su rendimiento Despu s aquellas propuestas que podamos considerar como tiles ser n implementadas sobre un software de enrutado gratuito y de c digo abierto GNU Zebra Todo este proyecto comenz como el an lisis de la principal de todas las propuestas la regla Ghost Flushing vi Abstract Contents I Complete Report xix 1 Introduction 1 1 1 Motivation Purpose and Goal 2 2 22 ee 1 1 2 Structure and method of this work 2 2 e 1 1 3 Chapters Overview una A ae ee e 2 2 BGPA Routing Protocol and its Environment 3 2 L Network Routing ar A ee Da usu Den Se e eee Ue AUR e Reo ESA N 3 2 1 1 Hop by hop Routing ss ae seee t pA aa demos ee gee Se EUER d 3 2 1 2 Mapping the Internet es 3 2 1 3 Exterior Interior routin
201. the expected performance 6 6 2 Odd things about GNU Zebra There are some characteristics about GNU Zebra that came into our attention First it implements the split horizon rule for the BGP4 by default being hard coded and impossible to deactivate Also it didn t applies jitter to the timers any timer There are even comments inside the code indicating it as future work Finally there is a strange behavior about how the MRAI timer works It never stops the timer is initialized to the value of 30 seconds and when it expires instead of remaining still it starts again from 30 This seems to be a way of compensating the lack of jittering or just heirloom from earlier versions Because of this features we did a special round of simulations the one without jitter and with split horizon A situation that supposedly didn t often happen in the routing softwares Chapter 7 Conclusions and Discussions 7 1 Quality of the Simulation Results How good are the results we got from the simulations done over SSFNet Well if we look to the characteristics of the simulator it tries to simulate everything from the routing protocol to all the layers below Supposing everything is well implemented and that the simulating engine That is used for other things that networking works properly we can trust the results At the beginning of this work we tried to do the only validation tests we could In the first place the BGP4 module comes with a pool o
202. the traditional BGP An example can be seen in fig 3 5 The chain of events in the figure looks like this e Node X updates from the path through K to the path through M And it is announced to S e Then X realizes that path is not good either So now it chooses the one through Y that is longer e The last event triggers the Ghost Flushing rule sending a withdrawal to e X sends the new good route to S after MRAI time With the ghost flushing rule this case turns out to behave worse because S should always route through X to reach Dst But during MRAI time it won t have that route because of the withdrawal generated by the ghost flushing rule We can state that this will happen always that more than two alternate paths spawn from the same node and at least two fail at the same time being the third one longer 18 Chapter 3 Ghost Flushing and other Proposals A Figure 3 5 Bad situation for ghost flushing Start up and Shorter Path For this cases no update to a longer path will happen on the routing tables of the routers This means that the ghost flushing rule won t be triggered thus no difference with the traditional BGP will happen 3 3 Ghost Buster Rule 3 3 1 How it works In the article 15 another rule was defined to improve the behavior of BGP on the studied case It is the Ghost Buster rule This rule is supposed to run over the ghost flushing rule both working at the same time The idea that originates it is that
203. this NLRI GHOST CODE If there is an entry in GhostData then We update the length of the last path about this NLRI in GhostData GhostData modify NLRI new path length else If new Route is longer than the old route then GhostData add NLRI old path length new path length End if End if 40 Chapter 4 BGP4 Simulation Environment GHOST CODE END end if end if end loop decision process 3 e Function Disseminates routes to peers Routes and withdrawals It creates a message with the new routes and the new withdrawals if any and it is send at the end If there is something to send It also sends the withdrawals associated with the Ghost Flushing Rule e When After handling an update if the decision process is needed e Data Input Changes to the LocRib GhostData e Pseudocode for each BGP peer neighbor loop create wds2send gt List of withdrawals to sent to this peer for each route changed in LocRIB loop if route is no in LocRIB anymore then Remove it from RIBOut Wds2send add route nlri end if end loop end loop for each BGP peer neighbor loop create ads2send gt List of advertisements to sent to this peer get wds2send for this peer created in the previous loop for each route changed in LocRIB loop if route is now in LocRIB then Replace any info in RIBOut related to route nlri with route ads2send add route If route nlri is in wds2send then removenlri from wds2send implicit wit
204. this was our operating system to run Zebra on Installing the software means to follow the typical procedure of installing an open source package compiling and installing using the configure script and makefiles included on the suite After this is done a proper configuration file has to be written An example can be found in the appendixes The file we can find in fig B 1 configures a router which interface to be known as a router has the 192 168 0 1 IP Its AS is number 1 and it has 5 neighbors in the ASs 2 to 5 It advertises the network 130 240 0 0 16 to all of its neighbors This file belongs to our modified version of Zebra so it has the bgp ghost flushing entry indicating the application of this rule is active Also the log messages of this rule debug bgp ghost flushing will be registered 6 2 Architecture of Zebra Routing Software 79 You can place this file in etc bgpd conf and it will be automatically loaded when the bgp daemon is started If not specified otherwise To automatically start bgpd when FreeBSD boots we can include a script executing bgpd daemon in usr local etc rc d Something to notice is that if we want bgpd to use the usual port 169 it has to be executed with root permissions 6 2 Architecture of Zebra Routing Software This chapter will try to give a small idea of how Zebra is structured This contents are mostly based on 14 and our experience modifying the software Intended to be a guideline for future m
205. thread associated to an event e thread fetch thread call thread execute are used to manage the execution of a thread From this list we distinguish four different FIFOs for the threads one for the ones reading from a socket another for the ones writing the one for the handle of different events and finally one for timer based actions If we want something to happen we just have to create a thread and place it in the corresponding FIFO For example to manage the MRAI timer we can use the thread add timer to create a thread associated to this timer We just need to define a function with the actions to be taken when the timer expires We pass it together with the initialization value of the timer to the thread_add_timer and done 6 3 2 Good Daemons speak Zebra Protocol The file zclient h defines zclient the API to talk with zebra BPG has the file bgp_zebra c that implements the functions corresponding to that API In that file the call backs to create destroy configure the different interfaces used by the router and route management are implemented This file give a series of functions used by the rest of the daemon to easily communicate with the Zebra daemon void bgp zebra announce struct prefix struct bgp info struct bgp To send routes to Zebra void bgp zebra withdraw struct prefix struct bgp info To eliminate routes from Zebra Inside this part also the functions that will inject routing informa
206. tion from the Zebra daemon are defined and implemented 6 3 3 bgpd source files We now will present all the relevant for this work source files showing their functions e bgp advertise c bgp_advertise h All the code related with sending messages to other BGP4 speak ers e bgp aspath c bgp aspath h Definition of the ASPath types and manipulation functions e bgp aspath c bgp aspath h Definition of the Attributes types and manipulation functions e bgp filter c bgp filter h All the filtering policies are implemented here e bgp fsm c bgp fsm h Here it can find the state machine e bgp_main c Starting of the bgpd daemon begins here e bgp packet c bgp packet h Here all the code related with the management of packets going in and out of the BGP socket e bgp route c bgp route h Route management Here we can find the decision process e bgp table c bgp table h Tables definition e bgp vty c bgp vty h Definition of configuration commands assertion e bgp zebra c bgp zebra h Zebra communications e bgpd c bgpd h bgpd structure definition The general functions are here 6 3 Architecture of bgpd 83 6 3 4 A bgpd Daemon is born In this section we will show what bgpd goes through since it is starts In fig 6 4 we can see all happening Most relevant when bgpd daemon starts First the bgp master a structure that manages al the possible BGP instances is created It also includes the main excution thread After the co
207. tions environment Sobrescribe la configuraci n local e forceghostbuster true false fuerza el uso de esta regla 4 3 Modificaciones al la Implementaci n regla Ghost Buster 119 e ghostdebug true false activa o desactiva los mensajes de debugging asociados con esta regla BGPSession environment e ghostbuster true false fija el uso de esta regla 4 3 2 La idea detr s de la modificaci n En este caso modificar el protocolo para que cumpla con la regla ghost buster no fue tan f cil como con la regla ghost flushing Siguiendo la estrategia de la anterior modificaci n intentamos identificar la tareas principales necesarias para esta regla Definimos cuatro tareas principales Creaci n e inicializaci n del temporizador Delta asociado con cada ruta recibida por el protocolo modificaci n del procedimiento de env o para que respetase la limitaci n delta tratamiento del evento de expiraci n de un temporizador delta Para todo ello fue necesaria la implementaci n de los temporizadores mensajes y clases necesarias para hacer esto funcionar Para la creaci n e inicializaci n del temporizador delta asociado con cada ruta se pens que el mejor lugar para implementarlo era dentro del c digo de la clase AdjRIBIn Modificamos el c digo de esta clase para que cada vez que una ruta era anadida al AdjRIBIn un temporizador delta era creado y asociado a la ruta Funciona del mismo modo cada vez que una ruta era eliminada del AdjRIBIn el t
208. tir a simular entornos con decenas de nodos con GNU Zebra llevando a resultados m s completos sobre carga y efectos en redes mayores 131 132 Cap tulo 8 Trabajo Futuro Part III Appendix 133 Appendix A BGP with Ghost Flushing Pseudocode Upon receiving message type Peer ASpath dst from peer p in router r in AS 1 If type Withdrawal 2 ASpathastp 3 If type Announcement 4 If AS Peer ASpathas The loop detection prevention mechanism 5 ASpathastp 6 Else 7 ASpathastp Peer ASpath The ASpath to dst associated with peer p 8 NewASpathas Compute the Preferred ASpath from the announcements associated with all the peers 9 If NewASpathasi 4 ASpathast 10 ASpathas NewASpathast 11 If NewASpathas Y 12 Send message withdrawal dst to each peer 13 Last Announced ASpathas 14 NextHopast NULL NextHopas to be used for routing packets to dst 15 Else 16 NextHopast px where px is the peer through which NewASpathast was announced 16a If NewASpathast less preferred than Last Announced ASpathast An empty path is considered longer than any other path 16b If currentTimeStamp Last AnnouncedTimeast lt minRouteAdver 16c Send message withdrawal dst to each peer 16d Last AnnouncedASpathast 17 If currentTimeStamp Last AnnouncedTimeas gt minRouteAdver 18 SendAnnouncement dst 19 Else 20 SendAnnouncement dst at time Las
209. tirada sobre esa NLRI a todos los nodos 4 2 1 Activando la regla Ghost Flushing desde el archivo DML El sistema de lectura del archivo de configuraci n tambi n fue modificado Dos entornos de configuraci n fueron modificados el global y el local Las aserciones locals son utilizadas por cada uno de los nodos Las globales afectan a todos y cada uno de los nodos definidos ste ltimo es especialmente til cuando se trabaja con ficheros DML pregenerados En esos casos modificar todos los nodos puede ser costoso Las aserciones definidas son 117 118 Cap tulo 4 Entorno de Simulaci n BGP4 bgpoptions environment Sobreescribe configuraci n local e forceghostflushing true false fuerza el uso de esta regla e ghostdebug true false activa o desactiva los mensajes de debugging asociados con esta regla BGPSession environment e ghostflushing true false fija el uso de esta regla 4 2 2 Esquema de modificaci n Modification En fig 4 1 podemos encontrar un esquema simplificado de como SSFNet trata los mensajes de actual izaci n con las modificaciones en negrita El completo est en la versi n completa de la memoria Nuevas Rutas decission process 1 Nuevas Rutas odificadas y nuevas decission_process_2 l Ambio en LocRIB I tun Tc decission process 3 Indicar que todas las rutas que han sido eliminadas del LocRIB para ser retiradas Si no hay impl cita Indicar todas las nuevas rut
210. tre niveles Unas ASs forman parte de la estructura de back bone estas proveen a otras ASs con interconectividad las cuales proveen de conexi n a otras redes menores y as sucesivamente hasta que llegamos al acceso de los hosts en el borde de la red BGP4 es el protocolo de encaminado externo que intercambia informaci n entre estos niveles O incluso elementos del mismo nivel Como podemos ver se dan escenarios de una alta interconectividad y la relaci n entre ASs se controla por medio de filtros El problema a tratar en este trabajo Como veremos m s adelante ocurre en situaciones de una alta interconectividad E Es ES ISP ISP ES Level 1 Level 1 x EN ISP Level 2 EN 2 W JE Level 2 ES rebel ES rebel ISP ISP ISP Level 3 Level 3 Level 3 ISP Level 3 ISP Level 3 Figura 2 5 Ca tico ejemplo de proveedores de Internet 108 Cap tulo 2 Protocolo de encaminamiento BGP4 y su entorno Cap tulo 3 Ghost Flushing y Otras Propuestas Como se ha afirmado antes BGP4 es un protocolo que resolvi muchos problemas que ocurr an en Internet Pero a su vez sufre de varios problemas derivados de los diferentes entornos Pol ticos y topol gicos que debe afrontar Un est ndar demasiado abierto que permite demasiadas implementa ciones diferentes 31 inestabilidad de rutas 16 33 mala interacci n entre BGP interno y externo 33 o tiempos de convergencia demasiado altos 12 13 15
211. ushing a GNU Zebra 6 1 Zebra como Software de Encaminado ooa a 6 11 Funcionalidades lt 4 Lage ee RATE PE LEES Rd t 6 2 Arquitectura de GNU Zebra e 6 2 1 M dulos Demonios y Sockets ee 0 3 PESTS cactus ees odeur nce UGUALE D pe won hn ev IUS de EEE esos as M 6 3 1 Tests y resultados oa dk PUTA OG X090 4 a 9 9 ROME RO AU 6 4 Conclusiones ers zn Rue vb AREE P dg hh PPAR 6 4 1 Conclusiones Generales e 7 Conclusiones Y Discusiones 7 1 Calidad de los resultados de Simulaci n eee eee 42 baregla GhostsElushing koe oe ema bee SO RO ir 7 3 Software de Encaminado GNU Zebra aoaaa aa 8 Trabajo Futuro 8 1 Interacci n de Ghost Flushing con otras reglas aooaa 8 2 Probando Zebra hasta su L mites ooa aa III Appendix A BGP with Ghost Flushing Pseudocode B Zebra bgpd node configuration file example 129 129 129 129 131 131 131 133 135 137 CONTENTS xi C DML 5 nodes clique scenario 139 D SSFNet Simulation execution Makefile 143 E Multi Network Models 145 F Zebra Testing Lab 147 G GNU Zebra log file example 149 H Digital Media Contents 151 xii CONTENTS List of Figures 2 1 Example of hop by hop routing between two hosts lt lt oaoa a 2 2 Routers communicating reachabillity information ee 2 3 New picture of the AS divided Internet he 2 4 Schema Simplified of the Update handling by SSFNet BGP4 Implementation 2
212. utas que hay en los RIB INn y si hay una mejor que la que se hab a elegido hasta ahora O no existe ninguna se pone la nueva O se elimina la vieja en el LOC RIB Solo hay uno Esta estructura almacenas las rutas elegidas para alcanzar cada destino conocido Si el LOC RIB es modificado puede existir la posibilidad de que sea necesario enviar nueva in formaci n a nuestros vecinos Para ellos existe otro proceso de decision que elegir qu debe ser anunciado Los nuevos anuncios o retiradas son puestas en otra tabla RIB OUT M s tarde la informaci n esta tabla ser procesada y las actualizaciones correspondientes ser n enviadas 2 1 Descripci n del Protocolo BGP4 Protocol 103 Keep alive son utilizadas por los nodos BGP para informar a sus vecinos que siguen funcionando y no hay ning n problema Si un nodo no recibe un mensaje de keep alive en m s del tiempo de hold negociado en el establecimiento de sesi n intentar saber si el nodo remoto funciona mediante mensajes de notificaci n Notificaciones son utilizadas para manejar los posibles errores que puedan ocurrir alrededor de BGP Hay otras caracter sticas y normas que existen alrededor de los mensajes entre las m s importante est n Temporizador MRAI timer or Minimum Router Advertisement Interval Esta es una limitaci n para controlar la sobrecarga y comportamiento de BGP4 En la configuraci n est ndar per peer un nodo no puede mandar m s de un mensaje de actualizac
213. validar el simulador Memoria completa es decir establecer un nodo y parar uno de ellos para ver que ocurr a Activamos la funci n de debugging del protocolo Despu s de revisar los archivos de log comprobamos que la implementaci n funcionaba correctamente Pruebas de Rendimiento En esta situaci n probamos dos escenarios clique de 5 y 7 nodos Repetimos los tests de la secci n anterior midiendo cuanto tiempo costaba que la red se estabilizase e 5 Nodos Edown con ghost flushing 1 3 segundos Edown sin ghost flushing 50 60 segundos e 7 Nodes Edown con ghost flushing 2 4 segundos Edown sin ghost flushing 110 120 segundos Mirando a los archivos de log vemos el comportamiento de convergencia descrito en el apartado te rico 6 4 Conclusiones 6 4 1 Conclusiones Generales Debemos resaltar que pudimos reproducir en un escenario real el comportamiento an malo en la conver gencia de BGP4 Esto demuestra que es un problema que no solo existe sobre el papel y que se puede dar con un software de encaminado real Sobre la capacidad de GNU Zebra como software de encaminado nuestra experiencia Desde dentro y desde fuera muestran este software como una opci n fiable y barata para configurar un router sobre un hardware convencional Esta opini n est tambi n soportada por art culos en la comunidad de encaminado 34 y los numerosos usuarios que lo utilizan Zebra mailing list 4 Adem s la posibilidad d
214. what impact would have the filter policies 12 in the performance of the ghost flushing rule This and other interactions would be needed to be studied although probably conclusions about it could be generated during the deployment of the rule on the Internet 8 2 Testing Zebra to its limits To test properly the implementation of ghost flushing and the capabilities of Zebra we would have needed more computers to create bigger and more complex BGP4 networks However by the time this project was finishing we learnt about a developing test environment thought for this case The Universidad Polit cnica de Madrid is working in a virtual environment generator to test network applications It is called VNUML Virtual Network User Mode Linux 17 It is a system to simulate multiple independent network scenarios on the same machines It is possible to run a high number of applications emulating they are on different machines One possible future work would be to test Zebra and the ghost flushing using this system making possible to test systems with tens of nodes 95 96 Chapter 8 Future Work Parte II Resumen en Espanol Cap tulo 1 Introducci n En el principio la redes exist an pero estaban aisladas nada las un a Sin embargo la necesidad de intercambiar informaci n entre computadores conectados a redes diferentes apareci En aquel entonces los routers fueron inventados para hacer esto posible El tiempo pas y las
215. withdrawal the info about that destination is removed from the RIB in corresponding to the neighbor which sent the update message After any change in this tables the decision process is run evaluating the routes in all the RIB INs and choosing the best ones If any for each destination known For every destination known to put them 2 2 BGP4 Protocol Description 7 Or remove in another table called LOC RIB There is only one This structure contains the routes currently chosen And used for every known destination After the LOC RIB has been modified maybe it s needed to send new information to the neighbors of this node Another decision process is run and this time it chooses what routes should be advertised or withdrawn to our neighbors This new advertisements or withdrawals ar put in another table RIB out Later the info in this table is processed and the corresponding updates will be send Keep alive are used by BGP nodes to inform their neighbors that the node is running and there is no problem If one node doesn t receive a keep alive message in the hold time negotiated in the open message it will try to know if the remote node works by notify messages Notify are used to notify errors surrounding the BGP protocol There are other characteristics surrounding the messages The most important are MRAI timer or Minimum Router Advertisement Interval This is a limitation to control the overhead and behavior of the B
216. would be solved applying CDIR and route aggregation on the BGP4 This will be analyzed on the following chapters 6 Chapter 2 BGP4 Routing Protocol and its Environment 2 2 2 Path Attributes Update messages carry their info as attributes They can be classified by two criteria transitive non transitive If it should resent when the route is retransmitted and well known optional Well know means that the attribute must on the update message and thus understood by all nodes Optional means the opposite not compulsory The main well known attributes are AS Path is the list of transited AS Origin if this route is internal or learned from out of the AS Unreachable mark if active it means that the destination is not reachable Inter AS metric Next hop the node where the path to the destination begins 2 2 3 The Protocol To send the protocol messages a TCP connections between the BGP4 nodes is used Being the default port used the 169 It relies on this protocol for the error control making everything much simpler This decision was criticized due to the original versions of TCP sensibility to congestion however modern implementations of TCP have features correcting this problem slow start congestion avoidance The messages sent by this protocol are of four types open update notification and keepalive This are their function Open messages are used at the beginning and establishment of the session between two speake

LTU - EX - - 04/228 - - SE - Luleå tekniska universitet

Contents

Download Pdf Manuals

Related Search

Related Contents

LTU - EX - - 04/228 - - SE - Lule&aring; tekniska universitet

Contents

Download Pdf Manuals

Related Search

Related Contents

LTU - EX - - 04/228 - - SE - Luleå tekniska universitet