# Stability of Switched Server Systems with Constraints on Service-Time and Capacity of Buffers

Authors: Li Wang; Zhonghe He; Chi Zhang
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

The execution of emptying policy ensures the convergence of any solution to the system to a unique periodic orbit, which does not impose constraints on service-time and capacity of buffers. Motivated by these problems, in this paper, the service-time-limited policy is first proposed based on the information resulted from the periodic orbit under emptying policy, which imposes lower and upper bounds on emptying time for the queue in each buffer, by introducing lower-limit and upper-limit service-time factors. Furthermore, the execution of service-time-limited policy in the case of finite buffer capacity is considered. Moreover, the notion of feasibility of states under service-time-limited policy is introduced and then the checking condition for feasibility of states is given; that is, the solution does not exceed the buffer capacity within the first cycle of the server. At last, a sufficient condition for determining upper-limit service-time factors ensuring that the given state is feasible is given.


---

## Body

## 1. Introduction

Switched server system is a class of mathematical models for queuing systems with finite number of conflicting queues alternately served by a single server. Moreover, there exists a nonzero setup time of the server whenever the server switches from serving one queue to another one, and assume that the jobs arrive at and leave the buffer at constant rates in this paper. The evolution of the system involves continuous changes of queues in buffers and discrete switching of the server, and thus switched server system is a special class of hybrid systems [1, 2], with extensive applications in practical problems, such as manufacturing systems [3, 4] and traffic signal control systems [5–7], and more applications of this field can be referred to [8].Fundamental synthesis problem for switched server systems is to design the scheduling policy of the server. The emptying policy (i.e., the server alternately empties queues in buffers with any fixed cyclic sequence) was proposed in [9], under which any solution to the system asymptotically converges to a unique periodic orbit analytically determined by system parameters [6]. However, the emptying policy does not impose constraints on queue-emptying time in converging process of the solution. In practical applications, the server with emptying policy must take longer time to empty buffers with larger queues, and thus other buffers have to wait longer time for service. Thus, in order to ensure fairness for all buffers, the upper bound for emptying time of each buffer based on emptying policy was considered in [10], and a conjecture about stability of the policy was given, which was further proved in [11]. Also, [12] considered distributed execution of emptying policy with upper bounds for queue-emptying time of buffers in the network with multiple servers. In most of literatures, a scheduling policy is first proposed, and then dynamic behaviors of the system are analyzed, as in [9]. In [13–16], a different idea for controlling the network was presented; that is, the steady state (a periodic orbit) of the system is first given, and then corresponding scheduling policy is derived ensuring the convergence of any solution to the steady state. However, the policies in [13–16] resulting from the given periodic orbit do not impose constraints on service time of buffers.The problems about designs of the scheduling policies with constraints on queue serving process mainly result from practical applications. For example, in traffic intersection, the signal control for signalized intersections was modeled as switched server systems in [5, 6], and emptying policy was applied, where signal light in a signalized intersection is seen as the server; incoming links to the signalized intersection are seen as buffers, which can accommodate queues of vehicles; the lost time between phase switching is seen as the nonzero setup time of the server; and signal control law is seen as the scheduling policy of the server. However, in traffic control [17], the shortest and longest green-time constraints on each of traffic phases are necessarily imposed for feasible signal control plans, with the purpose of ensuring traffic safety for drivers and pedestrians, and controlling total delay of signalized intersections, respectively. Thus, inspired by traffic control, the emptying policy is further extended in this paper, based on which the service-time-limited policy is proposed, with lower and upper bounds on queue-emptying time of each buffer by introducing lower-limit and upper-limit service-time factors, respectively. Furthermore, the buffer capacity is finite for most of real-world problems. For example, in a signalized intersection, incoming links with finite length only accommodates finite number of vehicles. Thus, the execution of service-time-limited policy in the case of finite buffer capacities is considered, and moreover the notion of feasibility of states under service-time-limited policy is introduced, that is, the state originating in which the solution asymptotically converges to the steady state (the periodic orbit) and does not exceed buffer capacities in the converging process. Moreover, the checking condition for feasibility of states is given; that is, the solution does not exceed buffer capacities within the first cycle of the server, and a sufficient condition for determining upper-limit service-time factors ensuring that the given state is feasible is given.The paper is organized as follows. After descriptions for the model of switched server systems in Section2, we introduce emptying and service-time-limited policies in Section 3. Feasibility of states and checking conditions under service-time-limited policy are considered in Section 4. Conclusions and future research topics are given in Section 5.


## 2. Descriptions of Switched Server Systems

A switched server system (see Figure1 for illustration) consists of n(n≥2) buffers and a single server, where the server alternately serves buffers in terms of the scheduling policy and only one buffer each time. Let xi(t)≥0 denote the queue of jobs in the buffer i at the moment t≥0. Because of nonnegative constraints on the queue of jobs in each buffer, the state space X of the system is defined as X≜{[x1,…,xn]T∈Rn:xi≥0,i=1,…,n}. Assume that the jobs arrive at the buffer i at a constant rate qi>0 [lots/s]. Whenever the buffer i, in which there are accumulative queues, that is, xi(t)>0, is served by the server, the jobs leave the buffer i at a constant rate si>0 [lots/s]; and whenever the buffer i, in which there are no accumulative queues, that is, xi(t)=0, is served by the server, the jobs leave the buffer i at the constant rate qi. Both qi and si are called arriving rate and service rate of jobs in the buffer i, respectively, and qisi-1 is called the load of the buffer i. Whenever the server switches from serving the buffer i to the buffer j, there exists a nonzero setup time lij>0, i,j=1,…,n, i≠j  [s], during which the server is in idle.Figure 1
A switched server system withn buffers.In terms of above descriptions for switched server systems, the dynamics of the queues of jobs in buffers can be described by the following.Whenever the bufferi with xi(t)>0 is served by the server,(1)x˙t=q-siei.Whenever the buffer i with xi(t)=0 is served by the server,(2)x˙t=q-qiei.Whenever the server switches from serving one buffer to another one,(3)x˙t=q,where x(t)=[x1(t),…,xn(t)]T∈X, q=[q1,…,qn]T, and ei∈Rn is n-dimensional unit vector; that is, the ith element of ei equals one and other elements of ei are zero.In the subsequent parts, we assume that the total load of buffers satisfies(4)∑j=1nqjsj-1<1.Obviously, there is no equilibrium in the system described by (1), (2), and (3), and the periodic orbit depending on the scheduling policy is the steady-state of the system, which attracts other trajectories of the system. It was proved in [15] that the inequality (4) is the sufficient and necessary condition for the existence of stable scheduling policy for the system.


## 3. Stability of Scheduling Policy

In this section, stability analysis of two scheduling policies, that is, emptying and service-time-limited policies, is presented, where the service-time-limited policy admits service-time constraints on buffers based on emptying policy.


### 3.1. Emptying Policy

The emptying policy is described as follows:(1)
The buffers are served by the server in terms of any cyclic sequence, for example,1→2→⋯→n→1.(2)
Whenever the server switches from serving the bufferi to the buffer i+1 (i=1,…,n-1), there exists a nonzero setup time li,i+1>0; and whenever the server switches from serving the buffer n to the buffer 1, the setup time is ln1>0.(3)
When the bufferi∈{1,…,n} is being served, the service-time g~i(k) for the queue is given by(5)g~ik=xitkisi-qi,where tki, k=1,2,…, denotes the moment the server starts serving the buffer i within the kth cycle of the server, xi(tki) denotes the queue of jobs in the buffer i at the moment tki, and then xi(tki)(si-qi)-1 is the service-time for emptying the queue xi(tki) in the buffer i.From the statements in emptying policy, the server, with nonzero setup times, empties queues in buffers in terms of cyclic sequence. The following results hold.Theorem 1 (see [6]).
Consider the switched server system described by (1), (2), and (3) under emptying policy. Assume that the total load of buffers satisfies (4). Then, the following statements hold:(1)
There exists a unique periodic orbitxp(t)=[x1p(t),…,xnp(t)]T to the system, which is globally asymptotically stable with respect to the state space X.(2)
The periodC of the periodic orbit xp(t) is given by(6)C=L1-∑j=1nqjsj-1,whereL≜l12+⋯+ln-1,n+ln1 is the total idle time within one cycle of the server.(3)
For the periodic orbitxp(t), the service-time gi for the queue in the buffer i is given by(7)gi=qisi-1C.Remark 2.
The periodic orbit in Theorem1 is denoted by xp(t) in the succeeding parts. It is derived from (6) and (7) in Theorem 1, that the periodic orbit xp(t) can be uniquely determined by given system parameters, and satisfy C=∑j=1ngj+L. Importantly, from (7) in Theorem 1, the significance of the periodic orbit xp(t) is that within the period C and the total number of jobs arriving at the system is exactly equal to the total number of jobs leaving the system at service rates. Specifically, if the signalized intersection is modeled as a switched server system, inequality (4) is the undersaturated condition for signalized intersections, and the period C is the minimum signal cycle (refer to detailed discussions in [6]). Moreover, the consensus problems (i.e., states of the system can converge to a common value by local protocol) have become fundamental investigations in coordinated control of multiagent systems, due to extensive applications in engineering fields (e.g., refer to [18, 19]). In the sense of traffic control, the saturation level of some direction is defined as the ratio of total number of vehicles arriving at and leaving the intersection. From the significance of the periodic orbit xp(t), saturation levels are equal in different directions. Then, the emptying policy can realize the consensus of saturation levels in traffic control, implying the balance of traffic loads in different directions. Thus, the periodic orbit xp(t) has practical meanings in applications to traffic control.


### 3.2. Service-Time-Limited Policy

The emptying policy does not restrict service-time for buffers. However, the problem of constraints on service-time of buffers is of importance in practical applications, as stated in Introduction. In this subsection, the service-time-limited policy is presented based on emptying policy, which can be described by the following.The first two terms(1) and (2) are the same as those in descriptions of emptying policy; and (3) in emptying policy is replaced by the following:(3′)
When the bufferi∈{1,…,n} is being served, the service-time g~i(k) for the queue is given by(8)g~ik=g_i,Ifxitkisi-qi<g_ixitkisi-qi,Ifg_i≤xitkisi-qi≤g-ig-i,Ifxitkisi-qi>g-i,whereg_i≜gi-qisi-1Γi,min and g-i≜gi+qisi-1Γi,max are, respectively, the shortest and longest service-time assigned to the buffer i, where gi is given by (7), and both Γi,min and Γi,max are, respectively, called service-time lower-limit and upper-limit factors, satisfying 0<Γi,min<C and Γi,max>0.The information resulted fromC and gi of the periodic orbit xp(t) determined in Theorem 1 is utilized for the design of service-time-limited policy. From (8), the service-time g~i(k) of the buffer i within the kth cycle is, respectively, restricted by the shortest service-time g_i and longest service-time g-i. If the queue-emptying time xi(tki)(si-qi)-1 is less than g_i assigned to the buffer i, then g~i(k)=g_i. In this case, the serving process of the buffer i is as follows: the queue in the buffer i is first served at the service-rate si until the queue is emptied (refer to dynamics in (1)) and then the buffer i is served at the arriving-rate qi until the shortest service-time g_i ends (refer to dynamics in (2)). If the queue-emptying time xi(tki)(si-qi)-1 is more than g-i assigned to the buffer i, then g~i(k)=g-i. Otherwise, the queue xi(tki) in the buffer i is emptied, and the server switches to the next buffer.Consider the following inequality:(9)∑j=1nqjsj-1<min⁡minj∈1,…,nΓj,minmaxj∈1,…,nΓj,min,minj∈1,…,nΓj,maxmaxj∈1,…,nΓj,max.If Γi,min and Γi,max satisfy 0<Γ1,min=⋯=Γn,min<C and Γ1,max=⋯=Γn,max>0, then (9) is the same as (4).The following results hold for switched server systems under service-time-limited policy.Theorem 3.
Consider the switched server system described by (1), (2), and (3) under service-time-limited policy. Assume that the total load of buffers satisfies (9). Then, any solution to the system asymptotically converges to the periodic orbit xp(t).The proof of Theorem3 can be referred to the appendix. Furthermore, consider the following two special cases for service-time-limited policy:(C1)
Γ1,min=⋯=Γn,min=0,Γi,max>0, i=1,…,n; that is, g_i=gi,g-i>gi, i=1,…,n.(C2)
Γ1,min=⋯=Γn,min=C,Γi,max>0, i=1,…,n; that is, g_i=0,g-i>gi, i=1,…,n.Consider the following inequality:(10)∑j=1nqjsj-1<minj∈1,…,nΓj,maxmaxj∈1,…,nΓj,max.If Γ1,max=⋯=Γn,max>0 is satisfied, then (10) is the same as (4).Theorem 4.
Consider the switched server system described by (1), (2), and (3) under service-time-limited policy with factors satisfying (C1) or (C2). Assume that the total load of buffers satisfies (10). Then, any solution to the system asymptotically converges to the periodic orbit xp(t).Proof.
When applying service-time-limited policy with factors satisfying (C1), the statements in Theorem4 can be derived by setting Γi,min=0, i=1,…,n, in the proof of Theorem 3; and when applying service-time-limited policy with factors satisfying (C2), the statements in Theorem 4 can be derived by Cases 1 and 3 in the proof of Theorem 3. In above two cases, (9) in the proof of Theorem 3 is changed to (10).


## 3.1. Emptying Policy

The emptying policy is described as follows:(1)
The buffers are served by the server in terms of any cyclic sequence, for example,1→2→⋯→n→1.(2)
Whenever the server switches from serving the bufferi to the buffer i+1 (i=1,…,n-1), there exists a nonzero setup time li,i+1>0; and whenever the server switches from serving the buffer n to the buffer 1, the setup time is ln1>0.(3)
When the bufferi∈{1,…,n} is being served, the service-time g~i(k) for the queue is given by(5)g~ik=xitkisi-qi,where tki, k=1,2,…, denotes the moment the server starts serving the buffer i within the kth cycle of the server, xi(tki) denotes the queue of jobs in the buffer i at the moment tki, and then xi(tki)(si-qi)-1 is the service-time for emptying the queue xi(tki) in the buffer i.From the statements in emptying policy, the server, with nonzero setup times, empties queues in buffers in terms of cyclic sequence. The following results hold.Theorem 1 (see [6]).
Consider the switched server system described by (1), (2), and (3) under emptying policy. Assume that the total load of buffers satisfies (4). Then, the following statements hold:(1)
There exists a unique periodic orbitxp(t)=[x1p(t),…,xnp(t)]T to the system, which is globally asymptotically stable with respect to the state space X.(2)
The periodC of the periodic orbit xp(t) is given by(6)C=L1-∑j=1nqjsj-1,whereL≜l12+⋯+ln-1,n+ln1 is the total idle time within one cycle of the server.(3)
For the periodic orbitxp(t), the service-time gi for the queue in the buffer i is given by(7)gi=qisi-1C.Remark 2.
The periodic orbit in Theorem1 is denoted by xp(t) in the succeeding parts. It is derived from (6) and (7) in Theorem 1, that the periodic orbit xp(t) can be uniquely determined by given system parameters, and satisfy C=∑j=1ngj+L. Importantly, from (7) in Theorem 1, the significance of the periodic orbit xp(t) is that within the period C and the total number of jobs arriving at the system is exactly equal to the total number of jobs leaving the system at service rates. Specifically, if the signalized intersection is modeled as a switched server system, inequality (4) is the undersaturated condition for signalized intersections, and the period C is the minimum signal cycle (refer to detailed discussions in [6]). Moreover, the consensus problems (i.e., states of the system can converge to a common value by local protocol) have become fundamental investigations in coordinated control of multiagent systems, due to extensive applications in engineering fields (e.g., refer to [18, 19]). In the sense of traffic control, the saturation level of some direction is defined as the ratio of total number of vehicles arriving at and leaving the intersection. From the significance of the periodic orbit xp(t), saturation levels are equal in different directions. Then, the emptying policy can realize the consensus of saturation levels in traffic control, implying the balance of traffic loads in different directions. Thus, the periodic orbit xp(t) has practical meanings in applications to traffic control.


## 3.2. Service-Time-Limited Policy

The emptying policy does not restrict service-time for buffers. However, the problem of constraints on service-time of buffers is of importance in practical applications, as stated in Introduction. In this subsection, the service-time-limited policy is presented based on emptying policy, which can be described by the following.The first two terms(1) and (2) are the same as those in descriptions of emptying policy; and (3) in emptying policy is replaced by the following:(3′)
When the bufferi∈{1,…,n} is being served, the service-time g~i(k) for the queue is given by(8)g~ik=g_i,Ifxitkisi-qi<g_ixitkisi-qi,Ifg_i≤xitkisi-qi≤g-ig-i,Ifxitkisi-qi>g-i,whereg_i≜gi-qisi-1Γi,min and g-i≜gi+qisi-1Γi,max are, respectively, the shortest and longest service-time assigned to the buffer i, where gi is given by (7), and both Γi,min and Γi,max are, respectively, called service-time lower-limit and upper-limit factors, satisfying 0<Γi,min<C and Γi,max>0.The information resulted fromC and gi of the periodic orbit xp(t) determined in Theorem 1 is utilized for the design of service-time-limited policy. From (8), the service-time g~i(k) of the buffer i within the kth cycle is, respectively, restricted by the shortest service-time g_i and longest service-time g-i. If the queue-emptying time xi(tki)(si-qi)-1 is less than g_i assigned to the buffer i, then g~i(k)=g_i. In this case, the serving process of the buffer i is as follows: the queue in the buffer i is first served at the service-rate si until the queue is emptied (refer to dynamics in (1)) and then the buffer i is served at the arriving-rate qi until the shortest service-time g_i ends (refer to dynamics in (2)). If the queue-emptying time xi(tki)(si-qi)-1 is more than g-i assigned to the buffer i, then g~i(k)=g-i. Otherwise, the queue xi(tki) in the buffer i is emptied, and the server switches to the next buffer.Consider the following inequality:(9)∑j=1nqjsj-1<min⁡minj∈1,…,nΓj,minmaxj∈1,…,nΓj,min,minj∈1,…,nΓj,maxmaxj∈1,…,nΓj,max.If Γi,min and Γi,max satisfy 0<Γ1,min=⋯=Γn,min<C and Γ1,max=⋯=Γn,max>0, then (9) is the same as (4).The following results hold for switched server systems under service-time-limited policy.Theorem 3.
Consider the switched server system described by (1), (2), and (3) under service-time-limited policy. Assume that the total load of buffers satisfies (9). Then, any solution to the system asymptotically converges to the periodic orbit xp(t).The proof of Theorem3 can be referred to the appendix. Furthermore, consider the following two special cases for service-time-limited policy:(C1)
Γ1,min=⋯=Γn,min=0,Γi,max>0, i=1,…,n; that is, g_i=gi,g-i>gi, i=1,…,n.(C2)
Γ1,min=⋯=Γn,min=C,Γi,max>0, i=1,…,n; that is, g_i=0,g-i>gi, i=1,…,n.Consider the following inequality:(10)∑j=1nqjsj-1<minj∈1,…,nΓj,maxmaxj∈1,…,nΓj,max.If Γ1,max=⋯=Γn,max>0 is satisfied, then (10) is the same as (4).Theorem 4.
Consider the switched server system described by (1), (2), and (3) under service-time-limited policy with factors satisfying (C1) or (C2). Assume that the total load of buffers satisfies (10). Then, any solution to the system asymptotically converges to the periodic orbit xp(t).Proof.
When applying service-time-limited policy with factors satisfying (C1), the statements in Theorem4 can be derived by setting Γi,min=0, i=1,…,n, in the proof of Theorem 3; and when applying service-time-limited policy with factors satisfying (C2), the statements in Theorem 4 can be derived by Cases 1 and 3 in the proof of Theorem 3. In above two cases, (9) in the proof of Theorem 3 is changed to (10).


## 4. Feasibility of Service-Time-Limited Policy

Based on emptying policy, service-time-limited policy admits service-time constraints on buffers by introducing service-time lower-limit and upper-limit factorsΓi,min and Γi,max,i=1,…,n, but does not bring constraints on the buffer capacity. However, the buffer capacity is finite for most of practical problems. Thus, we furthermore consider the execution of service-time-limited policy in case of finite buffer capacity.Letximax>0,i=1,…,n, be the capacity of the buffer i, defined as the maximum queue of jobs that the buffer i can accommodate. Then, theadmissible regionM⊂X of the system is denoted as M≜[0,x1max]×⋯×[0,xnmax].It is derived, from the significance of the periodic orbitxp(t), that the maximum queue of jobs in the buffer i is given by qi(C-gi) within the period C. Assume that the periodic orbit xp(t) lies inside the admissible region M; that is,(11)ximax>qiC-gi,i=1,…,n.Definition 5.
Consider the switched server system described by (1), (2), and (3) under service-time-limited policy. The state x0∈M is calledfeasible if for the given service-time lower-limit factors Γi,minf,i=1,…,n, there exist service-time upper-limit factors Γi,maxc>0,i=1,…,n, such that the solution x(t)=[x1(t),…,xn(t)]T originating in x0 asymptotically converges to the periodic orbit xp(t) and moreover satisfies x(t)∈M,∀t≥0.
Furthermore, it is deduced from (11) that there must exist service-time upper-limit factors Γi,max>0, i=1,…,n, satisfying the following inequalities:(12)ximax≥qiC-gi+∑j≠iqjsj-1Γj,max=qi∑j≠igj+qjsj-1Γj,max+L,i=1,…,n.Inequalities (12) indicate that when the queue of jobs in the buffer i is emptied, the queue of jobs in the buffer i does not exceed the buffer capacity after one cycle of the server. The factors Γi,max,i=1,…,n, satisfying (12) are noted as Γi,maxc,i=1,…,n, in the following parts.Theorem 6.
Consider the switched server system described by (1), (2), and (3) under service-time-limited policy with given Γi,minf and Γi,maxc>0,i=1,…,n. Assume that the total load of buffers satisfies (9) (or (10) if all Γi,minf,i=1,…,n satisfy (C1) or (C2)), and the state x0∈M has the property that the solution x(t)=[x1(t),…,xn(t)]T originating in the state x0 satisfies the condition [x1(t11),…,xn(t1n)]T∈M, where t1i is the moment the server starts serving the buffer i within the first cycle of the server. Then, the state x0∈M is feasible with respect to Γi,maxc>0,i=1,…,n.The proof of Theorem6 can be referred to the appendix. It is derived from Theorem 6 that the checking condition for feasibility of the state is that the corresponding solution does not exceed the buffer capacity within the first cycle of the server with given Γi,minf and Γi,maxc,i=1,…,n. Accordingly, the feasible region X0[Γi,minf,Γi,maxc]⊆M, that is, all of feasible states with respect to Γi,minf and Γi,maxc,i=1,…,n, can be obtained from the checking condition for feasibility of the state. Specifically, analytic expression of feasible region X0[Γi,minf,Γi,maxc] for switched server systems with two buffers can be easily determined as follows:(1)
If0≤Γi,minf<C, i=1,2, then X0[Γi,minf,Γi,maxc]=X01∪X02∪X03, where X0i,i=1,2,3, are, respectively, given by(13)X01=x0∈M:x10s1-q1-1<g1-q1s1-1Γ1,minf,x20+q2g1-q1s1-1Γ1,minf+l12≤x2max;X02=x0∈M:g1-q1s1-1Γ1,minf≤x10s1-q1-1≤g1+q1s1-1Γ1,maxc,x20+q2x10s1-q1-1+l12≤x2max;X03=x0∈M:x10s1-q1-1>g1+q1s1-1Γ1,maxc,x20+q2g1+q1s1-1Γ1,maxc+l12≤x2max.(2)
IfΓi,minf=C, i=1,2, then X0[Γi,minf,Γi,maxc]=X01∪X02, where X0i,i=1,2, are respectively given by(14)X01=x0∈M:x10s1-q1-1≤g1+q1s1-1Γ1,maxc,x20+q2x10s1-q1-1+l12≤x2max;X02=x0∈M:x10s1-q1-1>g1+q1s1-1Γ1,maxc,x20+q2g1+q1s1-1Γ1,maxc+l12≤x2max.From Theorem6, feasibility of the state depends on choices of factors Γi,minf and Γi,maxc,i=1,…,n. However, infeasibility of the state with respect to some given factors Γi,minf and Γi,maxc,i=1,…,n, does not imply inexistence of factors ensuring the state is feasible. Furthermore, we consider the problem of how to solve factors Γi,maxc,i=1,…,n, such that the given state is feasible with given Γi,minf,i=1,…,n.If service-time-limited policy is applied with givenΓi,minf=0 or 0<Γi,minf<C,i=1,…,n, in terms of the checking condition for feasibility of states in Theorem 6, the given state x0=[x1(0),…,xn(0)]T∈M is infeasible if at least one of the following inequalities holds:(15)xi0>ximax-qi∑j=1i-1gj-qjsj-1Γj,min+∑j=1i-1lj,j+1,i=2,…,n.The significance of (15) is that the queue in the buffer i≥2 exceeds the buffer capacity even if all of buffers j,j=1,…,i-1 are served with the shortest service-time within the first cycle of the server. Furthermore, a sufficient condition is given for determining Γi,maxc,i=1,…,n, ensuring the given state x0∈M is feasible.Proposition 7.
Consider the switched server system described by (1), (2), and (3) under service-time-limited policy with given Γi,minf,i=1,…,n. For the given state x0∈M, if the set Ω(x0) of factors [Γ1,max,…,Γn,max]T given by (16) is nonempty and there exists [Γ1,maxc,…,Γn,maxc]T∈Ω(x0), such that the total load of buffers satisfies (9) (or (10) if all Γi,minf,i=1,…,n, satisfy (C1) or (C2)), then the given state x0∈M is feasible with respect to [Γ1,maxc,…,Γn,maxc]T:(16)a∑j≠1qjsj-1Γj,max≤x1maxq1-∑j≠1gj-L⋮∑j≠nqjsj-1Γj,max≤xnmaxqn-∑j≠ngj-L.bq1s1-1Γ1,max≤x2max-x20q2-g1-l12⋮∑j=1n-1qjsj-1Γj,max≤xnmax-xn0qn-∑j=1n-1gj-∑j=1n-1lj,j+1c0<Γ1,max≤Γ1,max∗⋮0<Γn,max≤Γn,max.∗Proof.
Inequalities (a) in (16) imply that (12) holds; and we can derive from (b) in (16) that(17)x2t12≤x20+q2g1+q1s1-1Γ1,max+l12≤x2max⋮xnt1n≤xn0+qn∑j=1n-1gj+qjsj-1Γj,max+∑j=1n-1lj,j+1≤xnmax,which indicates that the solution does not exceed the buffer capacity within the first cycle of the server. Furthermore, Γi,max∗,i=1,…,n, in (c) are the maximum allowable service-time upper-limit factors. Thus, from Theorem 6, the given state x0∈M is feasible.


## 5. Conclusions

For most of real-world problems about queuing systems, service-times and queues of buffers must be constrained. In this paper, inspired by practical problems in traffic control, the service-time-limited policy is proposed, which is the extension to emptying policy. Moreover, the execution of service-time-limited policy in the case of finite buffer capacities is considered, and the notion of feasibility of states under service-time-limited policy is presented. Furthermore, based on the checking condition for feasibility of states (i.e., the solution does not exceed buffer capacities within the first cycle of the server), a sufficient condition for determining feasibility of states is given.The scheduling policy proposed in this paper admits taking into consideration service-time and queue constraints on buffers by the introduction of the notion of feasibility of states, and service-time upper-limit factors for the feasible state can be solved by testing the nonempty setΩ(x0). Thus, our results can be applied to traffic control as stated in the Introduction, especially in critical saturation case; for example, the length of queues of vehicles on incoming links may be larger, with lower traffic loads satisfying (4). Signal control of T-shape intersection is typical application of our results, which can be referred to [6] for details.From views of traffic control, the server may serve multiple nonconflicting flows, which is our further research extension of results in the paper.



---

*Source: 347931-2015-06-23.xml*