Multiple wireless spanning tree protocol for use in a wireless mesh network

• US 7,606,178 B2
• Filed: 02/10/2006
• Issued: 10/20/2009
• Est. Priority Date: 05/31/2005
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Kruys, Jan, Kumar, Rajneesh, Rahman, Shahriar I.
• Primary Examiner(s): Moe; Aung S
• Assistant Examiner(s): ELLIOTT IV, BENJAMIN H
• Application Number:
  US11/351,853
• Publication Number:
  US 20060268749A1
• Time in Patent Office: 1,348 Days
• Field of Search: 370/256, 370/395.31, 370/395.5, 370/408, 370/254, 370/255, 370/328, 370/395.21, 370/395.53, 370/338, 370/389, 455/403, 455/445, 455/452.2
• US Class Current: 370/256
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/18 Loop-free operations
• CPC Class Codes: H04L 45/306 Route determination based on the nature of the carried application
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering
• CPC Class Codes: H04L 47/15 in relation to multipoint traffic arrangements for broadcast or multicast in data networks H04L12/18
• CPC Class Codes: H04L 47/24 Traffic characterised by specific attributes, e.g. priority or QoS
• CPC Class Codes: H04W 28/021 in wireless networks with changing topologies, e.g. ad-hoc networks self-organizing networks H04W84/18
• CPC Class Codes: H04W 28/0236 radio quality, e.g. interference, losses or delay
• CPC Class Codes: H04W 28/08 Load balancing or load distribution transferring a connection for handling the traffic H04W36/22; wireless traffic scheduling H04W72/12
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 8/04 Registration at HLR or HSS [Home Subscriber Server]
• CPC Class Codes: H04W 84/12 WLAN [Wireless Local Area Networks]
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

An apparatus for, a method of, and a computer carrier medium carrying code to cause a processor to execute a method. The method includes running a plurality of instances of a wireless spanning tree protocol in a wireless mesh node, each instance substantially conforming to the IEEE 802.1 standard. Running an instance of wireless spanning tree protocol including the wireless mesh point wirelessly transmitting BPDU information to other wireless mesh points of the network or wirelessly receiving BPDU information from other wireless mesh points, the BPDU information encapsulated in one or more control/management frames, e.g., beacon or probe response frames of a wireless network standard, the BPDU information relating to a spanning tree topology for the instance.

Claims

1. A method in a first mesh point of a mesh of wireless mesh points (a “

wireless mesh network”

) in a wireless network, the method comprising;

establishing and/or maintaining, in collaboration with other wireless mesh points, a plurality of wireless spanning tree topologies in the wireless mesh network, the wireless mesh network substantially conforming to a wireless network standard, the wireless network standard providing a mechanism for a wireless network entity to wirelessly communicate with other wireless network entities using control/management frames for the exchange of wireless network information, the establishing and/or maintaining by running a respective plurality of instances (“

WSTP instances”

) of a wireless spanning tree protocol that substantially conforms to a standard IEEE 802.1 spanning tree protocol, each WSTP instance defining a corresponding wireless spanning tree topology including a corresponding root wireless mesh point,

wherein running a WSTP instance in the first wireless mesh point includes;

maintaining information on the spanning tree topology corresponding to the WSTP instance, the corresponding spanning tree topology being for a corresponding set of wireless mesh points that includes the first wireless mesh point, the corresponding spanning tree topology being for wirelessly communicating among the corresponding set of wireless mesh points, the maintained information including the identity of the corresponding root wireless mesh point for the corresponding spanning tree topology;

wirelessly sending a control/management frame including an indication that path cost information is encapsulated the control/management frame with the indication encapsulating the path cost information in the form of at least one path cost information element, and

as a result of receiving a control/management frame, ascertaining if the received control/management frame encapsulate path cost information, and if there is encapsulated path cost information, updating the maintained information on the corresponding spanning tree topology, and accordingly modifying any path cost information element for sending in a path-cost-information-encapsulating control/management frame,

wherein each root wireless mesh point is not required to have a wired network interface, and

wherein each path cost information element includes a path cost designed for wireless communication that has more than one possible value between two mesh points that are connectable, and that may include a bridging protocol data unit (“

BPDU”

) that substantially conforms to a standard IEEE 802.1 spanning tree protocol BPDU, but with a path cost different than a standard IEEE 802.1 spanning tree protocol BPDU path cost in that the path cost is designed for wireless communication and has more than one possible value between two mesh points that are connectable.

2. A method as recited in claim 1, wherein the control/management frames include beacon and probe response frames, such that the wireless network standard provides a mechanism for wireless network entities to wirelessly transmit beacon or probe response frames to other wireless network entities to advertise the radio characteristics of the wireless network entity,

such that in the running of a WSTP instance in a particular wireless mesh point,

the wirelessly sending a control/management frame includes wirelessly sending a beacon frame and, in the case a probe request frame was received that includes a bridging information request, a probe response frame, the beacon and probe response frame including an indication that path cost information is encapsulated, and that further encapsulates at least one path information element that substantially conforms to IEEE standard 802.1 spanning tree protocol BPDU information, but with a path cost that can take on multiple values between two mesh points that are connectable and that is calculated according to wireless information,

and such that in the running of a WSTP instance in a particular wireless mesh point,

as a result of receiving a beacon frame or probe response frame, ascertaining if the received beacon or probe response frame encapsulate path cost information, and if there is encapsulated path cost information, updating the maintained information on the corresponding spanning tree topology, and accordingly modifying any path cost information for sending in a path cost information-encapsulating beacon frame and probe response frame.

3. A method as recited in claim 2, wherein the maintained information includes a unique identifier for the corresponding spanning tree topology, and wherein the path cost information includes an indication of the identity of the spanning tree topology.

4. A method as recited in claim 2, wherein the root mesh point of at least one of the spanning tree topologies corresponding to the WSTP instances has an uplink to a first wired network.

5. A method as recited in claim 2, wherein the first wireless mesh point has an uplink to a first wired network.

6. A method as recited in claim 2, wherein at least two of the spanning tree topologies corresponding to the WSTP instances have the same root tree mesh point.

7. A method as recited in claim 6, wherein the first wireless mesh point is the root mesh point of the spanning tree topologies of the WSTP instances that have the same root tree mesh point.

8. A method as recited in claim 7, wherein first wireless mesh point has an uplink to a first wired network.

9. A method as recited in claim 6, wherein the root mesh point of the spanning tree topologies of the WSTP instances that have the same root tree mesh point has an uplink to a first wired network.

10. A method as recited in claim 6,

wherein each of the WSTP instances that have the same root tree mesh point uses a different path cost criterion designed for wireless communication that can take on multiple values for a wireless link between two wireless mesh points that are connectable.

11. A method as recited in claim 10, wherein the different path cost criteria are selected so that traffic is wirelessly transported between mesh points via different ones of the wireless spanning tree topologies of the WSTP instances that have the same root tree mesh point with different qualities of service (QoS).

12. A method as recited in claim 6, wherein traffic in the wireless network includes traffic for a plurality of virtual local area networks (“

VLANs”

), with one VLAN per spanning tree topology of the WSTP instances that have the same root tree mesh point.

13. A method as recited in claim 12, including trunking using one of the set of trunking mechanisms consisting of Inter-Switch Link (ISL) trunking and IEEE 802.1Q trunking.

14. A method as recited in claim 6, wherein traffic is classified into one of a pre-defined set of different classes according to a classification mechanism, wherein a different VLAN is used for each traffic class such that there is one respective WSTP instance of the WSTP instances that have the same root mesh point for each class, with a corresponding spanning tree topology for each class.

15. A method as recited in claim 14, wherein each of WSTP instances uses a distinct respective path cost criterion applicable to the traffic class.

16. A method as recited in claim 14, wherein traffic is classified using one of a subset of the IEEE 802.11e set of classes consisting of Voice, Video, Best Effort, and Background, and wherein the first wireless mesh point runs a respective instance of the WSTP for each class, such that the first wireless mesh point runs at most four instances of the WSTP with the same root mesh point for each of the at most four wireless spanning tree topologies corresponding to the at most four WSTP instances.

17. A method as recited in claim 16, wherein there is one VLAN per class.

18. A method as recited in claim 14, wherein the classification mechanism uses Resource ReSerVation Protocol (RSVP).

19. A method as recited in claim 14, wherein the GARP VLAN Registration Protocol (“

GVRP”

) is used to selectively choose on which VLAN wireless mesh points receive multicast traffic from their respective parents recursively until the root mesh point of the plurality of WSTP instances that have the same root mesh point is reached, such that different classes of multicast traffic are routed via the respective tree topologies of different WSTP instances.

20. A method as recited in claim 6, wherein each Bridge Protocol Data Unit (BPDU) in BPDU information includes an information element that indicates the quality of service (QoS).

21. A method as recited in claim 20, wherein traffic is classified into one of a pre-defined set of different classes according to a classification mechanism, and wherein the first wireless mesh point runs one respective WSTP instance of the WSTP instances that have the same root mesh point for each class, with a corresponding spanning tree topology for each class.

22. A method as recited in claim 21, wherein in addition to the indication of the class in the BPDU information, the path cost information includes an indication of the available admission capacity.

23. A method as recited in claim 22, wherein the path cost information includes an indication of path cost, and wherein the path cost calculated for a link uses the indication of the available admission capacity, the path cost calculated for a link taking one of a plurality of possible values for a link between two wireless mesh points that are connectable.

24. A method as recited in claim 1, wherein at least two root mesh points of at least two of the spanning tree topologies corresponding to the WSTP instances are different.

25. A method as recited in claim 24, wherein the distinct root mesh points of the at least two spanning tree topologies form a mesh of root mesh points as a result of the distinct root mesh points running a master WSTP instance forming a master wireless spanning tree topology, with one of the distinct root mesh points of the at least two spanning tree topologies forming the root mesh point of the master wireless spanning tree topology, such that a hierarchy of WSTP instances is run.

26. A method as recited in claim 24, wherein the at least two distinct root mesh points of the at least two of the spanning tree topologies corresponding to the WSTP instances have uplinks to a first wired network, the method further comprising:

for traffic addressed to an address in the first wired network or beyond, performing load balancing including routing traffic to different root mesh points that have an uplink.

27. A method as recited in claim 26, wherein the load balancing includes routing traffic to different root mesh points that have an uplink according to properties of the respective uplinks.

28. A first wireless mesh point as recited in claim 1, wherein the wireless standard is the IEEE 802.11 wireless LAN standard.

29. A method as recited in claim 1, further comprising, for each WSTP instance, as a result of wirelessly receiving one or more beacon frames from one or more other wireless mesh points of the network, the received beacon frames encapsulating path cost information for the WSTP instance, using the encapsulated path cost information of the instance received in the beacon frames from the other wireless mesh points to discover the next other wireless mesh point in the best path to the root wireless mesh point of the spanning tree topology for that WSTP instance prior to establishing a forwarding radio link with the next other wireless mesh point.

30. A method as recited in claim 1, wherein the encapsulated path cost information for each WSTP instance includes one or more radio parameters for path cost calculation for the path cost between a receiving wireless mesh point and other wireless mesh points for that WSTP instance.

31. A method as recited in claim 30, wherein the path cost for determining the spanning tree topology is a weighted sum of at least two of the included radio parameters.

32. A method as recited in claim 31, wherein the one or more included radio parameters include one or more of the received signal strength, the available transmission power, a measure of mobility of the first wireless mesh point, and a hop count.

33. A method as recited in claim 30, farther comprising, for each WSTP instance:

wirelessly receiving one or more beacon frames or probe response frames from one or more other wireless mesh points of the network, the received beacon or probe response frames encapsulating BPDU information including path costs for that WSTP instance; and

storing as part of the maintained information for the WSTP instance, path costs of encapsulating BPDU information received from other wireless mesh points.

34. A method as recited in claim 30, farther comprising, for each WSTP instance:

storing as part of the maintained information for the WSTP instance, radio path costs for alternate and/or backup links to links in the spanning tree topology for the WSTP instance.

35. A method as recited in claim 2, further comprising, for each WSTP instance:

storing information on dormant alternate and/or backup links for the tree topology of the WSTP instance with other wireless mesh points, the information being part of the maintained information for the corresponding spanning tree topology;

ascertaining whether or not there is a need to use an alternate and/or backup link; and

upon ascertaining the need for a dormant alternate and/or backup link, activating one or more of the dormant alternate and/or backup links according to the stored information.

36. A first wireless mesh point comprising:

a radio transceiver;

a wireless MAC protocol processor coupled to the radio transceiver, such that the radio transceiver and MAC protocol processor combination is able to wirelessly send and receive frames substantially conforming to a wireless network standard; and

a wireless spanning tree protocol processor coupled to the radio transceiver and configured to;

establish a plurality of active spanning tree topologies in a wireless mesh network of a plurality of mesh points, the wireless mesh network substantially conforming to the wireless network standard, the wireless network standard providing a mechanism for a wireless network entity to wirelessly communicate with other wireless network entities using control/management frames for the exchange of wireless network information, the first wireless mesh point, and

maintain information on each topology, each topology specifying the communication pathways between wireless mesh points in the wireless network, each spanning tree topology having a root mesh point, the maintained information including the identity of the root mesh point each topology determined according to a spanning tree protocol that substantially conforms to a standard IEEE 802.1 spanning tree protocol but with a path cost different than a standard IEEE 802.1 spanning tree protocol path cost in that the wireless spanning tree protocol path cost measure is designed for wireless communication and has one of a plurality of possible values for a path between two mesh points that are connectable,

wherein each root wireless mesh point is not required to have a wired network interface,

wherein the establishing of each spanning tree protocol of the plurality includes receiving spanning tree protocol capabilities from other wireless mesh points in control/management frames that encapsulate path cost information as one or more path cost information elements that may include bridge protocol data units (“

BPDUs”

), the path cost information announcing the spanning tree protocol capabilities of the first wireless mesh point for the topology by transmitting control/management frames that encapsulate path cost information as one or more path cost information elements for the topology,

wherein each path cost information element includes the path cost measure designed that has one of a plurality of possible values for a path between two mesh points that are connectable, and

wherein any BPDUs included in the one or more path cost information elements substantially conform to standard IEEE 802.1 spanning tree protocol BPDUs, but with a path cost different than a standard IEEE 802.1 spanning tree protocol BPDU path cost in that the path cost is designed for wireless communication and has one of a plurality of possible values for a path between two mesh points that are connectable.

37. A first mesh point as recited in claim 36, wherein the control/management frames include beacon and probe response frames, and wherein the wireless network standard provides a mechanism for wireless network entities to wirelessly transmit beacon or probe response frames to other wireless network entities to advertise the radio characteristics of the wireless network entity, such that the establishing of each spanning tree protocol of the plurality includes receiving spanning tree protocol capabilities from other wireless mesh nodes in beacon and probe response frames that encapsulate path cost information as at least one path cost information element, and announcing the spanning tree protocol capabilities of the first wireless mesh point for the topology by transmitting beacon frames or probe response frames that encapsulate path cost information as at least one path cost information element for the topology.

38. A first mesh point as recited in claim 37, wherein the maintained information for each spanning tree topology includes a unique identifier for the corresponding spanning tree topology.

39. A first mesh point as recited in claim 37, wherein the path cost information for a spanning tree topology of the plurality of topologies includes an indication of the identity of the spanning tree topology.

40. A first mesh point as recited in claim 37, further comprising:

a network interface to a wired network.

41. A first mesh point as recited in claim 37, wherein at least two of the spanning tree topologies have the same root tree mesh point.

42. A first mesh point as recited in claim 41, wherein traffic is classified into one of a pre-defined set of different classes according to a classification mechanism, such that there is one respective spanning tree topology that has the same root mesh point for each class.

43. A first mesh point as recited in claim 42, wherein each of the respective spanning tree topology is determined using a distinct respective path cost criterion applicable to the traffic class.

44. A first mesh point as recited in claim 37, wherein at least two root mesh points of at least two of the spanning tree topologies are different.

45. An apparatus in a first wireless mesh point, the apparatus comprising:

means for establishing and/or maintaining, in collaboration with other wireless mesh points, multiple instances of a spanning tree protocol (“

WSTP instances”

) in a wireless mesh network that includes the first wireless mesh point and the other wireless mesh points, the wireless mesh network conforming to a wireless network standard, each spanning tree protocol instance substantially conforming to a standard IEEE 802.1 spanning tree protocol, the wireless network including the first wireless mesh point and at least two other wireless mesh points, the wireless network standard providing a mechanism for a wireless network entity to wirelessly communicate with other wireless network entities using control/management frames for the exchange of wireless network information, the means for establishing and/or maintaining comprising;

means for maintaining information in the first wireless mesh point on a plurality of spanning tree topologies each determined according to a spanning tree protocol that substantially conforms to a standard IEEE 802.1 spanning tree protocol using a wireless network path cost measure that can have a plurality of values for a path between two mesh points that are connectable, the maintained information for a topology including maintaining the identity of a root wireless mesh point of the spanning tree topology; and

means for wirelessly transmitting bridging path cost information information for each topology as at least one path cost information element that may includes one or more bridge protocol data units (“

BPDUs”

) for the topology to other wireless mesh points of the network encapsulated in one or more control/management frames,

wherein the root wireless mesh point is not required to have a wired network interface, and

wherein the BPDUs substantially conforms to BPDUs according to the standard IEEE 802.1 spanning tree protocol, but with a path cost different than a standard IEEE 802.1 spanning tree protocol BPDU path cost in that the path cost is designed for wireless communication and has one of a plurality of possible values for a path between two mesh points that are connectable.

46. An apparatus as recited in claim 45, wherein the control/management frames include beacon and probe response frames, and wherein the wireless network standard provides a mechanism for wireless network entities to wirelessly transmit beacon or probe response frames to other wireless network entities to advertise the radio characteristics of the wireless network entity, such that the means for wirelessly transmitting path cost information transmits the path cost information as path cost information elements for the topology in one or more beacon or probe response frames.

47. An apparatus as recited in claim 45, wherein the path cost information includes an indication of the identity of the spanning tree topology of the plurality of topologies.

48. An apparatus as recited in claim 45, wherein a beacon or probe response frame from the first wireless mesh point includes an indication of whether or not BPDU path cost information is included.

49. An apparatus as recited in claim 45, further comprising:

means for interfacing to a wired network.

50. An apparatus as recited in claim 45, wherein at least two of the spanning tree topologies have the same root tree mesh point.

51. An apparatus as recited in claim 50, wherein traffic is classified into one of a pre-defined set of different classes according to a classification mechanism, such that there is one respective WSTP instance of the WSTP instances that have the same root mesh point for each class, with a corresponding spanning tree topology for each class.

52. An apparatus as recited in claim 51, wherein each of WSTP instances uses a distinct respective path cost criterion applicable to the traffic class.

53. An apparatus as recited in claim 45, wherein at least two root mesh points of at least two of the spanning tree topologies corresponding to the WSTP instances are different.

54. A computer readable storage medium configured with computer readable code that when executed by a processor of a processing system in a first wireless mesh point to cause the first wireless mesh point to carry out a method, the processing system and the computer readable storage medium a first wireless mesh point, the computer readable storage medium configured with:

code to cause establishing and/or maintaining, in collaboration with other wireless mesh nodes, multiple spanning tree topologies in a multi-hop wireless mesh network, each spanning tree topology according to a respective instance of a spanning tree protocol (“

WSTP instances”

) for a wireless mesh network, such that each WSTP instance substantially conforms to the standard IEEE 802.1 spanning tree protocol, the wireless network conforming to a wireless network standard, the wireless network including the first wireless mesh point and at least two other wireless mesh points, the first wireless mesh point including a transceiver coupled to the processor and configured to wirelessly transmit and receive frames, the wireless network standard providing a mechanism for a wireless network entity to wirelessly communicate with other wireless network entities using control/management frames for the exchange of wireless network information, the code to cause establishing and/or maintaining comprising;

code to cause the processor to maintain information in the first wireless mesh point on the plurality of spanning tree topologies determined according to the spanning tree protocol that substantially conforms to a standard IEEE 802.1 spanning tree protocol, but that uses a wireless network path cost measure that is designed for wireless communication and that has one of a plurality of values for a path between two connectable wireless mesh points, the maintained information for a topology including maintaining the identity of a root wireless mesh point of the spanning tree topology; and

code to cause the transceiver to wirelessly transmit path cost information for each topology as one or mote path cost information elements that may include bridge protocol data units (“

BPDUs”

) for the topology, the transmitting to other wireless mesh points of the network, the path cost information encapsulated in one or more control/management frames,

wherein each root wireless mesh point is not required to have a wired network interface,

wherein each path cost information element includes the path cost measure designed that has one of a plurality of possible values for a path between two mesh points that are connectable, and

wherein a BPDU substantially conforms to a standard IEEE 802.1 spanning tree protocol BPDU but with a path cost different than a standard IEEE 802.1 spanning tree protocol BPDU path cost in that the path cost is designed for wireless communication and has one of a plurality of possible values for a path between two mesh points that are connectable.

55. A computer readable storage medium as recited in claim 54, wherein the control/management frames include beacon and probe response frames, and wherein the wireless network standard provides a mechanism for wireless network entities to wirelessly transmit beacon or probe response frames to other wireless network entities to advertise the radio characteristics of the wireless network entity, such that the code to wirelessly transmit BPDU information causes transmitting BPDUs encapsulated in one or more beacon and probe response frames.

56. A computer readable storage medium as recited in claim 54, wherein the BPDU information includes an indication of the identity of the spanning tree topology of the plurality of topologies.

57. A computer readable storage medium as recited in claim 54, wherein a beacon or probe response frame from the first wireless mesh point includes an indication of whether or not BPDU information is included.

58. A computer readable storage medium as recited in claim 54, wherein at least two of the spanning tree topologies have the same root tree mesh point.

59. A computer readable storage medium as recited in claim 58, wherein traffic is classified into one of a pre-defined set of different classes according to a classification mechanism, wherein a different VLAN is used for each traffic class such that there is one respective WSTP instance of the WSTP instances that have the same root mesh point for each class, with a corresponding spanning tree topology for each class.

60. A computer readable storage medium as recited in claim 59, wherein each of the WSTP instances uses a distinct respective path cost criterion applicable to the traffic class.

61. A computer readable storage medium as recited in claim 54, wherein at least two root mesh points of at least two of the spanning tree topologies corresponding to the WSTP instances are different.