Contents

1 Historia

2 Evolution

3 ¿Qu’e es?

4 ¿D’onde se aplica?

5 ¿Qu’e informaci’on utiliza?

1. Hop-count: El n’umero de hops (saltos) a realizar a trav’es de la ruta. Cuando menor el Hop-count, mejor ruta.
2. Total latency: La latencia acumulada de los enlaces que conforman la ruta. A menor latencia, mejor ruta.
3. Estimated bandwidth: La tasa de transmisi’on (capacidad) promedio que se espera encontrar a trav’es de la ruta. A mayor ancho de banda, mejor ruta.
4. La congesti’on/carga de los enlaces.
5. La tasa de errores de los enlaces.
6. Cuestiones pol’iticas, econ’omicas, etc.

6 ¿Cu’ando se usa?

7 Classless VS classful routing

8 Routing est’atico

• Es la forma m’as primitiva de crear las tablas de routing, pero, en muchos casos efectiva (sobre todo si el sistema aut’onomo es peque no o estamos entrutando entre “stub” networks, es decir, entre redes que s’olo tienen un camino para comunicarse).
• Cuando se configuran los interfaces de red de un router, ’este s’olo sabe encaminar entre sus redes directamente conectadas. Si se necesita incluir informaci’on sobre como encaminar hacia una red remota, se pueden crear reglas manualmente en la tabla de routing.
• Ventaja: no introduce overhead al no necesitar un protocolo de routing.
• Desventaja: no es un trabajo automtico y por tanto, si la red es grande es tediso.

9 Routing din’amico

• Utilizando algoritmos de c’alculo de caminos ’optimos entre redes, o al menos, algoritmos que no posean lazos y que permitan alcanzar una red cualquier desde cualquier otra, es posible dise nar protocolos que los routers utilizan para crear de forma autom’atica (sin intervenci’on humana) y din’amica (adapt’andose as’i a los posibles cambios sobre carga y/o topolog’ia que puedan aparecer en la red) las tablas de routing de dichos routers.

10 IGP (Interior Gateway Protocols) vs EGP (Exterior Gateway Protocols)

• IGPs (RIP, EIGRP, OSPF and IS-IS) are used for routing within autonomous systems (usually recognizable by having a routing domain). All routing protocols, except BGP, are IGPs.
• EGPs are designed for use between different autonomous systems. BGP is the only currently-viable EGP.

11 Distance-Vector, Link-State and Path-Vector protocols

• When a router uses a distance-vector protocol, the routes are advertised as vectors of distances and directions. Distance-vector protocols typically use the Bellman-Ford Algorithm to compute the best path between routers.
• On the other hand, link-state protocols transmit the state of the links of the routers. In this case, the Dijkstra algorithm is used.
• Distance vector routing protocols are like using road signs to guide you on your way to a destination, only giving you information about distance and direction. However, link-state routing protocols are like using a map.
• Link-state routing protocols are also known as shortest path first protcols and build around Edsger Dijkstra’s shortest path first algorithm.
• Link-state routing protocols have a faster convergence than distance vector routing protocols.
• Usually, link-state routing protocols use event-driven updates (only send the state of the adjacent links when they detect some change).

12 Routing information or topology information?

• Depending of the used routing protocol, a router learns different information about the internetwork:
  1. In Distance-Vector protocols, routers accumuate enought knowledge to maintain a database of reachable networks and the output interface(s) which should be used to send data to these networks (and the distance), but not to know the exact topology of an internetwork. Entire routing table updates are sent, periodically, to all neighbors. When there is a change in the topology, only the changes in the routing table are sent.
  2. Otherwise, in Link-State protocols, routers can create a view (usually by means of a graph) of the topology.

13 Metrics

1. Hop count: the number of routers a packet must traverse.
2. Bandwidth (capacity): theoretical (not available) bits per second of the path.
3. Load: traffic utilization.
4. Delay: the time a packet takes to travel through a path.
5. Reliability: the probability of failure.
6. Administrative distance: priority or importance of the rules created by the routing protocol(s).
7. “Cost”: a combination of the previous metrics.

14 Administrative distance of the routing protocols

15 Time to convergence

• Defines how quickly the routers in the network share routing information and reach a state of consistent knowledge.
• A network in not completely operable until it has converged.
• The faster the convergence, the more preferable the protocol.

16 Load balancing

• Normally, when a router has one or more routes to the same destination and with the same cost, the packets can be forwarded in parallel, over all the links that belong to those routes. Thus, the overall transmission time is minimized.
• Some routing protocols, such as EIGRP, are also capable of load balancing across unequal-cost paths.

17 Multiple routing

• Routers are capable of run, simultaneously, several routing protocols.
• This is compulsory in border routers.

18 Distance vector routing protocols

• Slow convergence (the convergence time is proportional to the size of the network).
• Limited scalability (this is a consequence of the previous characteristic).
• Routing loops can appear when inconsistent routing tables are not updated due to the slow convergence in a changing network (some times, due to network inestability or problems).
• Typically, small resources usage.

19 Link state routing protocols

• Fast convergence.
• High scalability.
• Routing loops can appear, but are quite rare.
• Typically, medium/high resources usage.

20 The split horizon rule (distance-vector alg.)

• Distance vector routing algorithms typically implement this technique, to prevent information from being sent out the same interface from with it was received.
• The split horizon rule says that a router should not advertise a network through the interface from which the update came.
• Split horizon can be “improved” with poison reverse. In this case, the previous rule is broken, but only to tell that it has learned the information. This prevents learning incorrect information.
• Split horizon is a technique used to prevent a routing loop in networks using distance vector routing protocols. Split horizon updates reduce routing loops by preventing a routing update received on one interface to be forwarded out the same interface.

21 Route poisoning (distance-vector alg.)

• Route poisoning is used to mark the route as unreachable in a routing update that is sent to other routers, instead of saying nothing about a network that is, in fact, death.
• Route poisoning speeds up the convergence process as the information about a dead network spreads through the network more quickly than waiting for the hop count to read infinity.
• Avoid routing loops by advertising a metric of infinity.

22 A problem in distance-vector algorithms: count to infinity

• It’s tricky to see, but it can happen that a network, connected to a router X, goes down and a X does not communicate this to the other routers (this happens when the other routers send their update information faster than X). X will learn that there is a route to the dissapeared network through other router Y and will tell this to Y. When Y recives the updating from X, Y will increase the hop count for the disapeared net, and the cycle continues.
• The consecuence of this problem is that, altought the routers learn that the dead network is unreacheable, extra bandwidth is consumed.

23 Preventing count to infinity and loops: holddown timers

• Holddown timers are used to prevent regular updates from inappropiate reinstating a route that may have gone bad. If a route is identified as “down”, any other information for that route containing the same status, or worse, is ignores for a predetermined amount of time (the holddown period).
• This means that routers will leave a route marked as “unreacheable” in that state for a period of time that is long enoght for updates to propagate the routing tables.

24 RIP (Routing Information Protocol)

• RFC’s 1058 (1988) y 2453.
• Good choice for small networks (up to 16 hops).
• Creado por Xerox e inclu’ido en la versi’on UNIX BSD (Berkeley Software Distribution) 4.2 en 1982.
• Los routers utilizan el algoritmo de routing Distance-Vector (v’ease el Ap’endice 31).
• RIP messages are encapsulated into UDP segments, with both source and destination port numbers set to 520, sent to the broadcast IP address (255.255.255.255).
• El coste de cada enlace es siempre 1. Por tanto, el algoritmo minimiza el n’umero de saltos (hops). El coste mximo de una ruta es de 15 (16 means unreachable).
• Suppports split horizon and split horizon with poison reverse to prevent loops.
• Route tables can store up to 25 routes.
• Is capable of load balancing up to six equal cost path.
• Los routers se intercambian (entre vecinos inmediatos) sus “tablas de routing” (vectores con las distancias a todas las redes del AS y routers por los que encaminar hacia ellas) cada 30 segundos (update timer)¹ (no necesariamente de forma s’incrona) y cuando reciben nuevos datos acerca del AS, re-calculan los caminos m’inimos. Broadcast updates are sent to 255.255.255.255 or a multicast address.
• La regla anterior tiene una excepcin: la tabla de routing slo se enva hasta otro router si ste no est cubierto por la regla “split horizon”.
• Si un router tras el c’alculo detecta alguna variaci’on en su tabla de routing, esta es comunicada, sin espera, a todos sus vecinos directamente conectados.
• Transcurridos 180 segundos sin recibir informaci’on (invalid timer) desde el router X, todo router conectado directamente a X lo considera inalcanzable (unreacheable). En este momento re-calcula los caminos m’inimos (teniendo en cuenta este evento) y transmite la tabla de routing con los nuevos caminos a todos sus vecinos.
• Si tras 240 segundos (flush timer) no hay noticia del router X, se elimina de la tabla de rutas. Si esto no llega a ocurrir, tpicamente se esperan otros 180 segundos (holddown timer) antes de considerar cierta la informacin acerca de X (slow convergency).
• RIPv1 is a classful routing protocol and dones not send subnet mask information in the updates. Therefore, a router either uses the subnet mask configured on a local interface, or applies the default subnet mask based on the address class. Remember:
  Class A addresses ranges from 1.0.0.0 to 127.255.255.255  
  Class B addresses ranges from 128.0.0.0 to 191.255.255.255  
  Class C addresses ranges from 192.0.0.0 to 223.255.255.255

• Routers using RIPv1 are limited to using the same subnet mask for all subnets with the same classful network.
• Performs automatic summarization (agregation). For this reason, discontiguos topologies (desagregation) do not converge with RIPv1.
• RIPv1 automatically summarized subnedts to their classful address with sending an update out an interface that is on a differente major network than the subnetted address of the router. Because RIPv1 is a classful routing protocol, the subnest mask is not included in the routing update. When a router receives a RIPv1 routing update, RIP must determine the subnet mask for that route. If the route belongs to the same major classful network as the update (in other words, the receiving adapter belongs to the anounced subnet), RIPv1 applies the subnet mask of the receiving interface. If the route belongs to a different major classful network than the receiving interface (i.e., the adapter does not belong to the anounced subnet), RIPv1 applies the default classful mask.
• Because RIPv1 is as classful protocol, it does not support discontiguous networks of VLSM (Variable Length Subnet Masking).

25 RIPv2

• RFC 1723 (1994).
• Classless routing protocol (uses subnet masks).
• RIPv2 enhancements (of RIPv1):
  1. Next-hop addressed (used to identify a better next-hop address - if one exists -than the address of the sending router) are included in the routing updates.
  2. Use of multicast addresses instead of 255.255.255.255 (broadcast) in sending updates.
  3. Authentification option available.

26 RIPng

• RFC 2080 (1997).

27 OSPF

• Was designed by the IETF to replace RIP because its reliance on hop count as the only measure for choosing the best route.
• Version 2: RFC 1247 and RFC 2328 (IPv4)
• Version 3: RFC 2740 (IPv6).
• Classless routing protocol.
• There are two implementations: one to run on routers and the other to run on UNIX workstations (GATED).
• Los intercambios de los mensajes con informaci’on acerca del routing son autentificados.
• Los routers utilizan el algoritmo de routing Link-State (v’ease el Ap’endice 30) para calcular los caminos de coste m’inimo.
• Como mtrica se utiliza la capacidad de los enlaces.
• El c’alculo de los caminos m’inimos se produce cada vez que un router detecta un cambio en el coste de uno de sus enlaces o en su defecto, cada 30 minutos. En cualquier caso, los routers envian a todos los dem’as routers del AS (broadcasting) los costes de los enlaces con dichos routers.
• Soporta routing jer’arquico (permite definir AS’s dentro de los AS’s):

  

• A router runs more of one instance of OSPF when uses hierarchical routing.
• OSPF Cost Values:

  Fast Ethernet and faster	$10^8∕100\ast 10^6=1$
  Ethernet	$10^8∕10\ast 10^6=10$
  E1	$10^8∕2048\ast 10^3=48$
  T1	$10^8∕1544\ast 10^3=64$
  128 Kbps	$10^8∕128\ast 10^3=781$
  64 Kbps	$10^8∕64\ast 10^3=1562$
  56 Kbps	$10^8∕56\ast 10^3=1785$

• RFC 2328 does not specify which values should be used to determine the cost. For example, Cisco routers uses bandwidth and accumulates costs from one router to the destination network.
• To avoid a innecesary flooding in multiaccess networks (wireless, for example), OSPF elects a DR (Designated Router) to act as collection and distribution point for LSAs (Link-State Advertisements) sent and received. A BDR (Backup DR) is elected to take over the role of he DR should the DR fail. All other routers are known ad DROthers. All routers send their LSAs to the DR, which then floods the LSAs to all other routers in the multiaccesss network. The DR is the router with the highest OSPF interface priority and the BDR has the second highest OSPF interface priority. If the priorities are equal, the hightest Router-ID (an IP address) is used to break the tie.

28 IS-IS

• Originally designed by ISO (ISP 10589) for the OSI protocol suite. Later, Integrated IS-IS (or DUAL IS-IS), included support for IP networkds.

29 BGP

• RFC’s 1771 (versi’on 4), 1172, 1173 y 1930.
• ISPs and large instutions use the BGP to propagate routing information and uses the autonomous system number (a 32-bit number) in its configuration (RFC 1930).
• Utiliza el algoritmo Distance-Vector (v’ease el Ap’endice 31).
• BGP usa intensivamente el routing jer’arquico. Los routers se intercambian CDIRized prefixes (direcciones de redes que contienen otras redes de forma jer’arquica) [1]. Por ejemplo, en la Figura

  ---

  
  

  Figure 1: Routing jer’arquico en BGP.

  ---

  1 el router A.c enviar’a al router B.a informaci’on sobre las redes que son alcanzables desde A.c y B.a enviar’a a A.c informaci’on sobre las redes que son alcanzables desde B.a. N’otese que si la agregaci’on es ’optima, el intercambio de informaci’on es m’inimo.

30 Algoritmo de routing Link-State

• Consta de dos fases:
  1. Fase de flooding (inundaci’on). En ella, cada router “broadcasts” el estado de sus enlaces (redes conectadas al router² y coste de enviar datos a trav’es de ellas) al resto de routers del AS.
  2. Fase de c’alculo de los caminos m’inimos. Se utiliza normalmente el algoritmo de Dijkstra [2].

Flooding de los estados de los enlaces

• Cada router env’ia el estado de sus enlaces (redes conectadas al router y el coste de enviar datos a trav’es de ellas) a todos los routers directamente conectados.
• Todo router que recibe un mensaje con informaci’on del tipo anterior retransmite el mensaje a trav’es de todos sus enlaces excepto por el que lleg’o el mensaje.
• Cuando los mensajes son creados se les asigna un TTL que es decrementado cada vez que es retransmitido. De esta forma garantizamos que la fase de inundaci’on finaliza.

Algoritmo de Dijkstra

1. Sean dos listas (Confirmed y Tentative) de ternas (Destination, Cost, NextHop). Inicializar Confirmed con el nodo que ejecuta el algoritmo y Tentative con los nodos que pueden alcanzarse desde ’el.
2. Mientras Tentative no est’e vac’ia:
   1. Mover desde Tentative a Confirmed la terna de menor coste.
   2. Recarcular las distancias a los posibles destinos con esta terna.
3. En cada entrada de Confirmed queda almacenada la distancia m’inima a cada nodo de la red y el primer nodo que se tiene que atravesar para conseguirlo.

Ejemplo

• Dada la red de la figura

  

  obtener la tabla de encaminamiento para el nodo E seg’un el algoritmo Link-State.

Confirmed Tentative Comentarios (E,0,-) (B,4,B) Inicio (D,3,D) (F,2,F) (E,0,-) (B,4,B) Movemos (F,2,F) (D,3,D) (F,2,F) (E,0,-) (B,4,B) Actualizamos (F,2,F) (D,3,D) desde (C,2+1,F) (F,2,F) (E,0,-) (B,4,B) Movemos (F,2,F) (C,3,F) (D,3,D) (D,3,D) (E,0,-) (B,4,B) Actualizamos (F,2,F) (C,3,F) desde (D,3,D) (A,3+5,D) (D,3,D) (E,0,-) (B,4,B) Movemos (F,2,F) (A,8,D) (C,3,F) (D,3,D) (C,3,F) (E,0,-) (B,4,B) Actualizamos (F,2,F) (A,3+2,F) desde (D,3,D) (C,3,F) (C,3,F)

Confirmed Tentative Comentarios (E,0,-) (A,5,F) Movemos (F,2,F) (B,4,B) (D,3,D) (C,3,F) (B,4,B) (E,0,-) (A,5,F) Actualizamos (F,2,F) desde (D,3,D) (B,4,B) (C,3,F) (B,4,B) (E,0,-) Movemos (F,2,F) (A,5,F) (D,3,D) y (C,3,F) terminamos (B,4,B) (A,5,F)

31 Algoritmo de routing Distance-Vector

• Tambi’en llamado algoritmo de Bellman-Ford [2].
• Emplea el mismo modelo de red mediante un grafo, donde los nodos representan routers y los arcos enlaces de transmisi’on.
• Es un algoritmo progresivo (calcula las rutas progresivamente, mejor’andolas en cada iteraci’on) y distribuido (los c’alculos se realizan parcialmente en cada router).

Algoritmo de Bellman-Ford

• Cada cierto tiempo todos los routers vecinos intercambian los vectores con distancias a todos los dem’as routers del AS y se recalculan los vectores de distancias.
• Lo anterior tambi’en ocurre cuando un router detecta una variaci’on en la distancia a algunos de sus vecinos.

Ejemplo

• Dada la red de la figura

  

  obtener las tablas de encaminamiento seg’un el algoritmo Distance-Vector.

Tablas de encaminamiento iniciales. A B C D E F A 0 3/B 2/C 5/D $\infty$ $\infty$ B 3/A 0 $\infty$ 1/D 4/E $\infty$ C 2/A $\infty$ 0 2/D $\infty$ 1/F D 5/A 1/B 2/C 0 3/E $\infty$ E $\infty$ 4/B $\infty$ 3/D 0 2/F F $\infty$ $\infty$ 1/C $\infty$ 2/E 0

Tablas de encaminamiento tras el primer intercambio de vectores. A B C D E F A 0 3/B 2/C 4/C 7/B 3/C B 3/A 0 3/D 1/D 4/E 6/E C 2/A 3/D 0 2/D 3/F 1/F D 4/B 1/B 2/C 0 3/E 3/C E 7/B 4/B 3/F 3/D 0 2/F F 3/C 6/E 1/C 3/C 2/E 0

References