US6600724B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Routing table structures
Assignee: Cisco Technology Inc
•
Filing: 1998-04-28
•
Granted: 2003-07-29
•
Expires: 2018-04-28
Abstract
Abstract A routing table structure for ATM or other networks comprises a shortest path tree architected and organized as a pseudo-spanning tree. The pseudo-spanning tree is a graphical representation of computed routes within the network, optimized to a specified constraint for a specified network service category, and allows for rapid compilation of one or more source-computed routes (e.g., DTLs in an ATM network) by traversing from a destination node specified in a call request to the calculating node (i.e., the node at which the request is received). Unlike conventional spanning trees, however, the pseudo-spanning tree representation may include alternate routes between network nodes. By providing these alternate routes in a single routing table structure, the present invention may utilize less storage and processing resources as compared to routing table schemes of the past. Further, in addition to the single optimization criterion, the routing table structure includes other network traffic parameters for associated links and nodes of the network.
Inventors
- 👤 Dean Cheng
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 20:31
CPC Classifications
H; H04; H04L; H04L45/00; H04L45/48; H04L12/00; H04L12/02; H04L12/16; H04L12/18; H04L12/1886; H04L45/16; H04L45/24; H04L45/247
Claims Analysis
Total Claims: 54
Claim 1
Independent Claim
89 words
A computer network routing structure comprising, a shortest path tree organized as a pseudo-spanning tree, that provides a plurality of source-computed routes within a computer network, each source computed route optimized to a plurality of specified constraints for a specified network service category, the plurality of source computed routes provided in a single routing table structure, such that the pseudo-spanning tree traverses from a destination node, specified in a call request, to a calculating node, the call request associated with a specified service request and set of service parameters.
Claim 2
Dependent Claim
89 words
A computer network routing structure comprising, a shortest path tree organized as a pseudo-spanning tree, that provides a plurality of source-computed routes within a computer network, each source computed route optimized to a plurality of specified constraints for a specified network service category, the plurality of source computed routes provided in a single routing table structure, such that the pseudo-spanning tree traverses from a destination node, specified in a call request, to a calculating node, the call request associated with a specified service request and set of service parameters.
Claim 3
Dependent Claim
21 words
The computer network routing structure of claim 1 wherein each of the plurality of source-computed routes comprise designated transit lists (DTLs).
Claim 4
Dependent Claim
25 words
The computer network routing structure of claim 2 wherein the plurality of source-computed routes comprise alternate routes between a plurality of nodes of the network.
Claim 5
Dependent Claim
29 words
The computer network routing structure of claim 2 further comprising network traffic parameters other than the plurality of specified constraints for associated links and nodes of the computer network.
Claim 6
Dependent Claim
35 words
The computer network routing structure of claim 1 comprising a computer-generated shortest path tree that provides a plurality of inter-nodal paths in a computer network, each inter-nodal path optimized to a plurality of specified constraints.
Claim 7
Dependent Claim
99 words
The computer network routing structure of claim 1 wherein the pseudo-spanning tree comprises a tree structure including a root node, branch nodes and leaf nodes, the leaf nodes being characterized by having at least one parent node and no child nodes, the branch nodes being characterized by having at least one parent node and at least one child node which may be a leaf node or a branch node, and the root node being characterized by having no parent nodes, the root node, branch nodes and leaf nodes being connected by one or more links of the computer network.
Claim 8
Dependent Claim
37 words
The computer network routing structure of claim 6 wherein a child node having two or more parent nodes denotes two equal cost paths within the computer network to reach the node of the computer network represented thereby.
Claim 9
Independent Claim
89 words
A method comprising: generating a shortest path tree that acts as a computer network routing structure, organized as a pseudo-spanning tree, to provide a plurality of inter-nodal paths in a computer network, each inter-nodal path optimized to a plurality of specified constraints, such that the pseudo-spanning tree traverses from a destination node, specified in a call request, to a calculating node, the call request associated with a specified service request and set of service parameters; and providing the one or more inter-nodal paths in a single routing table structure.
Claim 10
Independent Claim
89 words
A method comprising: generating a shortest path tree that acts as a computer network routing structure, organized as a pseudo-spanning tree, to provide a plurality of inter-nodal paths in a computer network, each inter-nodal path optimized to a plurality of specified constraints, such that the pseudo-spanning tree traverses from a destination node, specified in a call request, to a calculating node, the call request associated with a specified service request and set of service parameters; and providing the one or more inter-nodal paths in a single routing table structure.
Claim 11
Dependent Claim
17 words
The method of claim 8 further comprising selecting the constraints prior to generating the shortest path tree.
Claim 12
Dependent Claim
16 words
The method of claim 9 wherein one of the constraints is an additive ATM traffic metric.
Claim 13
Dependent Claim
15 words
The method of claim 10 wherein each of the constraints comprises cell delay variation (CDV).
Claim 14
Dependent Claim
27 words
The method of claim 10 wherein one of the constraints comprises a function of the relative desirability of using a link or node within the computer network.
Claim 15
Dependent Claim
15 words
The method of claim 10 wherein one of the constraints comprises cell transfer delay (CTD).
Claim 16
Dependent Claim
24 words
The method of claim 9 further comprising selecting one of the paths in response to a request for a connection within the computer network.
Claim 17
Dependent Claim
22 words
The method of claim 14 wherein selecting one of the paths comprises tracing the inter-nodal paths from destination node to local node.
Claim 18
Dependent Claim
20 words
The method of claim 15 wherein the destination node is identified from information contained in the request for a connection.
Claim 19
Dependent Claim
31 words
The method of claim 16 wherein the destination node is selected from the graphical representation using an index pointer from a table accessed using the information to identify the destination node.
Claim 20
Dependent Claim
16 words
The method of claim 8 wherein the shortest path tree is generated using a Dijkstra procedure.
Claim 21
Dependent Claim
16 words
The method of claim 18 wherein one of the specified constraints comprises an ATM traffic parameter.
Claim 22
Dependent Claim
30 words
The method of claim 19 wherein the shortest path tree includes ATM traffic parameters other than the plurality of specified constraints on each inter-nodal path included in the pseudo-spanning tree.
Claim 23
Dependent Claim
28 words
The method of claim 8 wherein the graphical representation is generated so as to include an arbitrary number of paths between any two nodes of the computer network.
Claim 24
Dependent Claim
30 words
The computer network routing structure of claim 6 wherein traversal of the tree is restricted to a path from a child node to a parent node of the child node.
Claim 25
Dependent Claim
111 words
A machine-readable medium that provides executable instructions, which when executed by a processing system, cause the processing system to perform a method, the method comprising: generating a shortest path tree that acts as a computer network routing structure, organized as a pseudo-spanning tree, to provide a plurality of inter-nodal paths in a computer network, each inter-nodal path optimized to a plurality of specified constraints, such that the pseudo-spanning tree traverses from a destination node, specified in a call request, to a calculating node, the call request associated with a specified service request and set of service parameters; and providing the one or more inter-nodal paths in a single routing table structure.
Claim 26
Dependent Claim
111 words
A machine-readable medium that provides executable instructions, which when executed by a processing system, cause the processing system to perform a method, the method comprising: generating a shortest path tree that acts as a computer network routing structure, organized as a pseudo-spanning tree, to provide a plurality of inter-nodal paths in a computer network, each inter-nodal path optimized to a plurality of specified constraints, such that the pseudo-spanning tree traverses from a destination node, specified in a call request, to a calculating node, the call request associated with a specified service request and set of service parameters; and providing the one or more inter-nodal paths in a single routing table structure.
Claim 27
Dependent Claim
19 words
The machine readable medium of claim 23 further comprising selecting the constraint prior to generating the shortest path tree.
Claim 28
Dependent Claim
18 words
The machine readable medium of claim 24 wherein one of the constraints is an additive ATM traffic metric.
Claim 29
Dependent Claim
17 words
The machine readable medium of claim 25 wherein one of the constraints comprises cell delay variation (CDV).
Claim 30
Dependent Claim
29 words
The machine readable medium of claim 25 wherein one of the constraints comprises a function of the relative desirability of using a link or node within the computer network.
Claim 31
Dependent Claim
17 words
The machine readable medium of claim 25 wherein one of the constraints comprises cell transfer delay (CTD).
Claim 32
Dependent Claim
26 words
The machine readable medium of claim 24 further comprising selecting one of the paths in response to a request for a connection within the computer network.
Claim 33
Dependent Claim
24 words
The machine readable medium of claim 29 wherein selecting one of the paths comprises tracing the inter-nodal paths from destination node to local node.
Claim 34
Dependent Claim
22 words
The machine readable medium of claim 30 wherein the destination node is identified from information contained in the request for a connection.
Claim 35
Dependent Claim
33 words
The machine readable medium of claim 31 wherein the destination node is selected from the graphical representation using an index pointer from a table accessed using the information to identify the destination node.
Claim 36
Dependent Claim
18 words
The machine readable medium of claim 23 wherein the shortest path tree is generated using a Dijkstra procedure.
Claim 37
Dependent Claim
18 words
The machine readable medium of claim 33 wherein one of the specified constraints comprises an ATM traffic parameter.
Claim 38
Dependent Claim
31 words
The machine readable medium of claim 34 wherein the shortest path includes ATM traffic parameters other than the plurality of specified constraints on each inter-nodal path included in the pseudo-spanning tree.
Claim 39
Dependent Claim
30 words
The machine readable medium of claim 23 wherein the graphical representation is generated so as to include an arbitrary number of paths between any two nodes of the computer network.
Claim 40
Independent Claim
93 words
An apparatus comprising: means for generating a shortest path tree that acts as a computer network routing structure, organized as a pseudo-spanning tree, to provide a plurality of inter-nodal paths in a computer network, each inter-nodal path optimized to a plurality of specified constraints, such that the pseudo-spanning tree traverses from a destination node, specified in a call request, to a calculating node, the call request associated with a specified service request and set of service parameters; and means for providing the one or more inter-nodal paths in a single routing table structure.
Claim 41
Independent Claim
93 words
An apparatus comprising: means for generating a shortest path tree that acts as a computer network routing structure, organized as a pseudo-spanning tree, to provide a plurality of inter-nodal paths in a computer network, each inter-nodal path optimized to a plurality of specified constraints, such that the pseudo-spanning tree traverses from a destination node, specified in a call request, to a calculating node, the call request associated with a specified service request and set of service parameters; and means for providing the one or more inter-nodal paths in a single routing table structure.
Claim 42
Dependent Claim
17 words
The apparatus of claim 37 further comprising selecting the constraints prior to generating the shortest path tree.
Claim 43
Dependent Claim
16 words
The apparatus of claim 38 wherein one of the constraints is an additive ATM traffic metric.
Claim 44
Dependent Claim
15 words
The apparatus of claim 39 wherein one of the constraints comprises cell delay variation (CDV).
Claim 45
Dependent Claim
27 words
The apparatus of claim 39 wherein one of the constraints comprises a function of the relative desirability of using a link or node within the computer network.
Claim 46
Dependent Claim
15 words
The apparatus of claim 39 wherein one of the constraints comprises cell transfer delay (CTD).
Claim 47
Dependent Claim
24 words
The apparatus of claim 38 further comprising selecting one of the paths in response to a request for a connection within the computer network.
Claim 48
Dependent Claim
22 words
The apparatus of claim 43 wherein selecting one of the paths comprises tracing the inter-nodal paths from destination node to local node.
Claim 49
Dependent Claim
20 words
The apparatus of claim 44 wherein the destination node is identified from information contained in the request for a connection.
Claim 50
Dependent Claim
31 words
The apparatus of claim 45 wherein the destination node is selected from the graphical representation using an index pointer from a table accessed using the information to identify the destination node.
Claim 51
Dependent Claim
16 words
The apparatus of claim 37 wherein the shortest path tree is generated using a Dijkstra procedure.
Claim 52
Dependent Claim
16 words
The apparatus of claim 47 wherein one of the specified constraints comprises an ATM traffic parameter.
Claim 53
Dependent Claim
30 words
The apparatus of claim 48 wherein the shortest path includes ATM traffic parameters other than the plurality of the specified constraints on each inter-nodal path included in the pseudo-spanning tree.
Claim 54
Dependent Claim
28 words
The apparatus of claim 37 wherein the graphical representation is generated so as to include an arbitrary number of paths between any two nodes of the computer network.
References Cited (Backward Citations)
US4466060A
Cited
US4905233A
Cited
US5115495A
Cited
US5253248A
Cited
US5317562A
Cited
US5313454A
Cited
US5274643A
Cited
US5649108A
Cited
US5991272A
Cited
US5948069A
Cited
US5805593A
Cited
US5991295A
Cited
US5844887A
Cited
US6144661A
Cited
US5995503A
Cited
US6201810B1
Cited
US6202082B1
Cited
US6304549B1
Cited
US6067298A
Cited
US6026077A
Cited
US6097722A
Cited
US6104701A
Cited
US6141325A
Cited
US5903559A
Cited
US6041059A
Cited
US6122272A
Cited
US6094687A
Cited
US6256309B1
Cited
US6529498B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2006-07-28 | 2007-01-27 | 2007-07-29 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2010-07-28 | 2011-01-27 | 2011-07-29 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2014-07-28 | 2015-01-27 | 2015-07-29 | $7700.00 | Window Closed / Lapsed |