System and method for a distributed server for peer-to-peer networks

• US 7,639,681 B2
• Filed: 11/23/2004
• Issued: 12/29/2009
• Est. Priority Date: 11/23/2004
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Erwin, Jeffrey B., Kelly, Stephen T.
• Primary Examiner(s): Trost, IV; William
• Assistant Examiner(s): Shand; Roberta A
• Application Number:
  US10/996,895
• Publication Number:
  US 20060126611A1
• Time in Patent Office: 1,862 Days
• Field of Search: 370/351, 370/389, 370/400, 370/408, 370/409
• US Class Current: 370/389
• CPC Class Codes: H04L 61/5014 using dynamic host configuration protocol [DHCP] or bootstrap protocol [BOOTP]
• CPC Class Codes: H04L 61/5061 Pools of addresses
• CPC Class Codes: H04L 61/5092 by self-assignment, e.g. picking addresses at random and testing if they are already in use
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1044 Group management mechanisms management of multicast group membership H04L12/185; reconfiguring of node membership in a computing system to eliminate errors G06F11/1425
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: H04W 4/12 Messaging; Mailboxes; Announcements
• CPC Class Codes: H04W 40/00 Communication routing or communication path finding
• CPC Class Codes: H04W 8/26 Network addressing or numbering for mobility support
• CPC Class Codes: H04W 80/00 Wireless network protocols or protocol adaptations to wireless operation
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks
• CPC Class Codes: H04W 88/14 Backbone network devices
• CPC Class Codes: H04W 92/18 between terminal devices

Abstract

A logical distributed server is generated for managing (Internet Protocol (IP) address allocation for an ad-hoc, self-forming peer-to-peer (P2P) network. The logical distributed server is generated according to messaging scheme where nodes on the P2P network allocate addresses for themselves and for clients connected to them. Each node implements a server that listens on the incoming client connections. Each node maintains data structures that represent the current state of an address database. Routing requests are fielded by the nodes from the clients and the messaging scheme is used to inform other nodes of its action so a consistent address space is maintained between all the nodes on the P2P network.

Claims

1. A computer-implemented method for cooperatively managing a routed IP address space in the absence of managed network services, comprising:

identifying cooperative agents on a backbone network;

selecting a backbone address for a current cooperative agent on the backbone network;

wherein selecting the backbone address for the current cooperative agent includes comparing a portion of a selected backbone address for the current cooperative agent with the same portion of a selected backbone address of each of the identified cooperative agents on the backbone network;

selecting a client subnet address that corresponds to the current cooperative agent;

receiving a notification of an allocated client subnet address from another cooperative agent;

wherein relevance of the received notification is determined according to at least one of a timestamp included in the received notification and a hop count associated with the received notification;

notifying other cooperative agents on the backbone network of the client subnet address selection;

determining the relevance of the received notification;

forwarding the received notification to neighboring cooperative agents when the received notification is determined as relevant; and

discarding the received notification when the received notification is determined as irrelevant.

2. The computer-implemented method of claim 1, wherein identifying cooperative agents on the backbone network further comprises identifying mesh boxes on a mesh network.

3. The computer-implemented method of claim 1, wherein identifying cooperative agents on the backbone network further comprises broadcasting a discovery message that determines whether other cooperative agents are within communication range of the current cooperative agent.

4. The computer-implemented method of claim 3, wherein the discovery message includes an indication of randomly selected portion of the backbone address for the current cooperative agent for comparison with the same portion of backbone addresses selected by other cooperative agents.

5. The computer-implemented method of claim 4, wherein a conflict between the randomly selected portion of the backbone address for the current cooperative agent and the same portion for another cooperative agent is resolved by setting both portions to a single common value.

6. The computer-implemented method of claim 3, wherein the current cooperative agent waits for a specified time interval after broadcasting the discovery message to receive a response from other cooperative agents.

7. The computer-implemented method of claim 1, further comprising obtaining routing tables corresponding to neighboring cooperative agents of the current cooperative agent before selecting the backbone address, wherein the routing table include address allocations made by the neighboring cooperative agents.

8. The computer-implemented method of claim 1, wherein notifying other cooperative agents further comprises broadcasting an allocation message to neighboring cooperative agents, wherein the allocation message includes and indicator that the client subnet address has been allocated by the current cooperative agent.

9. The computer-implemented method of claim 8, further comprising broadcasting an additional allocation message to neighboring cooperative agents after a selected interval of time has elapsed, wherein the additional allocation message includes and indicator that the client subnet address is in use by the current cooperative agent.

10. The computer-implemented method of claim 1, further comprising selecting an unused subnet value from the client subnet address in response to a client routing request.

11. The computer-implemented method of claim 10, further comprising determining the number of remaining unused subnet values after the client routing request, wherein an additional client subnet address is allocated by the current cooperative agent when the number of remaining unused subnet values is under a specified threshold.

12. The computer-implemented method of claim 1, wherein the received notification is relevant when the timestamp occurs later than a local version of the timestamp.

13. The computer-implemented method of claim 1, wherein the received notification is irrelevant when the hop count is greater than a selected hop limit.

14. A computer-readable medium that includes computer-executable instructions for cooperatively managing a routed IP address space in the absence of managed network services, the instructions executing on a processor performing a method, comprising:

identifying neighboring mesh nodes on a mesh network;

wherein identifying mesh nodes on the mesh network further comprises broadcasting a discovery message that determines whether other mesh nodes are within communication range of the current mesh node;

wherein the discovery message includes an indication of randomly selected portion of the mesh-facing address for the current mesh node for comparison with the same portion of mesh-facing addresses selected by other mesh nodes;

wherein a conflict between the randomly selected portion of the mesh-facing address for the current mesh node and the same portion for another mesh node is resolved by setting both portions to a single common value;

obtaining routing tables corresponding to any neighboring mesh nodes, wherein the routing tables include address allocations made by the neighboring mesh nodes;

selecting a mesh-facing address for a current mesh node on the mesh network;

wherein selecting the mesh-facing address for the current mesh node includes comparing a portion of a selected mesh-facing address for the current mesh node with the same portion of a selected mesh-facing address of each of the identified mesh nodes on the mesh network;

selecting a client subnet range of addresses that corresponds to the current mesh node; and

notifying other mesh nodes on the mesh network of the client subnet range selection by the current mesh node.

15. The computer-readable medium of claim 14, wherein notifying other mesh nodes further comprises broadcasting an allocation message to the neighboring mesh nodes, wherein the allocation message includes and indicator that the client subnet range has been allocated by the current mesh node.

16. The computer-readable medium of claim 15, further comprising broadcasting an additional allocation message to the neighboring mesh nodes after a selected interval of time has elapsed, wherein the additional allocation message includes and indicator that the client subnet address is in use by the current mesh node.

17. A system for cooperatively managing a routed IP address space in the absence of managed network services, comprising:

a mesh network having mesh nodes included therein; and

a logical server distributed across the mesh network that is configured to execute computer-executable instructions on each of the mesh nodes, the computer-executable instructions comprising;

identifying neighboring mesh nodes on the mesh network by broadcasting a discovery message that determines whether other mesh nodes are within communication range of the current mesh node;

wherein the discovery message includes an indication of a selected portion of the mesh-facing address for the current mesh node for comparison with the same portion of mesh-facing addresses selected by other mesh nodes;

wherein the selected portion of the mesh-facing address is randomly selected;

wherein the discovery message includes an indication of randomly selected portion of the backbone address for the current mesh node for comparison with the same portion of backbone addresses selected by other mesh nodes;

wherein a conflict between the randomly selected portion of the backbone address for the current mesh node and the same portion for another mesh node is resolved by setting both portions to a single common value;

obtaining routing tables corresponding to any neighboring mesh nodes, wherein the routing tables include address allocations made by the neighboring mesh nodes;

selecting a mesh-facing address for a current mesh node on the mesh network;

selecting a client subnet range of addresses that corresponds to the current mesh node; and

notifying other mesh nodes on the mesh network of the client subnet range selection by broadcasting an allocation message to the neighboring mesh nodes, wherein the allocation message includes and indicator that the client subnet range has been allocated by the current mesh node.

18. The system of claim 17, wherein the logical server is further configured to broadcast an additional allocation message to the neighboring mesh nodes after a selected interval of time has elapsed, wherein the additional allocation message includes and indicator that the client subnet address is in use by the current mesh node.

19. The system of claim 17, wherein the computer-executable instructions further comprise:

selecting an unused subnet value from the client subnet range in response to a client routing request; and

determining the number of remaining unused subnet values after the client routing request, wherein an additional client subnet range is allocated by the current mesh node when the number of remaining unused subnet values is under a specified threshold.

20. The system of claim 17, wherein the computer-executable instructions further comprise:

receiving a notification of an allocated client subnet address from another cooperative agent;

determining the relevance of the received notification;

forwarding the received notification to neighboring cooperative agents when the received notification is determined as relevant; and

discarding the received notification when the received notification is determined as irrelevant.

21. The system of claim 20, wherein relevance of the received notification is determined according to at least one of a timestamp included in the received notification and a hop count associated with the received notification.