Routing of network traffic

• US 4,788,721 A
• Filed: 12/09/1987
• Issued: 11/29/1988
• Est. Priority Date: 12/09/1987
• Status: Expired due to Term

• Current Assignee: Telcordia Technologies Incorporated (Telefonaktiebolaget LM Ericsson)
• Original Assignee: Bell Communications Research, Inc. (Telefonaktiebolaget LM Ericsson)
• Inventors: Ott, Teunis J., Krishnan, Komandur R.
• Primary Examiner(s): BROWN, THOMAS
• Application Number:
  US07/130,423
• Time in Patent Office: 356 Days
• Field of Search: 379/221, 379/220, 379/113, 379/230, 340/827
• US Class Current: 379/221.07
• CPC Class Codes: H04Q 2213/13141 Hunting for free outlet, circuit or channel
• CPC Class Codes: H04Q 2213/13164 Traffic (registration, measurement,...)
• CPC Class Codes: H04Q 2213/13166 Fault prevention
• CPC Class Codes: H04Q 2213/13213 Counting, timing circuits
• CPC Class Codes: H04Q 2213/13332 Broadband, CATV, dynamic bandwidth allocation
• CPC Class Codes: H04Q 3/66 Traffic distributors

Abstract

A process is disclosed for 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. Also, at predetermined time intervals, occupancy factors are computed as determined by the network configuration and in response to traffic information. These occupancy factors are proportional to unassociated occupancy factors and allocation factors associated with calls of the various node-pairs; each of these latter factors is derived from a nominal routing scheme in which a call of the corresponding node-pair is treated as lost only if it is blocked on all of its permitted routes. Upon a request for service, the occupany factors corresponding to the busy-idle status of the links are used to compute an occupancy value associated with each of the end routes. Each route is converted to a candidate route based on traffic load at the initiation of the service request. The minimum occupancy 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.

Claims

1. An improved method for routing offered traffic through a network comprising nodes wherein each node is adapted to communicate with each of the other nodes, said method including the steps of

generating a set of routes between a pre-selected node pair, and

controlling the selection of the traffic route between the pre-selected node pair from the set of routes by evaluating the routes in the set in response to current usage of the set and from future estimates of traffic blockings that take into consideration expected total traffic, including the offered traffic, and

wherein in the improved method the step of controlling by evaluating comprises the step of generating occupancy factors, each of said occupancy factors determined from both unassociated occupancy factors and from allocation factors, said unassociated factors being derived from a nominal routing scheme in which offered traffic blocked on a single route is treated as lost and said allocation factors being derived from a nominal routing scheme in which offered traffic is lost only when all routes are busy.

2. An improved method for routing offered traffic through a network comprising nodes wherein each node is adapted to communicate with each of the other nodes, said method including the steps of

generating sets of routes between node pairs, and

controlling the selection of traffic routes between respective node pairs from the corresponding sets of routes by evaluating the routes in the sets in response to the current usage of the associated routes from estimates of future traffic blockings that take into consideration expected total traffic, including the offered traffic, and

wherein in the improved method the step of controlling by evaluating comprises the step of generating occupancy factors, each of said occupancy factors determined from both unassociated occupancy factors and from allocation factors, said unassociated factors being derived from a nominal routing scheme in which offered traffic blocked on a single route is treated as lost and said allocation factors being derived from a nominal routing scheme in which offered traffic is lost only when all routes are busy.

3. The method as recited in claim 2 wherein each set of routes, when evaluated, provides a candidate route having a corresponding occupancy value, and the step of controlling includes the step of routing the traffic over said candidate route only if said corresponding value is less than a predetermined threshold.

4. An improved method for routing a call through a switching system comprising a plurality of intelligent switches wherein each switch is arranged to communicate with each of the other switches, said method including the steps of

generating a set of routes between a pair of switches, and

controlling the selection of the call route between the pair of switches from route choices determined in response to the current usage of the set and from estimates of future call blockings that take into consideration expected total calls, including the call, and

wherein for the improved method the step of controlling the selection comprises the step of determining occupancy factors, each of said occupancy factors derived from both unassociated occupancy factors and from allocation factors, said unassociated factors being generated from a nominal routing scheme in which a call blocked on a single route is treated as a lost call and said allocation factors being generated from a nominal routing scheme in which a call is lost only when all routes are busy.

5. A method for routing offered traffic through a network comprising 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,

generating, at predetermined intervals, occupancy factors as determined by the network configuration, past and present traffic information and extimates of future traffic blocking take into consideration expected total traffic, including the offered traffic, said occupancy factors derived from both unassociated occupancy factors and allocation factors corresponding to a nominal routing scheme over the network,

upon a request for service between a particular node pair, computing occupancy values from the said occupancy factors corresponding 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 values is less than a preselected threshold, routing the request over the route having the minimum value;

otherwise, blocking the service request.

6. The method as recited in claim 5 wherein the step of generating occupancy factors includes the step of

equating said occupancy factors to the product θ

_km Δ

(k,j), where Δ

(k,j) is given by ##EQU3## where B is the Erlang-B formula, s_k is the number of potential servers in link k, 0≦

j≦

s_k k, h is the expected duration of said offered traffic, λ

_k is the expected usage of link k of the network and θ

_km is the allocation factor associated with the use of link k by a call coupling node-pair m.

7. The method as recited in claim 6 wherein the step of computing occupancy values includes the steps of

evaluating for each of the routes in said associated set the quantities ##EQU4## where R is one route and Δ

(k,X_k) is the unassociated 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 θ

_km is the allocation factor associated with the use of link k by calls coupling node-pair m, 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.

8. A method for routing traffic through a network, the network comprising a plurality of switches and a plurality of trunk groups interconnecting preselected switches according to a predetermined pattern, each switch arranged to communicate with each of the other switches, said method comprising the steps of

maintaining, within each switch, a table of routes with each of said routes comprising at most two trunk groups between the switch and each of the other switches,

maintaining, within each switch, unassociated occupancy factors and allocation factors for all trunk groups terminating on that switch,

upon a call received by an originating switch, identifying a destination switch from a call translation,

requesting said destination switch to transmit to said originating switch selected ones of said occupancy and allocation factors associated with corresponding ones of said routes between said originating and destination switches,

for each of said corresponding ones of said routes, computing occupancy values from said selected ones of said unassociated factors and said allocation factors, and

routing said call over the one of said routes associated with the minimum of said values whenever said minimum value is less than a preselected threshold;

otherwise, blocking said call.