CN1710882A - Routing method of sectional interaction to goal node according to scale value based on optimized diameter network - Google Patents

Abstract

The routing method based on the degree value of the optimized diameter network to the segmented iteration of the destination node belongs to the Internet technology field, and is characterized in that: the source node is repeatedly iterated [log _d n] times according to the iterative formula of the optimized diameter network, and d is the degree of the node value, n is the number of network nodes, and a sequence of length d ^x (x=[log _d n]) is obtained, and then the sequence is divided into d equal parts, and the position of the destination node is judged according to the node attribution determination method, so as to press Node routing determines the node number to be forwarded in the next step and forwards the packet to the node. The node that receives the packet then iterates the above operations in the same steps according to the result of the previous sequence division, and performs corresponding packet forwarding until the packet is finally forwarded to the destination node. The invention can realize fast communication based on low-delay packet forwarding between arbitrary nodes on a large-scale P2P network.

Description

A Routing Method Based on Optimal Diameter Networks to Segment and Iterate Destination Nodes According to Degree Values

technical field

The invention belongs to the technical field of Internet.

Background technique

The performance of P2P network largely depends on the maximum transmission delay and routing method of the network. A packet refers to a data packet with a certain format; the maximum transmission delay of the network refers to the maximum time difference between sending a packet and receiving a packet between any two points on the network. Based on the following reasons, we believe that the control of the most human transmission delay is very important for the congestion control of the network and the quality of service of the network: First, some applications will not perform well due to the excessive end-to-end delay, or even cannot perform ; Secondly, the uncertain change of the maximum transmission delay makes it difficult for the network to support many interactive real-time applications; finally, the larger the maximum transmission delay value, the more difficult it is for the transport layer protocol to support high-bandwidth applications.

The network diameter directly determines the maximum transmission delay of the network, and the routing mechanism determines the packet forwarding efficiency. A well-performing P2P network should have a relatively small network diameter and an efficient routing mechanism. There are some better methods (such as Chord, Pastry, Tapestry) at present, but the common weakness of these methods is that the network diameter is not small enough, the packet forwarding efficiency is low, and one host needs to maintain more information about other hosts. This is not suitable for applications that require high indicators such as maximum transmission delay in a large-scale network environment, such as applications such as virus early warning, pudding data distribution, and virus signature download.

The optimal diameter network has a strict topological structure. We use graph theory to describe the structure. First, we need to define some graph theory terms used. A directed graph refers to a graph in which all edges are directed edges, using the symbol G=(V, E), V is a point set, and E is an edge set; if there is a directed edge between point u and point v (u , v), then point v and point u are called neighbor points; the order of graph G is defined as the number of points in graph G; the in-degree of point v refers to the number of edges in graph G that end at point v , denoted as d _G ^- (v); the out-degree of point u refers to the number of edges starting from point u in graph G, denoted as d _G ⁺ (v); the in-degree and out-degree of a point are commonly referred to as points degree; the diameter of a graph G is defined as the maximum distance between two vertices of the graph G, denoted as d(G); if the degree of all points of the graph G is d, the graph G is called a d-regular graph. The graphs we mention below all refer to directed graphs, and the points in the topology graph of the network are called nodes.

Because a directed edge can be uniquely determined by its two neighbor nodes, we construct the edge of the directed graph by constructing neighbor nodes. Let the graph G be a directed regular graph (n>0, d>1) with order n, degree d, and diameter k, denoted as G=(V, E), and the point set of graph G is: V={ 0, 1, 2, ..., n-1}, for any node i∈V, we define the following formula:

d×i+s+t (modn)(1≤s≤d, t∈[0,n-1]) (1) The number calculated by this formula is used as the node number of the neighbor node of node i. The total routing table constructed in this way has the characteristics of modulo n periodic regression (see Figure 1), and its diameter can reach (log _d n rounded up), this structure has a smaller network diameter than the other structures mentioned above and is very close to the theoretical minimum.

次转发后到达目的节点。按度值对目的节点分段迭代的路由法在具有较小直径的同时还具有较小的计算开销，其计算复杂度为

(见图5)，该方法可以满足大规模网络中许多对于传输时延要求苛刻的应用。Based on the above-mentioned optimized diameter network topology, the present invention designs a routing method for segmenting and iterating the destination node according to the degree value. The method can make the data along the forwarding in the correct direction of the destination node, thus ensuring that the data passes through the most

After forwarding, it reaches the destination node. The routing method that iterates the destination node segment by degree value has a smaller diameter and a smaller computational overhead, and its computational complexity is

(See FIG. 5 ), this method can satisfy many applications with strict requirements on transmission delay in large-scale networks.

Contents of the invention

The purpose of the present invention is to overcome the generally low data forwarding efficiency problem of existing methods, and provide a new heuristic routing mechanism for fast data transmission on a large-scale P2P network.

次，得到一个长度为d^x的序列(令 )，再对该序列进行d等分，然后根据节点归属判定方法判断出目的节点所处位置，从而决定下一步转发的节点号并将分组转发给该节点，收到该分组的节点再根据上次序列划分的结果迭代上述操作，并进行相应的分组转发，直到分组被最终转发到目的节点为止。The technical solution adopted by the present invention to solve its technical problems is: source node iterative formula (1)

times to get a sequence of length d ^x (let ), and then divide the sequence by d, and then judge the location of the destination node according to the node attribution determination method, so as to determine the node number to be forwarded in the next step and forward the packet to the node. The result of sequence division iterates the above operations and performs corresponding packet forwarding until the packet is finally forwarded to the destination node.

The present invention is characterized in that:

The method is implemented in the following steps on a peer-to-peer network of any scale:

符号表示向上取整，求出w_x，其中，s＝1，t∈[0，...n-1]任取；Step 1: Set: n is the number of nodes in the peer-to-peer network, w ₀ is the node number of the source node, j is the node number of the destination node, P is the forwarding packet, d is the degree of the node, starting from the source node w ₀ , after the modulo n of the following calculation results, the value of w _k+1 is obtained: w _k+1 =d×w _k +s+t, and then iterate x times according to the formula repeatedly, x is the diameter of the optimized diameter network,

symbol Indicates rounding up to obtain w _x , where s=1, t∈[0,...n-1] is optional;

Step 2: Start with the first item w _x , write the next item in sequence with the difference between two adjacent numbers being +1, and judge whether the value of the next item is equal to n-1, when the value of the item is equal to n-1 When the value of the next item becomes 0, then continue to write the next item according to the method described in step 2 and make the same judgment until the d ^x item is written, and the sequence a is obtained;

Step 3: Use the node number w ₀ of the source node to divide the array a by d, and obtain d sub-sequences as: a ₁ , a ₂ ,...a _d , and divide the d neighbor nodes of the source node w ₀ according to Node numbers from small to large are recorded as: v ₁ , v ₂ , ... v _d ;

Step 4: Use the following node ownership determination method to determine the interval where the sequence number j of the destination node is located:

Suppose: the first item of the sub-column a _i is p (1≤i≤d), the last item of a _i is q, the length of the current sub-column to be divided is h, d is the degree of the node, n is the number of nodes, the kth h is equal to d ^xk during the d-time operation, but: $q=p+(\frac{h}{d}-1);$

When p>g, if j≥p or j≤q, then j∈a _i ;

When p<q, if p≤j≤q, then j∈a _i ;

Step 5: If the sequence number j of the destination node belongs to the sub-sequence a _i , then the source node w ₀ forwards the packet P and the sequence a _i to the neighbor node v _i corresponding to the subscript i: if the sequence number j of the destination node is in multiple sub-sequences all appear in the column, choose a sub-column a _k from it, 1<k<d, and forward the packet P and the sequence a _k to the neighbor node v k corresponding to the subscript _k ;

Step 6: The node that received the grouping described in step 5 then performs the same operation on the sequence of the destination node with the received sequence number j according to step 3-step 5 according to the division result of step 3 until the group P is received The node of is the destination node j.

的网络直径和复杂度，Pastry方法实现了log_b n的网络直径，CAN构造的网络直径可以达到1/2dn^1/d，而本路由方法的网络直径和计算复杂度均仅为 这要小于其他几种方法，从而解决了传统方法中数据转发效率低的问题。目前清华大学已经将该项研究成果运用在“P2P蠕虫防御系统”中，是该系统的重要组成部分。The routing method proposed by the present invention based on the optimized diameter network based on the segmented iteration of the destination node according to the degree value solves the problem of low packet forwarding efficiency caused by the limitation of the network diameter in the existing method, and can satisfy a large number of users with low time requirements. The application of delayed forwarding requirements provides a new technical method for low-latency packet forwarding on the P2P network that is close to the theoretical minimum value, and can realize fast communication between any nodes on a large-scale P2P network, as shown in Figure 5 Out of the performance comparison between this routing method and several classic routing methods Chord, Pastry and CAN, the Chord method achieves

The network diameter and complexity of the network, the Pastry method realizes the network diameter of log _b n, the network diameter of the CAN structure can reach 1/2dn ^1/d , and the network diameter and computational complexity of the routing method are only This is smaller than several other methods, thereby solving the problem of low data forwarding efficiency in traditional methods. At present, Tsinghua University has applied this research achievement in the "P2P Worm Defense System", which is an important part of the system.

Description of drawings

Figure 1. Schematic diagram of the principle of optimizing the Diameter network: a. The neighbor table of the Optimizing Diameter network; b. The routing tree of nodes 4 and 13;

Fig. 2. The flow chart of the routing method based on the degree value of the optimized diameter network for the segmented iteration of the destination node;

Figure 3. An example diagram of the application of the routing method based on the degree value of the optimized diameter network for the segmented iteration of the destination node;

Fig. 4. An example diagram of the specific implementation method of the routing method for destination node segmentation iteration in the "P2P worm defense system" according to the degree value: d=2, s=1, t=2, n=14, w ₀ =4 , j=5:

Figure 5. Schematic comparison of different methods.

Detailed ways

Step 1. Note: the node number of the source node is w ₀ , the node number of the destination node is j, the forwarding packet is P, the degree of the node is d, let i in the formula (1) be w _k , according to the formula (1) We can get formula (2):

w _k+1 ＝d×w _k +s+t (mod n)(s=1, t∈[0,n-1]) (2)

Starting from the source node w ₀ , iteratively calculate the formula x times ( ), find out w _x ;

Step 2. Take w _x as the first item of the sequence, write the arithmetic sequence whose length is d ^x and the difference between two adjacent items is 1, and modulo n for each item, finally we get the sequence a.

In fact, this step can also be operated as follows: starting from the first item w _x , write each item of the sequence sequentially with the difference between two adjacent numbers being 1, and judge whether the item is equal to n-1, when it is equal to n- When 1, the next element becomes 0, and then continue to write the next item in sequence and make the same judgment until d ^x elements are written;

Step 3. The node w ₀ divides the array a by d (because the length of a is d ^x , so the d equal division operation can always be performed, and the length of each divided sub-column is d ^x-1 ), divide the array a The d sub-columns obtained after d equal division are recorded as: a _l , a ₂ , ... a _d ; and the d neighbor nodes of w ₀ are recorded as: v ₁ , v ₂ , . ..v _d ;

Step 4. Use the node belonging determination method in step 6 to determine the interval where the number j is located. If j belongs to the sub-sequence a _i (1≤i≤d), then the node w ₀ forwards the packet P and the sequence ai to the subscript phase The corresponding neighbor node v _i ; if the number j appears in multiple sub-columns, choose a sub-column a _k (1≤k≤d) from it, and forward the packet P and the sequence a _k to the subscript relative The corresponding neighbor node v _k ;

Step 5. The node that received the packet P performs the same operations in steps 3 and 4 on the sequence that the received destination node j belongs to according to the result of the last division, and iterates the above operations repeatedly until the node that receives the packet P is the destination node j;

)，则：q＝p+(h/d-1)，那么：Step 6. Node ownership determination method: set the first item of the sub-column a _i to be p, the last item of a _i is q, h is the length of the sub-column to be divided, d is the degree of the node, and n is the number of nodes. h is equal to d ^xk (wherein

), then: q=p+(h/d-1), then:

(1) When p>q: if j≥p or j≤q, then j∈a _i

(2) When P<q: if p≤j≤q, then j∈a _i

That is to say, the destination node j belongs to the sub-column a _i (1≤i≤d) in the above two cases.

The hardware platform applicable to this routing method is a peer-to-peer network of any scale. Fig. 2 is a program flow chart of the routing method for the segmented iteration of the destination node according to the degree value, and Fig. 4 is a route for the segmented iteration of the destination node according to the degree value The specific implementation example of the method in "P2P worm defense system", we use d=3, 1≤s≤d, t=6, n=27 as parameters, construct a network topology with the periodic regression method, and its diameter is 3( See Figure 3). Assuming that node 8 in the "P2P worm defense system" wants to send packet P to node 17,

Routing is performed as follows:

(1) Take node 8 as the starting point to iteratively calculate the formula (2) (d=3, t=6, n=27, w ₀ =8), iterate 3 times in total, and find that w ₃ is equal to 10;

(2) With 10 as the first item, write an arithmetic sequence with a length of 27 and a difference of 1 between two adjacent items, and modulo 27 for each item, we get the sequence a:

a: 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 0 1 2 7 6 34;

(3) Node 8 divides sequence a into three equal parts, and obtains the following three sub-sequences:

a ₁ : 10 11 12 13 14 15 16 17 18

_a2 : 19 20 21 22 23 24 25 26 0

a ₃ : 1 2 3 4 5 6 7 8 9

The three neighbor nodes of node 8 are: 4, 5, 6, which are recorded as v ₁ , v ₂ , v ₃ respectively;

(4) Node 8 judges that destination node 17 belongs to sub-column a ₁ , and accordingly, node 8 sends packet P and sub-column a ₁ to its neighbor node v ₁ , namely node 4;

(5) After node 4 receives the packet P and the sequence a ₁ , set a=a ₁ , and then divide the sequence a into 3 equal parts to obtain the following 3 sub-sequences:

a ₁ : 10 11 12

a ₂ : 13 14 15

a ₃ : 16 17 18

The three neighbor nodes of node 4 are: 19, 20, 21, which are recorded as v ₁ , v ₂ , v ₃ respectively;

(6) Node 4 judges that destination node 17 belongs to sub-column a ₃ , accordingly, node 4 sends packet P and sub-column a ₃ to its neighbor node v ₃ , namely node 21;

(7) After node 21 receives the packet P and the sub-sequence a ₃ , set a=a ₃ , and then divide the sequence a into 3 equal parts to obtain 3 sub-sequences:

a ₁ : 16

_a2 :17

a ₃ : 18

The three neighbor nodes of node 21 are: 16, 17, 18, which are recorded as v ₁ , v ₂ , v ₃ respectively;

(8) The node 21 judges that the destination node 17 belongs to the sub-column a ₂ . Based on this, the node 21 sends the packet P to its neighbor node v ₂ , namely the node 17, which is the destination node.

So far, the routing process ends. The entire forwarding path is: 8→4→21→17.

It can be seen that the present invention has achieved the intended purpose.

Claims (1)

1. based on the routing method of optimizing diameter network by degree value to destination node subsection iteration, it is characterized in that, described method is realized by following steps successively on the peer-to-peer network of arbitrary scale: Step 1: Set: n is the number of nodes in the peer-to-peer network, w ₀ is the node number of the source node, j is the node number of the destination node, P is the forwarding packet, d is the degree of the node, starting from the source node w ₀ , after the modulo n of the following calculation results, the value of w _k+1 is obtained: w _k+1 =d×w _k +s+t, and then iterate x times according to the formula repeatedly, x is the diameter of the optimized diameter network, symbol

Indicates rounding up to obtain w _x , where s=1, t∈[0,...n-1] is optional; Step 2: Start with the first item w _x , write the next item in sequence with the difference between two adjacent numbers being +1, and judge whether the value of the next item is equal to n-1, when the value of the item is equal to n-1 When the value of the next item becomes 0, then continue to write the next item according to the method described in step 2 and make the same judgment until the d ^x item is written, and the sequence a is obtained; Step 3: Use the node number w ₀ of the source node to divide the array a by d, and obtain d sub-sequences as: a ₁ , a ₂ ,...a _d , and divide the d neighbor nodes of the source node w ₀ according to Node numbers from small to large are recorded as: v ₁ , v ₂ , ... v _d ; Step 4: Use the following node ownership determination method to determine the interval where the sequence number j of the destination node is located: Suppose: the first item of the sub-column a _i is p (1≤i≤d), the last item of a _i is q, the length of the current sub-column to be divided is h, d is the degree of the node, n is the number of nodes, the kth h is equal to d ^xk during the d-time operation, but: $q=p+(\frac{h}{d}-1);$ When p>q, if j≥p or j≤q, then j∈a _i ; When p<q, if p≤j≤q, then j∈a _i ; Step 5: If the sequence number j of the destination node belongs to the sub-sequence a _i , then the source node w ₀ forwards the packet P and the sequence a _i to the neighbor node v _i corresponding to the subscript i; all appear in the column, choose a sub-column a _k from it, 1≤k≤d, and forward the packet P and the sequence a _k to the neighbor node v _k corresponding to the subscript k; Step 6: The node that received the grouping described in step 5 then performs the same operation on the sequence of the destination node with the received sequence number j according to step 3-step 5 according to the division result of step 3 until the group P is received The node of is the destination node j.

Images