|
Home > Archive > CCNP > January 2003 > Dijkstra
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
|
|
| wirelessboy 2003-01-08, 4:55 am |
| dear all
Can we debug the activities of the Dijkstra algorithm , in a cisco router?
how does it go about calculating the best routes based on the link-state database
regards to all | |
|
| Debug IP ospf tree is a valid command, but not in the debug command reference so not too sure if it does exactly what you after, I'll try when I next do an OSPF lab.
I think you need to get hold of a copy of Routing TCP/IP Vol1 for how Dijkstra works, it's clearly laid out on P176 to 181, but a bit lengthy for retyping!!!
It's a book I wish I'd read when I was doing my CCNP - it would have made routing a lot easier. | |
| FastIP 2003-01-08, 12:12 pm |
| Try this: It is a Java applet showing the operation of Djikstra's SPF algorithm
http://www-b2.is.tokushima-u.ac.jp/...App.shtml?demo2
There are variations to the shapes of the trees in the demos on the left hand side of the page. Just choose the numbered demos.
Enjoy 
FastIP | |
| Mat P 2003-01-08, 12:26 pm |
| Great link, and the following quote from the book I mentioned explains it in laymans (ish) terms:
1. A router initializes the Tree database by adding itself as the root. This entry shows the router as its own neighbor, with a cost of 0.
2. All triples in the link state database describing links to the root router's neighbors are added to the Candidate database.
3. The cost from the root to each link in the Candidate database is calculated. The link in the Candidate database with the lowest cost is moved to the Tree database. If two or more links are an equally low cost from the root, choose one.
4. The Neighbor ID of the link just added to the Tree database is examined. With the exception of any triples whose Neighbor ID is already in the Tree database, triples in the link state database describing that router's neighbors are added to the Candidate database.
5. If entries remain in the Candidate database, return to step 3. If the Candidate database is empty, then terminate the algorithm. At termination, a single Neighbor ID entry in the Tree database should represent every router, and the shortest path tree is complete. | |
|
|
|
| Both great links, hopefully wirelessboys original question has been answered - or at least one of them. | |
|
|
|
|
|
