From: Howard C. Berkowitz (hcb@gettcomm.com)
Date: Thu Jul 08 2004 - 21:11:36 GMT-3
At 6:01 PM -0400 7/8/04, Bob Sinclair wrote:
>Pierre,
>
>Personally, I find the math very difficult to understand. That is why I
>like the DEMOs on the page referenced. If you check them out and click
>through them carefully, I think it helps to make the algorithm clear by
>stepping through examples graphically.
Radia Perlman's book, Interconnections, is a nice balance between
narration and formality. My OSPF tutorial at CertificationZone.com
draws from it, although I made some of the terminology, I think, even
less mathematical.
I'm not sure how important it is to know the algorithm, especially
because the OSPF implementations are beginning to do
performance-related things that the classic Dijkstra does not. The
programming detail of an implementation also is very critical to
performance, although not of concern with respect to certification.
Frankly, I think someone really needs the background of an advanced
undergraduate or graduate course in data structures, with special
reference to graph theory and tree traversal algorithms, before
really being able to appreciate algorithms. That said, you can see
sample implementations in John Moy's books, especially the second.
One thing that _is_ important to know for certifications, but is
often missed, is that the Dijkstra algorithm ONLY does intra-area
routes. In the implementations I know, the intra-area routes are
created from the tree, and the tree memory is then released. Once the
shortest path tree is created, then, as inter-area and external (type
1, type 2) routes are obtained, they are checked against the table of
more preferable route types to see if there is already a route of
more-preferred type to the destination.
Only if there is no such more-preferred route will an
inter-area/external-1/external-2 route be generated by OSPF. This
logic cannot be overridden and is an essential part of OSPF's
generating loop-free routes.
It is worth knowing that the intra-area, Dijkstra part increases load
exponentially with the number of prefixes (and the log of the number
of routers), while the subsequent inter-area, etc., part increases
load linearily with the number of prefixes. This is one argument not
to make nonzero areas too large, or to connect too many nonzero areas
to the same ABR -- the Dijkstra computation will take too much
resources, or, with more and more areas on the same ABR, it becomes
more likely there will need to be simultaneous Dijkstra computations
in more than one area.
The implementation approach will probably change somewhat as
subsecond convergence becomes more of a requirement. There are faster
shortest-path algorithms than classic Dijkstra, and some of the new
implementation also keep less-than-best routes for failover without
full route recomputation.
>
>just my 2 cents,
>
>Bob Sinclair
>CCIE #10427, CISSP, MCSE
>www.netmasterclass.net
>
>----- Original Message -----
>From: "Pierre-Alex Guanel" <pierreg@planetkc.com>
>To: "Bob Sinclair" <bsinclair@netmasterclass.net>; "Ccielab@Groupstudy.Com"
><ccielab@groupstudy.com>
>Sent: Thursday, July 08, 2004 4:49 PM
>Subject: Re: Advanced: OSPF Algorithm
>
>
>> Thanks Bob,
>>
>> Simple to understand you said?
>>
>> Shortest Path Problem
>> Given a connected graph G=(V,E), a weight d:E->R+ and a fixed vertex s in
>V,
>> find a shortest path from s to each vertex v in V.
>>
>>
>> Dijkstra's Algorithm
>> Dijkstra's algorithm is known to be a good algorithm to find a shortest
>> path.
>> 1.. Set i=0, S0= {u0=s}, L(u0)=0, and L(v)=infinity for v <> u0. If |V|
>=
>> 1 then stop, otherwise go to step 2.
>> 2.. For each v in V\Si, replace L(v) by min{L(v), L(ui)+dvui}. If L(v)
>is
>> replaced, put a label (L(v), ui) on v.
>> 3.. Find a vertex v which minimizes {L(v): v in V\Si}, say ui+1.
>> 4.. Let Si+1 = Si cup {ui+1}.
>> 5.. Replace i by i+1. If i=|V|-1 then stop, otherwise go to step 2.
>> The time required by Dijkstra's algorithm is O(|V|2). It will be reduced
>to
>> O(|E|log|V|) if heap is used to keep {v in V\Si : L(v) < infinity}.
> >
>> http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/dijkstra/Dijkstra.shtml
>>
>> Pierre
>>
>>
>> ----- Original Message -----
>> From: "Bob Sinclair" <bsinclair@netmasterclass.net>
>> To: "Pierre-Alex Guanel" <pierreg@planetkc.com>; "Ccielab@Groupstudy.Com"
>> <ccielab@groupstudy.com>
>> Sent: Wednesday, July 07, 2004 7:41 PM
>> Subject: Re: Advanced: OSPF Algorithm
>>
>>
>> > Pierre,
>> >
>> > A good understanding of OSPF requires a feel for the Dijkstra algorithm.
>> > Check out the java-based demos at the link below. I think the demos
>show
>> > that the math is really very easy to understand. Amazing that this
>> > algorithm from the 1950s is still useful today.
>> >
>> > http://tinyurl.com/xlim
>> >
>> > HTH,
>> >
>> > Bob Sinclair
>> > CCIE #10427, CISSP, MCSE
>> > www.netmasterclass.net
>> >
>> >
>> > ----- Original Message -----
>> > From: "Pierre-Alex Guanel" <pierreg@planetkc.com>
>> > To: "Ccielab@Groupstudy.Com" <ccielab@groupstudy.com>
>> > Sent: Wednesday, July 07, 2004 2:23 PM
>> > Subject: Advanced: OSPF Algorithm
>> >
>> >
>> > > How does OSPF add the cost of the links?
>> > >
>> > > >From what I have seen, it does not seem like the cost in the packet
>> gets
>> > > updated from hop to hope.
>> > >
>> > > The process of flooding just passes the original lsa along, unaltered.
>> > >
>> > > >From what I read, the OSPF algorithm knows how to find all the costs
>> and
>> > add
>> > > them up from the LSA using the Djakstra algorithm.
>> > >
>> > > Yes I know its all explained in RFC 2178 ...section 16, but I am
>> looking
>> > at
>> > > a simple explaination.
>> > >
>> > > thanks,
>> > >
>> > > Pierre
>> > >
>> > >
>_______________________________________________________________________
>> > > Please help support GroupStudy by purchasing your study materials
>from:
>> > > http://shop.groupstudy.com
>> > >
>> > > Subscription information may be found at:
>> > > http://www.groupstudy.com/list/CCIELab.html
>>
>> _______________________________________________________________________
>> Please help support GroupStudy by purchasing your study materials from:
>> http://shop.groupstudy.com
>>
>> Subscription information may be found at:
>> http://www.groupstudy.com/list/CCIELab.html
>
>_______________________________________________________________________
>Please help support GroupStudy by purchasing your study materials from:
>http://shop.groupstudy.com
>
>Subscription information may be found at:
>http://www.groupstudy.com/list/CCIELab.html
This archive was generated by hypermail 2.1.4 : Sun Aug 01 2004 - 10:11:50 GMT-3