Chapter 3 Design of Routing Algorithm
The mathematical model of the routing algorithm is the chart theory model. As shown below:
Figure 7 Selection of network model routing process is to find the optimal path of the source node and the target node in the weighted non-map (or award map), select the next station router according to the best path. As shown in Figure 7, the best path to 0 nodes to 4 nodes is 0 → 2 → 3 → 4, then the next station router when the data packet sent to 4 nodes in 0 nodes is 2 Node, the remaining colony push. There are currently many mature routing algorithms, typical, such as Dijkstra algorithms, can easily calculate a shortest path of a vertex to the remaining vertices, the complexity of the process is O (N2), calculates a network model routing table , A total of N times algorithm is called, so complexity is O (N3). Another typical algorithm is a FLOYED algorithm, which can calculate the shortest path between the vertices in the figure, complexity O (N3). Details of the routing algorithm can be found in the reference [6] and [7]. However, with the development of computer science, emerging computational models have been widely used, especially intelligent calculations. In this paper, the routing algorithm is designed, and the FLOYED algorithm is enabled, so that the routing table is calculated simultaneously by the minimum path. In addition, an algorithm is discussed independently designed and the convergence of the algorithm is initially discussed. Finally, the performance of the two algorithms is analyzed according to the experimental data. §3.1 FLOYED Routing Algorithm Designing the FLOYED Algorithm Starting from the adjacency matrix of the figure, according to the order of 0, 1, 2, ..., N-1, each node k (0 <= k <= n-1, respectively, respectively As the intermediate point of the new consideration, the A (k-1) obtained by the K-1 operation (A (-1) is based on the adjacent matrix GA of the figure, and each pair of nodes I to j is obtained. Currently shortest path length A (k) [i] [j]. The calculation formula is: a (k) [i] [j] = min (a (k-1) [i] [j], a (k-1) [i] [k] a (k-1) [ K] [j]), (0 <= i <= n-1, 0 <= j <= n-1). When I nodes are source nodes, the J node is the target node, and when I nodes are adjacent to the K node, the K node is the next station router at the current shortest path in the shortest path. When K takes N-1 from 0, the matrix A (N-1) is the final result - the matrix of the shortest path, while tracking the optimal routing table in accordance with the above method.
The principle is as described above, the FLOYED routing algorithm is designed as follows:
Algorithm floyed-routCompute. ROUTNUM is the number of routers, NetArray [RoutNum] [ROUTNUM] is a matrix of storage network topology information, and Valarray [RoutNum] [ROUTNUM] is a matrix of network dissipation information. .from is the source router, ROUTTABLE [ROUTNUM] [2] is the routing table to be returned. Matrix [RoutNum] [ROUTNUM] is a matrix that stores the shortest distance of the source router to other routers. Begin bval = true; for i = 0 to routnum-1 do for j = 0 to routnum-1 do matrix [i] [j] = valarray [i] [j]; for i = 0 to routnum-1 do begin / / Routing Table initialized ROTTABLE [I] [0] = - 1; ROUTTABLE [I] [1] = - 1; End; While (TRUE) Begin fork = 0 to RoutNum-1 Do for i = 0 To Routnum-1 Do for J = 0 TO ROUTNUM-1 Do Begin IF (Matrix [i] [j]> = (Matrix [i] [k] matrix [k] [j])) begin // Currently shortest path length A ( K) [i] [j] matrix [i] [j] = matrix [i] [k] matrix [k] [j]; if (i == from && netray [i] [k] == 1) Begin // Calculate the current shortest length routing table IF (i! = K = j) Begin RoutTable [J] [0] = J; ROUTTABLE [J] [1] = K; END; END; End; // end of if end; // end of for for i = 0 to routnum-1 do bval = bval and (routTable [i] [0]! = - 1) and (routTable [i] [1]! = -1); if (bval) Break; Else Bval = true; end; // end of while returns RoutTable; END. FLOYED algorithm is a traditional algorithm based on the matrix theory of Figure.
