Patent Publication Number: US-5155851-A

Title: Routing an incoming data stream to parallel processing stations

Description:
This is a continuation of application Ser. No. 07/351,377, filed May 15, 1989 now abandoned. 
    
    
     FIELD OF THE INVENTION 
     This invention relates generally to routing an arriving job stream to parallel, autonomous stations and, more particularly, to the allocation of the stream of incoming jobs among several parallel stations, each with its own service rate and finite buffer. 
     BACKGROUND OF THE INVENTION 
     The problem of routing an input job stream to one of several parallel processing stations, each with a finite buffer, so as to minimize the probability of blocking has conventionally been treated using state-independent or state-dependent approaches. Blocking in the sense used here means that an arriving job from the stream cannot be routed to any station because the buffers in all stations are full. 
     Representative of the state-independent approach is the description contained in the article entitled &#34;The Optimal Input Rates to a System of Manufacturing Cells&#34;, by D. D. Yao and J. G. Shanthikumar, and published in INFOR Vol. 25, No. 1, pg. 57-65, 1987. Yao et al have supplied a routing technique by deriving an optimum Bernoulli split of the arrival stream, making use of convexity properties of a so-called loss-rate function defined by Yao et al. However, such a routing method does not take into account the various states of the stations, and therefore the optimization is restricted to the framework of state-independent decision rules and routing methods. 
     An optimum state-dependent assignment or routing rule may be derived with the assumption of Poisson arrivals for the jobs and exponential service-time distributions for the stations and by solving the associated finite-state Markov decision process. The technique is state-dependent since information about the state of each processing station, such as the total number of jobs assigned to each buffer, is available and may be used for computation by a front-end routing processor. However, the state-space grows very rapidly with buffer capacities and this limits the size of systems that may be solved, particularly in real-time. 
     SUMMARY OF THE INVENTION 
     These shortcomings as well as other limitations of conventional techniques are obviated, in accordance with the present invention, by a method that routes an incoming job to an appropriate one of the numerous processing stations using policy-iteration on a nominal state-independent technique. The method allows for a nearly-optimal, state-dependent allocation method without the burdensome computation required of the optimal, state-dependent scheme. 
     Broadly speaking, the method applies to a system for routing an offered job from an incoming job stream through a switching device to one of several processing stations. At predetermined time intervals, occupancy factors are computed for the stations as determined by the system configuration and the rate of arrival of incoming jobs from the stream. Upon the arrival of an offered job from the stream, the occupancy factors corresponding to the activity status of the stations at the instant of the arrival of the offered job are used to compute utilization values associated with each of the stations. The minimum utilization value is compared to a preselected threshold. If the minimum utilization factor is less than the threshold, then the station having this minimum value is the one selected for processing the job, and the offered job is routed through the switch accordingly. Otherwise the offered job is blocked. 
     The organization and operation of this invention will be better understood from a consideration of the detailed description of the illustrative method, which follows, when taken in conjunction with the accompanying drawing. 
    
    
     BRIEF DESCRIPTION OF THE DRAWING 
     FIG. 1 is a block diagram depicting a parallel station system illustrative of the types of systems controlled by the methodology of the present invention; 
     FIG. 2 is a block diagram illustrative of the buffer of FIG. 1 showing various parameters defined for the buffer: and 
     FIG. 3 is a flow diagram illustrative of the steps for controlling the routing of an offered job to one of the several processing stations of FIG. 1. 
    
    
     DETAILED DESCRIPTION 
     With reference to FIG. 1, a block diagram of parallel station system 100 is shown as comprising switch 10, processor 20 and numerous (N) stations of which stations 30, 40 and 50 are representative. A job stream, appearing on line 11, serves as an input to switch 10. Each offered job in the stream is to be assigned, in the absence of blocking, to one of the stations 30,40, . . . , 50 operating in parallel. If an offered job is assigned to station 30, it is transmitted from switch 10 to station 30 via line 12. Similarly, lines 13 and 14 convey jobs assigned to stations 40 and 50, respectively. 
     Each job arriving at an individual station is stored in a buffer. For instance, buffer 31 is shown as composing part of station 30. In the modeling process discussed below, each buffer is treated as a queue, so system 100 may be viewed as being composed of N queues operating in parallel. The composition of a queue is shown in FIG. 2 for the i th  buffer. This queue has servers 1,2, . . . , s i , each of service rate μ i . These are also m i  additional waiting positions available. The parameter k i  denotes the total number of jobs in the queue; thus, k i  ranges over 0,1,2, . . . ,m i  +s i . 
     As is depicted in FIG. 1, each buffer 31,41,51 is monitored by processor 20 to determine the total number of jobs in each buffer, that is, the parameter k i  of each queue. For instance, lead 36 emanating from buffer 31 supplies the value of k 1  to processor 20. The collection of values for the various buffers, namely, (k 1 , k 2 , . . . , k N ) representing the current job state, serves as one input to processor 20. Station configuration information (s i , μ i  and m i ), as well as the information to compute the offered load factor λ i  (discussed below), serve as a second input to processor 20 via lead 22. 
     Processor 20 computes occupancy factors designated by Δ(i,k i ) in FIG. 1. Based on these factors, the switching state of switch 10 is selected by the control signal on lead 21 emanating from processor 20. The control signal includes: information, designated a station parameter, that identifies which of the stations is to receive the offered job, thereby effectuating the desired switching action; or a blocking signal to indicate to switch 10 that no station is available to accept the offered job. The mathematical formulation below details the manner in which the occupancy factors are computed. These factors have the general interpretation: each Δ(i,k i ) approximates the &#34;cost&#34;, in terms of future job blockings, of increasing the number of jobs in queue i from k i  to k i+1 . The formulation provides a methodology, and concomitant control mechanism, for routing job arrivals to one of the N stations such that the probability of blocking an offered job from the job stream is minimized. An indication that a job has been blocked is provided by line 19 emanating from switch 10. 
     FORMULATION 
     The development begins by considering a single queue of s servers, each of service rate μ, with m additional waiting positions and an incoming Poisson stream of rate λ; these parameters define an M/M/s/(s+m) queue. Furthermore, it is supposed that k (0,1,2, . . . , m+s) denotes the total number of jobs in the buffer queue, including in-service jobs and waiting jobs. With V k  defined as the cost of state k, an occupancy factor, designated Δ k , is defined as follows: 
     
         Δ.sub.k  V.sub.k+1 -V.sub.k =N.sub.k G               (1) 
    
     where 
     N k  =expected number of arrivals during the first passage from state k to state (k+1), and G=the steady-state blocking of the M/M/s/(s+m) queue, ##EQU1## 
     A first-order difference equation may then be used to compute N k , which results in the following: ##EQU2## 
     With the approximation that the streams arriving at the stations on the leads emanating from switch 10 are independent Poisson streams, it follows that by indexing the queue variables in equation (3) by the queue-index i, the `cost` of assigning an arriving job to queue i when the system is in state (k 1 , . . . , k N ) is obtained. Each station i has an associated set of occupancy factors, now denoted Δ(i,k i ), wherein the parameters s, μ, m, k and λ in equation (3) have a corresponding subscript i to signify the i th  queue or station. The occupancy factors are updated infrequently (say every half hour to two hours) by processor 20. 
     The occupancy factors are then used, at the instant an offered job arrives at switch 10, to determine utilization values of the N stations. The instantaneous state of the stations is determined by the vector (k 1 , . . . , k N ) at the moment of arrival of the offered job. Then, the routing control mechanism is as follows: route an offered job, when the system is in state (k 1 , . . . , k N ), to the station which has the smallest utilization value below a predetermined threshold. Typically, the threshold is set at a normalized value of 1.0. Since 0≦Δ(i,k i )≦1.0 with Δ(i,m i  +s i )=1, a threshold of 1.0 implies that blocking occurs only if all stations are fully utilized. 
     EXAMPLE 
     It is supposed that a job stream with an arrival rate of 4.0 is offered to two stations (N=2). TABLE I summarizes the information about the exemplary system. 
     
                       TABLE I                                                     
______________________________________                                    
               Service  Waiting                                           
Queue Server   Rate     Positions                                         
                                Load State Factor                         
i     s.sub.i  μ.sub.i                                                 
                        m.sub.i λ.sub.i                            
                                     k.sub.i                              
                                           Δ(i,k.sub.i)             
______________________________________                                    
1     1        1        5       0.784                                     
                                     0     0.061                          
                                     1     0.140                          
                                     2     0.240                          
                                     3     0.367                          
                                     4     0.530                          
                                     5     0.736                          
                                     6     1.000                          
2     5        1        1       3.216                                     
                                     0     0.076                          
                                     1     0.100                          
                                     2     0.139                          
                                     3     0.206                          
                                     4     0.333                          
                                     5     0.594                          
                                     6     1.000                          
______________________________________                                    
 
    
     The first column lists the buffer/queue identifiers for the two stations. As the next three columns depict: the first queue has one server, with a service rate of 1.0, and five additional waiting positions; and the second queue has five servers, each with a service rate of 1.0, and one additional waiting position. The fifth column shows the load factor λ i  ; the technique for determining its value will be discussed below. The sixth column shows the current state k i  of each queue. In each case, k i  ranges from 0 to m i  +s i  with m i  +s i  =6 for both queues. Finally, the seventh column shows the occupancy factors Δ(i,k i ) corresponding to each state k i  computed according to equation (3). 
     By way of an example of the routing control mechanism, if it is supposed that a job arrives when k 1  =2 and k 2  =3, then the job is routed to the second station since Δ(1,2)=0.240&gt;0.206=Δ(2,3). On the other hand, if the job arrives with k 1  =1 and k 2  =3, then the first station is selected since Δ(1,1)=0.140&lt;0.206=Δ(2,3). Moreover, if a job arrives with k 1  =k 2  =6, then blocking results. 
     FIG. 3 is a flow diagram illustrative of the steps described above for controlling the routing of an arriving or offered job in the job stream to the appropriate one of the stations so as to minimize job blocking. Block 200 indicates that certain information about the station configuration (e.g., s i , μ i  and m i ) and job stream information (λ and λ i ) is available for processing by processor 20. As depicted by block 210, the Δ(i,k i ) factors for predetermined time intervals are computed based on present job stream information. As shown by block 220, upon the detection at switch 10 of an offered job, the occupancy factors as well as the current status of the stations 30,40, . . . , 50, as provided to processor 20 by state vector (k 1 , k 2 , . . . , k N ), are used to compute the set of utilization values for the stations. The processing of block 230 is then invoked to route, via switching of switch 10 under control of processor 20, the offered job to the station having the minimum utilization factor, provided this factor is less than a predetermined threshold; otherwise, the offered job is blocked. 
     Determination of the λ i  Load Factors 
     The λ i  &#39;s represent the allocation of the Poisson arrival steam of rate λ to various parallel stations 30, 40, . . . , 50 under an optimum, state-independent scheme of Bernoulli splitting. In this scheme, each arriving job is assigned to a station chosen at random, according to a probability distribution, without regard to the status of the stations or to the assignment of previous jobs from the stream. The optimum probability distribution which minimizes blocking under such a random assignment can be determined by the formulation of a complex non-linear program, as follows: ##EQU3## 
     The λ i  &#39;s obtained from the solution of equation (4) are substituted in equation (3) to compute the occupancy factors for state-dependent routing. 
     Variations on the system arrangement of FIG. 1 may be readily appreciated by those skilled in the art. For instance, an electronic switch 10 will often incorporate processing capability so that switch 10 and processor 20 may coalesce into a single switch means effecting both processing and routing. 
     It is to be understood that the above-described embodiment is simply illustrative of the application of the application of the principles in accordance with the present invention. Other embodiments may be readily devised by those skilled in the art which may embody the principles in spirit and scope in accordance with the claims.