GATEWAY ADVERTISEMENT IN A WIRELESS MESH

• US 20100214979A1
• Filed: 02/25/2009
• Published: 08/26/2010
• Est. Priority Date: 02/25/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Huitema, Christian, Kuehnel, Thomas W., Karki, Mukesh, Hassan, Amer A., Manchanda, Alok, Mandhana, Taroon, Atas, Yusuf
• Granted Patent: US 8,976,795 B2
• Time in Patent Office: Days
• US Class Current: 370/328
• CPC Class Codes: H04L 41/00 Arrangements for maintenance, administration or management of data switching networks, e.g. of packet switching networks
• CPC Class Codes: H04L 41/0806 for initial configuration or provisioning, e.g. plug-and-play
• CPC Class Codes: H04L 41/0809 Plug-and-play configuration
• CPC Class Codes: H04L 41/0816 the condition being an adaptation, e.g. in response to network events
• CPC Class Codes: H04L 67/51 Discovery or management thereof, e.g. service location protocol [SLP] or web services
• CPC Class Codes: H04L 69/16 Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]
• CPC Class Codes: H04L 69/161 Implementation details of TCP/IP or UDP/IP stack architecture; Specification of modified or new header fields
• CPC Class Codes: H04W 4/02 Services making use of location information
• CPC Class Codes: H04W 4/08 User group management
• CPC Class Codes: H04W 48/16 Discovering, processing access restriction or access information
• CPC Class Codes: H04W 48/17 Selecting a data network PoA [Point of Attachment]
• CPC Class Codes: H04W 8/18 Processing of user or subscriber data, e.g. subscribed services, user preferences or user profiles; Transfer of user or subscriber data
• CPC Class Codes: H04W 80/06 Transport layer protocols, e.g. TCP [Transport Control Protocol] over wireless transmission control protocol/Internet protocol [TCP/IP] or user datagram protocol [UDP] H04L69/16
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

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 in a mesh network comprising at least one gateway to select a default gateway for the computing device, a gateway being a node in the mesh network configured to provide connectivity for other nodes in the mesh network to an external network outside the mesh network, the method comprising:

operating at least one processor of the computing device to;

receive over the mesh network at least one advertisement, each advertisement generated by a node of the mesh network and identifying the node that generated the advertisement as a gateway node in the mesh network such that the at least one advertisement identifies a set comprising at least one gateway node;

select a default gateway for the computing device from the set; and

using the selected default gateway in routing messages for the external network.

2. The method of claim 1, wherein:

each gateway node in the set is associated with at least one characteristic, the at least one characteristic being associated with a path through the mesh network between the identified gateway node and the computing device; and

selecting a default gateway for the computing device from the set comprises selecting the default gateway based on the at least one characteristic associated with each gateway node in the set.

3. The method of claim 2, wherein:

the method further comprises operating at least one processor of the computing device to;

for each gateway node in the set, compute a metric associated with a path through the mesh network between the gateway node and the computing device, wherein the at least one characteristic associated with the gateway node comprises the computed metric.

4. The method of claim 3, wherein:

each advertisement of the at least one advertisement further comprises a value;

computing the metric associated with a path through the mesh network between the gateway node and the computing device further comprises computing the metric based on the value in a received advertisement for the gateway node; and

the method further comprises operating at least one processor of the computing device to;

for a received advertisement, modify the value, producing a modified advertisement; and

forward the modified advertisement over the mesh network.

5. The method of claim 4, wherein the computed metric corresponds to a number of hops traversed in a path between the computing device and an identified gateway.

6. The method of claim 4, wherein the computed metric corresponds to a bandwidth of a path between the computing device and an identified gateway.

7. The method of claim 4, wherein the computed metric corresponds to a latency of a path between the computing device and an identified gateway.

8. The method of claim 4, wherein:

the method further comprises operating at least one processor of the computing device to;

store in a routing table a plurality of gateway nodes in the set and the computed metric associated with a path to each gateway node stored in the routing table;

repeatedly update the routing table in response to changed conditions in the mesh network; and

based on the stored metrics, repeatedly select a gateway node for use by the computing device from among the stored identified gateway nodes in the routing table.

9. A method of operating a computing device configured as a gateway in a mesh network, the mesh network comprising a plurality of computing devices configured as mesh nodes, the method comprising:

operating at least one processor of the computing device to;

generate an advertisement, the advertisement indicating that the computing device is configured as a gateway; and

transmit the advertisement over the mesh network.

10. The method of claim 9, wherein transmitting the advertisement over the mesh network comprises broadcasting the advertisement to the mesh nodes.

11. The method of claim 10, wherein the broadcasting is repeatedly performed at a periodic interval.

12. The method of claim 11, wherein the broadcasting is performed according to an ICMP protocol.

13. The method of claim 11, wherein the advertisement further comprises a value of the periodic interval.

14. The method of claim 9, wherein:

the gateway is connected to an external network separate from the mesh network;

the gateway routes network packets between mesh nodes and other nodes on the external network; and

the advertisement further comprises a route for reaching a specific node on the external network.

15. The method of claim 9, wherein:

the advertisement further comprises the network address of a DNS server.

16. A method of operating a mesh network comprising at least one gateway node, the gateway node being a computing device in the mesh network configured as a gateway, the mesh network further comprising a plurality of mesh nodes, the method comprising:

in each of the at least one gateway nodes, generating at least one advertisement;

propagating through the plurality of mesh nodes the at least one advertisement; and

in each mesh node of at least a portion of the plurality of mesh nodes, selecting a node as a default gateway based on a characteristic associated with each of the at least one gateway nodes, each characteristic associated with a gateway of the at least one gateway nodes being associated with a path between the mesh node and the gateway node.

17. The method of claim 16, wherein:

the characteristic associated with each gateway of the at least one gateway nodes is at least partly based on a hop value indicating the number of hops in the path between the mesh node and the gateway node; and

propagating through the plurality of mesh nodes the at least one generated advertisement comprises;

broadcasting the at least one generated advertisement from the at least one gateway node; and

in each mesh node of the plurality of mesh nodes;

receiving the at least one advertisement;

recording the hop value in the at least one advertisement; and

forwarding the at least one advertisement comprising the recorded hop value to at least another mesh node in the plurality of mesh nodes.

18. The method of claim 17, wherein the method further comprises, at each mesh node in the plurality of mesh nodes:

for each advertisement received from a gateway node in the at least one gateway nodes;

computing the characteristic associated with the path between the mesh node and the gateway node based on the hop value comprised in the advertisement; and

adding an identifier for the gateway node and the characteristic associated with the path between the mesh node and the gateway node to a routing table; and

selecting a node as a gateway node further comprises selecting a node as a gateway node based on the gateway node identifiers and the characteristic in the routing table.

19. The method of claim 18, wherein:

at each gateway node in the at least one gateway nodes, broadcasting is performed at a periodic broadcasting interval;

each advertisement further comprises an interval portion indicating the periodic broadcasting interval for the gateway node; and

the method further comprises, at each mesh node in the plurality of mesh nodes, when the mesh node has not received an advertisement from a gateway node within a time period, removing the gateway node from the routing table, the time period being based on the periodic broadcasting interval portion in the advertisement generated by the gateway node.

20. The method of claim 19, wherein the broadcasting is performed according to an ICMP protocol.