First note that LSAs are flooded throughout an area; this allows every router in an area to build link state databases with identical topological information. Shortest path computation based on Dijkstra’s algorithm (see Section 2.3) is performed at each router for every known destination based on the directional graph determined from the link state database; the cost used for each link is the metric value advertised for the default type of service in the link LSA packet; see Figure 6.11 presented later for the metric field. Originally, it was envisioned that there be different types of services that might require different metrics. Thus, a type of service (TOS) field was created. The default TOS is indicated by setting field, Number of TOS, to 0.
Metric field allows the value to be between1and65,535, both inclusive. If additional types of services are defined and supported by routers in an area, then for each type of service the shortest path can be computed separately. While the default metric is dimensionless, addi- tional types of services are identified based on attributes such as monetary cost, reliability, throughput, and delay. At the same time, the default metric being dimensionless provides the flexibility to not explicitly consider metrics for other types of services in an operational environment since through IP traffic engineering the link metric/cost can be determined and
F I G U R E 6.2 OSPF link state database synchronization process (based on [505]).
set just under the default TOS, which can still take into account diverse goals of a network and the network provider; we will discuss link cost determination for IP intradomain traffic engineering in Chapter 7.
A nice feature of Dijkstra’s algorithm computed at each router is that the entire shortest path from a source to a destination (in fact, for all destinations) is available at the end. OSPF allows a source routing option that can be used by user traffic on the path determined by Dijk- stra’s algorithm. Certainly, OSPF allows the default next hop option commonly deployed in IP networks; thus, once the path is computed, the next hop is also extracted from the shortest
path computation to update the routing table, and subsequently, the forwarding table. Note that routing table entries are for destinations identified through hosts or subnets or simply IP prefixes (with CIDR notation), not in terms of end routers. Thus, once the shortest path first computation is performed from a router to other reachable routers, reachable addresses from each destination router as learned through LSAs are identified, and the routing table en- tries are accordingly created for all such addresses. Because of CIDR, multiple similar route entries are possible. For example, there might be an entry for 10.1.64.0/24, and another for 10.1.64.0/18, where the difference is in the netmask. To select the route to be preferred by an arriving packet, OSPF uses a best route selection process. According to this process, the route(s) with the most specific match to the destination is to be selected, which is the one with the longest match. As an example, 10.1.64.0/24 would be preferred over 10.1.64.0/18. In case there are multiple paths available after this step, the second step selects the route where an intra-area path is given preference over an interarea path, which, in turn, gives preference over external paths for routers learned externally (refer to Section 6.2.8).
ECMP
An important feature of OSPF routing computation is the equal-cost multipath (ECMP) option;
that is, if two paths have the same lowest cost, then the outgoing link (next hop) for both can be listed in the routing table so that traffic can be equally split. It may be noted the orig- inal Dijkstra’s algorithm generates only one shortest path even if multiple shortest paths are available. To capture multiple shortest paths, where available, Dijkstra’s algorithm is slightly modified. In line 23 of Algorithm 2.5 in Chapter 2, if the greater than sign (>) is changed to a greater than or equal to sign (≥), it is possible to capture multiple shortest paths by identi- fying the next hops. In this case, line 25 is then updated to collect all next hops that meet the minimum, instead of just one when the strictly greater than sign is used. Thus, more than one outgoing link in the case of multiple shortest paths would need to be stored, instead of just one.
It is important to note that ECMP is based on the number of outgoing interfaces (links) involved on the shortest path at node level along the path, not at the source-destination path level. Consider the six-router network shown in Figure 6.3. Suppose the paths between router 1 and router 6 are of equal cost. Thus, for traffic from router 1 to router 6, it will be equally split at router 1 along the two directional links1→2 and1→5; traffic from router 1 that arrived at router 2 will be equally split further along its two outgoing links2→3 and 2→4. Thus, of the traffic from router 1 destined for router 6, 25% each will arrive at router 6 from links3→6and4→6, while one-half will arrive from link5→6. This illustrates the mean- ing of equal-cost being node interface–based. Since OSPF routing is directional, the traffic splitting for this example will be different for traffic going the other direction from router 6 to router 1. Since router 6 has three outgoing links, traffic will be split equally among the links6→3,6→4, and6→5. Note that the traffic sent on the first two links will be combined at router 2; thus, two-thirds of the traffic from router 6 destined for router 1 will arrive at router 6 from link2→1, while one-third will arrive from link5→1.
It may be noted that the OSPF specification does not say exactly how ECMP is to be accomplished from an implementation point of view. In concept, packets that arrive for the same destination router can be equally split among outgoing links of ECMP paths. However, this is not desirable for several reasons. For example, for a single TCP session (microflow), if
F I G U R E 6.3 OSPF equal-cost multipath (ECMP) example.
the packets are sent on different ECMP paths that might consist of links with different link bandwidths, packets can arrive with different delays; this can then affect TCP throughput.
If packets for this session are alternated across each link, then packets can arrive out of or- der. Thus, router software implementation handles ECMP path selection on a per-microflow basis. Yet, implementation at a per-microflow choice level at a router can have an effect as well. If every router in the network makes identical decisions because of the way flows are processed by the router software, for example, due to prefix matching, then microflows that arrive at router 1 destined for router 6 that are directed to link 1-2 would use only one of the paths 2-3-6 or 2-4-6 (see Figure 6.3). Thus, sophisticated, yet fast, router software imple- mentation addresses randomization of microflows to different ECMP outgoing links so that such situations do not occur. In summary, ECMP is possible only as approximate split by ran- domizing at a per-microflow level (or destination address level) from a practical point of view.
The ECMP feature is helpful in load balancing traffic, but may not be helpful when trou- bleshooting a network. Thus, some providers try to avoid using ECMP; that is, they seek the single shortest paths, to the extent possible. This will be discussed further in relation to IP traffic engineering in Chapter 7.
INTERAREAROUTINGCOMPUTATION
It is important to note that Dijkstra-based shortest path computation using link state in- formation is applied only within an area. For routing update between areas, information from one area is summarized using Summary LSAs without providing detailed link infor- mation; thus, interarea routing computation in OSPF is similar to the distance vector flavor.
Since OSPF employs only a two-level hierarchy, a looping problem typically known to oc- cur with a distance vector approach is not conceptually possible. Yet, due to aggregation and hierarchy, in certain situations, it is possible to create a scenario where looping can oc- cur [589].