Routing is the process of moving packets from one network to another. The routing decision takes place at the source network device. That is a router. The decision is made based on metrics used for a particular routing protocol. Routing protocols may use some or all of the following metrics in determining the best route to a destination network:

• Path length
• Reliability
• Delay
• Bandwidth
• Load
• Communication cost

Path length is measure in either a cost or a hop count. In link-state routing protocols, the cost is the sum of the costs associated with each link in the path. Distance-vector routing protocols assign a hop count to the path length, which measures the number of routers a packet traverses between the source and destination.

Reliability is typically the bit-error rate of a link connecting this router to a source or destination resource. For most of the routing protocols, the reliability of a link is assigned by the network engineer. Since it is arbitrary it can be used to influence and create paths that are favorable over other paths.

The delay metric is an overall measurement of the time it takes for a packet to move through all the internetworked devices, links and queues of each router. In addition, network congestion and the overall distance traveled between the source and destination are taken into consideration in evaluating the delay metric value. Because the delay value takes into account many different variables, it is an influential metric on the optimal path calculation.

Using bandwidth as a metric in optimal path calculations may be misleading. Though bandwidth of a bandwidth of 1.54 Mbps is greater than 56 Kbps, it may not be optimal due to the current utilization of the link or the load on the device on the receiving end of the link.

The load is a metric that assigns a value to a network resource based on the resources overall utilization. This value is a composite of CPU utilization, packets processed per second, and disassembly/reassembly of packets among other things. The monitoring of the device resources itself is an intensive process.

In some cases, communication lines are charged based on usage versus a flat monthly fee for public networks. For example, ISDN lines are charged based on usage time and potential the amount of data transmitted during that time. In these instances, communication cost becomes an important factor in determining the optimal route.

In designing a routing protocol based network the routing algorithm should have the following characteristics built into the design:

Optimality - using some or all of the metrics available for a routing protocol in order to calculate the optimal route. Different routing protocols may apply one metric as having a higher weight to the optimal route calculation than another has. An understanding of this behavior is important in choosing the routing protocol.

Simplicity - While routing protocols themselves may be complicated their implementation and operational support must be simplistic. Router overhead and efficient use of router resources is important in maintaining a stable and reliable network.

Robustness - Choose a routing algorithm that meets the requirements of the network design. In some cases, for instance small networks, a simplistic distance-vector routing protocol is sufficient. In large networks that require a hierarchical design requires the ability of the routing protocol to scale to the size of the network without itself becoming a hindrance on the network.

Rapid Convergence - The convergence time to recalculate and then use a new optimal path between a source and destination resource is paramount in meeting availability and service level requirements of a network.

Flexibility - The algorithms employed by the selected routing protocol must be flexible and adapt to the changing dynamics of network resources and the network as a whole.

1. RIP, RIP2 and IGRP Network Design

   RIP, RIP2 and IGRP are distance-vector based routing protocols. Distance-based vector routing protocols base the optimal route on the number of hops (i.e., devices) a packet must pass through to reach a destination. Routing Information Protocol (RIP) was the first routing protocol algorithm for distributing, calculating and managing available routes within a network. Interior Gateway Routing Protocol (IGRP) is a Cisco proprietary routing protocol algorithm using enhanced optimal route calculation. IGRP calculates optimal routes based on bandwidth, delay, reliability and load. RIP2 is the second generation of RIP. RIP2 supports the Internet Protocol Version 6 specification for 128-bit addressing, variable-length subnet masks (VLSM) and route summarization.

   1. Topology

      Distance-vector routing protocols use a flat network topology as shown in Figure 4.1. Since these protocols are distance-vector based routing algorithms it is beneficial to minimize the number of hops between two destinations. This requires careful planning of the core, distribution and access topology layers in planning the hierarchical service model. For most cases, when deploying distance-vector based routing protocols the service functions of the core, distribution and access layers typically co-mingle within a single router.

   2. Addressing and Summarization

      In RIP and IGRP networks the IP 16-bit addressing scheme of IP version 4 is supported. RIP2 supports both the IP version 4 16-bit and IP version 6 128-bit addressing scheme. Additionally, RIP and IGRP support on fixed subnet masks for a network. Every subnet address used in the RIP or IGRP network must use the same subnet masking. RIP2 using VLSM and the 128-bit addressing scheme allows for varied subnet masks of the router interface. This is because the RIP2 routing packet includes the subnet mask of the source and destination IP address. Because RIP2 supports VLSM the routing tables use are summarized. This reduces the memory requirements on the router by keeping the routing table to a minimum. RIP and IGRP do not summarize since every entry represents a unique network or subnet.

   3. Route Selection and Convergence

      Both RIP and RIP2 base the optimal route selection on the number of hops. IGPR enhances this by incorporating bandwidth, delay, reliability and load. Figure 4.2 illustrates the route selection difference between RIP, RIP2 and IGRP. RIP and IGRP use the first route within their routing tables as the optimal route for a destination network or subnet. RIP does not load balance so multiple entries within the table for a destination network only become available if the optimal route is recalculated as less favorable. IGRP will load balance packets over equal-cost paths to s destination network or subnet. This load balancing occurs in a round-robin fashion. Both RIP and IGRP build their tables and then transmit the entire routing table to adjacent routers. Each router in turn recalculates its table based on the information received from the sending router. Once this is completed the router forwards its new table to adjacent routers. Both RIP and IGRP periodically send their routing tables to adjacent routers. RIP defaults to a 30 second interval for sending the routing table to adjacent routers. IGRP defaults to a 90 seconds interval for sending the routing table to adjacent routers. Both RIP and IGRP will recalculate routing entries once recognizing a link outage or timeout to an adjacent router. However, the recalculated routing table is not forwarded to adjacent routers until the update interval has been reached. The periodic updating of neighbor routers for topology changes causes excessive convergence time for the network to learn new optimal routes.

      RIP2 however, addresses the periodic update problem by sending only the updated route entry at the time of the recalculation. While this sounds much like a link-state protocol update RIP2 still sends the entire table on a periodic basis. The ability of RIP2 to send an update at the time it is recalculated reduces the convergence time. RIP2 sends the entire routing table on a periodic basis just as RIP and IGRP. However, the table is smaller due to the use of VLSM and route summarization. RIP2 will load balance packets to a destination network or subnet over equal-cost paths.

   4. Network Scalability

   The time for convergence of RIP, IGRP and RIP2 networks is the single inhibitor to scaling these protocols to large networks. Convergence is not just a time factor but also a CPU and memory issue on each router. These protocols recalculate the entire table during convergence versus just the affected route. Therefore, convergence becomes a CPU intensive process thereby reducing the ability of a router to provide service levels during convergence. Since these protocols send the entire table in a periodic timeframe they consume bandwidth causing bandwidth constraints in an ongoing basis.

2. EIGRP Network Design

   Enhanced Interior Gateway Protocol (EIGRP) is a proprietary routing protocol of Cisco Systems. EIGRP merges the best of distance-vector protocol characteristic with advantages of link-state protocol characteristics. In addition, EIGRP uses Diffusing Update Algorithm (DUAL) for fast convergence and further reduction of possible routing loops with in the network. An advantage to using EIGRP over other routing protocols is its ability to support not only IP but also Novell NetWare IPX, and AppleTalk, thus simplifying network design and troubleshooting.

   1. Topology

      EIGRP uses a non-hierarchical flat networking topology. EIGRP automatically summarizes subnet router for networks directly connected to the router using the network number as the boundary. It has been found that the automatic summarization is sufficient for most IP networks.

   2. Addressing and Summarization

      EIGRP supports variable-length subnet masking (VLSM). Defining an address space for use by an EIGRP is a primary step in developing the routing architecture. EIGRP support for VLSM is made possible by including the subnet mask assigned to the router interface in the EIGRP routing messages. VLSM is essentially the subnetting of a subnet (sub-subnet). Using an appropriate addressing scheme, the size of the routing tables and convergence time can drastically be reduced through route summarization. EIGRP automatically summarizes the routes at network number boundaries. Figure 4.3 diagrams the use of route summarization. However, the network engineer can configure route summarization at the interface level using any bit-boundary of the address to further summarize the routing entries. The metric used in route summarization is the best route found for the routes used to determine the summarized route.

   3. Route Selection

      EIGRP uses the same metrics as IGRP. These values are bandwidth, delay, reliability and load. The metric placed on a route using EIGRP defaults to the using the minimum bandwidth of each hop plus a media-specific delay for each hop. The value for the metrics used in EIGRP are determined s follows:

      Bandwidth - EIGRP uses the default value for each interface to the value specified by the bandwidth interface command.

      Delay - The inherent delay associated with an interface. The delay metric can also be defined on an interface using the delay interface command.

      Reliability - A dynamically computed value averaged over five seconds. The reliability metric changes with each new weighted average.

      Load - A dynamically computed weighted average over five seconds. The load metric changes with each new weighted average.

   4. Convergence

      EIGRP employs Diffusing Update Algorithm (DUAL) for calculating route computations. DUAL uses distance vector algorithms to determine loop-free efficient paths selecting the best path for insertion into the routing table. DUAL however, also determines the second best optimal route for each entry termed a feasible successor. The feasible successor entry is used when the primary route becomes unavailable. Figure 4.4 illustrates the use of the feasible successor. Using this methodology of successor routes avoids a recalculation and therefore minimizes convergence time. Along with primary routes, EIGRP distributes the feasible successor entries to the neighboring routers.

   5. Scalability

      Scalability is a function of memory, CPU and bandwidth efficiencies. EIGRP is architected in optimizing these resources. Through route summarization, the routes advertised by neighbors are stored with minimal memory required. This enables an EIGRP network to expand without routing issues. Since EIGRP uses DUAL only routes that are affected by a change are recomputed and since EIGRP is based on using the same metrics as IGRP the computation CPU requirements are minimal. Because EIGPR only sends updates due to topology changes bandwidth is preserved. Steady-state bandwidth utilization of EIGRP is minimal due to the use of EIGRP's HELLO protocol for maintaining adjacencies between neighbors.

   6. Security

   Since EIGRP is a Cisco IOS proprietary routing protocol it is available only on Cisco routers. Additionally, route filters and authentication can be specified to further limit accidental or malicious routing disruptions from unknown routers connecting to the network.

3. OSPF Network Design

   Open Shortest Path First (OSPF) is a standards based link-state routing protocol defined by the Internet Engineering Task Force (IETF) OSPF workgroup and published in Request for Comment (RFC) 1247. OSPF is based on autonomous system (AS). OSPF defines an AS as a group of routers exchanging routing information using link-state protocol. OSPF is based on using a hierarchical networking topology. Defining the hierarchy requires planning to define boundaries that denote an OSPF area and address assignment.

   1. Topology

      OSPF defines its hierarchy based on areas. Figure 4.5 illustrates the OSPF hierarchy and various areas used to build and connect the OSPF network. An area is a common grouping of routers and their interfaces. OSPF has one single common area through which all other areas communicate. Due to the use of the OSPF algorithm and its demand on router resources it is necessary to keep the number of routers at 50 or below per OSPF area. Areas with unreliable links will therefore require many recalculations and are best suited to operate within small areas.

      The OSPF algorithm using a flooding technique for notifying neighbors of topology changes. The greater number of neighbors the more CPU intensive the topology change since the new route must be recalculated and forwarded to all attached neighbors. Cisco studies have resulted in a recommendation of no more than 60 neighbors per OSPF router.

      The OSPF link-state algorithm calculates a change for each specified area defined on the router. Area routers are usually also area border routers (ABR). That is they maintain and support OSPF routing tables for two OSPF areas. In general, there is a minimum of two areas for an ABR: The backbone area and one non-backbone area. The recommendation for OSPF is to limit the number of supported areas in a router to three. This will minimizes resources utilization for the calculation and distribution of link-state updates.

      OSPF uses a designated router as the keeper of all the OSPF routes within a local-area network. This reduces routing updates over a LAN thereby preserving LAN media bandwidth. OSPF routers attached to the same LAN as the designated router request a route only if their own table does not have an entry for the destination resource. A backup designated router is also used for availability and redundancy. The recommendation is to have a designated and backup designated router supporting only one LAN. In addition, the designated and backup designated router should be the least CPU intensive router on the LAN.

      The OSPF backbone must be designed for stability and redundancy. A link failure that partitions the backbone will result in application outages, which leads to poor availability. The size of the backbone should follow that recommended areas to be no more than 50 routers.

      Routers within the OSPF backbone must be contiguous. This follows the concept of the hierarchy and maintains the traffic for backbone updates within the backbone area routers. However, OSPF offers the use of a virtual link for connecting two non-contiguous routers through a non-native area router. Using a virtual link, a partitioned backbone can be circumvented until the link failure causing the outage is corrected. Finally, reserve the media used for the OSPF backbone for routers to avoid instability and unrelated routing protocol traffic.

      As with backbone areas each OSPF area must be contiguous. Not only contiguous in design but also contiguous in the network address space. Using a contiguous address space makes route summarization possible. The routers of an area connecting the area to the OSPF backbone area are termed area border routers (ABR). For availability, it is deemed appropriate to have more than one ABR connecting the area to the backbone area.

      Designing large-scale OSPF networks requires a review of the physical connectivity map between routers and the density of resources. Designing the network into geographic areas may be beneficial for simplifying implementation and operations but may not be beneficial for availability or performance. In general, smaller OSPF areas generate better performance and higher levels of availability than large OSPF areas.

   2. Addressing and Summarization

Maximizing the address space in OSPF networks assists in reducing resource utilization and maximizes route summarization. A hierarchical addressing scheme is the most effective means of designing an OSPF network. OSPF supports VLSM that lends itself to a hierarchical network address space specification. Using VLSM, route summarization is maximized at the backbone and ABR routers. Guidelines in defining an OSPF network for optimized route summarization are:

• Define the network address scheme in subnet ranges for use in each contiguous area.
• Use VLSM addressing to maximize address space.
• Define the network address space for future growth to allow the splitting of an area.
• Design the network with the intention of adding new OSPF routers in the future.

Route summarization increases the stability of an OSPF network. Using route summarization keeps route changes within an area. Route summarization must be explicitly specified when working with OSPF networks on Cisco routers. The specification of router summarization requires the following information:

• Determine route information needed by the backbone about each area
• Determine route information needed by an area for the backbone and other areas

OSPF route summarization occurs in area border routers. Using VLSM, bit-boundary summarization is possible on network or subnet addresses within the area. Since, OSPF route summarization is explicit the network design must incorporate summarization definitions for each OSPF area border router.

OSPF areas offer four types of routing information. These are:

Default - A default route of all packets for which the destination IP network or subnet is not explicitly found in the routing tables.

Intra-area routes - These are routes for network or subnets within a given area.

Interarea routes - This information provides areas with explicit network or subnet routers for networks or subnets within the OSPF autonomous system but not within the area.

External routes - These are routes learned from the exchange of routing information between autonomous systems. This results in routes that are external to the OSPF autonomous system.

OSPF route information provides information on three types of OSPF areas. These are non-stub areas, stub areas and stub areas without summaries. Stub areas are OSPF areas that connect only to one other area and therefore are considered a stub off the hierarchy. A non-stub area is an OSPF area that provides connectivity to more than one OSPF area.

Non-stub area characteristics are:

• Store default routes, static routes, intra-area routes interarea routes and external routes.
• OSPF interarea connectivity.
• Uses autonomous system border routers.
• Virtual links require non-stub areas.
• Most resource-intensive type of area.

Stub area characteristics are:

• Build default, intra-area, and interarea routes.
• Most useful in areas containing one ABR
• May contain multiple area border routers to same area
• Virtual links cannot connect through stub areas
• Cannot use autonomous system border routers.

Stub areas without summaries contain:

• Default and intra-area routers
• Recommended for single router connections to the backbone.

Table 4.x lists the OSPF area types against the routing information supported.

	Routing Information type
Area Type	Default	Intra-area	Interarea	External
Nonstub	Yes	Yes	Yes	Yes
Stub	Yes	Yes	Yes	No
Stub without summaries	Yes	Yes	No	No

1. Route Selection

   OSPF defaults route selection to the bandwidth metric. Under OSPF the bandwidth metric is determined by the type of media being used. The bandwidth metric for a link is the inverse of the bandwidth supported by the media used for the link. The bandwidth metric has been calibrated based on a metric of 1 for FDDI media. Figure 4.6 depicts an OSPF network and the applied bandwidth metric. The total metric for a given route is the sum of all the bandwidth metric values of all the links used for the route. Media that supports bandwidth greater than FDDI 100 Mbps default to the FDDI metric value of 1. In a configuration where media types connecting the router are faster than FDDI a manual cost greater than 1 must be applied to the FDDI link in order to favor the higher speed media type.

   OSPF route summarization uses the metric of the best route found within the summarized routes as a metric value for the summarized entry.

   OSPF external routes are defined as being either a type 1 or type 2 route. The metric for a type 1 external route is the sum of the internal OSPF metric and the external route metric. Type 2 external routes use only the metric of the external route. Type 1 external route metrics are more favorable in providing a truer metric for connecting to the external resource.

   For single ABR OSPF areas, all traffic leaving the area flows through the single ABR. This is done by having the ABR exchange a default route with the other routers of the area. In multiple ABR OSPF areas, the traffic can leave either through the ABR closest to the source of the traffic or the ABR nearer to the destination of the traffic. In this case, the ABRs exchange summarized routes with the other routers of the area.

   High availability network design requires redundant paths and routers. Redundancy is useful when employing equal-cost paths to take advantage of load balancing. Cisco routers will load-balance over a maximum of four equal-cost paths between a source and destination using either per-destination or per-packet load balancing when using OSPF. The default of per-destination is based on connectivity bandwidth at 56 Kbps or greater.

2. Convergence

   Since OSPF is a link-state based routing protocol, it adapts quickly to network topology changes. OSPF detects topology changes based on interface status or the failure to receive a response to an OSPF HELLO packet of an attached neighbor within a given amount of time. OSPF has a default timer of 40 seconds in broadcast networks (i.e., LANs) and two minutes in non-broadcast networks (i.e., WANs).

   The routes are recalculated by the router recognizing the failed link and sends a link-state packet to all the routers within the area. Each router then recalculates all the routes within its routing table.

3. Scalability

   The addressing scheme, number of areas and number of links within the OSPF network all affect the scalability of an OSPF network. Routers use memory for storing all the link states for each area a router belongs. The more areas attached to a router the larger the table. Scaling OSPF therefore depends on the effective use of route summarization and stub areas to reduce memory requirements. The larger the link-state database the more CPU cycles required during recalculation of the shortest path first algorithm. Minimizing the size of a OSPF area and the number of links within the area along with route summarization enables OSPF to scale to large networks. OSPF only sends small HELLO packets and link-state updates when a topology change occurs or at start-up. This is a great benefit for preserving bandwidth utilization as compared to distance-vector routing protocols such as RIP or IGRP.

4. Security

OPSF can use an authentication field to verify that a router connecting as a neighbor is indeed a router that belongs within the network. OSPF routers by their very nature do not allow the filtering of routes since all OSPF routers must have the same routing information within an area. Using authentication, an OSPF router can verify that it should exchange topology information with a new router that has joined the network. In this way, not only does OSPF provide some protection from unwanted access, it assists in keeping a stable network.