Effect of Varying Hellolnterval and RouterDeadInterval on convergence time of OSPF

Introduction :
Routing protocols used in the internet today exchange various control packets to discriminate routing information and to determine the liveliness of peering sessions established between pairs of routers. These control packets usually share resources such as bandwidth and buffer space with data traffic and therefore subject to loss. Congestion in the network can hinder the propagation of routing information or peering refresh requests if routing protocol message are not isolated from data traffic. OSPF protocol is a link state routing protocol. It maintains a database called link state database which describes the routing topology the way in which all the routers in the network are connected. Each OSPF router originates one or more LSAs (Link State Advertisement) to describe its local part of the routing domain. These LSAs are then distributed to every other router in the domain and as such the collection of all the LSAs taken together forms the link state database. Each OSPF router has an identical link-state database. Link-state databases are exchanged between neighboring routers soon after the routers have discovered each other. In a network using OSPF protocol for routing, the routers discover their neighbors using Hello packets. A router sends Hellos out of every interface at an interval configurable as the OSPF parameter Hellolnterval which defaults to 10s. If a Hello packet is received back, it specifies that the neighbor exists. This knowledge is used to create the Link State Database which is same at each router of the OSPF network. If there is a failure in receiving the hello packet over a specified interval configurable as RouterDeadInterval parameter, whose default value is 40s, it implies the link between the two routers is corrupted. The transmission and reception of Hello packets also enables a router to detect the failure of one of its neighbors; if enough time elapses (specified as the OSPF configurable parameter RouterDeadlnterval) without the router's receiving a Hello from a neighbor, the router stops advertising the connection to the router and starts routing data packets around the failure. During network failure, the time to detect neighbor failure dominates convergence time, since the rest of the OSPF protocol machinery (flooding updated LSAs and redoing the routing table calculations) required to route packets around the failure takes at most a few seconds. The Hello protocol ensures that the link between neighbors is bidirectional. Unless the link is

bidirectional, OSPF routers will not forward data packets over the link. This procedure prevents a routing failure that can be caused by unidirectional links in other protocols. The Hello protocol ensures that the neighboring routers agree on the Hellolnterval and RouterDeadlnterval parameters. This ensures that each router sends Hellos quickly enough so that losing an occasional Hello packet will not mistakenly bring the link down. Objective: Hence, the objective is to find the optimal value of Hellolnterval that will lead to fast failure detection in network while keeping the occurrence of false alarm within acceptable limits. We will study the effect of changing HelloInterval and RouterDeadInterval on convergence time of OSPF. OSPF has advantages like enhanced network security, better routing effectiveness and efficiency and increased routing flexibility over Distance-vector protocols which makes OSPF attractive for use on both small as well as large internets. Network instability can greatly impair service quality and reduce productivity. The ultimate goal in designing an enterprise network is to reduce down time and lost packets during the transition caused by defective equipment or congested links. Convergence time depends on how quickly the routing protocol can learn the new topology and recalculate the routing tables throughout entire network. Depending on the size of the network, convergence times could range from tens of seconds to minutes. So this study will help us get to an optimal value of HelloInterval and RouterDeadInterval that will lead to faster convergence time which is one of the key challenges of OSPF. Related Works: 1. Towards milliseconds 1GP convergence It proposed reducing the HelloInterval to milliseconds range to achieve recovery from network failures. But side effects were not considered due to this reduction in HelloInterval. There is a limit up to which it can be reduced safely. Since as it decreases, there is an increased chance that the network congestion will lead to loss of several consecutive Hello messages and thereby cause false breakdown of adjacency between routers even though the routers and the link between them are functioning perfectly well.

2. Sheikh-et all This paper described the study of the effects of traffic overload on the routing protocols like OSPF and BGP, when routing traffic is not isolated from data traffic. OSPFs behavior depends only on traffic overload and is insensitive to packet size. 3. Stability issues in OSPF routing by A. Basu and J.G. Riecke This paper describes that using sub second hello timers considerably improves the convergence for OSPF without significantly adding to processor loads.

Problem Description: Our work is a trade-off between faster failure detection and increased frequency of false alarm. We will consider a Star and a Mesh topology for the connection of the routers. Basically with the change of configuration the optimal hello interval time changes. All routers will follow OSPF configuration. OSPF configuration will allow us to change the HelloInterval and RouterDeadInterval time. By varying these two parameters we will study Failure detection time (FDT) and Failure recovery time (FRT). The simulation platform being used is OPNET.

Introduction to Routing:
The Internet consists of a huge number of computers connected together all over the world. It is an international network that enables its attached computers to exchange information. This information is encoded as long strings of bits called packets. The process of finding a path between source and destination and then sending data along the selected path is called routing. As these packets travel through the Internet on their way to their destination computers, routing decisions are made: Should the packet be sent this way or that way? The devices making these decisions are themselves computers, called routers. The distributed algorithms that the routers run among them in order to make the correct routing decisions are called routing protocols. The effectiveness of internetwork communications for a large part depends on the ability of the routers to forward packets in the most efficient way possible. The routers primary responsibility is to forward packets destined for local and remote networks by Determining the best path to send packets Forwarding packets towards their destination Routers build routing tables for forwarding packets. The information in the routing table specifies the next-hop router address for reaching the destination for a particular network address. The content of the routing table and the way it is presented varies for different protocols. A router maintains a separate routing table for different routed and routing protocols the routing table for IP is different from that of Internet packet exchange (IPX). The routing table will include the interface to be used to forward the packet. When a match is found, the router encapsulates the IP packet into the datalink frame of the outgoing interface, and the packet is then forwarded toward its destination. Routings can be either static or dynamic. Static routes are user-defined routes, configured to route a packet to a specific network destination by directing the packet to the interface of a router. Static routes are manually configured and this is reflected in routing table and takes precedence over routes chosen by dynamic routing protocols. Periodic routing updates are not present in static routing. As a result, neighboring routers dont exchange routing information and have no way to communicate any changes in the network topology. Static routing has advantages like

complete control of the network since the path to be followed for reaching destination is manually configured. The disadvantage is that maintaining networks manually can be tedious and prone to human error. Manual updating of table is required every time there is a change in the network topology which can be cumbersome in case of large network or a network where requirements change frequently. Dynamic routing protocols use an algorithm to enable routers to discover routes automatically to different destinations and to share the information with other routers. Dynamic routing protocols determine the best and the next-best paths to any destination networks. The most important feature of dynamic routing protocols is the ability to react to topological changes. Dynamic routing protocols can: Send and receive information about different networks Determine the optimal path to reach a destination React automatically to topological changes Ensure load balances when more than one path exists between the source and destination.

Routing protocol and routed protocol A routing protocol sends and receives routing information packets to and from other routers. A routed protocol can be routed by a router, which means that it can be forwarded from one router to another. A routed protocol contains the data elements required for a packet to be sent outside of its host network or network segment. In other words, a routed protocol can be routed. Routing protocols have their own set of algorithms that describe the method in which the routers will exchange routing updates with each other about the available networks. Routing protocols are also called as network protocols. A routing protocol supports many routed protocols and is used to send routing updates to routers in order to find the best path for transporting data. It supports routing protocol by providing a mechanism for sharing routing information between routers. Exchange of routes is required to update and maintain routing tables. E.g. RIP, OSPF etc. Routed protocols deal with the user applications. They are nothing more than data being transported across the networks. E.g. Internet protocol (IP), IPX etc. Interior Gateway Protocols:

IGP is used to find the route within an autonomous system (AS), which is a collection of routers and hosts controlled by a single administrative entity. They are categorized as Distance vector protocols and Link state protocols.
Distance vector protocols

Each router determines a routing table using routing information from neighboring nodes. The routers send all routing updates to directly connected neighbors at periodic intervals.
Link state protocols

The link state protocol is a protocol whereby each route broadcasts or multicast routing information about all its neighbors to all nodes in the internetwork. This makes is possible for each router to have the same image of the network.

Overview of OSPF
OSPF belongs to the general category of routing protocols called link-state protocols. OSPF is an Interior Gateway Protocol, which means that it is used by all the routers inside the same Autonomous System in order to route packets inside the AS.OSPF is based on Djikstras Shortest path algorithm. OSPF routers gather link state information and use the shortest path algorithm for calculating the optimal path for routing data packets. OSPF is used in large heterogeneous internetworks. The process of routing updates become more tedious and causes degradation of performance as the network grows. The routing protocol divides the network into smaller segments to overcome this problem. OSPF supports multi- paths, where shortest routes can be recalculated faster for an area, resulting in the use of minimum network routing traffic. The OSPF routing protocol keeps track of three tables the routing table, a table to track directly attached neighbors and a table to track topology and design of the whole internetwork called the link-state database. OSPF enables each router in the AS to calculate and update routing information. Each router in the routing domain is responsible for describing its local piece of the routing topology in link-state advertisements, or LSAs. These LSAs are then reliably distributed to all the other routers in the routing domain (reliable flooding) and the collection of LSAs generated by all of the routers form the link-state database.

OSPF Network Structure

OSPF routing domains are broken up into areas. The SPF runs within an area and interarea routes are passed between areas. Dividing an OSPF network into areas minimize the number of routing table entries, contains LSA flooding to a reasonable area and minimizes the impact of a topology change. A two level hierarchy of OSPF areas exists; area 0 or backbone area is designed as transit area and other areas should be attached to and only to area 0. The LSDB is identical for each router in an area. An Area Border Router has interfaces in two or more area and maintains a link-state database for which area to which they are connected.

OSPF operation
OSPF uses several messages to establish and maintain its neighbor relationships and to maintain correct routing information. OSPF Packet Types There are five different types of OSPF link-state packets (LSP). Each packet serves a specific purpose in the OSPF routing process. 1. Hello: Used to establish and maintain adjacency with other OSPF routers 2. Database description (DBD): The database description (DBD) packet keeps the list of the sending routers link state database abbreviated and is used by receiving routers to verify against the local link state database. 3. Link-state request (LSR): Having exchanged database description packets with neighboring routers, receiving routers can then request to know more information about any entry in the DBD by sending link state request (LSR). 4. Link-state update (LSU): Link state update is used to flood the link state advertisement to LSR. Seven different types of LSA are used in LSU. 5. Link-state acknowledgment (LSAck): Confirms receipt of an LSU Neighbor Discovery and Maintenance In OSPF, a router discovers neighbors by periodically sending OSPF Hello packets out all of its interfaces. By default, a router sends Helios out an interface every 10 seconds, although this interval is configurable as the OSPF parameter Hellolnterval. A

router learns the existence of a neighboring router when it receives the neighbor's OSPF Hello in turn. The part of the OSPF protocol responsible for sending and receiving Hello packets is called OSPF's Hello protocol. The transmission and reception of Hello packets also enables a router to detect the failure of one of its neighbors; if enough time elapses (specified as the OSPF configurable parameter RouterDeadlnterval, whose default value is 40 seconds) without the router's receiving a Hello from a neighbor, the router stops advertising the connection to the router and starts routing data packets around the failure.
Database Synchronization

As soon as the Hello protocol has determined that the connection between neighbors is bidirectional, the OSPF protocol decides whether databases need to be synchronized. If a decision to synchronize is made, each neighbor does two things: sends the linkstate headers of all the LSAs currently in its database to the other in a sequence of OSPF Database Description packets and starts flooding any future LSA updates over the connection. Commencing the flooding procedure is necessary to ensure that Database Exchange finishes in a deterministic time period. When an entire sequence of Database Description packets has been received, a router knows the link-state headers of all the LSAs in its neighbor's link-state database. In particular, the router knows which of the neighbor's LSAs it does not have and which of the neighbor's LSAs are more recent. The router then sends Link State Request packets to the neighbor requesting the desired LSAs, and the neighbor responds by flooding the LSAs in Link State Update packets. After having sent a full sequence of Database Description packets to the neighbor, having received a full sequence of Database Description Packets from the neighbor, and having had all of its Link State Request packets satisfied by Link State Updates received from the neighbor, the router declares the connection synchronized and advertises it as ready to be used for data traffic.