System and method for expanding the range of a mesh network

• US 7,715,395 B2
• Filed: 11/24/2004
• Issued: 05/11/2010
• Est. Priority Date: 11/24/2004
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ginchereau, Jason Earl, Erwin, Jeff Baird
• Primary Examiner(s): Trost, IV; William
• Assistant Examiner(s): Shand; Roberta A
• Application Number:
  US10/997,318
• Publication Number:
  US 20060120370A1
• Time in Patent Office: 1,994 Days
• Field of Search: 370/352, 370/392, 370/409, 370/351, 370/400, 370/401, 370/408, 370/463
• US Class Current: 370/392
• 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/122 by minimising distances, e.g. by selecting a route with minimum of number of hops
• CPC Class Codes: H04L 45/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04L 45/124 using a combination of metrics
• CPC Class Codes: H04L 45/20 Hop count for routing purposes, e.g. TTL
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing

Abstract

A system and method of expanding the range of a mesh network by determining whether a route through a local Internet service provider is an optimal path between two nodes. If the route through a local Internet service provider is an optimal path, a routing table is updated to include the optimal path so that mesh nodes on the mesh network have access to the routing table.

Claims

1. A system for expanding a range of a mesh network by using an internet service provider to facilitate a hop during data packet routing, the system comprising:

a processor; and

a memory having computer executable instructions configured for;

providing a first egress mesh node that is configured to communicate with an internet service provider and provide routing information for routing a data packet originating from an internal mesh node, wherein the first egress mesh node and the internal mesh node are located in a first portion of the mesh network;

providing a second egress mesh node in a second portion of the mesh network, wherein the second egress mesh node is configured to communicate with the internet service provider;

generating, at the first egress mesh node, an egress point descriptor, wherein the egress point descriptor indicates a route to utilize the internet service provider as a node in the mesh network to provide a first hop from the first egress mesh node to the internet service provider and to hop the data packet from the internet service provider to the second egress mesh node without entering the internet facilitated by the internet service provider, wherein the egress point descriptor includes,

a name of an internet service provider,

a gateway internet protocol address, and

trace route information for hopping the data packet from the first egress mesh node to the internet service provider and for hopping the data packet from the internet service provider to the second egress mesh node;

determining, at the first egress mesh node, whether the route indicated by the egress point descriptor is an optimal path for sending the data packet from the internal mesh node to the second egress mesh node by utilizing the internet service provider as a node of the mesh network, wherein determining whether the route indicted by the egress point descriptor is an optimal path for sending the data packet from the internal mesh node to the second egress mesh node by utilizing the internet service provider as a node of the mesh network includes,

comparing the name of the internet service provider of the egress point descriptor with a name of an internet service provider in communication with the first egress mesh node,

comparing the gateway internet protocol address of the egress point descriptor with a gateway internet protocol address of an internet service provider in communication with the first egress mesh node,

determining whether the trace route information indicates an acceptable hop count and latency for hopping the data packet from the first egress mesh node to the internet service provider and for hopping the data packet from the internet service provider to the second egress mesh node,

when the route indicated by the egress point descriptor is the optimal path,

updating a routing table with the optimal path by indicating the internet service provider as a node of the mesh network,

publishing the routing table for access by the internal mesh node,

receiving, at the first egress mesh node, the data packet from the internal mesh node for routing according to the optimal path, and

routing the data packet by hopping the data packet from the first egress mesh node to the internet service provider and by hopping the data packet from the internet service provider to the second egress mesh node without entering the Internet facilitated by the internet service provider.

2. The system of claim 1, wherein comparing the gateway internet protocol address of the egress point descriptor with a gateway internet protocol address of an internet service provider in communication with the first mesh node includes identifying internet protocol addressing rules and subnet rules of the internet service provider identified in the egress point descriptor.

3. The system of claim 1, wherein the egress point descriptor further includes an indication of performance capabilities.

4. The system of claim 3, wherein the performance capabilities includes at least one member of a group comprising:

an indication of upload capabilities and an indication of download capabilities.

5. The system of claim 3, wherein the performance capabilities includes an indication of current traffic volume.

6. The system of claim 3, wherein the performance capabilities includes an indication of interference.

7. The system of claim 3, wherein the performance capabilities includes an indication of load.

8. A computer implemented method for expanding a range of a mesh network by using an internet service provider to facilitate a hop during data packet routing, the method comprising:

providing a first egress mesh node that is configured to communicate with an internet service provider and provide routing information for routing a data packet originating from an internal mesh node, wherein the first egress mesh node and the internal mesh node are located in a first portion of the mesh network;

providing a second egress mesh node in a second portion of the mesh network, wherein the second egress mesh node is configured to communicate with the internet service provider;

generating, at the first egress mesh node, an egress point descriptor, wherein the egress point descriptor indicates a route to utilize the internet service provider as a node in the mesh network to provide a first hop from the first egress mesh node to the internet service provider and to hop the data packet from the internet service provider to the second egress mesh node without entering the internet facilitated by the internet service provider, wherein the egress point descriptor includes,

a name of an internet service provider,

a gateway internet protocol address, and

trace route information for hopping the data packet from the first egress mesh node to the internet service provider and for hopping the data packet from the internet service provider to the second egress mesh node;

determining, at the first egress mesh node, whether the route indicated by the egress point descriptor is an optimal path for sending the data packet from the internal mesh node to the second egress mesh node by utilizing the internet service provider as a node of the mesh network, wherein determining whether the route indicted by the egress point descriptor is an optimal path for sending the data packet from the internal mesh node to the second egress mesh node by utilizing the internet service provider as a node of the mesh network includes,

comparing the name of the internet service provider of the egress point descriptor with a name of an internet service provider in communication with the first egress mesh node,

comparing the gateway internet protocol address of the egress point descriptor with a gateway internet protocol address of an internet service provider in communication with the first egress mesh node,

determining whether the trace route information indicates an acceptable hop count and latency for hopping the data packet from the first egress mesh node to the internet service provider and for hopping the data packet from the internet service provider to the second egress mesh node,

when the route indicated by the egress point descriptor is the optimal path,

updating a routing table with the optimal path by indicating the internet service provider as a node of the mesh network,

publishing the routing table for access by the internal mesh node,

receiving, at the first egress mesh node, the data packet from the internal mesh node for routing according to the optimal path, and

routing the data packet by hopping the data packet from the first egress mesh node to the internet service provider and by hopping the data packet from the internet service provider to the second egress mesh node without entering the Internet facilitated by the internet service provider.

9. The computer implemented method of claim 8, wherein comparing the gateway internet protocol address of the egress point descriptor with a gateway internet protocol address of an internet service provider in communication with the first mesh node includes identifying internet protocol addressing rules and subnet rules of the internet service provider identified in the egress point descriptor.

10. The computer implemented method of claim 8, wherein the egress point descriptor further includes an indication of performance capabilities.

11. The computer implemented method of claim 10, wherein the performance capabilities includes at least one member of a group comprising:

an indication of upload capabilities and an indication of download capabilities.

12. The computer implemented method of claim 10, wherein the performance capabilities includes an indication of current traffic volume.

13. The computer implemented method of claim 10, wherein the performance capabilities includes an indication of interference.

14. The computer implemented method of claim 10, wherein the performance capabilities includes an indication of load.

15. A computer-readable storage medium having computer executable instructions for expanding a range of a mesh network by using an internet service provider to facilitate a hop during data packet routing, the instructions comprising:

providing a first egress mesh node that is configured to communicate with an internet service provider and provide routing information for routing a data packet originating from an internal mesh node, wherein the first egress mesh node and the internal mesh node are located in a first portion of the mesh network;

providing a second egress mesh node in a second portion of the mesh network, wherein the second egress mesh node is configured to communicate with the internet service provider;

generating, at the first egress mesh node, an egress point descriptor, wherein the egress point descriptor indicates a route to utilize the internet service provider as a node in the mesh network to provide a first hop from the first egress mesh node to the internet service provider and to hop the data packet from the internet service provider to the second egress mesh node without entering the internet facilitated by the internet service provider, wherein the egress point descriptor includes,

a name of an internet service provider,

a gateway internet protocol address, and

trace route information for hopping the data packet from the first egress mesh node to the internet service provider and for hopping the data packet from the internet service provider to the second egress mesh node;

determining, at the first egress mesh node, whether the route indicated by the egress point descriptor is an optimal path for sending the data packet from the internal mesh node to the second egress mesh node by utilizing the internet service provider as a node of the mesh network, wherein determining whether the route indicted by the egress point descriptor is an optimal path for sending the data packet from the internal mesh node to the second egress mesh node by utilizing the internet service provider as a node of the mesh network includes,

comparing the name of the internet service provider of the egress point descriptor with a name of an internet service provider in communication with the first egress mesh node,

comparing the gateway internet protocol address of the egress point descriptor with a gateway internet protocol address of an internet service provider in communication with the first egress mesh node,

determining whether the trace route information indicates an acceptable hop count and latency for hopping the data packet from the first egress mesh node to the internet service provider and for hopping the data packet from the internet service provider to the second egress mesh node,

when the route indicated by the egress point descriptor is the optimal path,

updating a routing table with the optimal path by indicating the internet service provider as a node of the mesh network,

publishing the routing table for access by the internal mesh node,

receiving, at the first egress mesh node, the data packet from the internal mesh node for routing according to the optimal path, and

routing the data packet by hopping the data packet from the first egress mesh node to the internet service provider and by hopping the data packet from the internet service provider to the second egress mesh node without entering the Internet facilitated by the internet service provider.

16. The computer-readable storage medium of claim 15, wherein comparing the gateway internet protocol address of the egress point descriptor with a gateway internet protocol address of an internet service provider in communication with the first mesh node includes identifying internet protocol addressing rules and subnet rules of the internet service provider identified in the egress point descriptor.

17. The computer-readable storage medium of claim 15, wherein the egress point descriptor further includes an indication of performance capabilities.

18. The computer-readable storage medium of claim 17, wherein the performance capabilities includes at least one member of a group comprising:

an indication of upload capabilities and an indication of download capabilities.

19. The computer-readable storage medium of claim 17, wherein the performance capabilities includes an indication of current traffic volume.

20. The computer-readable storage medium of claim 17, wherein the performance capabilities includes an indication of interference.