Hierarchical routing knowledge for multicast packet routing

• US 6,611,528 B1
• Filed: 10/10/2000
• Issued: 08/26/2003
• Est. Priority Date: 07/14/1997
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Farinacci, Dino, Rekhter, Yakov
• Primary Examiner(s): VANDERPUYE, KENNETH N
• Application Number:
  US09/685,219
• Time in Patent Office: 1,050 Days
• Field of Search: 370/432, 370/400, 370/389, 370/351, 370/390, 370/408, 370/396
• US Class Current: 370/432
• CPC Class Codes: H04L 12/18 for broadcast or conference , e.g. multicast
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/16 Multipoint routing

Abstract

The invention provides a method and system for multicast packet routing, in which only selected routers in a network subset (in a preferred embodiment, those routers on the border of the domain) maintain routing information external to the network subset, while all other routers in the network subset (non-border routers) maintain only information regarding routing within the network subset, including which border routers are on the path from the multicast source device or to the destination devices. The network subset is preferably a domain or other routing domain. A multicast distribution tree is maintained, using protocol messages which are transmitted from leaf nodes toward a root of the tree, while data packets to be multicast are distributed from the root toward the leaf nodes. In each network subset, such as a routing domain, each multicast packet is associated with a multicast distribution tree. The multicast distribution tree is associated with an upstream border router (UBR) and a set of downstream border routers (DBRs). The UBR and DBRs maintain complete routing information for each multicast source device, while all other routers in the network subset maintain routing information only to the UBR and DBRs. A “JOIN” or “PRUNE” protocol message associates a particular UBR with a particular multicast source device, so that non-border routers within the network subset only have to maintain routing information to border routers, while still being able to correctly maintain a multicast distribution tree rooted at a node outside the network subset.

Claims

1. A method for routing in a network a multicast packet using a first router, comprising:

receiving at the router the packet; and

forwarding the packet from the router to a second router based upon a first set of unicast routing information maintained at the first router, the information being for use in routing multicast packets from devices external to a subset of the network, the subset comprising the first router and the second router, the second router maintaining a second set of unicast routing information for use in routing multicast packets only from devices within the subset.

2. A method according to claim 1, wherein the subset comprises a component of a routing hierarchy, a network domain, a routing domain, or an autonomous routing group.

3. A method according to claim 1, wherein the second set of unicast information includes identification of an upstream border router for each multicast source device outside said subset.

4. A method according to claim 1, wherein, as received by the first router, the packet received by the first router is unencapsulated.

47. A computer readable medium, comprising:

said computer readable media containing instructions for execution in a processor for the practice of the method of claim 1, or claim 5.

5. A method for routing in a network a multicast packet using a first router, comprising:

receiving at the router the packet, the packet having been forwarded to the router from a second router, the first and second routers being in a subset of the network, the second router having forwarded the packet to the first router based upon a first set of unicast routing information maintained by the second router for use in routing multicast packets from devices external to the subset; and

forwarding from the first router the packet received from the second router based upon a second set of unicast routing information for use in routing multicast packets only from devices within the subset.

6. A method according to claim 5, wherein the subset comprises a component of a routing hierarchy, a network domain, a routing domain, or an autonomous routing group.

7. A method according to claim 5, wherein the second set of unicast information includes identification of an upstream border router for each multicast source device outside said subset.

8. A method according to claim 5, wherein, as received by the second router, the packet received by the first router is unencapsulated.

9. A first router for routing in a network a multicast packet, comprising:

means for receiving at the router the packet; and

means for forwarding the packet from the router to a second router based upon a first set of unicast routing information maintained at the router, the information being for use in routing multicast packets from devices external to a subset of the network, the subset comprising the first router and the second router, the second router maintaining a second set of unicast routing information for use in routing multicast packets only from devices within the subset.

10. A first router according to claim 9, wherein the subset comprises a component of a routing hierarchy, a network domain, a routing domain, or an autonomous routing group.

11. A first router according to claim 9, wherein the second set of unicast information includes identification of an upstream border router for each multicast source device outside said subset.

12. A first router according to claim 9, wherein, as received by the first router, the packet received by the first router is unencapsulated.

13. A first router for routing in a network a multicast packet, comprising:

means for receiving at the router the packet, the packet having been forwarded to the router from a second router, the first and second routers being in a subset of the network, the second router having forwarded the packet to the first router based upon a first set of unicast routing information maintained by the second router for use in routing multicast packets from devices external to the subset; and

means for forwarding from the first router the packet received from the second router based upon a second set of unicast routing information for use in routing multicast packets only from devices within the subset.

14. A first router according to claim 13, wherein the subset comprises a component of a routing hierarchy, a network domain, a routing domain, or an autonomous routing group.

15. A first router according to claim 13, wherein the second set of unicast information includes identification of an upstream border router for each multicast source device outside said subset.

16. A first router according to claim 13, wherein, as received by the second router, the packet received by the first router is unencapsulated.

17. A first router for routing in a network a multicast packet, comprising:

a first mechanism configured to receive at the router the packet; and

a second mechanism configured to forward the packet from the router to a second router based upon a first set of unicast routing information maintained at the first router, the information being for use in routing multicast packets from devices external to a subset of the network, the subset comprising the first router and the second router, the second router maintaining a second set of unicast routing information for use in routing multicast packets only from devices within the subset.

18. A first router according to claim 17, wherein the subset comprises a component of a routing hierarchy, a network domain, a routing domain, or an autonomous routing group.

19. A first router according to claim 17, wherein the second set of unicast information includes identification of an upstream border router for each multicast source device outside said subset.

20. A first router according to claim 17, wherein, as received by the first router, the packet received by the first router is unencapsulated.

21. A first router for routing in a network a multicast packet, comprising:

a first mechanism configured to receive at the router the packet, the packet having been forwarded to the router from a second router, the first and second routers being comprised in a subset of the network, the second router having forwarded the packet to the first router based upon a first set of unicast routing information maintained by the second router for use in routing multicast packets from devices external to the subset; and

a second mechanism configured to forward from the first router the packet received from the second router based upon a second set of unicast routing information for use in routing multicast packets only from devices within the subset.

22. A first router according to claim 21, wherein the subset comprises a component of a routing hierarchy, a network domain, a routing domain, or an autonomous routing group.

23. A first router according to claim 21, wherein the second set of unicast information includes identification of an upstream border router for each multicast source device outside said subset.

24. A first router according to claim 21, wherein, as received by the second router, the packet received by the first router is unencapsulated.

25. Computer-readable memory comprising computer-executable program instructions that when executed cause routing in a network of a multicast packet using a first router, the instructions when executed also causing:

receiving at the router of the packet; and

forwarding of the packet from the router to a second router based upon a first set of unicast routing information maintained at the router, the information being for use in routing multicast packets from devices external to a subset of the network, the subset comprising the first router and the second router, the second router maintaining a second set of unicast routing information for use in routing multicast packets only from devices within the subset.

26. Memory according to claim 25, wherein the subset comprises a component of a routing hierarchy, a network domain, arouting domain, or an autonomous routing group.

27. Memory according to claim 25, wherein the second set of unicast information includes identification of an upstream border router for each multicast source device outside said subset.

28. Memory according to claim 25, wherein, as received by the first router, the packet received by the first router is unencapsulated.

29. Computer-readable memory comprising computer-executable program instructions that when executed cause routing in a network of a multicast packet using a first router, the instructions when executed also causing:

receiving at the router the packet, the packet having been forwarded to the router from a second router, the first and second routers being in a subset of the network, the second router having forwarded the packet to the first router based upon a first set of unicast routing information maintained by the second router for use in routing multicast packets from devices external to the subset; and

forwarding from the first router of the packet received from the second router based upon a second set of unicast routing information for use in routing multicast packets from devices within the subset.

30. Memory according to claim 29, wherein the subset comprises a component of a routing hierarchy, a network domain, a routing domain, or an autonomous routing group.

31. Memory according to claim 29, wherein the second set of unicast information includes identification of an upstream border router for each multicast source device outside said subset.

32. Memory according to claim 29, wherein, as received by the second router, the packet received by the first router is unencapsulated.

33. A system of routers for routing a multicast packet in a network, comprising:

a network subset;

one or more routers internal to the network subset configured as a border router, the border router maintaining a first set of multicast routing information for devices external to the network subset; and

,

one or more routers internal to the network subset configured as a non-border router, the non-border router maintaining a second set of unicast routing information only for devices internal to the network subset.

34. A system of routers according to claim 33, wherein the border router is configured as an upstream border router that receives multi-cast packets from a multicast source device external to the network subset and distributes these packets downstream using unicast routing information to routers within the network subset.

35. A system of routers according to claim 34, wherein the second set of routing information includes identification of an upstream border router for each multicast source device external to the subset.

36. A system of routers according to claim 33, wherein the border router is configured as a downstream border router that receives unicast packets from a device within the network subset and distributes these packets downstream via multicast to a set of destination devices external to the network subset.

37. A system of routers according to claim 36, wherein the second set of routing information includes identification of a downstream border router that receives unicast packets from a device within the network subset and distributes these packets downstream via multicast to a set of destination devices external to the network subset.

38. A system of routers according to claim 33, wherein the network subset comprises a component of a routing hierarchy, a network domain, a routing domain, or an autonomous routing group.

39. A router used for routing a multicast packet in a network, the router belonging to a network subset that maintains at least part of a multicast distribution tree, the router comprising:

a first set of routing information maintained for routing multicast packets external to said network subset; and

,

a second set of routing information maintained for routing unicast packets internal to said network subset,

wherein, said multicast packets are transmitted as unicast packets while within said network subset.

40. A router according to claim 39, wherein the second set of routing information includes identification of an upstream border router that receives multi-cast packets from a multicast source device external to the network subset and distributes these packets downstream using unicast routing information to routers within the network subset.

41. A router according to claim 39, wherein the second set of routing information includes identification of a downstream border router that receives unicast packets from a device within the network subset and distributes these packets downstream via multicast to a set of destination devices external to the network subset.

42. A router according to claim 39, wherein the network subset comprises a component of a routing hierarchy, a network domain, a routing domain, or an autonomous routing group.

45. A router according to claim 39, wherein the second set of routing information includes identification of a downstream border router that receives unicast packets from a device within the network subset and distributes these packets downstream via multicast to a set of destination devices external to the network subset.

43. A router used for routing a multicast packet in a network, the router configurable as a border router or as a non-border router of a network subset, the router comprising:

means for defining a network subset;

means for defining a set of border routers, the border routers internal to the network subset;

if the router is configured as a border router of the network subset, means for maintaining a first set of multicast routing information for devices external to the network subset;

if the router is configured as a non-border router of the network subset, means for maintaining a second set of unicast routing information for devices internal to the network subset, and not maintaining multicast routing information for devices external to the network subset.

44. A router according to claim 43, wherein the second set of routing information includes identification of an upstream border router that receives multi-cast packets from a multicast source device external to the network subset and distributes these packets downstream using unicast routing information to routers within the network subset.

46. A router according to claim 43, wherein the network subset comprises a component of a routing hierarchy, a network domain, a routing domain, or an autonomous routing group.