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

• US 20060098607A1
• Filed: 10/28/2004
• Published: 05/11/2006
• 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: Zeng, Surong, Joshi, Avinash
• Granted Patent: US 7,606,187 B2
• Time in Patent Office: Days
• US Class Current: 370/338
• 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 fixed infrastructure nodes, the method comprising:

selecting certain infrastructure nodes as local multicast group leaders;

forming a multicast group leader cloud comprising the local multicast group leaders, wherein there are connections between the local multicast group leaders; and

forming local multicast trees each rooted at a local multicast group leader.

2. The method of claim 1, wherein the connections between the nodes in the multicast group leader cloud include wired connections.

3. The method of claim 1, wherein the connections between the nodes in the multicast group leader cloud include wireless connections.

4. The method of claim 1, wherein at least one node in the multicast group leader cloud is able 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 member of a multicast tree 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:

if the access point is a local multicast group leader, sending a join route reply from the access point to the requesting node, wherein on the way to the requesting node the route reply activates all entries for the requested multicast group along the route.

12. The method of claim 10, wherein if 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 on the way to the requesting node the route reply activates all entries for the requested multicast group along the route.

13. The method of claim 1, further comprising:

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

deleting the requesting node from the next hop list of the node that received the 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, wherein each packet transmitted in multicast or broadcast traffic carries a sequence number in the packet'"'"'s packet header, the method further comprising:

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

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

deleting a packet newly received by a node if the packet carries a sequence number that is currently being maintained on the receiving node'"'"'s sequence number list; and

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

20. A communications network, the network comprising:

a plurality of wireless nodes;

a plurality of fixed infrastructure nodes;

connections between the infrastructure nodes; and

a multicast group including at least some of the wireless nodes and at least some of the fixed infrastructure nodes,

wherein at least some of the fixed infrastructure nodes are adapted to act as local multicast group leaders for local multicast trees comprising at least one wireless node.

21. The network of claim 20, wherein the connections between infrastructure nodes include wired connections.

22. The network of claim 20, wherein the connections between infrastructure nodes include wireless connections.

23. The network of claim 20, wherein at least one infrastructure node is able 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, further comprising:

each wireless node being adapted to be able to join a multicast group by unicasting a join route request packet to an access point with which the requesting node is associated but which is not a local multicast group leader; and

the access point adapted 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 node, wherein on the way to the requesting node the route reply activates all entries for the requested multicast group along the route.

29. The network of claim 20, further comprising:

each wireless node being adapted to be able to join a multicast group by unicasting a join route request packet to a local multicast group leader; and

the local multicast group leader adapted to send a join route reply to the requesting node, wherein on the way to the requesting node the route reply activates all entries for the requested multicast group along the route.

30. The network of claim 20, further comprising:

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

the next hop node receiving the route pruning request, adapted to delete the requesting leaf node from the receiving node'"'"'s next hop list.

31. The network of claim 20, further comprising:

at least one multicast group member node being adapted 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:

intermediate nodes, along the route from the requesting node to the local multicast group leader, being adapted 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 being adapted 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 being adapted 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 is adapted to continue 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 being adapted 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, being adapted to unicast a join route request to enable a new branch between the requesting member and the discovered access point, and being adapted 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 is adapted to continue 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, further comprising:

packets adapted to carry a sequence number in a packet header;

at least one multicast group member being adapted to maintain a list of sequence numbers for packets received, being adapted to maintain each sequence number on the list for a period of time, being adapted 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 being adapted 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.