CN103139081B - Distributed hashtable routing table update method and node - Google Patents
Distributed hashtable routing table update method and node Download PDFInfo
- Publication number
- CN103139081B CN103139081B CN201110384912.XA CN201110384912A CN103139081B CN 103139081 B CN103139081 B CN 103139081B CN 201110384912 A CN201110384912 A CN 201110384912A CN 103139081 B CN103139081 B CN 103139081B
- Authority
- CN
- China
- Prior art keywords
- routing table
- node
- cryptographic hash
- overlay network
- update
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L45/00—Routing or path finding of packets in data switching networks
- H04L45/02—Topology update or discovery
- H04L45/021—Ensuring consistency of routing table updates, e.g. by using epoch numbers
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
- Computer And Data Communications (AREA)
Abstract
The invention discloses a kind of distributed hashtable routing table update method and node, wherein, methods described includes：When overlay network interior joint detects overlay network and adjusted, routing table update is carried out, and routing table cryptographic Hash notifies other nodes of overlay network after triggering routing table update cause information and updating；Other nodes carry out local routing table renewal according to triggering routing table update cause information, and calculate the cryptographic Hash of routing table after local update, exchanged it is determined that carrying out routing table when calculated cryptographic Hash and inconsistent received routing table cryptographic Hash, between the node with sending triggering routing table update cause information；The node of other nodes and transmission triggering routing table update cause information contrasts the difference between exchanged routing table, to being detected at overlay network difference, when it is determined that needing amendment local routing table, carries out routing table amendment.The present invention can eliminate the nonsynchronous phenomenon of routing table between node automatically, so as to avoid the routing table diffusion of mistake, overlay network routing performance will not be caused to decline.
Description
Technical field
The present invention relates to distributed hashtable (DHT, Distributed Hash Table) technology, more particularly to a kind of base
In the distributed hashtable routing table update method and node of DHT technologies.
Background technology
Distributed hashtable (DHT, Distributed Hash Table) technology be one kind be widely used in equity (P2P,
Peer to Peer) distributed resource in network searches technology.DHT overlay networks are each nodes according to certain topological structure group
Into the overlay network being located on IP network, the route of its storage for being responsible for a part of resource and message etc..DHT is handed in file
Change, Distributed Calculation, service it is shared in terms of fully shown its powerful technical advantage.
In DHT overlay networks, the keyword of each node and resource is respectively provided with unique mark, and wherein node identification is pair
The mapping of node address, Resource Key mark is the mapping to the Resource Key.When identification length is m bits, mark
Span be [0,2^m-1].The spacing-visible being made up of these marks is an end to end DHT ring.Common DHT
Algorithm has Chord, Pastry, Kademlia etc., and these algorithms define the division methods that each node in DHT rings is responsible for interval,
And the method for routing of P2P message etc..By taking Chord algorithms as an example, each overlay network node is responsible for storage keyword identification and is located at this
Resource between node identification and precursor node identification, the hop count for sending P2P message is generally O (log N), and wherein N is
The number of overlay network interior joint.
With the demonstration effect of P2P technologies, DHT technologies are also introduced into other technical systems, for building high property
Energy, expansible distributed data base system etc., the Dynamo systems of such as Amazon.
In these distributed data base systems, performance of the node (peer-to-peer) in terms of calculating, storing is preferable, and
The addition of each node and exit it is carefully controlled, overlay network adjust infrequently.But these systems are to the router efficiency of transmission P2P message
It is required that higher, it is desirable to which P2P message reaches destination node in fixed hop count.Therefore such system suitable uses single-hop DHT algorithms, i.e.,
Each node preserves full routing table, grasps the situation that all nodes of overlay network are responsible for interval, and the P2P message of transmission only needs a jump
Reach destination node.However, according to single-hop DHT, when overlay network node is more, then routing table is larger.
Under heterogeneous network environment, single-hop DHT can also be further combined with segmentation mark, dummy node even load equilibrium side
Method, i.e., each node is responsible for segmentation or the dummy node number being consistent with self-ability, to undertake suitable load.So, each section
In point routing table in addition to physical node information is stored, storage segmentation mark or the mapping between dummy node and physical node is also needed to close
System, routing table is more huge.
Using single-hop DHT, it is desirable in overlay network the routing table of each node storage it is synchronous with the holding of overlay network actual conditions or
Basic synchronization.
Fig. 1 is the schematic diagram of DHT rings, as shown in figure 1, overlay network 101 be undertake different role by all kinds of peer-to-peer (
Referred to as overlay network node) composition a logical network；Peer-to-peer overlay network node 102 in overlay network is basic in overlay network
Part, is that the overlay network node of storage and transmission service can be provided for other overlay network nodes in same overlay network.It is right
Any overlay network node in DHT rings, in the presence of a precursor node and a descendant node.
Fig. 2 is the flow chart that node adds overlay network, as shown in Fig. 2 node, which adds overlay network, specifically includes following steps：
Step 201, add node and acquire own node mark；Adding node can be by searching own configuration information
Mode or the mode such as ask to obtain itself node identification to server；
Step 202, add node and send Attach Request message to its known overlay network any node；
Step 203, the node for receiving Attach Request message forwards messages to the responsible node for adding node；
Step 204 is to step 205, and responsible node sends attachment response message, and the attachment response message is forwarded to addition
Node；
Step 206, responsible node sends in routing update request message, the routing update request message to addition node and contained
There is the current overlay network full routing table that itself is stored；
Step 207, add node and initialize itself routing table by routing update request message, and road is replied to responsible node
By updating response；
Step 208, add node and send addition overlay network request message to responsible node；
Step 209, responsible node adds overlay network response message to node reverts back is added, so far, adds node and is responsible for
Node completes to consult, and determines responsible node to the interval for adding node migrating data；
Step 210, responsible node adds node and completes data constantly to node transmission data storage request message is added
Response message is replied after storage；The process continues to that data migration process is completed；
Step 211, the preparation that node has completed the interval partial data of adapter migration is now added, its responsible node is to superposition
Net all other node and send routing update request message；The routing update request message can be using shapes such as broadcast or hierarchical broadcasts
Formula is sent；
Step 212, each node of overlay network updates the routing table that is locally stored by routing update request message, and to responsible section
Point replys routing update response message.
According to segmentation mark or dummy node even load equalization algorithm, newly added node may be needed from multiple in net section
DHT intervals are responsible in point adapter, therefore adding node need to interact with multiple in net node, and above-mentioned steps 208 are performed respectively to step
212。
If the request close at the time of of two or more nodes adds overlay network, because the Data Migration time is longer, add
Process may be present overlapping.Fig. 3 is the flow chart that two nodes add overlay network in similar time, as shown in figure 3, this example is assumed
Overlay network only includes node A and node B in the existing node of net, and respectively newly added node C and node D is responsible node.Fig. 3
Shown flow specifically includes following steps：
Step 301, addition node C has completed the attaching process to responsible node A；
Step 302, responsible node A sends in routing update request message, the routing update request message to node C and included
Full routing table, routing table includes node A, B relevant information；
Step 303, node C initializes local routing table according to request, and sends routing update response message to node A；
Step 304, node C sends to node A and adds overlay network request message；
Step 305, node A sends to node C and adds overlay network response message, so far, adds node and responsible node is complete
Into negotiation, determine responsible node to the data interval for adding node migration；
Step 306, node A sends data to node C, carries out Data Migration；
Step 307, now add node C and completed the preparation as overlay network member, responsible node A is other to overlay network
All nodes (only node B at present) send routing update request message, to notify node C to add overlay network；
Step 308, node B updates local routing table, and sends routing update response message to node A；
Step 309, later than node C, close at the time of, add node D and completed attachment to responsible node B
Journey；
Step 310, responsible node B sends in routing update request message, the routing update request message to node D and included
Full routing table, routing table includes node A, B relevant information；
Step 311, node D initializes local routing table according to routing update request message, and sends route more to node B
New response message；
Step 312, node D sends to node B and adds overlay network request message；
Step 313, node B sends to node D and adds overlay network response message, so far, adds node and responsible node is complete
Into negotiation, determine responsible node to the data interval for adding node migration；
Step 314, node B sends data to node D, carries out Data Migration；
Step 315, now add node D and completed the preparation as overlay network member, responsible node B is sent to node A
Routing update request message, notifies node D to add overlay network；
Step 316, node A updates local routing table, and sends routing update response message to node B；
Step 317, this front nodal point B has known that node C adds the information of overlay network, therefore responsible node B sends road to node C
By renewal request message, node D is notified to add overlay network；
Step 318, node C updates local routing table, and sends routing update response message to node B.
After the completion of above step, newly added node D when it does not turn into overlay network member because will not receive on adding
Node C routing update request message, its routing table is asynchronous with overlay network actual conditions.
P2P message can be sent to the destination node of mistake by the nonsynchronous node of routing table, and the node for receiving P2P message is looked into
Ask the routing table being locally stored and obtain the next-hop of the destination address, and the P2P message is forwarded.So, P2P message is most
Correct destination node is still reached eventually, but adds hop count.Subsequently, if the nonsynchronous node of routing table is responsible for new node
Addition, its preserve routing table can be delivered to newly added node.Therefore incorrect routing table can spread, and cause overlay network
Can constantly it decline.
The content of the invention
In view of this, it is a primary object of the present invention to provide a kind of distributed hashtable routing table update method and section
Point, can eliminate the nonsynchronous phenomenon of routing table between node, so as to avoid the routing table diffusion of mistake, it is to avoid overlay network routing performance
Decline.
To reach above-mentioned purpose, the technical proposal of the invention is realized in this way：
A kind of distributed hashtable routing table update method, including：
When overlay network interior joint detects the overlay network and adjusted, routing table update is carried out, and routing table will be triggered
Routing table cryptographic Hash notifies other nodes of the overlay network after updating cause information and updating.
Preferably, routing table cryptographic Hash notifies its of the overlay network after triggering routing table update cause information and update
After his node, methods described also includes：
Other described nodes carry out local routing table renewal according to the triggering routing table update cause information, and calculate this
The cryptographic Hash of routing table after ground updates, it is determined that when calculated cryptographic Hash and inconsistent received routing table cryptographic Hash, with hair
Send progress routing table exchange between the node of triggering routing table update cause information；
The node of other described nodes and transmission triggering routing table update cause information is according to the route exchanged
Table determine the need for amendment local routing table, it is necessary to when carry out routing table amendment.
Preferably, the node of other described nodes and transmission triggering routing table update cause information is according to being exchanged
Routing table determine the need for amendment local routing table, it is necessary to when carry out routing table amendment, be：
Basis is obtained the node of other described nodes and transmission triggering routing table update cause information from other side respectively
The routing table taken contrast with the difference between itself routing table, the node for causing routing table difference is detected, according to spy
Result is surveyed when it is determined that needing itself self-modified routing table, local routing table amendment is carried out.
Preferably, the overlay network is adjusted, and is：New node adds the overlay network and/or to have node to exit described
Overlay network.
Preferably, the triggering routing table update cause information includes at least one of following information：
New node adds the overlay network, node and exits the overlay network, node and be responsible for interval change；
The routing table cryptographic Hash is each Hash for routeing table segmenting in routing table cryptographic Hash or node complete in node
Value.
Preferably, methods described also includes：
For routing table or routing table subsection setup counter；
Other described nodes determine that calculate cryptographic Hash differs with received routing table or route table segmenting cryptographic Hash
During cause, the counter is added one；When determining that the count value of the counter reaches given threshold, triggering route is sent with described
Table carries out routing table exchange between updating the node of cause information.
Preferably, when the routing table cryptographic Hash is the cryptographic Hash of each route table segmenting in node, methods described also includes：
Other described nodes carry out local routing table renewal according to the triggering routing table update cause information, it is determined that updating
When the cryptographic Hash of certain route table segmenting of the cryptographic Hash of certain route table segmenting with being received is inconsistent afterwards, triggering road is sent with described
Inconsistent routing table segment exchange is only carried out between the node of table renewal cause information.
A kind of overlay network node, including detection unit, updating block and notification unit；Wherein：
Detection unit, for detecting whether the overlay network adjusts, triggers updating block during generation；
Updating block, for carrying out routing table update；
Notification unit, for routing table cryptographic Hash after triggering routing table update cause information and renewal to be notified into the superposition
Other nodes of net.
Above-mentioned node also includes crosspoint and amending unit, wherein：
Crosspoint, is exchanged for carrying out routing table with other described nodes；
Amending unit, for being contrasted and itself routing table of the node according to the routing table obtained from other described nodes
Between difference, the node for causing routing table difference is detected, when it is determined that needing the node itself self-modified routing table,
Carry out local routing table amendment.
Wherein, the overlay network is adjusted, and is：New node adds the overlay network and/or has node to exit described fold
Screening；
The triggering routing table update cause information includes at least one of following information：
New node adds the overlay network, node and exits the overlay network, node and be responsible for interval change；
The routing table cryptographic Hash is each Hash for routeing table segmenting in routing table cryptographic Hash or node complete in node
Value.
A kind of overlay network node, including receiving unit, updating block, computing unit and determining unit；Wherein：
Receiving unit, for receive other nodes transmission triggering routing table update cause information and update after routing table breathe out
Uncommon value；
Updating block, for carrying out local routing table renewal according to the triggering routing table update cause information；
Computing unit, the cryptographic Hash for calculating routing table after the node local update；
Whether consistent with received routing table cryptographic Hash determining unit, calculate cryptographic Hash for determination.
Above-mentioned node also includes crosspoint and amending unit, wherein：
When the determining unit determines to calculate cryptographic Hash and inconsistent received routing table cryptographic Hash, triggering is exchanged
Unit；
Crosspoint, is exchanged for carrying out routing table with other described nodes；
Amending unit, for being contrasted and itself routing table of the node according to the routing table obtained from other described nodes
Between difference, the node for causing routing table difference is detected, when it is determined that needing the node itself self-modified routing table,
Carry out local routing table amendment.
Wherein, the triggering routing table update cause information includes at least one of following information：
New node adds the overlay network, node and exits the overlay network, node and be responsible for interval change；
The routing table cryptographic Hash is each Hash for routeing table segmenting in routing table cryptographic Hash or node complete in node
Value.
In the present invention, when node determines to have new node to add or have node to exit overlay network, the node carries out local
After routing update, routing table cryptographic Hash notifies other of the overlay network after triggering routing table update cause information and update
Node；Other described nodes carry out local routing table renewal according to the triggering routing table update cause information, and calculate local
The cryptographic Hash of routing table after renewal, it is determined that with routing table cryptographic Hash received by itself it is inconsistent when, other described nodes with
And carry out routing table exchange between the node for sending triggering routing table update cause information；Other described nodes and described
The node for sending triggering routing table update cause information according to acquired routing table information and is locally stored between routing table respectively
Difference overlay network is detected, it is determined that when needing itself self-modified routing table, carry out local routing table amendment.So, this hair
Bright technical scheme automatic when there is node to carry out routing table update can eliminate the nonsynchronous phenomenon of routing table between node, so that
The routing table diffusion of mistake is avoided, overlay network routing performance will not be caused to decline；Enter walking along the street only with cryptographic Hash in the present invention
By the verification of table, routing table exchange is just carried out between node when finding that check value is inconsistent, routing table asynchrony phenomenon is eliminated
Expense it is smaller.
Brief description of the drawings
Fig. 1 is the schematic diagram of DHT rings；
Fig. 2 is the flow chart that node adds overlay network；
Fig. 3 is the flow chart that two nodes add overlay network in similar time；
Fig. 4 is that interior joint of the embodiment of the present invention carries out routing update and carries out the first pass of routing table verification and amendment
Figure；
Fig. 5 is that interior joint of the embodiment of the present invention carries out routing update and carries out the second procedure of routing table verification and amendment
Figure；
Fig. 6 is that interior joint of the embodiment of the present invention carries out routing update and carries out the 3rd flow of routing table verification and amendment
Figure；
Fig. 7 is that interior joint of the embodiment of the present invention carries out routing update and carries out the 4th flow of routing table verification and amendment
Figure；
Fig. 8 constitutes structural representation for a kind of of overlay network node of the embodiment of the present invention；
Fig. 9 is another composition structural representation of overlay network node of the embodiment of the present invention.
Embodiment
The present invention basic thought be：When node determines to have new node to add or have node to exit overlay network, the section
Point is carried out after local routing renewal, routing table cryptographic Hash after triggering routing table update cause information and renewal can be notified into described folded
Other nodes of screening；Other described nodes carry out local routing table renewal according to the triggering routing table update cause information,
And calculate the cryptographic Hash of routing table after local update, it is determined that with routing table cryptographic Hash received by itself it is inconsistent when, it is described
Routing table exchange is carried out between the node of other nodes and transmission triggering routing table update cause information；Other described sections
Point and the node for sending triggering routing table update cause information are respectively according to acquired routing table information with locally depositing
Difference between storage routing table is detected to overlay network, it is determined that when needing itself self-modified routing table, carrying out local routing table amendment.
To make the purpose of the present invention, technical scheme and advantage are more clearly understood, by the following examples and referring to the drawings, right
The present invention is further described.
Fig. 4 is that interior joint of the embodiment of the present invention carries out routing update and carries out the first pass of routing table verification and amendment
Figure.Overlay network is responsible for distribution form using the resource of similar Chord algorithms, i.e., each node is responsible for this node identification and precursor node
Hash space between mark.In this example, it is assumed that the routing table information that node D is preserved is imperfect, and it is unaware of depositing for node C
；Node D responsible node is node B.As shown in figure 4, the node of this example carries out routing update and carries out routing table verification
And the flow of amendment specifically includes following steps：
Step 401, node B receives nodes X and exits overlay network request message, or has found nodes X by detection of connectivity
Failure, it needs the failed information of nodes X being broadcast to whole overlay network；
Step 402, node B sends routing update request message to node D, wherein the information left containing nodes X and more
The cryptographic Hash of full routing table after new；
Step 403, node D updates routing table according to request, the cryptographic Hash of full routing table after updating is calculated, to node B
Routing table update response message is sent, and includes cryptographic Hash obtained by above-mentioned calculating；
Step 404, the cryptographic Hash in the response message that node B is relatively received finds the two with calculated value is locally stored
It is not inconsistent；
Step 405, node B sends full routing table to node D, and requesting node D returns to full routing table；
Step 406, node D sends full routing table to node B；
Step 407, lack in the routing table received with the routing table being locally stored, discovery that node B contrasts are received
Node C；
Step 408, node B sends connective probe requests thereby to node C；
Step 409, node C sends connective probe response message to node B, and node B confirms node C in net, without repairing
Positive local routing table；
Step 410, the node D contrasts routing table received and the routing table being locally stored, find the routing table received
In many egress C；
Step 411, node D sends connective probe request message to node C；
Step 412, node C sends connective probe response message to node D；
Step 413, node D confirms that node C, in net, is modified to local routing table.
Fig. 5 is that interior joint of the embodiment of the present invention carries out routing update and carries out the second procedure of routing table verification and amendment
Figure.In this example, overlay network is divided into some segmentations using the load-balancing algorithm based on segmentation, hash space, and each node is born
Blame the segmentation number being consistent with self-ability.In this example, it is assumed that node D preserves the responsible interval situation on node C with working as
Preceding network condition is asynchronous.Node D is node Y responsible node, and node B is also included in overlay network.As shown in figure 5, this example
Node carry out routing update and carry out the flow of routing table verification and amendment specifically including following steps：
Step 501, node D adds the responsible node of overlay network for node Y, and complete to node Y data migration process
Into this is responsible for interval change message and is broadcast to whole overlay network by its needs；
Step 502, node D is sent in routing update request message, the routing update request message to node B includes section
Point Y is responsible for the cryptographic Hash of full routing table after the information of interval change and renewal；
Step 503, node B updates routing table according to routing update request message, calculates the Kazakhstan of full routing table after updating
Uncommon value, sends routing table update response message, and include cryptographic Hash obtained by above-mentioned calculating to node D；
Step 504, node D relatively receives the cryptographic Hash in response and calculated value is locally stored, it is found that the two is not inconsistent；
Step 505, node D sends full routing table to node B, and requesting node B returns to full routing table；
Step 506, node B sends full routing table to node D；
Step 507, C is responsible in the routing table received with the routing table being locally stored, discovery that node B contrasts are received
Interval is not inconsistent with local record；
Step 508, node B is sent to node C is responsible for interval probe request message；
Step 509, node C is sent to node B is responsible for interval probe response message, and this is responsible in interval probe response message
It is responsible for the situation in interval comprising this node, node B confirms that routing table is locally stored is responsible for interval record correctly on node C,
Without self-modified routing table；
Step 510, C is responsible for area in the routing table received with the routing table being locally stored, discovery that node D contrasts are received
Between be not inconsistent with local record；
Step 511, node D is sent to node C is responsible for interval probe request message；
Step 512, node C is sent to node D is responsible for interval probe response message, and this is responsible in interval probe response message
It is responsible for interval situation comprising this node；
Step 513, node D confirms that locally being responsible for interval on node C records wrong, is modified to routing table.
To accelerate the discovery of routing table difference, reduce the expense of exchange routing table between node, routing table can be segmented,
The cryptographic Hash of subsidiary each segmentation in routing update request and response message.The segmentation of routing table should be carried out by agreement, to ensure
Identical routing table, which is calculated, will obtain identical segmentation cryptographic Hash for verifying.Fig. 6 is carried out for interior joint of the embodiment of the present invention
Routing update and the 3rd flow chart for carrying out routing table verification and amendment.Overlay network is responsible for using the resource of similar Chord algorithms
Interval distribution form, i.e., each node is responsible for the hash space between this node identification and precursor node identification.In this example, node
The routing table information that M is preserved is imperfect, and it is unaware of node P and left in overlay network, overlay network also including node N.Such as Fig. 6
Shown, the node of this example carries out routing update and carries out the flow of routing table verification and amendment specifically including following steps：
Step 601, node M meets the situation for needing broadcast table to update；
Step 602, node M sends in routing table update request message, the routing table update request message to node N and contained
The information of situation and the cryptographic Hash of each route table segmenting are adjusted on overlay network；
Step 603, node N requests more than update routing table, and calculate update after each route table segmenting cryptographic Hash,
Sent to node M and above-mentioned calculated cryptographic Hash is included in routing table update response message, the routing table update response message；
Step 604, node M relatively receives the cryptographic Hash in response message and calculated value is locally stored, and finds certain section of Kazakhstan
Uncommon value is not inconsistent；
Step 605, node M sends the routing table that cryptographic Hash is not inconsistent part to node N, and requesting node N returns to the Duan Lu
By table；
Step 606, node N sends the routing table that cryptographic Hash is not inconsistent part to node M；
Step 607, lack in the routing table received with the routing table being locally stored, discovery that node N contrasts are received
Node P；
Step 608, node N sends connective probe request message to node P；
Step 609, the node M contrast routing table received and the routing table being locally stored, find the routing table received
In many egress P；
Step 610, node M sends connective probe request message to node P；
Step 611, node N requests timer does not receive node P probe response message then, and probe requests thereby is overtime,
Confirm that node P has failed, without self-modified routing table；
Step 612, node M request timer does not receive node P probe response message then, and probe requests thereby is overtime,
Confirm that node P has failed, routing table is modified.
To avoid situations such as single-point overloads, node finds that contained cryptographic Hash is not inconsistent in routing update request and response message
Afterwards, routing table can not be exchanged immediately, but corresponding counter is added 1, device to be counted is reached after given threshold, then with it is other
Node carries out routing table and exchanges and further handle.In this example, overlay network includes node Q, node M and node N.Fig. 7 is
Interior joint of the embodiment of the present invention carries out routing update and carries out the 4th flow chart of routing table verification and amendment, as shown in fig. 7, this
The node of example carries out routing update and carries out the flow of routing table verification and amendment specifically including following steps：
Step 701, node Q, which is met, need to update the situation of routing table；
Step 702, node Q sends routing update request message to node M, and attaches route table segmenting cryptographic Hash；
Step 703, node M is updated by routing update request message to routing table, calculates the Kazakhstan of routing table after updating
Uncommon value, routing update response message, and cryptographic Hash obtained by subsidiary above-mentioned calculating are sent to node Q；
Step 704, node M finds that routing table section cryptographic Hash is not inconsistent with local record, adds 1 by the segment counter value, and
Counter results are compared with given threshold, not up to given threshold；
Overlay network continues to run with a period of time；
Step 705, node M meets the situation for needing to update routing table；
Step 706, node M sends routing update request message to node N, and attaches route table segmenting cryptographic Hash；
Step 707, node N is updated by routing update request message to routing table, calculates the Kazakhstan of routing table after updating
Uncommon value, routing update response message, and subsidiary above-mentioned cryptographic Hash are sent to node M；
Step 708, node M finds that routing table section cryptographic Hash is not inconsistent with local record, adds 1 by the segment counter value, and
Counter results are compared with given threshold, not up to given threshold；
Step 709, node M sends routing update request message to node P, and attaches route table segmenting cryptographic Hash；
Step 710, node P is updated by routing update request message to routing table, calculates the Kazakhstan of routing table after updating
Uncommon value, routing update response message, and subsidiary above-mentioned cryptographic Hash are sent to node M；
Step 711, node M finds that routing table section cryptographic Hash is not inconsistent with local record, adds 1 by the segment counter value, and
Counter results are compared with given threshold, not up to given threshold；
Overlay network continues to run with a period of time；
Step 712, node M with certain node progress routing update requests/response messages after interacting, and certain segment counter value adds
Given threshold is reached after 1.Node M and this section of routing table of the node switching, to being detected where difference, and carry out corresponding position
Reason, it is 0 to reset the segment counter.
Fig. 8 constitutes structural representation for a kind of of overlay network node of the embodiment of the present invention, as shown in figure 8, this example is folded
Screening node includes detection unit 80, updating block 81 and notification unit 82；Wherein：
Detection unit 80, for detecting whether the overlay network adjusts, triggers updating block 81 during generation；
Updating block 81, for carrying out routing table update；
Notification unit 82, for routing table cryptographic Hash after triggering routing table update cause information and renewal to be notified into described folded
Other nodes of screening.
On the basis of overlay network node shown in Fig. 8, the overlay network node of this example also includes crosspoint (in Fig. 8 not
Diagram) and amending unit (not shown in Fig. 8), wherein：
Crosspoint, is exchanged for carrying out routing table with other described nodes；
Amending unit, for being contrasted and itself routing table of the node according to the routing table obtained from other described nodes
Between difference, the node for causing routing table difference is detected, when it is determined that needing the node itself self-modified routing table,
Carry out local routing table amendment.
The overlay network is adjusted, and is：New node adds the overlay network and/or has node to exit the overlay network；
Above-mentioned triggering routing table update cause information includes at least one of following information：
New node adds the overlay network, node and exits the overlay network, node and be responsible for interval change.
Above-mentioned routing table cryptographic Hash is each Hash for routeing table segmenting in routing table cryptographic Hash or node complete in node
Value.
Fig. 9 is another composition structural representation of overlay network node of the embodiment of the present invention, as shown in figure 9, this example
Overlay network node includes receiving unit 90, updating block 91, computing unit 92 and determining unit 93；Wherein：
Receiving unit 90, for receive other nodes transmission triggering routing table update cause information and update after routing table
Cryptographic Hash；
Updating block 91, for carrying out local routing table renewal according to the triggering routing table update cause information；
Computing unit 92, the cryptographic Hash for calculating routing table after the node local update；
Whether consistent with received routing table cryptographic Hash determining unit 93, calculate cryptographic Hash for determination.
On the basis of overlay network node shown in Fig. 9, the overlay network node of this example also includes crosspoint (in Fig. 9 not
Diagram) and amending unit (not shown in Fig. 9), wherein：
Crosspoint, is exchanged for carrying out routing table with other described nodes；
Amending unit, for being contrasted and itself routing table of the node according to the routing table obtained from other described nodes
Between difference, the node for causing routing table difference is detected, when it is determined that needing the node itself self-modified routing table,
Carry out local routing table amendment.
The overlay network is adjusted, and is：New node adds the overlay network and/or has node to exit the overlay network.
Above-mentioned triggering routing table update cause information includes at least one of following information：
New node adds the overlay network, node and exits the overlay network, node and be responsible for interval change.
Above-mentioned routing table cryptographic Hash is each Hash for routeing table segmenting in routing table cryptographic Hash or node complete in node
Value.
It will be appreciated by those skilled in the art that the realization of each processing unit in overlay network node shown in Fig. 8 and Fig. 9
Function can refer to earlier figures 4 and understand to the associated description of Fig. 7 distributed hashtable routing table update method.Art technology
Personnel should be appreciated that the function of each processing unit in overlay network node shown in Fig. 8 and Fig. 9 can be by running on processor
Program and realize, can also be realized by specific logic circuit.
The foregoing is only a preferred embodiment of the present invention, is not intended to limit the scope of the present invention.
Claims (13)
1. a kind of distributed hashtable routing table update method, it is characterised in that methods described includes：
When overlay network interior joint detects the overlay network and adjusted, routing table update is carried out, and routing table update will be triggered
Routing table cryptographic Hash notifies other nodes of the overlay network after cause information and renewal；
Wherein, other described nodes are used to carry out local routing table renewal according to the triggering routing table update cause information, and
Calculate the cryptographic Hash of routing table after local update；When it is determined that calculated cryptographic Hash and received routing table cryptographic Hash are inconsistent
When, other described nodes are additionally operable to the progress routing table between the node for sending triggering routing table update cause information and exchanged.
2. according to the method described in claim 1, it is characterised in that will triggering routing table update cause information and update the way of escape by
Table cryptographic Hash notifies after other nodes of the overlay network that methods described also includes：
Other described nodes carry out local routing table renewal according to the triggering routing table update cause information, and calculate locally more
The cryptographic Hash of routing table after new, it is determined that when calculated cryptographic Hash and inconsistent received routing table cryptographic Hash, being touched with sending
Send out progress routing table exchange between the node of routing table update cause information；
The node of other described nodes and transmission triggering routing table update cause information is true according to the routing table exchanged
It is fixed whether need amendment local routing table, it is necessary to when carry out routing table amendment.
3. method according to claim 1 or 2, it is characterised in that other described nodes and transmission triggering route
Table update cause information node according to the routing table exchanged determine the need for amendment local routing table, it is necessary to when enter walking along the street
By table amendment, it is：
Other described nodes and the transmission triggering routing table update cause information node respectively according to from other side obtain
Routing table contrast with the difference between itself routing table, the node for causing routing table difference is detected, according to detection tie
Fruit carries out local routing table amendment when it is determined that needing itself self-modified routing table.
4. method according to claim 1 or 2, it is characterised in that the overlay network is adjusted, and is：New node is added
The overlay network and/or there is node to exit the overlay network.
5. method according to claim 1 or 2, it is characterised in that the triggering routing table update cause information include with
At least one of lower information：
New node adds the overlay network, node and exits the overlay network, node and be responsible for interval change；
The routing table cryptographic Hash is each cryptographic Hash for routeing table segmenting in routing table cryptographic Hash or node complete in node.
6. method according to claim 5, it is characterised in that methods described also includes：
For routing table or routing table subsection setup counter；
When other described nodes determine to calculate cryptographic Hash with received routing table or inconsistent route table segmenting cryptographic Hash,
The counter is added one；When determining that the count value of the counter reaches given threshold, triggering routing table is sent more with described
Routing table exchange is carried out between the node of new cause information.
7. method according to claim 6, it is characterised in that the routing table cryptographic Hash is each route table segmenting in node
Cryptographic Hash when, methods described also includes：
Other described nodes carry out local routing table renewal according to the triggering routing table update cause information, it is determined that after updating certain
When the cryptographic Hash of certain route table segmenting of the cryptographic Hash for routeing table segmenting with being received is inconsistent, triggering routing table is sent with described
Inconsistent routing table segment exchange is only carried out between the node for updating cause information.
8. a kind of overlay network node, it is characterised in that the node includes detection unit, updating block and notification unit；Wherein：
Detection unit, for detecting whether the overlay network adjusts, triggers updating block during generation；
Updating block, for carrying out routing table update；
Notification unit, for routing table cryptographic Hash after triggering routing table update cause information and renewal to be notified into the overlay network
Other nodes；
Wherein, other described nodes are used to carry out local routing table renewal according to the triggering routing table update cause information, and
Calculate the cryptographic Hash of routing table after local update；When it is determined that calculated cryptographic Hash and received routing table cryptographic Hash are inconsistent
When, other described nodes are additionally operable to the progress routing table between the node for sending triggering routing table update cause information and exchanged.
9. node according to claim 8, it is characterised in that the node also includes crosspoint and amending unit, its
In：
Crosspoint, is exchanged for carrying out routing table with other described nodes；
Amending unit, for being contrasted according to the routing table obtained from other described nodes between the node itself routing table
Difference, the node for causing routing table difference is detected, when it is determined that needing the node itself self-modified routing table, carry out
Local routing table amendment.
10. node according to claim 8 or claim 9, it is characterised in that the overlay network is adjusted, and is：New node is added
The overlay network and/or there is node to exit the overlay network；
The triggering routing table update cause information includes at least one of following information：
New node adds the overlay network, node and exits the overlay network, node and be responsible for interval change；
The routing table cryptographic Hash is each cryptographic Hash for routeing table segmenting in routing table cryptographic Hash or node complete in node.
11. a kind of overlay network node, it is characterised in that the node includes receiving unit, updating block, computing unit, exchange
Unit and determining unit；Wherein：
Receiving unit, for receive other nodes transmission triggering routing table update cause information and update after routing table Hash
Value；
Updating block, for carrying out local routing table renewal according to the triggering routing table update cause information；
Computing unit, the cryptographic Hash for calculating routing table after the node local update；
Determining unit, it is whether consistent with received routing table cryptographic Hash for determining to calculate cryptographic Hash, it is determined that being calculated
When cryptographic Hash and inconsistent received routing table cryptographic Hash, crosspoint is triggered；
Crosspoint, is exchanged for carrying out routing table with other described nodes.
12. node according to claim 11, it is characterised in that the node also includes amending unit, wherein：
Amending unit, for being contrasted according to the routing table obtained from other described nodes between the node itself routing table
Difference, the node for causing routing table difference is detected, when it is determined that needing the node itself self-modified routing table, carry out
Local routing table amendment.
13. the node according to claim 11 or 12, it is characterised in that the triggering routing table update cause information includes
At least one of following information：
New node adds the overlay network, node and exits the overlay network, node and be responsible for interval change；
The routing table cryptographic Hash is each cryptographic Hash for routeing table segmenting in routing table cryptographic Hash or node complete in node.
Priority Applications (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201110384912.XA CN103139081B (en) | 2011-11-28 | 2011-11-28 | Distributed hashtable routing table update method and node |
| PCT/CN2012/077457 WO2013078852A1 (en) | 2011-11-28 | 2012-06-25 | Routing table updating method and node for distributed hush table |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201110384912.XA CN103139081B (en) | 2011-11-28 | 2011-11-28 | Distributed hashtable routing table update method and node |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN103139081A CN103139081A (en) | 2013-06-05 |
| CN103139081B true CN103139081B (en) | 2017-08-11 |
Family
ID=48498408
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201110384912.XA Active CN103139081B (en) | 2011-11-28 | 2011-11-28 | Distributed hashtable routing table update method and node |
Country Status (2)
| Country | Link |
|---|---|
| CN (1) | CN103139081B (en) |
| WO (1) | WO2013078852A1 (en) |
Families Citing this family (9)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN104683415A (en) * | 2013-12-02 | 2015-06-03 | 乐视网信息技术（北京）股份有限公司 | Method and device for transmitting deleted data notification message in peer-to-peer network |
| CN103986649B (en) * | 2014-05-28 | 2017-08-11 | 新华三技术有限公司 | A kind of Border Gateway Protocol smooth restarting method and routing device |
| CN104702503B (en) * | 2015-03-26 | 2018-05-18 | 中国电子科技集团公司第七研究所 | Network route method and system |
| CN107181686B (en) | 2016-03-09 | 2020-06-23 | 阿里巴巴集团控股有限公司 | Method, device and system for synchronizing routing table |
| CN105915457B (en) * | 2016-04-29 | 2018-12-11 | 清华大学 | A kind of route renewing method of the Border Gateway Protocol based on routing check |
| CN107734008A (en) * | 2017-09-27 | 2018-02-23 | 柏科数据技术（深圳）股份有限公司 | Method, apparatus, node device and the storage medium of a kind of troubleshooting in data-storage system |
| CN109361625B (en) * | 2018-10-24 | 2021-12-07 | 新华三技术有限公司合肥分公司 | Method, device and controller for checking forwarding table item |
| CN112104576B (en) * | 2020-08-14 | 2022-02-22 | 中国科学院声学研究所 | Resident flow table storage and calibration method of SDN switch |
| CN112822224B (en) * | 2021-04-19 | 2021-06-22 | 国网浙江省电力有限公司 | Safe transmission method for financial data query |
Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN102037704A (en) * | 2008-05-23 | 2011-04-27 | 爱立信电话股份有限公司 | Maintaining distributed hash tables in an overlay network |
| CN102057647A (en) * | 2008-06-12 | 2011-05-11 | 爱立信电话股份有限公司 | Maintenance of overlay networks |
Family Cites Families (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN101442479B (en) * | 2007-11-22 | 2011-03-30 | 华为技术有限公司 | Method, equipment and system for updating route in P2P peer-to-peer after node failure |
| CN101505263B (en) * | 2008-02-05 | 2011-10-26 | 华为技术有限公司 | Method and device for maintaining routing information |
| JP2010028551A (en) * | 2008-07-22 | 2010-02-04 | Brother Ind Ltd | Content distributed storage system, node device, node processing program, and address information change notifying method |
| CN101984605B (en) * | 2010-11-12 | 2016-04-13 | 中兴通讯股份有限公司 | Diameter node in routing discovering method and indirectly connected diameter system |
-
2011
- 2011-11-28 CN CN201110384912.XA patent/CN103139081B/en active Active
-
2012
- 2012-06-25 WO PCT/CN2012/077457 patent/WO2013078852A1/en active Application Filing
Patent Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN102037704A (en) * | 2008-05-23 | 2011-04-27 | 爱立信电话股份有限公司 | Maintaining distributed hash tables in an overlay network |
| CN102057647A (en) * | 2008-06-12 | 2011-05-11 | 爱立信电话股份有限公司 | Maintenance of overlay networks |
Also Published As
| Publication number | Publication date |
|---|---|
| WO2013078852A1 (en) | 2013-06-06 |
| CN103139081A (en) | 2013-06-05 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN103139081B (en) | Distributed hashtable routing table update method and node | |
| EP3270553B1 (en) | Ospf point-to-multipoint over broadcast or nbma mode | |
| ES2620082T3 (en) | Identification of routes taken through a network of interconnected devices | |
| CN102075359B (en) | A kind of server disposition method of coordinate Network Based and device | |
| EP2672679A1 (en) | Method and Apparatus for Maintaining Routing Information | |
| CN101986622B (en) | A kind of automatic identifying method of PCE status attribute and system | |
| CN105024844A (en) | Method, server and system for computing cross-domain routing | |
| US9069761B2 (en) | Service-aware distributed hash table routing | |
| CN101483610A (en) | Route updating method for link state routing protocol | |
| Abid et al. | Exploiting 3D structure for scalable routing in MANETs | |
| CN105763444B (en) | A kind of route synchronization method and device | |
| KR20130080626A (en) | A routing method between domains for content centric network and the content centric network | |
| CN104092611A (en) | Method and device for determining label switching route with restrained cross region | |
| CN105991365B (en) | The method, apparatus and system of path detection | |
| CN111884827B (en) | Method for synchronizing topological information in SFC network and routing network element | |
| CN107078961A (en) | Intermediate System-to-Intermediate System topology clear area | |
| CN112671652B (en) | Message forwarding method and device | |
| Jingjing et al. | The deployment of routing protocols in distributed control plane of SDN | |
| EP2122906B1 (en) | Discovery of disconnected components in a distributed communication network | |
| CN105763446B (en) | A kind of link-state information processing method and processing device | |
| WO2011150741A1 (en) | Point to point (p2p) overlay network, data resources operation method and new node join method thereof | |
| Zhang et al. | Cloud aided internet mobility | |
| Verma et al. | Cluster Based Routing in NDN | |
| Fersi et al. | Consistent and efficient bootstrapping ring-based protocol in randomly deployed wireless sensor networks | |
| Masuda et al. | Splitable: Toward routing scalability through distributed bgp routing tables |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| C06 | Publication | ||
| PB01 | Publication | ||
| C10 | Entry into substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |