US4931941A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Adaptive routing of network traffic
Assignee: Iconectiv LLC
•
Filing: 1988-07-25
•
Granted: 1990-06-05
•
Expires: 2008-07-25
Abstract
Abstract A process is disclosed for adaptively routing service requests through a network comprising nodes interconnected with links. The network is also arranged so that each node may communicate with each of the other nodes. At preselected time intervals, sets of routes through the network are generated in response to the network configuration and traffic information. Over predetermined periods, traffic data is measured to determine carried load and blocking for each link. Also, at predetermined time intervals, occupancy factors are computed as determined by the network configuration and in response to traffic information including measured traffic data. Each of the occupany factors is derived from a nominal routing scheme in which a call blocked on a single route is treated as a lost call as in separable routing. Upon a request for service, the occupany factors corresponding to the busy-idle status of the links are used to compute an occupany value associated with each of the routes. Each route is converted to a candidate route based on traffic load at the initiation of the service request. The minimum occupany value for each set of routes is selected as the candidate route for bridging a given node pair. If this minimum value is less than a preselected threshold, the traffic is routed over this candidate route, thereby satisfying the service request. Otherwise, the request is denied.
Inventors
- 👤 Komandur R. Krishnan
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-25 22:19
CPC Classifications
H; H04; H04Q; H04Q3/00; H04Q3/64; H04Q3/66; H04Q2213/00; H04Q2213/13141; H04Q2213/13164; H04Q2213/13166; H04Q2213/13213; H04Q2213/13217; H04Q2213/13332
Claims Analysis
Total Claims: 11
Claim 1
Independent Claim
191 words
A method for routing offered traffic through a network composed of a plurality of nodes interconnected by links according to a preselected pattern, wherein each node is arranged to communicate with the other nodes, said method comprising the steps of generating, for use at preselected intervals, sets of routes, each route composed of at least one link and each set including at least one route between each node pair, over predetermined periods, measuring link data to estimate an equivalent offered load for each link, said equivalent offered load for each link being given by the ratio φ/(1-α), where φ is the carried load and α is the blocking, as obtained from measured link data, and computing route occupancy factors based on said equivalent offered load, upon a request for service between a particular node pair, computing occupancy values from said occupancy factors in relation to the current usage of the links comprising the routes in the set associated with the node pair, and if the minimum of the occupancy value is less than a preselected threshold, routing the request over the route having the minimum value; otherwise, blocking the service request.
Claim 2
Independent Claim
191 words
A method for routing offered traffic through a network composed of a plurality of nodes interconnected by links according to a preselected pattern, wherein each node is arranged to communicate with the other nodes, said method comprising the steps of generating, for use at preselected intervals, sets of routes, each route composed of at least one link and each set including at least one route between each node pair, over predetermined periods, measuring link data to estimate an equivalent offered load for each link, said equivalent offered load for each link being given by the ratio φ/(1-α), where φ is the carried load and α is the blocking, as obtained from measured link data, and computing route occupancy factors based on said equivalent offered load, upon a request for service between a particular node pair, computing occupancy values from said occupancy factors in relation to the current usage of the links comprising the routes in the set associated with the node pair, and if the minimum of the occupancy value is less than a preselected threshold, routing the request over the route having the minimum value; otherwise, blocking the service request.
Claim 3
Dependent Claim
48 words
The method as recited in claim 1 wherein φ is equal to the average number of busy servers in each said link in a given period and α is equal to the proportion of time all servers in each said link are busy in the same given period.
Claim 4
Independent Claim
206 words
A method for routing offered traffic through a network composed of a plurality of nodes interconnected by links according to a preselected pattern, wherein each node is arranged to communicate with the other nodes, said method comprising the steps of generating, for use at preselected intervals, sets of routes, each route composed of at least one link and each set including at least one route between each node pair, over predetermined periods, measuring link data to estimate an equivalent offered load for each link and computing route occupancy factors based on said equivalent offered load, said occupancy factors being given by the Δ(k,j) factors obtained from the relation ##EQU3## where B is the Erlang-B formula, s k is the number of potential servers in link k, 0<j<s k and y k is the equivalent offered load for each link k, upon a request for service between a particular node pair, computing occupancy values from said occupancy factors in relation to the current usage of the links comprising the routes in the set associated with the node pair, and if the minimum of the occupancy value is less than a preselected threshold, routing the request over the route having the minimum value; otherwise, blocking the service request.
Claim 5
Independent Claim
206 words
A method for routing offered traffic through a network composed of a plurality of nodes interconnected by links according to a preselected pattern, wherein each node is arranged to communicate with the other nodes, said method comprising the steps of generating, for use at preselected intervals, sets of routes, each route composed of at least one link and each set including at least one route between each node pair, over predetermined periods, measuring link data to estimate an equivalent offered load for each link and computing route occupancy factors based on said equivalent offered load, said occupancy factors being given by the Δ(k,j) factors obtained from the relation ##EQU3## where B is the Erlang-B formula, s k is the number of potential servers in link k, 0<j<s k and y k is the equivalent offered load for each link k, upon a request for service between a particular node pair, computing occupancy values from said occupancy factors in relation to the current usage of the links comprising the routes in the set associated with the node pair, and if the minimum of the occupancy value is less than a preselected threshold, routing the request over the route having the minimum value; otherwise, blocking the service request.
Claim 6
Dependent Claim
95 words
The method as recited in claim 3 wherein the step of computing occupancy values includes the steps of evaluating for each of the routes in the associated set the quantities ##EQU4## where R is one route and Δ(k,X k ) is the occupancy factor evaluated such that j=X k , X k being the number of busy servers in link k at the initiation of the service request, and the summation is over all links k comprising each route R, and equating said occupancy values for the routes in the set with the V(R) quantities.
Claim 7
Dependent Claim
33 words
The method as recited in claim 4 wherein y k =φ/(1-α), where φ is the carried load and α is the blocking, as obtained from the measured link data for each link k.
Claim 8
Dependent Claim
46 words
The method as recited in claim 5 wherein φ is equal to the average number of busy servers in link k in a given period and α is equal to the proportion of time all servers in link k are busy in the same given period.
Claim 9
Independent Claim
190 words
A method for routing offered traffic through a network composed of a plurality of nodes interconnected by links according to a preselected pattern, wherein each node is arranged to communicate with the other nodes, said method comprising the steps of generating, for use at preselected intervals, sets of routes, each route composed of at least one link and each set including at least one route between each node pair, initially computing route occupancy factors using a presumed set of nominal link loads in order to service requests received prior to the first estimate of an equivalent offered load, over predetermined periods, measuring link data to estimate said equivalent offered load for each link and computing route occupancy factors based on said equivalent offered load, upon a request for service between a particular node pair, computing occupancy values from said occupancy factors in relation to the current usage of the links comprising the routes in the set associated with the node pair, and if the minimum of the occupancy value is less than a preselected threshold, routing the request over the route having the minimum value; otherwise, blocking the service request.
Claim 10
Independent Claim
190 words
A method for routing offered traffic through a network composed of a plurality of nodes interconnected by links according to a preselected pattern, wherein each node is arranged to communicate with the other nodes, said method comprising the steps of generating, for use at preselected intervals, sets of routes, each route composed of at least one link and each set including at least one route between each node pair, initially computing route occupancy factors using a presumed set of nominal link loads in order to service requests received prior to the first estimate of an equivalent offered load, over predetermined periods, measuring link data to estimate said equivalent offered load for each link and computing route occupancy factors based on said equivalent offered load, upon a request for service between a particular node pair, computing occupancy values from said occupancy factors in relation to the current usage of the links comprising the routes in the set associated with the node pair, and if the minimum of the occupancy value is less than a preselected threshold, routing the request over the route having the minimum value; otherwise, blocking the service request.
Claim 11
Dependent Claim
23 words
The method as recited in claim 7 wherein the nominal link loads equal the number of servers in each of the corresponding links.
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) | 1993-06-04 | 1993-12-04 | 1994-06-05 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1997-06-04 | 1997-12-04 | 1998-06-05 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2001-06-04 | 2001-12-04 | 2002-06-05 | $7700.00 | Window Closed / Lapsed |