Efficient caching of routing information for unicast and multicast connections

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.

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.

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.

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.

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.

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.

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.

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.