Author: bjr Date: 9 feb 2018 Updated: 17 feb 2020 From notes dated 13 jan 2013 From RFC 1058: Routing Information Protocol Distance routing protocols The aim of a distance routing protocol is for each router to have a list of accessible nets, the interface to use to reach each accessible net, the IP address of a machine on the L2 network of that interface, and a distance to the net when using that interface. Each router exchanges with its neighbor router this table. The neighbor then updates its table depending whether what it learns. A route to a network is updated if an announced route is shorter, or if the old route expires. Here is a simple example: +----| R1 |---+---| R2 |---+ | | | / \ / \ / \ / A \ / B \ / C \ Triangular icons represent a network, with the name inside - networks A, B and C. The routers R1 and R2 connect the the networks as shown, with both connected to B, and R1 alone connected to A, and R2 alone connected to C. The routing tables for any router are vectors Table(Router) : Network -> (Distance, Via) along with a timer for the vector, that can age out the vector from the table. The routing protocol begins with known information, including a set of vectors for each directly connected interface with distance 0. Other information, the static routes, are inserted by manual configuration. In rounds of table announcements to direct neighbors, the tables are updated and should converge to a stable, and globally consistent, knowledge of the best routes between all networks. ADVERTISE: The routers exchange tables in RIP messages every 30 seconds. The message is network, distance pairs for every vector in the table, broadcast out each of the router's interfaces. UPDATE: If a router receives a vector (n,d) from router r, it consults its current table for a vector associated with n. * If no vector, add n->(d+1,r) to the table; * If n->(d',r') is in the table, if r==r' then update the distance to d+1; * If n->(d',r') is in the table, and r!=r' and d+1(0,Local), B->(0,Local) Table(R2): B->(0,Local), C->(0,Local) When R1 receives (B,0), (C,0) from R2, it rejects the update to B and places in a new vector for C. Likewise for R2: Table(R1): A->(0,Local), B->(0,Local), C->(1,R2) Table(R2): B->(0,Local), C->(0,Local), A->(1,R1) Counting to Infinity The following example shows the "problem" (technique?) of counting to infinity, to update the routing tables when a router or network leaves. +----| R1 |---+---| R2 |---+---| R3 |---* | | | | / \ / \ / \ / \ / A \ / B \ / C \ / D \ The converged tables: Table(R1): A->(0,Local), B->(0,Local), C->(1,R2), D->(2,R2) Table(R2): B->(0,Local), C->(0,Local), A->(1,R1), D->(1,R3) Table(R3): C->(0,Local), D->(0,Local), B->(1,R2), A->(2,R2) Consider the removal of R3. The route to D in Table(R2) ages out, but the route to D in R1 is advertised as (D,2) back to R2. Hence, Table(R2) is updated: Table(R1): A->(0,Local), B->(0,Local), C->(1,R2), D->(2,R2) Table(R2): B->(0,Local), C->(0,Local), A->(1,R1), D->(3,R1) R2 now advertises (D,3) to R1, which has R2 as the Via for D, so Table(R1) accepts a distance update: Table(R1): A->(0,Local), B->(0,Local), C->(1,R2), D->(4,R2) Table(R2): B->(0,Local), C->(0,Local), A->(1,R1), D->(3,R1) then R1 advertise (D,4) to R2. Since R1 is the Via for D in Table(R2), it also accepts a distance update: Table(R1): A->(0,Local), B->(0,Local), C->(1,R2), D->(4,R2) Table(R2): B->(0,Local), C->(0,Local), A->(1,R1), D->(5,R1) and this continues with R1 and R2 exchanging increasing distance values for the route to D, until it obtains a value (16) which RIP considers to be "infinity". Then the vector for network D is dropped from the table. Split Horizon In the above situation, a technique called Split Horizon would speed convergence of the vectors in the tables. There are two versions of split horizon, with and without Poison Reverse. In both versions, the advertise vectors are inspected if the Via in the vector is router directly attached to the network to which vector will be advertised. In simple split horizon, for such vectors, they are not advertised. For poison reverse, they are advertised with an infinite distance (16). Note: The reverse calculates from the Via the interface linking the via, and suppresses the advertisement for the entire interface. All routers on this interface will be subject to the poison reverse, or the omission of the vector from the advertisement. In this example, either style speeds convergence - R1 either does not report any vector for D, or a vector for D with an infinite distance. Therefore the counting to infinity never starts, and the vector for D will age out of Table(R1) once it has aged out of Table(R2). Question: Can poison reverse help? If R2 reports an infinite path immediately on aging out its vector, this would strike the vector for network D from R1's table; or the poison reverse from R1 to R2, once R2 has no vector for network D in its table, might solicit an advertisement of infinite distance to D, back to R1, causing it to strike its vector for network D from its list. Failure of Split Horizon Split horizon is not a complete solution. This network still suffers from counting to infinity even with split horizon: +----| R1 |---+---| R2 |---+---| R3 |---* | | | | | / \ | / \ | / B \ | / D \ | | | | +----- -----| R4 |---------+ | | / \ / \ / A \ / C \ At convergence, the tables are: Table(R1): A->(0,lo), B->(0,lo), C->(1,R2), D->(2,R2) // or C->(1,R4) Table(R2): B->(0,lo), C->(0,lo), A->(1,R1), D->(1,R3) // or A->(1,R4) Table(R3): D->(0,lo), C->(0,lo), B->(1,R2), A->(1,R4) Table(R4): A->(0,lo), C->(0,lo), B->(1,R1), D->(1,R3) // or B->(1,R1) Suppose R3 is removed, and the vector for network D ages out of R2 and R4. Although R1 will not advertise D to R2, it will advertise (D,2) to R4, and R4 will then add D->(3,R1) to its table. R4 will advertise (D,3) to R2, that will put D->(4,R4) in its table. When R2 now advertises (D,3) to R1, it will update to D->(4,R2), and then R4 will update to D->(5,R1), and so on. Counting to infinity has begun.