Routing an incoming data stream to parallel processing stations

• US 5,155,851 A
• Filed: 09/19/1991
• Issued: 10/13/1992
• Est. Priority Date: 05/15/1989
• Status: Expired due to Term

• Current Assignee: TTI Inventions A LLC (Intellectual Ventures LLC)
• Original Assignee: Bell Communications Research, Inc. (Telefonaktiebolaget LM Ericsson)
• Inventors: Krishnan, Komandur R.
• Primary Examiner(s): Clark, David L.
• Assistant Examiner(s): Fagan, Matthew C.
• Application Number:
  US07/762,610
• Time in Patent Office: 390 Days
• Field of Search: 395/650
• US Class Current: 718/105
• CPC Class Codes: G06F 15/161 Computing infrastructure, e.g. computer clusters, blade chassis or hardware partitioning casings, cabinets, racks or drawers for data centers H05K5/00
• CPC Class Codes: G06F 2209/5022 Workload threshold
• CPC Class Codes: G06F 9/505 considering the load

Abstract

A process controls the routing of an arriving job in a job stream through a switch to one of a plurality of processing stations. At predetermined time intervals, occupancy factors associated with the stations are computed as determined by station configuration information and job stream information. Upon the arrival of an incoming job, the occupancy factors corresponding to the current processing status of the stations are used to compute station utilization values. The station having the minimum utilization value is selected to receive and process the incoming job provided this minimum value is less than a preselected threshold; otherwise, the incoming job is denied processing permission.

Claims

1. A method for routing an offered data job arriving from an incoming job stream through data switch means to one of a plurality of processing stations, the switch means and the stations being arranged in a configuration wherein each of the stations has a measurable current processing status, said method comprising the steps of

configuring each of the stations with a buffer queue having waiting positions and with a number of servers having a service rate for serving the queue.

generating and storing allocation load factors in a computer, the computer being coupled to the switch means and the processing stations, said allocation factors being based on a random assignment of the incoming job stream to the stations,

measuring the current processing status of each of the stations at predetermined intervals, and providing the current processing status at each of the predetermined intervals to the computer,

executing mathematical forecasting formulae stored in the computer to generate occupancy factors at the predetermined intervals with the computer, said forecasting formulae being expressed in terms of said waiting positions, said servers, said service rate, said allocation factors, and past and present offered data jobs in the job stream as determined by the current processing status at the predetermined intervals of each of the stations, said occupancy factors thereby providing estimates of future data job blockings given the processing status at the beginning of each of the predetermined intervals,

upon the arrival of the offered data job, measuring the current processing status of the stations and providing each current processing status to the computer,

generating utilization values in the computer, one for each station, from said occupancy factors in correspondence to the current processing status of the stations to produce routing alternatives through the switch means, and

establishing a connection route for the offered data job through the switch means in accordance with one of said routing alternatives based on said utilization values.

2. The method as recited in claim 1 wherein

the job stream has a given job rate,

the current processing status is indicative of a number of active servers and a number of offered jobs in said waiting positions for each station,

said allocation factors are expressed in terms of said job rate, and

said formulae are expressed in terms of said servers, said waiting positions, said service rate, said allocation factors, and a blocking formula which accounts for said future job blockings given the current status of each station at each of the predetermined intervals.

3. A method for routing an offered data job arriving from an incoming job stream through data switch means to one of a plurality of processing stations, the switch means and the stations interconnected in an arrangement wherein each of the stations has a measurable current processing status, said method comprising the steps of

configuring each of the stations with a buffer queue having waiting positions and with a number of servers having a service rate for serving the queue.

generating allocation load factors with a computer, the computer being coupled to the switch means and the processing stations, said allocation factors being based on a random assignment of the incoming job stream to the stations,

measuring the current processing status of each of the stations at predetermined intervals and providing the current processing status to the computer,

generating occupancy factors at the predetermined intervals with the computer, said occupancy factors being determined by the configuration of each of the stations, said occupancy factors providing estimates of future job blockings given the processing status at the beginning of each of the predetermined intervals, wherein the processing stations are numbered 1, 2, . . . i, . . . N, and wherein the step of generating occupancy factors includes the step of equating said occupancy factors for the i^th station to Δ

(i,k_i) factors determined from a relation ##EQU4## where s_i is the number of servers serving the i^th station queue,

μ

_i is the service rate of said i^th station queue,

m_i is the number of additional waiting positions in said i^th station queue,

λ

_i is one of said allocation factors, and

k_i =[0,1, . . . ,] m_i +s_i,

upon the arrival of the offered data job, measuring the current processing status of the stations, providing each current processing status to the computer, and generating utilization values in the computer, one for each station, from said occupancy factors in correspondence to the current processing status of the stations to produce routing alternatives through the switch means, and

establishing a connection route for the offered data job through the switch means in accordance with one of said routing alternatives based on said utilization values.

4. The method as recited in claim 3 wherein the step of generating utilization values includes the steps of

selecting for each of the stations (i=1,2, . . . , N) its associated one of said occupancy factors Δ

(i,k_i), with k_i equal to a total number of jobs being serviced by the i^th station upon arrival of the offered job, and

equating said utilization values to a set of Δ

(i,k_i) factors determined from each current processing status expressed by k₁,k₂, . . . ,k_N.

5. A system for selectively routing an offered data job arriving from an incoming job stream of digital data to one of a plurality of processing stations each having a measurable current processing status, each of the stations including a buffer queue having additional waiting positions and a number of servers having a service rate for serving the queue, said system comprising

a switch for receiving the job stream,

job routing lines interconnecting each of the stations to said switch, and

means, coupled to said switch and each of the stations, for controlling said switch to route the offered job, said means for controlling including

means for measuring the current status of the stations upon the arrival of the offered job, said status indicative of the number of servers serving the queue in each of the stations, the service rate of the servers, and the number of additional waiting positions in the queue,

means, coupled to said means for measuring, for generating allocation load factors based on a random assignment of the incoming job to the stations, for receiving the current status of the stations, and for periodically generating estimates of future job blockings using traffic estimation formulae to produce routing alternatives through the switch means to said job routing lines for the offered job, wherein the processing stations are numbered 1, 2, . . . i, . . . N, and wherein said means for generating includes means for determining occupancy factors by equating said occupancy factors for the i^th station to Δ

(i,k_i) factors determined from a relation ##EQU5## where s_i is the number of servers serving the i^th station queue,

μ

_i is the service rate of said i^th station queue,

m_i is the number of additional waiting positions in said i^th station queue,

λ

_i is one of said allocation factors, and

k_i =[0,1, . . . ,]m_i +s_i,

means for receiving said occupancy factors and for selecting one of said routing alternatives based on said received occupancy values, and

means, coupled to said switch, for establishing a connection route through said switch in accordance with said one of said routing alternatives.

6. The system as recited in claim 5 wherein said means for determining further includes

means for evaluating for each of the stations (i=1,2, . . . , N) its associated one of said occupancy factors Δ

(i,k_i), with k_i being the total number of jobs in service by the i^th station upon the arrival of the offered job, to produce utilization values, and

means for equating said utilization values to the set of Δ

(i,k_i) factors determined from each current status expressed by k₁,k₂, . . . , k_N, and further wherein said means for selecting selects said one routing alternative based on said utilization values.

7. The system as recited in claim 6 wherein said means for controlling further includes means for transmitting to said switch;

a station parameter identifying a selected one of the stations to receive the offered job whenever a minimum of said utilization values is less than a predetermined threshold, said selected one of the stations. corresponding to said one of said routing alternatives;

or a blocking signal whenever said minimum utilization value is equal to or exceeds said predetermined threshold.