Hierarchical routing knowledge for multicast packet routing

• US 6,078,590 A
• Filed: 07/14/1997
• Issued: 06/20/2000
• 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): Kizou, Hassan
• Assistant Examiner(s): Previl, Daniel
• Application Number:
  US08/897,215
• Time in Patent Office: 1,072 Days
• Field of Search: 370/400, 370/389, 370/351, 370/390, 370/408, 370/432, 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 of routing multicast packets in a network, including the steps of

defining a subset of said network;

defining a set of border routers within said subset;

for said border routers, maintaining a first set of unicast routing information for routing multicast packets from devices external to said subset; and

for routers within said subset other than said border routers, maintaining a second set of unicast routing information for routing multicast packets only from devices within said subset.

2. A method as in claim 1, wherein said subset comprises a component of a routing hierarchy, a network domain, a routing domain, or an autonomous routing group.

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

4. A method of maintaining a multicast distribution tree in a subset of a network, including the steps of

associating each multicast packet with a multicast source device and a set of destination devices;

associating said multicast source device with an upstream border router within the subset;

associating said destination devices with a corresponding set of downstream border routers within the subset;

transmitting multicast data packets from said multicast source device to said destination devices, by routing those multicast data packets from said multicast source device to said upstream border router;

transmitting multicast data packets from said multicast source device to said destination devices, by routing those multicast data packets within the subset from the upstream border router to the downstream border routers; and

transmitting multicast data packets from said multicast source device to said destination devices, by routing those multicast data packets from said downstream border routers to the destination devices.

5. A method as in claim 4, wherein said subset comprises a network domain, a routing domain, or an autonomous routing group.

6. A method as in claim 4, wherein each said multicast packet is transmitted from said multicast source device to said destination device without encapsulation.

7. A method of routing multicast packets in a network, including the steps of

defining a subset of said network;

defining a set of border routers within said subset;

for routing multicast packets from a multicast source device external to the subset, maintaining for a border router a first set of unitcast routing information regarding the multicast source device; and

for routing multicast packets from a multicast source device external to the subset, maintaining for a non-border router a second set of unicast routing information regarding only a border router within the subset which is expected to route the multicast packet to the non-border router.

8. A method as in claim 7, wherein said subset comprises a component of a routing hierarchy, a network domain, a routing domain, or an autonomous routing group.

9. A method as in claim 7, wherein said second set of unicast routing information includes identification of an upstream border router for each multicast source device outside said subset.