short computer networks review in 6 hours

Convergence time analysis of open shortest path first routing protocol in internet scale networks

S.U. Malik, S.K. Srinivasan and S.U. Khan

Proposed is a novel method to compute the intra-area convergence time of open shortest path first (OSPF) based networks in the presence of designated routers (DRs) on Ethernet and non-broadcast multi-access segments. The capacity of the proposed method is demonstrated by evaluating the convergence time performance of OSFP on internet scale networks (having a thousand autonomous system level routers). The method has also been used to analyse the effects of: (a) the number of DRs, (b) cascading failures, and (c) topological changes on the convergence time of the routers within an area. Furthermore, the time the network takes from a cold state to reach a stable (steady) state in an area is also analysed.

Introduction: Open shortest path first (OSPF) is an adaptive routing protocol to distribute routing information within a single autonomous system (AS) [1]. OSPF divides the network into areas. Each area consists of one or more segments. A segment constitutes the set of routers con- nected via a common communication channel (example Ethernet). When a failure occurs, topologies are regenerated and paths are recalcu- lated by all of the routers within that area [2]. The time a router takes to discover the area topology is known as the convergence time [1]. To improve the convergence time of a segment in an area, a router is selected as a designated router (DR) on each segment.

Fast convergence time is required to meet network based application demands and quality of service (QoS) requirements of modern dynamic large-scale routing domains, such as data centres. Therefore, a lot of effort and studies have been made to improve the performance of OSPF [3]. However, the convergence time analysis of OSPF that incor- porates DRs has never been studied. We address the aforementioned, by developing a novel method to compute the intra-area convergence time of OSPF-based networks that incorporates DRs, which is the primary contribution of this Letter. Moreover, to analyse and benchmark the pro- tocol on internet scale networks is another contribution of this work. We also show how to use our method to study the effect of: (a) DRs, (b) cas- cading failures, and (c) topological changes on the convergence time of the routers within an area.

For our experiments, we simulated the detailed implementation of the OSPF protocol based on the specifications reported in [2]. To get realis- tic measurements we generate topologies from BRITE [4], using Otter [4] (as shown in Fig. 1.) that represents the exact same characteristics as those of the internet. The results and analysis provided in this Letter will be extremely useful for network administrators seeking to deploy OSPF. Moreover, the results are also useful in the behavioural analysis of OSPF and can provide the basis to re-evaluate the design of the protocol to achieve performance optimisation.

Fig. 1 Sample topology for one thousand routers

Problem formulation: Consider a network composed of N routers. Let Ri be the ith router, where 1 ≤ i ≤ N . A link between two routers Ri and Rj (if it exists) has a communication cost that represents the minimum time for transferring a message from Ri to Rj , which can be represented by the following expression [5]:

del(Ri, Rj) = D(Ri, Rj)

n +

s

bij (1)

where D(Ri, Rj) is the physical distance between Ri and Rj , n is the propagation delay of the medium (optical fibre in our case), s is the size of the message in kilobytes, and bij is the available bandwidth between Ri and Rj . If the routers are not directly connected, then the communication cost is the sum of the cost of all links in the shortest path from Ri to Rj . Without loss of generality, we assume that

ELECTRONICS LETTERS 13th September 2012 V

del(Ri, Rj) = del(Rj, Ri), which is a common assumption in the literature [5]. Let M be the number of segments within an area and Sk be the kth segment in that area, where 1 ≤ k ≤ M . Let DS be the set of DRs within an area and 6k is the convergence time of Sk . If a failure occurs (could be a link or a router), the routers connected to the failed link or failed router will initiate the updates. Let Rko be a router that initiates an update in response to a failure. Let Rr be the set of all other routers in the area defined as Rr = (

⋃N i−1{Ri})\{{Rko} < DS}.

Rko will detect a failure if no response is received from a neighbouring router for a period longer than the dead interval (DI). Rko will then update its link state and forward the updated link state to the DR of segment k (represented as dk . The link state is the description of the interface of the router (IP address of the interface, mask, type of network, routers con- nected to) and the relationship to other routers. The DR will then flood the information to every other router in the segment after receiving the update. Let Rki represent a router that belongs to S

k . The time for Rki to receive the update (c(Rki )) can be calculated as follows:

c(Rki ) = DI, if Rki = Rko

c∀k[S:Ri [k(d k) + del(dk, Rki ), if Rki [ Rr

{ (2)

where

c(dk) = c∀j[k:k[S(R k j ) + del(R

k i , d

k) (3)

We assume that other updates, such as change in bandwidth (Dbij), are local and incur zero update time. Therefore in (2), the value of c(Rki ) for Rki = Rko, is DI. The DI of routers is usually four times the ‘Hello’ inter- val, which is the time between consecutive transmissions of ‘Hello’ packets that are used to indicate the liveliness of nodes. The ‘Hello’ interval is 10 seconds for broadcast and P2P networks, and 30 seconds for all other media [2]. The value of c(Rki ) for Rki [ Rr is the sum of the time required for dk to receive updates and the time dk

takes to deliver updates to Rki . The value of c(dk) is calculated in (3), which is the sum of c(Rkk) (the node sending the update to d

k ) and the communication cost between them, which is given as del(Rkj , d

k). Moreover, (2) and (3) are used to calculate 6k based on the following equation:

6k = max(c(dk) + del∀j[k(dk, Rkj )) (4)

The last router (maximum time taken to receive an update from the cor- responding dk ) in Sk that receives the update, determines 6k . Now, using (2), (3) and (4) the convergence time of an area t can be calculated as follows:

t = max∀k[S((6k )) + c((Rko) + del(R k o, d

k) (5)

The maximum 6k amongst all of the segments plus the time when the update is initiated and reaches to the respective DR determines the value of t.

Results and discussion: The value of t determines the time an area requires to reach a stable (steady) state from an unstable state, which is caused by an update. Therefore, to avoid message losses the network must converge quickly. To this end, we evaluate the effect of: (a) the number of DRs, (b) cascading failures, and (c) topology on the value of t.

We assume optical fibre as the communication medium having propa- gation delay v = 300 × 106 miles/s. Ethernet channels have a maximum transmit unit (MTU) of 1500 bytes [1]. Also, fragmentation is usually avoided in OSPF [1]. Therefore, we assume the message size s to be 1 KB (lower than the 1500B cap, but not too low and is typically used in the literature for experimentation, such as in [6]). The bandwidth value bij is kept constant at 100 Mbit/s, as advocated in [7] for evalu- ation purposes. The values of D(Ri, Rj) are assigned from within the range of [1 – 100] km.

Fig. 2 depicts the effect of the number of DRs on the value of t. To analyse the effect on large and average scale networks, we used N ¼ {1000, 300}. A DR can decrease the segment convergence time from O(n 2) to O(n) [1]. However, including more DRs in an area has no effect or in some cases may even increase the value of t. As reported in Fig. 2, the mean value of t increases gradually as the number of DRs increases in the topology. To see why, consider a router R under DR1. If DR2 is added to the area and R now falls under DR2, then DR1 can no longer directly communicate with R, but instead it is obliga- tory to communicate via DR2. From this example we can see that

ol. 48 No. 19

including a DR can increase the length of communication paths in the area, thereby possibly increasing its convergence time. Therefore, the placement of DR is crucial towards the value of t.

0 10 20 30 40

1 10 20 30 40 50 60 70 80 90 100 DR

m e

a n

( t)

, m

s mean (t) for

mean (t) for N = 1000

N = 300

Fig. 2 Effect of DRs on t

Fig. 3 depicts the effect of cascading failures of routers (also called nodes) and links on t. The number of DRs in an area is set to one (to avoid the influence of multiple DRs on t). When a node fails, nearby nodes absorb the load of the failed node. The failed nodes can in turn cause their neighbours to fail (due to overloading) resulting in cascading failures, also known as terminal failure in (communication and power) networks. The degree and placement of a failed node determines its effect on the value of t. If a failed node or link is in the shortest path of other nodes, then t may increase. This is because updates to such routers may require a longer path. However, if a failed node or link is: (a) a leaf node, a node with low degree, or link on the edge of the top- ology, or (b) not included in the shortest path, then t can decrease as the failed node need not be updated. Moreover, as can be seen from Fig. 3, node failures can affect t more adversely than link failures. Link failures directly affect only the two routers they are connected to, but node fail- ures affect all its neighbours which is typically more than two.

0.40 0.45 0.50 0.55 0.60

0 5 15 25 35 50 number of failures

m e a n (

t) , m

s link failure node failure N = 300 DR = 1

Fig. 3 Effect of node and link failure on t

Fig. 4 illustrates the variation of t due to the changes in the topology, and shows that the value of t increases as the number of routers within an area increases. However, an interesting observation is that the value of t may decrease in certain cases when a router that is included in a top- ology changes the value of max(6k) by adding a new shortest path. To avoid the influence of multiple DRs in an area on t, the number of DRs is set to one in Fig. 4.

ELECTRONICS

0.3

0.5

0.7

0.9

100 200 300 400 500 600 700 800 900 1000 N

m e

a n

( r)

, m

s

mean (r) DR = 1

Fig. 4 Effect of random topological changes on t

Conclusion: We have developed a method to compute the intra-area convergence time for OSPF-based networks that incorporates DRs. The results reveal that the factors, such as: (a) the number of DRs, (b) the placement of DRs, (c) interconnection amongst the routers, and (d) the number of routers, in a topology impact the convergence time. Our convergence time analysis technique can therefore be used to evalu- ate and compare OSPF network design solutions.

# The Institution of Engineering and Technology 2012 5 July 2012 doi: 10.1049/el.2012.2310 One or more of the Figures in this Letter are available in colour online.

S.U. Malik, S.K. Srinivasan and S.U. Khan (North Dakota State University, ND 58108, USA)

E-mail: [email protected]

References

1 Moy, J.T.: ‘OSPF; Anatomy of an Internet routing protocol’ (Addison- Wesley, 1998)

2 Moy, J.: ‘OSPF Version 2, The Internet Society OSPFv2’, http://www. ietf.org/rfc/rfc2328.txt, accessed on 08 May, 2012

3 Goyal, M., Soperi, M., Baccelli, E., Choudhury, G., Shaikh, A., and Hosseini, H.: ‘Improving convergence speed and scalability in OSPF: a survey’, IEEE ComST, 2012, 14, (2), pp. 443 – 463

4 Medina, A., Lakhina, A., Matta, I., and Byers, J.: ‘BRITE: An Approach to Universal Topology Generation’. MASCOTS, Ohio, 2001

5 Khan, S.U., and Ahmad, I.: ‘A pure Nash equilibrium based game theoretical method for data replication across multiple servers’, IEEE Trans. Knowl. Data Eng., 2009, 21, (4), pp. 537 – 553

6 Wang, B., Zhang, J., Guo, Y., and Chen, W.: ‘Fast-converging distance vector routing mechanism for IP networks’, J. Netw., 2010, 05, (9), pp. 1069 – 1075

7 Prasad, R.S., Murray, M., Dovrolis, C., and Claffy, K.: ‘Bandwidth estimation: metrics, measurement techniques, and tools’, IEEE Netw., 2003, 17, (6), pp. 27 – 35

LETTERS 13th September 2012 Vol. 48 No. 19