Patent US6621798B1 successfully refreshed from Google Patents.
US6621798B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method to sequence changes for IP network configuration
Assignee: Nokia of America Corp
•
Filing: 1999-10-14
•
Granted: 2003-09-16
•
Expires: 2019-10-14
Abstract
Abstract Updating of routers is achieved by insuring that the scheduling of router updates is such that a zone of turbulence that occurs where the updating takes place does not prevent reaching any router that may be in need of updating. For IP routers that have a task scheduling capability, this is achieved by estimating the time for communicating update information to all routers that need to be updated, adding that estimate to time of day, and transmitting the update specifications. In arrangements where routers do not have a task scheduling capability, updating is sequenced. One embodiment creates a set of traceroute trees that cover the nodes to be updated, and leaf nodes of the trees are taken up at random, placed in an ordered list and deleted from the trees. Another embodiment is more tree centric, in that once a starting node is identified (and its associated tree), all of its nodes are considered before progressing to another tree. A third embodiment takes advantage of the fact that is a node to be updated in not reachable when its updating is to be done, a second try that follows a delay is likely to succeed.
Inventors
- 👤 P. Krishnan
- 👤 Subrata Mazumdar
- 👤 Tejas Naik
- 👤 Ganesan Ramu
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-05 17:16
CPC Classifications
H; H04; H04L; H04L45/00; H04L45/02; H04L45/48; H04L45/484
Claims Analysis
Total Claims: 25
Claim 1
Independent Claim
109 words
A method for updating routers in a network, comprising the steps of: employing one or more traceroute trees, where each tree has a root node, leaf nodes, and edges that connect each leaf node to the root node, through n intermediate nodes, where n is an integer ≧0, where the trees, collectively, cover the routers to be updated, where nodes and edges of each tree are labeled with a tree identifier, and where nodes that belong to more than one tree, when such nodes exist, are labeled with one tree identifier; updating said routers, starting with leaves of said trees, and proceeding towards the respective roots of the trees.
Claim 2
Independent Claim
109 words
A method for updating routers in a network, comprising the steps of: employing one or more traceroute trees, where each tree has a root node, leaf nodes, and edges that connect each leaf node to the root node, through n intermediate nodes, where n is an integer ≧0, where the trees, collectively, cover the routers to be updated, where nodes and edges of each tree are labeled with a tree identifier, and where nodes that belong to more than one tree, when such nodes exist, are labeled with one tree identifier; updating said routers, starting with leaves of said trees, and proceeding towards the respective roots of the trees.
Claim 3
Dependent Claim
23 words
The method of claim 1 , carried out with a tool that is resident on a computer that is coupled to said network.
Claim 4
Dependent Claim
20 words
The method of claim 2 where said one or more trees have root nodes that are accessible by said computer.
Claim 5
Dependent Claim
39 words
The method of claim 2 where said one or more trees have root nodes that are selected from a set comprising said computer, routers which said computer can reach via an out-of-band connection, area border routes, and gateway routers.
Claim 6
Dependent Claim
16 words
The method of claim 1 further comprising a step of constructing said one or more trees.
Claim 7
Dependent Claim
30 words
The method of claim 5 where said step of constructing said one or more trees selects nodes that are reachable from a computer that carries out said method, at random.
Claim 8
Dependent Claim
39 words
The method of claim 5 where said step of constructing said one or more trees selects nodes as root nodes from a preferable subset of nodes that are reachable from a computer that carries out said method, at random.
Claim 9
Dependent Claim
17 words
The method of claim 7 where said computer reaches said root nodes by executing a telnet process.
Claim 10
Dependent Claim
33 words
The method of claim 1 where said step of employing develops a sequence for updating said nodes to be updates, and said step of updating said routers updates in accordance with said sequence.
Claim 11
Dependent Claim
14 words
The method of claim 9 where said sequence is developed in a node-centric manner.
Claim 12
Dependent Claim
14 words
The method of claim 9 where said sequence is developed in a tree-centric manner.
Claim 13
Dependent Claim
142 words
The method of claim 9 where said sequence is developed by a process that creates an ordered update sequencing list, by executing steps that comport with the logic: While (there are nodes left in any of the set of trees) do { Choose a leaf s i from the set of trees at random such that node s l is not an internal node for any tree (OR fail). Output leaf s i , and its label sn j to the ordered update sequencing list Remove node s i from tree sn j repeat the following { if there is no edge with label x out of a non-leaf node, remove label x from all edges into that node (or edges with label x into that node) unless the node is labeled x; } until (no edge or label is removable); }.
Claim 14
Dependent Claim
25 words
The method of claim 12 where said process further comprises a step of pruning from said list nodes that do not need to be updated.
Claim 15
Dependent Claim
92 words
The method of claim 9 where said sequence is developed by a process that creates an ordered update sequencing list, by executing steps that comport with following the logic: While (node exists in any tree) do { Pick start node sn j randomly While (leaf node s i exists in tree sn j and node s i is not an intermediate node of a tree other than sn j ) { Put (s i , sn j ) in update sequencing list Remove node s i from tree sn j } }.
Claim 16
Dependent Claim
25 words
The method of claim 14 where said process further comprises a step of pruning from said list nodes that do not need to be updated.
Claim 17
Independent Claim
108 words
A method for updating routers in a network, comprising the steps of: maintaining a set of routers to be updated, selecting a router from said set of routers to be updated, determining whether said router can be reached from a computer that carries out said method, when said step of determining concludes that said router can be reached, reaching said router, updating said router, removing said router from said list of routers to be updated, returning to said step of selecting, and when said step of determining concludes that said router cannot be reached, taking a preselected action that occupies time, and returning to said step of determining.
Claim 18
Independent Claim
108 words
A method for updating routers in a network, comprising the steps of: maintaining a set of routers to be updated, selecting a router from said set of routers to be updated, determining whether said router can be reached from a computer that carries out said method, when said step of determining concludes that said router can be reached, reaching said router, updating said router, removing said router from said list of routers to be updated, returning to said step of selecting, and when said step of determining concludes that said router cannot be reached, taking a preselected action that occupies time, and returning to said step of determining.
Claim 19
Dependent Claim
13 words
The method of claim 16 where said preselected action is a wait period.
Claim 20
Dependent Claim
17 words
The method of claim 16 where said preselected action is a wait period of a preselected duration.
Claim 21
Dependent Claim
25 words
The method of claim 16 where said preselected action is a direction to select a different router from said set of routers to be updated.
Claim 22
Independent Claim
82 words
A method for updating routers in a network, comprising the steps of: selecting a time for communicating update information to each of said routers to be updated, based on said step of selecting a time, formulating a time-of-day for updating of said routers to be updated, including said time-of-day with updating information that is destined to each of said routers to be updated as an update task scheduling time-of execution specification, and transmitting said updating information to said routers to be updated.
Claim 23
Independent Claim
82 words
A method for updating routers in a network, comprising the steps of: selecting a time for communicating update information to each of said routers to be updated, based on said step of selecting a time, formulating a time-of-day for updating of said routers to be updated, including said time-of-day with updating information that is destined to each of said routers to be updated as an update task scheduling time-of execution specification, and transmitting said updating information to said routers to be updated.
Claim 24
Dependent Claim
13 words
The method of claim 20 where said selecting a time, selects a duration.
Claim 25
Dependent Claim
29 words
The method of claim 20 where said duration is selected by performing ping operations, to determine time that is required to reach each of the routers to be updated.
References Cited (Backward Citations)
US5917820A
Cited
US6055561A
Cited
US6069889A
Cited
US6130889A
Cited
US5926463A
Cited
US6415312B1
Cited
US6363319B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2006-09-15 | 2007-03-17 | 2007-09-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2010-09-15 | 2011-03-17 | 2011-09-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2014-09-15 | 2015-03-17 | 2015-09-16 | $7700.00 | Window Closed / Lapsed |