Multiplex communications – Network configuration determination – Using a particular learning algorithm or technique
Reexamination Certificate
1997-06-30
2003-06-24
Rao, Seema S. (Department: 2666)
Multiplex communications
Network configuration determination
Using a particular learning algorithm or technique
C370S351000, C370S408000
Reexamination Certificate
active
06584075
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to switching systems and more particularly to the computation of routes for nodes of switching network.
2. Description of Related Art
Routing algorithms are known in the prior art for determining minimum cost routes from a source to a destination through A switching network.
Switching nodes, and network routers are also known which direct digital packets from an incoming port to an outgoing link which goes toward the destination.
The Problems
Route computation presents a difficult problem. It is computationally difficult and time consuming to determine the most cost effective routes through a switching network. Nevertheless, routing decisions need to be made quickly.
Network configurations can change quickly and unexpectedly when links go down or are restored or when new links are initiated. Nodes of a switching network need to be able to adapt quickly to avoid service deterioration when changes to network configuration occur.
SUMMARY OF THE INVENTION
One embodiment of the invention relates to a particularly convenient representation of network routing trees which permits routing decisions to be made with great speed and with relatively small amounts of processing power. The representation permits changes in network configuration to be accommodated in many instances with a quick patch to keep the network operational until a new routing table can be calculated. Unnecessary calculation of routing tables can be avoided when network configuration changes when the resulting change would not improve the routing tree. Improvement or not can be quickly determined using this representation.
Another embodiment of the invention relates to a route computation engine for performing routing calculations for a switching node.
Another embodiment of the invention relates to a router having one or more input ports, a plurality of output ports, and a controller. The controller directs digital information from the one or more input ports to one or more appropriate output port(s). The controller is also configured to maintain routing information in one or more tables with each entry in a table comprising a node identification, a parent node identification, a link identifier and an effective distance by which a node identified by the node identification is separated from a designated node.
Another embodiment of the invention relates to a switching system for providing digital communications including a plurality of switching nodes interconnected by digital communications links, a source of digital information connected to a first one of the switching nodes, and a destination for the digital information connected to a second one of the switching nodes, in which at least the first one of the 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 the node identification is separated from the first one of the switching nodes.
Another embodiment of the invention is directed to a method of determining a unicast route from a source node to a destination node over a switching network, by storing a preferred routing tree linking each node of a switching network, in a table in at least one node, looking up a destination node in a table and determining a parent of the destination node, and if the parent is the source node, terminating the search, and otherwise if the parent is not the source node, continuing to look up parent nodes of each intervening node until the source node is reached. The determined route is then the set of parent nodes between the source node and the destination node.
Another embodiment of the invention relates to a method of determining a multicast route from a source node to a plurality of destinations, by determining a route between the source node and a first destination and recording the route as a first partial list of nodes constructed by beginning with the 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. The single list of nodes represents a round trip traversal of all nodes in a multicast tree.
Another embodiment of the invention relates to a method of patching a preferred (low cost) 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 the preferred 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 the link, identifying nodes on the first partial tree using an effective distance to source field in the table, selecting a replacement link running between a node on the first tree and the node on the second partial tree at the end of the link, and overwriting in the table an entry for the failed link with an entry for the replacement link.
Another embodiment of the invention relates to a method of determining whether recalculation of a minimum cost tree is necessary when a link having a connection to a first node at a first end and a connection to a second node at a second end becomes available, by determining the effective distance from a source node to the first node using a table, determining the effective distance from the source node to the second node using a table, and recalculating the minimum cost tree only if the distance from a source node to the second node is greater than the sum of the distance from the source node to the first node plus the effective distance of the link.
Other aspects of the invention relate to computer program products for carrying out the techniques of the invention and to the transmission of such computer program products over a network.
The foregoing and other features, aspects and advantages of the present invention will become more apparent from the following detailed description of the present invention when taken in conjunction with the accompanying drawings.
REFERENCES:
patent: 4987536 (1991-01-01), Humblet
patent: 5117422 (1992-05-01), Hauptschein et al.
patent: 5233604 (1993-08-01), Ahmadi et al.
patent: 5291477 (1994-03-01), Liew
patent: 5321815 (1994-06-01), Bartolanzo, Jr. et al.
patent: 5933425 (1999-08-01), Iwata
Gupta Amit
Hsiao Tony
Rom Raphael
Duong Frank
Rao Seema S.
Rosenthal & Osha L.L.P.
Sun Microsystems Inc.
LandOfFree
Efficient caching of routing information for unicast and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Efficient caching of routing information for unicast and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient caching of routing information for unicast and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3146287