Congestion control for connectionless traffic in data networks via alternate routing

A method of controlling congestion in the flow of information bearing packets traveling over paths in a network of interconnected nodes, comprising the steps of

• routing packets from each node to destination nodes via multihop primary routing paths;
• monitoring congestion in said nodes in said network;
• and
• routing packets from ones of said nodes to said destinations via alternate multihop routing paths in the event that congestion is encountered in said network;
• wherein said alternate routing paths are determined by
• grouping said interconnected nodes into a plurality of layers, each layer containing nodes that are the same distance, in hops from a particular destination;
• assigning a weighting factor to each path between interconnected nodes in said layers;
• assigning a weighting factor to each path between interconnected nodes in adjacent layers;
• and
• selecting said alternate routing paths as a function of combinations of said weighting factors.

A method of selecting loop free alternate multi-hop paths for information bearing packets traveling over a network of communication nodes, comprising the steps of

• storing in each of said communication nodes information describing the connections between each node in said network and neighboring nodes;
• storing in each of said communication nodes information for assigning weights assigned to paths between each connected pair of nodes;
• grouping interconnected nodes into k layers, each layer containing nodes having the same distance, in hops, from a potential destination;
• computing, for each node in layer k, the pairwise sum of the stored weights assigned to a) paths between said each node in layer k and a first set of connected nodes in layer k;
• and b) paths between said first set of connected nodes in layer k and a second set of connected nodes in layer k-1, and
• selecting as the alternate route from said node in layer k to said potential destination, the path having the smallest of said pairwise sums.

A method of reducing congestion in a connectionless network including a plurality of interconnected nodes, comprising the steps of

• associating with each node in said network, a primary route to be taken by at least a portion of traffic from said node destined for each destination node;
• associating with each node in said network, an alternate route to be taken by traffic from said node destined for each destination node in the event that said primary route is congested;
• monitoring congestion in said network, and
• routing traffic on said alternate route in the event that congestion is detected;
• wherein said first association step includes forming a k-hop route using adaptive minimum spanning tree routing;
• and
• wherein said second association step includes forming a route having at least k+1 hops, based upon connectivity information locally available in said each node.

In a network of interconnected nodes in which packets are transmitted over a primary route determined by selecting the shortest path, in hops, between the originating node and the destination node, a method of providing an alternate route in the event said primary route is congested, said method comprising the steps of

• grouping nodes between said originating node and said destination node into a plurality of groups, such that the nodes in the k.sup.th group are equally distant, in hops, from said destination node;
• assigning a weight w(i,j) to each path between nodes i and j in group k and a weight w(j,j') to each path between node j in group k and node j' in group k-1,
• determining if said primary route is congested, and
• if so, routing said packets via an alternate path selected such that w(i,j)+w(j,j') is minimized.

A method of determining an alternate route for traffic in a network of nodes when the primary route between said nodes is congested, comprising the steps of

• for each destination, forming groups of said nodes as a function of the distance of each of said nodes from said destination;
• assigning a first weighting factor to each path between a node in one of said groups and each connected node in the same group, and a second weighting factor to each path between each of said connected nodes in the same group and other connected nodes in another of said groups;
• and
• responsive to congestion in said network of nodes, selecting said alternate route as a function of said first and second weighting factors.

Apparatus for controlling congestion in the flow of information bearing packets traveling over paths in a network of interconnected nodes, comprising

• a) means for monitoring congestion in primary and secondary routing paths within said network;
• and
• b) means for routing packets from each node to destination nodes via multihop primary routing paths in the absence of congestion and for routing packets from ones of said nodes to said destinations via alternate multihop routing paths in the event that congestion is encountered in said primary routing paths;
• wherein said routing means includes
• means for grouping said interconnected nodes into a plurality of layers, each layer containing nodes that are the same distance, in hops from a particular destination;
• means for assigning a weighting factor to each path between interconnected nodes in said layers, and for assigning a weighting factor to each path between interconnected nodes in adjacent layers;
• and
• means for selecting said alternate routing paths as a function of combinations of said weighting factors.

Apparatus for selecting loop free alternate multi-hop paths for information bearing packets traveling over a network of communication nodes, comprising

• means for storing in each of said communication nodes (a) information describing the connections between each node in said network and neighboring nodes, and (b) information for assigning weights to paths between each connected pair of nodes;
• means for grouping interconnected nodes into k layers, each layer containing nodes having the same distance, in hops, from a potential destination;
• means for computing, for each node in layer k, the pairwise sum of the stored weights assigned to a) paths between said each node in layer k and a first set of connected nodes in layer k;
• and b) paths between said first set of connected nodes in layer k and a second set of connected nodes in layer k-1, and
• means for selecting as the alternate route from said node in layer k to said potential destination, the path having the smallest of said pairwise sums.

Apparatus for reducing congestion in a connectionless network including a plurality of interconnected nodes, comprising

• means for associating with each node in said network a) a primary route to be taken by at least a portion of traffic from said each node destined for each destination node, and b) an alternate route to be taken by traffic from said node destined for each destination node in the event that said primary route is congested;
• means for monitoring congestion in said network, and
• means for routing traffic on said alternate route in the event that congestion is detected;
• wherein said associating means includes (a) means for forming a k-hop route using adaptive minimum spanning tree routing, and (b) means for forming a route having at least k+1 hops based upon connectivity information locally available in said each node.

In a network of interconnected nodes in which packets are transmitted over a primary route determined by selecting the shortest path, in hops, between the originating node and the destination node, apparatus for providing an alternate route in the event said primary route is congested, said apparatus comprising

• means for grouping nodes between said originating node and said destination node into a plurality of groups, such that the nodes in the k.sup.th group are equally distant, in hops, from said destination node,
• means for assigning a weight w(i,j) to each path between nodes i and j in group k and a weight w(i,j'), to each path between node j in group k and node j' in group k-1, and
• means for determining if such primary route is congested;
• and
• means responsive to said determining means for routing said packets via an alternate path selected such that w(i,j)+w(i,j') is minimized.

Apparatus for determining an alternate route for traffic in a network of nodes when the primary route between said nodes is congested, comprising

• for each destination, means for forming groups of said nodes as a function of the distance of each of said nodes from said destination;
• means for assigning a first weighting factor to each path between a node in one of said groups of each connected node in the same group, and a second weighting factor to each path between each of said connected nodes in the same group and other connected nodes in another of said groups;
• and
• means responsive to the occurrence of congestion in said network of nodes for selecting said alternate route as a function of said first and second weighting factors.