Patent JPS6472060A successfully refreshed from Google Patents.
Patent US6836463B2 successfully refreshed from Google Patents.
US6836463B2
Expired / Lapsed
US
⏱️ 0.0 years remaining
System for communicating labeled routing trees to establish preferred paths and source routes with local identifiers in wireless computer networks
Assignee: Nokia Solutions and Networks Oy
•
Filing: 1999-10-15
•
Granted: 2004-12-28
•
Expires: 2019-10-15
Abstract
Abstract One or more labeled routing trees (LRTS) are produced at a router of a computer network according to a shortest path determination made over a partial topology graph of the network, which graph is produced according to knowledge of adjacent links of the router and one or more LRTs of neighboring routers. The LRTs of the router may be updated in response to receipt of routing state update messages, and such messages may include local link identifiers assigned by a head of a link to which the identifiers pertain, and node parameters of a tail of the link to which the local link identifiers pertain. The routing state update messages may be transmitted within the network: (i) in response to a new destination node being detected by an existing node within the network, (ii) in response to a destination becoming unreachable by a collection of the existing nodes, (iii) in response to the change in the cost of a path to at least one destination exceeding a threshold and/or (iv) in situations where a routing loop may be encountered among two or more of the nodes of the network (e.g., at times when a path implied in the LRT of the router leads to a loop).
Inventors
- 👤 J. Joaquin Garcia-Luna-Aceves
- 👤 Marcelo Spohn
- 👤 David A. Beyer
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 20:15
CPC Classifications
H; H04; H04L; H04L45/00; H04L45/48; H04L45/484; H04L45/02; H04W; H04W28/00; H04W28/16; H04W28/18; H04W76/00; H04W76/10; H04W8/00; H04W8/22; H04W8/24; H04W8/26
Claims Analysis
Total Claims: 13
Claim 1
Independent Claim
240 words
A method for routing information along preferred paths in a computer network in which a plurality of routers are interconnected by communication links, comprising: forming a partial topology graph for a router by combining link-state information of each adjacent link, router-state information of each adjacent router, and link-state information and node-state information of each link adjacent to each adjacent router; and computing a plurality of labeled routing trees (LRT) for the router using only the partial topology graph, each LRT corresponding to a type of service of the computer network, each LRT specifying a preferred path from the router to each of a plurality of destination routers in the network, wherein the LRTs of the router are updated in response to receipt of routing state update messages, the routing state update messages including one or more local link identifiers, each local link identifier assigned by a head-of-link router to which the identifier pertains, and wherein the routing state update messages are transmitted within the computer network in response to at least one of: (i) a new destination router being detected by an existing router within the network, (ii) a destination router becoming unreachable by a collection of the existing routers, (iii) a change in the cost of a path to at least one destination router exceeding a threshold delta, and (iv) in situations where a routing loop may be encountered among two or more of the routers of the network.
Claim 2
Independent Claim
240 words
A method for routing information along preferred paths in a computer network in which a plurality of routers are interconnected by communication links, comprising: forming a partial topology graph for a router by combining link-state information of each adjacent link, router-state information of each adjacent router, and link-state information and node-state information of each link adjacent to each adjacent router; and computing a plurality of labeled routing trees (LRT) for the router using only the partial topology graph, each LRT corresponding to a type of service of the computer network, each LRT specifying a preferred path from the router to each of a plurality of destination routers in the network, wherein the LRTs of the router are updated in response to receipt of routing state update messages, the routing state update messages including one or more local link identifiers, each local link identifier assigned by a head-of-link router to which the identifier pertains, and wherein the routing state update messages are transmitted within the computer network in response to at least one of: (i) a new destination router being detected by an existing router within the network, (ii) a destination router becoming unreachable by a collection of the existing routers, (iii) a change in the cost of a path to at least one destination router exceeding a threshold delta, and (iv) in situations where a routing loop may be encountered among two or more of the routers of the network.
Claim 3
Dependent Claim
31 words
The method of claim 1 , wherein situations where a routing loop may be encountered include times when a path implied in the LRT of the router leads to a loop.
Claim 4
Dependent Claim
193 words
A source routing protocol, for a computer network in which a plurality of routers are interconnected by communication links, comprising distributing, among the plurality of routers of the computer network, a local link identifier corresponding to each router within routing state update messages, the routing state update messages including a link-state information and a node-state information, wherein each router maintains a plurality of labeled routing tree (LRT), each LRT corresponding to a type of service of the computer network, wherein the LRTs of routers in the computer network are updated in response to receipt of one or more routing state update messages and wherein LRTs are updated according to whether an optimum routine approach or a least overhead routing approach is used within the computer network, the optimum routing approach routing state update messages are transmitted when at least one of: (i) a routing state update message which causes a link to be added to a subject router's labeled routing trees is received, (ii) a recent routing state update message regarding an existing link in the subject router's labeled routing trees is received, and (iii) a destination becomes unreachable by the subject router.
Claim 5
Dependent Claim
193 words
A source routing protocol, for a computer network in which a plurality of routers are interconnected by communication links, comprising distributing, among the plurality of routers of the computer network, a local link identifier corresponding to each router within routing state update messages, the routing state update messages including a link-state information and a node-state information, wherein each router maintains a plurality of labeled routing tree (LRT), each LRT corresponding to a type of service of the computer network, wherein the LRTs of routers in the computer network are updated in response to receipt of one or more routing state update messages and wherein LRTs are updated according to whether an optimum routine approach or a least overhead routing approach is used within the computer network, the optimum routing approach routing state update messages are transmitted when at least one of: (i) a routing state update message which causes a link to be added to a subject router's labeled routing trees is received, (ii) a recent routing state update message regarding an existing link in the subject router's labeled routing trees is received, and (iii) a destination becomes unreachable by the subject router.
Claim 6
Dependent Claim
259 words
A source routing protocol, for a computer network in which a plurality of routers are interconnected by communication links, comprising distributing, among the plurality of routers of the computer network, a local link identifier corresponding to each router within routing state update messages, the routing state update messages including a link-state information and a node-state information, wherein each router maintains a plurality of labeled routing tree (LRT), each LRT corresponding to a type of service of the computer network, wherein the LRTs of routers in the computer network are updated in response to receipt of one or more routing state update messages and wherein LRTs are updated according to whether an optimum routing approach or a least overhead routing approach is used within the computer network, wherein in the last overhead routing approach state update messages are transmitted: (i) when a subject router finds a new destination or any neighbors of the subject router report same, (ii) when a destination becomes unreachable by the subject router or any of its neighbors, (iii) when the subject router finds that the change in the cost of path to at least one destination exceeds a threshold delta, (iv) when a path implied in any of the labeled routing trees of the subject router leads to a loop, and/or a new successor chosen to given destination has an address larger than an address of the subject router and a reported distance from the new successor to a particular destination is larger than a reported distance from a previous successor to that particular destination.
Claim 7
Dependent Claim
259 words
A source routing protocol, for a computer network in which a plurality of routers are interconnected by communication links, comprising distributing, among the plurality of routers of the computer network, a local link identifier corresponding to each router within routing state update messages, the routing state update messages including a link-state information and a node-state information, wherein each router maintains a plurality of labeled routing tree (LRT), each LRT corresponding to a type of service of the computer network, wherein the LRTs of routers in the computer network are updated in response to receipt of one or more routing state update messages and wherein LRTs are updated according to whether an optimum routing approach or a least overhead routing approach is used within the computer network, wherein in the last overhead routing approach state update messages are transmitted: (i) when a subject router finds a new destination or any neighbors of the subject router report same, (ii) when a destination becomes unreachable by the subject router or any of its neighbors, (iii) when the subject router finds that the change in the cost of path to at least one destination exceeds a threshold delta, (iv) when a path implied in any of the labeled routing trees of the subject router leads to a loop, and/or a new successor chosen to given destination has an address larger than an address of the subject router and a reported distance from the new successor to a particular destination is larger than a reported distance from a previous successor to that particular destination.
Claim 8
Dependent Claim
135 words
A source routing protocol, for a computer network in which a plurality of routers are interconnected by communication links, comprising distributing, among the plurality of routers of the computer network, a local link identifier corresponding to each router within routing state update messages, the routing state update messages including a link-state information and a node-state information, wherein each router maintains a plurality of labeled routing tree (LRT), each LRT corresponding to a type of service of the computer network, and wherein the routing state update message includes performance characteristic information and addressing information for a link of the computer network and a tail-of-link router pertaining to the link, the routing state update message further includes a time stamp assigned by a head-of-link router, the time stamp indicating the validity of the routing state update message.
Claim 9
Dependent Claim
135 words
A source routing protocol, for a computer network in which a plurality of routers are interconnected by communication links, comprising distributing, among the plurality of routers of the computer network, a local link identifier corresponding to each router within routing state update messages, the routing state update messages including a link-state information and a node-state information, wherein each router maintains a plurality of labeled routing tree (LRT), each LRT corresponding to a type of service of the computer network, and wherein the routing state update message includes performance characteristic information and addressing information for a link of the computer network and a tail-of-link router pertaining to the link, the routing state update message further includes a time stamp assigned by a head-of-link router, the time stamp indicating the validity of the routing state update message.
Claim 10
Dependent Claim
17 words
The source routing protocol of claim 5 wherein the performance characteristics include link-state parameters of the link.
Claim 11
Dependent Claim
20 words
The source routing protocol claim 5 of wherein the routing state update message further includes a type of service vector.
Claim 12
Dependent Claim
36 words
The source routing protocol of claim 7 wherein the type of service vector specifies a type of service routing tree in which the link is being used by a router transmitting the routing state update message.
Claim 13
Dependent Claim
20 words
The source routing protocol of claim 5 wherein the routing state update message includes addressing information for the head-of-link router.
References Cited (Backward Citations)
US4466060A
Cited
US4987536A
Cited
US5115433A
Cited
EP0465201A2
Cited
EP0539737A1
Cited
US5231634B1
Cited
US5231634A
Cited
US5233604A
Cited
US5487064A
Cited
US5596719A
Cited
US5548578A
Cited
US5515508A
Cited
US5706291A
Cited
US5509123A
Cited
US5845086A
Cited
WO1996019887A1
Cited
US5557748A
Cited
US5600644A
Cited
US5572528A
Cited
US5608721A
Cited
US5721819A
Cited
US5638371A
Cited
US5682382A
Cited
US5805593A
Cited
US5721725A
Cited
US5633866A
Cited
US5933425A
Cited
US5737318A
Cited
US5652751A
Cited
US5854899A
Cited
GB2313254A
Cited
US5881246A
Cited
US5896379A
Cited
EP0841763A1
Cited
US6026303A
Cited
US5999536A
Cited
US5964841A
Cited
US5918016A
Cited
US5926463A
Cited
US6246669B1
Cited
US6006272A
Cited
WO1999046899A2
Cited
US6108314A
Cited
US6301244B1
Cited
WO2000039967A2
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2007-12-28 | 2008-06-28 | 2008-12-28 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2011-12-28 | 2012-06-28 | 2012-12-28 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2015-12-28 | 2016-06-28 | 2016-12-28 | $7700.00 | Window Closed / Lapsed |