Patent US6895441B1 successfully refreshed from Google Patents.
US6895441B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Path rerouting mechanism utilizing multiple link bandwidth allocations
Assignee: Nokia Siemens Networks Ethernet Solutions Ltd
•
Filing: 2001-07-30
•
Granted: 2005-05-17
•
Expires: 2021-07-30
Abstract
Abstract A path reroute mechanism for use in communication networks comprising multiple searches for a routing path to restore traffic following a failure that could not be protected by a previously established protection route (i.e. protection tunnel, bypass, etc.) or for routing or rerouting of traffic paths for optimization or any other purpose. Each node advertises TLVs that include bandwidth allocation information used to derive the actual amount of bandwidth available for protection purposes, protected paths and unprotected paths or a portion of this information such as in the case where unprotected paths are not supported. Searches are performed on larger and larger portions of the available bandwidth until a route for the path is found.
Inventors
- 👤 Lior Shabtay
- 👤 Yoram Shamir
- 👤 Leonid Shmulevich
- 👤 Ofir Friedman
- 👤 Yaron Raz
- 👤 Zacky Pickholz
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 11:07
CPC Classifications
H; H04; H04L; H04L45/00; H04L45/28; H04L45/22
Claims Analysis
Total Claims: 60
Claim 1
Independent Claim
161 words
A method of path routing in a network, said method comprising the steps of: receiving link state advertising information generated by nodes within said network, said link state advertising information utilized to derive available bandwidth on a particular link for protection paths, protected paths and unprotected paths; performing a first search for a path using only links having sufficient bandwidth available of a type the same as that of the path to be found to accommodate said path; if said first search is not successful then, performing a second search for a path using only links having sufficient combined bandwidth available reserved for protected paths and unprotected paths to accommodate said path; if said second search is not successful then, performing a third search for a path using only links having sufficient combined bandwidth available reserved for protection paths, protected paths and unprotected paths to accommodate said path; and configuring appropriate nodes within said network in accordance with the path found.
Claim 2
Independent Claim
161 words
A method of path routing in a network, said method comprising the steps of: receiving link state advertising information generated by nodes within said network, said link state advertising information utilized to derive available bandwidth on a particular link for protection paths, protected paths and unprotected paths; performing a first search for a path using only links having sufficient bandwidth available of a type the same as that of the path to be found to accommodate said path; if said first search is not successful then, performing a second search for a path using only links having sufficient combined bandwidth available reserved for protected paths and unprotected paths to accommodate said path; if said second search is not successful then, performing a third search for a path using only links having sufficient combined bandwidth available reserved for protection paths, protected paths and unprotected paths to accommodate said path; and configuring appropriate nodes within said network in accordance with the path found.
Claim 3
Dependent Claim
37 words
The method according to claim 1 , wherein the bandwidth available reserved for protection paths represents the bandwidth of a link that is saved for protection path uses and that is not currently allocated for non-protection paths.
Claim 4
Dependent Claim
30 words
The method according to claim 1 , wherein said type comprises bandwidth available for unprotected paths if the path to be found is to use bandwidth reserved for unprotected paths.
Claim 5
Dependent Claim
30 words
The method according to claim 1 , wherein said type comprises bandwidth available for protected paths if the path to be found is to use bandwidth reserved for protected paths.
Claim 6
Dependent Claim
42 words
The method according to claim 1 , wherein said link state advertising information comprises one or more type, length, value (TLV) objects flooded using a link state routing protocol, wherein said one or more TLVs optionally function as sub-TLVs of other TLVs.
Claim 7
Dependent Claim
30 words
The method according to claim 1 , wherein said routing protocol is chosen from the group comprising the Open Shortest Path First (OSPF) protocol, OSPF extensions, OSPF-TE or OSPF-TE extensions.
Claim 8
Dependent Claim
24 words
The method according to claim 1 , wherein said routing protocol comprises the Intermediate System to Intermediate System (ISIS) protocol or any extensions thereof.
Claim 9
Dependent Claim
24 words
The method according to claim 1 , wherein said routing protocol comprises the Private Network to Network Interface (PNNI) protocol or any extensions thereof.
Claim 10
Dependent Claim
63 words
The method according to claim 1 , wherein said link state information relating to the bandwidth available on a particular link is apportioned in accordance with a plurality of classes for the available bandwidth of said protection paths, a plurality of classes for the available bandwidth of said protected paths and a plurality of classes for the available bandwidth of said unprotected paths.
Claim 11
Dependent Claim
52 words
The method according to claim 1 , wherein said link state information relating to the bandwidth available on a particular link comprises a first TLV adapted to indicate bandwidth available for protected-LSPs, a second TLV adapted to indicate bandwidth available for unprotected-LSPs and a third TLV adapted to indicate total available bandwidth.
Claim 12
Dependent Claim
67 words
The method according to claim 1 , wherein said link state information relating to the bandwidth available on a particular link comprises a first TLV adapted to indicate bandwidth available for protected-LSPs for a plurality of classes, a second TLV adapted to indicate bandwidth available for unprotected-LSPs for a plurality of classes and a third TLV adapted to indicate total available bandwidth for a plurality of classes.
Claim 13
Dependent Claim
25 words
The method according to claim 1 , wherein said first search, said second search and said third searches are is performed utilizing the Dijkstra algorithm.
Claim 14
Dependent Claim
26 words
The method according to claim 1 , wherein said the configuration of nodes within said network utilizes Reservation Protocol (RSVP) signaling, RSVP-TE or any extensions thereof.
Claim 15
Dependent Claim
24 words
The method according to claim 1 , wherein said the configuration of nodes within said network utilizes LDP signaling, CR-LDP or any extensions thereof.
Claim 16
Dependent Claim
27 words
The method according to claim 1 , wherein said step of configuring nodes within said network comprises configuring the Multiprotocol Label Switching (MPLS) forwarding within the nodes.
Claim 17
Dependent Claim
33 words
The method according to claim 1 , further comprising the steps of re-calculating and re-advertising the available bandwidth for protection paths, protected paths and unprotected paths in response to changes in network topology.
Claim 18
Dependent Claim
37 words
The method according to claim 1 , further comprising the steps of recalculating and re-advertising the available bandwidth for protection paths, protected paths and unprotected paths in response to changes in the link state of said network.
Claim 19
Independent Claim
114 words
A method of path routing in a network, said method comprising the steps of: receiving link state advertising information generated by nodes within said network, said link state advertising information utilized to derive available bandwidth on a particular link for protection paths and non-protection paths; performing a first search for a path using only links having sufficient bandwidth available reserved for non-protection paths to accommodate said path; if said first search is not successful then, performing a second search for a path using only links having sufficient combined bandwidth available reserved for protection paths and non-protection paths to accommodate said path; and configuring appropriate nodes within said network in accordance with the path found.
Claim 20
Independent Claim
114 words
A method of path routing in a network, said method comprising the steps of: receiving link state advertising information generated by nodes within said network, said link state advertising information utilized to derive available bandwidth on a particular link for protection paths and non-protection paths; performing a first search for a path using only links having sufficient bandwidth available reserved for non-protection paths to accommodate said path; if said first search is not successful then, performing a second search for a path using only links having sufficient combined bandwidth available reserved for protection paths and non-protection paths to accommodate said path; and configuring appropriate nodes within said network in accordance with the path found.
Claim 21
Independent Claim
141 words
A method of routing unprotected Label Switched Paths (LSPs) in a network, said method comprising the steps of: receiving link state advertising information generated by nodes within said network, said link state advertising information utilized to derive available bandwidth on a particular link for protection paths, protected paths and unprotected paths; performing a first search for a path using only links having sufficient available bandwidth for unprotected paths to accommodate said path; if said first search is not successful then, performing a second search for a path using only links having sufficient combined available bandwidth for protected paths and unprotected paths to accommodate said path; and if said second search is not successful then, performing a third search for a path using only links having sufficient combined available bandwidth for protection paths, protected paths and unprotected paths to accommodate said path.
Claim 22
Independent Claim
141 words
A method of routing unprotected Label Switched Paths (LSPs) in a network, said method comprising the steps of: receiving link state advertising information generated by nodes within said network, said link state advertising information utilized to derive available bandwidth on a particular link for protection paths, protected paths and unprotected paths; performing a first search for a path using only links having sufficient available bandwidth for unprotected paths to accommodate said path; if said first search is not successful then, performing a second search for a path using only links having sufficient combined available bandwidth for protected paths and unprotected paths to accommodate said path; and if said second search is not successful then, performing a third search for a path using only links having sufficient combined available bandwidth for protection paths, protected paths and unprotected paths to accommodate said path.
Claim 23
Dependent Claim
24 words
The method according to claim 19 , further comprising the step of configuring appropriate nodes within said network in accordance with the path found.
Claim 24
Dependent Claim
37 words
The method according to claim 19 , wherein the bandwidth available reserved for protection paths represents the bandwidth of a link that is saved for protection path uses and that is not currently allocated for non-protection paths.
Claim 25
Dependent Claim
42 words
The method according to claim 19 , wherein said link state advertising information comprises one or more type, length, value (TLV) objects flooded using a link state routing protocol, wherein said one or more TLVs optionally function as sub-TLVs of other TLVs.
Claim 26
Dependent Claim
30 words
The method according to claim 19 , wherein said routing protocol is chosen from the group comprising the Open Shortest Path First (OSPF) protocol, OSPF extensions, OSPF-TE or OSPF-TE extensions.
Claim 27
Dependent Claim
24 words
The method according to claim 19 , wherein said routing protocol comprises the Intermediate System to Intermediate System (ISIS) protocol or any extensions thereof.
Claim 28
Dependent Claim
24 words
The method according to claim 19 , wherein said routing protocol comprises the Private Network to Network Interface (PNNI) protocol or any extensions thereof.
Claim 29
Dependent Claim
63 words
The method according to claim 19 , wherein said link state information relating to the bandwidth available on a particular link is apportioned in accordance with a plurality of classes for the available bandwidth of said protection paths, a plurality of classes for the available bandwidth of said protected paths and a plurality of classes for the available bandwidth of said unprotected paths.
Claim 30
Dependent Claim
52 words
The method according to claim 19 , wherein said link state information relating to the bandwidth available on a particular link comprises a first TLV adapted to indicate bandwidth available for protected-LSPs, a second TLV adapted to indicate bandwidth available for unprotected-LSPs and a third TLV adapted to indicate total available bandwidth.
Claim 31
Dependent Claim
67 words
The method according to claim 19 , wherein said link state information relating to the bandwidth available on a particular link comprises a first TLV adapted to indicate bandwidth available for protected-LSPs for a plurality of classes, a second TLV adapted to indicate bandwidth available for unprotected-LSPs for a plurality of classes and a third TLV adapted to indicate total available bandwidth for a plurality of classes.
Claim 32
Dependent Claim
25 words
The method according to claim 19 , wherein said first search, said second search and said third searches are is performed utilizing the Dijkstra algorithm.
Claim 33
Dependent Claim
26 words
The method according to claim 19 , wherein said the configuration of nodes within said network utilizes Reservation Protocol (RSVP) signaling, RSVP-TE or any extensions thereof.
Claim 34
Dependent Claim
24 words
The method according to claim 19 , wherein said the configuration of nodes within said network utilizes LDP signaling, CR-LDP or any extensions thereof.
Claim 35
Dependent Claim
27 words
The method according to claim 19 , wherein said step of configuring nodes within said network comprises configuring the Multiprotocol Label Switching (MPLS) forwarding within the nodes.
Claim 36
Dependent Claim
33 words
The method according to claim 19 , further comprising the steps of recalculating and re-advertising the available bandwidth for protection paths, protected paths and unprotected paths in response to changes in network topology.
Claim 37
Dependent Claim
37 words
The method according to claim 19 , further comprising the steps of recalculating and re-advertising the available bandwidth for protection paths, protected paths and unprotected paths in response to changes in the link state of said network.
Claim 38
Independent Claim
141 words
A method of routing protected Label Switched Paths (LSPs) in a network, said method comprising the steps of: receiving link state advertising information generated by nodes within said network, said link state advertising information utilized to derive available bandwidth on a particular link for protection paths, protected paths and unprotected paths; performing a first search for a path using only links having sufficient available bandwidth for protected paths to accommodate said path; if said first search is not successful then, performing a second search for a path using only links having sufficient combined available bandwidth for protected paths and unprotected paths to accommodate said path; and if said second search is not successful then, performing a third search for a path using only links having sufficient combined available bandwidth for protection paths, protected paths and unprotected paths to accommodate said path.
Claim 39
Independent Claim
141 words
A method of routing protected Label Switched Paths (LSPs) in a network, said method comprising the steps of: receiving link state advertising information generated by nodes within said network, said link state advertising information utilized to derive available bandwidth on a particular link for protection paths, protected paths and unprotected paths; performing a first search for a path using only links having sufficient available bandwidth for protected paths to accommodate said path; if said first search is not successful then, performing a second search for a path using only links having sufficient combined available bandwidth for protected paths and unprotected paths to accommodate said path; and if said second search is not successful then, performing a third search for a path using only links having sufficient combined available bandwidth for protection paths, protected paths and unprotected paths to accommodate said path.
Claim 40
Dependent Claim
24 words
The method according to claim 35 , further comprising the step of configuring appropriate nodes within said network in accordance with the path found.
Claim 41
Dependent Claim
37 words
The method according to claim 35 , wherein the bandwidth available reserved for protection paths represents the bandwidth of a link that is saved for protection path uses and that is not currently allocated for non-protection paths.
Claim 42
Dependent Claim
42 words
The method according to claim 35 , wherein said link state advertising information comprises one or more type, length, value (TLV) objects flooded using a link state routing protocol, wherein said one or more TLVs optionally function as sub-TLVs of other TLVs.
Claim 43
Dependent Claim
25 words
The method according to claim 35 , wherein said routing protocol comprises the Open Shortest Path First (OSPF) protocol, OSPF extensions, OSPF-TE or OSPF-TE extensions.
Claim 44
Dependent Claim
24 words
The method according to claim 35 , wherein said routing protocol comprises the Intermediate System to Intermediate System (ISIS) protocol or any extensions thereof.
Claim 45
Dependent Claim
24 words
The method according to claim 35 , wherein said routing protocol comprises the Private Network to Network Interface (PNNI) protocol or any extensions thereof.
Claim 46
Dependent Claim
63 words
The method according to claim 35 , wherein said link state information relating to the bandwidth available on a particular link is apportioned in accordance with a plurality of classes for the available bandwidth of said protection paths, a plurality of classes for the available bandwidth of said protected paths and a plurality of classes for the available bandwidth of said unprotected paths.
Claim 47
Dependent Claim
52 words
The method according to claim 35 , wherein said link state information relating to the bandwidth available on a particular link comprises a first TLV adapted to indicate bandwidth available for protected-LSPs, a second TLV adapted to indicate bandwidth available for unprotected-LSPs and a third TLV adapted to indicate total available bandwidth.
Claim 48
Dependent Claim
67 words
The method according to claim 35 , wherein said link state information relating to the bandwidth available on a particular link comprises a first TLV adapted to indicate bandwidth available for protected-LSPs for a plurality of classes, a second TLV adapted to indicate bandwidth available for unprotected-LSPs for a plurality of classes and a third TLV adapted to indicate total available bandwidth for a plurality of classes.
Claim 49
Dependent Claim
25 words
The method according to claim 35 , wherein said first search, said second search and said third searches are is performed utilizing the Dijkstra algorithm.
Claim 50
Dependent Claim
26 words
The method according to claim 35 , wherein said the configuration of nodes within said network utilizes Reservation Protocol (RSVP) signaling, RSVP-TE or any extensions thereof.
Claim 51
Dependent Claim
24 words
The method according to claim 35 , wherein said the configuration of nodes within said network utilizes LDP signaling, CR-LDP or any extensions thereof.
Claim 52
Dependent Claim
27 words
The method according to claim 35 , wherein said step of configuring nodes within said network comprises configuring the Multiprotocol Label Switching (MPLS) forwarding within the nodes.
Claim 53
Dependent Claim
33 words
The method according to claim 35 , further comprising the steps of re-calculating and re-advertising the available bandwidth for protection paths, protected paths and unprotected paths in response to changes in network topology.
Claim 54
Dependent Claim
37 words
The method according to claim 35 , further comprising the steps of recalculating and re-advertising the available bandwidth for protection paths, protected paths and unprotected paths in response to changes in the link state of said network.
Claim 55
Dependent Claim
189 words
A network device, comprising: one or more line PHY line interfaces for interfacing said network device to one or more communication links; a switch adapted to switch data between a plurality of ingress inputs and a plurality of egress outputs; a processor; memory means coupled to said processor; software means operative on said processor for: receiving link state advertising information generated by nodes within said network, said link state advertising information utilized to derive available bandwidth on a particular link for protection paths, protected paths and unprotected paths; performing a first search for a path using only links having sufficient bandwidth available of a first type the same as that of the path to be found to accommodate said path; if said first search is not successful then, performing a second search for a path using only links having sufficient combined available bandwidth of a second type opposite of that of the path to be found to accommodate said path; and if said second search is not successful then, performing a third search for a path using only links having sufficient protection path bandwidth available to accommodate said path.
Claim 56
Dependent Claim
189 words
A network device, comprising: one or more line PHY line interfaces for interfacing said network device to one or more communication links; a switch adapted to switch data between a plurality of ingress inputs and a plurality of egress outputs; a processor; memory means coupled to said processor; software means operative on said processor for: receiving link state advertising information generated by nodes within said network, said link state advertising information utilized to derive available bandwidth on a particular link for protection paths, protected paths and unprotected paths; performing a first search for a path using only links having sufficient bandwidth available of a first type the same as that of the path to be found to accommodate said path; if said first search is not successful then, performing a second search for a path using only links having sufficient combined available bandwidth of a second type opposite of that of the path to be found to accommodate said path; and if said second search is not successful then, performing a third search for a path using only links having sufficient protection path bandwidth available to accommodate said path.
Claim 57
Dependent Claim
188 words
A computer program product for use in a network device, said computer program product comprising: a computer useable medium having computer readable program code means embodied in said medium for performing a path reroute in a network, said computer program product comprising: computer readable program code means for advertising link state information utilized to derive the available bandwidth on a particular link for protection paths, protected paths and unprotected paths; computer readable program code means for performing a first search for a path using only links having sufficient bandwidth available of a type the same as that of the path to be found to accommodate said path; computer readable program code means for performing a second search, if said first search is not successful, for a path using only links having sufficient combined bandwidth available reserved for protected paths and unprotected paths to accommodate said path; and computer readable program code means for performing a third search, if said second search is not successful, for a path using only links having sufficient combined bandwidth available reserved for protection paths, protected paths and unprotected paths to accommodate said path.
Claim 58
Dependent Claim
188 words
A computer program product for use in a network device, said computer program product comprising: a computer useable medium having computer readable program code means embodied in said medium for performing a path reroute in a network, said computer program product comprising: computer readable program code means for advertising link state information utilized to derive the available bandwidth on a particular link for protection paths, protected paths and unprotected paths; computer readable program code means for performing a first search for a path using only links having sufficient bandwidth available of a type the same as that of the path to be found to accommodate said path; computer readable program code means for performing a second search, if said first search is not successful, for a path using only links having sufficient combined bandwidth available reserved for protected paths and unprotected paths to accommodate said path; and computer readable program code means for performing a third search, if said second search is not successful, for a path using only links having sufficient combined bandwidth available reserved for protection paths, protected paths and unprotected paths to accommodate said path.
Claim 59
Dependent Claim
27 words
The method according to claim 52 , further comprising computer readable program code means for configuring appropriate nodes within said network in accordance with the path found.
Claim 60
Dependent Claim
22 words
The method according to claim 52 , wherein said first search, said second search and said third search employ the Dijkstra algorithm.
References Cited (Backward Citations)
US5590118A
Cited
US6496476B1
Cited
US6507561B1
Cited
US6512740B1
Cited
US5856981A
Cited
US20020141334A1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2008-05-16 | 2008-11-15 | 2009-05-17 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2012-05-16 | 2012-11-15 | 2013-05-17 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2016-05-16 | 2016-11-15 | 2017-05-17 | $7700.00 | Window Closed / Lapsed |