Multicast routing in ad-hoc networks

• US 7,310,335 B1
• Filed: 10/31/2000
• Issued: 12/18/2007
• Est. Priority Date: 09/06/2000
• Status: Expired due to Fees

• Current Assignee: Nokia Solutions and Networks US LLC (Nokia Corporation)
• Original Assignee: Nokia Networks (Nokia Corporation)
• Inventors: Garcia-Luna-Aceves, Jose J., Spohn, Marcelo
• Primary Examiner(s): Chan, Wing
• Assistant Examiner(s): DUONG, DUC T
• Application Number:
  US09/703,074
• Time in Patent Office: 2,604 Days
• Field of Search: 370254-256, 370/351, 370/352, 370/353, 370/354, 370/355, 370/356, 370/390, 370/400, 370/401, 370/408, 370/432, 370/473, 370/389, 370/392, 709220-223, 709/228, 709/252, 709/238
• US Class Current: 370/390
• 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/16 Multipoint routing
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 47/15 in relation to multipoint traffic arrangements for broadcast or multicast in data networks H04L12/18
• CPC Class Codes: H04L 47/17 Interaction among intermediate nodes, e.g. hop by hop
• CPC Class Codes: H04W 40/246 Connectivity information discovery

Abstract

Multicast routing in ad-hoc networks by exchange of multicast group update information and routing tree information among neighboring routers is disclosed. A router propagates multicast group update information based on the update information and the routing tree information. A router also determines whether to forward multicast data packets based on control information in the multicast data packets and the routing tree information.

Claims

1. A method for communicating multicast group membership information in a network between a plurality of routers in a multicast group, the method comprising:

reporting routing tree information from each of the plurality of routers reports to other routers of said plurality of routers, wherein the routing tree information comprises a source tree for a unicast routing protocol;

receiving update information at a second router in the network from a first router, said update information comprising update information on a multicast group and a network address of said first router;

using said update information to indicate that said first router is becoming a member of said multicast group;

determining, based at least in part on said update information and the routing tree information reported by said first router, whether said second router is to transmit said update information so that all members of said multicast group remain connected, by determining if said source tree reported by said first router has said second router as a root of a subtree from which said first router is excluded, and if at least one neighbor router of said second router in said subtree is not a member of said multicast group; and

in response to a positive determination, transmitting said update information from said second router to said at least one neighbor router of said second router.

2. The method of claim 1, further comprising:

configuring said update information to comprise an identifier of said multicast group.

3. The method of claim 1, further comprising:

configuring said update information to comprise a network address of said first router.

4. The method of claim 1, wherein said determining further comprises determining if said first router is not a member of said multicast group.

5. The method of claim 4, further comprising:

configuring said update information to comprise a time stamp, wherein said determining further comprises determining if said time stamp is valid.

6. The method of claim 5, further comprising:

configuring said time stamp to comprise a first time stamp and wherein said determining if said time stamp is valid comprises determining if said first time stamp is more recent than a second time stamp stored in said second router, wherein said second time stamp is associated with said multicast group and said first router.

7. The, method of claim 1, further comprising:

configuring said update information to comprise an indication that said first router is no longer a member of said multicast group.

8. The method of claim 7, further comprising:

configuring the routing tree information to comprise a source tree for a unicast routing protocol, wherein said determining comprises determining if said source tree reported by said first router has said second router as the root of said subtree from which said first router is excluded, and if at least one neighbor router of said second router in said subtree is a member of said multicast group.

9. The method of claim 8, wherein said determining further comprises determining if said first router is not a member of said multicast group.

10. The method of claim 9, further comprising:

configuring said update information to comprise a time stamp, and wherein said determining further comprises determining if said time stamp is valid.

11. The method of claim 10, further comprising:

configuring said time stamp to comprise a first time stamp, wherein said determining if said time stamp is valid comprises determining if said first time stamp is more recent than a second time stamp stored in said second router, wherein said second time stamp is associated with said multicast group and said first router.

12. A method for forwarding multicast packets in a network comprising a plurality of routers in a multicast group, the method comprising:

reporting routing tree information from each of the plurality of routers to other routers of said plurality of routers;

receiving a multicast packet at a second router from a first router, said multicast packet comprising control information, wherein a multicast packet is from a selected source and for a selected multicast group;

determining, based at least in part on said control information and the routing tree information reported by said first router, if said multicast packet is to be forwarded by said second router, wherein said routing tree information comprises a source tree for a unicast routing protocol; and

in response to a positive determination that said multicast packet is to be forwarded,

forwarding said multicast packet from said second router to at least a third router,

creating an entry in a multicast forwarding cache, wherein said entry indicates that a multicast packet from said selected source and said selected multicast group is to be forwarded from said second router, and

maintaining by said second router a multicast packet-forwarding cache, wherein said multicast packet-forwarding cache comprises an entry indicating each multicast packet recently forwarded by said second router,

wherein said determining comprises determining whether said first router is a next hop in a shortest path from said second router to the source of the multicast packet according to said source tree.

13. The method of claim, 12, further comprising:

configuring said multicast packet to comprise an address of the multicast group.

14. The method of claim 12, further comprising:

configuring said multicast packet to comprise an address of the source of said multicast packet.

15. The method of claim 12, further comprising:

configuring said multicast packet to comprise a time value, wherein said time value is used to limit the time said multicast packet is allowed to remain in the network.

16. A method for forwarding multicast packets in a network comprising a plurality of routers in a multicast group, the method comprising:

reporting routing tree information from each of the plurality of routers to other routers of said plurality of routers;

receiving a multicast packet at a second router from a first router, said multicast packet comprising control information, wherein a multicast packet is from a selected source and for a selected multicast group;

determining, based at least in part on said control information and the routing tree information reported by said first router, if said multicast packet is to be forwarded by said second router; and

in response to a positive determination that said multicast packet is to be forwarded,

forwarding said multicast packet from said second router to at least a third router,

creating an entry in a multicast forwarding cache, wherein said entry indicates that a multicast packet from said selected source and said selected multicast group is to be forwarded from said second router, and

configuring the routing tree information reported by said first router to comprise a source tree for a unicast routing protocol,

wherein said determining comprises determining if said first router is a next hop in a shortest path from said second router to the source of the multicast packet according to said source tree, and if said source tree has said second router in a subtree with at least one router in said subtree being a member of the multicast group.

17. An apparatus, comprising:

a plurality of routers in a multicast group configured to communicate multicast group membership information in a network to other routers of said plurality of routers, wherein each of the plurality of routers reports routing tree information to other routers of said plurality of routers, wherein the routing tree information comprises a source tree for a unicast routing protocol;

a first router; and

a second router,

wherein said first router is configured to receive update information transmitted from said second router and comprises update information on a multicast group and an indication that said second router is becoming a member of said multicast group,

wherein said first router is configured to determine, based at least in part on said update information and the routing tree information reported by said second router, whether said first router is to transmit said update information to at least one neighbor router of said first router, by determining if said source tree reported by said second router has said first router as a root of a subtree from which said second router is excluded, and at least one neighbor router of said first router in said subtree is not a member of said multicast group, so that all members of said multicast group remain connected, and

wherein said first router, in response to a positive determination that said first router is to transmit said update information, is configured to transmit said update information to said at least one neighbor router.

18. The apparatus of claim 17, wherein said update information comprises an identifier of said multicast group.

19. The apparatus of claim 17, wherein said update information comprises a network address of said first router.

20. The apparatus of claim 19, wherein said first router is further configured to determine whether said first router is to transmit said update information by determining if said second router is not a member of said multicast group.

21. The apparatus of claim 20, wherein said update information comprises a time stamp, and wherein said first router further determines whether said first router is to transmit said update information by determining if said time stamp is valid.

22. The apparatus of claim 21, wherein said first router is further configured to store a time stamp associated with said multicast group and said second router, wherein said time stamp comprises a first time stamp and wherein said first router is configured to determine whether said time stamp is valid by determining if said first time stamp is more recent than said second time stamp.

23. The apparatus of claim 17, wherein said update information comprises an indication that said second router is no longer a member of said multicast group.

24. The apparatus of claim 23, wherein the routing tree information comprises a source tree for a unicast routing protocol, and wherein said first router is configured to determine whether said first router is to transmit said update information by determining if said source tree reported by said second router has said first router as the root of a subtree from which said second router is excluded, and at least one neighbor router of said first router in said subtree is a member of said multicast group.

25. The apparatus of claim 24, wherein said first router is further configured to determine whether said first router must transmit said update information by determining if said second router is not a member of said multicast group.

26. The apparatus of claim 25, wherein said update information comprises a time stamp, and wherein said first router further determines whether said first router must transmit said update information by determining if said time stamp is valid.

27. The apparatus of claim 26, wherein said first router is further configured to store a time stamp associated with said multicast group and said second router, wherein said time stamp comprises a first time stamp and wherein said first router is configured to determine whether said tire stamp is valid by determining if said first time stamp is more recent than said second time stamp.

28. An apparatus, comprising:

a plurality of routers in a multicast group configured to forward multicast packets in a network, wherein each of the plurality of routers reports control information including routing tree information to other routers of said plurality of routers, wherein said routing tree information comprises a source tree for a unicast routing protocol;

a first router;

a second router; and

a third router, wherein said first router comprises a multicast forwarding cache and is configured to receive a multicast packet from said second router in said network, wherein said multicast packet is from a selected source and for a selected multicast group,

wherein said first router is configured to determine, based at least in part, on said control information and the routing tree information reported by said second router to said first router, if said multicast packet is to be forwarded by said first router and to determine whether said first router is a next hop in a shortest path from said second router to the source of the multicast packet according to said source tree, and

wherein said first router, in response to a positive determination that said multicast packet is to be forwarded, is configured to forward said multicast packet to at least said third router,

wherein said first router is configured to create an entry indicating that a multicast packet from said selected source and said selected multicast group are to be forwarded after making a positive determination that said multicast packet is to be forwarded,

wherein said first router comprises a multicast packet-forwarding cache, and

wherein said multicast packets forwarding cache comprises an entry indicating each multicast packet recently forwarded by said first router.

29. The apparatus of claim 28, wherein said multicast packet comprises an address of the multicast group.

30. The apparatus of claim 28, wherein said multicast packet comprises an address of the source of said multicast packet.

31. The apparatus of claim, 28, wherein said multicast packet comprises a time value, wherein said time value is used to limit the time said multicast packet is allowed to remain in the system.

32. An apparatus, comprising:

a plurality of routers in a multicast group configured to forward multicast packets in a network, wherein each of the plurality of routers reports control information including routing tree information to other routers of said plurality of routers;

a first router;

a second router; and

a third router, wherein said first router comprises a multicast forwarding cache and is configured to receive a multicast packet from said second router in said network, wherein said multicast packet is from a selected source and for a selected multicast group,

wherein said first router is configured to determine, based at least in part, on said control information and the routing tree information reported by said second router to said first router, if said multicast packet is to be forwarded by said first router, and

wherein said first router, in response to a positive determination that said multicast packet is to be forwarded, is configured to forward said multicast packet to at least said third router, and

wherein said first router is configured to create an entry indicating that a multicast packet from said selected source and said selected multicast group are to be forwarded after making a positive determination that said multicast packet is to be forwarded,

wherein the routing tree information reported by said second router comprises a source tree for a unicast routing protocol, and

wherein said first router is further configured to determine if said second router is a next hop in a shortest path from said first router to the source of the multicast packet according to said source tree, and if said source tree has said first router in a subtree with at least one router in said subtree being a member of the multicast group.