Home

“Ghost-Flushing” Technique and Other Proposals

Contents

1. 2 2 2 122 Estructura modular de GNU Zebra Todo acaba pasando por el demonio Zebra 126 Pseudocode implementation of Ghost Flushing over BGP e 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 2 2 2 137 29 nodes structure Image Generated by RaceWay network visualization tool 145 4 110 nodes struet re4 sr a ne Ba Ge o ob Ro laete a eae Be Bae Rd 145 208 nodes str et re rn mE aw ee EA a Meee nee 146 409 nodes sbr ct re 2 votos soy ER erage ale OS na LE Oe he ake ot 146 Zebra testing Lab A1208 e 147 Hp procurve switch 2524 used during the tests se 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 Lulea 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 Nives without whom I wouldn t have the chance to e
2. Clique Initial SetUp Num Messages 16000 14000 12000 10000 BGP4 EA GhostFlushing GhostBuster 20 Messages 8000 GhostBuster 30 6000 gt GhostBuster 50 4000 ud 2000 maa 0 456 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 456 7 8 9 1011 12 13 14 15 16 17 18 19 20 Size Figure 5 57 Clique Fail Down time Jitter Split horizon Clique Initial Fail Down Num Messages 9000 8000 7000 2009 BGP4 8 5000 GhostFlushing 2 GhostBuster 20 EI 4000 GhostBuster 30 3000 gt GhostBuster 50 2000 1000 o 456 7 8 9 1011 12 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 3 400 GhostFlushing S GhostBuster 20 E 300 GhostBuster 30 GhostBuster 50 200 100 0 A Size Figure 5 59 AltPath Set Up time Jitter Split horizon 72 Chapter 5 B
3. Time date machine tmp gt SSFNet Simulator Part gt ask choice depending on machine E p hie DML fich Generaion E J et Ve 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 Y 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
4. 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 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
5. 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 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 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 si
6. Chapter 8 Future Work Parte II Resumen en Espanol Capitulo 1 Introducci n En el principio la redes existian pero estaban aisladas nada las conectaba 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 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 tama o 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 l
7. 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 simulator 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 in 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
8. 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 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 disposition 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 Operative System Sun Solaris 9 This simulations were stored in a department store server named claudius sm luth se Allthe machines had the same account mounted so they all stored their results in the same space while they used their
9. 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 VTY 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 connected 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 in
10. 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 en algunas situaciones son solo algunos ejemplos de los varios problemas que adolecen BGP4 En este trabajo analizaremos un peque o 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 alca
11. 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 de 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 Capitulo 6 Aplicando la regla Ghost Flushing a GNU Zebra Capitulo 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 Al 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 simula
12. 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 Tha 17 2 ge i s sigma2 gt L oc I Account tmp O 512 Mb A O aa 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 Hallb ck 4 3 Analysis of SSFNet s BGP4 Implementation In this section we ll 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 Implem
13. 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 34 7 23 23 23 23 path 5 6 2004 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 51 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
14. 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 COCO CC o o DN PP 0 0 U 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 co 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
15. 2 GhostBuster 20 3 6000 GhostBuster 30 GhostBuster 50 4000 2000 0 Qtr YO 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 o S 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 z GhostBuster 30 E GhostBuster 50 5000 v jo Messages o o E x EZ o ize Figure 5 49 AltPath Fail Over messages No Jitter Split horizon Fail Over We appreciate small differences from the case where the split horizon was activated About the Edown 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 Sec
16. 3 1 Como Funciona En el art culo 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 est 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 anuncio podr an ser retrasados a n m s 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 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 Again a more complex definition and mathematical descriptions can be found in 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
17. 5 BGP4 Cases Simulation Bad GhostFlushing Fail Down Time Observations 54 710 66100 774to 88 710 145310 156 60 167910 lt 66 1 774 lt 88 7 lt 100 lt 156 6 lt 167 9 lt 179 2 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 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 1 2 3 4 Nodes Figure 5 41 Comparing the advantage of using jitter on timers We can appreciate a dramatic improvement en each version of the protocol The Convergence time in this multi scenario improves in a 10 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 000 100 IMS BGPA 3 80 4 Gh
18. 50 29 110 208 nodes 409 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 KS Test p value 0000 50 White Normal Fail Down Time 120 9 to 143 to lt lt 132 154 1 32 510 lt 43 6 to lt 54 6 to lt 65 710 lt 76 70 lt 4 657 767 87 8 Convergence Time Figure 5 37 White Fail 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 value 0000 Observations 8 310 92 to lt 17 6 lt 101 3 Convergence Time Figure 5 38 White Fail 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 Std 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 54 3 63 8 lt 121 130 5 Convergence Time Figure 5 39 Bad Fail over time Jitter No Split horizon 64 Chapter
19. 8 R 33 4 9 9 The Update Process c 22 8 22 Wr 3 a pen A 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 DML file 37 4 4 2 Modification Schema e 3T 4 4 3 Deeper Inside the Modification Pseudocode llle 37 4 5 Modifications to SSFNet s BGP4 for the Ghost Buster Rule 41 4 5 1 Activating The Ghost Buster feature from the DML file 41 4 5 2 The main idea for the modification o 41 4 5 3 Howvall this mess works ioi a uele de ea A ee x 41 4 5 4 Deep inside the code Pseudocode o o 42 4 5 5 Data structures needed to make all this work o 44 4 5 0 gt Class Schema io a ee OE Ra ande 45 5 BGP4 Cases Simulation 47 5 17 Simulated Cases en sos SX AA AS AAA dde o 47 DLL Clique a re E ada RE Ta HUIUS 47 5 1 2 Alternate Path AltPath n AT 513 White models o minimis did ara ee ed 48 Dado Bad model 2a er RN ee 48 5 15 Multi Collection a zugenommen ete eoi E 49 5 2 Simulation Results Split horizon disabled No jitter nn nn 50 5 2 1 Ghque Topology an sae ia rien II RAR a 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 y de Y 54 5 2 4 White Topology 32 00 er be did aaa a a d 55 5 2 9 Bad Cased 2 5 a S ee ce Sk dh grag ee ee tek kN Yay Se le a
20. ASpath 310 ASpath ASpath 310 00 2 210 1 2 210 N 2310 dst 3210 4210 9 0 31069 410 310 G 13 410 ASpath 210 ASpath 210 ASpath 210 ASpath 210 d t 3 e t 31 ASpath ASpath ASpath ASpath ASpath ASpath Q 2 2310 a T a 34210 4321 321081 Ya 4210 32106 Xa 4210 3210 f 4210 ASpath 4210 ASpath 2310 ASpath 4210 ASpath 3210 ASpath 4210 ASpath 3210 Ht 32 8 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 O 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
21. Many have appeared but all of them were scientific initiatives or industry products that imposed themselves over 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 a new change in the Internet routing schema is 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 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 Whatev
22. 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 configure statically Systems 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 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 24
23. Multi Topology Set Up Looking at the results in this graphics 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 techniques start 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 when we use the much more conservative approach of ghost buster 5 2 Simulation Results Split horizon disabled No jitter 55 350000 300000 250000 200000 messages 50000 0 Multi Fail Down Messages 150000 4 100000 4 BGP4 GhostFlushing GhostBuster 20 GhostBuster 30 GhostBuster 50 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 being ghost buster 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
24. 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 redes 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 impuse 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
25. 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 Flushin 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 messages n bm gt ghost debug 0 vty out vty BGP Ghost Flushin 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 fushing 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 com
26. 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 Origen si la ruta es interna a la AS o si ha sido recibida desde otra AS 101 102 Cap tulo 2 Protocolo de encaminamiento BGPA4 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 demas a 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 sonlas siguientes Inicializaci n estos mensajes son usados en el estable
27. 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 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 peque as 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 bueno puntos y malos puntos Vemos un mal rendimiento en escenarios medianos y peque os escenarios menos de 200 nodos para la situaci n de set up y fail down Esto
28. 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 it had become 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 we 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 operative 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 imple
29. 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 K 3 A LA 2 1 1 D0 O d t 61 e t 91 Dell 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 be done 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 the withdrawn destination Now under the ghost flushing rule a wit
30. 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 como 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 O 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 e
31. 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 enviarla 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 Capitulo 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 3 sio ee BGP4 Jitter GF Jitter GB 20 Jitt
32. 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 functionalities 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 operative 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 i
33. 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 en diferentes m quinas Esto permitir 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 Capitulo 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 AnnouncedASpathast 1 14 NextHopas 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 cu
34. configuration file example Appendix C DML 5 nodes clique scenario _schema _find schemas Net Net randomstream generator MersenneTwister stream seed lacasito reproducibility_level timeline frequency 1000000000 bgpoptions split_horizon false jitter_mrai false 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 interfac
35. 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 That 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 logging to table dumps after every update 1An 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 weak point Since this simulator runs over C it has to be compiled in the machine it was 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 machine used by many students 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 module The installati
36. 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 link link link link link link mm TM TM m 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 O 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 class
37. 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 traditional 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 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 u
38. 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 Capitulo 6 Aplicando la regla Ghost Flushing a GNU Zebra Despu s del an lisis de la simulaci n de las diferentes modificaciones 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 caracter sticas m s importante es la modularidad cada protoco
39. 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 falsa ser eliminada de la red Flushed pero costar a n m s mensajes m s anuncios Actualizaciones con nuevas rutas y mucho m s tiempo Si a todo esto le a adimos 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 como contenidos 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 peque o 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 210 w d 310 laid 30 3 79 40 30 Ge 14 40 3108 T4 410 ASpath 0 ASpath 0 ASpath 10 ASpath 10 ASpath 120 ASpath 120 MC j b t 1 c t 2 ASpath
40. 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 bgpoptions 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 mejo
41. 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 peering iff it receiv ouncement about th at least delta otherwise it suppres announcement until delta time passes GhostBuster Rule Figura 3 6 Regla Ghost Buster en su enunciado original en ingl s t t A 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 interes 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
42. 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 Space used None 5 Response On the standard output will write a topology file of the structure before specified gen White 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
43. 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 para 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 Este 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 qu
44. 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 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 again and compare the simulation output with the theoretical results So we created a first 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
45. 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 properly 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 rout
46. 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 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 that when node 12 goes down Node 2 changes from P to Pa and advertises it to 1 Then Node realizes that P is not valid either and then chooses P5 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
47. 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 withdrawal 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 BGP4 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 mod
48. 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 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 problem 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 th
49. 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 speakers 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
50. 0 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 low number of IPs CIDR support metrics links guality 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 softw
51. 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 about 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 23647 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 35647 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 N 0 P U N oo w N rcvd 213 98 0 0 16 send UP
52. 0 Qi 210 71 2310 dst 3210 4210 a t 0 3108 9410 310 Gi X4 410 ASpath 210 ASpath 210 ASpath 210 ASpath 210 d t 3 e t 31 ASpath ASpath ASpath ASpath ASpath ASpath AQ 2310 a 5 a 5 q A 34210 43210 32103 Ya 4210 321035 q 4210 3210 i v 4210 ASpath 4210 ASpath 2310 ASpath 4210 ASpath 3210 ASpath 4210 ASpath 3210 Dt 32 g t 33 b t 61 ASpath ASpath D w 342 E X4 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 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 nod
53. 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 a 350 2007 BGP4 3 250 GhostFlushing 5 GhostBuster 20 8 200 GhostBuster 30 159 Ei GhostBuster 50 100 50 Bd 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 7 29000 7 BGP4 S 5000 GhostFlushing 8 GhostBuster 20 3 4000 GhostBuster 30 3000 gt GhostBuster 50 2000 1000 04 pe n 4 5 6 7 8 9 1011 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 dista
54. 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 GhostFlushing 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 appreciate general improvement in allthe 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
55. 16 7 58 4 66 7 100 1 Convergence Time Figure 5 22 White Fail time 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 appreciate 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 6 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 3 Convergence Time 174610 lt 182 9 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 m BGP4 GhostFlushing GhostBuster 20 GhostBuster 30 GhostBuster 50 4 5 6 7 8 9
56. 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 UpdateMessage 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 give a deep look to 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
57. 68 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 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
58. 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 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 Inte
59. DATE 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 withdrawn 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 e ssfnet ghost tar gz Raceways SSFNet 2 0 Simulator with the ghost flushing and ghost buster modifications on the BGP4 module e ssfnet sim tools tar gz Programs developed to create run and analyze the simulations e zebra 0 94 ghost tar gz GNU Zebra version 0 94 modified to use the ghost flushing rule e zebra tools tar gz Collection of tools to generate configuration files for GNU Zebra and run them report e proyecto gf pdf The complete report of this Master s Thesis show 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 T
60. Eau See oa a a BRA Aaa v ae tg feed esr eat E 77 6 1 25 HBEaLUres De RA 78 6 1 3 Setting Up a Zebra BGP speaker 2 Ke 78 6 2 Architecture of Zebra Routing Software kse 79 6 2 1 Modules Daemons and Sockets KL 79 6 2 2 Zebra Code Structure n nn nen 80 6 3 Architecture of bgpd sim i mimma Den BS 81 6 3 1 A Threads lifes morisien 2022 A A sat ae 81 6 3 2 Good Daemons speak Zebra Protocol KK e 82 6 3 3 Bgpd sourcerfiles a u ee ku Qe ae ee en ee RA 82 6 3 4 A bgpd Daemon is born gt o vde ca lees 83 6 3 5 From an Update Arrival to an Update Departure 83 0 3 0 The VT Y interface 24 a ke A as a e m UR TRU 85 6 4 Modifications to the code of bgpd e 86 6 4 1 Implementing ghost flushing over GNU Zebra o o 86 6 4 2 Modifying the VTY configuration environment o e 86 6 5 O RN 89 6 5 1 Testing and Developing Environment e 89 6 5 2 Testing means Programming e 91 6 5 3 Tests nd results 0 omo RISE eqq uu Ye eaa ante 91 6 6 CONCUSIOAS svo oye e ee en AR E bU PEN neh 92 6 6 1 General Conclusions e 92 6 6 2 Odd things about GNU Zebra o o e 92 7 Conclusions and Discussions 93 7 1 Quality of the Simulation Results 2 2 en 93 1 2 The Ghost Flushing Rule lt 3 acdsee 2 2 a2 A a ao be aa 93 7 3 The GNU Zebra Routing Software e 94 8 Future Work 95 8 1 Interaction of Ghost Flushing with ot
61. 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 lt ss 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 de ba SS A SS o eiit it 5l GhostsElushi 2 o o O 22 ea 5 3 27 Ghost Buster 230 sn ass Ai aie a en de A MKI 6 Aplicando la regla Ghost Flushing a GNU Zebra 6 1 Zebra como Software de Encaminado CE rn nn 6 11 Funcionalidades daina 3 kolaa ee A A A ee ee 6 2 Arquitectura de GNU Zebra m nn nn nn 6 2 1 M dulos Demonios y Sockets o e e ee 0 3 A a ts a te ee a as M 6 3 1 Tests y resultados oa 2 dk KAN OG X090 4 vasa ACO RO a 6 4 Conclusiones ers zn ee ee a e 6 4 1 Conclusiones Generales ee 7 Conclusiones Y Discusiones 7 1 Calidad de los resultados de Simulaci n ke 42 baregla GhostsElushing koe oe ema e 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 Pr
62. GP4 Cases Simulation AltPath Initial SetUp Num Messages 14000 12000 10000 BGP4 8 8000 GhostFlushing 2 GhostBuster 20 2 6000 GhostBuster 30 GhostBuster 50 4000 2000 0 Figure 5 60 AltPath Set Up Messages no Jitter Split horizon AltPath Fail Down Time 450 400 350 300 BGP4 3 250 GhostFlushing 8 GhostBuster 20 8 200 GhostBuster 30 150 gt GhostBuster 50 100 50 4 0 Swe PF 4 750 Size Figure 5 61 AltPath Fail Over time Jitter Split horizon AltPath Fail Down Num Messages 25000 20000 BGP4 g 15000 GhostFlushing 2 GhostBuster 20 o GhostBuster 30 10000 GhostBuster 50 5000 ob Swe LP ee P P 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 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 2 8
63. 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 an deactivated The idea is to see which is the best combination of settings In fig 5 67 we can see the result of this comparison 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 No
64. 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 200 BGP4 GhostFlushing GhostBuster 20 md E GhostBuster 30 200 gt GhostBuster 50 100 Seconds ao S S 4567 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 time 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 great bad impact in the Eup 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 456 7 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 BG
65. 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 second 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 intranet IPs of the range 192 168 0 1 192 168 0 7 numbering all the computers from bgpl to bgp7 This way we could control all the computers from a remote location Office use the switch manage ment 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 cent
66. P4 seems to have a linear convergence On the size of que clique of Egown the ghost flushing version seem 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 AltPath Topology AltPath Initial SetUp Time a o N o O lt o 6 6 BGP4 na GhostFlushing GhostBuster 20 Er GhostBuster 30 300 GhostBuster 50 EN me Sn OP 0709 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 samem even if there are delays So no differences in the number of messages Fail Over All the
67. SFNet 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 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 valu
68. Spath ASpath w Gv 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 mero 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 adem s el nuevo camino se propague Como veremos en
69. 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 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 zcient 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 u
70. 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 Active loop detection sender receiver 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 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 BGP4 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 wel
71. aits 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 convergence 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 10 D 20 10 Q 2 20 1200 2 210 310 410 30 3 14 40 A X4 40 3103s 410 ASpath 0 ASpath 0 ASpath 10 ASpath 10 ASpath 120 ASpath 120 SOS UE b t 1 t2 ASpath ASpath 310 ASpath ASpath 310 0 0 21
72. ar 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 retirada 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 R
73. ares 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 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
74. ases 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 30 in the biggest topology 70 Chapter 5 BGP4 Cases Simulation 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 ea 100 s BGP4 3 804 GhostFlushing 8 GhostBuster 20 604 B GhostBuster 30 GhostBuster 50 40 20 456 7 8 9 1011 12 13 14 15 16 17 18 19 20 Size Figure 5 55 Clique Set Up time Jitter Split horizon
75. ationships es 10 2 3 1 Relationship Classification and Internet Disposition 11 DAS ISOIN pe A omes etos Bot ars ab 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 dee 2 2 22 2 ld bid ae a WE Red 13 3 1 2 High Convergence Time and The Ghost Information ss 13 3 2 Ghost Flushing Rule 4 0 Ss A Banane da dE S 15 3 2 1 How t works A A o Mg 15 3 2 2 Convergence time uuu A ER DR oe Red eve 16 3 3 Ghost B ste Rule sama daa AA bbb ee Eee ew ka da 4 8 18 oS How it works Lando e dd da ee 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 A AED ee ere 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 1 Choosing a Simulator s x 2 A an Ser Sak re hg dd 21 44 1 NS 2 and BEPHH ag aan 1 ee ah 21 41 2 o NA A de bao apes ee bbe Pee Ru uou eue d 22 4 2 Simulation Environment 24 4 2 1 Simulation Parameters and Method 2 020000 0004 24 4 2 2 Simulating means programming nn nn 25 vil viii CONTENTS 42 32 The Hardware essa 55 5 a bbb See e a A 31 4 3 Analysis of SSFNet s BGP4 Implementation es 32 4 31 Source Structure zx aa nr ewe EEL na a ne 32 4 3 2 BGPSession Class x md Ea na
76. 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_router_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 the code that installs the commands in the V TY 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
77. bout 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 reappears 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 He 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
78. 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 this simulator as the one 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 ghost 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 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 more theoretical setting 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 S
79. calable 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 Figure 4 1 SSFNet logo 2On the digital media accompanying this report there are examples of the configuration files and logs showing this situation 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 resear
80. 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 operative 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 routi
81. ch 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 graphical 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
82. cimiento 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 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 e
83. cionaremos estos ejemplos con la situaci n problem tica Provider a 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 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 I e 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 Interca
84. ciones 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 son 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 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 rese a partes de este art culo importantes para este trabajo En cap tulos posteriores rela
85. d 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 sets 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 pa
86. 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 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 recibido informaci n fantasma 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 encontr
87. ded to run a simulation The main functions to be sone 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 initial 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 indiv
88. ding 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 a 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 Implicit 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 reaching 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
89. dor 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 a adir 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 nodos 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 ning n 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 cua
90. e 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 _extends 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 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_eb
91. 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 e 5 35 Multi Fail time Jitter No Split horizon 2 2 22 CC 2e 5 36 Multi Fail messages Jitter No Split horizon o soaa 5 37 White Fail time Jitter No Split horizon e 5 38 White Fail time Jitter No Split horizon e 5 39 Bad Fail over time Jitter No Split horizon EC nn nn 5 40 Bad Fail over time Jitter No Split horizon a 5 41 Comparing the advantage of using jitter on timers lees 5 42 Clique Set Up time No Jitter Split horizon 020 0000 000 4 5 43 Clique Set Up Messages No Jitter Split horizon oaoa 5 44 Clique Fail Down time No Jitter Split horizon ke 5 45 Clique Fail Down messages No Jitter Split horizon 2 2 22 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 sooo 5 53 Multi Fail messages no Jitter Split horizon ooa a 5 54 Comparing between having or not Split Horizon se 5 55 Clique Set Up time Jitter Split ho
92. e 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 O 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 is too late in t 3 all nodes realize that 1 cannot reach 0 and choose another AS path 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 appreciate how the combination of a highly interconnected topol ogy clique MRAI limitation and ghost information have as a consequence a extremely high convergence 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
93. e can appreciate that the complexity is much better than the one on the traditional BGP with minRouter Adver xn messages O 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 in this case depends 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 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 S 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 Flu
94. e 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 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
95. e 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 gt old select gt attr gt aspath gt count amp amp int thread timer remain second mi thread gt 1 if bm gt ghost_debug zlog_info s 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
96. e se conoce como relaciones entre ASs 18 Internet es una red que pertenece a una serie de compa as con intereses econ micos las compa 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 para alcanzar solo una serie de destinos 104 Cap tulo 2 Protocolo de encaminamiento BGPA4 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 e
97. e 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 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
98. e 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 initial 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 sim2SH 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
99. eated 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 nodes 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
100. efernced 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 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 c
101. els 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 Race Way 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 on the simulation options Split horizon and Jitter and the topology 1To 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 gu BGP4 80 GhostFlushing GhostBuster 20 60 4 2 GhostBuster 30 gt GhostBuster 50 40 Seconds 20 456 7 8 91011 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 yi 10000 BGP4 gt E GhostFlushing 2 8000 GhostBuster 20 3 S
102. enting 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 sre 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 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 c
103. er 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 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
104. er 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 situaciones 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 empeza
105. er 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 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
106. er 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 that passes 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 Convergence 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 w
107. er 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 Acci 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 wirh rawal 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 podemo
108. es 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 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 Two 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 nee
109. 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 de AS est en la lista y en caso positivo descartar tal ruta En caso negativo puede aceptar la ruta y retransmitirla a adiendo 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
110. es 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 actualizaci 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 sun 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
111. esarrolladores 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 peque o mapa de como algunas de las funciones de BGP4 est n implementadas en bgpd de GNU Zebra Capitulo 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 fushing 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
112. ese 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 obtenidos 4 Implementaci n de las soluciones validadas en un software real de encaminamiento GNU Zebra Capitulo 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
113. est 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 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 lastPath length if lastPath gt longPath longPath lastPath return isGhost public boolean isGhost 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 nl
114. ethod 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 happening 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 Timers 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 consi
115. ey hold in their tables Happens in t 3 ASpath 0 ASpath 0 ASpath 20 ASpath 10 ASpath ASpath 310 10 Q _ 10 1 2 20 1207 210 120 210 wl wW Ax S j 310 410 w W 30 YH 30 33 4 40 310 3 410 ASpath 0 ASpath 10 ASpath 10 ASpath 120 ASpath 120 ww b t 1 e t 2 WS hae ASpath ASpath Me w 1 2 w m gt dst a t 0 w OL uis 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 mathematical 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 MRAT Now we will show all the convergence times relevant to this work Fail Down situation Edown n h 3 1 2hnE min Route Adver 22 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 W
116. gineering 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 2000 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
117. gp_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 interface 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 mm m m m aaa L2 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
118. handra 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 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 En
119. 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 networks Also you can define networks adjusting the size to the demands 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 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 ne
120. hdrawal message means that the previous AS path advertised 16 Chapter 3 Ghost Flushing and other Proposals 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 hot elapse since the last announcement then send withdrawal fast 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 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 th
121. her features 2 2 2 eee 95 8 2 Testing Zebra to its limits Sa KK K KL 95 II Resumen en Espanol 97 1 Introducci n 99 1 1 Motivaci n prop sito y objetivos s 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 n de ciclos KL 101 2 L 2 Atributos d ruta a Er NN nn wee 101 21235 El Protocolo 22 2 2 Be REGIA SUE VERRE ee 102 2 1 4 Soporte CIDR Zr NK ae eee oe a A WR E a 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 3 1 El 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 RARE In m Rte ar ae 3 2 1 Como Funcion iem mm Rem Kokit rer Er Se Bari 3 2 2 Tiempo de convergencia e 3 9 Regla Ghost Busterz canta 8 Sean an a ALA EP RE RW see Ree Ie EA 3 9 1 Como B nci nas xu ug b ra RS aeu ee ege elei mode UE ja 3 3 2 Tiempo de Convergencia 3 42 Otras Solutiones a anna E a a ge A S d didi iuto ne de e deme JA X 3 4 1 Reglas de Resets os duo A Xx OY dox ow o a RO UU 3 4 2 Otros enfoques sobre el mismo problema L 4
122. hesis RelatedDoc Articles Related with this Master s Thesis README txt Data media contents description 151 152 Appendix H Digital Media Contents O o 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 C
123. hing 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 of 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 mathematica
124. idually 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 has been due to 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 Tel The first one because of the pipe functionality really useful to modify and create 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 ghost lushing 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 therefor some software was needed to modify this files according to the simulation parameter
125. ified 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 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 m
126. interno pero definitivamente no para externo Aserciones de Consistencia sobre Rutas para poder identificar totalmenta 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 Detecci n Activa 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 Capitulo 3 Ghost Flushing y Otras Propuestas Capitulo 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
127. ions an 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 and its Environment Router Client zu Router Client o o Router a 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 Rout
128. is 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 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 everyt
129. itecture of bgpd 83 6 3 4 A bgpd Daemon is born In this section we will show what bgpd goes through since it is started In fig 6 4 we can see all that happens 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 command 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 VTY 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 staritng 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
130. 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 FEN ISP ISP FEN 1 Level 1 Level 1 EEN ISP EEN 2 J Jt Level 2 E NES 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 to 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 a
131. izon 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 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 GhostBuster 20 3 1500000 GhostBuster 30 gt GhostBuster 50 1000000 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 4500 4000 3500 3000 n 2500 8 amp 2000 1500 1000 500 Multi Fail Down Time BGP4 GhostFlushing GhostBuster 20 GhostBuster 30 GhostBuster 50 Size Figure 5 35 Multi Fail time Jitter No Split horizon 4000000 3500000 3000000 2500000 2000000 messages 1500000 1000000 500000 0 Multi Fail Down Messages BGP4 GhostFlushing GhostBuster 20 GhostBuster 30 GhostBuster
132. l 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 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 so the simulations are configured in OTCL This is also a strong point favoring this simulator Tcl is a good scripting language to
133. l 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 estos resultados y conclusiones podemos decir que merece la pena implementar esta regla en GNU Zebra Los resultados son buenos y los inconvenientes suficientemente peque os 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
134. l 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 again 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 appre ciate 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 re
135. l show if it s less than the MRAI value no effect of this rule is noticed 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 gt delta h Being K Sat T 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 in delta h time The maximum length of an AS Path is d then the equation for t The convergence time is t t E g delta h h 3 4 By definition of K we 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
136. lementation 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 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 lis
137. liable 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 created 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 i
138. lling the command in a node en 85 Inserting the Ghost Flushing code in the decission process see 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 22 2 0 VR a oo TSn ern 90 Esquema Simplificado de el procesado de un anuncio en la implementaci n de BGP4 en DOPING Eee Era a o sisaan da EDAD a Gree ees ch EG e 104 Distribuci n de clases IB 822 2 2 eee dA a A AAA 4 105 Ejemplo de una configuraci n de Router Reflectors ne 106 Piltr s aplicadoss 3 v va ae Zar AA A A A es ie ee So BUS 106 Ca tico ejemplo de proveedores de Internet 2 2 L 107 Ejemplo de informaci n fantasma creciendo en un 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 112 Paso a paso la regla ghost flushing en acci n se 113 Un mal caso para la regla Ghost Flushing eee 114 Regla Ghost Buster en su enunciado original en ingl s o 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 k ke 120 MUI Esa 72 a5 EA si ES AS SAA e Rote N 121 Mezclando BGP4 tradicional con ghost flushing M s es peor
139. lo 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 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 Capitulo 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 ejec
140. m4SH 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 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 th
141. mands will cancel their effect router bgp ASnumb bgp ghost flushing configure terminal no bgp ghost flushing SS ES 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 6 5 Tests 6 5 1 Testing and Developing Environment Setting a proper environment to work with the Zebra daemon modify it and testing 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 Operative System FreeBSD 5 2 All of them have the same operative 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
142. mbiando 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 entre 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 aa ES ISP ISP ES Level 1 Level 1 x EN ISP Level 2 EN 2 W JE Level 2 ES Be ES Be 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 Capitulo 3 Ghost Flushing y Otras Propuestas Como se ha afirmado antes BGP4 es un protocolo que resolvi
143. mented 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 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 re
144. n 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 rutas 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 nods 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 error
145. nce 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 9 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 BGP4 GhostFlushing GhostBuster 20 GhostBuster 30 GhostBuster 50 Figure 5 30 AltPath Set Up Messages no Jitter No Split horizon v L Na 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 E EG gt GhostFlushing 5 E GhostBuster 20 o 5 GhostBuster 30 z 10000 vs GhostBuster 50 5000 0 E AU Az Vv wy x LP 095 Size Figure 5 32 AltPath Fail Over messages Jitter No Split hor
146. nd 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 networks 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 the establishment of TCP IP in 1982 the big first step to standardization From that point the routing protocols as we know them were born
147. ndo 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 un aspecto atractivo El nico problema es que por muy bueno que sea el software nunca superar a 129 130 Capitulo 7 Conclusiones Y Discusiones un router empotrado Es decir una colecci n de hardware y software especificamente disenada para encaminar informaci n Pero vamos 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 d
148. ng 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 Zebra 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 coperatively 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 Y 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 Y 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
149. 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 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 op
150. nternet 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 topolog a de red 12 En casos en los 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 Capitulo 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 permiti
151. nto account some of them Split horizon jitter but not others 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 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
152. nviar 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 Impicito Actualizar lista de espera 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 era 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 a adidos para ajustarse a las diferentes necesidades en tama os 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 acabar
153. nzable 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 Tiempo 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 Capitulo 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
154. obando Zebra hasta su L mites rn 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 se 2 3 New picture of the AS divided Internet he 2 4 Schema Simplified of the Update handling by SSFNet BGP4 Implementation 2 5 IP classes distribution ss dad le alo eR 2 6 Example of a Route Reflector Configuration inside the same AS 256 Filter Policies uu a Aa Anne 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 s 3 3 Ghost Elushing Rule 4 40 46454 N 2 a ER 3 4 Step by step Ghost Flushing Rule in action e 3 5 Bad situation for ghost flushing 222 2 0 0 0 0200000000002 0 0000 3 6 Ghost Buster tiles 44 Wow owe we eme em nnd dee ana b oA 4 l SSH Net logo 20s 2 2223 Rad a A a ee te Be ee ren dd O Sa eg 4 2 Two extremes between realit
155. obre Zebra se comportaba como debia Correcci n e Realizar peque as 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 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
156. od 57 5 3 Simulation Results Split horizon disabled Jitter Activated 58 53 1 Clique Topology 41 5153 cech etw bos en ee E J K 58 5 32 AltPath Topology a oo a ee ha A LRL 60 5 3 3 Multi Topology 4 4 4 x m E Rana 222 Aa is a la de m dy te hyl 61 5 374 White Topology L 435a me a aaa obese o e y pr S ure ee 62 5 95 Bad Case esee V ordei des du ee eS 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 un a U 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 w De E re Boe 00 70 5 5 2 AltPath Topology 222220 nn nn nn 71 5 5 3 Multi Topology 4 4 5 x nen E DD AG qu AAA Va 73 5 6 Comparing all the techniques ooa 74 5 7 Combining nodes with and without ghost flushing se 74 9 8 VCONCIUSIONS s e bus Seeded daa E RE RE eg 75 5 81 Ghost Fl shing 5 23214 24 doe pe p a ana Rb Y b ARR deed 75 58 2 Ghosts Buster 2 loto tt u Gade eas a a e eue E e td X 76 CONTENTS ix 6 Applying the Ghost Flushing Rule to Zebra Routing Software 77 6 1 Zebras a Routing Softwares a vee vA e ERR t REESE Rae 77 64 1 History ta
157. ode 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 responsible for disseminating routes to peers int dop Route rte Calculates the degree of preferenceof 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 ProtocolSes
158. 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 a 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 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 adver
159. on included to apply a patch to the NS 2 simulator and then the first problems appeared It wasn t compatible with the lastest 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 got to make 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 the tutorial We reinstalled the software and tested the example without the BGP patch and the the problem disappeared Since everything else worked finely Seeemed so and for the BGP simulations we didn t need this 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 resul
160. onds 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 a BGP4 g 800 GhostFlushing 8 GhostBuster 20 Bd 600 5 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 BGPA GhostFlushing 60000 GhostBuster 20 GhostBuster 30 40000 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 c
161. one by bgp1 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 occ 5c 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 1
162. ontains 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 s BGP4 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 DE BusterRoute amp van EE 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 cr
163. orse 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 the 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 takes 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
164. os 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 alg n tiempo nuevos problemas aparecieron Como consecuencia nuevas versiones de BGP fueron desarrolladas A principios de los 90 la ltima versi n BGP4 fue publica e implantada en Internet 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 peque o 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 I
165. ostFlushing S GhostBuster 20 A 60 2 GhostBuster 30 gt GhostBuster 50 40 20 0 q PLE E a DNE ER 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 12000 4 10000 4 BGP4 gt GhostFlushing 2 8000 4 GhostBuster 20 3 g GhostBuster 30 6000 4 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 eo w S e A BGP4 mA GhostFlushing GhostBuster 20 Pa 2 GhostBuster 30 gt GhostBuster 50 m a eo Seconds N S S a eo 100 4 50 4 456 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 A
166. 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 3 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 ese camino tampoco es bueno Entonces ahora elige uno a trav s de Y que es m s largo e El ltimo evento dispara la regla ghost flushing enviando un mensaje de retirada a 114 Capitulo 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 fushing 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
167. outing 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 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 MRS 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
168. path 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 RUNTIME echo Max Memory MAXMEM megabytes echo OutPut File NOMFICH JAVAC java Orm 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 Cmv 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 Figure E 1 29 nodes structure Image Generated by RaceWay network visualization tool Figure E 2 110 nodes structure 145 146 Appendix E Multi Network Models s Figure E 3 208 nodes structure 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
169. 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 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 84 Chapter 6 Applying the Ghost Flushing Rule to Zebra Routing Software F 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 Withdra
170. quire 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 protocol is implemented in different daemons this includes some of the various advantages of this software package e Easier 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 operative 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
171. r 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 Capitulo 5 Simulaci n de Casos de BGP4 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 ibid How worse Co o 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 Edown con ese n mero de nodos usando ghost flushing comparado con el mejor Egown 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
172. r 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 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 l o 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
173. r 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 a adida 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 temporizador 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 a adimos 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 DeltaTimer 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 mantene
174. raditional 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 consequence 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 SS 4000 BGPi GhostFlushing GhostBuster 20 GhostBuster 30 GhostBuster 50 Seconds w S o S 2000 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 T 7 29 110 208 409 Nodes Messages Figure 5 15 Multi Set Up Messages no Jitter No Split horizon Multi Fail Down Time 3500 3000 2 2500 m BGP4 3 2000 GhostFlushing 8 GhostBuster 20 amp 1500 L GhostBuster 30 GhostBuster 50 1000 500 ol gt 0 29 110 208 409 Size Figure 5 16 Multi Fail time no Jitter No Split horizon 5 2 3
175. ralize 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 ln 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 d
176. results are seen in the number of messages 5 2 4 White Topology Normal Distribution KS Test p value 0000 80 40 Observations 20 White Normal Fail Down Time Mh n i Figure 5 18 White Fail time no Jitter No Split horizon 596 68 1 93 7 10 lt to lt lo lt 68 1 768 102 2 Convergence Time 153 3 178 8 to lt to lt 161 8 1874 56 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 998 Convergence Time Figure 5 19 White Fail time no Jitter No Split horizon Normal Distribution Led White GhostBuster Delta20 Fail Down Time KS Test p value 0000 100 80 2 2 60 8 El 6 40 20 o 8 310 lt 267 to 91 to lt 175 lt 359 100 2 Convergence Time Figure 5 20 White Fail time no Jitter No Split horizon Normal Distribution PR White GhostBuster Delta30 Fail Down Time KS Test p value 0000 A jo i o Convergence Time Figure 5 21 White Fail 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 Observations pa 8 310 50 10 58 410 91 7 to
177. ri 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 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
178. rizon kse 5 56 Clique Set Up Messages no Jitter Split horizon e 5 57 Clique Fail Down time Jitter Split horizon ooa a a 5 58 Clique Fail Down messages Jitter Split horizon e 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 o ooa a 5 66 Multi Fail messages Jitter Split horizon ooo aa 5 67 Multi Pommin ee n ad BRAS BAD ar ee 5 68 Mixing BGP4 with ghost flushing More is worse ees 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 a 81 bgpd daemon initialization process ke 83 Zebra s bgpd handling an incoming update message o ooo 84 Zebra s bgpd decision process Simplified e 84 Small part of the bgpds VTY tree 2 L 85 Defining a command re 2 2 03 AAA RUE esse e AT de dc as 85 Insta
179. rnet 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 es 1 1 2 Structure and method of this work aoaaa aa 1 1 3 Gh pters Overview una A ae ee e 2 2 BGP4 Routing Protocol and its Environment 3 2 L Network Routing ar A ee aan Den rn A 3 2 1 1 Hop by hop Routing ss ae seee t pA aa Ana 9E ala ene EUER d 3 2 1 2 Mapping the Internet 2 oo nn 3 2 1 3 Exteri r Interior routine 64 44 a dd a GA xoc RTR MO Ye UR 3 4 2 3 BGPA Protocol Description pao manalaa ER A AA un ar Bo 5 2 2 1 Path Vectors and Loop Detection lt o e 5 23232 Path Attmibutesma o aa Fu med dete EVE E ooo bd ur ew e UE e Rd d 6 22213 D he Protocol sss eue Ix a 8 a ee dedi are 6 2 24 CIDR support and BGP4 e 8 22 5 Internal BGP ABGP a kee ee I A a 9 2 3 Autonomous System Rel
180. 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 positive 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 s
181. 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 the chosen simulator SSFNet and finally the details about then 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 R
182. rrentTimeStamp Last AnnouncedTimeast lt minRoute Adver 16c Send message withdrawal dst to each peer 16d Last AnnouncedASpathast 1 17 If currentTimeStamp Last AnnouncedTimeas gt minRouteAdver 18 SendAnnouncement dst 19 Else 20 SendAnnouncement dst at time Last 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
183. s 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 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 5456789 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
184. s announcements external_update Create new UpdateMessage Put the withdrawals and the first route to be sent in it if any L 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 anything 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 to 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 bi
185. s 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 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 QO 20 10 1 3 20 1201 i fi 120 210 WI 310 410 W 30 GG 194 30 59 40 31066 XA 410 K j ME DIN xw N ASpath 10 ASpath 10 E 4 ASpath 0 P pa ASpath 120 ASpath 120 N b t 1 6 1 2 w A
186. se extra cpu time noticeable or memory usage 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 76 Chapter 5 BGP4 Cases Simulation 5 8 2 Ghost Buster The results about the ghost buster rule are 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 overperforms all the rest of the rules 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 that depending on the point of view the ghost buster performs better or w
187. se 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 demasiado 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 habia 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
188. sed 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 information 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 Arch
189. shing 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 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 obeys to two reasons In the first place some implementations doesn t include the MRAI limitation so this way we make sure this 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 peering iff it receiv ouncement about th at least delta otherwise it suppres announcement until delta time passes Mu Figure 3 6 Ghost Buster rule The delta value can be set with any value however as the simulations wil
190. sion 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 protocol below this one 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 and update message is received 2 When a 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 Imp
191. 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 trafic 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 Environment 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 decission_process_2 Calculate grade of preference for new routes Changes in LocRIB J 10000000 decission process 3 Ifa 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 thi
192. stall 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 decision process to implement the Ghost Flushing rule So here we did the same the attack point was the decision process bgp_process at bgp route c _ bap_process 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 gt 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 W
193. ste 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 tiempo 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 ZA RD Y 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 Capitulo 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 cualqui
194. sts 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 How all this mess works 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 lifecicle 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 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 Modifica
195. t 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 address were about to exhaust and also the routing tables where growing too much A patch to the TP 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 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
196. t 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 operative system FreeBSD is commonly accepted as one of the strongest free Unix Linux option for networking work so this was our operative 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 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 Some
197. th 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 l placa 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 om Y pias m we add this NLRI and the routes ANA POA OMI length to the GhostData data structure announcements n N If the MRAI timer is not expired n n yet we forcefully send a l niri 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 long
198. 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 we received 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 replacement 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 too 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 modifie
199. thing 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 modifications 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 rout
200. tions highlighted with bold letters try send_update 1 Function Tries to send a message Tf 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 BGP4 for the Ghost Buster Rule 43 DeltaTimerExpired DeltaTimeoutMessage Route PEER Class handle_event AdjRIBIn Delta Timer It receives the route whose associated 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 r
201. tisements 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 BGP4 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 ramdom 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 correspon
202. 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 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 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 at 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 mod
203. ts 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 routes 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
204. ts 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 converged in a much sorter 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 After doing some research this behavior was a feature in old routing softwares that would lead to unstable situations and not used anymore 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 s
205. tter 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 00 0 5 16 Multi Fail time no Jitter No Split horizon ke 5 17 Multi Fail messages no Jitter No Split horizon k 5 18 White Fail time no Jitter No Split horizon aooaa 5 19 White Fail time no Jitter No Split horizon 2 2 2 oo Emm nn 5 20 White Fail time no Jitter No Split horizon 2 2 2 on nn nn 5 21 White Fail time no Jitter No Split horizon 2 2 2 oo Emm nn 5 22 White Fail time no Jitter No Split horizon aooaa a 5 23 Bad Fail over time no Jitter No Split horizon nn 5 24 Bad Fail over time no Jitter No Split horizon s 5 25 Clique Set Up time Jitter No Split horizon ooa 5 26 Clique Set Up Messages no Jitter No Split horizon s 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
206. tudies 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 an 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 2 Structure and method of this work BGP4 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 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
207. twork 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 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 sess
208. 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 completo 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 e
209. utada por otro demonio el demonio Zebra Esto ayuda a dividir el c digo seg n la funci n que desempe e La comunicaci n entre todos los demonios se realiza sobre sockets y usando el protocolo Zebra Veamos un peque o ejemplo En emphfig 6 1 tenemos al Zebra trabajando con 3 demonios uno 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 teniamos dos objetivos e Comprobar si la implementaci n de ghost flushing realizada s
210. utas 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 implicita Indicar todas las nuevas rutas del LocRIB para ser enviadas exteral_update con todos los anuncios Si MRAI no expirado todavia Forzamos el envio 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 a adimos 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 peque a 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
211. 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 12000 10000 BGP4 gt zZ GhostFlushing p 8000 GhostBuster 20 3 d GhostBuster 30 6000 GhostBuster 50 4000 2000 o Figure 5 11 AltPath Set Up Messages no Jitter No Split horizon AltPath Fail Down Time 500 4 450 400 350 BGP4 2 300 GhostFlushing E gt g 250 GhostBuster 20 200 CET GhostBuster 30 Pa es GhostBuster 50 150 100 4 Da 50 0 v vk OD RR 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 x PP eo 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 t
212. w 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 40 4 7 Nodes z 8 Nodes 9 Nodes 10 Nodes How worse 11 Nodes 12 Nodes 13 Nodes 14 Nodes 15 Nodes 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 let 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 toal 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 E 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 star noticing
213. wal 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 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
214. xist 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 Lule 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 pa s fue llevado a cabo durante un programa de in tercambio Erasmus entre el Centro Polit cnico Superior de Zaragoza Espa a 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 Nives 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 d
215. y and theory o o e 000020004 43 Simulation schema aos a vin ed A ek eo A RN Madd ee eS 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 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 4 10 Delta Tamer Expires zu ta ja add a A A a ee T 4 11 Ghost Buster modification Classes interaction o nn 5 1 Full connected 5 nodes clique 2 on on m nn 5 2 Alternate Path scenario of 11 nodes The alternate path has 5 nodes 5 and the clique lern tan nes ee oak d Min Gee ein BE Sd nding Be 5 3 White topology 2 4 are Era ars en ee ae re b 4 Bad topology tic zu Mean hee ex We ere mur iere A oo ee 5 5 29 nodes structure Image Generated by RaceWay network visualization tool 5 6 Clique Set Up time no Jitter No Splithorizon 22e 5 7 Clique Set Up Messages no Jitter No Split horizon k 5 8 Clique Fail Down time no Jitter No Split horizon 00 0 5 9 Clique Fail Down messages no Jitter No Split horizon ss 5 10 AltPath Set Up time no Jitter No Split horizon 00 5 11 AltPath Set Up Messages no Ji

Download Pdf Manuals

Related Search

Related Contents

Memorex MVDR2100 DVD Player User Manual  Benutzerhandbuch  KitchenAid KSW80R User's Manual  ecker白  Procombi Exclusive 24, 30 & 35  User Guide Guía del Usuario  L20 Tape Library Installation Manual    USER MANUAL  Sony DPF-D72  

Copyright © All rights reserved. Failed to retrieve file