Patent US6611528B1 successfully refreshed from Google Patents.
US6611528B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Hierarchical routing knowledge for multicast packet routing
Assignee: Cisco Technology Inc
•
Filing: 2000-10-10
•
Granted: 2003-08-26
•
Expires: 2020-10-10
Abstract
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.
Inventors
- 👤 Dino Farinacci
- 👤 Yakov Rekhter
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 07:56
CPC Classifications
H; H04; H04L; H04L12/00; H04L12/02; H04L12/16; H04L12/18; H04L45/00; H04L45/02; H04L45/04; H04L45/16
Claims Analysis
Total Claims: 58
Claim 1
Independent Claim
97 words
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.
Claim 2
Independent Claim
97 words
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.
Claim 3
Dependent Claim
28 words
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.
Claim 4
Dependent Claim
29 words
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.
Claim 5
Dependent Claim
23 words
A method according to claim 1 , wherein, as received by the first router, the packet received by the first router is unencapsulated.
Claim 6
Independent Claim
116 words
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.
Claim 7
Independent Claim
116 words
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.
Claim 8
Dependent Claim
28 words
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.
Claim 9
Dependent Claim
29 words
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.
Claim 10
Dependent Claim
23 words
A method according to claim 5 , wherein, as received by the second router, the packet received by the first router is unencapsulated.
Claim 11
Dependent Claim
97 words
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.
Claim 12
Dependent Claim
97 words
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.
Claim 13
Dependent Claim
29 words
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.
Claim 14
Dependent Claim
30 words
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.
Claim 15
Dependent Claim
24 words
A first router according to claim 9 , wherein, as received by the first router, the packet received by the first router is unencapsulated.
Claim 16
Dependent Claim
117 words
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.
Claim 17
Dependent Claim
117 words
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.
Claim 18
Dependent Claim
29 words
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.
Claim 19
Dependent Claim
30 words
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.
Claim 20
Dependent Claim
24 words
A first router according to claim 13 , wherein, as received by the second router, the packet received by the first router is unencapsulated.
Claim 21
Dependent Claim
104 words
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.
Claim 22
Dependent Claim
104 words
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.
Claim 23
Dependent Claim
29 words
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.
Claim 24
Dependent Claim
30 words
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.
Claim 25
Dependent Claim
24 words
A first router according to claim 17 , wherein, as received by the first router, the packet received by the first router is unencapsulated.
Claim 26
Dependent Claim
124 words
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.
Claim 27
Dependent Claim
124 words
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.
Claim 28
Dependent Claim
29 words
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.
Claim 29
Dependent Claim
30 words
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.
Claim 30
Dependent Claim
24 words
A first router according to claim 21 , wherein, as received by the second router, the packet received by the first router is unencapsulated.
Claim 31
Dependent Claim
111 words
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.
Claim 32
Dependent Claim
111 words
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.
Claim 33
Dependent Claim
26 words
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.
Claim 34
Dependent Claim
28 words
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.
Claim 35
Dependent Claim
22 words
Memory according to claim 25 , wherein, as received by the first router, the packet received by the first router is unencapsulated.
Claim 36
Dependent Claim
129 words
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.
Claim 37
Dependent Claim
129 words
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.
Claim 38
Dependent Claim
27 words
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.
Claim 39
Dependent Claim
28 words
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.
Claim 40
Dependent Claim
22 words
Memory according to claim 29 , wherein, as received by the second router, the packet received by the first router is unencapsulated.
Claim 41
Independent Claim
82 words
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.
Claim 42
Independent Claim
82 words
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.
Claim 43
Dependent Claim
49 words
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.
Claim 44
Dependent Claim
32 words
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.
Claim 45
Dependent Claim
49 words
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.
Claim 46
Dependent Claim
52 words
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.
Claim 47
Dependent Claim
31 words
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.
Claim 48
Dependent Claim
78 words
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.
Claim 49
Dependent Claim
78 words
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.
Claim 50
Dependent Claim
50 words
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.
Claim 51
Dependent Claim
50 words
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.
Claim 52
Dependent Claim
29 words
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.
Claim 53
Dependent Claim
125 words
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.
Claim 54
Dependent Claim
125 words
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.
Claim 55
Dependent Claim
50 words
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.
Claim 56
Dependent Claim
50 words
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.
Claim 57
Dependent Claim
29 words
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.
Claim 58
Dependent Claim
30 words
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 .
References Cited (Backward Citations)
US4131767A
Cited
US4161719A
Cited
US4445213A
Cited
USRE33900E
Cited
US4316284A
Cited
US4397020A
Cited
US4438511A
Cited
US4446555A
Cited
US4424565A
Cited
US4419728A
Cited
US4439763A
Cited
US4456957A
Cited
US4437087A
Cited
US4464658A
Cited
US4506358A
Cited
US4532626A
Cited
US4507760A
Cited
US4499576A
Cited
US4903261A
Cited
US4819228A
Cited
US4771425A
Cited
US4646287A
Cited
US4879551A
Cited
US5054034A
Cited
US4679227A
Cited
US4731816A
Cited
US4833706A
Cited
US4644532A
Cited
US4723267A
Cited
US4970678A
Cited
US4679189A
Cited
US4677423A
Cited
US4750136A
Cited
US4757495A
Cited
US4763191A
Cited
US4835737A
Cited
US4933937A
Cited
US4769810A
Cited
US4769811A
Cited
US5491804A
Cited
US4965772A
Cited
US4827411A
Cited
US4893306A
Cited
US5088032A
Cited
US4922486A
Cited
US4991169A
Cited
US4980897A
Cited
US4864559A
Cited
US5212686A
Cited
US5255291A
Cited
US4962532A
Cited
US5020058A
Cited
EP0384758A2
Cited
US4979118A
Cited
US5095480A
Cited
US4960310A
Cited
US5003595A
Cited
US4962497A
Cited
US5477541A
Cited
US5208811A
Cited
US5307343A
Cited
US5014265A
Cited
EP0431751B1
Cited
US5128945A
Cited
US5072449A
Cited
US5033076A
Cited
US5237564A
Cited
US5206886A
Cited
US5228062A
Cited
US5199049A
Cited
US5136580A
Cited
US5226120A
Cited
US5604868A
Cited
US5309437A
Cited
US5249178A
Cited
US5271004A
Cited
US5287453A
Cited
US5229994A
Cited
US5243342A
Cited
US5059925A
Cited
US5115431A
Cited
US5280470A
Cited
US5166930A
Cited
US5253251A
Cited
US5280480A
Cited
US5268592A
Cited
US5317562A
Cited
US5274631A
Cited
US5247516A
Cited
US5241682A
Cited
US5313582A
Cited
US5224099A
Cited
US5442630A
Cited
US5268900A
Cited
US5490258A
Cited
US5311509A
Cited
US5280500A
Cited
US5287103A
Cited
US5519858A
Cited
US5386567A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2006-08-25 | 2007-02-24 | 2007-08-26 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2010-08-25 | 2011-02-24 | 2011-08-26 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2014-08-25 | 2015-02-24 | 2015-08-26 | $7700.00 | Window Closed / Lapsed |