Core assisted mesh protocol for multicast routing in ad-hoc Networks

• US 6,917,985 B2
• Filed: 03/09/2001
• Issued: 07/12/2005
• Est. Priority Date: 03/10/2000
• Status: Expired due to Term

• Current Assignee: Regents of the University of California (University of California)
• Original Assignee: Regents of the University of California (University of California)
• Inventors: Garcia-Luna-Aceves, Joaquin J., Madruga, Ewerton L.
• Primary Examiner(s): Barot, Bharat
• Application Number:
  US09/802,476
• Publication Number:
  US 20010034793A1
• Time in Patent Office: 1,586 Days
• Field of Search: 709200-202, 709237-242, 709/230, 370/256, 370/351, 370/390, 370/397, 370/408, 370/409, 370/238, 370328-329, 370431-432, 701/10, 707/10
• US Class Current: 709/238
• CPC Class Codes: H04L 12/185 with management of multicast group membership
• CPC Class Codes: H04L 12/1854 with non-centralised forwarding system, e.g. chaincast
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 40/248 Connectivity information update
• CPC Class Codes: H04W 40/30 for proactive routing

Abstract

A method of providing multicast routing for use in ad hoc broadcast networks, such as wireless and mobile networks. The method is described within a protocol referred to as core-assisted mesh protocol, or CAMP. The method departs from traditional tree-structured multicast protocols and utilizes multicast meshes in which the network need not be flooded with control or data packets to establish routing paths. Each router configured for CAMP is capable of accepting unique packets arriving from any neighbor in the mesh, wherein packets are forwarded along reverse shortest paths to the receiver. Multiple cores may be defined for a group wherein the loss of a single core does not prevent packet flow. Routers for sender-only hosts are allowed to join the multicast mesh in simplex mode, and in certain cases may join without the sending of a join request.

Claims

1. A method of multicast communication within a wireless network, comprising:

defining a shared multicast mesh of routers for each multicast group wherein multiple paths are established between any two routers; and

forwarding packets from a source connected within the shared multicast mesh of the multicast group along a reverse shortest path to a receiver;

wherein the reverse shortest path is a shortest path from the receiver to the source.

2. A method as recited in claim 1, wherein said routers are configured to accept unique packets being received from any neighboring router within the shared multicast mesh.

3. A method as recited in claim 1, wherein said routers maintain the reverse shortest path mapping to the receivers.

4. A method as recited in claim 3, wherein routers maintain the reverse shortest path mapping by sending out a heartbeat message to successors when packets arrive through paths other than their respective reverse shortest path from traffic sources, wherein the heartbeat message as received by the successor triggers a push join operation to force the successor and all routers in the paths to the traffic sources to join the shared multicast mesh.

5. A method as recited in claim 3, wherein routing is established between routers such that network flooding with data or control packets to establish a routing structure is not required.

6. A method as recited in claim 1, wherein routers for sender-only hosts join the multicast mesh in simplex mode.

7. A method as recited in claim 1, wherein routers share group membership reports with neighbors and track relationships between neighbors and groups.

8. A method as recited in claim 7, wherein multicast addresses are mapped to one or more cores as part of a group membership report.

9. A method as recited in claim 1, wherein routers are configured to allow the definition of multiple cores for a group within the shared multicast mesh.

10. A method of allowing a host to join a multicast mesh for multicast communication within a wireless network, comprising:

determining an address of a first multicast group to which said host desires to join;

interacting with a first designated router, by said host, requesting that it gain membership in said first multicast group;

announcing membership in the first multicast group if the first designated router joining has multiple neighboring routers which are duplex members of the first multicast group; and

sending a join request for membership in the first multicast group to neighboring routers if one or fewer of the neighboring routers are duplex members of the first multicast group.

11. A method as recited in claim 10, wherein the routers are configured to generate an acknowledgement to the join request, such that non-core routers can acknowledge group membership.

12. A method of maintaining shortest path routes within a group'"'"'s mesh populated with routers, comprising:

caching packet identifiers of forwarded packets in a cache;

forwarding a multicast packet from a neighboring router if the packet identifier is not contained within the cache; and

transmitting heartbeat messages whenever traffic arrives through a path from a source that is not a reverse shortest path, wherein the heartbeat message is configured to trigger a push join to correct routing;

wherein the reverse shortest path is a shortest path from the receive to the source.