System and method to support multicast routing in large scale wireless mesh networks

• US 7,606,187 B2
• Filed: 10/28/2004
• Issued: 10/20/2009
• Est. Priority Date: 10/28/2004
• Status: Active Grant

• Current Assignee: ARRIS Enterprises LLC (CommScope Holding Company, Inc.)
• Original Assignee: MeshNetworks, Inc. (Motorola Solutions, Inc.)
• Inventors: Joshi, Avinash, Zeng, Surong
• Primary Examiner(s): Appiah, Charles N
• Assistant Examiner(s): Karikari, Kwasi
• Application Number:
  US10/975,587
• Publication Number:
  US 20060098607A1
• Time in Patent Office: 1,818 Days
• Field of Search: 455/437, 370/338, 370/392, 370/256, 370/370, 370/351, 370/432, 370/312
• US Class Current: 370/312
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04W 4/08 User group management
• CPC Class Codes: H04W 40/00 Communication routing or communication path finding
• CPC Class Codes: H04W 40/26 for hybrid routing by combining proactive and reactive routing
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

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.

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.

2. The method of claim 1, further comprising:

forming a multicast group leader cloud comprising the local multicast group leaders, wherein there are connections between the local multicast group leaders, wherein the connections between the local multicast group leaders in the multicast group leader cloud include wired connections.

3. The method of claim 1, further comprising:

forming a multicast group leader cloud comprising the local multicast group leaders, wherein there are connections between the local multicast group leaders, wherein the connections between the local multicast group leaders in the multicast group leader cloud include wireless connections.

4. The method of claim 1, wherein at least one local multicast group leader operates to access the internet.

5. The method of claim 1, further comprising:

searching for and maintaining routes to the local multicast group leaders.

6. The method of claim 5, wherein the step of searching for and maintaining routes comprises:

employing proactive and reactive routing that dynamically searches for and maintains routes to the local multicast group leaders.

7. The method of claim 1, wherein each node in the network maintains a unicast routing table.

8. The method of claim 1, wherein each local multicast tree comprises at least one forwarding member, and wherein each forwarding member maintains a multicast routing table.

9. The method of claim 1, wherein the local multicast trees are formed on-demand.

10. The method of claim 1, further comprising:

when a node wishes to join a multicast group, unicasting a join route request packet from the node to an access point with which the node is associated.

11. The method of claim 10, further comprising:

when the access point is a local multicast group leader, sending a join route reply from the access point to the requesting 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 node.

12. The method of claim 10, wherein when the access point is not a local multicast group leader, the method further comprises:

enabling the access point'"'"'s ability to accept multicast traffic from the multicast group leader cloud;

creating a multicast entry for the requested multicast group in a multicast routing table; and

sending a join route reply from the access point to the requesting 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 node.

13. The method of claim 1, further comprising:

sending a route pruning request from a leaf node to a next hop node in the multicast group to which the leaf node belongs; and

deleting the requesting leaf node from a next hop list of the next hop node that received the route pruning request.

14. The method of claim 1, further comprising:

unicasting a route request from a requesting node to the requesting node'"'"'s local multicast group leader in order to refresh the requesting node'"'"'s group membership.

15. The method of claim 14, wherein unicasting the route request to the local multicast group leader extends life times for memberships of all nodes belonging to a branch to which the requesting node belongs.

16. The method of claim 14, further comprising:

extending life times for a previous hop and a next hop of the route request at an intermediate node along the route from the requesting node to the local multicast group leader.

17. The method of claim 1, further comprising:

using unicast routing to discover a better unicast route from a node to a local multicast group leader than a current route between the node and the local multicast group leader;

unicasting a join route request to enable a new route between the requesting node and the local multicast group leader; and

before the requesting node switches to the new route, continuing to utilize the previous route for the requesting node to send and receive multicast traffic.

18. The method of claim 1, further comprising:

using unicast routing to discover a preferable access point for a node to be associated with compared to an access point that is currently the node'"'"'s local multicast group leader;

unicasting a join route request to enable a new branch between the requesting node and the discovered access point;

selecting the discovered access point as the requesting node'"'"'s local multicast group leader; and

before the requesting node switches to the new branch, continuing to utilize the previous branch to the previous multicast group leader for the requesting node to send and receive multicast traffic.

19. The method of claim 1 further comprising:

maintaining a list in each member node of sequence numbers for packets received by each member node; and

maintaining each sequence number on the list for a period of time,

wherein the deleting step comprises deleting a packet newly received by a node when the packet carries a sequence number that is currently being maintained on the receiving node'"'"'s sequence number list, and

wherein the accepting step comprises accepting a packet newly received by a node when the packet carries a sequence number that is not currently being maintained on the receiving node'"'"'s sequence number list.

40. The method of claim 1, wherein the node comprises a member node of a first local multicast tree of with the first local multicast group leader.

41. The method of claim 1, wherein the node is not a member node of a first local multicast tree of with the first local multicast group leader, wherein the first local multicast group leader comprises an associated access point of the node, and further wherein the node transmits the message packet to the first local multicast group leader by tunneling the message packet to the first local multicast group leader.

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.

21. The network of claim 20, further comprising wired connections between infrastructure nodes.

22. The network of claim 20, further comprising wireless connections between infrastructure nodes.

23. The network of claim 20, wherein at least one infrastructure node operates to access the internet.

24. The network of claim 20, wherein the plurality of wireless nodes employ unicast routing to search for and maintain routes to the fixed infrastructure nodes.

25. The network of claim 20, wherein each node in the network maintains a unicast routing table.

26. The network of claim 20, wherein each member of a multicast tree maintains a multicast routing table.

27. The network of claim 20, wherein the local multicast trees are formed on-demand.

28. The network of claim 20,

wherein each wireless node operates to join a multicast group when desired by unicasting a join route request packet to an access point with which the requesting wireless node is associated but which is not a local multicast group leader;

and

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.

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.