Routing of network traffic using discrete traffic measurement data

• US 5,142,570 A
• Filed: 06/15/1990
• Issued: 08/25/1992
• Est. Priority Date: 06/15/1990
• Status: Expired due to Term

• Current Assignee: TTI Inventions A LLC (Intellectual Ventures LLC)
• Original Assignee: Bell Communications Research, Inc. (Telefonaktiebolaget LM Ericsson)
• Inventors: Chaudhary, Ved P., Krishnan, Komandur R.
• Primary Examiner(s): Dwyer, James L.
• Assistant Examiner(s): Matar, Ahmad F.
• Application Number:
  US07/538,657
• Time in Patent Office: 802 Days
• Field of Search: 379/220, 379/221, 379/207, 379/112, 379/113
• 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/13217 Cranckback in routing, trombone connection, loopback circuit
• CPC Class Codes: H04Q 2213/13332 Broadband, CATV, dynamic bandwidth allocation
• CPC Class Codes: H04Q 2213/13344 Overflow
• 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 factrors 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. At predetermined intervals, traffic usage data is measured. At regular intervals, the occupancy factors corresponding to the busy-idle status of the links are used to compute occupancy values associated with each of the routes. Occupancy values not exceeding a threshold generate sequential route sets for each interval. Offered traffic is sequentially routed over the sequential route sets.

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, and wherein each node includes measurement means for measuring traffic usage data at each node at regular intervals determined by the measurement means, 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, to generate occupancy factors, each of said occupancy factors determined from both unassociated occupancy factors and 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,

wherein the improved method comprises the steps of

measuring traffic usage data at discrete intervals corresponding to the regular intervals of the measurement means,

computing occupancy values corresponding to the measured traffic usage data and selecting a sequential route set from the set of routes to sequentially route the offered traffic during the next one of said discrete intervals based on said computed occupancy values, and

sequentially routing the offered traffic through the network over said sequential route set during the next one of said discrete intervals.

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, and wherein each node includes measurement means for measuring traffic usage data at each node at regular intervals determined by the measurement means, 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, to generate occupancy factors, each of said occupancy factors determined from both unassociated occupancy factors and 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,

wherein the improved method comprises the steps of

measuring traffic usage data at discrete intervals corresponding to the regular intervals of the measurement means,

computing occupancy values corresponding to the measured traffic usage data and selecting sequential route sets from the sets of routes to sequentially route the offered traffic during the next one of said discrete intervals based on said computed occupancy values, and

sequentially routing the offered traffic through the network over said sequential route sets during the next one of said discrete intervals.

3. The method as recited in claim 2 wherein each set of routes, when evaluated, determines each said sequential route set based on the corresponding occupancy values having not exceeding predetermined threshold subject to each sequential route set having at least one route between each node pair.

4. The method as recited in claim 3 wherein each set of routes does not exceed a predetermined number of links.

5. 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, and wherein each switch includes measurement means for measuring traffic usage data at each switch at regular intervals determined by the measurement means, 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, to generate 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,

wherein the improved method comprises the steps of

measuring traffic usage data at discrete intervals corresponding to the regular intervals of the measurement means,

computing occupancy values corresponding to the measured traffic usage data and selecting a sequential route set from the set of routes to sequentially route the offered traffic during the next one of said discrete intervals based on said computed occupancy values, and

sequentially routing the offered traffic through the network over said sequential route set during the next one of said discrete intervals.

6. A method for routing offered traffic through a network comprising a plurality of nodes interconnected by links according to a preselected pattern, and wherein each node includes measurement means for measuring traffic usage data at each node at regular intervals determined by the measurement means, 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 estimates of future traffic, said occupancy factors derived from both unassociated occupancy factors and allocation factors corresponding to a nominal routing scheme over the network,

measuring traffic usage at predetermined intervals corresponding to the regular intervals of the measurement means to obtain usage of the links,

determining occupancy factors for each of said intervals, evaluating said occupancy values corresponding to said occupancy factors at each of said intervals, and selecting occupancy factors based on a predetermined threshold,

arranging said selected occupancy values in a pre-defined order to obtain sequential route sets, and

upon a request for service between a particular node pair, sequentially routing said offered traffic over a corresponding one of said sequential route sets during the next one of said predetermined intervals.

7. The method as recited in claim 6 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, 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.

8. The method as recited in claim 7 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 average occupancy of link k, rounded to the nearest integer value, over the last measurement interval, 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.

9. 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, and wherein each switch includes measurement means for measuring traffic usage data at each switch at regular intervals determined by the measurement means, said method comprising the steps of

maintaining, within each switch, a table of routes with each of said routes comprising at most a predetermined number of 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,

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 as based on traffic measured at predetermined intervals corresponding to the regular intervals of the measurement means,

evaluating the occupancy values from said requested occupancy factors and allocation factors, selecting values not exceeding a predetermined threshold, and arranging selected ones of said evaluated occupancy values to obtain a sequential route sets, and

upon a call request, sequentially routing the traffic over the route sets during the next one of said predetermined intervals.