Patent US5253248A successfully refreshed from Google Patents.
US5253248A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Congestion control for connectionless traffic in data networks via alternate routing
Assignee: Nokia Bell Labs
•
Filing: 1990-07-03
•
Granted: 1993-10-12
•
Expires: 2010-07-03
Abstract
Abstract A congestion control scheme for connectionless networks relieves congestion by routing a portion of traffic on a congested primary path onto a predefined alternate path constructed such that loop-freedom is guaranteed. Explicit care is taken to avoid spreading congestion onto alternate paths. The control actions are taken in a completely distributed manner, based on local measurements only and therefore no signaling messages need to be exchanged between nodes. If desired, lower loss priority may be assigned to alternate routed traffic. Congestion is monitored locally and thresholds defined to declare the onset and abatement of congestion. The present invention affords at least an order of magnitude improvement in end-to-end cell blocking under sustained focussed overload.
Inventors
- 👤 Subrahmanyam Dravida
- 👤 P. Harshavardhana
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 16:44
CPC Classifications
H; H04; H04Q; H04Q3/00; H04Q3/64; H04Q3/66; H04Q3/665; H04L; H04L45/00; H04L45/12; H04L45/122; H04L45/18; H04L45/24; H04L45/247; H04L47/00; H04L47/10; H04L47/12; H04L47/122; H04L47/29; H04L47/30
Claims Analysis
Total Claims: 35
Claim 1
Independent Claim
232 words
A method of routing information packets from a first node in a network of interconnected nodes to a destination node, comprising the steps of a) forming a first routing table containing the primary route to be taken by information packets at said first node destined for said destination node and a second routing table containing an alternate route to be taken by information packets when said primary route is congested; b) monitoring congestion in said network; and c) routing a portion of said information packets over said alternate route in the presence of congestion; wherein said second routing table is formed by d) determining other nodes in said network that are interconnected with said first node; e) organizing each of said interconnected nodes including said first node into a series of layers in accordance with their distance, in hops, to said destination node; f) assigning a weight to each possible path between said first node and each of said other interconnected nodes in the same layer as said first node; g) assigning a weight to each possible path between each of said other interconnected nodes in said same layer and a connected node in a different layer, said different layer being closer to said destination node; and h) selecting said alternate route by minimizing the pairwise sum of the weights obtained during said first and second assigning steps (f) and (g) above.
Claim 2
Independent Claim
232 words
A method of routing information packets from a first node in a network of interconnected nodes to a destination node, comprising the steps of a) forming a first routing table containing the primary route to be taken by information packets at said first node destined for said destination node and a second routing table containing an alternate route to be taken by information packets when said primary route is congested; b) monitoring congestion in said network; and c) routing a portion of said information packets over said alternate route in the presence of congestion; wherein said second routing table is formed by d) determining other nodes in said network that are interconnected with said first node; e) organizing each of said interconnected nodes including said first node into a series of layers in accordance with their distance, in hops, to said destination node; f) assigning a weight to each possible path between said first node and each of said other interconnected nodes in the same layer as said first node; g) assigning a weight to each possible path between each of said other interconnected nodes in said same layer and a connected node in a different layer, said different layer being closer to said destination node; and h) selecting said alternate route by minimizing the pairwise sum of the weights obtained during said first and second assigning steps (f) and (g) above.
Claim 3
Dependent Claim
25 words
The method of claim 1 wherein said weight assigning steps include computing the distance between nodes using coordinate information representing the location of said nodes.
Claim 4
Independent Claim
145 words
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.
Claim 5
Independent Claim
145 words
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.
Claim 6
Dependent Claim
22 words
The invention defined in claim 3 wherein said primary path contains k hops and said alternate path contains at least k+1 hops.
Claim 7
Dependent Claim
25 words
The invention defined in claim 3 wherein said selecting step includes forming the pairwise sum of weighting factors assigned during both of said assigning steps.
Claim 8
Dependent Claim
27 words
The invention defined in claim 3, wherein said assigning step includes: forming said weighting factor as a function of the distance between nodes connected via said paths.
Claim 9
Dependent Claim
26 words
The invention defined in claim 3, wherein said alternate route is used only for a portion of the packets intended for a congested primary routing path.
Claim 10
Dependent Claim
50 words
The invention defined in claim 7, wherein said method further includes the steps of marking any packet transmitted over an alternate routing path; examining each packet at each node before it is routed, to determine if it has been marked; and routing marked packets only if said node is uncongested.
Claim 11
Independent Claim
167 words
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.
Claim 12
Independent Claim
167 words
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.
Claim 13
Dependent Claim
22 words
The invention defined in claim 9, wherein said first storing step includes forming an adaptive minimum spanning tree representation of said network.
Claim 14
Dependent Claim
32 words
The invention defined in claim 9, wherein said second storing step includes storing coordinate information representing the horizontal and vertical location of each of said nodes with respect to a reference system.
Claim 15
Independent Claim
139 words
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.
Claim 16
Independent Claim
139 words
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.
Claim 17
Dependent Claim
142 words
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 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.
Claim 18
Dependent Claim
142 words
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 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.
Claim 19
Independent Claim
123 words
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.
Claim 20
Independent Claim
123 words
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.
Claim 21
Dependent Claim
164 words
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.
Claim 22
Dependent Claim
164 words
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.
Claim 23
Dependent Claim
22 words
The invention defined in claim 15 wherein said primary path contains k hops and said alternate path contains at least k+1 hops.
Claim 24
Dependent Claim
37 words
The invention defined in claim 15 wherein said selecting means includes means for forming pairwise sums of said weighting factors for a) paths between nodes in the same layer, and b) paths between nodes in adjacent layers.
Claim 25
Dependent Claim
29 words
The invention defined in claim 15, wherein said assigning means includes: means for forming said weighting factor as a function of the distance between nodes connected via said paths.
Claim 26
Dependent Claim
33 words
The invention defined in claim 15, wherein said routing means is arranged so that said alternate route is used only for a portion of the packets intended for a congested primary routing path.
Claim 27
Dependent Claim
53 words
The invention defined in claim 19, wherein said apparatus further includes means for marking any packet transmitted over an alternate routing path; means for examining each packet at each node before it is routed, to determine if it has been marked; and means for routing marked packets only if said node is uncongested.
Claim 28
Dependent Claim
166 words
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.
Claim 29
Dependent Claim
166 words
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.
Claim 30
Dependent Claim
137 words
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.
Claim 31
Dependent Claim
137 words
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.
Claim 32
Dependent Claim
150 words
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 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.
Claim 33
Dependent Claim
150 words
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 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.
Claim 34
Dependent Claim
128 words
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.
Claim 35
Dependent Claim
128 words
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.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1996-10-11 | 1997-04-12 | 1997-10-12 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2000-10-11 | 2001-04-12 | 2001-10-12 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2004-10-11 | 2005-04-12 | 2005-10-12 | $7700.00 | Window Closed / Lapsed |