US 6,611,528 B1Grant
Hierarchical routing knowledge for multicast packet routing
Issue Date:2003-08-26
•47 Claims
•1 Drawing Sheets
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.
Metadata
Assignee
- Cisco Technology, Inc.
Inventors
- Dino Farinacci
- Yakov Rekhter
Application Information
Application Number:US 09/685,219
Filing Date:2000-10-10
Priority Date:1997-07-14
Art Unit:7
Classifications
IPC:
H04L 400
Field of Search:
370432370400370389370351370390370408370396
Patent Drawings (1 sheets)
Description
[0002] This is a continuation of copending U.S. patent application Ser. No. 09/585,700 filed May 31, 2000 entitled “Hierarchical Routing Knowledge for Multicast Packet Routing,” which, in turn, is a continuation of U.S. patent application Ser. No. 08/897,215 filed Jul. 14, 1997 (now U.S. Pat. No. 6,078,590). Said copending application and said patent are hereby incorporated by reference herein in their entireties.
BACKGROUND OF THE INVENTION
[0003] 1. Field of the Invention
[0004] The invention relates to routing multicast packets.
[0005] 2. Related Art
[0006] In a network of networks, sometimes called an “internet” (alternatively, an “internet”), routers are typically separated into a set of routing domains (alternatively, “autonomous routing groups” or “domains”). Routers in each routing domain maintain information about destinations and associated “next hops” to those destinations; the routers are able to maintain such information by exchanging routing protocol messages.
[0007] Such networks can include systems for transmitting packets which are unicast (directed to a single destination device) or multicast (directed to multiple destination devices). When packets are multicast, they are transmitted using a multicast distribution tree. Accordingly, when a router forwards a multicast packet, the router must maintain routing information about its communication interface to the next hop toward the root of the multicast distribution tree, and for all successive next hops leading to the multiple destination devices.
[0008] One problem which has arisen in the art is that a large amount of information must therefore be recorded for routing multicast packets; this problem is made worse with increasing size of the internet.
[0009] Accordingly, it would be desirable to provide a method and system for routing multicast packets in an internet, in which not all routers in a routing domain would be required to maintain complete routing information for roots of multicast trees, if those roots are external to the routing domain. This advantage is achieved in an embodiment of the invention in which only selected routers in a routing domain maintain routing information about those roots which are external to the routing domain, while all other routers in the routing domain maintain only routing information about those roots which are internal to the routing domain.
SUMMARY OF INVENTION
[0010] 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 network subset) maintain routing information about roots of multicast trees for roots which are 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 routing to border routers of the network subset, but not including routing to roots which are external to the network subset. The network subset is preferably a routing domain or other autonomous routing group.
[0011] In a preferred embodiment, 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 or other autonomous system, each multicast packet is associated with a multicast distribution tree. A subtree of the multicast distribution tree within a single routing domain is associated with an upstream border router (UBR) and a set of downstream border routers (DBRs). A “JOIN” or “PRUNE” protocol message includes information which associates a particular UBR with a root of a particular multicast tree. The UBR and DBRs maintain complete routing information for each root of a multicast tree, while all other routers in the network subset (non-border routers) maintain routing information only to destinations within the network subset, including the UBR and DBRs.
BRIEF DESCRIPTION OF THE DRAWING
[0012] FIG. 1 shows a block diagram of a routing domain embedded in a network.
DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT
[0013] In the following description, a embodiment of the invention is described with regard to preferred process steps and data structures. Those skilled in the art would recognize after perusal of this application that embodiments of the invention can be implemented using general purpose processors or special purpose processors adapted to particular process steps and data structures described herein, and that implementation of the process steps and data structures described herein would not require undue experimentation or further invention.
Routing Domain Within A Network
[0014] FIG. 1 shows a block diagram of a routing domain within a network.
[0015] In a network of networks 100, a network subset 110 includes a set of routers 120 internal to the network subset 110. Messages routed within the network subset 110 are routed by those routers 120 internal to the network subset 110.
[0016] In a preferred embodiment, the network subset 110 comprises a routing domain, but in alternative embodiments, the network subset 110 may comprise any other autonomous routing group, such as a set of routers which are topologically close, which share common administrative control, or which otherwise form a defined subset of the network 100.
[0017] The routers 120 include a set of border routers 170; all other routers 120 are non-border routers 180. Border routers 170 are those which are considered on the border of the network subset 110, as generally defined by having a routing peer relationship with both a router 120 within the network subset 110, as well as with a router 120 outside the network subset 110. Non-border routers 120 are all other routers 120 in the network subset 110.
[0018] Pairs of routers 120 are coupled by communication links 130, each of which is capable of transmitting packets 140 from one router 120 to another router 120. Packets 140 can include user data or protocol information, or both.
[0019] Each router 120 maintains routing information about the network 100, including information for routing unicast packets 140 (packets 140 which are specified for a single destination device 150) and information for routing multicast packets 140 (packets 140 which are specified for multiple destination devices 150).
Routing Multicast Packets
[0020] For multicast packets 140, additional information is maintained. A is multicast distribution tree comprises a set of routers 120 which distribute the multicast packets 140 from a selected multicast source device 160 to a plurality of destination is devices 150. As used herein with regard to routing multicast packets, the phrase “multicast source device” refers to any device which acts as the root of a multicast tree. The routers 120 maintain information regarding (a) the outbound communication links 130 in the multicast distribution tree, but also (b) the inbound communication link 130 the router 120 expects the multicast packet 140 to arrive from. The latter information allows the router 120 to discard multicast packets 140 which were misrouted, such as in a loop.
[0021] Where a multicast packet 140 is routed downward along the multicast distribution tree to one or more destination devices 150 outside the network subset 110, the one or more border routers 170 of the network subset 110 which route the packet 140 outside the network subset 110 are classed as downstream border routers (“DBR”) 170. A downstream border router 170 thus receives multicast packets 140 destined for particular destination devices 150 outside the network subset 110 and distributes those multicast packets 140 downstream in the multicast distribution tree to those particular destination devices 150 in a part of the multicast distribution tree which is outside the network subset 110.
[0022] Where a multicast packet 140 is routed along the multicast distribution tree from a multicast source device 160 outside the network subset 110, the border router 170 of the network subset 110 which routes the packet 140 from outside the network subset 110 is classed as an upstream border router (“UBR”) 170. An upstream border router 170 thus receives multicast packets 140 from a particular multicast source device 160 outside the network subset 110 and distributes those multicast packets 140 downstream in the multicast distribution tree. Part of the multicast distribution tree is within the network subset 110.
[0023] Each router 120 thus maintains routing information including entries for those multicast source devices 160 for which multicast packets must be forwarded. Where the multicast source device 160 is outside the network subset 110, this information includes (a) for border routers 170, routing information regarding the multicast source device 160 and all successive next hop devices, or (b) for non-border routers, 180, routing information for only the border router 170 which is expected to route the packet 140 from the multicast source device 160.
Multicast Packet Protocol Messages
[0024] In a preferred embodiment, the multicast distribution tree is created and modified by control messages in a Sparse Mode PIM multicast routing protocol. In alternative embodiments, other protocols, such as CBT, could be used instead or in addition. A “JOIN” protocol message is used to add a non-border routers 180 or a border router 170 to the multicast distribution tree. A “PRUNE” protocol message is used to remove a non-border routers 180 or a border router 170 from the multicast distribution tree.
[0025] Both JOIN and PRUNE protocol messages are transmitted from a first router 120 at a leaf of the multicast distribution tree to a sequence of routers 120 in the multicast distribution tree; which may traverse through a border router 170 in the direction of transmission toward the root of the multicast distribution tree. Once the multicast distribution tree includes a set of routers 120, information about the multicast distribution tree at each router 120 is sufficient to forward multicast packets 140 to those routers 120 in the multicast distribution tree, and therefore to those destination devices 150 for which the multicast packets 140 are destined.
[0026] Within the network subset 110, JOIN and PRUNE protocol messages each include information which designate the UBR 170 on a path to the multicast source device 160. Thus, non-border router 180 within the network subset 110 maintain routing information only about the UBR 170 for the multicast distribution tree for the network subset 110, but need not maintain routing information about the multicast source device 160.
[0027] Outside the network subset 110, JOIN and PRUNE protocol messages each designate the multicast source device 160 explicitly. Thus border routers 170 within the network subset 110, and all routers 120 outside the network subset 110, maintain routing information about the actual multicast source device 160 for the multicast distribution tree. Of course, some routers 120 outside the network subset 110 may be within a second network subset 110, and can therefore maintain routing information only about the UBR 170 for the multicast distribution tree for the second network subset 110.
[0028] When a DBR 170 receives a JOIN or PRUNE protocol message for a particular multicast distribution tree, and the DBR 170 determines that its upstream neighbor router 120 for that multicast distribution tree is a non-border routers 180, the DBR 170 uses the routing information from other border routers 170 within the network subset 110 to find an address (in a preferred embodiment, the IP address) of the UBR 170 for that multicast distribution tree, includes the address of the associated UBR 170 in a JOIN or PRUNE protocol message, and sends that JOIN or PRUNE protocol message to its upstream neighbor router 120.
[0029] When a DBR 170 which is part of a particular multicast distribution tree determines (such as from routing information received from other border routers 170 within the network subset 110) that the UBR 170 for that multicast distribution tree has changed, the DBR 170 removes itself using a PRUNE protocol message from the multicast distribution tree associated with the old UBR 170, and adds itself using a JOIN protocol message to the multicast distribution tree associated with the new UBR 170.
[0030] If the DBR 170 determines that its upstream neighbor router 120 towards the new UBR 170 is different from its upstream neighbor towards the old UBR 170, then the DBR 170 sends a JOIN protocol message to its upstream neighbor router 120 towards the new UBR 170, and sends a PRUNE protocol message to its upstream neighbor router 120 towards the old UBR 170. However, if the DBR 170 determines that its upstream neighbor router 120 towards the new UBR 170 is the same as its upstream neighbor router 120 towards the old UBR 170, the DBR 170 constructs a combined protocol message including both JOIN and PRUNE components; a PRUNE component includes the address of the old UBR 170, while a JOIN component includes the address of the new UBR 170.
[0031] When a non-border routers 180 receives a combined protocol message including both JOIN and PRUNE components, the non-border routers 180 follows a similar procedure. However, when selecting an upstream neighbor router 120 for its own JOIN or PRUNE protocol message, the non-border routers 180 uses the address of the UBR 170 included in the received combined protocol message rather than the address of the multicast source device 160. The non-border routers 180 copies the UBR 170 information from the received combined protocol message into a new combined protocol message for sending upstream towards the multicast source device 160.
[0032] If the combined protocol message received by the non-border routes 180 contains both JOIN and PRUNE components for the same multicast distribution tree, the non-border routers 180 does not remove the sending router 120 from the multicast distribution tree specified by the PRUNE component of the combined protocol message.
[0033] If the message contains both JOIN and PRUNE components for the same multicast distribution tree, the non-border routers 180 determines whether its upstream neighbor router 120 towards a first UBR 170 in the PRUNE component is different from its upstream neighbor router towards a second UBR 170 in the JOIN component of the combined protocol message. If the first UBR 170 and the second UBR 170 are different, the non-border routers 180 sends a PRUNE protocol message to its upstream neighbor router 120 towards the UBR 170 in the PRUNE component, and sends a JOIN protocol message to its upstream neighbor router 120 towards the UBR 170 in the JOIN component of the combined protocol message. However, if the first UBR 170 and the second UBR 170 are identical, the non-border routers 180 transmits the combined protocol message with both JOIN and PRUNE components unchanged to that upstream neighbor router 120.
[0034] When a border router 170 receives a combined protocol message including both JOIN and PRUNE components, and the UBR 170 information included in the combined protocol message identifies that same border router 170, the border router 170 follows a similar procedure, but when sending its own combined protocol message, the border router 170 sends that combined protocol message without any UBR 170 information.
[0035] Because multicast packets 140 are transmitted using the multicast distribution tree, and because the multicast distribution trees is maintained using hierarchical routing knowledge (within the network subset 110, knowledge about multicast source it devices 160 in the network subset 110, and only outside or on the border of the network subset 110, knowledge about multicast source devices 160 outside the network subset 110), it is possible to distribute multicast packets 140 using hierarchical routing knowledge without encapsulation. Once the multicast distribution tree is constructed, as described bed herein, any one of the routers 120 can select multicast packets 140 that should be forwarded using that multicast distribution tree without requiring the router 120 to maintain routing information for the root of that multicast distribution tree.
Alternative Embodiments
[0036] Although preferred embodiments are disclosed herein, many variations are possible which remain within the concept, scope, and spirit of the invention, and these variations would become clear to those skilled in the art after perusal of this application.
Claims
What is claimed is:
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.
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.
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.
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.
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.
Patent Citations (204)
| Patent | Date | Inventor | Cited By |
|---|---|---|---|
| US4131767(A) | 1978-12-01 | Weinstein | Applicant |
| US4161719(A) | 1979-07-01 | Parikh et al. | Applicant |
| US4316284(A) | 1982-02-01 | Howson | Applicant |
| US4397020(A) | 1983-08-01 | Howson | Applicant |
| US4419728(A) | 1983-12-01 | Larson | Applicant |
| US4424565(A) | 1984-01-01 | Larson | Applicant |
| US4437087(A) | 1984-03-01 | Petr | Applicant |
| US4438511(A) | 1984-03-01 | Baran | Applicant |
| US4439763(A) | 1984-03-01 | Limb | Applicant |
| US4445213(A) | 1984-04-01 | Baugh et al. | Applicant |
| US4446555(A) | 1984-05-01 | Devault et al. | Applicant |
| US4456957(A) | 1984-06-01 | Schieltz | Applicant |
| US4464658(A) | 1984-08-01 | Thelen | Applicant |
| US4499576(A) | 1985-02-01 | Fraser | Applicant |
| US4506358(A) | 1985-03-01 | Montgomery | Applicant |
| US4507760(A) | 1985-03-01 | Fraser | Applicant |
| US4532626(A) | 1985-07-01 | Flores et al. | Applicant |
| US4644532(A) | 1987-02-01 | George et al. | Applicant |
| US4646287(A) | 1987-02-01 | Larson et al. | Applicant |
| US4677423(A) | 1987-06-01 | Benvenuto et al. | Applicant |
| US4679189(A) | 1987-07-01 | Olson et al. | Applicant |
| US4679227(A) | 1987-07-01 | Hughes-Hartogs | Applicant |
| US4723267(A) | 1988-02-01 | Jones et al. | Applicant |
| US4731816(A) | 1988-03-01 | Hughes-Hartogs | Applicant |
| US4750136(A) | 1988-06-01 | Arpin et al. | Applicant |
| US4757495(A) | 1988-07-01 | Decker et al. | Applicant |
| US4763191(A) | 1988-08-01 | Gordon et al. | Applicant |
| US4769810(A) | 1988-09-01 | Eckberg, Jr. et al. | Applicant |
| US4769811(A) | 1988-09-01 | Eckberg, Jr. et al. | Applicant |
| US4771425(A) | 1988-09-01 | Baran et al. | Applicant |
| US4819228(A) | 1989-04-01 | Baran et al. | Applicant |
| US4827411(A) | 1989-05-01 | Arrowood et al. | Applicant |
| US4833706(A) | 1989-05-01 | Hughes-Hartogs | Applicant |
| US4835737(A) | 1989-05-01 | Herrig et al. | Applicant |
| US4864559(A) | 1989-09-01 | Perlman | Applicant |
| US4879551(A) | 1989-11-01 | Georgiou et al. | Applicant |
| US4893306(A) | 1990-01-01 | Chao et al. | Applicant |
| US4903261(A) | 1990-02-01 | Baran et al. | Applicant |
| US4922486(A) | 1990-05-01 | Lidinsky et al. | Applicant |
| US4933937(A) | 1990-06-01 | Konishi | Applicant |
| US4960310(A) | 1990-10-01 | Cushing | Applicant |
| US4962497(A) | 1990-10-01 | Ferenc et al. | Applicant |
| US4962532(A) | 1990-10-01 | Kasiraj et al. | Applicant |
| US4965772(A) | 1990-10-01 | Daniel et al. | Applicant |
| US4970678(A) | 1990-11-01 | Sladowski et al. | Applicant |
| US4979118(A) | 1990-12-01 | Kheradpir | Applicant |
| US4980897(A) | 1990-12-01 | Decker et al. | Applicant |
| US4991169(A) | 1991-02-01 | Davis et al. | Applicant |
| US5003595(A) | 1991-03-01 | Collins et al. | Applicant |
| US5014265(A) | 1991-05-01 | Hahne et al. | Applicant |
| US5020058(A) | 1991-05-01 | Holden et al. | Applicant |
| US5033076(A) | 1991-07-01 | Jones et al. | Applicant |
| US5054034(A) | 1991-10-01 | Hughes-Hartogs | Applicant |
| US5059925(A) | 1991-10-01 | Weisbloom | Applicant |
| US5072449(A) | 1991-12-01 | Enns et al. | Applicant |
| US5088032(A) | 1992-02-01 | Bosack | Applicant |
| US5095480(A) | 1992-03-01 | Fenner | Applicant |
| USRE33900(E) | 1992-04-01 | Howson | Applicant |
| US5115431(A) | 1992-05-01 | Williams et al. | Applicant |
| US5128945(A) | 1992-07-01 | Enns et al. | Applicant |
| US5136580(A) | 1992-08-01 | Videlock et al. | Applicant |
| US5166930(A) | 1992-11-01 | Braff et al. | Applicant |
| US5199049(A) | 1993-03-01 | Wilson | Applicant |
| US5206886(A) | 1993-04-01 | Bingham | Applicant |
| US5208811(A) | 1993-05-01 | Kashio et al. | Applicant |
| US5212686(A) | 1993-05-01 | Joy et al. | Applicant |
| US5224099(A) | 1993-06-01 | Corbalis et al. | Applicant |
| US5226120(A) | 1993-07-01 | Brown et al. | Applicant |
| US5228062(A) | 1993-07-01 | Bingham | Applicant |
| US5229994(A) | 1993-07-01 | Balzano et al. | Applicant |
| US5237564(A) | 1993-08-01 | Lespagnol et al. | Applicant |
| US5241682(A) | 1993-08-01 | Bryant et al. | Applicant |
| US5243342(A) | 1993-09-01 | Kattemalalavadi et al. | Applicant |
| US5243596(A) | 1993-09-01 | Port et al. | Applicant |
| US5247516(A) | 1993-09-01 | Bernstein et al. | Applicant |
| US5249178(A) | 1993-09-01 | Kurano et al. | Applicant |
| US5253251(A) | 1993-10-01 | Aramaki | Applicant |
| US5255291(A) | 1993-10-01 | Holden et al. | Applicant |
| US5260933(A) | 1993-11-01 | Rouse | Applicant |
| US5260978(A) | 1993-11-01 | Fleischer et al. | Applicant |
| US5268592(A) | 1993-12-01 | Bellamy et al. | Applicant |
| US5268900(A) | 1993-12-01 | Hluchyj et al. | Applicant |
| US5271004(A) | 1993-12-01 | Proctor et al. | Applicant |
| US5274631(A) | 1993-12-01 | Bhardwaj | Applicant |
| US5274635(A) | 1993-12-01 | Rahman et al. | Applicant |
| US5274643(A) | 1993-12-01 | Fisk | Applicant |
| US5280470(A) | 1994-01-01 | Buhrke et al. | Applicant |
| US5280480(A) | 1994-01-01 | Pitt et al. | Applicant |
| US5280500(A) | 1994-01-01 | Mazzola et al. | Applicant |
| US5283783(A) | 1994-02-01 | Nguyen et al. | Applicant |
| US5287103(A) | 1994-02-01 | Kasprzyk et al. | Applicant |
| US5287453(A) | 1994-02-01 | Roberts | Applicant |
| US5291482(A) | 1994-03-01 | McHarg et al. | Applicant |
| US5305311(A) | 1994-04-01 | Lyles | Applicant |
| US5307343(A) | 1994-04-01 | Bostica et al. | Applicant |
| US5309437(A) | 1994-05-01 | Perlman et al. | Applicant |
| US5311509(A) | 1994-05-01 | Heddes et al. | Applicant |
| US5313454(A) | 1994-05-01 | Bustini et al. | Applicant |
| US5313582(A) | 1994-05-01 | Hendel et al. | Applicant |
| US5317562(A) | 1994-05-01 | Nardin et al. | Applicant |
| US5319644(A) | 1994-06-01 | Liang | Applicant |
| US5327421(A) | 1994-07-01 | Hiller et al. | Applicant |
| US5331637(A) | 1994-07-01 | Francis et al. | Examiner |
| US5345445(A) | 1994-09-01 | Hiller et al. | Applicant |
| US5345446(A) | 1994-09-01 | Hiller et al. | Applicant |
| US5353283(A) | 1994-10-01 | Tsuchiya | Examiner |
| US5359592(A) | 1994-10-01 | Corbalis et al. | Applicant |
| US5361250(A) | 1994-11-01 | Nguyen et al. | Applicant |
| US5361256(A) | 1994-11-01 | Doeringer et al. | Examiner |
| US5361259(A) | 1994-11-01 | Hunt et al. | Applicant |
| US5365524(A) | 1994-11-01 | Hiller et al. | Applicant |
| US5367517(A) | 1994-11-01 | Cidon et al. | Applicant |
| US5371852(A) | 1994-12-01 | Attanasio et al. | Applicant |
| US5386567(A) | 1995-01-01 | Lien et al. | Applicant |
| US5390170(A) | 1995-02-01 | Sawant et al. | Applicant |
| US5390175(A) | 1995-02-01 | Hiller et al. | Applicant |
| US5394394(A) | 1995-02-01 | Crowther et al. | Applicant |
| US5394402(A) | 1995-02-01 | Ross | Applicant |
| US5400325(A) | 1995-03-01 | Chatwani et al. | Applicant |
| US5408469(A) | 1995-04-01 | Opher et al. | Applicant |
| US5416842(A) | 1995-05-01 | Aziz | Applicant |
| US5422880(A) | 1995-06-01 | Heitkamp et al. | Applicant |
| US5422882(A) | 1995-06-01 | Hiller et al. | Applicant |
| US5423002(A) | 1995-06-01 | Hart | Applicant |
| US5426636(A) | 1995-06-01 | Hiller et al. | Applicant |
| US5428607(A) | 1995-06-01 | Hiller et al. | Applicant |
| US5430715(A) | 1995-07-01 | Corbalis et al. | Applicant |
| US5430729(A) | 1995-07-01 | Rahnema | Applicant |
| US5442457(A) | 1995-08-01 | Najafi | Applicant |
| US5442630(A) | 1995-08-01 | Gaglieardi et al. | Applicant |
| US5452297(A) | 1995-09-01 | Hiller et al. | Applicant |
| US5473599(A) | 1995-12-01 | Li et al. | Applicant |
| US5473607(A) | 1995-12-01 | Hausman et al. | Applicant |
| US5477541(A) | 1995-12-01 | White et al. | Applicant |
| US5485455(A) | 1996-01-01 | Dobbins et al. | Applicant |
| US5490140(A) | 1996-02-01 | Abensour et al. | Applicant |
| US5490258(A) | 1996-02-01 | Fenner | Applicant |
| US5491687(A) | 1996-02-01 | Christensen et al. | Applicant |
| US5491804(A) | 1996-02-01 | Heath et al. | Applicant |
| US5497368(A) | 1996-03-01 | Reijnierse et al. | Applicant |
| US5504747(A) | 1996-04-01 | Sweazey | Applicant |
| US5509006(A) | 1996-04-01 | Wilford et al. | Applicant |
| US5511168(A) | 1996-04-01 | Perlman et al. | Applicant |
| US5517494(A) | 1996-05-01 | Green | Applicant |
| US5519704(A) | 1996-05-01 | Farinacci et al. | Applicant |
| US5519858(A) | 1996-05-01 | Walton et al. | Applicant |
| US5526489(A) | 1996-06-01 | Nilakantan et al. | Applicant |
| US5530963(A) | 1996-06-01 | Moore et al. | Applicant |
| US5535195(A) | 1996-07-01 | Lee | Applicant |
| US5539734(A) | 1996-07-01 | Burwell et al. | Applicant |
| US5541911(A) | 1996-07-01 | Nilakantan et al. | Applicant |
| US5541927(A) | 1996-07-01 | Kristol et al. | Examiner |
| US5546370(A) | 1996-08-01 | Ishikawa | Applicant |
| US5555244(A) | 1996-09-01 | Gupta et al. | Applicant |
| US5561669(A) | 1996-10-01 | Lenney et al. | Applicant |
| US5583862(A) | 1996-12-01 | Callon | Applicant |
| US5592470(A) | 1997-01-01 | Rudrapatna et al. | Applicant |
| US5598581(A) | 1997-01-01 | Daines et al. | Applicant |
| US5600798(A) | 1997-02-01 | Chenrukui et al. | Applicant |
| US5604868(A) | 1997-02-01 | Komine et al. | Applicant |
| US5608726(A) | 1997-03-01 | Virgile | Applicant |
| US5617417(A) | 1997-04-01 | Sathe et al. | Applicant |
| US5617421(A) | 1997-04-01 | Chin et al. | Applicant |
| US5630125(A) | 1997-05-01 | Zellweger | Applicant |
| US5631908(A) | 1997-05-01 | Saxe | Applicant |
| US5632021(A) | 1997-05-01 | Jennings et al. | Applicant |
| US5634010(A) | 1997-05-01 | Ciscon et al. | Applicant |
| US5638359(A) | 1997-06-01 | Peltola | Applicant |
| US5644718(A) | 1997-07-01 | Belove et al. | Applicant |
| US5659684(A) | 1997-08-01 | Giovannoni et al. | Applicant |
| US5666353(A) | 1997-09-01 | Klausmeier et al. | Applicant |
| US5673265(A) | 1997-09-01 | Gupta et al. | Applicant |
| US5678006(A) | 1997-10-01 | Valizadeh et al. | Applicant |
| US5680116(A) | 1997-10-01 | Hashimoto et al. | Applicant |
| US5684797(A) | 1997-11-01 | Azner et al. | Applicant |
| US5687324(A) | 1997-11-01 | Green et al. | Applicant |
| US5689506(A) | 1997-11-01 | Chiussi et al. | Applicant |
| US5694390(A) | 1997-12-01 | Yamato et al. | Applicant |
| US5724351(A) | 1998-03-01 | Chao et al. | Applicant |
| US5748186(A) | 1998-05-01 | Raman | Applicant |
| US5748617(A) | 1998-05-01 | McLain, Jr. | Applicant |
| US5751971(A) | 1998-05-01 | Dobbins et al. | Examiner |
| US5754547(A) | 1998-05-01 | Nakazawa | Applicant |
| US5802054(A) | 1998-09-01 | Bellenger | Applicant |
| US5835710(A) | 1998-11-01 | Nagami et al. | Applicant |
| US5854903(A) | 1998-12-01 | Morrison et al. | Applicant |
| US5856981(A) | 1999-01-01 | Voelker | Applicant |
| US5892924(A) | 1999-04-01 | Lyon et al. | Applicant |
| US5898686(A) | 1999-04-01 | Virgile | Applicant |
| US5903559(A) | 1999-05-01 | Acharya et al. | Applicant |
| US5917820(A) | 1999-06-01 | Rekhter | Examiner |
| US5930259(A) | 1999-07-01 | Katsube et al. | Examiner |
| US6055364(A) | 2000-04-01 | Speakman et al. | Applicant |
| US6078590(A) | 2000-06-01 | Farinacci et al. | Applicant |
| US6182147(B1) | 2001-01-01 | Farinacci | Applicant |
| US6192417(B1) | 2001-02-01 | Block et al. | Examiner |
| US6215766(B1) | 2001-04-01 | Ammar et al. | Examiner |
| EP384758 | 1990-08-01 | Applicant | |
| EP431751 | 1991-06-01 | Applicant | |
| EP567217 | 1993-10-01 | Applicant | |
| WO93/07569 | 1993-04-01 | Applicant | |
| WO93/07692 | 1993-04-01 | Applicant | |
| WO94/01828 | 1994-01-01 | Applicant | |
| WO95/20850 | 1995-08-01 | Applicant |
Non-Patent Literature (16)
- U.S. patent application Ser. No. 09/167,682, Mahajan et al., filed Oct. 7, 1998.Applicant
- Zhang, et al., “Rate-Controlled Static-Priority Queueing,” INFOCOM 1993, pp. 227-236.Applicant
- Deering, et al., “Multicast Routing in Datagram Internetworks and Extended LANs”, ACM Transactions on Computer Systems, vol. 8, No. 2, May 1990, pp. 85-110.Applicant
- Deering, et al., “An Architecture for Wide-Area Multicast Routing”, Computer Commnication Review, ACM SiGCOMM, vol. 24, No. 4, Oct. 1994, pp. 126-135.Applicant
- http://www.cisco.com/warp/public/614/17.htm/ “Multicast Routing” published at least as early as Sep., 27, 1999.Applicant
- William Stallings, Data and Computer Communications, pp. 329-333, Prentice Hall, Upper Saddle River, New Jersey 07458.Applicant
- Allen, M., “Novell IPX Over Various WAN Media (IPXW AN).” Network Working Group, RFC 1551, Dec. 1993, pp. 1-22.Applicant
- Becker, D., 3c589.c:A Etherlink3 ethernet driver for linux, [email protected], May 3, 1994, pp. 1-13.Applicant
- Chowdhury, et al., “Alternative Bandwidth Allocation Algorithms for Packet Video in ATM Networks,” INFOCOM 1992, pp. 1061-1068.Applicant
- Doeringer, W., “Routing on Longest-Matching Prefixes,” IEEE/ACM Transactions in Networking, vol. 4, No. 1, Feb. 1996, pp. 86-97.Applicant
- Esaki, et al., “Datagram Delivery in an ATM-Internet,” 2334b IEICE Transactions on Communications, Mar., 1994, No. 3, Tokyo, Japan.Applicant
- IBM Corporation, “Method and Apparatus for the Statistical Multiplexing of Voice, Data and Image Signals,” IBM Technical Disclosure Bulletin, No. 6, Nov. 1992, pp. 409-411.Applicant
- Pei, et al., “Putting Routing Tables in Silicon,” IEEE Network Magazine, Jan. 1992, pp. 42-50.Applicant
- Perkins, D., “Requirements for an Internet Standard Point-to-Point Protocol,” Network Working Group, RFC 1547, Dec. 1993, pp. 1-19.Applicant
- Simpson, W., The Point-to-Point Protocol (PPP), Network Working Group, RFC 1548, Dec. 1993, pp. 1-53.Applicant
- Tsuchiya, P.F., “A Search Algorithm for Tabe Entries with Non-Contiguous Wildcarding,” Abstract, Bellcore.Applicant