short computer networks review in 6 hours

OVERVIEW OF OPEN SHORTEST PATH FIRST, VERSION 2 (OSPF V2) ROUTING IN THE TACTICAL ENVIRONMENT

William V. Wollman and Yosry Barsoum The MITRE Corporation, 145 WyckofS Road, Eatontown, N . J . 07724

1.0 ABSTRACT

The United States Department of the Army is expected to mandate the use of the Open Shortest Path First, Version 2 (OSPF V2) as the interior gateway routing protocol for use across tactical communication systems that use the Internet Protocol (IP). This paper provides an overview of the OSPF V2 routing protocol and analysis of OSPF V2 routing overhead. The paper describes the minimum OSPF V2 routing overhead that can be expected when operating through the Single Channel Ground and Airborne Radio System (SINCGARS). The paper also suggests changes that will allow OSPF V2 to operate better in the tactical environment.

2.0 INTRODUCTION

OSPF V2 is a link-state routing protocol that employs a version of Dijkstra's shortest path first protocol, and is an open standard. OSPF V2 is defined by the Internet Engineering Task Force in Request for Comments (RFC) 1583 [l]. OSPF allows collections of contiguous networks and hosts to be grouped together. RFC 1583 labels such a group, together with the routers having interfaces to any one of the included networks, an area. OSPF areas are interconnected via a backbone area, which is called area zero. OSPF'requires that IP datagram exchanges between areas must traverse the OSPF backbone area.

OSPF V2 is normally used within primarily static corporate networks. Within the tactical environment, communication nodes are mobile and the networks connectivity and associated topology is in a constant state of change. Attrition can also lead to sudden

dramatic network topology changes. Also, tactical networks have significant bandwidth constraints. Therefore, the OSPF parameters used for operations in the tactical environment need to be well understood and carefully selected. Routing bandwidth utilization should be minimized. However, the ability to detect, advertise, and route around network outages should be timely. In addition, the grouping of networks within OSPFs hierarchical architecture should be carefully designed to ensure network reconfigurations can be performed with ease.

3.0 OSPF ROUTING PROTOCOL

OSPF supports a number of messages that allow routing information to be exchanged within and between areas. OSPFs area architecture limits the required number and size of routing messages through IP route aggregation at area boundaries. The OSPF IP routing database is maintained through the exchange of Link State Update (LSU) messages. LSU messages encapsulate a variety of OSPF messages called Link State Advertisements (LSAs). There are five types of LSAs that are defined within OSPF, as follows:

Router Link Advertisements (RLAs), Network Link Advertisements (NLAs), Network Summary Link Advertisements (SLAs), Autonomous System (AS) Boundary Router SLAs, and AS External Link Advertisements.

The nodes within an area use FUAs and NLAs to maintain a description of the area's topology and link connectivity. The RLA describes the state of a router's links to an area. The NLAs are used across multi-access networks

0-7803-2489-7/95 $4.00 0 1995 IEEE 925 28.6-1

by an elected Designated Router (DR) to advertise all of the routers that interface to the multi-access network. Multi-access networks include broadcast networks (e.g., the Ethernet and SINCGARS) and non-broadcast networks (e.g., X.25 and Frame Relay networks). Network SLAs are used to pass routing information between areas, which operate within the OSPF network. SLAs are only generated by routers that participate in more than one area, i.e., Area Border Routers (AJ3Rs). The last two LSAs are used to pass routing information from another AS to the areas within an OSPF network architecture.

3 . 1 THE OSPF BACKBONE NETWORK

One example of a simple OSPF network topology operating through SINCGARS is illustrated in Figure 1. In this illustration, the routers, SINCGARS Internet Controllers (INCs), which are directly connected to SINCGARS, support the backbone area, area zero. These INCs can also be referred to as ABRs, since they are attached to multiple areas. To minimize the amount of bandwidth utilized by the INCs to exchange routing information, OSPF allows the multi-access network DR to communicate routing information to all other routers that are directly connected to the multi-access network through the use of NLAs. In addition, a backup DR is selected to maintain operations of the network when the primary DR fails.

The determination of a DR is negotiated during the network's initial operations. These negotiations continue throughout the life of the multi-access network to ensure continued operations in case the elected DR or backup DR fail. The network designer can influence this process by configuring certain INCs with the ability to accept the DR role and others without this capability. Any INC with a router priority of zero will not be able to act as either a DR or a backup DR. However, if the SINCGARS network is partitioned during tactical operations,

at least one DR would be required in each partition to ensure continuity of operations.

OSPF AREA 0

Figure 1. SINCGARS Network Segmented into OSPF Areas By INCs

3.2 THE OSPF HELLO PROTOCOL

The OSPF Hello Protocol establishes and maintains router neighbor relationships and supports selection of the DR on multi-access networks. When a router's interface to the multi- access network becomes operational, the router will begin to send Hello packets to all of the other routers interfaced to the network every hello interval. Hello packets are transmitted across broadcast multi-access networks to the IP multicast address, "AIlSPFRouters." Non- broadcast multi-access networks normally require each potential DR to be configured with the IP addresses of potential multi-access network neighbor routers.

A small Hello interval will permit the quick selection of a DR and fast detection of connectivity changes within the network. However, this small interval consumes significantly more bandwidth than a longer Hello interval would require. However, if the network is partitioned, a longer Hello interval will delay the responsiveness of the network in determining partitions. Assumptions as to the likelihood of a network partition, the seriousness of that situation, and how much overhead is willing to be paid to obtain a desired level of responsiveness in discovering and recovering from a partition are required to determine the proper Hello interval.

28.6-2 926

The Hello interval is also correlated to an OSPF parameter known as the router dead interval. Normally, the default router dead interval is four times the chosen Hello interval. If four consecutive Hellos are missed, the router assumes that its neighbor is not operating. If a DR detects a dead neighbor, it will broadcast the change to the network within an LSU packet. It will also continue to send Hello packets to the dead neighbor to determine when it will become operational again. This hello message will be transmitted at a slower interval (i.e., the Poll interval) than the Hello interval. When the neighbor becomes operational again, a new LSU is broadcast to indicate the network's new state.

The dead interval timer is also used to determine the time required for a multi-access network to choose a DR. After a router's interface is initially activated on the multi-access network, it will remain in a wait state for a period of time equal to the dead interval timer value. During this period, the router will exchange hello packets with other routers operating on the network. Once this period expires, the router will propose a multi-access network DR based upon multi-access network router priorities and network connectivity, if a DR is not already chosen. Only routers with two way connectivity to the other routers on the network can be elected as the DR or backup DR. By specification, all of the routers communicating across a multi-access network must use the same hello interval and dead interval value. This simplifies OSPFs implementations, but limits flexible network designs. For instance, if different Hello intervals were allowed, OSPF routing overhead could be reduced [ 2 ] .

Including the IP header, the Hello packet contains a minimum of 64 bytes. A multiple of four additional bytes are concatenated to the packet to advertise the routers that the source has heard from within the past dead interval period. For transmission across SINCGARS, the IP datagram is then encapsulated within a MIL- STD-188-220( ) envelope, which requires 17

bytes of overhead. For instance, at least 85 bytes are transmitted within every Hello packet if there are two routers operating on the network. These Hello packets are transmitted once in every Hello interval. The Hello interval is a user-defined parameter that can be set to as low as one second. Generally, a higher value would be used. Of concern in the tactical environment is not only the bandwidth requirements of hello packets, but also the burst time required for each hello packet.

Figure 2 illustrates the bandwidth requirements in bits per second (bps) for hello exchanges across a twenty node broadcast network using a variety of hello intervals. If one assumes the data rate of SINCGARS network to be approximately 5 kbps, each router would require approximately a quarter of a second to transmit its hello packet, in addition to any radio key up time. For a tweny node network this would require a bit more than 5 seconds of OSPF transmission time per hello interval. This data assumes a fully connected SINCGARS network.

B

s 600 300 ;'!lEE3 0 1 5 30 45 60 90 120

Hello Interval in Seconds

Figure 2. OSPF Hello Bandwidth Requirements for a Twenty Node Broadcast Network

3 . 3 OSPF NETWORK TOPOLOGY DATABASE SYNCHRONIZATION

Once the multi-access network's DR is elected, the DR will attempt to establish an adjacency with all of the other routers attached to the network. This requires the exchange of a number of messages, which includes database description packets and Network LSAs. The database description packets describe the DRs

927 28.6-3

current information on the state of the area. Each router maintains a separate link state database for each interfaced area. This database consists of router, network, summary, and AS external LSAs. If neighbor router database description information differs, the two routers will exchange link-state requests (LSRs), updates, and acknowledgments to ensure that their databases are synchronized with the most current information about the common area's state. Note that link-state updates and link state acknowledgments are sent to the multicast address, "AllSPFRouters," by the DR and BDR. Other routers will send these messages to the "AllDRouters." Retransmissions of link-state updates are sent as unicast packets. During these exchanges the routers will pass through various states to include down, initialization, exchange started, exchange, loading and full. An illustration of the OSPF database exchange process is provided in Figure 3.

Hello (DR=O, seen=O) Down pb Down

Hello (DR=RTZ, seen -..., RTI) Init

D-D (Seq=y+n, Slave)

D-D (Ses=v+n, Master) m

Link State Request

Link Stare Update b Full Loading

Full

Figure 3. OSPF Database Description Exchange [l]

The database description packet consists of the 24 byte OSPF header and eight additional bytes to support database description packet

sequencing and miscellaneous protocol negotiation information. Optimally, the remainder of the packet contains LSA headers for every LSA known to the router. Because each LSA header uniquely describes a particular LSA and its age, an adjacent router can use this information to determine if its database is current. If the router determines that the LSA descriptor is not within its database or has an age less than its matching LSA, the router will request the complete LSA from its neighbor within a LSR packet. Each LSR packet includes an OSPF header and 12 bytes of information, which describe each LSA requested. Each router is only permitted one outstanding LSR packet at any time. The number of LSAs that are required within a database description is dependent on the size and architecture of the network.

Within the database description packet for the backbone area, the ABR will include one router LSA header for the backbone area interface and summary LSA headers for any other areas with which the router is associated. If an associated area is designed to include one range of IP addresses, route aggregation will permit one summary LSA to describe the entire area. If multiple IP address ranges exist within an area, separate summary LSAs are required for each range of addresses. If an area is designed with many addresses that are not sequential, a summary LSA will be required for every IP subnet. Therefore, the assignment of IP address ranges to an area will be necessary to minimize the bandwidth required by OSPF. The database description packet for the DR will include one router LSA header, one network LSA header for the backbone area, and any of the summary LSA headers for other interfaced areas.

An LSU packet will be sent in response to the received LSR and will contain the LSAs requested. The LSU packet will contain a 24 byte OSPF header and a four byte field describing the number of LSAs within the LSU. For the backbone area illustrated in Figure 1, a RLA will require 40 bytes. That is, 24 bytes for the LSA header and 16 bytes describing the routers

28.6-4 928

link to backbone area. If each area is supported by one range of IP addresses, only one summary LSA is required per area per border router. Every summary LSA requires 28 bytes. The DR network LSA will be 24 bytes plus four bytes for every router that is attached to the multi- access network. If AS boundary routers exist within an area, a 28 byte AS Boundary Routers (ASBR) advertisement is required. Additionally, a 36 byte AS external link advertisement for each external networks known by the ASBR is required.

Finally, each LSU packet is acknowledged with an LSU acknowledgment packet. This packet is very similar to the database description packet. The LSU acknowledgment packet consists of the OSPF 24 byte header and a 20 byte header of each LSA within the LSU. The LSR, LSU, and LSU acknowledgment packet exchanges complete the topology synchronization procedures within the OSPF. However, on broadcast networks LSU acknowledgments are not always necessary. For instance, if a router broadcasts an LSU to " AllDRouters" on a multi-access network, an acknowledgment can simply be the DRs forwarding of the LSU change to " AlISPFrouters."

Almost all of the events that generate an LSU packet transmission occur during network transients. The link state refresh timer is the only event that will force LSU transmissions during steady state network operations. According to RFC 1583, the link state refresh timer is considered to be an architectural parameter with a constant value of 30 minutes[l]. This value can not be changed by the network manager.

During initial network operations, it is difficult to characterize the amount of bandwidth required to synchronize router databases. Since routers will be turning on and establishing adjacencies with the DR at different times, the bandwidth required will vary. Also, many events can abort a database description exchange. For

instance, if two way hello connectivity is lost at any time during a database description exchange, the exchange is aborted and must start over. Also, reception of out of sequence database description packets will lead to a restart of the database exchange. Lower layer protocol collisions can also hinder the database description exchange [3]. Simulation is required to analyze the different possible effects on the network during these critical periods.

4 . 0 OSPF ARCHITECTURE CONSTRAINTS

OSPF requires strict adherence to a hierarchical network architecture when multiple areas are being used. This requirement can limit its ability to find the shortest path between two points on the network when they are part of separate areas. For instance, two directly connected areas cannot send traffic to one another without traversing the OSPF backbone network. To overcome this problem, the two areas must be combined into one area. An illustration of this potential routing problem is provided in Figure 4. To avoid this problem, the entire network could be configured as one backbone area. In this case, the penalty is that more intra- area LSAs occur, and OSPFs route aggregation capabilities are not used.

OSPF route aggregation capabilities allow routing overhead to be reduced, if the IP addressing plan and topology are constructed, so that routes to multiple, specific addresses within an area can be correctly summarized with routes to partial address matches at area boundaries and AS boundaries. If this can not be achieved, LSU OSPF routing overhead can increase very quickly. Also, if OSPF areas are very large, routing table update delays can lead to improper packet routing and possibly transient loops and network congestion [3]. Generally, it is always desirable to eliminate routing oscillations due to links that constantly switch between a connected and disconnected state. The value of the hello interval will impact how OSPF minimizes this probability of link oscillation. Also, a larger

929 28.6-5

Area Zero B Area One Area Two Connectivity - Routing Path

Figure 4. OSPF Inter-area Routing Path Selection Requirements

hello interval leads to an increased wait state for selection of a DR on multi-access networks due to the increased value of the dead interval. This increases network convergence times. For tactical networks it may be desirable to create a new timer that can separate the initial DR selection time from the value of the dead interval.

Also, tactical network routing overhead could be reduced if the OSPF hello intervals could be different for different routers operating across a multi-access network. Within the tactical environment, not all access points are as critical as others and bandwidth is very limited. Although this change would increase the complexity of an OSPF implementation, the reduction of bandwidth utilization gained could be significant enough to warrant the change. Additional analysis is required to determine the percentage of bandwidth reduction.

5.0 CONCLUSION

A description of the OSPF V2 protocol has been provided. Two protocol changes have been suggested. These changes could lead to a reduction of OSPF overhead and quicker multi- access network DR selection. OSPF V2 allows routing overhead to be reduced if the IP addressing plan and topology are constructed so that routes to multiple, specific addresses within an area can be correctly summarized. Reduced routing bandwidth can also be accomplished by minimizing the number of routes that have to be

advertised through the network. This can be done by: 1) reducing the number of routing destinations that have to be described by employing aggregation or summarization, and 2) reducing the number of possible routes to be considered by imposing hierarchy. This is a complex network design task and forces the network designer to concurrently think about the network topology, routing and their relationships.

LIST OF REFERENCES

1.

2 .

3.

3.

4.

5.

6 .

Moy, J., OSPF Version 2, Request For Comments 1583, Internet Engineering Task Force, March 1994

Perlman, R., "A Comparison Between Two Routing Protocols: OSPF and IS- IS," IEEE Network Magazine, Vol. 5, No. 5, September 1991, pp. 18-24

Huitema, C., Routing in the Internet, Prentice Hall, Englewood Cliffs, NJ, 1995

Luna, Garcia and Zaumen, Protocols Analysis and Standard Protocol Suite Selection f o r DISN, SRI International, 22 January 1993

Perlman, R., Interconnections:Routers and Bridges, Addison-Wesley, Reading, Massachusetts, 1992

Baker, F., "OSPF Fundamentals," LAN Magazine, Vol. 9, No. 13, December 1994, pp. 71-78

Coltun, R., "An Internet Routing Protocol," The MITRE Washington Networking Center Newsletter, Vol. 4, No. 1, Winter 1990, pp. 5-12, Limited Distribution

28.6-6 930