# Research on Routing Algorithm Based on Limitation Arrangement Principle in Mathematics

Authors: Jianhui Lv; Xingwei Wang; Min Huang
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

Since the research on information consistency of the whole network under OSPF protocol has been insufficient in recent years, an algorithm based on limitation arrangement principle for routing decision is proposed and it is a permutation and combination problem in mathematical area. The most fundamental function of this algorithm is to accomplish the information consistency of the whole network at a relatively fast speed. Firstly, limitation arrangement principle algorithm is proposed and proved. Secondly, LAP routing algorithm in single link network and LAP routing algorithm in single link network with multiloops are designed. Finally, simulation experiments are worked by VC6.0 and NS2, which proves that LAPSN algorithm and LAPSNM algorithm can solve the problem of information consistency of the whole network under OSPF protocol and LAPSNM algorithm is superior to Dijkstra algorithm.


---

## Body

## 1. Introduction

With the rapid development of social economic, the computer network develops rapidly. The relationship between the current Internet and our life is more and more close. Meanwhile, network resource and the amount of information are consistently increasing, which leads to the emergence of many problems including the following: the computer network loads onerously, the switch speed of information slows down, and the communication quality becomes poor [1]. Therefore, it should not be ignored to design an efficient, stable, and flexible routing algorithm to solve the problems. In recent years, the routing algorithm has been a hotspot, and research on routing algorithm mainly includes three different directions as follows: (1) a new network environment is proposed, and a routing algorithm is studied under it, for example, Ad Hoc, NoC, WSN, IoT, and DNT [2–6]; (2) a hybrid routing algorithm is designed based on two or more mature algorithms, which is usually heuristic or intelligent (e.g., artificial intelligence and biological intelligence); (3) the traditional research mode is converted and a new routing algorithm is designed, which is the theoretical innovation [7–11].Routing algorithm is a special computation method, and its purpose is to realize routing function. The traditional routing algorithms include static/dynamic, host intelligently/routing intelligently, domain/outside, and link state/distance vector [12–15]. In short, routing algorithm should be fast in convergence speed, simple and easily understood, stable, strong, and flexible. In fact, it is of no significance to only do research on routing algorithm. The routing algorithm should be used to some routing protocols. The routing protocol can collect data of network in current state, for this reason, and then find the optimal path [16]. RIP and OSPF [17, 18] are two typical internal gateway protocols. RIP protocol fails to cope with a large amount of nodes in network, so OSPF protocol has been a common protocol in recent years. OSPF protocol was proposed in 1989 and it aims at accomplishing the information consistency of the whole network as soon as possible [19]. In OSPF protocol, Dijkstra algorithm [20] is always used to accomplish the information consistency of the whole network under OSPF protocol and it is also approved by domestic and foreign experts and scholars.Information consistency is defined as follows: any one routing node can know the information of the other routing nodes. For example, there are 4 nodes in network; they are A, B, C, and D. If A owns the information “**”, B owns the information “@@”, C owns the information “##”, and D owns the information “$$”, then they all own “**”, “@@”, “##”, and “$$” after accomplishing the information consistency. Of course, it is very important to keep information consistency of the whole network. Three reasons are listed as follows. (1) OSPF protocol focuses on whether the link state is synchronous or not. The information of all routing nodes must keep consistency; namely, any routing node can know the network topology at any time. (2) In recent years, Internet technology has developed rapidly; plenty of science and technology information resources are stored in Internet. These resources can be browsed online and shared smoothly by keeping the information consistency of the whole network. (3) The other routing nodes can be regarded as the copies to exchange information with each other when one or more routing nodes go wrong. In this way, the integrity of the network information can be guaranteed. But, it is a pity that the research on information consistency of the whole network under OSPF protocol has been insufficient for 25 years and people only focus on how to detect the information consistency [21–23]. In terms of the study of information consistency, Dijkstra algorithm has been selected as the unique algorithm so far (i.e., no other algorithms). Generally, Dijkstra algorithm focuses on the cost of link, and plenty of time is spent to compare all cost of link when the shortest path is found. Does it have a kind of new method that can avoid the trouble to achieve the same purpose as Dijkstra algorithm? In this paper, we will study the information consistency of the whole network under OSPF protocol.Given the above consideration, LAP routing algorithms including LAPSN algorithm and LAPSNM algorithm are proposed to solve the problem of the information consistency of the whole network under OSPF protocol. The LAP routing algorithms are inspired by LAP algorithm that is a permutation and combination problem in mathematical area. Meanwhile, LAP algorithm is a new algorithm and it is proposed and proved based on another limitation arrangement problem. Three strategies are used to design LAP routing algorithms, including the depth traversal method, off nodes method, and added loops method. The static experiments on VC6.0 and the dynamic experiments on NS2 are performed for two designed LAP routing algorithms. The former results reveal that routing algorithm in this paper is feasible and effective. The latter results demonstrate that the routing algorithm can accomplish the information consistency of the whole network and LAPSNM algorithm is superior to Dijkstra algorithm and LAPSN algorithm.The paper is organized as follows. Section2 proposes the limitation arrangement principle algorithm and gives the optimal limitation arrangement. The limitation arrangement principle algorithm is applied to OSPF protocol and to solve the problem of information consistency, two routing algorithms including LAPSN algorithm and LAPSNM algorithm are designed in Section 3. Experimental results based on two routing algorithms are reported in Section 4. Finally, Section 5 concludes this paper.


## 2. Description of LAP Algorithm

To discuss this paper, the notations are introduced in Notations section.


### 2.1. LAP Algorithm

#### 2.1.1. Another Limitation Arrangement Problem

Limitation arrangement principle (LAP) is a permutation and combination problem in mathematical area, and it is a new mathematical problem inspired by another limitation arrangement (ALA) problem. ALA problem can be described in Definition1.Definition 1.
Given a positive integern and a set B={1,2,…,n}, n elements in set B are arranged; if 12,23,…,(n-1)n are not included in an arrangement, then the arrangement is an another limitation arrangement. Let Qn represent the number of ALA, and Qn is shown in Theorem 2.Theorem 2.
Considern≥1, and then
(1)Qn=n!-n-11n-1!+n-12n-2!-n-13(n-3)!+⋯+-1n-1n-1n-11!.


#### 2.1.2. LAP Problem

Definition 3.
Given a positive integern and a set B={1,2,…,n}, n elements in set B are arranged; if 12,23,…,(n-1)n and n(n-1),(n-1)(n-2),…,21 are not included in an arrangement, then the arrangement is a limitation arrangement (LA). Suppose 12,23,…,(n-1)n is named as model 1 and n(n-1),(n-1)(n-2),…,21 is named as model 2. Let N represent the number of LA, and N is shown in Theorem 4.Theorem 4.
Consider(2)N=n!-a1(n-1)!+a2(n-2)!-a3(n-3)!+⋯+-1n-1an-11!,n≥40,1≤n<4,
where ai is shown in
(3)ai=n-i1·21+n-i+11n-i-11·22+n-i+21n-i1n-i-21·23⋮+ni-n-i1+n-i+11n-i-11iiiiiiiiiiiiiiiiiii+n-i+21n-i1n-i-21iiiiiiiiiiiiiiiiiin-i1+⋯·2i.Proof.
(1) Consider1≤n≤4:(a)
n=1, the arrangement of set B is {1}, and 1 ∈ model 1 and 1∈ model 2;(b)
n=2, the arrangements of set B are {12} and {21}, and among them, 12 ∈ model 1 and 21 ∈ model 2;(c)
n=3, the arrangements of set B are {123}, {231}, {312}, {132}, {213}, and {321}, and among them, the front three arrangements belong to model 1, and the others belong to model 2.
Consequently, whenn=1, 2 or 3, all arrangements are not LAs. In short, N=0.
(2) Considern≥4. The style of N is similar to that of Qn by Theorem 2, so ai is just to be proved in Theorem 4. On this condition, the method of abstract generalizations is adopted to prove ai. Let n=10; then a1, a2, and a3 can be got as follows:
(4)a1=10-11·21+102-10-11·22,a2=10-21·21+10-1110-31·22+103-10-21iii+10-1110-31·23,a3=10-31·21+10-2110-41·22+10-1110-3110-51·23+104-10-31iiiiiiiiiiiiiiiiii+10-2110-41iiiiiiiiiiiiiiiii+10-1110-31iiiiiiiiiiiiiiiii×10-3110-51·24.
To compare and analyzea1, a2, and a3, when n=10, we generalize ai. Consider
(5)ai=10-i1·21+10-i+1110-i-11·22+10-i+2110-i110-i-21·23⋮+10i-10-i1iiiiiiiiiiiiiiiiii+10-i+1110-i-11iiiiiiiiiiiiiiiiiii+10-i+2110-i1iiiiiiiiiiiiiiiiiii×10-i-21+⋯·2i.
The trend is extended to arbitraryn; the formula (3) can be got.
To sum up (1) and (2), Theorem4 is proved.


### 2.2. Optimal LA Algorithm

InN LAs, there must be a LA that is the optimal limitation arrangement (OLA). OLA can be described in Definition 5.Definition 5.
Supposen≥4, given two LA events: X and Y. The corresponding LAs are {x1,x2,…,xn} and {y1,y2,…,yn}. The corresponding mathematical expectations are E(X) and E(Y), and we have the following formula:
(6)EX=∑k=1nxk-k,EY=∑k=1nyk-k.IfE(X)≠E(Y), then the event of the lesser mathematical expectation is OLA; otherwise, X or Y can be regarded as OLA.According to Definition5, we give Theorem 6.Theorem 6.
Considern≥4, and then
(7)OLA:=1,3,…,2i-1,…,n,2,4,…,2i,…,n-1;iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiin≥5,n%2=11,3,…,2i-1,…,n-1,2,4,…,2i,…,n;iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiin≥5,n%2=02,4,1,3or3,1,4,2;iiiiiiiiiiiiiiiiiiiiiiiin=4.Proof.
(1) Considern=4, there are two LAs, they are {2,4,1,3} and {3,1,4,2}, and their mathematical expectations are 6, so they can be regarded as OLA.
(2) Considern%2=0, suppose LA is {k1,k2,…,kn/2,…,kn}, and it is denoted by event K. E(K) can be shown in
(8)EK=k1-1+k2-2+⋯+kn/2-n2+kn/2+1-n2-1+⋯+kn-n.
We have two constraint conditions as follows:(9)1≤ki≤n,i=1,2,…,n,2≤kj+1-kj≤n-1,j=1,2,…,n-1,(10)kn/2+1-n2-1,…,kn-1-n+1,kn-n=k1-1,k2-1,…,kn/2-n2.
Formula (10) is substituted into formula (8); we have the following two formulas:
(11)EK=2k1-1+k2-2+⋯+kn/2-n2,(12)EK=2kn-n+kn-1-n+1(kn/2+1-n2-1)iiiiiiii+⋯+kn/2+1-n2-1.(a)
For formula (11), if k1-1 is minimum, then k1=1. Formula (9) is taken into account, k2≠2, and then k2=3. In a similar way, k1,k2,…,kn/2 is 1,3,…,n-1.(b)
For formula (12), if kn-n is minimum, then kn=n. Similarly, formula (9) is taken into account; kn,kn-1,…,kn/2+1 is n,n-2,…,2.
In short, whenn%2=0, OLA is {1,3,…,2i-1,…,n-1,2,4,…,2i,…,n}.
(3) Considern%2=1. Its proof method is similar to that of n%2=0.
To sum up (1), (2), and (3), Theorem6 is proved.


## 2.1. LAP Algorithm

### 2.1.1. Another Limitation Arrangement Problem

Limitation arrangement principle (LAP) is a permutation and combination problem in mathematical area, and it is a new mathematical problem inspired by another limitation arrangement (ALA) problem. ALA problem can be described in Definition1.Definition 1.
Given a positive integern and a set B={1,2,…,n}, n elements in set B are arranged; if 12,23,…,(n-1)n are not included in an arrangement, then the arrangement is an another limitation arrangement. Let Qn represent the number of ALA, and Qn is shown in Theorem 2.Theorem 2.
Considern≥1, and then
(1)Qn=n!-n-11n-1!+n-12n-2!-n-13(n-3)!+⋯+-1n-1n-1n-11!.


### 2.1.2. LAP Problem

Definition 3.
Given a positive integern and a set B={1,2,…,n}, n elements in set B are arranged; if 12,23,…,(n-1)n and n(n-1),(n-1)(n-2),…,21 are not included in an arrangement, then the arrangement is a limitation arrangement (LA). Suppose 12,23,…,(n-1)n is named as model 1 and n(n-1),(n-1)(n-2),…,21 is named as model 2. Let N represent the number of LA, and N is shown in Theorem 4.Theorem 4.
Consider(2)N=n!-a1(n-1)!+a2(n-2)!-a3(n-3)!+⋯+-1n-1an-11!,n≥40,1≤n<4,
where ai is shown in
(3)ai=n-i1·21+n-i+11n-i-11·22+n-i+21n-i1n-i-21·23⋮+ni-n-i1+n-i+11n-i-11iiiiiiiiiiiiiiiiiii+n-i+21n-i1n-i-21iiiiiiiiiiiiiiiiiin-i1+⋯·2i.Proof.
(1) Consider1≤n≤4:(a)
n=1, the arrangement of set B is {1}, and 1 ∈ model 1 and 1∈ model 2;(b)
n=2, the arrangements of set B are {12} and {21}, and among them, 12 ∈ model 1 and 21 ∈ model 2;(c)
n=3, the arrangements of set B are {123}, {231}, {312}, {132}, {213}, and {321}, and among them, the front three arrangements belong to model 1, and the others belong to model 2.
Consequently, whenn=1, 2 or 3, all arrangements are not LAs. In short, N=0.
(2) Considern≥4. The style of N is similar to that of Qn by Theorem 2, so ai is just to be proved in Theorem 4. On this condition, the method of abstract generalizations is adopted to prove ai. Let n=10; then a1, a2, and a3 can be got as follows:
(4)a1=10-11·21+102-10-11·22,a2=10-21·21+10-1110-31·22+103-10-21iii+10-1110-31·23,a3=10-31·21+10-2110-41·22+10-1110-3110-51·23+104-10-31iiiiiiiiiiiiiiiiii+10-2110-41iiiiiiiiiiiiiiiii+10-1110-31iiiiiiiiiiiiiiiii×10-3110-51·24.
To compare and analyzea1, a2, and a3, when n=10, we generalize ai. Consider
(5)ai=10-i1·21+10-i+1110-i-11·22+10-i+2110-i110-i-21·23⋮+10i-10-i1iiiiiiiiiiiiiiiiii+10-i+1110-i-11iiiiiiiiiiiiiiiiiii+10-i+2110-i1iiiiiiiiiiiiiiiiiii×10-i-21+⋯·2i.
The trend is extended to arbitraryn; the formula (3) can be got.
To sum up (1) and (2), Theorem4 is proved.


## 2.1.1. Another Limitation Arrangement Problem

Limitation arrangement principle (LAP) is a permutation and combination problem in mathematical area, and it is a new mathematical problem inspired by another limitation arrangement (ALA) problem. ALA problem can be described in Definition1.Definition 1.
Given a positive integern and a set B={1,2,…,n}, n elements in set B are arranged; if 12,23,…,(n-1)n are not included in an arrangement, then the arrangement is an another limitation arrangement. Let Qn represent the number of ALA, and Qn is shown in Theorem 2.Theorem 2.
Considern≥1, and then
(1)Qn=n!-n-11n-1!+n-12n-2!-n-13(n-3)!+⋯+-1n-1n-1n-11!.


## 2.1.2. LAP Problem

Definition 3.
Given a positive integern and a set B={1,2,…,n}, n elements in set B are arranged; if 12,23,…,(n-1)n and n(n-1),(n-1)(n-2),…,21 are not included in an arrangement, then the arrangement is a limitation arrangement (LA). Suppose 12,23,…,(n-1)n is named as model 1 and n(n-1),(n-1)(n-2),…,21 is named as model 2. Let N represent the number of LA, and N is shown in Theorem 4.Theorem 4.
Consider(2)N=n!-a1(n-1)!+a2(n-2)!-a3(n-3)!+⋯+-1n-1an-11!,n≥40,1≤n<4,
where ai is shown in
(3)ai=n-i1·21+n-i+11n-i-11·22+n-i+21n-i1n-i-21·23⋮+ni-n-i1+n-i+11n-i-11iiiiiiiiiiiiiiiiiii+n-i+21n-i1n-i-21iiiiiiiiiiiiiiiiiin-i1+⋯·2i.Proof.
(1) Consider1≤n≤4:(a)
n=1, the arrangement of set B is {1}, and 1 ∈ model 1 and 1∈ model 2;(b)
n=2, the arrangements of set B are {12} and {21}, and among them, 12 ∈ model 1 and 21 ∈ model 2;(c)
n=3, the arrangements of set B are {123}, {231}, {312}, {132}, {213}, and {321}, and among them, the front three arrangements belong to model 1, and the others belong to model 2.
Consequently, whenn=1, 2 or 3, all arrangements are not LAs. In short, N=0.
(2) Considern≥4. The style of N is similar to that of Qn by Theorem 2, so ai is just to be proved in Theorem 4. On this condition, the method of abstract generalizations is adopted to prove ai. Let n=10; then a1, a2, and a3 can be got as follows:
(4)a1=10-11·21+102-10-11·22,a2=10-21·21+10-1110-31·22+103-10-21iii+10-1110-31·23,a3=10-31·21+10-2110-41·22+10-1110-3110-51·23+104-10-31iiiiiiiiiiiiiiiiii+10-2110-41iiiiiiiiiiiiiiiii+10-1110-31iiiiiiiiiiiiiiiii×10-3110-51·24.
To compare and analyzea1, a2, and a3, when n=10, we generalize ai. Consider
(5)ai=10-i1·21+10-i+1110-i-11·22+10-i+2110-i110-i-21·23⋮+10i-10-i1iiiiiiiiiiiiiiiiii+10-i+1110-i-11iiiiiiiiiiiiiiiiiii+10-i+2110-i1iiiiiiiiiiiiiiiiiii×10-i-21+⋯·2i.
The trend is extended to arbitraryn; the formula (3) can be got.
To sum up (1) and (2), Theorem4 is proved.


## 2.2. Optimal LA Algorithm

InN LAs, there must be a LA that is the optimal limitation arrangement (OLA). OLA can be described in Definition 5.Definition 5.
Supposen≥4, given two LA events: X and Y. The corresponding LAs are {x1,x2,…,xn} and {y1,y2,…,yn}. The corresponding mathematical expectations are E(X) and E(Y), and we have the following formula:
(6)EX=∑k=1nxk-k,EY=∑k=1nyk-k.IfE(X)≠E(Y), then the event of the lesser mathematical expectation is OLA; otherwise, X or Y can be regarded as OLA.According to Definition5, we give Theorem 6.Theorem 6.
Considern≥4, and then
(7)OLA:=1,3,…,2i-1,…,n,2,4,…,2i,…,n-1;iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiin≥5,n%2=11,3,…,2i-1,…,n-1,2,4,…,2i,…,n;iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiin≥5,n%2=02,4,1,3or3,1,4,2;iiiiiiiiiiiiiiiiiiiiiiiin=4.Proof.
(1) Considern=4, there are two LAs, they are {2,4,1,3} and {3,1,4,2}, and their mathematical expectations are 6, so they can be regarded as OLA.
(2) Considern%2=0, suppose LA is {k1,k2,…,kn/2,…,kn}, and it is denoted by event K. E(K) can be shown in
(8)EK=k1-1+k2-2+⋯+kn/2-n2+kn/2+1-n2-1+⋯+kn-n.
We have two constraint conditions as follows:(9)1≤ki≤n,i=1,2,…,n,2≤kj+1-kj≤n-1,j=1,2,…,n-1,(10)kn/2+1-n2-1,…,kn-1-n+1,kn-n=k1-1,k2-1,…,kn/2-n2.
Formula (10) is substituted into formula (8); we have the following two formulas:
(11)EK=2k1-1+k2-2+⋯+kn/2-n2,(12)EK=2kn-n+kn-1-n+1(kn/2+1-n2-1)iiiiiiii+⋯+kn/2+1-n2-1.(a)
For formula (11), if k1-1 is minimum, then k1=1. Formula (9) is taken into account, k2≠2, and then k2=3. In a similar way, k1,k2,…,kn/2 is 1,3,…,n-1.(b)
For formula (12), if kn-n is minimum, then kn=n. Similarly, formula (9) is taken into account; kn,kn-1,…,kn/2+1 is n,n-2,…,2.
In short, whenn%2=0, OLA is {1,3,…,2i-1,…,n-1,2,4,…,2i,…,n}.
(3) Considern%2=1. Its proof method is similar to that of n%2=0.
To sum up (1), (2), and (3), Theorem6 is proved.


## 3. LAP Routing Algorithm Design

### 3.1. Basic Points

OSPF protocol pays attention to the information consistency of the whole network, namely, whether the link state is synchronous or not in computer network. LetS={1,2,…,n}, and these elements in set S are different from each other. These routers in network are converted into different numbers, and they can be regarded as the elements in set S. Suppose n nodes are arranged in a single link network, and then only these adjacent nodes can exchange information at the initial moment. Right after this, the n nodes are moved repeatedly by some methods, and information consistency of n nodes can be accomplished at some point. The process can be regarded as LAP transform, and the method can be named as LAP. In fact, LAP algorithm can be used for computer network and to keep the information consistency of the whole network under OSPF protocol, which is inspired by the following three basic points: the existence of network path, the construction of adjacent routers, and the existence of network loops.


#### 3.1.1. Network Path

Only when network connection is available, the information can be transmitted fluently. We have Theorem7.Theorem 7.
Suppose network connection is available; a path can be found from nodevi to node vk.Proof.
Suppose all nodes are included into setS, and the computer network can be decomposed into n single link structures. They are denoted by l1,l2,…,ln, the corresponding sets of nodes are denoted by S1,S2,…,Sn, and these connection nodes between each single link are denoted by trace1,trace2,…,tracen-1 (e.g., the connection node between S1 and S2 is trace1). We have the following formula:
(13)S=S1∪S2∪⋯∪Sn,Si∩Si+1=tracei.
Let nodevi be in single link li and node vk in single link lk; then vi∈Si and vk∈Sk. If i=k, then node vi and node vk are in the same single link. It is obvious that a path can be found from node vi to node vk. If i≠k, any i<k, then a path can also be found from node vi to node vk by these connection nodes tracei,tracei+1,…,tracek-1. Similarly, a path can also be found from node vi to node vk when i>k. To sum up, Theorem 7 is proved.


#### 3.1.2. Adjacent Routers

At the initial moment, nodevi is adjacent to node vi+1 and node vi-1, and node vi can get the information of node vi+1 and node vi-1 indirectly (i.e., node vi can exchange information with node vi+1 and node vi-1 without any hop). Right after this, n nodes should be rearranged by running the limitation arrangement after n nodes are moved. In short, node vi should not be adjacent to node vi+1 and node vi-1 at the next limitation arrangement moment. It should be adjacent to other routing nodes except node vi, node vi+1, and node vi-1, which is named the maximization construction on adjacent routers. For example, there are four routing nodes in single link network; they are v1, v2, v3, and v4 in turn. At the initial moment, node v2 can get the information of node v1 and node v3 indirectly. At the next limitation arrangement moment, node v2 should be adjacent to node v4. And then, the arrangement may be {v2,v4,v1,v3} not {v4,v3,v2,v1}. All processes need LAP algorithm to realize the maximization construction on adjacent routers, which aims at improving the speed of information consistency of the whole network (e.g., node v2 should be adjacent to other routing nodes. Otherwise, the solution is still the local optimal solution).


#### 3.1.3. Network Loops

The single link network is an ideal network topology, and there are a lot of loops in the actual network topology. At the initial moment, if one routing node is adjacent to many routing nodes, then it can accomplish information consistency with the other routing nodes faster. When these loops in network are so adequate that the network topology becomes an undirected complete graph, it is the best state that information consistency of the whole network can be accomplished at the fastest speed. So, the study of adding multiloops to single link network is necessary (See Section3).


### 3.2. LAP Routing Algorithm in Single Link Network

#### 3.2.1. Symmetric 0/1 Table

In this paper, we use symmetric 0/1 table to mark the results of information exchange. In terms of nodevi and node vk, if node vi and node vk have accomplished the information exchange, then the corresponding element value is 1; otherwise, it is 0. Any element of the symmetric 0/1 table is denoted by ai,k and shown in the following formula:
(14)ai,k=1,routingnodeiandroutingnodekhavebeencommunicated0,otherwise.In terms ofn routers, the state of information exchange after the initial moment is shown in Table 1.Table 1
Information exchange table after initialization forn routers.
ID
1
2
3
⋯
n
-
1
n
1
1
1
0
⋯
0
0
2
1
1
1
⋯
0
0
3
0
1
1
⋯
0
0
⋮
⋮
⋮
⋮
⋮
⋮
⋮
n
-
1
0
0
0
⋱
1
1
n
0
0
0
⋯
1
1In Table1, at the initial moment, all routing nodes are converted into different numbers and arranged for {1,2,…,n}. Any routing node knows its own information; hence ai,i=1. And because adjacent routing nodes can exchange information indirectly,  ai,i+1=ai+1,i=1. At the next limitation arrangement moment, if a routing node can obtain the new information of other routing nodes, then the element is changed to 1 from 0. If all the elements in Table 1 are 1, then n routing nodes have accomplished the information consistency in single link network. Here, it must be noted that OLA should be considered as the first LA in LAP routing algorithm because the corresponding mathematical expectation is the least, which saves time at the next limitation arrangement moment.Suppose there are five routers in single link network. At the initial moment, the arrangement is{1,2,3,4,5}; the status of information exchange can be seen from Table 2(a). The arrangement is {1,3,5,2,4} at the first limitation arrangement moment (i.e., OLA). The symmetric 0/1 table should be modified; then a1,3, a3,5, a5,2, and a2,4 are changed to 1 from 0. The status of information exchange can be seen from Table 2(b). After OLA, a1,4 and a1,5 are still 0; the next limitation arrangement should ensure that routing node 1 and routing node 4 or/and routing node 5 are adjacent. The arrangement is {1,4,5,2,3} at the second limitation arrangement moment, and a1,4 is changed to 1 from 0. The status of information exchange can be seen from Table 2(c). At the third limitation arrangement moment, the arrangement is {1,5,4,2,3}. a1,5 is changed to 1 from 0, and the status of information exchange can be seen from Table 2(d). In Table 2(d), all elements are 1; in other words, the five routers have accomplished the information consistency.Table 2
Changing process of information exchange for five routers.
(a)
ID
1
2
3
4
5
1
1
1
0
0
0
2
1
1
1
0
0
3
0
1
1
1
0
4
0
0
1
1
1
5
0
0
0
1
1
(b)
ID
1
2
3
4
5
1
1
1
1
0
0
2
1
1
1
1
1
3
1
1
1
1
1
4
0
1
1
1
1
5
0
1
1
1
1
(c)
ID
1
2
3
4
5
1
1
1
1
1
0
2
1
1
1
1
1
3
1
1
1
1
1
4
1
1
1
1
1
5
0
1
1
1
1
(d)
ID
1
2
3
4
5
1
1
1
1
1
1
2
1
1
1
1
1
3
1
1
1
1
1
4
1
1
1
1
1
5
1
1
1
1
1


#### 3.2.2. Depth Traversal Method

After initialization and OLA, one node is selected randomly as the head node, and then does depth traversal for the network topology. The concrete method is described in Hypothesis1.Hypothesis 1.
When the next routing node needs to be researched, the next routing node number should be the routing node number which accomplishes the information consistency with the other routing nodes at the slowest speed. Namely, it is the routing node number that the number of 0 in one row or column in symmetric 0/1 table is the greatest and the used routing node number in former cannot be regarded as the next routing node number. If the number of 0 in two or more rows is equal, then the minimal routing node number should be regarded as the next routing node number.
Suppose there are eight routers in single link network; the routing node number 1 is regarded as the head node, and the changing process of LA is shown in column 2 in Table3.
As can be seen from column 2 in Table3, the information consistency of eight routers can be accomplished by six times LAs, and the total number of coped routing nodes is 48.Table 3
Changing process of LA in single link network for eight routers.
LA numbers
LAs (no off nodes)
LAs (off nodes)
1
1,3
,
5,7
,
2,4
,
6,8
1,3
,
5,7
,
2,4
,
6,8
2
1,8
,
2,5
,
3,6
,
7,4
1,8
,
2,5
,
3,6
,
7,4
3
1,4
,
8,3
,
7,6
,
2,5
1,4
,
8,3
,
7,6
,
2,5
4
1,5
,
8,7
,
6,4
,
3,2
1,5
,
8,7
,
6
5
1,6
,
7,4
,
3,2
,
5,8
1,6
,
7
6
1,7
,
4,3
,
2,5
,
8,6
1,7
Total coped routing nodes
48
34


#### 3.2.3. Off Nodes Method

It is a phenomenon: at some moment, one or more routing nodes have accomplished the information consistency with the other routers in advance. If these routing nodes are still coped in the following LAs, then a lot of time will be spent because a lot of information is exchanged repeatedly. Given the above statement, we have Hypothesis2.Hypothesis 2.
If one or more routing nodes have accomplished the information consistency with the other routing nodes in advance, then they should not be coped in the following LAs.
Suppose there are eight routers in single link network. In this way, the changing process of LA is shown in column 3 in Table3.
It needs the same LA numbers (i.e., six times LAs) to accomplish the information consistency of eight routers under Hypotheses1 and 2 as can be seen from Table 3. However, it needs to cope with 48 routing nodes (See column 2) under Hypothesis 1 because every time LA needs to cope with 8 routing nodes. And it needs to cope with 34 routing nodes (See column 3) under Hypothesis 2 because routing nodes 2, 3, and 4 are off at the forth LA, routing node 5 is off at the fifth LA, and routing node 6 is off at the sixth LA. In other words, the total number of coped routing nodes decreases obviously under Hypothesis 2, which proves that, in comparison with Hypothesis 1, Hypothesis 2 is better. Additionally, an example of five routers in single link network (see Table 2 for details). After the first limitation arrangement moment, routing nodes 2 and 3 have accomplished the information consistency with the other routing nodes (i.e., all elements of column 2 and 3 are 1). So they should not be coped in the following LAs; namely, routing nodes 2 and 3 are off (see Table 2(b) for details).


#### 3.2.4. LAPSN Algorithm Description

After analysis of LAP algorithm and its related theorems, depth traversal method, and off nodes method, the routing algorithm based on limitation arrangement principle in single link network (LAPSN) is described in Algorithm 1.Algorithm
1: LAPSN.Step  1.
n routing nodes in single link network are converted into different numbers.Step  2. The OLA is got by Theorem 6. The current state of information exchange is marked by symmetric 0/1 table.Step  3. The ith LA is run, and k routing nodes are coped. The number of off routing nodes is checked, right after this; suppose it is m; the (i+1)th LA is run and k-m routing nodes are coped. Otherwise, the (i+1)th LA is run and k routing nodes are coped.Step  4. Check the current LA. If the number of routing nodes is 2, then convert to Step 5; otherwise, convert to Step 3.Step  5. Check the symmetric 0/1 table. If all elements in symmetric 0/1 table are 1, then end algorithm 1; otherwise, convert to Step 2.


### 3.3. LAP Routing Algorithm in Single Link Network with Multiloops

#### 3.3.1. Added Loops Model

The complex networks can be got by adding multiloops to single link network. In reality, the single link network with multiloops is the complex networks. The added loops model is shown in Figure1.Figure 1
The model of single link network with multiloops.The dashed line in Figure1 represents that the link between two routing nodes cannot be added. At the initial moment, the adjacent routing nodes are connected, so the link between routing node i and routing node i+1 or routing node i-1 cannot be added. The link between routing node i and routing node i-2 or routing node i+2 cannot be added because there is a link between them in OLA. For the same reason, the link between routing node 2 and routing node n cannot be added.Theorem 8.
SupposeP links can be added to single link network; the kinds of added links are 2P-1, where P is shown in formula (15). In this paper, we maintain that the number of links added is equivalent to that of loops added. Consider
(15)P=(n-2)(n-3)2-1.Proof.
(1) Proof of formula  (15) is as follows.
The total number of links in an undirected complete graph isn(n-1)/2. At the initial moment, the number of links in single link network is n-1. At OLA moment, the number of links is n-1. We have formula (16), and it is equivalent to formula (15). Consider
(16)P=nn-12-(n-1)-(n-1)=n-2n-32-1.
(2) Proof of2P-1 is as follows.
Give three variablesx, y, and n, x+yn is shown in the following formula:
(17)x+yn=n0x0yn+n1x1yn-1+⋯+nn-1xn-1y1+nnxny0.
Letx=y=1 and n=P; formula (17) can be converted to the following formula:
(18)P0+P1+P2+⋯+PP-1+PP=2P.
According to permutation and combination principle, it hasP1 kinds to add 1-loops (i.e., only one loop) to single link network and P2 kinds to add 2-loops to single link network. Similarly, it has Pk kinds to add k-loops to single link network. To summarize, the kinds of added links in single link network are P1+P2+⋯+PP-1+PP. We know that it is equivalent to 2P-1 when both sides of formula (18) are subtracted by 1.
To sum up (1) and (2), Theorem8 is proved.In order to study the network model of added loops, given is an added loops method and it is shown in Hypothesis3.Hypothesis 3.
Begin to add loops to single link network from the head node, and then add loops to single link network from the next node. The sequence by which links are added is1,4,1,5,…,1,n,2,5,2,6,…,n-3,n.


#### 3.3.2. LAPSNM Algorithm Description

Limitation arrangement principle in single link network with multiloops (LAPSNM) is described in Algorithm 2.Algorithm
2: LAPSNM.Step  1.
n routing nodes in single link network are converted into different numbers.Step  2. The OLA is got by Theorem 6. The current state of information exchange is marked by symmetric 0/1 table. The total number of coped routing nodes is recorded, and it is M.Step  3. Add links to single link network, and then run LAPSN algorithm. If the current number of added links is less than P, then run Step 3 repeatedly; otherwise, convert to Step 4.Step  4. Update M. If M=n, then convert to Step 5; otherwise, convert to Step 3.Step  5. Update symmetric 0/1 table. If all elements in symmetric 0/1 table are 1, then end Algorithm 2; otherwise, convert to Step 3.


## 3.1. Basic Points

OSPF protocol pays attention to the information consistency of the whole network, namely, whether the link state is synchronous or not in computer network. LetS={1,2,…,n}, and these elements in set S are different from each other. These routers in network are converted into different numbers, and they can be regarded as the elements in set S. Suppose n nodes are arranged in a single link network, and then only these adjacent nodes can exchange information at the initial moment. Right after this, the n nodes are moved repeatedly by some methods, and information consistency of n nodes can be accomplished at some point. The process can be regarded as LAP transform, and the method can be named as LAP. In fact, LAP algorithm can be used for computer network and to keep the information consistency of the whole network under OSPF protocol, which is inspired by the following three basic points: the existence of network path, the construction of adjacent routers, and the existence of network loops.


### 3.1.1. Network Path

Only when network connection is available, the information can be transmitted fluently. We have Theorem7.Theorem 7.
Suppose network connection is available; a path can be found from nodevi to node vk.Proof.
Suppose all nodes are included into setS, and the computer network can be decomposed into n single link structures. They are denoted by l1,l2,…,ln, the corresponding sets of nodes are denoted by S1,S2,…,Sn, and these connection nodes between each single link are denoted by trace1,trace2,…,tracen-1 (e.g., the connection node between S1 and S2 is trace1). We have the following formula:
(13)S=S1∪S2∪⋯∪Sn,Si∩Si+1=tracei.
Let nodevi be in single link li and node vk in single link lk; then vi∈Si and vk∈Sk. If i=k, then node vi and node vk are in the same single link. It is obvious that a path can be found from node vi to node vk. If i≠k, any i<k, then a path can also be found from node vi to node vk by these connection nodes tracei,tracei+1,…,tracek-1. Similarly, a path can also be found from node vi to node vk when i>k. To sum up, Theorem 7 is proved.


### 3.1.2. Adjacent Routers

At the initial moment, nodevi is adjacent to node vi+1 and node vi-1, and node vi can get the information of node vi+1 and node vi-1 indirectly (i.e., node vi can exchange information with node vi+1 and node vi-1 without any hop). Right after this, n nodes should be rearranged by running the limitation arrangement after n nodes are moved. In short, node vi should not be adjacent to node vi+1 and node vi-1 at the next limitation arrangement moment. It should be adjacent to other routing nodes except node vi, node vi+1, and node vi-1, which is named the maximization construction on adjacent routers. For example, there are four routing nodes in single link network; they are v1, v2, v3, and v4 in turn. At the initial moment, node v2 can get the information of node v1 and node v3 indirectly. At the next limitation arrangement moment, node v2 should be adjacent to node v4. And then, the arrangement may be {v2,v4,v1,v3} not {v4,v3,v2,v1}. All processes need LAP algorithm to realize the maximization construction on adjacent routers, which aims at improving the speed of information consistency of the whole network (e.g., node v2 should be adjacent to other routing nodes. Otherwise, the solution is still the local optimal solution).


### 3.1.3. Network Loops

The single link network is an ideal network topology, and there are a lot of loops in the actual network topology. At the initial moment, if one routing node is adjacent to many routing nodes, then it can accomplish information consistency with the other routing nodes faster. When these loops in network are so adequate that the network topology becomes an undirected complete graph, it is the best state that information consistency of the whole network can be accomplished at the fastest speed. So, the study of adding multiloops to single link network is necessary (See Section3).


## 3.1.1. Network Path

Only when network connection is available, the information can be transmitted fluently. We have Theorem7.Theorem 7.
Suppose network connection is available; a path can be found from nodevi to node vk.Proof.
Suppose all nodes are included into setS, and the computer network can be decomposed into n single link structures. They are denoted by l1,l2,…,ln, the corresponding sets of nodes are denoted by S1,S2,…,Sn, and these connection nodes between each single link are denoted by trace1,trace2,…,tracen-1 (e.g., the connection node between S1 and S2 is trace1). We have the following formula:
(13)S=S1∪S2∪⋯∪Sn,Si∩Si+1=tracei.
Let nodevi be in single link li and node vk in single link lk; then vi∈Si and vk∈Sk. If i=k, then node vi and node vk are in the same single link. It is obvious that a path can be found from node vi to node vk. If i≠k, any i<k, then a path can also be found from node vi to node vk by these connection nodes tracei,tracei+1,…,tracek-1. Similarly, a path can also be found from node vi to node vk when i>k. To sum up, Theorem 7 is proved.


## 3.1.2. Adjacent Routers

At the initial moment, nodevi is adjacent to node vi+1 and node vi-1, and node vi can get the information of node vi+1 and node vi-1 indirectly (i.e., node vi can exchange information with node vi+1 and node vi-1 without any hop). Right after this, n nodes should be rearranged by running the limitation arrangement after n nodes are moved. In short, node vi should not be adjacent to node vi+1 and node vi-1 at the next limitation arrangement moment. It should be adjacent to other routing nodes except node vi, node vi+1, and node vi-1, which is named the maximization construction on adjacent routers. For example, there are four routing nodes in single link network; they are v1, v2, v3, and v4 in turn. At the initial moment, node v2 can get the information of node v1 and node v3 indirectly. At the next limitation arrangement moment, node v2 should be adjacent to node v4. And then, the arrangement may be {v2,v4,v1,v3} not {v4,v3,v2,v1}. All processes need LAP algorithm to realize the maximization construction on adjacent routers, which aims at improving the speed of information consistency of the whole network (e.g., node v2 should be adjacent to other routing nodes. Otherwise, the solution is still the local optimal solution).


## 3.1.3. Network Loops

The single link network is an ideal network topology, and there are a lot of loops in the actual network topology. At the initial moment, if one routing node is adjacent to many routing nodes, then it can accomplish information consistency with the other routing nodes faster. When these loops in network are so adequate that the network topology becomes an undirected complete graph, it is the best state that information consistency of the whole network can be accomplished at the fastest speed. So, the study of adding multiloops to single link network is necessary (See Section3).


## 3.2. LAP Routing Algorithm in Single Link Network

### 3.2.1. Symmetric 0/1 Table

In this paper, we use symmetric 0/1 table to mark the results of information exchange. In terms of nodevi and node vk, if node vi and node vk have accomplished the information exchange, then the corresponding element value is 1; otherwise, it is 0. Any element of the symmetric 0/1 table is denoted by ai,k and shown in the following formula:
(14)ai,k=1,routingnodeiandroutingnodekhavebeencommunicated0,otherwise.In terms ofn routers, the state of information exchange after the initial moment is shown in Table 1.Table 1
Information exchange table after initialization forn routers.
ID
1
2
3
⋯
n
-
1
n
1
1
1
0
⋯
0
0
2
1
1
1
⋯
0
0
3
0
1
1
⋯
0
0
⋮
⋮
⋮
⋮
⋮
⋮
⋮
n
-
1
0
0
0
⋱
1
1
n
0
0
0
⋯
1
1In Table1, at the initial moment, all routing nodes are converted into different numbers and arranged for {1,2,…,n}. Any routing node knows its own information; hence ai,i=1. And because adjacent routing nodes can exchange information indirectly,  ai,i+1=ai+1,i=1. At the next limitation arrangement moment, if a routing node can obtain the new information of other routing nodes, then the element is changed to 1 from 0. If all the elements in Table 1 are 1, then n routing nodes have accomplished the information consistency in single link network. Here, it must be noted that OLA should be considered as the first LA in LAP routing algorithm because the corresponding mathematical expectation is the least, which saves time at the next limitation arrangement moment.Suppose there are five routers in single link network. At the initial moment, the arrangement is{1,2,3,4,5}; the status of information exchange can be seen from Table 2(a). The arrangement is {1,3,5,2,4} at the first limitation arrangement moment (i.e., OLA). The symmetric 0/1 table should be modified; then a1,3, a3,5, a5,2, and a2,4 are changed to 1 from 0. The status of information exchange can be seen from Table 2(b). After OLA, a1,4 and a1,5 are still 0; the next limitation arrangement should ensure that routing node 1 and routing node 4 or/and routing node 5 are adjacent. The arrangement is {1,4,5,2,3} at the second limitation arrangement moment, and a1,4 is changed to 1 from 0. The status of information exchange can be seen from Table 2(c). At the third limitation arrangement moment, the arrangement is {1,5,4,2,3}. a1,5 is changed to 1 from 0, and the status of information exchange can be seen from Table 2(d). In Table 2(d), all elements are 1; in other words, the five routers have accomplished the information consistency.Table 2
Changing process of information exchange for five routers.
(a)
ID
1
2
3
4
5
1
1
1
0
0
0
2
1
1
1
0
0
3
0
1
1
1
0
4
0
0
1
1
1
5
0
0
0
1
1
(b)
ID
1
2
3
4
5
1
1
1
1
0
0
2
1
1
1
1
1
3
1
1
1
1
1
4
0
1
1
1
1
5
0
1
1
1
1
(c)
ID
1
2
3
4
5
1
1
1
1
1
0
2
1
1
1
1
1
3
1
1
1
1
1
4
1
1
1
1
1
5
0
1
1
1
1
(d)
ID
1
2
3
4
5
1
1
1
1
1
1
2
1
1
1
1
1
3
1
1
1
1
1
4
1
1
1
1
1
5
1
1
1
1
1


### 3.2.2. Depth Traversal Method

After initialization and OLA, one node is selected randomly as the head node, and then does depth traversal for the network topology. The concrete method is described in Hypothesis1.Hypothesis 1.
When the next routing node needs to be researched, the next routing node number should be the routing node number which accomplishes the information consistency with the other routing nodes at the slowest speed. Namely, it is the routing node number that the number of 0 in one row or column in symmetric 0/1 table is the greatest and the used routing node number in former cannot be regarded as the next routing node number. If the number of 0 in two or more rows is equal, then the minimal routing node number should be regarded as the next routing node number.
Suppose there are eight routers in single link network; the routing node number 1 is regarded as the head node, and the changing process of LA is shown in column 2 in Table3.
As can be seen from column 2 in Table3, the information consistency of eight routers can be accomplished by six times LAs, and the total number of coped routing nodes is 48.Table 3
Changing process of LA in single link network for eight routers.
LA numbers
LAs (no off nodes)
LAs (off nodes)
1
1,3
,
5,7
,
2,4
,
6,8
1,3
,
5,7
,
2,4
,
6,8
2
1,8
,
2,5
,
3,6
,
7,4
1,8
,
2,5
,
3,6
,
7,4
3
1,4
,
8,3
,
7,6
,
2,5
1,4
,
8,3
,
7,6
,
2,5
4
1,5
,
8,7
,
6,4
,
3,2
1,5
,
8,7
,
6
5
1,6
,
7,4
,
3,2
,
5,8
1,6
,
7
6
1,7
,
4,3
,
2,5
,
8,6
1,7
Total coped routing nodes
48
34


### 3.2.3. Off Nodes Method

It is a phenomenon: at some moment, one or more routing nodes have accomplished the information consistency with the other routers in advance. If these routing nodes are still coped in the following LAs, then a lot of time will be spent because a lot of information is exchanged repeatedly. Given the above statement, we have Hypothesis2.Hypothesis 2.
If one or more routing nodes have accomplished the information consistency with the other routing nodes in advance, then they should not be coped in the following LAs.
Suppose there are eight routers in single link network. In this way, the changing process of LA is shown in column 3 in Table3.
It needs the same LA numbers (i.e., six times LAs) to accomplish the information consistency of eight routers under Hypotheses1 and 2 as can be seen from Table 3. However, it needs to cope with 48 routing nodes (See column 2) under Hypothesis 1 because every time LA needs to cope with 8 routing nodes. And it needs to cope with 34 routing nodes (See column 3) under Hypothesis 2 because routing nodes 2, 3, and 4 are off at the forth LA, routing node 5 is off at the fifth LA, and routing node 6 is off at the sixth LA. In other words, the total number of coped routing nodes decreases obviously under Hypothesis 2, which proves that, in comparison with Hypothesis 1, Hypothesis 2 is better. Additionally, an example of five routers in single link network (see Table 2 for details). After the first limitation arrangement moment, routing nodes 2 and 3 have accomplished the information consistency with the other routing nodes (i.e., all elements of column 2 and 3 are 1). So they should not be coped in the following LAs; namely, routing nodes 2 and 3 are off (see Table 2(b) for details).


### 3.2.4. LAPSN Algorithm Description

After analysis of LAP algorithm and its related theorems, depth traversal method, and off nodes method, the routing algorithm based on limitation arrangement principle in single link network (LAPSN) is described in Algorithm 1.Algorithm
1: LAPSN.Step  1.
n routing nodes in single link network are converted into different numbers.Step  2. The OLA is got by Theorem 6. The current state of information exchange is marked by symmetric 0/1 table.Step  3. The ith LA is run, and k routing nodes are coped. The number of off routing nodes is checked, right after this; suppose it is m; the (i+1)th LA is run and k-m routing nodes are coped. Otherwise, the (i+1)th LA is run and k routing nodes are coped.Step  4. Check the current LA. If the number of routing nodes is 2, then convert to Step 5; otherwise, convert to Step 3.Step  5. Check the symmetric 0/1 table. If all elements in symmetric 0/1 table are 1, then end algorithm 1; otherwise, convert to Step 2.


## 3.2.1. Symmetric 0/1 Table

In this paper, we use symmetric 0/1 table to mark the results of information exchange. In terms of nodevi and node vk, if node vi and node vk have accomplished the information exchange, then the corresponding element value is 1; otherwise, it is 0. Any element of the symmetric 0/1 table is denoted by ai,k and shown in the following formula:
(14)ai,k=1,routingnodeiandroutingnodekhavebeencommunicated0,otherwise.In terms ofn routers, the state of information exchange after the initial moment is shown in Table 1.Table 1
Information exchange table after initialization forn routers.
ID
1
2
3
⋯
n
-
1
n
1
1
1
0
⋯
0
0
2
1
1
1
⋯
0
0
3
0
1
1
⋯
0
0
⋮
⋮
⋮
⋮
⋮
⋮
⋮
n
-
1
0
0
0
⋱
1
1
n
0
0
0
⋯
1
1In Table1, at the initial moment, all routing nodes are converted into different numbers and arranged for {1,2,…,n}. Any routing node knows its own information; hence ai,i=1. And because adjacent routing nodes can exchange information indirectly,  ai,i+1=ai+1,i=1. At the next limitation arrangement moment, if a routing node can obtain the new information of other routing nodes, then the element is changed to 1 from 0. If all the elements in Table 1 are 1, then n routing nodes have accomplished the information consistency in single link network. Here, it must be noted that OLA should be considered as the first LA in LAP routing algorithm because the corresponding mathematical expectation is the least, which saves time at the next limitation arrangement moment.Suppose there are five routers in single link network. At the initial moment, the arrangement is{1,2,3,4,5}; the status of information exchange can be seen from Table 2(a). The arrangement is {1,3,5,2,4} at the first limitation arrangement moment (i.e., OLA). The symmetric 0/1 table should be modified; then a1,3, a3,5, a5,2, and a2,4 are changed to 1 from 0. The status of information exchange can be seen from Table 2(b). After OLA, a1,4 and a1,5 are still 0; the next limitation arrangement should ensure that routing node 1 and routing node 4 or/and routing node 5 are adjacent. The arrangement is {1,4,5,2,3} at the second limitation arrangement moment, and a1,4 is changed to 1 from 0. The status of information exchange can be seen from Table 2(c). At the third limitation arrangement moment, the arrangement is {1,5,4,2,3}. a1,5 is changed to 1 from 0, and the status of information exchange can be seen from Table 2(d). In Table 2(d), all elements are 1; in other words, the five routers have accomplished the information consistency.Table 2
Changing process of information exchange for five routers.
(a)
ID
1
2
3
4
5
1
1
1
0
0
0
2
1
1
1
0
0
3
0
1
1
1
0
4
0
0
1
1
1
5
0
0
0
1
1
(b)
ID
1
2
3
4
5
1
1
1
1
0
0
2
1
1
1
1
1
3
1
1
1
1
1
4
0
1
1
1
1
5
0
1
1
1
1
(c)
ID
1
2
3
4
5
1
1
1
1
1
0
2
1
1
1
1
1
3
1
1
1
1
1
4
1
1
1
1
1
5
0
1
1
1
1
(d)
ID
1
2
3
4
5
1
1
1
1
1
1
2
1
1
1
1
1
3
1
1
1
1
1
4
1
1
1
1
1
5
1
1
1
1
1


## 3.2.2. Depth Traversal Method

After initialization and OLA, one node is selected randomly as the head node, and then does depth traversal for the network topology. The concrete method is described in Hypothesis1.Hypothesis 1.
When the next routing node needs to be researched, the next routing node number should be the routing node number which accomplishes the information consistency with the other routing nodes at the slowest speed. Namely, it is the routing node number that the number of 0 in one row or column in symmetric 0/1 table is the greatest and the used routing node number in former cannot be regarded as the next routing node number. If the number of 0 in two or more rows is equal, then the minimal routing node number should be regarded as the next routing node number.
Suppose there are eight routers in single link network; the routing node number 1 is regarded as the head node, and the changing process of LA is shown in column 2 in Table3.
As can be seen from column 2 in Table3, the information consistency of eight routers can be accomplished by six times LAs, and the total number of coped routing nodes is 48.Table 3
Changing process of LA in single link network for eight routers.
LA numbers
LAs (no off nodes)
LAs (off nodes)
1
1,3
,
5,7
,
2,4
,
6,8
1,3
,
5,7
,
2,4
,
6,8
2
1,8
,
2,5
,
3,6
,
7,4
1,8
,
2,5
,
3,6
,
7,4
3
1,4
,
8,3
,
7,6
,
2,5
1,4
,
8,3
,
7,6
,
2,5
4
1,5
,
8,7
,
6,4
,
3,2
1,5
,
8,7
,
6
5
1,6
,
7,4
,
3,2
,
5,8
1,6
,
7
6
1,7
,
4,3
,
2,5
,
8,6
1,7
Total coped routing nodes
48
34


## 3.2.3. Off Nodes Method

It is a phenomenon: at some moment, one or more routing nodes have accomplished the information consistency with the other routers in advance. If these routing nodes are still coped in the following LAs, then a lot of time will be spent because a lot of information is exchanged repeatedly. Given the above statement, we have Hypothesis2.Hypothesis 2.
If one or more routing nodes have accomplished the information consistency with the other routing nodes in advance, then they should not be coped in the following LAs.
Suppose there are eight routers in single link network. In this way, the changing process of LA is shown in column 3 in Table3.
It needs the same LA numbers (i.e., six times LAs) to accomplish the information consistency of eight routers under Hypotheses1 and 2 as can be seen from Table 3. However, it needs to cope with 48 routing nodes (See column 2) under Hypothesis 1 because every time LA needs to cope with 8 routing nodes. And it needs to cope with 34 routing nodes (See column 3) under Hypothesis 2 because routing nodes 2, 3, and 4 are off at the forth LA, routing node 5 is off at the fifth LA, and routing node 6 is off at the sixth LA. In other words, the total number of coped routing nodes decreases obviously under Hypothesis 2, which proves that, in comparison with Hypothesis 1, Hypothesis 2 is better. Additionally, an example of five routers in single link network (see Table 2 for details). After the first limitation arrangement moment, routing nodes 2 and 3 have accomplished the information consistency with the other routing nodes (i.e., all elements of column 2 and 3 are 1). So they should not be coped in the following LAs; namely, routing nodes 2 and 3 are off (see Table 2(b) for details).


## 3.2.4. LAPSN Algorithm Description

After analysis of LAP algorithm and its related theorems, depth traversal method, and off nodes method, the routing algorithm based on limitation arrangement principle in single link network (LAPSN) is described in Algorithm 1.Algorithm
1: LAPSN.Step  1.
n routing nodes in single link network are converted into different numbers.Step  2. The OLA is got by Theorem 6. The current state of information exchange is marked by symmetric 0/1 table.Step  3. The ith LA is run, and k routing nodes are coped. The number of off routing nodes is checked, right after this; suppose it is m; the (i+1)th LA is run and k-m routing nodes are coped. Otherwise, the (i+1)th LA is run and k routing nodes are coped.Step  4. Check the current LA. If the number of routing nodes is 2, then convert to Step 5; otherwise, convert to Step 3.Step  5. Check the symmetric 0/1 table. If all elements in symmetric 0/1 table are 1, then end algorithm 1; otherwise, convert to Step 2.


## 3.3. LAP Routing Algorithm in Single Link Network with Multiloops

### 3.3.1. Added Loops Model

The complex networks can be got by adding multiloops to single link network. In reality, the single link network with multiloops is the complex networks. The added loops model is shown in Figure1.Figure 1
The model of single link network with multiloops.The dashed line in Figure1 represents that the link between two routing nodes cannot be added. At the initial moment, the adjacent routing nodes are connected, so the link between routing node i and routing node i+1 or routing node i-1 cannot be added. The link between routing node i and routing node i-2 or routing node i+2 cannot be added because there is a link between them in OLA. For the same reason, the link between routing node 2 and routing node n cannot be added.Theorem 8.
SupposeP links can be added to single link network; the kinds of added links are 2P-1, where P is shown in formula (15). In this paper, we maintain that the number of links added is equivalent to that of loops added. Consider
(15)P=(n-2)(n-3)2-1.Proof.
(1) Proof of formula  (15) is as follows.
The total number of links in an undirected complete graph isn(n-1)/2. At the initial moment, the number of links in single link network is n-1. At OLA moment, the number of links is n-1. We have formula (16), and it is equivalent to formula (15). Consider
(16)P=nn-12-(n-1)-(n-1)=n-2n-32-1.
(2) Proof of2P-1 is as follows.
Give three variablesx, y, and n, x+yn is shown in the following formula:
(17)x+yn=n0x0yn+n1x1yn-1+⋯+nn-1xn-1y1+nnxny0.
Letx=y=1 and n=P; formula (17) can be converted to the following formula:
(18)P0+P1+P2+⋯+PP-1+PP=2P.
According to permutation and combination principle, it hasP1 kinds to add 1-loops (i.e., only one loop) to single link network and P2 kinds to add 2-loops to single link network. Similarly, it has Pk kinds to add k-loops to single link network. To summarize, the kinds of added links in single link network are P1+P2+⋯+PP-1+PP. We know that it is equivalent to 2P-1 when both sides of formula (18) are subtracted by 1.
To sum up (1) and (2), Theorem8 is proved.In order to study the network model of added loops, given is an added loops method and it is shown in Hypothesis3.Hypothesis 3.
Begin to add loops to single link network from the head node, and then add loops to single link network from the next node. The sequence by which links are added is1,4,1,5,…,1,n,2,5,2,6,…,n-3,n.


### 3.3.2. LAPSNM Algorithm Description

Limitation arrangement principle in single link network with multiloops (LAPSNM) is described in Algorithm 2.Algorithm
2: LAPSNM.Step  1.
n routing nodes in single link network are converted into different numbers.Step  2. The OLA is got by Theorem 6. The current state of information exchange is marked by symmetric 0/1 table. The total number of coped routing nodes is recorded, and it is M.Step  3. Add links to single link network, and then run LAPSN algorithm. If the current number of added links is less than P, then run Step 3 repeatedly; otherwise, convert to Step 4.Step  4. Update M. If M=n, then convert to Step 5; otherwise, convert to Step 3.Step  5. Update symmetric 0/1 table. If all elements in symmetric 0/1 table are 1, then end Algorithm 2; otherwise, convert to Step 3.


## 3.3.1. Added Loops Model

The complex networks can be got by adding multiloops to single link network. In reality, the single link network with multiloops is the complex networks. The added loops model is shown in Figure1.Figure 1
The model of single link network with multiloops.The dashed line in Figure1 represents that the link between two routing nodes cannot be added. At the initial moment, the adjacent routing nodes are connected, so the link between routing node i and routing node i+1 or routing node i-1 cannot be added. The link between routing node i and routing node i-2 or routing node i+2 cannot be added because there is a link between them in OLA. For the same reason, the link between routing node 2 and routing node n cannot be added.Theorem 8.
SupposeP links can be added to single link network; the kinds of added links are 2P-1, where P is shown in formula (15). In this paper, we maintain that the number of links added is equivalent to that of loops added. Consider
(15)P=(n-2)(n-3)2-1.Proof.
(1) Proof of formula  (15) is as follows.
The total number of links in an undirected complete graph isn(n-1)/2. At the initial moment, the number of links in single link network is n-1. At OLA moment, the number of links is n-1. We have formula (16), and it is equivalent to formula (15). Consider
(16)P=nn-12-(n-1)-(n-1)=n-2n-32-1.
(2) Proof of2P-1 is as follows.
Give three variablesx, y, and n, x+yn is shown in the following formula:
(17)x+yn=n0x0yn+n1x1yn-1+⋯+nn-1xn-1y1+nnxny0.
Letx=y=1 and n=P; formula (17) can be converted to the following formula:
(18)P0+P1+P2+⋯+PP-1+PP=2P.
According to permutation and combination principle, it hasP1 kinds to add 1-loops (i.e., only one loop) to single link network and P2 kinds to add 2-loops to single link network. Similarly, it has Pk kinds to add k-loops to single link network. To summarize, the kinds of added links in single link network are P1+P2+⋯+PP-1+PP. We know that it is equivalent to 2P-1 when both sides of formula (18) are subtracted by 1.
To sum up (1) and (2), Theorem8 is proved.In order to study the network model of added loops, given is an added loops method and it is shown in Hypothesis3.Hypothesis 3.
Begin to add loops to single link network from the head node, and then add loops to single link network from the next node. The sequence by which links are added is1,4,1,5,…,1,n,2,5,2,6,…,n-3,n.


## 3.3.2. LAPSNM Algorithm Description

Limitation arrangement principle in single link network with multiloops (LAPSNM) is described in Algorithm 2.Algorithm
2: LAPSNM.Step  1.
n routing nodes in single link network are converted into different numbers.Step  2. The OLA is got by Theorem 6. The current state of information exchange is marked by symmetric 0/1 table. The total number of coped routing nodes is recorded, and it is M.Step  3. Add links to single link network, and then run LAPSN algorithm. If the current number of added links is less than P, then run Step 3 repeatedly; otherwise, convert to Step 4.Step  4. Update M. If M=n, then convert to Step 5; otherwise, convert to Step 3.Step  5. Update symmetric 0/1 table. If all elements in symmetric 0/1 table are 1, then end Algorithm 2; otherwise, convert to Step 3.


## 4. Simulation Results

In this Section, we will give two kinds of simulation experiments, one is to test the performance of LAPSN algorithm (i.e., optimization results under Hypothesis2) and LAPSNM algorithm (i.e., optimization results by adding links to single link network), and the other one is to be compared with Dijkstra algorithm on information consistency delays of the whole network. The test environment is set up on a personal computer with Intel Q8400, 2.66 GHZ CPU, 4 G RAM, and running on Windows 7. In addition, two different simulators (i.e., VC6.0 and NS2) are selected to test LAPSN algorithm and LAPSNM algorithm, which is necessary and reasonable. Three reasons are listed as follows. Firstly, VC6.0 adopts C++ code; the results often are ideal because they are without considering bandwidth, delays, cache, and so forth. However, it can be used to test enormous routing nodes. NS2 is a network simulator, and it adopts VC++ code and OTCL script. The results often are considerably realistic. However, it usually is applied to test relatively fewer routing nodes. Secondly, the combination of two experiments of different styles can further prove the rationality of algorithms, which ensures that the structure of this paper is rigorous and the algorithms can be more easily accepted by other authors. Finally, VC tests Hypotheses 1 and 2 and the method of added links, which is microcosmic. NS2 tests delays of algorithms, which is macroscopic.


### 4.1. Static Experiments

LAPSN algorithm and LAPSNM algorithm are implemented in VC6.0.


#### 4.1.1. LAPSN Algorithm Experiment

There are 5–400 routing nodes in single link network and the step size is one. The LA numbers and code running time under Hypothesis1 are shown in Figure 2.Figure 2
LA numbers and code running time under Hypothesis1.The line that comes from LA numbers changes smoothly and stably and the curve that comes from the code running time also changes smoothly and stably, which proves that Hypothesis1 has impact on LAPSN algorithm stably. Additionally, the number of LA is 0 at the beginning because the limitation arrangement is generated when the number of routing nodes in single link network is greater than 4, which can be seen from (2) on condition where 1≤n<4. In summary, Hypothesis 1 has a good adaptability for LAPSN algorithm.In order to prove the performance of Hypothesis2, we do two kinds of experiments. One is given 75–115 routing nodes in single link network and the step size is five, and the other one is given 40–400 routing nodes in single link network and the step size is forty. The experimental results are shown in Figures 3 and 4.Figure 3
The relationship between LA numbers and the number of coped routing nodes in a LA wheren=75–115 with step size of 5 in single link network.Figure 4
The relationship between LA numbers and the number of coped routing nodes in a LA wheren=40–400 with step size of 40 in single link network.Suppose routing nodes in single link network aren. The number of coped routing nodes in a LA begins to decrease when LA numbers are about n/2 because some routing nodes begin to be off at this moment, which can be proved by Hypothesis 2. By analysis of Figures 3 and 4, we know that the change of the relationship between LA numbers and the number of coped routing nodes in a LA is very stable by 21 polygonal lines. The concrete performance is denoted by r, that is, the difference between 1 and the ratio of the total number of coped routing nodes under Hypothesis 2 and the total number of coped routing nodes without Hypothesis 2 and shown in Table 4.Table 4
Performance table of LAPSN algorithm under Hypothesis1 and Hypothesis 2.
Nodes
40
75
80
85
90
95
100
105
110
Total nodes coped under Hypothesis1
1520
5475
6240
7055
7920
8835
9800
10815
11880
Total nodes coped under Hypothesis2
1006
3554
4048
4557
5124
5702
6301
6965
7647
Performance
0.3381
0.3508
0.3513
0.3541
0.3530
0.3546
0.3570
0.3560
0.3563
Nodes
115
120
160
200
240
280
320
360
400
Total nodes coped under Hypothesis1
12995
14160
25280
39600
57120
77840
101760
128880
159200
Total nodes coped under Hypothesis2
8353
9096
16151
25233
36323
49405
64526
81620
100805
Performance
0.3572
0.3576
0.3611
0.3628
0.3641
0.3653
0.3659
0.3667
0.3668We know that the performance is in(0,0.5) by Figures 3 and 4 because the number of coped routing nodes in a LA begins to decrease when LA numbers are about n/2. As can be seen from Table 4, with the increase of routing nodes in single link network, the performance on LAPSN algorithm under Hypothesis 2 improves correspondingly and they are in (0.3381,0.3668). In addition, the total number of coped routing nodes under Hypothesis 2 is less than that of Hypothesis 1. The results prove that Hypothesis 2 has a good optimization performance on LAPSN algorithm.


#### 4.1.2. LAPSNM Algorithm Experiment

The experimental examples are the same as Section4.1.1. We study the relationship between the number of added links and the total number of coped routing nodes. LAPSNM algorithm is run, and we have Figures 5 and 6.Figure 5
The relationship between the number of added links andM where n=75–115 with step size of 5 under Hypothesis 3.Figure 6
The relationship between the number of added links andM where n=40–400 with step size of 40 under Hypothesis 3.In general, with the increase of the number of added links, the total number of routing nodes which are coped decreases. When the number of added links reachesP, the information consistency of whole network is accomplished (i.e., it can be seen from (15)), because the complex network is an undirected complete graph and all routing nodes can exchange information with each other at the same time (i.e., the total number of coped routing nodes is n which is seen from (7)). In short, LAPSNM algorithm is superior to LAPSN algorithm.


### 4.2. Dynamic Experiments

LAPSN algorithm and LAPSNM algorithm are implemented in NS2. Because Dijkstra algorithm is only used to accomplish the information consistency of the whole network under OSPF protocol at present, they are compared with Dijkstra algorithm in this section.


#### 4.2.1. LAPSN Algorithm Test

Simulation parameters are as follows: packet size is 256 MB, link capacity is 1 Mbit/s, buffer queue type is Droptail, link type is Duplex-link, and buffer queue size is 1 GB. Routing nodes are 11–20 in single link network, the corresponding network delays are 11–20 ms, and movement delays of routing node are 1 ms. The information consistency delays of whole network are shown in Figure7.Figure 7
The relationship between routing nodes in single link network and information consistency delays.In Figure7, the information consistency delays of LAPSN algorithm are greater than that of Dijkstra algorithm. With the increase of routing nodes in single link network, the delays difference is greater and greater. Generally, LAPSN algorithm can solve the problem of information consistency of the whole network under OSPF protocol. But it is inferior to Dijkstra algorithm.


#### 4.2.2. LAPSNM Algorithm Test

Simulation parameters are as follows: routing nodes are 20 in single link network, the corresponding network delays are 20 ms, buffer queue size is 5 GB, and the other simulation parameters are the same as Section4.2.1. We add 5, 10, 25, and 100 loops to single link network. The changing process of accumulation delays is shown in Figure 8, and the information consistency delays of whole network are shown in Table 5.Table 5
The comparison table of information consistency delays/ms.
Algorithm
LAPSN
Dijkstra
LAPSNM
R
=
5
R
=
10
R
=
25
R
=
100
Delays
461
380
357
313
288
171Figure 8
The changing process of information consistency delays in single link network with 5, 10, 25, and 100 loops.As can be seen from Figure8 and Table 5, the more added loops to the single link network, the less obviously the information consistency delays of the whole network. Therefore, we conclude that LAPSNM algorithm also can solve the problem of information consistency of the whole network under OSPF protocol and it is superior to LAPSN algorithm and Dijkstra algorithm.


## 4.1. Static Experiments

LAPSN algorithm and LAPSNM algorithm are implemented in VC6.0.


### 4.1.1. LAPSN Algorithm Experiment

There are 5–400 routing nodes in single link network and the step size is one. The LA numbers and code running time under Hypothesis1 are shown in Figure 2.Figure 2
LA numbers and code running time under Hypothesis1.The line that comes from LA numbers changes smoothly and stably and the curve that comes from the code running time also changes smoothly and stably, which proves that Hypothesis1 has impact on LAPSN algorithm stably. Additionally, the number of LA is 0 at the beginning because the limitation arrangement is generated when the number of routing nodes in single link network is greater than 4, which can be seen from (2) on condition where 1≤n<4. In summary, Hypothesis 1 has a good adaptability for LAPSN algorithm.In order to prove the performance of Hypothesis2, we do two kinds of experiments. One is given 75–115 routing nodes in single link network and the step size is five, and the other one is given 40–400 routing nodes in single link network and the step size is forty. The experimental results are shown in Figures 3 and 4.Figure 3
The relationship between LA numbers and the number of coped routing nodes in a LA wheren=75–115 with step size of 5 in single link network.Figure 4
The relationship between LA numbers and the number of coped routing nodes in a LA wheren=40–400 with step size of 40 in single link network.Suppose routing nodes in single link network aren. The number of coped routing nodes in a LA begins to decrease when LA numbers are about n/2 because some routing nodes begin to be off at this moment, which can be proved by Hypothesis 2. By analysis of Figures 3 and 4, we know that the change of the relationship between LA numbers and the number of coped routing nodes in a LA is very stable by 21 polygonal lines. The concrete performance is denoted by r, that is, the difference between 1 and the ratio of the total number of coped routing nodes under Hypothesis 2 and the total number of coped routing nodes without Hypothesis 2 and shown in Table 4.Table 4
Performance table of LAPSN algorithm under Hypothesis1 and Hypothesis 2.
Nodes
40
75
80
85
90
95
100
105
110
Total nodes coped under Hypothesis1
1520
5475
6240
7055
7920
8835
9800
10815
11880
Total nodes coped under Hypothesis2
1006
3554
4048
4557
5124
5702
6301
6965
7647
Performance
0.3381
0.3508
0.3513
0.3541
0.3530
0.3546
0.3570
0.3560
0.3563
Nodes
115
120
160
200
240
280
320
360
400
Total nodes coped under Hypothesis1
12995
14160
25280
39600
57120
77840
101760
128880
159200
Total nodes coped under Hypothesis2
8353
9096
16151
25233
36323
49405
64526
81620
100805
Performance
0.3572
0.3576
0.3611
0.3628
0.3641
0.3653
0.3659
0.3667
0.3668We know that the performance is in(0,0.5) by Figures 3 and 4 because the number of coped routing nodes in a LA begins to decrease when LA numbers are about n/2. As can be seen from Table 4, with the increase of routing nodes in single link network, the performance on LAPSN algorithm under Hypothesis 2 improves correspondingly and they are in (0.3381,0.3668). In addition, the total number of coped routing nodes under Hypothesis 2 is less than that of Hypothesis 1. The results prove that Hypothesis 2 has a good optimization performance on LAPSN algorithm.


### 4.1.2. LAPSNM Algorithm Experiment

The experimental examples are the same as Section4.1.1. We study the relationship between the number of added links and the total number of coped routing nodes. LAPSNM algorithm is run, and we have Figures 5 and 6.Figure 5
The relationship between the number of added links andM where n=75–115 with step size of 5 under Hypothesis 3.Figure 6
The relationship between the number of added links andM where n=40–400 with step size of 40 under Hypothesis 3.In general, with the increase of the number of added links, the total number of routing nodes which are coped decreases. When the number of added links reachesP, the information consistency of whole network is accomplished (i.e., it can be seen from (15)), because the complex network is an undirected complete graph and all routing nodes can exchange information with each other at the same time (i.e., the total number of coped routing nodes is n which is seen from (7)). In short, LAPSNM algorithm is superior to LAPSN algorithm.


## 4.1.1. LAPSN Algorithm Experiment

There are 5–400 routing nodes in single link network and the step size is one. The LA numbers and code running time under Hypothesis1 are shown in Figure 2.Figure 2
LA numbers and code running time under Hypothesis1.The line that comes from LA numbers changes smoothly and stably and the curve that comes from the code running time also changes smoothly and stably, which proves that Hypothesis1 has impact on LAPSN algorithm stably. Additionally, the number of LA is 0 at the beginning because the limitation arrangement is generated when the number of routing nodes in single link network is greater than 4, which can be seen from (2) on condition where 1≤n<4. In summary, Hypothesis 1 has a good adaptability for LAPSN algorithm.In order to prove the performance of Hypothesis2, we do two kinds of experiments. One is given 75–115 routing nodes in single link network and the step size is five, and the other one is given 40–400 routing nodes in single link network and the step size is forty. The experimental results are shown in Figures 3 and 4.Figure 3
The relationship between LA numbers and the number of coped routing nodes in a LA wheren=75–115 with step size of 5 in single link network.Figure 4
The relationship between LA numbers and the number of coped routing nodes in a LA wheren=40–400 with step size of 40 in single link network.Suppose routing nodes in single link network aren. The number of coped routing nodes in a LA begins to decrease when LA numbers are about n/2 because some routing nodes begin to be off at this moment, which can be proved by Hypothesis 2. By analysis of Figures 3 and 4, we know that the change of the relationship between LA numbers and the number of coped routing nodes in a LA is very stable by 21 polygonal lines. The concrete performance is denoted by r, that is, the difference between 1 and the ratio of the total number of coped routing nodes under Hypothesis 2 and the total number of coped routing nodes without Hypothesis 2 and shown in Table 4.Table 4
Performance table of LAPSN algorithm under Hypothesis1 and Hypothesis 2.
Nodes
40
75
80
85
90
95
100
105
110
Total nodes coped under Hypothesis1
1520
5475
6240
7055
7920
8835
9800
10815
11880
Total nodes coped under Hypothesis2
1006
3554
4048
4557
5124
5702
6301
6965
7647
Performance
0.3381
0.3508
0.3513
0.3541
0.3530
0.3546
0.3570
0.3560
0.3563
Nodes
115
120
160
200
240
280
320
360
400
Total nodes coped under Hypothesis1
12995
14160
25280
39600
57120
77840
101760
128880
159200
Total nodes coped under Hypothesis2
8353
9096
16151
25233
36323
49405
64526
81620
100805
Performance
0.3572
0.3576
0.3611
0.3628
0.3641
0.3653
0.3659
0.3667
0.3668We know that the performance is in(0,0.5) by Figures 3 and 4 because the number of coped routing nodes in a LA begins to decrease when LA numbers are about n/2. As can be seen from Table 4, with the increase of routing nodes in single link network, the performance on LAPSN algorithm under Hypothesis 2 improves correspondingly and they are in (0.3381,0.3668). In addition, the total number of coped routing nodes under Hypothesis 2 is less than that of Hypothesis 1. The results prove that Hypothesis 2 has a good optimization performance on LAPSN algorithm.


## 4.1.2. LAPSNM Algorithm Experiment

The experimental examples are the same as Section4.1.1. We study the relationship between the number of added links and the total number of coped routing nodes. LAPSNM algorithm is run, and we have Figures 5 and 6.Figure 5
The relationship between the number of added links andM where n=75–115 with step size of 5 under Hypothesis 3.Figure 6
The relationship between the number of added links andM where n=40–400 with step size of 40 under Hypothesis 3.In general, with the increase of the number of added links, the total number of routing nodes which are coped decreases. When the number of added links reachesP, the information consistency of whole network is accomplished (i.e., it can be seen from (15)), because the complex network is an undirected complete graph and all routing nodes can exchange information with each other at the same time (i.e., the total number of coped routing nodes is n which is seen from (7)). In short, LAPSNM algorithm is superior to LAPSN algorithm.


## 4.2. Dynamic Experiments

LAPSN algorithm and LAPSNM algorithm are implemented in NS2. Because Dijkstra algorithm is only used to accomplish the information consistency of the whole network under OSPF protocol at present, they are compared with Dijkstra algorithm in this section.


### 4.2.1. LAPSN Algorithm Test

Simulation parameters are as follows: packet size is 256 MB, link capacity is 1 Mbit/s, buffer queue type is Droptail, link type is Duplex-link, and buffer queue size is 1 GB. Routing nodes are 11–20 in single link network, the corresponding network delays are 11–20 ms, and movement delays of routing node are 1 ms. The information consistency delays of whole network are shown in Figure7.Figure 7
The relationship between routing nodes in single link network and information consistency delays.In Figure7, the information consistency delays of LAPSN algorithm are greater than that of Dijkstra algorithm. With the increase of routing nodes in single link network, the delays difference is greater and greater. Generally, LAPSN algorithm can solve the problem of information consistency of the whole network under OSPF protocol. But it is inferior to Dijkstra algorithm.


### 4.2.2. LAPSNM Algorithm Test

Simulation parameters are as follows: routing nodes are 20 in single link network, the corresponding network delays are 20 ms, buffer queue size is 5 GB, and the other simulation parameters are the same as Section4.2.1. We add 5, 10, 25, and 100 loops to single link network. The changing process of accumulation delays is shown in Figure 8, and the information consistency delays of whole network are shown in Table 5.Table 5
The comparison table of information consistency delays/ms.
Algorithm
LAPSN
Dijkstra
LAPSNM
R
=
5
R
=
10
R
=
25
R
=
100
Delays
461
380
357
313
288
171Figure 8
The changing process of information consistency delays in single link network with 5, 10, 25, and 100 loops.As can be seen from Figure8 and Table 5, the more added loops to the single link network, the less obviously the information consistency delays of the whole network. Therefore, we conclude that LAPSNM algorithm also can solve the problem of information consistency of the whole network under OSPF protocol and it is superior to LAPSN algorithm and Dijkstra algorithm.


## 4.2.1. LAPSN Algorithm Test

Simulation parameters are as follows: packet size is 256 MB, link capacity is 1 Mbit/s, buffer queue type is Droptail, link type is Duplex-link, and buffer queue size is 1 GB. Routing nodes are 11–20 in single link network, the corresponding network delays are 11–20 ms, and movement delays of routing node are 1 ms. The information consistency delays of whole network are shown in Figure7.Figure 7
The relationship between routing nodes in single link network and information consistency delays.In Figure7, the information consistency delays of LAPSN algorithm are greater than that of Dijkstra algorithm. With the increase of routing nodes in single link network, the delays difference is greater and greater. Generally, LAPSN algorithm can solve the problem of information consistency of the whole network under OSPF protocol. But it is inferior to Dijkstra algorithm.


## 4.2.2. LAPSNM Algorithm Test

Simulation parameters are as follows: routing nodes are 20 in single link network, the corresponding network delays are 20 ms, buffer queue size is 5 GB, and the other simulation parameters are the same as Section4.2.1. We add 5, 10, 25, and 100 loops to single link network. The changing process of accumulation delays is shown in Figure 8, and the information consistency delays of whole network are shown in Table 5.Table 5
The comparison table of information consistency delays/ms.
Algorithm
LAPSN
Dijkstra
LAPSNM
R
=
5
R
=
10
R
=
25
R
=
100
Delays
461
380
357
313
288
171Figure 8
The changing process of information consistency delays in single link network with 5, 10, 25, and 100 loops.As can be seen from Figure8 and Table 5, the more added loops to the single link network, the less obviously the information consistency delays of the whole network. Therefore, we conclude that LAPSNM algorithm also can solve the problem of information consistency of the whole network under OSPF protocol and it is superior to LAPSN algorithm and Dijkstra algorithm.


## 5. Conclusions

In this paper, we give three definitions including ALA, LA, and OLA. Four theorems are proved including LAs, OLA, network path, and added loops. Three hypotheses are proposed including depth traversal method, off nodes method, and added loops method. In order to do further research on information consistency of the whole network under OSPF protocol, two LAP routing algorithms are designed. In Static Experiments section, the results reveal that LAPSN algorithm and LAPSNM algorithm have a good performance. In the Dynamic Experiments section, the results prove that LAPSN algorithm and LAPSNM algorithm can solve the problem of information consistency of the whole network under OSPF protocol and the performance of LAPSNM is superior to that of LAPSN algorithm and Dijkstra algorithm. In the next steps, we will study the stability of LAPSN algorithm and LAPSNM algorithm and propose a new algorithm for the complex networks.



---

*Source: 539793-2014-10-30.xml*