Method and apparatus for maintaining routing information

• US 8,732,298 B2
• Filed: 07/12/2010
• Issued: 05/20/2014
• Est. Priority Date: 02/05/2008
• Status: Active Grant

• Current Assignee: Huawei Technologies Co., Ltd. (Huawei Investment & Holding Co., Ltd.)
• Original Assignee: Huawei Technologies Co., Ltd. (Huawei Investment & Holding Co., Ltd.)
• Inventors: Shi, Guangyu, Chen, Jian, Gong, Hao
• Primary Examiner(s): Nguyen, Quang N
• Assistant Examiner(s): YI, DAVID
• Application Number:
  US12/834,239
• Publication Number:
  US 20100281163A1
• Time in Patent Office: 1,408 Days
• Field of Search: 709/224, 709/242, 709/243
• US Class Current: 709/224
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1051 Group master selection mechanisms
• CPC Class Codes: H04L 67/1093 Some peer nodes performing special functions

Abstract

A method and apparatus for maintaining routing information in a Peer-to-Peer (P2P) network are provided. The method includes that: a super maintenance node receives routing update information of an ordinary node in its home area; the super maintenance node sends routing update information to super maintenance nodes in other network areas; the super maintenance nodes in other network areas notify ordinary nodes in their home network areas to update routing information. With the present invention, a node of strong processing capabilities at the network area border is chosen to act as a super maintenance node and other nodes as ordinary nodes; when a node joins or fails, an ordinary node sends detected routing update information only to the super maintenance node in the local network area; the super maintenance node then forwards the update information to super maintenance nodes in other network areas. Each super maintenance node notifies ordinary nodes in its home network area of the received routing update information.

Claims

1. A method for maintaining routing information, comprising:

receiving, by a super maintenance node, routing update information of an ordinary node in a home network area of the super maintenance node from the ordinary node;

sending, by the super maintenance node, the received routing update information to super maintenance nodes in other network areas;

calculating, by the super maintenance node, a range of node IDs in a second network area and creating routing update information according to a method for constructing a node ID that carries geographic location information when the super maintenance node knows that super maintenance nodes in the second network area have failed and notifying, by the super maintenance node, ordinary nodes in the home network area of the super maintenance node of the created routing update information; and

performing, by the super maintenance node, a registration including;

registering, by the super maintenance node, node ID, IP address, and hierarchical relations, of the super maintenance node in a DHT;

or

registering, by the super maintenance node, in a public address;

or

registering, by the super maintenance node, as an IP Anycast group member.

2. The method according to the claim 1, wherein before receiving, by the super maintenance node, the routing update information of the ordinary node in the home network area of the super maintenance node from the ordinary node, the method further comprises:

receiving, by the super maintenance node, a routing update notification from an ordinary node.

3. The method according to the claim 1, wherein the notifying, by the super maintenance node, ordinary nodes in the home network area of the super maintenance node to update routing information, further comprises:

sending the created routing update information to the ordinary nodes in the home network area of the super maintenance node.

4. The method according to the claim 1, wherein the notifying, by the super maintenance node, ordinary nodes in the home network area of the super maintenance node to update routing information comprises:

sending, by the super maintenance node, the updated routing information to ordinary nodes in home network area;

or

sending, by the super maintenance node, another routing update notification to the ordinary nodes according to the routing update information so that the ordinary nodes obtain the new routing information from the super maintenance node upon reception of the another routing update notification;

or

sending, by the super maintenance node, the routing update information by broadcast;

or

spreading, by the super maintenance node, the routing update information gradually by a parallel multicast to ordinary nodes in the home network area.

5. A system for maintaining routing information, comprising,

a first ordinary node, a first super maintenance node, a second ordinary node, a third super maintenance node, a fourth ordinary node, a fourth super maintenance node and a fifth ordinary node, wherein

the first ordinary node in a home network area of the first super maintenance node and is configured to:

generate routing update information and send the routing update information to the first super maintenance node;

the first super maintenance node is configured to;

receive the routing update information from the first ordinary node and send routing update information to the third super maintenance node and to the second ordinary node in the home network area of the first super maintenance node according to the routing update information;

the second ordinary node is configured to;

receive the routing update information from the first super maintenance node and update routing information according to the received routing update information;

the third super maintenance node is configured to;

receive the routing update information from the first super maintenance node and send routing update information to the fourth ordinary node in a home network area of the third super maintenance node and to the fourth super maintenance node according to the routing update information;

the fourth ordinary node is configured to;

receive the routing update information from the third super maintenance node and update routing information according to the received routing update information;

the fourth super maintenance node is configured to;

receive the routing update information from the third super maintenance node and send routing update information to the fifth ordinary node in a home network area of the fourth super maintenance node according to the routing update information; and

the fifth ordinary node is configured to;

receive the routing update information from the fourth super maintenance node and update routing information according to the received routing update information,

wherein one or more of the first, second or third super maintenance nodes is configured to calculate a range of node IDs in a network area and create routing update information according to a method for constructing a node ID that carries geographic location information when the first, second or third super maintenance node knows that super maintenance nodes in the network area have failed, and notify the first, second, fourth or fifth ordinary nodes in respective home network areas of the first, third and fourth super maintenance nodes of the created routing update information, and

one or more of the first, second or third super maintenance nodes is configured to perform a registration including;

registering node ID, IP address, and hierarchical relations, of itself in a DHT;

or

registering itself in a public address;

or

registering itself as an IP Anycast group member.

9. The system according to the claim 5, the first super maintenance node is further configured to:

send the created routing update information to the first and second ordinary nodes in the home network area of the first super maintenance node.

6. A system for maintaining routing information, comprising,

a first ordinary node, a first super maintenance node, a second ordinary node, a second super maintenance node, and a third ordinary node, wherein:

the first ordinary node in a home network area of the first super maintenance node and is configured to;

generate routing update information and send the routing update information to the first super maintenance node;

the first super maintenance node is configured to;

receive the routing update information from the first ordinary node and send routing update information to the second super maintenance node and to the second ordinary node in the home network area of the first super maintenance node according to the routing update information;

the second ordinary node is configured to;

receive the routing update information from the first super maintenance node and update routing information according to the received routing update information;

the second super maintenance node is configured to;

receive the routing update information from the first super maintenance node and send routing update information to the third ordinary node in a home network area of the second super maintenance node according to the routing update information; and

the third ordinary node is configured to;

receive the routing update information from the second super maintenance node and update routing information according to the received routing update information,

wherein one or more of the first or second super maintenance nodes is configured to calculate a range of node IDs in a network area and generate routing update information according to a method for constructing a node ID that carries geographic location information when the first or second super maintenance node knows that super maintenance nodes in the network area have failed, and notify the first, second, or third ordinary nodes in respective home network areas of the first and second super maintenance nodes of the generated routing update information, and

one or more of the first or second super maintenance nodes is configured to perform a registration including;

registering node ID, IP address, and hierarchical relations, of itself in a DHT;

or

registering itself in a public address;

or

registering itself as an IP Anycast group member.

10. The system according to the claim 6, the first super maintenance node is further configured to:

send the created routing update information to the first and second ordinary nodes in the home network area of the first super maintenance node.

7. A super maintenance node, comprising:

a receiver, configured to receive routing update information from an ordinary node;

a transmitter, configured to send the received routing update information to super maintenance nodes in other network areas and to notify ordinary nodes in a home network area of the super maintenance node to update routing information; and

a computing processor, configured to;

calculate a range of node IDs in a network area and generate routing update information according to a method for constructing a node ID that carries geographic location information when the super maintenance node knows that super maintenance nodes in the network area have failed, the transmitter notifies the ordinary nodes in the home network area of the super maintenance node of the generated routing update information, and

perform a registration including;

registering node ID, IP address, and hierarchical relations, of the super maintenance node in a DHT;

or

registering the super maintenance node in a public address;

or

registering the super maintenance node as an IP Anycast group member.

8. The super maintenance node according to the claim 7,

wherein the transmitter further sends the generated routing update information to the ordinary nodes in the home network area of the super maintenance node.

11. A method for maintaining routing information, comprising:

sending, by an ordinary node in a home network area of a super maintenance node, routing update information of the ordinary node to the super maintenance node and

updating, by the ordinary node, routing information according to a routing update notification from the super maintenance node,

wherein;

the super maintenance node is configured to calculate a range of node IDs in a target network area and generates routing update information according to a method for constructing a node ID that carries geographic location information when the super maintenance node knows that super maintenance nodes in the target network area have failed and notify the ordinary node in the home network area of the super maintenance node to update routing information by sending the generated routing update information to the ordinary node in the home network area of the super maintenance node, and

the super maintenance node is configured to perform a registration including;

registering node ID, IP address, and hierarchical relations, of the super maintenance node in a DHT;

or

registering the super maintenance node in a public address;

or

registering the super maintenance node as an IP Anycast group member.

12. The method according to the claim 11, wherein before the sending, by the ordinary node in the home network area of the super maintenance node, the routing update information of the ordinary node to the super maintenance node, the method further comprises:

obtaining, by the ordinary node, an address of the super maintenance node; and

sending, by the ordinary node, the routing update notification to the super maintenance node.

13. The method according to the claim 11, wherein

the ordinary node queries the DHT to obtain an address of the super maintenance node;

or

the ordinary node obtains an address of the super maintenance node from the public address;

or

the ordinary node initiates an Anycast request and receive an address of the super maintenance node return from a router;

or

an address of the super maintenance node in the home network area is configured for the ordinary node.

14. The method according to the claim 11, further comprising:

obtaining, by the ordinary node, new routing information from the super maintenance node upon reception of another routing update notification.