Patent US5230071A successfully refreshed from Google Patents.
Patent US6728779B1 successfully refreshed from Google Patents.
US6728779B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for exchanging routing information in a packet-based data network
Assignee: Nokia of America Corp
•
Filing: 2000-05-31
•
Granted: 2004-04-27
•
Expires: 2020-05-31
Abstract
Abstract Routing information is exchanged between edge routers in different autonomous systems that independently define their routing policies. A Simple Path Vector Protocol extends the prior art Border Gateway Protocol in a manner that is guaranteed to converge by adding a new attribute to the routing messages sent by an edge router to its peers in the different systems. This attribute is a path history, which is dynamically computed at each router as the routing path to a particular destination is changed. The path history attribute is sent in a routing message by a router to its peers together with the sending router's path to that destination. By observing the dynamic path history that is computed at a router as a received routing message from a peer router that contains a history attribute is processed, a cycle can be identified in the newly computed history and associated with a policy conflict at that receiving router's associated autonomous system. A path whose history contains a cycle is automatically suppressed as a permitted path to that destination.
Inventors
- 👤 Timothy G. Griffin
- 👤 Gordon Thomas Wilfong
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 20:45
CPC Classifications
H; H04; H04L; H04L12/00; H04L12/28; H04L45/00; H04L45/02; H04L45/033
Claims Analysis
Total Claims: 29
Claim 1
Independent Claim
148 words
A method at a first router comprising: a) selecting for processing a routing message received from one peer router from among a group of a plurality of peer routers of the first router, the routing message comprising a path from the peer router to a destination end router and an associated path history associated with that path, the path history indicating a sequence of any number of path change events that allowed the one peer router to adopt that path; b) determining a new path from the first router to the destination end router from a set of stored paths to the destination end router and the path in the routing message; c) dynamically computing a new path history associated with the determined new path; and d) sending the determined new path and its associated new path history to one or more of the plurality of peer routers.
Claim 2
Independent Claim
148 words
A method at a first router comprising: a) selecting for processing a routing message received from one peer router from among a group of a plurality of peer routers of the first router, the routing message comprising a path from the peer router to a destination end router and an associated path history associated with that path, the path history indicating a sequence of any number of path change events that allowed the one peer router to adopt that path; b) determining a new path from the first router to the destination end router from a set of stored paths to the destination end router and the path in the routing message; c) dynamically computing a new path history associated with the determined new path; and d) sending the determined new path and its associated new path history to one or more of the plurality of peer routers.
Claim 3
Dependent Claim
58 words
The method of claim 1 wherein determining the new path comprises choosing as the new path the highest ranked permitted path from the first router to the destination end router from a rank-ordered set of permitted paths, and determining whether that new path is different than the old path from the first router to the destination end router.
Claim 4
Dependent Claim
52 words
The method of claim 2 wherein when the new path is determined to be different than the old path, dynamically computing the history of the new path as a function of whether the rank order of the new path is lower, higher, or equal to the rank order of the old path.
Claim 5
Dependent Claim
82 words
The method of claim 3 wherein when the rank order of the old path is lower than the rank order of the new path, then the history of the new path is a combination of a signed new path with a path history, the sign indicating that the new path is ranked higher than the old path and the path history indicating a sequence of events that led to the one peer router to adopt a specific sub-path of the new path.
Claim 6
Dependent Claim
82 words
The method of claim 3 wherein when the rank order of the old path is higher than the rank order of the new path, then the history of the new path is a combination of a signed old path with a path history, the sign indicating that the new path is ranked lower than the old path and the path history indicating a sequence of events that led to the one peer router to abandon a specific sub-path of the old path.
Claim 7
Dependent Claim
31 words
The method of claim 1 further comprising, e) after dynamically computing the new path history, determining whether there is a cycle present in the new path history determined in step b).
Claim 8
Dependent Claim
84 words
The method of claim 6 further comprising, when in step e) a cycle is determined to be present in the new path history determined in step b): f) determining a newer path from the first router to the destination end router from the set of stored paths to the destination and the path in the routing message, which excludes as being the newer path the new path determined in step b) which associated path history was determined in step e) to contain the cycle.
Claim 9
Dependent Claim
50 words
The method of claim 7 further comprising determining whether the newer path determined in step f) is different than the original old path, and when it is different, setting the history of the newer path determined in step f) to a function of the history of the original old path.
Claim 10
Dependent Claim
29 words
The method of claim 1 wherein the routing message selected for processing from the one peer router is the oldest unprocessed received routing message from the one peer router.
Claim 11
Dependent Claim
125 words
A router comprising: means for selecting for processing a routing message received from one peer router from among a group of a plurality of peer routers of the first router, the routing message comprising a path from the peer router to a destination end router and an associated path history associated with that path, the path history indicating a sequence of any number of path change events that allowed the one peer router to adopt that path; means for determining a new path from the first router to the destination end router from a set of stored paths to the destination end router and the path in the routing message; and means for dynamically computing a new path history associated with the determined new path.
Claim 12
Dependent Claim
125 words
A router comprising: means for selecting for processing a routing message received from one peer router from among a group of a plurality of peer routers of the first router, the routing message comprising a path from the peer router to a destination end router and an associated path history associated with that path, the path history indicating a sequence of any number of path change events that allowed the one peer router to adopt that path; means for determining a new path from the first router to the destination end router from a set of stored paths to the destination end router and the path in the routing message; and means for dynamically computing a new path history associated with the determined new path.
Claim 13
Dependent Claim
65 words
The router of claim 10 wherein the means for determining the new path comprises means for choosing as the new path the highest ranked permitted path from the first router to the destination end router from a rank-ordered set of permitted paths, and means for determining whether the new path is different than the old path from the first router to the destination end router.
Claim 14
Dependent Claim
57 words
The router of claim 11 wherein when the new path is determined to be different than the old path, then the means for dynamically computing the new path history computes the history as a function of whether the rank order of the new path is lower, higher, or equal to the rank order of the old path.
Claim 15
Dependent Claim
82 words
The router of claim 12 wherein when the rank order of the old path is lower than the rank order of the new path, then the history of the new path is a combination of a signed new path with a path history, the sign indicating that the new path is ranked higher than the old path and the path history indicating a sequence of events that led to the one peer router to adopt a specific sub-path of the new path.
Claim 16
Dependent Claim
82 words
The router of claim 12 wherein when the rank order of the old path is higher than the rank order of the new path, then the history of the new path is a combination of a signed old path with a path history, the sign indicating that the new path is ranked lower than the old path and the path history indicating a sequence of events that led to the one peer router to abandon a specific sub-path of the old path.
Claim 17
Dependent Claim
20 words
The router of claim 10 further comprising means for determining whether there is a cycle in the new path history.
Claim 18
Dependent Claim
82 words
The router of claim 15 wherein when a cycle is determined to be present in the new path history, then the means for determining a new path determines a newer path from the router to the destination end router from the set of stored paths to the destination and the path in the selected received routing message from the one peer router, which excludes as being the newer path the new path which associated path history was determined to contain the cycle.
Claim 19
Dependent Claim
29 words
The router of claim 10 wherein the routing message selected for processing from the one peer router is the oldest unprocessed received routing message from the one peer router.
Claim 20
Dependent Claim
167 words
A computer readable media tangibly embodying a program of instructions executable by a computer to perform at a first router a method for exchanging routing information with a group of a plurality of peer routers, the method comprising: a) selecting for processing a routing message received from one of the peer routers, the routing message comprising a path from the peer router to a destination end router and an associated path history associated with that path, the path history indicating a sequence of any number of path change events that allowed the one peer router to adopt that path; b) determining a new path from the first router to the destination end router from a set of stored paths to the destination end router and the path in the routing message; c) dynamically computing a new path history associated with the determined new path; and d) sending the determined new path and its associated new path history to one or more of the plurality of peer routers.
Claim 21
Dependent Claim
167 words
A computer readable media tangibly embodying a program of instructions executable by a computer to perform at a first router a method for exchanging routing information with a group of a plurality of peer routers, the method comprising: a) selecting for processing a routing message received from one of the peer routers, the routing message comprising a path from the peer router to a destination end router and an associated path history associated with that path, the path history indicating a sequence of any number of path change events that allowed the one peer router to adopt that path; b) determining a new path from the first router to the destination end router from a set of stored paths to the destination end router and the path in the routing message; c) dynamically computing a new path history associated with the determined new path; and d) sending the determined new path and its associated new path history to one or more of the plurality of peer routers.
Claim 22
Dependent Claim
61 words
The media of claim 18 wherein in the method determining the new path comprises choosing as the new path the highest ranked permitted path from the first router to the destination end router from a rank-ordered set of permitted paths, and determining whether that new path is different than the old path from the first router to the destination end router.
Claim 23
Dependent Claim
55 words
The media of claim 19 wherein in the method when the new path is determined to be different than the old path, dynamically computing the history of the new path as a function of whether the rank order of the new path is lower, higher, or equal to the rank order of the old path.
Claim 24
Dependent Claim
85 words
The media of claim 20 wherein in the method when the rank order of the old path is lower than the rank order of the new path, then the history of the new path is a combination of a signed new path with a path history, the sign indicating that the new path is ranked higher than the old path and the path history indicating a sequence of events that led to the one peer router to adopt a specific sub-path of the new path.
Claim 25
Dependent Claim
85 words
The media of claim 20 wherein in the method when the rank order of the old path is higher than the rank order of the new path, then the history of the new path is a combination of a signed old path with a path history, the sign indicating that the new path is ranked lower than the old path and the path history indicating a sequence of events that led to the one peer router to abandon a specific sub-path of the old path.
Claim 26
Dependent Claim
30 words
The media of claim 18 wherein the method further comprises, e) after dynamically computing the new path history, determining whether there is a cycle present in the new path history.
Claim 27
Dependent Claim
82 words
The media of claim 23 wherein the method further comprises, f) when a cycle is determined to be present in the new path history, determining a newer path from the first router to the destination end router from the set of stored paths to the destination end router and the path in the routing message, which excludes as being the newer path the new path determined in step b) which associated path history was determined in step c) to contain the cycle.
Claim 28
Dependent Claim
45 words
The media of claim 24 wherein the method further comprises determining whether the newer path is different than the original old path, and when it is different, setting the history of the newer path to a function of the history of the original old path.
Claim 29
Dependent Claim
32 words
The media of claim 18 wherein in the method the routing message selected for processing from the one peer router is the oldest unprocessed received routing message from the one peer router.
References Cited (Backward Citations)
US3988587A
Cited
US4656658A
Cited
US4825206A
Cited
US4972457A
Cited
EP0817424A2
Cited
US6115393A
Cited
US5398277A
Cited
US6453064B1
Cited
US5898826A
Cited
US5864605A
Cited
US6055492A
Cited
US6535518B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2007-04-27 | 2007-10-27 | 2008-04-27 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2011-04-27 | 2011-10-27 | 2012-04-27 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2015-04-27 | 2015-10-27 | 2016-04-27 | $7700.00 | Window Closed / Lapsed |