SPF Algorithm - Equal Cost Routes

I have a question on the SPF algorithm.  During the SPF run, if there are two or more equal cost paths to a router which path is placed in the tree database?  I don't recall seeing anything on it in the video and the book TCP/IP Routing (Vol1) says if there are two or more equal cost paths choose one.  There is nothing on how that path is chosen.  Thanks!

Comments

  • peetypeety ✭✭✭

    I'd say it's probably "arbitrary", and you're probably dependent upon how the internal data structures are buit.

    When I "teach" the algorithm for OSPF, I use an example that shows a rather mechanical process.  http://ieoc.com/forums/p/23086/179726.aspx#179726

  • JoeMJoeM ✭✭✭

    I have a question on the SPF algorithm.  During the SPF run, if there are two or more equal cost paths to a router which path is placed in the tree database?  I don't recall seeing anything on it in the video and the book TCP/IP Routing (Vol1) says if there are two or more equal cost paths choose one.  There is nothing on how that path is chosen.  Thanks!

     

    For context, which video are you referencing?   I have the INE CCNP series.

    Since this appears to be for the CCNP, I will put my focus on OSPF.

    My answer is, all of them would go into the OSPF database. However, I think the real question is, which equal-cost paths would make it from the OSPF database into the routing table (and cef)?

     

    For redistributed routes (LSA 5), it would depend on the forwarding address.  Which of the original redistributing routers is the closest (forwarding metric).

    The Effects of the Forwarding Address on Type 5 LSA Path Selection

    "....When the metric of the redistributed route from multiple ASBRs are
    equal as illustrated in the document, the forwarding address changes the
    behavior of the type 5 LSA path selection. When a router receives two type 5
    LSAs to the same destination with the forwarding addresses set on both LSAs,
    the router makes a comparison based on the metric to the forwarding addresses.

    The LSA with a forwarding address that offers the smaller metric is placed into
    the routing table."

     

    Otherwise, I think it would only depend on the number of maximum-path permitted. By default, this is 4, and can be increased to a max of 16.

     

    Here is another interesting CISCO faq answer?

    Q.
    What algorithm is used by OSPF if equal cost routes exist?




    A. If equal cost routes exist, OSPF uses CEF load balancing. For more
    information, refer to
    Troubleshooting
    Load Balancing Over Parallel Links Using Cisco Express
    Forwarding
    .

     

     

  • Thank-you both for the quick replies.  You are both touching on part of my question.  The initial question was related specification to the SPF run and how a equal cost path is chosen to be placed in the SPF tree.  The next part of the question is if only one path is chosen for the SPF tree how do multiple equal cost paths get installed in the LSDB and later the routing table.  I'm trying to understand the correlation between the SPF tree and the LSDB.  Thanks!

  • JoeMJoeM ✭✭✭

    Follows the rules of OSPF using the Dijkstra Algorithm.

    Here is a basic explanation without the math. TCP/IP GUIDE:  OSPF Route Deternmination using SPF Trees

     

    EDIT:  The SPF tree is created from the LSDB which is an accumalation of the LSA's received.

    Definitely not true that there is always (only) a single path chosen. By default, 4 equal-cost paths are allowed.

    What is the full statement from the book?    Possibly an an error or incomplete explanation?

  • Sorry, for the delay in my response.  Here is the excerpt from TCP/IP Vol1 I referenced:

    1.  A router initiallizes 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 hjust added to the Tree database is examined.  With the exception of any triple 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, 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.

    I may be overthinking this but I want to make sure I understand the process.

    Thanks!

  • There is a good description of this in:

     

    OSPF and IS-IS: Choosing an IGP for Large-Scale Networks

     

    8.1. SPF Enhancements

    8.1.1. Equal-Cost Multipath

     

    Previously the algorithm would randomly select one path if there were two equal cost paths. Then SPF was modified to include both of them.

     

    Old behaviour:

     


    3.


    The cost from the root to each node in the candidate database is calculated. The link in the candidate database with the lowest cost is moved to the tree database, along with the cost from the root. If two or more links are an equally low cost from the root, choose one. If any entries are left in the candidate database with a link to the neighbor just moved to the tree, those entries are deleted from the candidate database.


    New behaviour:


    But the inefficiency of this rule also reveals itself at this point. If multiple equal-cost paths exist, choosing only one of the paths means all traffic will be routed on that path, possibly congesting it, while other equally good paths are ignored. We can modify Step 3 so that if there are multiple links in the candidate database to the same node and equally low cost, all the links can be moved from the candidate database to the tree database. InFigure 8.9, moving the R3-R4 link to the tree database empties the candidate database so that the SPF can stop. An enhancement to the router’s forwarding processes can then be made that takes advantage of these multipleequal-cost paths by spreading traffic across all of them. This is equal-cost multipath (ECMP), or load balancing.[1]

    [1] Load balancing is a more generic term that can also refer to data processing, such as spreading traffic across multiple Web servers. ECMP is more specific to the forwarding of network traffic.

    This is a great book so I recommend you read it. Sorry for the wonky formatting, for some reason when pasting it seems I get the formatting from the book.


Sign In or Register to comment.