Routing Protocol Theory

bermovick

I'm reading Chapter 8 in Odom's book and there's a couple pieces I just read that I can't make sense of. Regarding LSDB's, page 334 shows 8 routers and discusses how the LSA's are flooded. For those without the book, consider the 2 end-point routers are R1 and R8. There are 3 routes between the 2: The first goes through R2, R3, and R4. The second through R5 and R6, and the third through only R7.

Near the bottom of page 334 it says that before flooding an LSA, a router first asks it's neighbor if it already has the LSA (to prevent routing loops), and only sends it if the neighbor does not. So far this makes sense. All things being equal, R1 will likely get information about the far-side of R8 from R7, and let R2 and R5 know it already has it when they ask.

The problem I have comes in on page 335 when it says every router has an identical copy of the LSDB in memory. Except it doesn't from what I understand. R1 only knows about R8 through R7 in this example; it told R2 and R5 that it didn't need this information - but if the R7 route has a higher cost, how will it know that one of the other routes is better? (Unless perhaps even though it told it's neighbors it didn't need the LSA information, it made a note that there was a potential route out that interace still)

EDIT: But even then, unless it asks for it, it's not going to know about the cost for the other routes. I'm reading more; perhaps it's explained later.

typesh

Hey bermovick,

Have a look at Page 351 and 352. This might explain it a little better.

R1 will still form and adjacency with R2 and R5. For each router that R1 becomes fully adjacent with, a full exchange of the contents of their respective LSDBs will occur. Having this information will allow R1 to construct the mathematical equivalent of a topology map for which it will apply the Dijkstra SPF Algorithm. After this exchange has occurred, my understanding is that R5 and R2 will still ask R1 if it needs a route for x.x.x.x (30 minutes later) and at that point, R1 can say "no" since R5 and R2 have already told R1 about x.x.x.x. This is under the assumption that no network changes have occurred.

bermovick

Hehe yeah; I just read through that not too long ago. I'm thinking the previous example was just an extremely stripped-down explanation of how a non-specific LS routing protocol works, and wasn't entirely accurate since each router DOES exchange this information with each of it's neighbors.

Of course now I'm wondering how loop avoidance works without split horizon still. I almost understand it, but I think I'll have to ponder it more... It seems it should be obvious.

typesh

bermovick wrote: »

Of course now I'm wondering how loop avoidance works without split horizon still. I almost understand it, but I think I'll have to ponder it more... It seems it should be obvious.

Check these out as well:

https://supportforums.cisco.com/thread/10878.pdf;jsessionid=BA687AF6313EC84533A52020AB126CFE.node0


Distance vector versus link-state - Packet Life

The PacketLife link shows an illustration of how each router "views" the network under DV and LS protocols. I found it very helpful.

bermovick

Hehe, your first link quickly goes over my head. Perhaps I can try reading it again later when I'm not trying to absorb everything I've just read from my book.

The PacketLife link actually does look good, and something I'll bookmark or keep open to refer to as I read, but here's my thoughts as to why loop avoidance isn't entirely prevented (although admittedly REALLY unlikely):

Ok, the 10-second update is just a 'keepalive' HELLO, and doesn't contain any LSA information.
Every 30 minutes (from the last time this happened) each router that's directly connected to a given subnet broadcasts out the LSA.
If that link goes down while this 30-minute LSA broadcast is still propagating(sp?), I see the potential for a loop (edit: or ... something) to be created.

Using the PacketLife topology, with the addition of an R2-R4 link, if the R1-R3 link goes down right after those 2 routers broadcast it, here's the scenario I think:
R1 & R3 sends out the 30-minute LSA broadcast.
link drops.
R1 & R3 send out an update that the link is down.
R2 and R4 receive the 1st broadcast.
R2 and R4 (both?) copy the broadcast out the R2-R4 link.
R2/R4 receive the 'link down' update.
R2/R4 receive the first LSA update from R4/R2

GAH, the timing of things gets confusing. Maybe I'm once again over-thinking it.

typesh

This is what the first link says about loop avoidance:

There is no loop avoidance in OSPF,
like those you would see in distance-vector routing protocols.
The loop avoidance is inherent in the SPF algorithm,
which OSPF (as a link-state routing protocol) uses to calculate routes.
This way, a tree is built for each router with itself as the root.
Trees by definition do not have loops.
Extensions to this tree exist only for load-balancing reasons.

So it looks like loop avoidance is built into SPF.

bermovick wrote: »

Using the PacketLife topology, with the addition of an R2-R4 link, if the R1-R3 link goes down right after those 2 routers broadcast it, here's the scenario I think:
R1 & R3 sends out the 30-minute LSA broadcast.
link drops.
R1 & R3 send out an update that the link is down.

At that point all the other routers will receive messages that the subnet has failed. So if the R1-R3 link fails, then R4 will recalculate and realize that it can still reach R1 (and available R1 subnets) by going from R3 to R2 and then to R1.

Does that help at all...?

bermovick

Actually you know what? I think it does... sortof. I think I was still thinking in distance-vector terms. It's still pretty tough to wrap my head around the whole 'each router knows the entire topology' though, because I think that's the key to how it avoids loops like I outlined above. I'll just have to take it on faith for now I think and try to make sense again later when I have additional information.

JaCkNiFe

Firstly; Hello Everyone, I am new to the forum. I am happy to be a part of a Cisco community.

LSA (Link State Advertisements)- OSPF data packets that contain link-state and routing information that neighboring routers use to update their LSDB.

LSDB (Link State Database)- Best visualized as a (topology) map that the Dijkstra's SPF algorithm uses to calculate the best route(s) (through a metric of "cost") to be placed in the routing table.

Each router receiving an LSA will be asked to check its LSDB against the LSA. If the receiving routers LSDB does not reflect the changes within the LSA it will update its LSDB and forward the LSA to adjacent Routers within the same area, that do not have an updated copy of the LSDB. This process will continue until all routers within the Area have the updated LSDB. LSA are flooded when OSPF neighborships are formed, every 30 minutes by default, and when something changes within the topology.


I hope that helps.