Patent US4466060A successfully refreshed from Google Patents.
US4466060A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Message routing in a computer network
Assignee: Nokia Bell Labs
•
Filing: 1982-02-11
•
Granted: 1984-08-14
•
Expires: 2002-02-11
Abstract
Abstract An adaptive distributed message routing algorithm that may be implemented in a computer program to control the routing of data messages in a packet message switching digital computer network. Network topology information is exchanged only between neighbor nodes in the form of minimum spanning trees, referred to as exclusionary trees. An exclusionary tree is formed by excluding the neighbor node and its links from the tree. From the set of exclusionary trees received a route table and transmitted exclusionary trees are constructed.
Inventors
- 👤 Guy G. Riddle
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 16:21
CPC Classifications
G; G06; G06F; G06F15/00; G06F15/16; G06F15/163; G06F15/173; G06F15/17356; G06F15/17368; G06F15/17381; H; H04; H04L; H04L45/00; H04L45/02; H04L45/48; H04L45/484
Claims Analysis
Total Claims: 25
Claim 1
Independent Claim
68 words
In a computer network comprising a plurality of nodes, the method of routing messages among said nodes comprising the following steps for each node: receiving a first exclusionary tree from at least one neighbor node, constructing at least a second exclusionary tree from said first exclusionary tree, transmitting said second exclusionary tree to a neighbor node, and routing messages according to the information in said first exclusionary tree.
Claim 2
Dependent Claim
68 words
In a computer network comprising a plurality of nodes, the method of routing messages among said nodes comprising the following steps for each node: receiving a first exclusionary tree from at least one neighbor node, constructing at least a second exclusionary tree from said first exclusionary tree, transmitting said second exclusionary tree to a neighbor node, and routing messages according to the information in said first exclusionary tree.
Claim 3
Dependent Claim
75 words
In a computer network comprising a plurality of nodes and a plurality of links, the method of routing messages over said links comprising the following steps for each node: receiving a first exclusionary tree over at least one of said links, constructing at least a second exclusionary tree from said first exclusionary tree, transmitting said second exclusionary tree over one of said links, and routing messages according to the information in said first exclusionary tree.
Claim 4
Dependent Claim
75 words
In a computer network comprising a plurality of nodes and a plurality of links, the method of routing messages over said links comprising the following steps for each node: receiving a first exclusionary tree over at least one of said links, constructing at least a second exclusionary tree from said first exclusionary tree, transmitting said second exclusionary tree over one of said links, and routing messages according to the information in said first exclusionary tree.
Claim 5
Dependent Claim
55 words
The method as set forth in either claim 1 or claim 2 wherein said step of routing messages according to the information in said first exclusionary tree comprises the steps of constructing an intermediate form of the information contained in said first exclusionary tree, and routing messages according to the information in said intermediate form.
Claim 6
Dependent Claim
16 words
The method as set forth in claim 3 wherein said intermediate form comprises a routing graph.
Claim 7
Dependent Claim
16 words
The method as set forth in claim 3 wherein said intermediate form comprises a route table.
Claim 8
Dependent Claim
94 words
In a computer network comprising a plurality of nodes and a plurality of links, the method of routing messages among the nodes comprising the following steps for each node: receiving a plurality of exclusionary trees, one over each of a plurality of links, constructing from the received exclusionary trees a plurality of new exclusionary trees, one for each of the links, transmitting said one of the new exclusionary trees over each of the links, constructing a route table from the received exclusionary trees, and routing messages according to the information in the route table.
Claim 9
Dependent Claim
94 words
In a computer network comprising a plurality of nodes and a plurality of links, the method of routing messages among the nodes comprising the following steps for each node: receiving a plurality of exclusionary trees, one over each of a plurality of links, constructing from the received exclusionary trees a plurality of new exclusionary trees, one for each of the links, transmitting said one of the new exclusionary trees over each of the links, constructing a route table from the received exclusionary trees, and routing messages according to the information in the route table.
Claim 10
Dependent Claim
47 words
The method as set forth in claim 6 further comprising the steps of: retaining the received exclusionary trees, receiving a new exclusionary tree over one of said plurality of links, and replacing the retained exclusionary tree received from said one link with the new received exclusionary tree.
Claim 11
Dependent Claim
56 words
The method as set forth in claim 7 further comprising the steps of: receiving a second new exclusionary tree over said one link before the above recited step of replacing is performed, discarding first said new exclusionary tree, and replacing the retained exclusionary tree received over said one link with said second new received exclusionary tree.
Claim 12
Dependent Claim
46 words
The method of claim 6 further comprising the steps of: detecting the occurrence of a new link coming up, and transmitting a hello message on said new link, said hello message including information identifying the transmitting node and including no information identifying the intended receiving node.
Claim 13
Dependent Claim
89 words
The method of claim 9 further comprising the steps of retaining a copy of said transmitted exclusionary trees, receiving a hello message over a link, determining in response to said hello message if a copy of an exclusionary tree previously transmitted over said link has been retained and, if so, transmitting over said link a copy of said previously transmitted exclusionary tree and, if not, constructing from the received exclusionary trees above recited a new exclusionary tree for said link and transmitting said new exclusionary tree over said link.
Claim 14
Dependent Claim
25 words
The method of claim 9 wherein said hello message further includes information identifying the version number of the routing method used by the transmitting node.
Claim 15
Dependent Claim
65 words
The method of claim 11 further comprising the steps of receiving a hello message, comparing the version number of the routing method used by the node transmitting said hello message with the version number of the routing method used by the receiving node, and if equal, transmitting an exclusionary tree over the link, and if different, modifying the routing method used by the receiving node.
Claim 16
Dependent Claim
25 words
The method in claim 12 wherein said step of modifying comprises the step of transmitting an exclusionary tree over the link in a modified format.
Claim 17
Dependent Claim
23 words
The method in claim 12 wherein said step of modifying comprises the step of refraining from transmitting an exclusionary tree over the link.
Claim 18
Dependent Claim
33 words
The method of claim 6 further comprising the steps of: retaining the received exclusionary trees, detecting the occurrence of a link going down, and discarding the retained exclusionary tree received over said link.
Claim 19
Dependent Claim
20 words
The method as set forth in claim 6 wherein said route table contains multiple routes for a given destination node.
Claim 20
Dependent Claim
18 words
The method as set forth in claim 16 wherein said multiple routes are indicated by multiple node numbers.
Claim 21
Dependent Claim
18 words
The method as set forth in claim 16 wherein said multiple routes are indicated by multiple link numbers.
Claim 22
Dependent Claim
17 words
The method as set forth in claim 18 wherein said network includes multiple links interconnecting two nodes.
Claim 23
Dependent Claim
21 words
The method as set forth in claim 19 wherein said multiple links are treated independently and carry identical exclusionary tree information.
Claim 24
Dependent Claim
22 words
The method as set forth in claim 6 wherein said exclusionary trees include weight information indicating relative delays encountered on said links.
Claim 25
Dependent Claim
16 words
The method as set forth in claim 6 wherein said exclusionary trees are minimum spanning trees.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1987-08-14 | 1988-02-13 | 1988-08-14 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1991-08-14 | 1992-02-13 | 1992-08-14 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1995-08-14 | 1996-02-13 | 1996-08-14 | $7700.00 | Window Closed / Lapsed |