System and method to support multicast routing in large scale wireless mesh networks
First Claim
1. A method for supporting multicast routing in a multi-hop wireless ad hoc network that includes a plurality of fixed infrastructure nodes communicatively coupled to a backbone, the method comprising:
- selecting certain infrastructure nodes as local multicast group leaders;
forming a plurality of local multicast trees each rooted at a local multicast group leader, and each comprising a plurality of members;
transmitting a message packet destined for a plurality of destination nodes, wherein each of the plurality of destination nodes is a member of at least one local multicast tree, and further wherein each of the plurality of destination nodes is a member of at least one multicast group identified by a multicast group address associated with the multicast group, from a node to a first local multicast group leader, wherein the message packet includes the multicast group address;
forwarding the message packet to the backbone by the first local multicast group leader;
receiving the message packet by at least one other local multicast group leader via the backbone; and
distributing the message packet to the plurality of destination nodes by each of the at least one other local multicast group leaders distributing the message packet to each member having the multicast group address of its associated local multicast tree,wherein each packet transmitted in multicast or broadcast traffic carries a sequence number in the packet'"'"'s packet header, the method further comprising;
deleting a packet newly received by a node when the packet carries a sequence number that has been previously received by the node; and
accepting a packet newly received by the node when the packet carries a sequence number that has not been previously received by the node.
8 Assignments
0 Petitions
Accused Products
Abstract
Provided is a system and method for a multicast routing algorithm to work in infrastructure based mesh networks. It chooses access points, fixed infrastructure gateway nodes connected to each other and/or the global internet via a wired/wireless backbone, as a group of local multicast group leaders to form a multicast group leader cloud. Each local multicast group leader is elected on-demand according to the local multicast group member'"'"'s request. Each local multicast group leader forms a local multicast tree rooted at this leader connecting all multicast group members associated with the AP. The processes of electing and maintaining local multicast trees rooted at APs enable efficient coordination with underlying unicast routing to exploit the advantages of fixed infrastructure nodes. Therefore, routing overhead and multicast tree convergence time are reduced. The method can support large networks with fast topology change due to fast convergence and reduced routing overhead.
-
Citations
41 Claims
-
1. A method for supporting multicast routing in a multi-hop wireless ad hoc network that includes a plurality of fixed infrastructure nodes communicatively coupled to a backbone, the method comprising:
-
selecting certain infrastructure nodes as local multicast group leaders; forming a plurality of local multicast trees each rooted at a local multicast group leader, and each comprising a plurality of members; transmitting a message packet destined for a plurality of destination nodes, wherein each of the plurality of destination nodes is a member of at least one local multicast tree, and further wherein each of the plurality of destination nodes is a member of at least one multicast group identified by a multicast group address associated with the multicast group, from a node to a first local multicast group leader, wherein the message packet includes the multicast group address; forwarding the message packet to the backbone by the first local multicast group leader; receiving the message packet by at least one other local multicast group leader via the backbone; and distributing the message packet to the plurality of destination nodes by each of the at least one other local multicast group leaders distributing the message packet to each member having the multicast group address of its associated local multicast tree, wherein each packet transmitted in multicast or broadcast traffic carries a sequence number in the packet'"'"'s packet header, the method further comprising; deleting a packet newly received by a node when the packet carries a sequence number that has been previously received by the node; and accepting a packet newly received by the node when the packet carries a sequence number that has not been previously received by the node. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 40, 41)
-
-
20. A communications network, the network comprising:
-
a plurality of wireless nodes; a plurality of fixed infrastructure nodes communicatively coupled to a backbone; a multicast group including at least some of the wireless nodes and at least some of the fixed infrastructure nodes, the multicast group comprising; a plurality of local multicast trees each rooted at a local multicast group leader selected from the plurality of the fixed infrastructure nodes, and further each local multicast tree comprising at least one wireless node, wherein the multicast group operates to distribute a message packet to the plurality of wireless nodes and the plurality of fixed infrastructure nodes by; transmitting the message packet destined for a plurality of destination nodes, wherein each of the plurality of destination nodes is a member of at least one local multicast tree, and further wherein each of the plurality of destination nodes is a member of at least one multicast group identified by a multicast group address associated with the multicast group, from a node to a first local multicast group leader, wherein the message packet includes the multicast group address; forwarding the message packet to the backbone by the first local multicast group leader; receiving the message packet by at least one other local multicast group leader via the backbone; and distributing the message packet to the plurality of destination nodes by each of the at least one other local multicast group leaders distributing the message packet to each member having the multicast group address of its associated local multicast tree; packets carrying a sequence number in a packet header; at least one multicast group member operating to delete a packet newly received when the packet carries a sequence number that has been previously received by the at least one multicast group member; and
accept a packet newly received when the packet carries a sequence number that has not been previously received by the at least one multicast group member.- View Dependent Claims (21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39)
wherein the access point operates to, upon receipt of the join route request, enable its ability to accept multicast traffic from other local multicast group leaders, create a multicast entry for the requested multicast group in a multicast routing table, and send a join route reply to the requesting wireless node, wherein the join route reply activates one or more entries within one or more forwarding members of the requested multicast group along a route between the access point and the requesting wireless node.
-
-
29. The network of claim 20,
wherein each wireless node operates to join a multicast group by unicasting a join route request packet to a local multicast group leader; - and
wherein the local multicast group leader operates to send a join route reply to the requesting wireless node, wherein the route reply activates one or more entries within one or more forwarding members of the requested multicast group along a route between the local multicast group leader and the requesting wireless node.
- and
-
30. The network of claim 20, further comprising:
-
a leaf node, wherein the leaf node operates to send a route pruning request to a next hop in a multicast group to which the leaf node belongs; and wherein the next hop node receiving the route pruning request deletes the requesting leaf node from the receiving next hop node'"'"'s next hop list.
-
-
31. The network of claim 20, further comprising:
at least one multicast group member node operating to unicast a route request to a local multicast group leader in order to refresh the requesting node'"'"'s group membership.
-
32. The network of claim 31, further comprising:
one or more intermediate nodes, along the route from the requesting node to the local multicast group leader, wherein the one or more intermediate nodes operate to extend life times for a previous hop and a next hop of the route request.
-
33. The network of claim 31, wherein the unicasting of the route request extends life times for group memberships of all nodes belonging to a branch to which the requesting node belongs.
-
34. The network of claim 20, further comprising:
at least one multicast group member operating to discover a better unicast route to a local multicast group leader than a current route between the member and the local multicast group leader, and further operating to unicast a join route request to enable a new route between the requesting member and the local multicast group leader.
-
35. The network of claim 34, wherein the group member continues to utilize the previous route to send and receive multicast traffic, until the requesting member switches to the new route.
-
36. The network of claim 20, further comprising:
at least one multicast group member operating to use unicast routing to discover a preferable access point to be associated with compared to an access point that is currently the member'"'"'s local multicast group leader, and to unicast a join route request to enable a new branch between the requesting member and the discovered access point, and to select the discovered access point as the requesting member'"'"'s local multicast group leader.
-
37. The network of claim 36, wherein the group member continues to utilize the previous branch to the previous multicast group leader in order to send and receive multicast traffic until the requesting member switches to the new branch.
-
38. The network of claim 20,
wherein the at least one multicast group member further operates to maintain a list of sequence numbers for packets received, and to maintain each sequence number on the list for a period of time, and to delete a newly received packet if the received packet carries a sequence number that is currently being maintained on the member'"'"'s sequence number list, and to accept a newly received packet if the packet carries a sequence number that is not currently being maintained on the member'"'"'s sequence number list. -
39. The network of claim 20, wherein the plurality of wireless nodes comprise mobile ad hoc wireless nodes.
Specification