Research of the Adaptive Routing Algorithm Based on State Perception in a Reconfigurable Network

To improve the effectiveness and accuracy of the message transmission in a reconfigurable network efficiently, this paper proposes a reconfigurable fault tolerant model and a mechanism based on the minimum cost path in a reconfigurable network, it also proposes an adaptive routing algorithm based on node state perception when the network link interrupts, at last the theoretical analysis and simulation experiment is conducted, the result shows that the algorithm has the superiority in the aspects of the RFTNM successful operation rate, the physical link utilization, the network transmission delay and the average packet arrival rate of success, it is more suitable for mobile social network


INTRODUCTION
With the rapid development of the traditional network, Internet users are becoming increasingly demanding as the Internet applications and their performance. Nowadays, the Internet with IPv4 as its core protocol is facing severe challenges and other issues, such as poor routing scalability, dissatisfactory service quality, inefficient mobile networks and security risks, etc. Moreover, with the popularization and application of sensor technologies, smart phones, tablet computers and other mobile devices, more and more people are keen to access the Internet through a variety of access methods on mobile terminals. Therefore, the next generation network, reconfigurable network as a typical example, has been emerged recently, including mobile social networks, MSN, and so on. [1]. Reconfigurable networks based on the six degrees of separation founded by Professor Stanley Milgram, Harvard University [2], can make social networking expanded through mobile devices to maintain people's relationships in a virtual cyberspace.
Routing is an very important technology for any networking. Traditional network routing algorithms have been designed primarily on the hop count of packet data between nodes, delay, network link states and other factors. However, limited mobile nodes and intermittent connections are not taken into account. Furthermore, in a reconfigurable network, users who carry mobile terminals have a particular social relationship and the regular socializing, which are the essential features distinct from other mobile networks. A terrible issue is that how to improve the effectiveness of message transmissions by using features of social networks and user relationships [3].

II.
RELATED RESEARCHES Current researches for reconfigurable networks, in academia and industry, have focused on community detection, routing algorithms, privacy and security, middleware design, application development and other related areas. In the study of routing algorithms, Vahdat and Becker proposed Epidemic routing [4], also known as infectious routing, that means the data transmission between nodes depends on the store and forward mechanism. Although this algorithm has great advantages in the transmission delay and the successful transmission rate of data, plenty of network bandwidth and memory resources have been used up. Lindgren et al. raised a probabilistic routing protocol PROPHET [5] after considering the factor of limited node resources. The nodes can collect meet information in that protocol and update the transmission probability of data of success with other nodes when they meet. This algorithm is more applicable to the nodes in a network without enough memory. Context-Aware Routing (CAR) [6], integrating the simultaneous and asynchronous transmission, can predict the next state based on the historical information of the meets. Daly and Haahr proposed a routing algorithm SimBet by using social network analysis [7], and its theoretical basis is the small-world properties and the node centrality theory proposed by Freeman. Encounter between nodes can exchange the node centrality and similarity of those nodes.
The unpredictable movement direction of the mobile terminals will cause the network link failure so that a variety of application services interrupt. It not only goes for a poor user experience, but also brings the economic losses to service providers. To reduce the average intensity of all the nodes on the mapped path, a logical tolerant network has been constructed by a heuristic algorithm in literature [8]. To pre-consider the backup link, the event of a link failure in the primary path would make data migrate to the backup link in order to prevent service interruptions in literature [9]. Some of these studies considered how to optimize network resources only, and the others solved the problem of link interruptions simply by introducing a backup link, which made the cost too high. To this end, this paper proposes a fault-tolerant model and a mechanism based on the least-cost path in a reconfigurable network, and presents an adaptive routing algorithm based on node state perception while some network link is interrupted. In this method, the reliability of the reconfigurable network International Conference on Civil, Materials and Environmental Sciences (CMES 2015) can be ensured through the minimal cost of routing reconstruction.

III. RECONFIGURABLE FAULT-TOLERANT NETWORK MODEL (RFTNM)
Undirected graph G p = (N p , E p , C p ) represents the physical network, where N p and E p denote the set of physical nodes and the set of links respectively, C p represents the carrying capacity of services that the physical network can provide.
Undirected graph G t = (N t , E t , R t ), represents the demand of RFTNM construction, where N t is the set of virtual nodes that a user requests in RFTNM, E t is the set of virtual links, both of them are a subset of N p and E p , respectively, and, R t represents carrying requirements of services in a RFTNM construction request.
The Construction of RFTNM can be described as a mapping from G t to a subset of G p , which satisfies the constraints in G t , and can be expressed by G s : M: G t →G s , G s = (N s , E s , C s ), wherein N N , E E , C s indicates the carrying capacity of services that the RFTNM construction can provide. Before the construction algorithm, the following concepts will be presented first.

A. Influence of node
In network G p , assuming that the degree of node ni is di, vector NI = (1/d1, 1/d2, ..., 1/dn) is the influence vector of node ni corresponding to adjacent nodes, named Influence of node [10].

B. Resource criticality
represents the resource criticality of x, α and β are the adjustment factors, and α + β = 1. Ψ (x) says that the greater its value is, the more impact the fault of resource x has on the network.

C. Cost function of RFTNM Construction
where c(es) and c(ns) respectively represent the initial costs of nodes and the physical links occupied by RFTNM construction. The more serious the node criticality is, the higher cost the RFTNM construction can be by its resources.
The needs of RFTNM construction can be divided into two adjacent nodes and the basic needs of the link bandwidth between them, represented with (s, t, d), where s and t represents two adjacent nodes, and d indicates that the requirements of the link bandwidth. Triple (s, t, d) is known as meta-demands of RFTNM construction.
RFTNM construction is actually to determine the path connected s and t in G p , which denotes as P s, t , satisfied e P ∈ s, t , b(e)≥de, where b(e) indicates the link bandwidth. For meta-demands of each RFTNM construction, maybe, there is more than one candidate path satisfied the conditions, hence the built path with the minimum cost should be chosen as the best one.
The minimum cost path connected nodes s and t is available by weights matrix W(G p ) of G p and the shortest path algorithm. The process of the Minimum Cost Path Algorithm (short as TMCPA) is as follows (Input: G p , G r , and Output: G s ): (1) Initialization: G s ←NULL; (2) Decomposition the demands of RFTNM construction G r : for each built meta-demand (s, t, d), the steps (3) to (5)  , the minimum cost path P , between s and t can be found through the shortest path algorithm, if there is no such path, G s ←NULL, and go to (6); (5) G G P , , update the carrying capacity of network services on the path P , ; (6) If G s !=NULL, mapping result G s is returned; otherwise it is impossible to build RFTNM.
Steps (3) to (5) in the above algorithm calculate the shortest path between s and t, and choose the minimum cost path P , .
Step (4) updates the weight matrix and obtains the shortest path between s, t according to the updating weights matrix.
Step (5)  In RFTNM, the node failure can be recorded in a fault matrix, in which the vertical axis represents the node input ports and the horizontal axis represents the node output ports. Each axis has four directions, represented as N, W, S and E. Every element in the matrix is represented by 0 or 1 corresponding to the faults in the channel between the input and output ports. 1 indicates that the corresponding channel is good, 0 indicates that the corresponding channel is faulty.
Port priority policy (with PriorityAssign function): Assuming that there are four ports to select for forwarding after each packet enters one node. The port priority is identified as P1> P2> P3> P4. The packet input port's priority is the lowest level P4. In the other three ports, the port direction closer to the port of destination node, whose priority is the highest level P1. The node port direction perpendicular to the one which closer to the destination node, its priority is the junior level P2. If the ports with P1 and P2 are only one of each, the priority of the remaining port is level P3.
The steps of AFTRA-NSP algorithm is as follows: (1) Obtain the port priority of the local node. When the packet enters an local node, offset Δx and Δy to the destination node are calculated first, and then the port priority of this local node is determined by considering the direction of the input port (InputDir): {P1, P2, P3, P4} = PriorityAssign (InputDir, Δx , Δy). (1) (2) Obtain the port priority of the adjacent nodes corresponding to level P1. With forwarding nodes that first comes from the nodes corresponding to the ports with level P1, offset Δx N1 and Δy N1 of the packet in the adjacent nodes are available by decrement one to Δx and Δy, respectively, and their input directions are the opposite directions of P1. The port priority of the adjacent nodes can be calculated by function PriorityAssign, in which P N represents the port of the adjacent nodes with level P r , and P N represents the port of the adjacent nodes with level P k corresponding to the port with level P k of the local node.
(3) Select a path within the fault matrix. According to the port combinations of P1 P N , P1 P N , P1 P N , the fault matrix is checked to determine if the current combination of the selected paths is available or not. The formula is given for determination: availability f f N , where i, j, m, n {N, W, S, E}, ∈ f ij and f N are the elements from the fault matrix of the local node and from the fault matrix of the adjacent splice nodes, respectively, i is the input direction, j is the direction of P1, m is the direction P1 , n is the direction of selected port P N .
If availability is 1, port P1 is supposed to forward packets. Otherwise, all the path combinations of P1 are not available, the process proceed to step 4.
(4) Select and determine the local node ports and the corresponding adjacent nodes by downgrading. It determines by repeating steps (2) and (3) until meeting the lowest level P4.
(5) Return to the upper level node after selecting the input port P4. If all the port combinations are failed, the input port is enabled and the process returns to the upper level node.

V. RESULTS
First, we perform the algorithm complexity analysis. In TMCPA algorithm, it is assumed that G p has n nodes and G r has m nodes, so the worst time complexity of the requirement decomposition of RFTNM construction is O(m 2 ). Again, assuming that meta-demands are decomposed with k, for each meta-demand, the worst time complexity of updating the weight matrix and the shortest path algorithm is O(n 2 ), as well. So the worst time complexity of TMCPA algorithm is O(m 2 +kn 2 ). In our algorithm, the storage consumed is mainly to store meta-demands and the shortest path, therefore the space complexity is O(k+n).
In check to see the proposed algorithm, the NS-2 simulation tools are used for testing. They can randomly generate a physical network topology, in which the connection probability of the nodes is 0.02, the bandwidth resources evenly distribute between 50 and 100, and the packet size is 10 bits. The arrival process of the RFTNM construction request follows a Poisson process for 100 time units and the intensity of λ r =5. And, the process of link failure occurred obeys a Poisson process for the intensity of λ f . The average recovery time for link failure is 400 time units. Additionally, the existence time for each RFTNM obeys an exponential distribution for θ = 400.
(1) Compare TMCPA with Basic VNA, BACA algorithm in the successful operation rate of RFTNM and the physical link utilization.
Successful operation rate of RFTNM refers to a percentage of the successful number of RFTNM built and operated and the number of requests built. That can reflect the validity and the fault-tolerance of these construction methods. It says the higher the successful operation rate is, the more efficient and fault-tolerance the construction methods are. Fig. 1 shows the simulation result of the successful rate for different values of λ λ and the average operation time for 5000 time units.
From Fig. 1, we can see that when λ λ is small, the probability of a link failure is much less than the request arrival rate, moreover, the successful operation rate of all the three algorithms is high. As λ λ increases, the link-failure probability increases as well and all these three successful operation rates decline in a way. In spite of considering the maximum load of nodes and links, the Basic VNA processes routing only with the shortest path algorithm. It is prone to get bottlenecks to make the successful operation rate lower than the others. On the other hand, considering the load balancing of the entire network during resource assignments, BACA can take advantage of the network resources. Nonetheless, it does not consider the urgency of resources, therefore RFTNM are much affected when a fault occurs. Its successful operation rate is on the middle. To make up for the shortcomings of the first two algorithms, the successful operation rate of TMCPA is on the highest.
The average utilization of the physical link is a ratio of all the link bandwidth occupied by RFTNM construction and all the bandwidth of link resources in the physical network, which can reflect the utilization of the network resources. Fig. 2 is the result of the average utilization of links for the simulation operation time with 5000 time units. It shows that the link utilization of those algorithms has little difference when the rate of the link failure is lower. However, with increasing at the rate of link failures, the link utilization of Basic VNA and BACA decreases greatly. On the contrary, that of TMCPA has reduced inconspicuously since it has a reconfigurable capability and takes the urgency of the resources into account.  (2) Compare AFTRA-NSP with XY, FFBR algorithms on network delay and the average arrival rate of packets of success. Fig. 3 is the average transmission delay of XY, FFBR and AFTRA-NSP under link failures. When a fault present, XY routing has the highest transmission delay, and the transmission delays of AFTRA-NSP and FFBR increased slowly because they are adaptive. AFTRA-NSP, however, solves the problem that FFBR forwards packets blindly. It can still find the optimal routing ports based on the node state when a link failure appears. So the smallest changes are in its transmission delay. Fig. 4 is the average packet arrival rate of success of XY, FFBR and AFTRA-NSP in discrete situations. In a failure-free network, each algorithm can guarantee 100% packet arrival rate. But, with increasing at the rate of link failures, the arrival rate of XY decreases in the maximum, which of FFBR follows XY. And AFTRA-NSP is of the highest rate because it is capable of perceiving the node state, determining priorities, and then selecting the best route in order to ensure the reliability of the data transmission.
VI. CONCLUSION This paper firstly analyzes the latest progress and research status of reconfigurable network, secondly propose a fault-tolerant network model and a mechanism based on the least-cost path in reconfigurable network. Then the adaptive algorithm of fault-tolerant routing has been presented based on node state perception when the network link is interrupted, which can improve the reliability of reconfigurable network by minimizing the reconstruction cost. And finally, we have made the performance of the algorithm including the theoretical analysis and experimental verification. The results show that this method is superior to other algorithms in the successful construction rate, the average utilization of physical links, network transmission delay and successful arrival rate of packets. The next step in the research is primarily concentrated on the recovery mechanism and load balancing with multi-node failure.