US6584075B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Efficient caching of routing information for unicast and multicast connections
Assignee: Oracle America Inc
•
Filing: 1997-06-30
•
Granted: 2003-06-24
•
Expires: 2017-06-30
Abstract
Abstract A routing engine for a node controller of a switch or for a router provides enhanced routing for unicast and multicast connections by representing preferred routing trees, associated with different bandwidths and quality of service indications, as tables having, for each entry, a node identification, a parent node identification, a link identifier and ah effective distance by which a node identified by the node identification is separated from the controller or router. The routing engine adapts quickly to changes in network configurations, such as link failure, by quickly patching a table affected by the failure in order to maintain service until a new preferred routing tree can be calculated. Recalculations of preferred routing trees are avoided by using said table to determine whether a new link or a restored link could possibly provide a more cost effective route than that specified in the existing table.
Inventors
- 👤 Amit Gupta
- 👤 Raphael Rom
- 👤 Tony Hsiao
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-31 03:31
CPC Classifications
H; H04; H04L; H04L45/00; H04L45/22; H04L12/00; H04L12/02; H04L12/16; H04L12/18; H04L12/185; H04L12/1863; H04L12/1877; H04L45/16; H04L45/28; H04L45/302; H04L45/48
Claims Analysis
Total Claims: 34
Claim 1
Independent Claim
95 words
Computer apparatus for determining routing at a node of a network, comprising: a. one or more input ports; b. a plurality of output ports: c. a controller for directing digital information from said one or more input ports to an appropriate output port, said controller configured to maintain routing information in one or more tables, each entry in each of the one or more tables comprising a node identification, a parent node identification, a link identifier and an effective distance by which a node identified by said node identification is separated from a designated node.
Claim 2
Dependent Claim
95 words
Computer apparatus for determining routing at a node of a network, comprising: a. one or more input ports; b. a plurality of output ports: c. a controller for directing digital information from said one or more input ports to an appropriate output port, said controller configured to maintain routing information in one or more tables, each entry in each of the one or more tables comprising a node identification, a parent node identification, a link identifier and an effective distance by which a node identified by said node identification is separated from a designated node.
Claim 3
Dependent Claim
21 words
The computer apparatus of claim 1 in which said one or more tables contains a representation of a minimum cost tree.
Claim 4
Dependent Claim
32 words
The computer apparatus of claim 1 in which said computer apparatus maintains routing information in a plurality of tables, one or more for each of a plurality of quality of service levels.
Claim 5
Dependent Claim
41 words
The computer apparatus of claim 1 in which quality of service is established by specifying values for bandwidth, and one of constant bit rate, real time variable bit rate, non-real time variable bit rate, available bit rate and unspecified bit rate.
Claim 6
Dependent Claim
105 words
A switching system for providing digital communications, comprising: a. a plurality of switching nodes interconnected by digital communications links; b. a source of digital information connected to a first one of said switching nodes; and c. a destination for said digital information connected to a second one of said switching nodes; in which at least said first one of said switching nodes is configured, with a routing table including, in each entry, a node identification, a parent node identification, a link identifier and an effective distance by which a node identified by said node identification is separated from said first one of said switching nodes.
Claim 7
Dependent Claim
105 words
A switching system for providing digital communications, comprising: a. a plurality of switching nodes interconnected by digital communications links; b. a source of digital information connected to a first one of said switching nodes; and c. a destination for said digital information connected to a second one of said switching nodes; in which at least said first one of said switching nodes is configured, with a routing table including, in each entry, a node identification, a parent node identification, a link identifier and an effective distance by which a node identified by said node identification is separated from said first one of said switching nodes.
Claim 8
Independent Claim
116 words
A method of determining a unicast route from a source node to a destination node over a switching network, comprising the steps of: a. storing a preferred routing tree linking each node of a switching network, in a table in at least said source node; b. looking up a destination node in a table and determining a parent of said destination node; c. if said parent is said source node, terminating said search; and d. if said parent is not said source node, continuing looking up parent nodes for each intervening node until said source node is reached; the determined route then including the set of parent nodes between said source node and said destination node.
Claim 9
Independent Claim
116 words
A method of determining a unicast route from a source node to a destination node over a switching network, comprising the steps of: a. storing a preferred routing tree linking each node of a switching network, in a table in at least said source node; b. looking up a destination node in a table and determining a parent of said destination node; c. if said parent is said source node, terminating said search; and d. if said parent is not said source node, continuing looking up parent nodes for each intervening node until said source node is reached; the determined route then including the set of parent nodes between said source node and said destination node.
Claim 10
Independent Claim
169 words
A method of determining a multicast route from a source node to a plurality of destinations, comprising the steps of: a. determining a route between said source node and a first destination and recording said route as a first partial list of nodes constructed by beginning with said destination node at the center and adding a next parent node to each end of the list until the source node is reached; b. determining a partial list of nodes for a next destination in the same way until a node is reached which is on the first list; c. determining a partial list of nodes for each destination in the same way until each destination has a partial list of nodes constructed; and d. patching in each partial list of nodes into the previous partial list of nodes until all partial lists of nodes have been patched into a single list of nodes, said single list of nodes represents a round trip traversal of all nodes in a multicast tree.
Claim 11
Independent Claim
169 words
A method of determining a multicast route from a source node to a plurality of destinations, comprising the steps of: a. determining a route between said source node and a first destination and recording said route as a first partial list of nodes constructed by beginning with said destination node at the center and adding a next parent node to each end of the list until the source node is reached; b. determining a partial list of nodes for a next destination in the same way until a node is reached which is on the first list; c. determining a partial list of nodes for each destination in the same way until each destination has a partial list of nodes constructed; and d. patching in each partial list of nodes into the previous partial list of nodes until all partial lists of nodes have been patched into a single list of nodes, said single list of nodes represents a round trip traversal of all nodes in a multicast tree.
Claim 12
Independent Claim
140 words
A method of patching a preferred routing tree represented as a table when a link between a first node of a switching network and a second node fails resulting in partitioning said preferred routing tree into a first partial tree and a second partial tree comprising the steps of: a. using a list of network links to determine all nodes which connect to a node on the second partial tree at one end of said link; b. identifying nodes on said first partial tree using an effective distance to source field in said table; c. selecting a replacement link running between a node on said first tree and said node on the second partial tree at the end of said link; and d. overwriting in said table an entry for the failed link with an entry for said replacement link.
Claim 13
Independent Claim
140 words
A method of patching a preferred routing tree represented as a table when a link between a first node of a switching network and a second node fails resulting in partitioning said preferred routing tree into a first partial tree and a second partial tree comprising the steps of: a. using a list of network links to determine all nodes which connect to a node on the second partial tree at one end of said link; b. identifying nodes on said first partial tree using an effective distance to source field in said table; c. selecting a replacement link running between a node on said first tree and said node on the second partial tree at the end of said link; and d. overwriting in said table an entry for the failed link with an entry for said replacement link.
Claim 14
Dependent Claim
20 words
The method of claim 8 in which said patching occurs before recalculation of a new preferred routing tree is completed.
Claim 15
Dependent Claim
24 words
The method of claim 9 in which routing is determined based on a patched preferred routing tree as soon as the patch is completed.
Claim 16
Dependent Claim
42 words
The network of claim 8 , in which the replacement link is selected based on the minimum effective distance to the source node from said node on the second partial tree if a candidate replacement node were to be the replacement node.
Claim 17
Dependent Claim
132 words
A computer program product comprising: a. a memory medium; b. a computer program, stored on said memory medium, said computer program comprising instructions for determining a unicast route from a source node to a destination node over a switching network, by storing a preferred routing cost tree linking each node of a switching network, in a table in at least one computer apparatus, looking up a destination node in a table and determining a parent of said destination node if said parent is said source node, terminating said search; and if said parent is not said source node, continue looking up parent nodes of each intervening node until said source node is reached; in which the determined route is the set of parent nodes between said source node and said destination node.
Claim 18
Dependent Claim
132 words
A computer program product comprising: a. a memory medium; b. a computer program, stored on said memory medium, said computer program comprising instructions for determining a unicast route from a source node to a destination node over a switching network, by storing a preferred routing cost tree linking each node of a switching network, in a table in at least one computer apparatus, looking up a destination node in a table and determining a parent of said destination node if said parent is said source node, terminating said search; and if said parent is not said source node, continue looking up parent nodes of each intervening node until said source node is reached; in which the determined route is the set of parent nodes between said source node and said destination node.
Claim 19
Dependent Claim
23 words
The computer program product of claim 12 , in which said computer program is transmitted from said memory medium over a network interface.
Claim 20
Dependent Claim
183 words
A computer program product comprising: a. a memory medium; b. a computer program, stored on said memory medium, said computer program comprising instructions for determining a multicast route from a source node to a plurality of destinations by determining a route between said source node and a first destination and recording said route as a first partial list of nodes constructed by beginning with said destination node at the center and adding a next parent node to each end of the list until the source node is reached; determining a partial list of nodes for a next destination in the same way until a node is reached which is on the first list; determining a partial list of nodes for each destination in the same way until each destination has a partial list of nodes constructed; and patching in each partial list of nodes into the previous partial list of nodes until all partial lists of nodes have been patched into a single list of nodes, said single list of nodes represents a round trip traversal of all nodes in a multicast tree.
Claim 21
Dependent Claim
183 words
A computer program product comprising: a. a memory medium; b. a computer program, stored on said memory medium, said computer program comprising instructions for determining a multicast route from a source node to a plurality of destinations by determining a route between said source node and a first destination and recording said route as a first partial list of nodes constructed by beginning with said destination node at the center and adding a next parent node to each end of the list until the source node is reached; determining a partial list of nodes for a next destination in the same way until a node is reached which is on the first list; determining a partial list of nodes for each destination in the same way until each destination has a partial list of nodes constructed; and patching in each partial list of nodes into the previous partial list of nodes until all partial lists of nodes have been patched into a single list of nodes, said single list of nodes represents a round trip traversal of all nodes in a multicast tree.
Claim 22
Dependent Claim
23 words
The computer program product of claim 14 , in which said computer program is transmitted from said memory medium over a network interface.
Claim 23
Dependent Claim
154 words
A computer program product comprising: a. a memory medium; b. a computer program, stored on said memory medium, said computer program comprising instructions for patching a preferred routing tree represented as a table when a link between a first node of a switching network and a second node fails, which results in partitioning said preferred routing tree into a first partial tree and a second partial tree by using a list of network links to determine all nodes which connect to a node on the second partial tree at the end of said link; identifying nodes on said first partial tree using an effective distance to source field in said table; selecting a replacement link running between a node on said first tree and said node on the second partial tree at the end of said link overwriting in said table an entry for the failed link with an entry for said replacement link.
Claim 24
Dependent Claim
154 words
A computer program product comprising: a. a memory medium; b. a computer program, stored on said memory medium, said computer program comprising instructions for patching a preferred routing tree represented as a table when a link between a first node of a switching network and a second node fails, which results in partitioning said preferred routing tree into a first partial tree and a second partial tree by using a list of network links to determine all nodes which connect to a node on the second partial tree at the end of said link; identifying nodes on said first partial tree using an effective distance to source field in said table; selecting a replacement link running between a node on said first tree and said node on the second partial tree at the end of said link overwriting in said table an entry for the failed link with an entry for said replacement link.
Claim 25
Dependent Claim
22 words
The computer program product of claim 16 , in which said computer program is transmitted from said memory medium over network interface.
Claim 26
Dependent Claim
67 words
A computer data signal embodied in a carrier wave and representing a sequence of instructions which, when executed by one or more processors, causes the one or more processors to use a routing table including, in each entry, a node identification, a parent node identification, a link identification and an effective distance by which a node identified by said node identification is separated from a source node.
Claim 27
Dependent Claim
67 words
A computer data signal embodied in a carrier wave and representing a sequence of instructions which, when executed by one or more processors, causes the one or more processors to use a routing table including, in each entry, a node identification, a parent node identification, a link identification and an effective distance by which a node identified by said node identification is separated from a source node.
Claim 28
Dependent Claim
104 words
A switching system for providing digital communications, comprising: a. a plurality of switching nodes interconnected by digital communications links; b. a source of digital information connected to a first one of said switching nodes; and c. a destination for said digital information connected to a second one of said switching nodes; in which at least one processor of said switching system is configured with a routing table including, in each entry, a node identification, a parent node identification, a link identifier and an effective distance by which a node identified by said node identification is separated from said first one of said switching nodes.
Claim 29
Dependent Claim
104 words
A switching system for providing digital communications, comprising: a. a plurality of switching nodes interconnected by digital communications links; b. a source of digital information connected to a first one of said switching nodes; and c. a destination for said digital information connected to a second one of said switching nodes; in which at least one processor of said switching system is configured with a routing table including, in each entry, a node identification, a parent node identification, a link identifier and an effective distance by which a node identified by said node identification is separated from said first one of said switching nodes.
Claim 30
Dependent Claim
91 words
Computer apparatus for determining routing for a node of a network, comprising: a processor for calculating routing of digital information from at least one node of a network from a source node to a destination node, said processor configured to maintain routing information in one or more tables for a node, each entry in each of the one or more tables comprising a node identification, a parent node identification, a link identifier and an effective distance by which a node identified by said node identification is separated from a designated node.
Claim 31
Dependent Claim
91 words
Computer apparatus for determining routing for a node of a network, comprising: a processor for calculating routing of digital information from at least one node of a network from a source node to a destination node, said processor configured to maintain routing information in one or more tables for a node, each entry in each of the one or more tables comprising a node identification, a parent node identification, a link identifier and an effective distance by which a node identified by said node identification is separated from a designated node.
Claim 32
Dependent Claim
21 words
The computer apparatus of claim 20 in which said one or more tables contains a representation of a minimum cost tree.
Claim 33
Dependent Claim
31 words
The computer apparatus of claim 20 in which said processor maintains routing information in a plurality of tables, one or more for each of a plurality of quality of service levels.
Claim 34
Dependent Claim
41 words
The computer apparatus of claim 20 in which quality of service is established by specifying values for bandwidth, and one of constant bit rate, real time variable bit rate, non-real time variable bit rate, available bit rate and unspecified bit rate.
References Cited (Backward Citations)
US4987536A
Cited
US5321815A
Cited
US5117422A
Cited
US5233604A
Cited
US5291477A
Cited
US5933425A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2006-06-23 | 2006-12-23 | 2007-06-24 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2010-06-23 | 2010-12-23 | 2011-06-24 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2014-06-23 | 2014-12-23 | 2015-06-24 | $7700.00 | Window Closed / Lapsed |