Automatic network address assignment in a wireless mesh

• US 8,385,230 B2
• Filed: 02/25/2009
• Issued: 02/26/2013
• Est. Priority Date: 02/25/2009
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Kuehnel, Thomas W., Manchanda, Alok, Mandhana, Taroon, Hassan, Amer A., Karki, Mukesh, Huitema, Christian, Atas, Yusuf
• Primary Examiner(s): Sefcheck, Gregory
• Assistant Examiner(s): Rivas, Salvador E
• Application Number:
  US12/392,777
• Publication Number:
  US 20100214959A1
• Time in Patent Office: 1,462 Days
• Field of Search: None
• US Class Current: 370/255
• CPC Class Codes: H04L 61/103 across network layers, e.g. resolution of network layer into physical layer addresses or address resolution protocol [ARP]
• CPC Class Codes: H04L 61/4511 using domain name system [DNS]
• CPC Class Codes: H04L 61/5046 Resolving address allocation conflicts; Testing of addresses testing when self-assigning an address H04L61/5092
• 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: H04W 8/26 Network addressing or numbering for mobility support

Abstract

A computing environment containing a mesh network that is adapted to provide a reliable transport mechanism over which services may be delivered. Nodes of the mesh can automatically select routable addresses without conflicts, which allows nodes of the mesh to be accessed, even as the mesh changes through the addition or deletion of nodes. Also, nodes communicate with a protocol that supports service advertisements. These advertisements can identify mesh nodes that supply services, such as file or print servers, for which devices that have not yet connected to the network may be searching. Advertisements can also identify services to be used by nodes in the network, allowing, for example, a node to select a gateway providing a reliable connection to an external network. The mesh network can be used as a transport for communication using protocols, such as TCP/IP, that generally exhibit poor performance when using unreliable transports.

Claims

1. A method of operating a computing device configured as a node of a mesh network to select a network address for the computing device that is unique on the mesh network, the method comprising an act of:

operating at least one processor on the computing device to select a network address by executing computer-executable instructions performing acts of;

(A) conditionally selecting a network address based on whether a network address for the computing device is stored in a portion of non-volatile memory on the computing device, the conditionally selecting comprising;

when a network address for the computing device is stored in the portion of non-volatile memory on the computing device, selecting the stored network address as the network address for the computing device;

when a network address for the computing device is not stored in the portion of non-volatile memory on the computing device;

(1) generating a first portion of a network address based on an identifier associated with the computing device, where the first portion comprises a suffix for a network address, where the identifier comprises a MAC address associated with the computing device, and where the generating comprises computing a hash value based on the MAC address; and

(2) selecting as the network address for the computing device a network address based on the generated first portion and on a second portion associated with the network;

(B) detecting if the selected network address conflicts with another network address assigned to a computing device in the mesh network;

(C) when the selected network address does not conflict;

storing the selected network address in the portion of non-volatile memory; and

(D) when the selected network address does conflict;

generating a different first portion of a network address;

selecting as the selected network address for the computing device a network address based on the different first portion and the second portion associated with the network; and

performing acts (B) and either (C) or (D) on the selected network address.

2. The method of claim 1, wherein the detecting if the selected network address conflicts with another network address comprises detecting if the selected network address is the same as another network address assigned to a computing device in the mesh network.

3. The method of claim 2, wherein the second portion comprises a network address prefix.

4. The method of claim 3, wherein the prefix comprises an identifier of a subnet for the mesh network.

5. The method of claim 1, wherein generating a different first portion of a network address comprises incrementing the suffix generated in act (1).

6. The method of claim 1, wherein generating a different first portion of a network address comprises obtaining from a user of the computing device a random number for a suffix.

7. The method of claim 1, wherein act (D) further comprises communicating using the selected network address with a computing device not on the mesh network.

8. The method of claim 1, wherein act (D) further comprises using the selected network address to communicate a service advertisement to at least one computing device on the mesh network, wherein the service advertisement indicates an availability of a service offered by the computing device.

9. A computer-readable storage medium that does not consist of a transitory signal and that comprises computer-executable instructions that, when executed on at least one processor of a computing device configured as a node of a mesh network, implement a method of operating the computing device to select a network address for the computing device that is unique on the mesh network, the method comprising acts of:

(A) conditionally selecting a network address based on whether a network address for the computing device is stored in a portion of non-volatile memory on the computing device, the conditionally selecting comprising;

when a network address for the computing device is stored in the portion of non-volatile memory on the computing device, selecting the stored network address as the network address for the computing device; and

when a network address for the computing device is not stored in the portion of non-volatile memory on the computing device;

(1) generating a first portion of a network address based on an identifier associated with the computing device, where the first portion comprises a suffix for a network address, where the identifier comprises a MAC address associated with the computing device, and where the generating comprises computing a hash value based on the MAC address; and

(2) selecting as the network address for the computing device a network address based on the generated first portion and on a second portion associated with the network;

(B) detecting if the selected network address conflicts with another network address assigned to a computing device in the mesh network;

(C) when the selected network address does not conflict;

storing the selected network address in the portion of non-volatile memory; and

(D) when the selected network address does conflict;

generating a different first portion of a network address;

selecting as the selected network address for the computing device a network address based on the different first portion and the second portion associated with the network; and

performing acts (B) and either (C) or (D) on the selected network address.

10. The computer-readable storage medium of claim 9, wherein the detecting if the selected network address conflicts with another network address comprises detecting if the selected network address is the same as another network address assigned to a computing device in the mesh network by issuing a gratuitous Address Resolution Protocol reply.

11. The computer-readable storage medium of claim 9, wherein the second portion comprises a network address prefix.

12. The computer-readable storage medium of claim 11, wherein the prefix comprises an identifier of a subnet for the mesh network, the identifier of a subnet being in a range of subnet identifiers allocated for private network addresses.

13. The computer-readable storage medium of claim 9, wherein generating a different first portion of a network address comprises incrementing the suffix generated in act (1).

14. A method of operating a mesh network, the method comprising:

selecting a network address for each of a plurality of computing devices configured as nodes on the network, the selected network address for each computing device being unique on the mesh network, the selecting comprising for each computing device, operating at least one processor on the computing device to select the network address by executing computer-executable instructions performing acts of;

(A) generating a first portion of a network address based on an identifier associated with the computing device; and

(B) selecting as the network address for the computing device a network address based on the generated first portion and on a second portion associated with the network;

(C) detecting if the selected network address conflicts with another network address assigned to a different computing device in the mesh network;

(D) when the selected network address does conflict;

(1) generating a different first portion of a network address;

(2) selecting as the selected network address for the computing device a network address based on the different first portion and the second portion associated with the network; and

(3) performing acts (C) and (D) on the selected network address; and

(E) communicating using the selected network address, the communicating comprising receiving a network packet addressed to the selected network address, wherein;

act (A) comprises generating a suffix for a network address by computing a hash value based on a MAC address associated with the computing device;

generating a different first portion of a network address in act (1) comprises incrementing the suffix generated in act (A); and

when a network address conflict is detected in act (D) by the computing device and by the different computing device with the conflicting address, acts (1), (2), and (3) are performed on only one of the computing device and the different computing device, based on the value of the MAC address associated with the one of the computing device and the different computing device.

15. The method of claim 14, wherein detecting if the network address conflicts with another network address comprises detecting if the network address is the same as another network address assigned to a computing device in the mesh network.

16. The method of claim 15, wherein:

the first portion comprises a network address suffix, the suffix comprising an identifier of a subnet for the mesh network;

the second portion comprises a network address prefix; and

the identifier associated with the computing device is a MAC address.