DISCOVERY AND AUTHENTICATION SCHEME FOR WIRELESS MESH NETWORKS

• US 20070189249A1
• Filed: 05/02/2006
• Published: 08/16/2007
• Est. Priority Date: 05/03/2005
• Status: Active Grant

• Current Assignee: SRI International, Inc.
• Original Assignee: PacketHop, Inc. (SRI International, Inc.)
• Inventors: Gonzalez, Jose, Burke, Scott, Gurevich, David
• Granted Patent: US 7,814,322 B2
• Time in Patent Office: Days
• US Class Current: 370/338
• CPC Class Codes: H04L 45/20 Hop count for routing purposes, e.g. TTL
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04L 63/061 for key exchange, e.g. in peer-to-peer networks cryptographic mechanisms or cryptographic arrangements for key agreement H04L9/0838
• CPC Class Codes: H04L 63/0823 using certificates cryptographic mechanisms or cryptographic arrangements for entity authentication involving certificates H04L9/3263
• CPC Class Codes: H04L 63/162 at the data link layer
• CPC Class Codes: H04W 12/041 Key generation or derivation
• CPC Class Codes: H04W 12/043 using a trusted network node as an anchor
• CPC Class Codes: H04W 12/062 Pre-authentication
• CPC Class Codes: H04W 12/068 using credential vaults, e.g. password manager applications or one time password [OTP] applications
• CPC Class Codes: H04W 12/069 using certificates or pre-shared keys
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 8/005 Discovery of network devices, e.g. terminals
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks
• CPC Class Codes: H04W 88/06 adapted for operation in multiple networks or having at least two operational modes, e.g. multi-mode terminals

Abstract

Wireless network devices discover individual mesh nodes and networks of mesh nodes. An association is formed on the basis of peer-to-peer interactions at layer-1, layer-2 and/or higher layers of the Open System Interconnect (OSI) model. In particular, the system uses Beacon, Probe Request, Probe Response, Association Request, Association Response, and Disassociation frames and introduces a new Extensible Mesh Information Element (EMIE) used by mesh nodes to discover, authenticate, and associate with other peer nodes.

Claims

1. A wireless device, comprising:

a processor adapted to operate in both a mesh mode that uses a peer-to-peer based mesh discovery scheme to discover, form and/or dissolve different mesh networks and also at the same time operate as a station service in an infrastructure environment for communicating with Access Points (APs) or operate as an Access Point service in an ad hoc environment for communicating with Stations.

2. The wireless device according to claim 1 wherein the processor is further adapted to identify a peer mesh node and then negotiate operating as the AP service or the Station service when further negotiating association with the peer mesh node.

3. The wireless device according to claim 2 wherein the processor upon successfully associating with a peer node creates a peer-to-peer link connectivity context independent of any mesh network-wide connectivity context and that is indexed by an address of the associated peer node.

4. The wireless device according to claim 2 wherein the processor when operating as the Station service passively scans by searching for Beacon frames from AP nodes or mesh nodes, the processor performing a standard 802.11 association and authentication when a Beacon frame is received from an AP node that qualifies for association and performing a mesh node association and authentication when a mesh Beacon frame is received from a mesh node that qualifies for mesh association.

5. The wireless device according to claim 4 wherein the processor when operating as the station service also actively scans by sending 802.11 probe request frames and mesh probe request frames, the processor conducting a 802.11 authentication when probe response frames are received back that contain Service Station Identifiers (SSID) and conducting a mesh authentication and association when mesh probe response frames are received back that contain a Extensible Mesh Information Element (EMIE) and qualify for association.

6. The wireless device according to claim 2 wherein the processor when operating AP service actively scans by sending Beacon frames to enable both standard 802.11 Station nodes and mesh nodes to locate the AP service by passive scanning, the AP service also responding to Probe request frames from standard 802.11 Station nodes and Mesh probe request frames from mesh nodes.

7. The wireless device according to claim 1 wherein the mesh discovery scheme operated by the processor sends messages containing Extensible Mesh Information Elements (EMIEs) that convey information used by other mesh nodes for mesh discovery, authentication, and association operations.

8. The wireless device according to claim 7 wherein the EMIE includes at least one of the following:

an APCounter value that identifies a number of AP nodes associated with mesh nodes in a wireless mesh network;

a HopCounter value that identifies a number of wireless hops between a peer mesh node associated to a nearest AP node;

a MeshCounter value that identifies a number of nodes in a locally connected wireless mesh network;

or

an AssociationCounter value that identifies a number of directly connected peer mesh nodes.

9. The wireless device according to claim 1 including an association table that maintains mesh link association contexts that are indexed according to a transmitting peer mesh node address for managing a peer-to-peer mesh node connection and also maintains network wide association contexts that are indexed according to Service Set Identifiers (SSIDs).

10. A method for discovering other wireless nodes, comprising:

conducting a mesh discovery operation that discovers Access Point (AP) nodes, Station nodes, or mesh nodes;

scanning on different channels to discover the different AP nodes, Station nodes, and mesh nodes according to what AP nodes, station nodes, and mesh nodes are part of a current mesh association; and

using a mesh association operation to then determine when to associate with any newly discovered AP nodes, Station nodes, or mesh nodes.

11. The method according to claim 10 including using peer-to-peer source and destination addresses to provide a link connectivity context to associate with the mesh nodes and using a network wide connectivity context to associate with the AP nodes and the Station nodes.

12. The method according to claim 10 including operating in an AP mode, Station mode, or mesh mode while discovering and authenticating different peer nodes.

13. The method according to claim 12 including while currently operating in the mesh mode and associated with either AP or mesh nodes:

sending AP/STA probe requests and mesh probe requests on each configured channel;

discovering peer nodes by listening for AP/STA probe responses, mesh probe responses, AP/STA beacons and mesh beacons on each of the configured channels; and

using the mesh association operation after scanning all configured channels to determine which discovered peer nodes to associate with.

14. The method according to claim 12 including when currently operating in the mesh mode and associated with an AP node:

sending only mesh probe request frames on a current channel;

discovering peers by listening for mesh probe responses only on the current channel; and

using the mesh association operation to then determine which discovered peers to associate with.

15. The method according to claim 12 including when currently operating in the mesh mode and associated with one or more other mesh nodes:

sending both AP/STA probe requests and mesh probe requests on a current channel and then on any other configured channels;

listening for AP/STA probe responses, mesh probe responses, AP/STA Beacons, and mesh Beacon frames on the current channel and then on any other configured channels; and

using the mesh association operation to then determine which discovered peer nodes to associate with when one or more mesh probe responses are detected.

16. The method according to claim 10 including when currently operating in the mesh mode and associated with one of the AP nodes and at least one other mesh node:

sending only mesh probe requests on a current channel;

listening for mesh probe responses on the current channel; and

using the mesh association operation to determine what discovered peers to associate with when one or more mesh probe responses are detected.

17. The method according to claim 10 wherein the mesh association operation includes:

receiving one or more mesh probe responses that can include any combination of the following values

an APCounter value that identifies a number of AP nodes associated with mesh nodes in a wireless mesh network;

a HopCounter value that identifies a number of wireless hops between a peer mesh node associated to a nearest AP node;

a MeshCounter value that identifies a number of nodes in a locally connected wireless mesh network; and

an AssociationCounter value that identifies a number of directly connected peer mesh nodes;

comparing any of the values received from any of the mesh probe responses; and

associating with the peer nodes according to the comparison.

18. The method according to claim 17 including:

associating different priorities to whatever APCounter value, HopCounter value, MeshCounter value and AssociationCounter values are contained in the mesh probe responses; and

associating with the peer nodes according to the priorities.

20. A mesh node, comprising:

a processor that operates as a Station service for scanning, authenticating and associating with Access Point (AP) nodes and mesh nodes; and

the processor also operating as an AP service for scanning, authenticating, and associating with Station nodes and mesh nodes.

21. The mesh node according to claim 20 wherein the processor is configured when operating the Station service or AP service or to check for either a Service Set Identifier (SSID) or an Extensible Mesh Information Element (EMIE) in received discovery messages and operate in a conventional 802.11 mode when the discovery messages include the SSID and operate in a mesh mode when the discovery messages include the EMIE.

22. The mesh node according to claim 20 wherein the processor is configured when operating the Station service or the AP service to send both 802.11 probe request frames and mesh probe request frames.

23. The mesh node according to claim 20 wherein the processor is configured to use a random token negotiated with a peer to determine whether to operate as the AP service or the STA service.

24. The mesh node according to claim 20 wherein the processor is configured to associate with other peer nodes according to different factors associated with layer-1, layer-2 and layer-3 of the Open System Interconnect (OSI) model.

25. The mesh node according to claim 24 wherein the processor conducts different layer-1 channel scans for discovering other peer nodes according to current associations with other nodes.

26. The mesh node according to claim 24 wherein the processor associates with the peer nodes according to different layer-2 connectivity information and/or layer-3 forwarding information received in Extensible Mesh Information Elements (EMIEs) from the peer nodes.

27. The mesh node according to claim 25 wherein the processor also associates with the peer nodes according to preconfigured policy values associated with the peer nodes.

28. The mesh node according to claim 20 including dynamically configuring mutually reversible authenticator and supplicant authentication services with peer nodes according to the type of discovered peer nodes and peer addresses independently of any pre-existing centralized mesh authentication infrastructure.

29. The mesh node according to claim 28 including conducting authentication with the peer nodes using a single authentication operation between the dynamically configured supplicant and the dynamically configured authenticator.

30. A method for authenticating devices in a wireless network, comprising:

dynamically configuring mutually reversible authenticator and supplicant services with peers according to the type of peers and peer addresses discovered in the wireless network independently of any pre-existing centralized mesh authentication infrastructure.

31. The method according to claim 30 including conducting authentication with the peers using a single authentication operation between the dynamically configured authenticator and the dynamically configured supplicant.

32. The method according to claim 30 including:

discovering different Access Point (AP) peers, Station peers, or mesh peers in the wireless network;

dynamically operating a Station service as an authenticator for authenticating with discovered AP peers;

dynamically operating an AP service as a supplicant for authenticating with discovered Station peers.

33. The method according to claim 32 including:

negotiating with discovered mesh peers for operating as the authenticator or the supplicant; and

dynamically configuring the Station service or the AP service for authenticating with the discovered mesh peer according to the negotiation.

34. The method according to claim 33 including negotiating with the mesh peers to operate as the authenticator or the supplicant according to which has the highest Media Access Control (MAC) address.

35. The method according to claim 30 including operating in a mesh mode after completing the authentication using the AP or Station service to authenticate peers.

36. The method according to claim 35 including generating or receiving Pairwise Master Key Identifiers (PMKIDs) for individual peer-to-peer connections with the peers according to local and peer addresses.

37. The method according to claim 36 including generating the PMKID value according to which local or peer has a higher MAC address.

38. The method according to claim 35 wherein computing the PMKIDs according to the following:

PMKID=HASH(PMK, “

PMK Name”

∥

MAX(AA|SPA)∥

MIN(AA|SPA)),

where PMK is the Pairwise Master Key, AA is the Authenticator MAC Address, SPA is the Supplicant MAC Address, PMK Name is a character string for the PMK, and HASH is a hashing operation.

39. The method according to claim 30 including pre-configuring individual nodes for generating Pairwise Master Keys (PMKs) and then using the PMKs in the individual nodes to generate a single Pairwise Master Key Identifier (PMKID) for individual peer-to-peer connections and then using the PMKIDs to encrypt data exchanges between the individual peer-to-peer connections.