# US 2008/0304485 A1 · Centrally controlled routing with tagged packet forwarding in a wireless mesh network

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2008/0304485 A1
- Document ID: US20080304485A1
- Status: Published application
- Kind: A1
- Application number: 11/758,990
- Filed: 2007-06-06
- Published: 2008-12-11
- Earliest claimed: 2007-06-06
- Assignees: Cisco Technology, Inc.
- Inventors: Santanu Sinha; Robert B. O'Hara, JR.; Shahriar I. Rahman
- Web page: https://patentgrep.com/patent/US20080304485A1

## CPC

- H04W 40/246: {Connectivity information discovery}
- H04L 12/66: Arrangements for connecting between networks having differing types of switching systems, e.g. gateways
- H04L 45/42: Centralised routing
- H04L 45/50: using label swapping, e.g. multi-protocol label switch [MPLS]
- H04W: WIRELESS COMMUNICATION NETWORKS (broadcast communication H04H; communication systems using wireless links for non-selective communication, e.g. wireless extensions H04M1/72)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

Embodiments of the present invention include a method, an apparatus, and logic encoded in one or more computer-readable tangible medium to carry out a method. One method includes tagging packets and forwarding packets in a wireless mesh network using stored forwarding information for the tag, wherein the forwarding information is according to a centrally determined routing method and tag distribution method.

## Claims

### Claim 1

A method comprising:
receiving from each mesh point of a wireless mesh network information sufficient to determine a map of mesh points and one or more available wireless links between the mesh points, the mesh points of the wireless mesh network including a root mesh point and one or more additional mesh points;
in response to detecting that a client of a particular mesh point that has access point capabilities is joining the mesh network, using a centralized routing process to determine at least one path from the client to the root mesh point for at least one traffic class;
assigning an upstream tag to one or more determined paths for each traffic class from the client, such that each assigned upstream tag has at least one corresponding upstream path; and
for each upstream tag, sending to at least each mesh point in the upstream tag's one or more paths tag information on the upstream tag, such that a receiving mesh point can store forwarding information for the upstream tag, including the upstream tag of the path, and one or more immediate next hops of the receiving mesh point for the corresponding path or paths of the upstream tag,
such that a packet that has been tagged to include a tag can be forwarded by a receiving mesh point by looking up the tag in its stored forwarding information to determine the next hop for the tagged packet, and forwarding the tagged packet to the next hop.

### Claim 2 (depends on 1)

A method as recited in claim 1, further comprising:
using the centralized routing process to determine at least one path from the root mesh point to the client for each traffic class for the client;
assigning a downstream tag to one or more determined paths for the same traffic class for the client, each such assigned tag having at least one corresponding downstream path; and
for each tag, sending to the at least each mesh point in the downstream tag's one or more paths tag information on the downstream tag including for each mesh point, such that a receiving mesh point can store forwarding information for the downstream tag, including the tag of the path, and one or more immediate next hops of the mesh point for the path or paths of the downstream tag.

### Claim 3 (depends on 1)

A method as recited in claim 1,
wherein the mesh points of the mesh network are controlled by a controller using control messages between the controller and the mesh points, and wherein the centralized routing method is configured to determine paths for control messages and paths for one or more classes of data traffic.

### Claim 4 (depends on 2)

A method as recited in claim 2,
wherein the mesh network is controlled by a controller, and wherein the downstream paths are from the controller via the root mesh point and the upstream paths are from the controller via the root mesh point.

### Claim 5 (depends on 2)

A method as recited in claim 2, further comprising:
receiving information that a packet of a traffic class of a first client has traversed the mesh from the first client to a second client;
using the centralized routing process to determine one or more intra-mesh paths for the traffic class;
associating a tag for each direction of traffic between the first and second clients; and
distributing tag information to the mesh points in the determined intra-mesh paths so that a packet from either client can be tagged and then forwarded to the other client without having to traverse the root mesh point.

### Claim 6 (depends on 2)

A method as recited in claim 2, further comprising:
receiving an indication of a particular next link in a tagged path is broken;
modifying or deleting each tagged path that includes the particular next link; and
distributing tag information to any mesh points in any modified or deleted paths.

### Claim 7 (depends on 2)

A method as recited in claim 2, wherein at least some of the next hop information of a tag includes more than one next hop in a priority order with a highest priority next hop and a next highest priority next hop, such that in the case the highest priority next hop is not reachable, a tagged packet is forwarded to the next highest priority next hop.

### Claim 8

A method of routing packets in a wireless mesh network, the method comprising:
in response to detecting that a mesh point has joined the mesh network via a parent mesh point, setting up a control path for control messages to control the discovered mesh point; and
in response to detecting that a client is joining the mesh network via a particular discovered mesh point that has access point functionality, assigning a tag for the client for a class of traffic in the upstream direction, the tag defining at least one centrally determined upstream path between the client and the root mesh point of the mesh network for the type of client traffic and the level of service subscribed by the client,
wherein tag information on assigned tags are distributed to each mesh point in each path defined by the tag, the tag information including at least one next hop for the path, such that a packet transmitted in the upstream direction for the type of client traffic and the level of service of the tag can be tagged at the particular discovered mesh point, and such that a tagged packet can forwarded by each mesh point in at least one path of the tag by looking up the tag and forwarding to the next hop of the tag.

### Claim 9

An apparatus comprising:
one or more processors;
a memory subsystem;
a network interface configured to couple the apparatus to a network to which a mesh network is connected, the mesh network including a root mesh point and one or more additional mesh points; and
logic, including instructions encoded in one or more tangible media for execution and when executed, causing a control plane process to be executed, the control plane process including:
receiving from each mesh point of the wireless mesh network information sufficient to determine a map of all mesh points and the available links between the mesh points, the mesh points of the wireless mesh network including a root mesh point and one or more leaf mesh points;
as a result of detecting that a client of a particular mesh point that has access point capabilities is joining the mesh network, using a centralized routing process to determine at least one path from the client to the root mesh point for at least one traffic class;
assigning an upstream tag to one or more determined paths for each traffic class from the client, such that each assigned upstream tag has at least one corresponding upstream path; and
for each upstream tag, sending to at least each mesh point in the upstream tag's one or more paths tag information on the upstream tag, such that a receiving mesh point can store forwarding information for the upstream tag, including the upstream tag of the path, and one or more immediate next hops of the receiving mesh point for the corresponding path or paths of the upstream tag,
such that a packet that has been tagged to include a tag can be forwarded by a receiving mesh point by looking up the tag in its stored forwarding information to determine the next hop for the tagged packet, and forwarding the tagged packet to the next hop.

### Claim 10 (depends on 9)

An apparatus as recited in claim 9,
wherein the control plane process further includes sending and receiving control packets from the mesh points of the mesh network to control the mesh points, and
wherein the centralized routing method is configured to determine paths for control messages and paths for one or more classes of data traffic.

### Claim 11 (depends on 9)

An apparatus as recited in claim 9, wherein at least some of the next hop information of a tag includes more than one next hop in a priority order with a highest priority next hop and a next highest priority next hop, such that in the case the highest priority next hop is not reachable, a tagged packet is forwarded to the next highest priority next hop.

### Claim 12

A method comprising:
receiving at a first mesh point of a wireless mesh network a packet, the mesh network including a root mesh point and one or more other mesh points;
ascertaining if the received packet includes a tag, and in the case that the packet includes a tag, looking up a tag data structure maintained in the first mesh point, the data structure containing tag entries each including a tag and forwarding information, each tag entry corresponding to one or more paths from a source to a destination; and
in the case that the looking up results in a matched tag entry that includes an indication of a next hop mesh point in the forwarding information, forwarding the packet to the next hop mesh point of the matched tag entry,
wherein the tag data structure is formed from tag information received from a central controller, and
wherein the forwarding information to at least one next hop mesh points of each tag entry in the tag data structure is part of at least one path for the tag determined by the central controller using a central routing method for a traffic class, and distributed by the central controller as tag information to mesh points in the path or paths of the tag.

### Claim 13 (depends on 12)

A method as recited in claim 12, wherein the first mesh point includes access point functionality, further comprising ascertaining whether the packet is to a client of the first mesh point, and in the case that the packet is to a client of the first mesh point, removing any tag in the packet, and transmitting the packet to the client of the first mesh point.

### Claim 14 (depends on 12)

A method as recited in claim 12, wherein the first mesh point includes access point functionality, and wherein the tag data structure includes entries for any clients of the first mesh point that includes an indication of the source and of the traffic class, the method further comprising:
receiving a client packet from a first client of the first mesh point for a first class of traffic; and
looking up the tag data structure to ascertain whether there is a tag entry for the source being the first client for the first traffic class, and in the case that a match is found, adding the tag of the matched entry to the received packet to form a tagged packet, retrieving forwarding information including a next hop from the matched tag entry, and forwarding the packet to the next hop of the matched tag entry.

### Claim 15 (depends on 12)

A method as recited in claim 12,
wherein the first mesh point includes access point functionality, and
wherein the tag information is formed by a process at the central controller including:
receiving from each mesh point of a wireless mesh network information sufficient to determine a map of all mesh points and the available links between the mesh points, the mesh points of the wireless mesh network including a root mesh point and one or more additional mesh points;
in response to detecting that a client of a particular mesh point that has access point capabilities is joining the mesh network, using the centralized routing process to determine at least one path from the client to the root mesh point for at least one traffic class; and
assigning an upstream tag to one or more determined paths for each traffic class from the client, such that each assigned upstream tag has at least one corresponding upstream path; for each upstream tag, sending to at least each mesh point in the upstream tag's one or more paths tag information on the upstream tag.

### Claim 16 (depends on 15)

A method as recited in claim 15, wherein the process at the central controller further includes:
using the centralized routing process to determine at least one downstream path from the root mesh point to the client for each traffic class for the client;
using the centralized routing process to determine at least one upstream path to the root mesh point from the client for each traffic class for the client;
assigning a downstream tag to one or more determined downstream paths for the same traffic class for the client, such each assigned downstream tag has at least one corresponding downstream path; and
assigning a upstream tag to one or more determined upstream paths for the same traffic class for the client, such each assigned upstream tag has at least one corresponding upstream path; and
for each tag, sending to the at least each mesh point in the tag's one or more paths tag information on the tag.

### Claim 17 (depends on 12)

A method as recited in claim 12, wherein the first mesh point of the mesh network is controlled by the controller using control messages between the controller and the first mesh points, and wherein the centralized routing method is configured to determine paths for control messages and paths for one or more classes of data traffic.

### Claim 18 (depends on 16)

A method as recited in claim 16, wherein the mesh network is controlled by a controller, and wherein the downstream paths are from the controller via the root mesh point and the upstream paths are from the controller via the root mesh point.

### Claim 19 (depends on 14)

A method as recited in claim 14, wherein the looking up of the tag data structure to ascertain whether there is a tag entry for the source being the first client first includes ascertaining if there is an entry for one or more intra-mesh paths with the destination of the client packet as the destination of the intra-mesh paths.

### Claim 20

Logic encoded in one or more tangible media for execution and when executed operable to:
receive at a first mesh point of a wireless mesh network a packet, the mesh network including a root mesh point and one or more other mesh points;
ascertain if the received packet includes a tag, and in the case that the packet includes a tag, look up a tag data structure maintained in the first mesh point, the data structure containing tag entries each including a tag and forwarding information, each tag entry corresponding to one or more paths from a source to a destination; and
in the case that the looking up results in a matched tag entry that includes an indication of a next hop mesh point in the forwarding information, forwarding the packet to the next hop mesh point of the matched tag entry,
wherein the tag data structure is formed from tag information received from a central controller, and
wherein the forwarding information to at least one next hop mesh points of each tag entry in the tag data structure is part of at least one path for the tag determined by the central controller using a central routing method for a traffic class, and distributed by the central controller as tag information to mesh points in the path or paths of the tag.

### Claim 21 (depends on 20)

Logic as recited in claim 20, wherein the first mesh point includes access point functionality, and wherein the tag data structure includes entries for any clients of the first mesh point that includes an indication of the source and of the traffic class, the logic when executed further operable to:
receive a client packet from a first client of the first mesh point for a first class of traffic; and
look up the tag data structure to ascertain whether there is a tag entry for the source being the first client for the first traffic class, and in the case that a match is found, adding the tag of the matched entry to the received packet to form a tagged packet, retrieving forwarding information including a next hop from the matched tag entry, and forwarding the packet to the next hop of the matched tag entry.
