# Delay-Optimal Scheduling for Two-Hop Relay Networks with Randomly Varying Connectivity: Join the Shortest Queue-Longest Connected Queue Policy

Authors: Seung Jun Baek; Joon-Sang Park
Journal: Mathematical Problems in Engineering
 (2017)

---

## Abstract

We consider a scheduling problem for a two-hop queueing network where the queues have randomly varying connectivity. Customers arrive at the source queue and are later routed to multiple relay queues. A relay queue can be served only if it is in connected state, and the state changes randomly over time. The source queue and relay queues are served in a time-sharing manner; that is, only one customer can be served at any instant. We propose Join the Shortest Queue-Longest Connected Queue (JSQ-LCQ) policy as follows: (1) if there exist nonempty relay queues in connected state, serve the longest queue among them; (2) if there are no relay queues to serve, route a customer from the source queue to the shortest relay queue. For symmetric systems in which the connectivity has symmetric statistics across the relay queues, we show that JSQ-LCQ is strongly optimal, that is, minimizes the delay in the stochastic ordering sense. We use stochastic coupling and show that the systems under coupling exist in two distinct phases, due to dynamic interactions among source and relay queues. By careful construction of coupling in both phases, we establish the stochastic dominance in delay between JSQ-LCQ and any arbitrary policy.


---

## Body

## 1. Introduction

We consider a scheduling problem in queueing systems with random connectivity of servers. For example, in wireless communication systems, the communication channel may randomly become unavailable for data transmissions due to fluctuation of channel quality over time. To cover areas with poor channel quality, relay networks have been widely adopted [1–3] in which there exist relay nodes responsible for relaying data packets in a hop-by-hop manner to destination. In this paper, we investigate the minimum delay scheduling in two-hop relay networks with random connectivity. Delay-optimal scheduling in multihop networks with random connectivity is an open problem and has eluded researchers even for very simple models. Low-latency communications have recently attracted much attention in upcoming 5G (5th-generation) communication networks [4]. There exist many 5G applications which require extremely low latency, for example, autonomous vehicles, remote surgery, and automated factories.We consider a queueing model depicted in Figure1. The system consists of one source queue (SQ) and n relay queues (RQs). We consider a time-slotted system, where a customer arrives at the SQ with probability λ at each time slot. The customers at the SQ are routed to one of the RQs selected by the scheduler. Each RQ is associated with a service state called connectivity: the scheduler can serve a RQ only if the RQ is in connected state. The connectivity of the RQs changes randomly over time. Customers are routed or served in a time-sharing manner; at a given time slot, either a customer is routed from the SQ to a RQ, or a customer is served from a RQ in connected state and exits the system. This is a common model for relay networks inhalf-duplex operation; that is, the queues in adjacent hops cannot be served simultaneously.Figure 1
Two-hop queueing network model. The system consists of one source queue (SQ) andn relay queues (RQs). Only one customer can be served at any instant (half duplex). Binary variable Ci represents the connectivity of the ith RQ, i=1,…,n.Potential engineering applications of our queueing model include wireless relay networks. In 5G communication systems, wireless relays are expected to be widely used to enhance capacity and coverage of the network [5]. In such networks, data packets can be delivered to a mobile user throughmultiple relay devices, for example, as in device-to-device (D2D) communications [6, 7]. Our model is applicable to downlink packet transmissions in such next-generation cellular networks as follows. In the downlink scenario, we regard the SQ as the queue located at the base station (BS). Also a RQ is a queue located at a relay node (RN), and the customers correspond to data packets. Suppose the BS intends to send a stream of packets to a mobile user, say user i, which is located at cell edge with poor channel quality. Instead of transmitting packets directly to user i, which is likely to fail most of the time, the BS chooses to transmit packets to one of the multiple RNs. The RNs typically have better channels to user i and later transmit the temporarily stored packets to user i. Each channel from a RN to user i may undergo fading due to, for example, the mobility of user i. As a result, the channel between a RQ and user i may randomly switch between “on” and “off” state; in our model, this can be viewed as the RQs being randomly “connected” to user i over time. A related technique of utilizing multiple relays over time-varying channels, called cooperative relaying or opportunistic relaying, has been studied extensively [8–13]. Meanwhile, our model is applicable to the uplink transmission for cellular networks as well. In the uplink scenario, a user node becomes the source queue and utilizes multiple relay nodes equipped with queues. The packets are eventually relayed to the base station, which is the destination node, by the relay nodes.The time-sharing service of customers between SQ and RQs is analogous to half-duplex transmissions of packets in wireless relay networks, that is, only either BS or RN can transmit at a time slot. While full-duplex relays are recently under investigation [14, 15], half-duplex relays are still widely used [14] since they are simple to design and cost-effective. In addition, the connectivity from the SQ to RQs is assumed to be always in connected state in our model. A common architecture for cellular networks with relays proposes using nodes dedicated for relaying called Relay Stations (RSs). The RSs are typically installed in fixed locations which are in line-of-sight (LOS) to the BS [16]. Therefore, the channel quality between the BS and a RS is typically very high. Also, in D2D networks in which mobile nodes are selected to act as RNs, it makes sense to select mobiles which have good channels to the BS in the first place. Such a high quality channel between the BS and RSs can be modelled as being always in “on” state, which is assumed in our model.We introduce a policy called Join the Shortest Queue-Longest Connected Queue (JSQ-LCQ).Definition 1.
The JSQ-LCQ policy is defined as follows:(1)
If there exist RQs which are nonempty and connected, serve a customer from thelongest queue among the connected RQs.(2)
If there is no RQ to serve, route a customer from the SQ to theshortest queue among the RQs.
It is observed that the JSQ-LCQ is a simple and greedy policy with tehe following properties:(i)
JSQ-LCQ prioritizes serving the RQs over serving the SQ. If there is any chance to serve a RQ, it will do so.(ii)
Among the connected RQs, it will serve the longest one. This is an attempt to make the RQs as “balanced” as possible.(iii)
When JSQ-LCQ routes a customer to RQ, it chooses the shortest RQ. Again the policy attempts to balance the RQs.
JSQ-LCQ focuses on balancing queues during the service and routing so as to maximize the “opportunism” of time-varying connectivity, that is, so that as many nonempty queues as possible can observe the connected state. LCQ is inspired by the policy in [17] with the same name. In the single-hop case where the queues are served in parallel, the LCQ policy is delay-optimal for the symmetric system; that is, connectivity and arrival processes have identical statistics across the queues [17]. Meanwhile, in a two-hop network, if all the queues are in connected state and are served in parallel without time-sharing constraints, it is well-known that the JSQ policy is delay-optimal [18]. However, two-hop networks with the time-sharing constraint and random connectivity are considered in our problem. Two-hop networks are very different from one-hop networks, since the customers served in the first hop do not leave but stay in the system, waiting to be served; moreover, the service availability randomly changes over time. The question is as follows: does there exist a delay-optimal policy for such two-hop networks? If so, can we find the optimal policy? In this paper, we answer these questions in the affirmative as follows. Assume a symmetric system; that is, the connectivity has a symmetric distribution across the RQs. Our claim is thatJSQ-LCQ is optimal in a strong sense, that is, in the stochastic ordering sense.In this paper, we establish the delay optimality of a two-hop network model with time-varying connectivity. We show that JSQ-LCQ policy is strongly optimal, such that it minimizes the number of customers in the system in the stochastic ordering sense. We use the coupling argument to show that the queue length processes under JSQ-LCQ is stochastically dominated by any other feasible policy. However, unlike typical coupling, we show that the coupled systems can exist intwo distinct phases. Such a system behaviour is attributable to dynamic interactions among random connectivity, queue states, and the time-sharing constraint of service. The system phases are characterized in terms of certain relations between the queue states of JSQ-LCQ and another arbitrary policy in comparison. Specifically, the phases are defined based on (i) the difference in the source queue lengths and (ii) theweak majorization relations between the vectors of relay queue lengths, of the compared policies. We carefully develop the coupling argument for these phases, which leads to the stochastic dominance of the total number of customers in the system. To our knowledge, delay optimality for two-hop relay networks, even for simple channel models, has not been well-known yet. Considering that there exist few works on delay-optimal scheduling, we believe that our work opens a new possibility for deeper understanding of the problem. In summary, the key contributions of our work are listed as follows: this paper(i)
proposes JSQ-LCQ and proves the delay optimality of the algorithm for two-hop relay networks with time-varying connectivity, which is of theoretical significance;(ii)
introduces a novel coupling technique associated with the transition of system phases defined in terms of the majorization relations among source and relay queues.This paper is organized as follows. We present related works in Section2. In Section 3, we describe the system model. The optimality of JSQ-LCQ is proved in Section 4. Simulation results are reported in Section 5. Section 6 concludes the paper.


## 2. Related Work

Delay-optimal scheduling is not only important from an engineering perspective but also of theoretical and mathematical interest. Delay optimality is notoriously hard to achieve with time-varying service capacity, and there exist only a few results which we review below. In their seminal work [17], Tassiulas and Ephremides considered a single-hop scheduling of parallel queues with time-varying connectivity, that is, with “on-off” channels. They proposed LCQ and showed that, under the symmetry assumptions, LCQ is delay-optimal in the stochastic ordering sense. Yeh and Cohen [19] considered single-hop scheduling over multiaccess fading channels when the capacity region of the users’ service has a polymatroid structure [20]. They proposed Longest Queue Highest Possible Rate (LQHPR) policy which successively allocates higher rates to longer queues. LQHPR is shown to be delay-optimal when the arrival statistics and capacity region are symmetric across users. For multihop case, authors of [21] consider scheduling tandem queues with interference constraints; that is, the adjacent queues cannot be served simultaneously. In their model, queues are always in connected state. The delay-optimal policy is obtained by serving the nonempty queue closest to the destination and then serving the next nonempty and noninterfering queue closest to the destination, which is iteratively done over the entire network. Interestingly, we observe that JSQ-LCQ policy has a similar principle to the policy in [21]: JSQ-LCQ prioritizes serving the RQs (“closer” to the destination) whenever possible, and the SQ has the lower priority. However, it is highly nontrivial to extend the optimality result to networks with time-varying connectivity like our model. Recently, Cui et al. [22] studied a two-hop network with “on-off” channels. However, there exists only one relay queue in their model, and the authors propose a policy which is asymptotically optimal using a dynamic programming (DP) approach. We observe that delay-optimal scheduling has been found only for simple models, for example, single-hop network with symmetric service capacity. To our knowledge, even with symmetric connectivity, there is no known delay-optimal scheduling for two-hop relay networks involving multiple relay queues under the time-sharing (half-duplex) constraint.Our scheme can be regarded as a relay selection and scheduling scheme for two-hop cooperative relay networks, that is, a cooperative transmission utilizing multiple RNs, for example, [8–10, 23, 24]. Bletsas et al. [8] consider a relay selection algorithm for two-hop cooperative relay networks where there exist multiple RNs for a source-destination pair. The “best” relay is chosen based on either the minimum or harmonic mean of the instantaneous channel gains of source-relay (S-R) and relay-destination (R-D) links. A time slot is divided by half, and S-R transmission occurs at the first half of the time slot, and R-D transmission occurs at the second half. Cui et al. [9] considered two-hop relay networks with multiple source, relay, and destination nodes. Their scheme selects RNs in an opportunistic manner, that is, based on favorable Signal-to-Noise-Ratio (SNR) among multiple S-R and R-D pairs. In [23], the authors considered a model in which the RNs have buffers where the transmission occurs over two phases (time slots) as follows. In the first time slot, a S-R pair with the best channel is scheduled, and the transmitted packet is stored in the selected relay for later transmission. In the second time slot, the best R-D pair is scheduled in which the RN transmits previously stored data. Note these works focus on maximizing transmission rates or throughput; however they do not consider the delay issue. For example, the queues are assumed to be infinitely backlogged in the aforementioned works. Also the links are scheduled in a fixed manner; for example, the selected S-R and R-D pairs are scheduled to transmit over two consecutive time slots. In contrast, our work not only considers relay selection but also link scheduling. For example, when our scheme selects the shortest RQ to route (JSQ), it can be regarded as selecting “best” relay. In other words, by balancing the RQs, the policy will enhance opportunism by making as many nonempty RQs as possible observe the connected state. In a general approach to ensure delay optimality for multihop cooperative networks, one needs a problem formulation via Markov Decision Process (MDP), for example, [25, 26]. To achieve delay optimality, one requires solving infinite time horizon MDP. However, it is difficult to apply MDP-based policies to large systems due to “curse of dimensionality.” Wang et al. [11] considered queue-based cooperative relaying by approximately solving MDP using a stochastic learning approach. The authors proposed a distributed online algorithm which is shown to be asymptotically optimal under the heavy-traffic limit.In contrast to delay optimality,throughput optimal policies are relatively well-known; a policy is said to be throughput optimal if the policy makes a queueing system stable whenever stability is feasible. Tassiulas and Ephremides [27] showed that the routing and scheduling underbackpressure algorithm based on backlog differentials are throughput optimal for multihop networks with link constraints. However, backpressure algorithm only ensures throughput optimality but does not provide any guarantee on achievable delay. A number of enhancements to backpressure algorithm have been proposed to address the issue of delay performance [28–34]. Backpressure algorithm often suffers from long delays in large multihop networks. This is because the algorithm explores all possible paths from source to destination. The routing based solely on backpressure may create a long path resulting in large delays. To alleviate this problem, in [31, 32] an algorithm is proposed which adaptively exploits short paths, while maintaining the stabilizing property of backpressure algorithm. Specifically, the algorithm uses shortest paths under the light traffic but utilizes longer paths with increasing traffic to ensure stability. Practical implementations of backpressure algorithm are proposed in [35–37]. Note that the aforementioned works considered throughput optimal schemes; however, throughput optimality is a relatively weak form of performance as compared to delay optimality.


## 3. System Model

Consider a time-slotted system consisting of one SQ andn RQs. Only one customer can be served at a time slot: either a customer is routed from the SQ to one of the RQs, or a customer is served at one of the RQs. A customer can be served from a RQ only if the RQ is in connected state. The service at the RQs has randomly varying connectivity. A RQ is connected with probability p, and the connectivity is independent over time slots and across the RQs (similar to [17], we do not need the independence of connectivity across the RQs. We only need the assumption that the joint distribution of connectivity is symmetric across the RQs, under which our optimality result will hold as well. However, the independence assumption will simplify the arguments on, e.g., stability and stochastic coupling, which we discuss later). The arrival of a customer at the SQ is i.i.d. over time slots with probability λ.The number of customers at SQ (resp., RQs) at timet is denoted by X(t)∈Z+ (resp., Y(t)=(Y1(t),…,Yn(t))∈Z+n). Let C(t)=(C1(t),…,Cn(t))∈0,1n be a random process indicating the connectivity at the RQs. Specifically, C1(t),…,Cn(t) are i.i.d. Bernoulli random variables with parameter p. Denote the arrival process by A(t)∈0,1. The state of the system at time t is denoted by S(t)≔(A(t),C(t),X(t),Y(t)). We define the set ofactions which a policy can take at a given timeslot. An action takes a value from the set of symbols defined by A≔I,R1,R2,…,Rn,S1,S2,…,Sn. Symbol I stands for the policy being idle, Ri stands for routing a customer from the SQ to the ith RQ, and Si represents serving a customer from the ith RQ. Policy π(t) is defined as a scheduling decision at time t which takes a value from A. Note that π(t) is based on the entire history of scheduling actions π(t),s<t and system states (S(t),s≤t). The SQ and RQs evolve as follows: (1)Xt+1=Xt-1πt∈R1,…,Rn++At,Yit+1=Yit-1πt=Si·Cit++1πt=Rifor i=1,…,n, where 1(·) is the indicator function and [x]+≔max(x,0).Next we consider the condition for stability. The arrival rate to the system isλ. The service rate from the SQ to RQs is one per time slot, whereas the overall service rate at the RQs is 1-(1-p)n on average. Hence the utilization at the first and second hops is given by λ and λ/{1-(1-p)n}, respectively. Due to the time-sharing constraint, the combined utilization must be less than 1; that is, (2)1>λ+λ1-1-pn⟹λ<1-1-pn2-1-pn.It is known that throughput optimal policies such as backpressure algorithm [27] can stabilize the system under condition (2). Later, we will show that JSQ-LCQ is delay optimal; that is, the average number of customers in the system under JSQ-LCQ is no more than that under any other policy including backpressure algorithm. Thus, JSQ-LCQ is a stable policy under condition (2); note that delay optimality implies throughput optimality. Due to the memoryless property of connectivity, it suffices to consider π(t) which is astatic state-feedback policy; that is, there exists optimal π(t) which bases its decision only on the present state of the system. Under such π(t), queue state process (X(t),Y(t)), t=0,1,2,…, forms a Markov chain; if π(t) is throughput optimal, the Markov chain is stationary and ergodic under stability condition (2).


## 4. Delay Optimality of JSQ-LCQ

In this section, we will prove the delay optimality of JSQ-LCQ. We will show that JSQ-LCQ is optimal in the stochastic ordering sense which we define as follows. For two random variablesA and B in R, let A~B denote that they have the identical distribution.Definition 2 (see [38]).
LetU and V be random variables in R. U is said to be stochastically smaller than V, denoted by U≤stV, if there exist random variables U′ and V′ such that (1)
U~U′;(2)
V~V′;(3)
U′≤V′ a.s.
Note thatU≤stV is equivalent to stating that, for any increasing function f:R→R,(3)PfU>z≤PfV>z,∀t≥0.For vector x∈Rn, let x≔∑i=1nxi. We state the main theorem as follows.Theorem 3.
LetX(t) and Y(t) denote the queue length processes of the SQ and RQs under JSQ-LCQ. Also let X~(t) and Y~(t) denote the length of the SQ and RQs under an arbitrary policy. Suppose (X(t),Y(t)) and (X~(t),Y~(t)) are in an arbitrary initial state (x0,y0) at time t=0. Then, for t≥0,(4)Xt+Yt≤stX~t+Y~t.Theorem3 states that the number of customers in the system under JSQ-LCQ is stochastically smaller than that under any other policy. By Little’s law, the theorem implies that JSQ-LCQ will minimize the delay in the stochastic ordering sense. Theorem 3 is a much stronger statement than, for example, achieving the minimum average delay, as we can see from (3). To prove Theorem 3, we will use stochastic coupling arguments leveraging the forward induction technique [18]. Specifically, we show that one can construct the sample paths of queue length processes under JSQ-LCQ and another arbitrary policy by properly coupling the arrival and connectivity processes so that (4) holds.


### 4.1. Coupling

Letπ(t) denote the JSQ-LCQ policy. Let π~(t) denote another arbitrary policy. (X(t),Y(t)) (resp., (X~(t),Y~(t)) in Theorem 3 denote the queue length processes under π(t) (resp., π~(t)). In the following we use forward induction [18, Section 8.3] by coupling the connectivity of the RQs under π(t) and π~(t) as follows. Suppose the process of RQs under π(t), or Y(t), has the connectivity given by C(t)=(c1,…,cn) at time t. We will couple C(t) with the connectivity variables for Y~(t) as follows: if the ith longest queue of Y(t) has the connectivity c∈{0,1}, then let the ith longest queue of Y~(t) have the same connectivity c, for i=1,…,n. In other words, Y[i](t) and Y~[i](t) see the same connectivity variable by the coupling for i=1,…,n. This coupling will not change the marginal distributions of the connectivity seen by Y(t) and Y~(t) as is required in (1) and (2) of Definition 2 (see also [18, Proposition 8.3.2]), because this coupling involves simply permuting the connectivity variables across the RQs. Specifically, the connectivity variables are i.i.d. across the RQs and thus their joint distribution is symmetric or invariant to permutation; that is,(5)PC1t=c1,…,Cnt=cn=PC1t=cP1,…,Cnt=cPn,where P is an arbitrary permutation of the index set 1,2,…,n. Next, the arrivals to the system are coupled as follows: if an arrival occurs at the SQ under π(t), then let there be an arrival at the SQ under π~(t). In the rest of the proof, we will assume that the queue length processes under π and π~ are coupled in the above fashion.Unlike previous works on single-hop scheduling, the coupling argument in our problem must consider dynamic interactions among queues, connectivity, and the half-duplex constraint, as follows. JSQ-LCQ prioritizes serving the RQs; that is, it will serve the RQs whenever possible, in a balanced manner. Thus, the RQs will tend to be short under JSQ-LCQ. This means that, due to half-duplex operation, the SQ will get relatively long. However, if many RQs become empty due to prioritized service, the number of nonempty and connected RQs will become small. Hence JSQ-LCQ may be forced to frequently route customers to the RQs, in a balanced manner, in which case the RQs will build up. However, as the number of nonempty RQs grows, there will be many nonempty and connected RQs, and JSQ-LCQ will again begin to actively serve the RQs. Thus, we observe that the system exhibits some cyclic patterns in the services and evolution of the queue states.Based on this observation, we identify that there existtwo distinct phases in our coupling process. In the first phase, the RQs tend to be short and the SQ tends to be long under JSQ-LCQ. In the second phase, the SQ tends to be short and RQs tend to be long. The first phase is calledweak majorization (WM) phase, and the second phase is calledwater-filling majorization (WFM) phase. We will explain the phases in more detail in the subsequent sections. We show that, by introducing the concept of phases, we are able to handle the aforementioned patterns in system behaviour. Specifically, under proper coupling, we show that the system remains in either of the two phases or makes the transition to the other phase. Later we will show that this construction implies the desired stochastic majorization given by (4).


### 4.2. Weak Majorization (WM) Phase

For vectorx∈Rn, let xk denote the kth longest entry of x; that is, x[1]≥⋯≥x[n].Definition 4.
For two vectorsx,y∈Rn, if(6)∑k=1jxk≤∑k=1jyk,j=1,…,n,x is said to beweakly majorized by y, which is denoted as x≺wy.
Recall that(X(t),Y(t)) (resp., (X~(t),Y~(t))) is the queue length processes under JSQ-LCQ or π (resp., an arbitrary policy or π~).Definition 5.
We say the system is in weak majorization (WM) phase if(1)
the following relation holds:(7)0≤Xt-X~t≤12Y~t-Yt;equivalently, there exists integerδ≥0 such that(8)Xt-X~t=δ,Y~t-Yt≥2δ;(2)
Y(t) is weakly majorized by Y~(t); that is,(9)Yt≺wY~t.We discuss the implication of the WM phase. Firstly, JSQ-LCQ will greedily serve the RQs whenever possible, making the overall length of RQs small. By contrast, the customers that arrived at the SQ will have to wait relatively long due to the half-duplex constraint. Condition (8) represents these properties; that is, the SQ under JSQ-LCQ is relatively long, and the sum-length of the RQs is relatively small. In addition, if we rearrange the inequality on the right of condition (8),(10)Yt+δ≤Y~t-δ,which is interpreted as follows. There are an excess of δ customers backlogged at the SQ under JSQ-LCQ. Thus, if we compare only the SQs, JSQ-LCQ appears to be δ customers “behind” π~. Now suppose JSQ-LCQ adds these δ customers to Y(t) by serving the SQ for δ times to “catch up” π~, which takes δ time slots. During this time interval, π~ can serve δ customers from the RQs to push the customers out of the system as much as possible, in which case Y~(t) is reduced by δ. However, (10) shows that, even after such actions by π~, the number of customers under JSQ-LCQ still is no more than that under π~. Thus, condition (8) indicates that JSQ-LCQ is in fact sufficiently “ahead” of π~ in WM phase. Secondly, not only will the RQs be short, but also they are well “balanced” due to JSQ-routing and LCQ-scheduling principles. Condition (9) represents this property. An example of the system in WM phase is depicted in Figure 2.Figure 2
Example of the system in weak majorization (WM) phase. The figure in the above (resp., below) shows the queues under policy JSQ-LCQ orπ (resp., π~). The SQ under π is longer than that under π~; that is, X(t)=2 and X~(t)=1. In addition, the number of customers in the RQs satisfies the following: we have Y~(t)-Y(t)=5-3=2≥2{X(t)-X~(t)}, which satisfies (8). Next, we have Y(t)≺wY~(t) satisfying (9); that is, the RQs under JSQ-LCQ are “better balanced” than those under π~.However, the system may get out of WM phase if most of the RQs are emptied out, after which JSQ-LCQ will mainly serve the SQ. Consequently, the RQs will become relatively long but the SQ will become relatively short, in contrast to WM phase. In that case, the system makes the transition to WFM phase, which we will define and discuss in detail in Section4.3.To use forward induction we will show that if the system is in WM phase at timet, under a proper coupling of connectivity and arrivals, the system will either remain in WM phase or make the transition to WFM phase at time t+1. Later, we will make a similar coupling argument for the system in WFM phase: a system in WFM phase at time t either stays in WFM phase or makes the transition to WM phase at time t+1. This implies that the same argument holds for all time s such that s≥t due to forward induction; that is, the aforementioned relation between the queue states will propagate over time through coupling [18, 21].Lemma 6.
Consider the queue length processes defined in Theorem3. There exists coupling between (X(t),Y(t)) and (X~(t),Y~(t)) such that if the system is in WM phase at time t≥0, either the system remains in WM phase or it makes the transition to WFM phase at time t+1.Proof.
Initially, att=0, the queue states are identical to initial condition (x0,y0). By definition, the system is in WM phase at time 0 because (8)-(9) are satisfied when the queue states are identical.
Now consider the system at timet where we make the induction hypothesis; that is, the system is in WM phase at time t. Once the connectivity and queue states are coupled, π(t) and π~(t) may take different actions from A. For the sake of simplicity, we will define new symbols for actions denoted by S, R, and I with some abuse of notation: (i)
π(t)=S denotes that a service has occurred at one of the RQs (a precise notation will be π(t)∈S1,…,Sn) under π at time t.(ii)
π(t)=R denotes that a routing from the SQ to one of the RQs (a precise notation will be π(t)∈R1,…,Rn) has occurred under π at time t.(iii)
π(t)=I denotes that the policy idles at time t.
For instance,(π(t),π~(t))=(S,R) denotes the event that π served a RQ and π~ routed a customer from the SQ to a RQ. We will consider a total of 9 cases, since (π(t),π~(t)) can possibly take 9 action pairs. Recall that, in all cases, we will use the coupling introduced in Section 4.1; that is, Y[i](t) and Y~[i](t) see the same connectivity variable for i=1,…,n. Also X(t) and X~(t) see the same arrival variable.
Case
1 (πt,π~t=S,S). In this case, a service has occurred under both policies. Suppose the service has occurred at jth longest RQ under π. Also suppose that the kth longest RQ was served under π~. Since π uses LCQ, the served RQ was the longest among the connected queues. This implies that the connectivity variables for Y[i](t),i=1,…,j-1, must be 0. From the construction of coupling, this implies that the connectivity of Y~[i](t) is also 0 for i=1,…,j-1. Thus, k≥j must hold. We have that, for any l=1,…,n, (11)∑i=1lY~it+1-∑i=1lYit+1=-1l≥k+∑i=1lY~it--1l≥j+∑i=1lYit=1l≥j-1l≥k+∑i=1lY~it-∑i=1lYit≥0due to k≥j and induction hypothesis Y(t)≺wY~(t). Thus, we have Y(t+1)≺wY~(t+1); that is, (9) holds at time t+1. In addition, (8) is satisfied at time t+1, because X(t) and X~(t) did not change, and Y~(t)-Y(t) remains unchanged since Y(t+1)=Y(t)-1 and Y~(t+1)=Y~(t)-1. Consequently, the system is in WM phase at time t+1.
Case
2 (π(t),π~(t)=(R,R)). Both policies routed a customer to a RQ; thus (8) clearly holds at time t+1. Next, suppose π~ has routed a customer to the kth longest RQ, whereas π has routed a customer to the shortest RQ. We have that, for any l=1,…,n, (12)∑i=1lY~it+1-∑i=1lYit+1=1l≥k+∑i=1lY~it-1l=n+∑i=1lYit=1l≥k-1l=n+∑i=1lY~it-∑i=1lYit≥0,which holds due to k≤n and the induction hypothesis. Thus, we have that Y(t+1)≺wY~(t+1); that is, (9) holds at time t+1. Thus the system is in WM phase at time t+1.
Case
3 (π(t),π~(t)=(I,I)). Since there is no change in the queue states under both policies, WM phase is maintained at time t+1.
Case
4 (π(t),π~(t)=(S,R)). In this case, π serves a RQ, and π~ routes a customer to a RQ. Since π serves a RQ, we have that Y(t+1)≺wY(t). Since π~ routes a customer to a RQ, Y~(t)≺wY~(t+1) holds. By induction hypothesis (9), this implies that Y(t+1)≺wY~(t+1); that is, (9) holds at time t+1.
Suppose the service occurred at queuej under π, and the routing occurred at queue k under π~. Also it is implied that X~(t)>0 in this case. We have that(13)Xt+1=Xt,X~t+1=X~t-1,(14)Yjt+1=Yjt-1,Y~kt+1=Y~kt+1.Let δ=X(t)-X~(t)≥0. From (13), we have that(15)Xt+1-X~t+1=Xt-X~t+1=δ+1.Also Y~(t)-Y(t)≥2δ implies that, from (14),(16)Y~t+1-Yt+1=Y~t-Yt+2≥2δ+1.Thus, (8) is satisfied at time t+1. Consequently, the system is in WM phase at time t+1.
Case
5 (π(t),π~(t)=(R,I)). This is the case where π serves the SQ and π~ idles. We consider two cases.
Case
5.1 (X(t)>X~(t)). In this case, at time t+1 we have that (17)Xt+1=Xt-1,X~t+1=X~t,Yt+1=Yt+1,Y~t+1=Y~t.Let δ≔X(t)-X~(t)>0. Then(18)Y~t+1-Yt+1=2δ-1≥2δ-1holds, and X(t+1)-X~(t+1)=δ-1. Thus (8) is satisfied at time t+1.
Next we check if weak majorization (9) holds at time t+1. Let us define y≔Y[n](t). Suppose that there were k more queues which have had length y at time t.
Firstly consider the case wherek=0. This implies that the RQ to which the customer is routed is still the shortest queue at time t+1 under π. Since π performs JSQ, Y[n](t) is incremented by 1. Thus we have that(19)Ynt+1=Ynt+1,Yit+1=Yit,i=1,…,n-1.We will show that(20)∑i=1lYit+1≤∑i=1lY~it+1holds for l=1,…,n. Clearly, (20) holds for 1≤l≤n-1. For l=n, consider the following. Since X(t) and X~(t) differ by at least one customer, Y(t) and Y~(t) differ by at least two customers by induction hypothesis (8). This implies that (21)∑i=1nYit+1=1+∑i=1nYit≤-1+Y~t.Since Y~(t+1)=Y~(t), we conclude that (20) holds for l=n. Consequently, Y(t+1)≺wY~(t+1); that is, the weak majorization is maintained at time t+1.
Secondly, consider the case wherek>0. At time t+1, the RQ which received a customer under π becomes (n-k)th longest queue, or, equivalently, we are incrementing (n-k)th longest queue at time t (which was of length y) by one. Thus, we have that Y[n-k](t+1)=y+1 and Y[i](t+1)=Y[i](t)=y for i≥n-k+1. We will show that (22)∑i=1lYit+1≤∑i=1lY~it+1,for l=n-k, which implies Y(t+1)≺wY~(t+1); this is because (22) already holds for l<n-k due to induction hypothesis of weak majorization at time t; and if (22) holds for l=n-k, it will do so for l>n-k by construction. Define(23)k∗=maxj∣∑i=1jYit=∑i=1jY~it.Here we implicitly assume the set in the RHS of (23) is nonempty; otherwise Y(t+1)≺wY~(t+1) holds and we are done. We have that k∗≠n, because k>0.
We will show thatk∗<n-k holds by contradiction. Suppose k∗≥n-k. Then we must have that Y[k∗](t)=Y~[k∗](t)=y. Since there are at least 2δ>0 more customers in Y~(t), we have that (24)∑i=k∗+1nY~it-Yit≥2δ.However, since Y[i](t)=y for y>k∗, we have that (25)∑i=k∗+1nY~it≥2δ+n-k∗y>n-k∗y.However since Y~[k∗](t)=y, we must have that Y~[i](t)≤y, for i>k∗, and thus (25) cannot hold, yielding a contradiction. Thus, we have that k∗<n-k, which implies that(26)∑i=1n-kYit<∑i=1n-kY~it.Since π routes a customer to the (n-k)th longest RQ, (26) implies that (22) holds for l=n-k. Thus, the weak majorization hypothesis continues to hold for time t+1.
Case
5.2. (X(t)=X~(t)). In this case, we have X(t+1)<X~(t+1). Thus, condition (8) ceases to hold, andthe system makes the transition to WFM phase. We will discuss WFM phase in detail and prove the transition of phases in the next section.
Case
6 (π(t),π~(t)=(I,S)). This is the case where π idles and π~ serves a RQ. Since π is idle, we must have X(t)=0, which in turn implies X~(t)=0 due to induction hypothesis (8). Suppose the service has occurred on jth longest RQ under π~. We must have Y[j](t)=0; otherwise π would have served the jth longest RQ instead of idling, because the jth longest RQ is in connected state due to coupling. Given Y[j](t)=0, we cannot have ∑i=1jY[i](t)=∑i=1jY~[i](t), because(27)∑i=1j-1Yit=∑i=1jYit=Y~jt+∑i=1j-1Y~it>∑i=1j-1Y~it,which will violate induction hypothesis (9). Thus, we have that(28)∑i=1jYit<∑i=1jY~it.This implies that(29)∑i=1jYit+1≤∑i=1jY~it+1.Combining this with the induction hypothesis (9), we conclude that Y(t+1)≺wY~(t+1).
Case
7 (π(t),π~(t)=(S,I)). This is the case where π serves a RQ and π~ idles. Clearly (8) holds at time t+1, because the SQ remains unchanged. Since one of the RQs was served under π, we clearly have that(30)Yt+1≺wYt≺wY~t=Y~t+1;that is, (9) holds at time t+1.
Case
8 (π(t),π~(t)=(I,R)). This case cannot happen, because if it were to happen, we must have X(t)=0 because π is work-conserving. This in turn would imply X~(t)=0 by the induction hypothesis.
Case
9 ((π(t),π~(t))=(R,S)). In this case, π serves the SQ and π~ serves a RQ. Suppose the service has occurred at the jth longest queue of Y~(t). π will route the customer to the shortest queue in Y(t), or Y[n](t). Since a departure occurred at the jth longest queue of Y~(t) but did not occur at Y(t), we must have Y[k](t)=0 for k≥j. Thus, the customer is routed to one of the empty RQs under π, which leads to Y[j](t+1)≤1. We will consider two cases: X(t)=X~(t) and X(t)>X~(t).
Case
9.1 (X(t)>X~(t)). This case implies that X(t) and X~(t) differ by at least one customer. From (8), this implies that there are at least two more customers in Y~(t). The jth longest RQ under π has been incremented by one where π~ has been decremented.
Firstly, consider the caseY~[j](t)≥2. Since the jth longest RQ was served under π~, this implies that Y~[j](t+1)≥1. However, since we have Y[j](t+1)≤1, weak majorization Y(t+1)≺wY~(t+1) will clearly hold due to induction hypothesis (9) at time t.
Secondly, consider the caseY~[j](t)=1. Suppose there were more than one queue with length 1 under π~ at time t. Then we have that Y~[j](t+1)=1≥Y[j](t+1). Since Y[k](t)=0 for k≥j, this implies Y(t+1)≺wY~(t+1), and we are done.
Now suppose that thejth longest RQ under π~ was the only RQ with length one. This implies that(31)Yt=∑i=1jYit,Y~t=∑i=1jY~it.After the policies took the actions, we have that(32)∑i=1jY~it+1=-1+∑i=1jY~it,∑i=1jYit+1=1+∑i=1jYit.By induction hypothesis, there have been at least 2δ>0 more customers for Y~(t) than those for Y(t). Thus if we combine (31)-(32) we have that(33)∑i=1jY~it+1-Yit+1=-2+∑i=1jY~it-Yit≥2δ-2≥0.Accordingly, we claim that the following holds for all k≤j: (34)∑i=1kYit+1≤∑i=1kY~it+1since Y[k](t+1)=Y[k](t) and Y~[k](t+1)=Y~[k](t) for all k≤j due to (33) and the induction hypothesis. If j=n, it implies that Y(t+1)≺wY~(t+1). If j<n, since Y[k](t)=Y[k](t+1)=0 for k>j, we see that Y(t+1)≺wY~(t+1) holds as well.
Next we examine if (8) holds at time t+1. By assumption we have X(t)-X~(t)=δ>0, and thus X(t+1)-X~(t+1)=δ-1≥0. Also(35)Y~t+1-Yt+1=Y~t-Yt-2≥2δ-2=2δ-1.Thus, (8) holds at time t+1. In conclusion, the system remains in WM phase at time t+1.
Case
9.2 (X(t)=X~(t)). In this case, the system makes the transition to WFM phase which we introduce in the next section. The phase transition will be proved later as well.


### 4.3. Water-Filling Majorization (WFM) Phase

We have the following definition.Definition 7.
Considerx and x~ in Z+ and n-dimensional vectors y and y~ in Z+n. We say (x,y) is water-filling majorized by (x~,y~) denoted by (36)x,y≺wwfx~,y~if the following holds: (1)
x<x~.(2)
Letξ denote the difference between x and x~; that is, ξ=x~-x. Let y~′∈Z+n be a vector formed by adding ξ to the entries of y~ in a “water-filling” manner. Specifically, let l(ξ) be a number that satisfies(37)ξ=∑j=1nlξ-y~j+.Let us add[l(ξ)-y~[j]]+ to y~[j] for j=1,…,n, and let y~′ denote the resulting vector. Then we have that(38)y≺wy~′.We say that the system is in WFM phase if, at time t,(39)Xt,Yt≺wwfX~t,Y~t.In other words, we have(40)Xt<X~t,(41)Yt≺wY~′t,where Y~′(t) is constructed by routing ξ=X~(t)-X(t) customers to Y~(t) in the “water-filling” manner.We discuss the implication of the WFM phase. As mentioned earlier, JSQ-LCQ prioritizes serving the RQs and hence will generate many empty RQs. As a result, JSQ-LCQ may be forced to route customers, resulting in a short SQ, for example, as in (40), and will cause the RQs to build up. During the WFM phase, it is possible that Y(t)≺wY~(t); even the number of customers in the RQs under JSQ-LCQ can be larger than that under π~; for example, see the example in Figure 3. However, from a broader perspective, the queues are still “well-balanced” under JSQ-LCQ in WFM phase as follows. There are ξ more customers in the SQ under π~, and if we distribute those ξ customers to the RQ in the “water-filling” manner (equivalently, route ξ customers one after another using JSQ) and denote the resulting vector of RQs by Y~′(t), then we have Y(t)≺wY~′(t). Put differently, a shorter SQ means that JSQ-LCQ is still “ahead” of π~ in pushing customers closer to the destination. Suppose π~ attempts to “catch up” the difference in a balanced manner, that is, by routing ξ head-of-line customers in the SQ to the RQs in a water-filling manner. The RQs under JSQ-LCQ are still better balanced; that is, Y(t)≺wY~(t). In summary, if we compare only the RQs in WFM phase, JSQ-LCQ may appear worse than other policies; however, if we consider the SQ and RQs in a combined way, we find that JSQ-LCQ is better off in terms of balancing queues, which leads to enhanced opportunism.Figure 3
Example of the system in water-filling majorization (WFM) phase. The SQ underπ~ has an excess of ξ≔X~(t)-X(t)=2 customers compared to that under π, which satisfies (40). The RQs at time t under JSQ-LCQ are not necessarily better balanced than those under π~; we observe that Y(t)≺wY~(t), if we compare the system in the upper left and the bottom left. However, if we construct Y~′(t) by performing a “water-filling” routing of ξ=2 customers from X~(t) to Y~(t), we observe that Y(t) is better balanced than Y~′(t), if we compare the queues in the upper right and the bottom right. Thus, we have Yt≺wY~′(t), which satisfies (41).In the proof of Lemma6, we argued that in cases (5.2) and (9.2) the system makes the transition to WFM phase, and hence we will check if the transition actually occurred, that is, whether (X(t+1),Y(t+1))≺wwf(X~(t+1),Y~(t+1)) holds in those cases. Below we will continue and conclude the proof.Proof of Lemma6, Continued.
⁡
Case
5.2 ((π(t),π~(t))=(R,I)). Note that X(t)=X~(t); thus we have X(t+1)<X~(t+1). Hence property (40) holds at time t+1. Next we will show (41) holds at time t+1. Note that Y(t+1) is obtained by performing the JSQ routing to Y(t). Since ξ≔X~(t+1)-X(t+1)=1, Y~′(t+1) can be constructed by performing water-filling routing of one customer to Y~(t+1). Note that water-filling routing of one customer is equivalent to the JSQ routing of one customer. In other words, Y(t+1) and Y~′(t+1) are obtained by performing JSQ each on Y(t) and Y~(t+1), respectively. Note that Y(t)≺wY~(t)=Y~(t+1) holds due to induction hypothesis (9). Thus, given the relation Y(t)≺wY~(t+1), if we perform the JSQ routing to both Y(t) and Y~(t+1), the weak majorization relation will be preserved after JSQ. Thus, we have Yt+1≺wY~′(t+1), satisfying (41) at time t+1. Thus, we conclude that (X(t+1),Y(t+1))≺wwf(X~(t+1),Y~(t+1)) holds, and the system is in WFM phase at time t+1.
Case
9.2 ((π(t),π~(t))=(R,S)). We have that X(t+1)+1=X(t)=X~(t)=X~(t+1); thus (40) is satisfied at time t+1.
Suppose there was a service from thejth longest queue from Y~(t). The jth longest queue of Y(t) must be empty; otherwise the queue must have been served under π. Thus, we have that (42)Yj=0,Y~jt≥1.In order to construct Y~′(t+1), we first need to take action (π(t),π~(t))=(R,S) and then perform water-filling routing of ξ customers to Y~(t+1). Suppose these steps are taken in the following sequence: (1)
π~(t) takes action S.(2)
π(t) takes action R.(3)
Perform water-filling routing toY~(t+1) to yield Y~′(t+1).
Let us denote the RQs after step (1) underπ~ by Z~(t). Due to Y(t)≺wY~(t) and (42), a departure from jth longest queue does not affect the weak majorization among RQs; that is, Y(t)≺wZ~(t) holds. Next, consider steps (2) and (3). We have X~(t+1)-X(t+1)=ξ=1; clearly, (2) is the JSQ operation on Y(t) with a single customer under π, and (3) is also the JSQ operation on Z~(t) with ξ=1 customer under π~. Therefore, Y(t)≺wZ~(t) implies that Y(t+1)≺wY~′(t+1); that is, (41) holds at time t+1. In conclusion, the system makes the transition to WFM phase at time t+1.Next we consider the coupling of queues underπ and π~ in WFM phase.Lemma 8.
There exists a coupling between queue length processes(X(t),Y(t)) and (X~(t),Y~(t)) such that if the system is in WFM phase at time t≥0, either the system remains in WFM phase or it makes the transition to WM phase at time t+1.Proof.
As previously, the queue connectivity is coupled such thatY[i](t) and Y~[i](t) have the same connectivity variable for i=1,…,n. The arrivals at X(t) and X~(t) are coupled; that is, they see the same arrival variable. Similar to WM phase, we consider a total of 9 action pairs of (π(t),π~(t)).
Case
1 ((π(t),π~(t))=(S,S)). Firstly, there is no change in the SQs; thus we have X(t+1)=X(t) and X~(t+1)=X~(t), and hence (40) holds at time t+1.
Secondly, suppose that thejth longest RQ has been served under π and the kth longest RQ has been served under π~. In the proof of Case 1 of Lemma 6, we have shown that k≥j holds due to the LCQ policy in π. We further showed that the following holds:(43)Yt+1≺wY~t+1.Since Y~′(t+1) is obtained by routing ξ≔X~(t)-X(t)>0 customers to Y(t+1), thus clearly we have that Y~t+1≺wY~′(t+1) holds. Consequently, Y(t+1)≺wY~(t+1) holds, which shows that (41) holds at time t+1. Therefore, the system remains in WFM phase at time t+1.
Cases
2 and 3 ((π(t),π~(t))=(I,I) or (R,R)). Similar to the case for WM phase, it is straightforward to show that if π and π~ perform identical actions of I and R, property (39) is preserved at time t+1.
Case 4 ((π(t),π~(t))=(R,S)). Let ξ≔X~(t)-X(t). Since π performed routing and π~ performed a service, X~(t+1)-X(t+1)=ξ+1>0, satisfying (40) at time t+1.
Next we will show thatYt+1≺wY~′(t+1). Suppose the service has occurred at jth longest queue of Y~(t). Let us denote the index of this jth longest queue by j′. Due to coupling of connectivity, we must have that the jth longest queue of Y(t) is zero. In order to construct Y~′(t+1), we need to take two steps on Y~(t): (i) serve RQ j′ and (ii) route ξ+1 customers to the RQs in a water-filling manner. We will rearrange these steps to compare Y(t) and Y~′(t) as follows: (1)
Serve a customer from RQj′ under π~.(2)
Routeξ customers to the RQ in the water-filling manner under π~.(3)
Perform JSQ of a customer fromX(t) and X~(t) so as to yield Y(t+1) and Y~′(t+1), respectively.
LetZ(t) denote the vector of RQs under π~ after steps (1) and (2) are completed. We will consider two cases.
Case
4.1. This is the case where the following is assumed:(44)∑i=1j-1Yit≤∑i=1j-1Zit.Since Y[j](t)=0, we have that Y[k]=0, k≥j. This implies that Y[k](t)≤Z[k](t),∀k≥j. Thus, we have that Y(t)≺wZ(t). Since both Y(t+1) and Y~′(t+1) are formed by performing JSQ routing to Y(t) and Z(t), Y(t)≺wZ(t) implies that Yt+1≺wY~′(t+1).
Case
4.2. This is the case where the following is assumed:(45)∑i=1j-1Yit>∑i=1j-1Zit.In order for (45) to hold, we must have (46)Yj-1t=Zj-1t+1from the induction hypothesis Y(t)≺wY~′(t). That is, because only one customer is served from the jth longest RQ in Y~(t), Y[j-1](t) and Z[j-1](t) cannot differ by more than one customer; otherwise it would violate the induction hypothesis. Next, we will show that the following holds: (47)Zj-1t=Zjt=⋯=Znt,using contradiction. Suppose there exists j-1≤k≤n-1 such that Z[k](t)>Z[k+1](t). The only difference between Y~′(t) and Z(t) is that Z(t) is formed by serving the jth longest queue in step (1),before performing water-filling routing in step (2). Therefore, we have that (48)Y~i′t=Zit,i=1,…,k.However, (48) contradicts (46), and hence (47) holds.
Next, we consider step (3). Recall that the length of thejth longest RQ in Y(t) is zero. After performing JSQ at step (3), we have that(49)Yjt+1=1,Yit+1=0,i=j+1,…,n.Next, we consider Z(t). From (46) and (47), (j-1)th longest queue is the shortest queue in Z(t); otherwise Y(t) and Z(t) will differ by more than two customers, violating induction hypothesis (41). Thus, in step (3), one customer from X~(t) will be routed to the (j-1)th shortest queue of Z(t). Thus we have that, from (46),(50)Y~j-1t+1=Zj-1t+1=Yj-1t=Yj-1t+1.Also, in (47), we must have Z[j-1](t)>0 because it is formed by water-filling of ξ>0 customers. Then we have that (51)Yj-1t+1=Y~j-1′t+1,Yit+1≤Y~i′t+1,i≥j.Thus, we have that Yt+1≺wY~′(t+1); that is, (41) holds at time t+1. We conclude that the system remains in WFM phase at time t+1.
Case
5 ((π(t),π~(t))=(I,S)). In this case, we can show that the system remains in WFM phase at time t+1 in a similar manner to that used for (R,S), because action pair (I,S) can be regarded as a special case of (R,S) with X(t)=0 (i.e., π “routes” zero customers to the RQ).
Case
6 ((π(t),π~(t))=(R,I)). Since a routing has occurred at the SQ under π, clearly we have X(t+1)<X~(t+1). Let ξ=X~(t)-X(t). To construct Y~′(t+1), we need to perform water-filling routing to Y~(t+1) with ξ+1 customers; however, we can alternatively construct Y(t+1) and Y~′(t+1) for comparison purposes as follows: (1)
Perform water-filling routing ofξ customers from X~(t) to Y~(t).(2)
Perform JSQ from bothX(t) and X~(t) so as to yield Y(t+1) and Y~′(t+1), respectively.
By induction hypothesis,Y(t) is weakly majorized by the resulting vector in step (1) which is Y~′(t). In step (2), JSQ has been performed equally on Y(t) and Y~′(t), and thus the weak majorization relation is preserved between the RQs. Thus, we have Y(t+1)≺wY~′(t+1).
Case
7 ((π(t),π~(t))=(S,I)). Since there is no change in the SQs, X(t+1)<X~(t+1) holds. Also, since a RQ has been served under π, we have(52)Yt+1≺wYt≺wY~′t=Y~′t+1;that is, the system is in WFM phase at time t+1.
Case
8 ((π(t),π~(t))=(I,R)). Irrespective of which RQ π~ routes a customer to, we have(53)Yt+1=Yt≺wY~′t≺wY~′t+1by induction hypothesis and the definition of Y~′(t). Thus, (41) holds at time t+1. The system may make the transition to either WFM phase or WM phase depending on the length of the SQs. If ξ=1, that is, X~(t)=X(t)+1, we have that X(t+1)=X~(t+1), and (53) implies that Y(t+1)≺wY~(t+1). Thus, the system makes the transition to WM phase at time t+1. Otherwise (ξ>1), from (53), the system remains at WFM phase.
Case
9 ((π(t),π~(t))=(S,R)). Using a similar argument to Case 8, we have(54)Yt+1≺wYt≺wY~′t≺wY~′t+1.Also, the system makes the transition to either WFM phase or WM phase. If X~(t)-X(t)=1, (54) implies Y(t+1)≺wY~(t+1), and thus the system is in WM phase at time t+1; otherwise, from (54), the system remains in WFM phase.


### 4.4. Proof and Remarks

We are now ready to prove Theorem3.Proof of Theorem3.
Lemmas6 and 8 imply that we can couple the queue length processes such that the system is either in WM phase or in WFM phase for all s≥t, by using forward induction [18]. If the system is in WM phase at time t, it is implied that (55)Xt+Yt≤X~t+Y~tbecause X(t)≤X~(t) and Y(t)≺wY~(t). If the system is in WFM phase at time t, we have that since Y(t)≺wY~′(t),(56)Yt≤Y~′t=Y~t+ξ=Y~t+X~t-Xt,which implies (55) as well. In conclusion, using the proposed coupling, we can construct sample paths under which (55) is satisfied for all t=0,1,2,…. This completes the proof of (3).Remark 9.
One could ask, can we construct direct coupling between the processes ofsum-queues which leads to delay optimality? That is, if we define Z(t)≔X(t)+Y(t) and Z~(t)≔X~(t)+Y~(t), can we directly couple Z(t) and Z~(t) to show optimality, instead of coupling the vectors of SQ and RQs as in our proof? We believe it is quite unlikely, because the information on individual queue lengths, which is lost if we take the sum of queue lengths, is vital in proving the optimality of JSQ-LCQ. For example, if we consider action pair (π,π~)=(R,S), the number of customers in the system reduces by one under π~; however it remains fixed under JSQ-LCQ. Thus π~ appears to get ahead of JSQ-LCQ in terms of reducing the sum-queue length. However, this is not true in the long term, as we have analyzed through coupling in WM and WFM phases which were defined based on the (weak) majorization of queue vectors. Importantly, in a half-duplex two-hop network, we route a customer at the expense of the opportunity to serve a RQ in that time slot and vice versa. Thus, routing and service are inherently in a tradeoff relation, and thus it is crucial that the scheduling and routing decisions properly balance queues so as to maximize the time-varying opportunity in channel connectivity. We have rigorously showed that JSQ-LCQ is able to capture those aspects and as a result achieves delay optimality in the stochastic ordering sense.


## 4.1. Coupling

Letπ(t) denote the JSQ-LCQ policy. Let π~(t) denote another arbitrary policy. (X(t),Y(t)) (resp., (X~(t),Y~(t)) in Theorem 3 denote the queue length processes under π(t) (resp., π~(t)). In the following we use forward induction [18, Section 8.3] by coupling the connectivity of the RQs under π(t) and π~(t) as follows. Suppose the process of RQs under π(t), or Y(t), has the connectivity given by C(t)=(c1,…,cn) at time t. We will couple C(t) with the connectivity variables for Y~(t) as follows: if the ith longest queue of Y(t) has the connectivity c∈{0,1}, then let the ith longest queue of Y~(t) have the same connectivity c, for i=1,…,n. In other words, Y[i](t) and Y~[i](t) see the same connectivity variable by the coupling for i=1,…,n. This coupling will not change the marginal distributions of the connectivity seen by Y(t) and Y~(t) as is required in (1) and (2) of Definition 2 (see also [18, Proposition 8.3.2]), because this coupling involves simply permuting the connectivity variables across the RQs. Specifically, the connectivity variables are i.i.d. across the RQs and thus their joint distribution is symmetric or invariant to permutation; that is,(5)PC1t=c1,…,Cnt=cn=PC1t=cP1,…,Cnt=cPn,where P is an arbitrary permutation of the index set 1,2,…,n. Next, the arrivals to the system are coupled as follows: if an arrival occurs at the SQ under π(t), then let there be an arrival at the SQ under π~(t). In the rest of the proof, we will assume that the queue length processes under π and π~ are coupled in the above fashion.Unlike previous works on single-hop scheduling, the coupling argument in our problem must consider dynamic interactions among queues, connectivity, and the half-duplex constraint, as follows. JSQ-LCQ prioritizes serving the RQs; that is, it will serve the RQs whenever possible, in a balanced manner. Thus, the RQs will tend to be short under JSQ-LCQ. This means that, due to half-duplex operation, the SQ will get relatively long. However, if many RQs become empty due to prioritized service, the number of nonempty and connected RQs will become small. Hence JSQ-LCQ may be forced to frequently route customers to the RQs, in a balanced manner, in which case the RQs will build up. However, as the number of nonempty RQs grows, there will be many nonempty and connected RQs, and JSQ-LCQ will again begin to actively serve the RQs. Thus, we observe that the system exhibits some cyclic patterns in the services and evolution of the queue states.Based on this observation, we identify that there existtwo distinct phases in our coupling process. In the first phase, the RQs tend to be short and the SQ tends to be long under JSQ-LCQ. In the second phase, the SQ tends to be short and RQs tend to be long. The first phase is calledweak majorization (WM) phase, and the second phase is calledwater-filling majorization (WFM) phase. We will explain the phases in more detail in the subsequent sections. We show that, by introducing the concept of phases, we are able to handle the aforementioned patterns in system behaviour. Specifically, under proper coupling, we show that the system remains in either of the two phases or makes the transition to the other phase. Later we will show that this construction implies the desired stochastic majorization given by (4).


## 4.2. Weak Majorization (WM) Phase

For vectorx∈Rn, let xk denote the kth longest entry of x; that is, x[1]≥⋯≥x[n].Definition 4.
For two vectorsx,y∈Rn, if(6)∑k=1jxk≤∑k=1jyk,j=1,…,n,x is said to beweakly majorized by y, which is denoted as x≺wy.
Recall that(X(t),Y(t)) (resp., (X~(t),Y~(t))) is the queue length processes under JSQ-LCQ or π (resp., an arbitrary policy or π~).Definition 5.
We say the system is in weak majorization (WM) phase if(1)
the following relation holds:(7)0≤Xt-X~t≤12Y~t-Yt;equivalently, there exists integerδ≥0 such that(8)Xt-X~t=δ,Y~t-Yt≥2δ;(2)
Y(t) is weakly majorized by Y~(t); that is,(9)Yt≺wY~t.We discuss the implication of the WM phase. Firstly, JSQ-LCQ will greedily serve the RQs whenever possible, making the overall length of RQs small. By contrast, the customers that arrived at the SQ will have to wait relatively long due to the half-duplex constraint. Condition (8) represents these properties; that is, the SQ under JSQ-LCQ is relatively long, and the sum-length of the RQs is relatively small. In addition, if we rearrange the inequality on the right of condition (8),(10)Yt+δ≤Y~t-δ,which is interpreted as follows. There are an excess of δ customers backlogged at the SQ under JSQ-LCQ. Thus, if we compare only the SQs, JSQ-LCQ appears to be δ customers “behind” π~. Now suppose JSQ-LCQ adds these δ customers to Y(t) by serving the SQ for δ times to “catch up” π~, which takes δ time slots. During this time interval, π~ can serve δ customers from the RQs to push the customers out of the system as much as possible, in which case Y~(t) is reduced by δ. However, (10) shows that, even after such actions by π~, the number of customers under JSQ-LCQ still is no more than that under π~. Thus, condition (8) indicates that JSQ-LCQ is in fact sufficiently “ahead” of π~ in WM phase. Secondly, not only will the RQs be short, but also they are well “balanced” due to JSQ-routing and LCQ-scheduling principles. Condition (9) represents this property. An example of the system in WM phase is depicted in Figure 2.Figure 2
Example of the system in weak majorization (WM) phase. The figure in the above (resp., below) shows the queues under policy JSQ-LCQ orπ (resp., π~). The SQ under π is longer than that under π~; that is, X(t)=2 and X~(t)=1. In addition, the number of customers in the RQs satisfies the following: we have Y~(t)-Y(t)=5-3=2≥2{X(t)-X~(t)}, which satisfies (8). Next, we have Y(t)≺wY~(t) satisfying (9); that is, the RQs under JSQ-LCQ are “better balanced” than those under π~.However, the system may get out of WM phase if most of the RQs are emptied out, after which JSQ-LCQ will mainly serve the SQ. Consequently, the RQs will become relatively long but the SQ will become relatively short, in contrast to WM phase. In that case, the system makes the transition to WFM phase, which we will define and discuss in detail in Section4.3.To use forward induction we will show that if the system is in WM phase at timet, under a proper coupling of connectivity and arrivals, the system will either remain in WM phase or make the transition to WFM phase at time t+1. Later, we will make a similar coupling argument for the system in WFM phase: a system in WFM phase at time t either stays in WFM phase or makes the transition to WM phase at time t+1. This implies that the same argument holds for all time s such that s≥t due to forward induction; that is, the aforementioned relation between the queue states will propagate over time through coupling [18, 21].Lemma 6.
Consider the queue length processes defined in Theorem3. There exists coupling between (X(t),Y(t)) and (X~(t),Y~(t)) such that if the system is in WM phase at time t≥0, either the system remains in WM phase or it makes the transition to WFM phase at time t+1.Proof.
Initially, att=0, the queue states are identical to initial condition (x0,y0). By definition, the system is in WM phase at time 0 because (8)-(9) are satisfied when the queue states are identical.
Now consider the system at timet where we make the induction hypothesis; that is, the system is in WM phase at time t. Once the connectivity and queue states are coupled, π(t) and π~(t) may take different actions from A. For the sake of simplicity, we will define new symbols for actions denoted by S, R, and I with some abuse of notation: (i)
π(t)=S denotes that a service has occurred at one of the RQs (a precise notation will be π(t)∈S1,…,Sn) under π at time t.(ii)
π(t)=R denotes that a routing from the SQ to one of the RQs (a precise notation will be π(t)∈R1,…,Rn) has occurred under π at time t.(iii)
π(t)=I denotes that the policy idles at time t.
For instance,(π(t),π~(t))=(S,R) denotes the event that π served a RQ and π~ routed a customer from the SQ to a RQ. We will consider a total of 9 cases, since (π(t),π~(t)) can possibly take 9 action pairs. Recall that, in all cases, we will use the coupling introduced in Section 4.1; that is, Y[i](t) and Y~[i](t) see the same connectivity variable for i=1,…,n. Also X(t) and X~(t) see the same arrival variable.
Case
1 (πt,π~t=S,S). In this case, a service has occurred under both policies. Suppose the service has occurred at jth longest RQ under π. Also suppose that the kth longest RQ was served under π~. Since π uses LCQ, the served RQ was the longest among the connected queues. This implies that the connectivity variables for Y[i](t),i=1,…,j-1, must be 0. From the construction of coupling, this implies that the connectivity of Y~[i](t) is also 0 for i=1,…,j-1. Thus, k≥j must hold. We have that, for any l=1,…,n, (11)∑i=1lY~it+1-∑i=1lYit+1=-1l≥k+∑i=1lY~it--1l≥j+∑i=1lYit=1l≥j-1l≥k+∑i=1lY~it-∑i=1lYit≥0due to k≥j and induction hypothesis Y(t)≺wY~(t). Thus, we have Y(t+1)≺wY~(t+1); that is, (9) holds at time t+1. In addition, (8) is satisfied at time t+1, because X(t) and X~(t) did not change, and Y~(t)-Y(t) remains unchanged since Y(t+1)=Y(t)-1 and Y~(t+1)=Y~(t)-1. Consequently, the system is in WM phase at time t+1.
Case
2 (π(t),π~(t)=(R,R)). Both policies routed a customer to a RQ; thus (8) clearly holds at time t+1. Next, suppose π~ has routed a customer to the kth longest RQ, whereas π has routed a customer to the shortest RQ. We have that, for any l=1,…,n, (12)∑i=1lY~it+1-∑i=1lYit+1=1l≥k+∑i=1lY~it-1l=n+∑i=1lYit=1l≥k-1l=n+∑i=1lY~it-∑i=1lYit≥0,which holds due to k≤n and the induction hypothesis. Thus, we have that Y(t+1)≺wY~(t+1); that is, (9) holds at time t+1. Thus the system is in WM phase at time t+1.
Case
3 (π(t),π~(t)=(I,I)). Since there is no change in the queue states under both policies, WM phase is maintained at time t+1.
Case
4 (π(t),π~(t)=(S,R)). In this case, π serves a RQ, and π~ routes a customer to a RQ. Since π serves a RQ, we have that Y(t+1)≺wY(t). Since π~ routes a customer to a RQ, Y~(t)≺wY~(t+1) holds. By induction hypothesis (9), this implies that Y(t+1)≺wY~(t+1); that is, (9) holds at time t+1.
Suppose the service occurred at queuej under π, and the routing occurred at queue k under π~. Also it is implied that X~(t)>0 in this case. We have that(13)Xt+1=Xt,X~t+1=X~t-1,(14)Yjt+1=Yjt-1,Y~kt+1=Y~kt+1.Let δ=X(t)-X~(t)≥0. From (13), we have that(15)Xt+1-X~t+1=Xt-X~t+1=δ+1.Also Y~(t)-Y(t)≥2δ implies that, from (14),(16)Y~t+1-Yt+1=Y~t-Yt+2≥2δ+1.Thus, (8) is satisfied at time t+1. Consequently, the system is in WM phase at time t+1.
Case
5 (π(t),π~(t)=(R,I)). This is the case where π serves the SQ and π~ idles. We consider two cases.
Case
5.1 (X(t)>X~(t)). In this case, at time t+1 we have that (17)Xt+1=Xt-1,X~t+1=X~t,Yt+1=Yt+1,Y~t+1=Y~t.Let δ≔X(t)-X~(t)>0. Then(18)Y~t+1-Yt+1=2δ-1≥2δ-1holds, and X(t+1)-X~(t+1)=δ-1. Thus (8) is satisfied at time t+1.
Next we check if weak majorization (9) holds at time t+1. Let us define y≔Y[n](t). Suppose that there were k more queues which have had length y at time t.
Firstly consider the case wherek=0. This implies that the RQ to which the customer is routed is still the shortest queue at time t+1 under π. Since π performs JSQ, Y[n](t) is incremented by 1. Thus we have that(19)Ynt+1=Ynt+1,Yit+1=Yit,i=1,…,n-1.We will show that(20)∑i=1lYit+1≤∑i=1lY~it+1holds for l=1,…,n. Clearly, (20) holds for 1≤l≤n-1. For l=n, consider the following. Since X(t) and X~(t) differ by at least one customer, Y(t) and Y~(t) differ by at least two customers by induction hypothesis (8). This implies that (21)∑i=1nYit+1=1+∑i=1nYit≤-1+Y~t.Since Y~(t+1)=Y~(t), we conclude that (20) holds for l=n. Consequently, Y(t+1)≺wY~(t+1); that is, the weak majorization is maintained at time t+1.
Secondly, consider the case wherek>0. At time t+1, the RQ which received a customer under π becomes (n-k)th longest queue, or, equivalently, we are incrementing (n-k)th longest queue at time t (which was of length y) by one. Thus, we have that Y[n-k](t+1)=y+1 and Y[i](t+1)=Y[i](t)=y for i≥n-k+1. We will show that (22)∑i=1lYit+1≤∑i=1lY~it+1,for l=n-k, which implies Y(t+1)≺wY~(t+1); this is because (22) already holds for l<n-k due to induction hypothesis of weak majorization at time t; and if (22) holds for l=n-k, it will do so for l>n-k by construction. Define(23)k∗=maxj∣∑i=1jYit=∑i=1jY~it.Here we implicitly assume the set in the RHS of (23) is nonempty; otherwise Y(t+1)≺wY~(t+1) holds and we are done. We have that k∗≠n, because k>0.
We will show thatk∗<n-k holds by contradiction. Suppose k∗≥n-k. Then we must have that Y[k∗](t)=Y~[k∗](t)=y. Since there are at least 2δ>0 more customers in Y~(t), we have that (24)∑i=k∗+1nY~it-Yit≥2δ.However, since Y[i](t)=y for y>k∗, we have that (25)∑i=k∗+1nY~it≥2δ+n-k∗y>n-k∗y.However since Y~[k∗](t)=y, we must have that Y~[i](t)≤y, for i>k∗, and thus (25) cannot hold, yielding a contradiction. Thus, we have that k∗<n-k, which implies that(26)∑i=1n-kYit<∑i=1n-kY~it.Since π routes a customer to the (n-k)th longest RQ, (26) implies that (22) holds for l=n-k. Thus, the weak majorization hypothesis continues to hold for time t+1.
Case
5.2. (X(t)=X~(t)). In this case, we have X(t+1)<X~(t+1). Thus, condition (8) ceases to hold, andthe system makes the transition to WFM phase. We will discuss WFM phase in detail and prove the transition of phases in the next section.
Case
6 (π(t),π~(t)=(I,S)). This is the case where π idles and π~ serves a RQ. Since π is idle, we must have X(t)=0, which in turn implies X~(t)=0 due to induction hypothesis (8). Suppose the service has occurred on jth longest RQ under π~. We must have Y[j](t)=0; otherwise π would have served the jth longest RQ instead of idling, because the jth longest RQ is in connected state due to coupling. Given Y[j](t)=0, we cannot have ∑i=1jY[i](t)=∑i=1jY~[i](t), because(27)∑i=1j-1Yit=∑i=1jYit=Y~jt+∑i=1j-1Y~it>∑i=1j-1Y~it,which will violate induction hypothesis (9). Thus, we have that(28)∑i=1jYit<∑i=1jY~it.This implies that(29)∑i=1jYit+1≤∑i=1jY~it+1.Combining this with the induction hypothesis (9), we conclude that Y(t+1)≺wY~(t+1).
Case
7 (π(t),π~(t)=(S,I)). This is the case where π serves a RQ and π~ idles. Clearly (8) holds at time t+1, because the SQ remains unchanged. Since one of the RQs was served under π, we clearly have that(30)Yt+1≺wYt≺wY~t=Y~t+1;that is, (9) holds at time t+1.
Case
8 (π(t),π~(t)=(I,R)). This case cannot happen, because if it were to happen, we must have X(t)=0 because π is work-conserving. This in turn would imply X~(t)=0 by the induction hypothesis.
Case
9 ((π(t),π~(t))=(R,S)). In this case, π serves the SQ and π~ serves a RQ. Suppose the service has occurred at the jth longest queue of Y~(t). π will route the customer to the shortest queue in Y(t), or Y[n](t). Since a departure occurred at the jth longest queue of Y~(t) but did not occur at Y(t), we must have Y[k](t)=0 for k≥j. Thus, the customer is routed to one of the empty RQs under π, which leads to Y[j](t+1)≤1. We will consider two cases: X(t)=X~(t) and X(t)>X~(t).
Case
9.1 (X(t)>X~(t)). This case implies that X(t) and X~(t) differ by at least one customer. From (8), this implies that there are at least two more customers in Y~(t). The jth longest RQ under π has been incremented by one where π~ has been decremented.
Firstly, consider the caseY~[j](t)≥2. Since the jth longest RQ was served under π~, this implies that Y~[j](t+1)≥1. However, since we have Y[j](t+1)≤1, weak majorization Y(t+1)≺wY~(t+1) will clearly hold due to induction hypothesis (9) at time t.
Secondly, consider the caseY~[j](t)=1. Suppose there were more than one queue with length 1 under π~ at time t. Then we have that Y~[j](t+1)=1≥Y[j](t+1). Since Y[k](t)=0 for k≥j, this implies Y(t+1)≺wY~(t+1), and we are done.
Now suppose that thejth longest RQ under π~ was the only RQ with length one. This implies that(31)Yt=∑i=1jYit,Y~t=∑i=1jY~it.After the policies took the actions, we have that(32)∑i=1jY~it+1=-1+∑i=1jY~it,∑i=1jYit+1=1+∑i=1jYit.By induction hypothesis, there have been at least 2δ>0 more customers for Y~(t) than those for Y(t). Thus if we combine (31)-(32) we have that(33)∑i=1jY~it+1-Yit+1=-2+∑i=1jY~it-Yit≥2δ-2≥0.Accordingly, we claim that the following holds for all k≤j: (34)∑i=1kYit+1≤∑i=1kY~it+1since Y[k](t+1)=Y[k](t) and Y~[k](t+1)=Y~[k](t) for all k≤j due to (33) and the induction hypothesis. If j=n, it implies that Y(t+1)≺wY~(t+1). If j<n, since Y[k](t)=Y[k](t+1)=0 for k>j, we see that Y(t+1)≺wY~(t+1) holds as well.
Next we examine if (8) holds at time t+1. By assumption we have X(t)-X~(t)=δ>0, and thus X(t+1)-X~(t+1)=δ-1≥0. Also(35)Y~t+1-Yt+1=Y~t-Yt-2≥2δ-2=2δ-1.Thus, (8) holds at time t+1. In conclusion, the system remains in WM phase at time t+1.
Case
9.2 (X(t)=X~(t)). In this case, the system makes the transition to WFM phase which we introduce in the next section. The phase transition will be proved later as well.


## 4.3. Water-Filling Majorization (WFM) Phase

We have the following definition.Definition 7.
Considerx and x~ in Z+ and n-dimensional vectors y and y~ in Z+n. We say (x,y) is water-filling majorized by (x~,y~) denoted by (36)x,y≺wwfx~,y~if the following holds: (1)
x<x~.(2)
Letξ denote the difference between x and x~; that is, ξ=x~-x. Let y~′∈Z+n be a vector formed by adding ξ to the entries of y~ in a “water-filling” manner. Specifically, let l(ξ) be a number that satisfies(37)ξ=∑j=1nlξ-y~j+.Let us add[l(ξ)-y~[j]]+ to y~[j] for j=1,…,n, and let y~′ denote the resulting vector. Then we have that(38)y≺wy~′.We say that the system is in WFM phase if, at time t,(39)Xt,Yt≺wwfX~t,Y~t.In other words, we have(40)Xt<X~t,(41)Yt≺wY~′t,where Y~′(t) is constructed by routing ξ=X~(t)-X(t) customers to Y~(t) in the “water-filling” manner.We discuss the implication of the WFM phase. As mentioned earlier, JSQ-LCQ prioritizes serving the RQs and hence will generate many empty RQs. As a result, JSQ-LCQ may be forced to route customers, resulting in a short SQ, for example, as in (40), and will cause the RQs to build up. During the WFM phase, it is possible that Y(t)≺wY~(t); even the number of customers in the RQs under JSQ-LCQ can be larger than that under π~; for example, see the example in Figure 3. However, from a broader perspective, the queues are still “well-balanced” under JSQ-LCQ in WFM phase as follows. There are ξ more customers in the SQ under π~, and if we distribute those ξ customers to the RQ in the “water-filling” manner (equivalently, route ξ customers one after another using JSQ) and denote the resulting vector of RQs by Y~′(t), then we have Y(t)≺wY~′(t). Put differently, a shorter SQ means that JSQ-LCQ is still “ahead” of π~ in pushing customers closer to the destination. Suppose π~ attempts to “catch up” the difference in a balanced manner, that is, by routing ξ head-of-line customers in the SQ to the RQs in a water-filling manner. The RQs under JSQ-LCQ are still better balanced; that is, Y(t)≺wY~(t). In summary, if we compare only the RQs in WFM phase, JSQ-LCQ may appear worse than other policies; however, if we consider the SQ and RQs in a combined way, we find that JSQ-LCQ is better off in terms of balancing queues, which leads to enhanced opportunism.Figure 3
Example of the system in water-filling majorization (WFM) phase. The SQ underπ~ has an excess of ξ≔X~(t)-X(t)=2 customers compared to that under π, which satisfies (40). The RQs at time t under JSQ-LCQ are not necessarily better balanced than those under π~; we observe that Y(t)≺wY~(t), if we compare the system in the upper left and the bottom left. However, if we construct Y~′(t) by performing a “water-filling” routing of ξ=2 customers from X~(t) to Y~(t), we observe that Y(t) is better balanced than Y~′(t), if we compare the queues in the upper right and the bottom right. Thus, we have Yt≺wY~′(t), which satisfies (41).In the proof of Lemma6, we argued that in cases (5.2) and (9.2) the system makes the transition to WFM phase, and hence we will check if the transition actually occurred, that is, whether (X(t+1),Y(t+1))≺wwf(X~(t+1),Y~(t+1)) holds in those cases. Below we will continue and conclude the proof.Proof of Lemma6, Continued.
⁡
Case
5.2 ((π(t),π~(t))=(R,I)). Note that X(t)=X~(t); thus we have X(t+1)<X~(t+1). Hence property (40) holds at time t+1. Next we will show (41) holds at time t+1. Note that Y(t+1) is obtained by performing the JSQ routing to Y(t). Since ξ≔X~(t+1)-X(t+1)=1, Y~′(t+1) can be constructed by performing water-filling routing of one customer to Y~(t+1). Note that water-filling routing of one customer is equivalent to the JSQ routing of one customer. In other words, Y(t+1) and Y~′(t+1) are obtained by performing JSQ each on Y(t) and Y~(t+1), respectively. Note that Y(t)≺wY~(t)=Y~(t+1) holds due to induction hypothesis (9). Thus, given the relation Y(t)≺wY~(t+1), if we perform the JSQ routing to both Y(t) and Y~(t+1), the weak majorization relation will be preserved after JSQ. Thus, we have Yt+1≺wY~′(t+1), satisfying (41) at time t+1. Thus, we conclude that (X(t+1),Y(t+1))≺wwf(X~(t+1),Y~(t+1)) holds, and the system is in WFM phase at time t+1.
Case
9.2 ((π(t),π~(t))=(R,S)). We have that X(t+1)+1=X(t)=X~(t)=X~(t+1); thus (40) is satisfied at time t+1.
Suppose there was a service from thejth longest queue from Y~(t). The jth longest queue of Y(t) must be empty; otherwise the queue must have been served under π. Thus, we have that (42)Yj=0,Y~jt≥1.In order to construct Y~′(t+1), we first need to take action (π(t),π~(t))=(R,S) and then perform water-filling routing of ξ customers to Y~(t+1). Suppose these steps are taken in the following sequence: (1)
π~(t) takes action S.(2)
π(t) takes action R.(3)
Perform water-filling routing toY~(t+1) to yield Y~′(t+1).
Let us denote the RQs after step (1) underπ~ by Z~(t). Due to Y(t)≺wY~(t) and (42), a departure from jth longest queue does not affect the weak majorization among RQs; that is, Y(t)≺wZ~(t) holds. Next, consider steps (2) and (3). We have X~(t+1)-X(t+1)=ξ=1; clearly, (2) is the JSQ operation on Y(t) with a single customer under π, and (3) is also the JSQ operation on Z~(t) with ξ=1 customer under π~. Therefore, Y(t)≺wZ~(t) implies that Y(t+1)≺wY~′(t+1); that is, (41) holds at time t+1. In conclusion, the system makes the transition to WFM phase at time t+1.Next we consider the coupling of queues underπ and π~ in WFM phase.Lemma 8.
There exists a coupling between queue length processes(X(t),Y(t)) and (X~(t),Y~(t)) such that if the system is in WFM phase at time t≥0, either the system remains in WFM phase or it makes the transition to WM phase at time t+1.Proof.
As previously, the queue connectivity is coupled such thatY[i](t) and Y~[i](t) have the same connectivity variable for i=1,…,n. The arrivals at X(t) and X~(t) are coupled; that is, they see the same arrival variable. Similar to WM phase, we consider a total of 9 action pairs of (π(t),π~(t)).
Case
1 ((π(t),π~(t))=(S,S)). Firstly, there is no change in the SQs; thus we have X(t+1)=X(t) and X~(t+1)=X~(t), and hence (40) holds at time t+1.
Secondly, suppose that thejth longest RQ has been served under π and the kth longest RQ has been served under π~. In the proof of Case 1 of Lemma 6, we have shown that k≥j holds due to the LCQ policy in π. We further showed that the following holds:(43)Yt+1≺wY~t+1.Since Y~′(t+1) is obtained by routing ξ≔X~(t)-X(t)>0 customers to Y(t+1), thus clearly we have that Y~t+1≺wY~′(t+1) holds. Consequently, Y(t+1)≺wY~(t+1) holds, which shows that (41) holds at time t+1. Therefore, the system remains in WFM phase at time t+1.
Cases
2 and 3 ((π(t),π~(t))=(I,I) or (R,R)). Similar to the case for WM phase, it is straightforward to show that if π and π~ perform identical actions of I and R, property (39) is preserved at time t+1.
Case 4 ((π(t),π~(t))=(R,S)). Let ξ≔X~(t)-X(t). Since π performed routing and π~ performed a service, X~(t+1)-X(t+1)=ξ+1>0, satisfying (40) at time t+1.
Next we will show thatYt+1≺wY~′(t+1). Suppose the service has occurred at jth longest queue of Y~(t). Let us denote the index of this jth longest queue by j′. Due to coupling of connectivity, we must have that the jth longest queue of Y(t) is zero. In order to construct Y~′(t+1), we need to take two steps on Y~(t): (i) serve RQ j′ and (ii) route ξ+1 customers to the RQs in a water-filling manner. We will rearrange these steps to compare Y(t) and Y~′(t) as follows: (1)
Serve a customer from RQj′ under π~.(2)
Routeξ customers to the RQ in the water-filling manner under π~.(3)
Perform JSQ of a customer fromX(t) and X~(t) so as to yield Y(t+1) and Y~′(t+1), respectively.
LetZ(t) denote the vector of RQs under π~ after steps (1) and (2) are completed. We will consider two cases.
Case
4.1. This is the case where the following is assumed:(44)∑i=1j-1Yit≤∑i=1j-1Zit.Since Y[j](t)=0, we have that Y[k]=0, k≥j. This implies that Y[k](t)≤Z[k](t),∀k≥j. Thus, we have that Y(t)≺wZ(t). Since both Y(t+1) and Y~′(t+1) are formed by performing JSQ routing to Y(t) and Z(t), Y(t)≺wZ(t) implies that Yt+1≺wY~′(t+1).
Case
4.2. This is the case where the following is assumed:(45)∑i=1j-1Yit>∑i=1j-1Zit.In order for (45) to hold, we must have (46)Yj-1t=Zj-1t+1from the induction hypothesis Y(t)≺wY~′(t). That is, because only one customer is served from the jth longest RQ in Y~(t), Y[j-1](t) and Z[j-1](t) cannot differ by more than one customer; otherwise it would violate the induction hypothesis. Next, we will show that the following holds: (47)Zj-1t=Zjt=⋯=Znt,using contradiction. Suppose there exists j-1≤k≤n-1 such that Z[k](t)>Z[k+1](t). The only difference between Y~′(t) and Z(t) is that Z(t) is formed by serving the jth longest queue in step (1),before performing water-filling routing in step (2). Therefore, we have that (48)Y~i′t=Zit,i=1,…,k.However, (48) contradicts (46), and hence (47) holds.
Next, we consider step (3). Recall that the length of thejth longest RQ in Y(t) is zero. After performing JSQ at step (3), we have that(49)Yjt+1=1,Yit+1=0,i=j+1,…,n.Next, we consider Z(t). From (46) and (47), (j-1)th longest queue is the shortest queue in Z(t); otherwise Y(t) and Z(t) will differ by more than two customers, violating induction hypothesis (41). Thus, in step (3), one customer from X~(t) will be routed to the (j-1)th shortest queue of Z(t). Thus we have that, from (46),(50)Y~j-1t+1=Zj-1t+1=Yj-1t=Yj-1t+1.Also, in (47), we must have Z[j-1](t)>0 because it is formed by water-filling of ξ>0 customers. Then we have that (51)Yj-1t+1=Y~j-1′t+1,Yit+1≤Y~i′t+1,i≥j.Thus, we have that Yt+1≺wY~′(t+1); that is, (41) holds at time t+1. We conclude that the system remains in WFM phase at time t+1.
Case
5 ((π(t),π~(t))=(I,S)). In this case, we can show that the system remains in WFM phase at time t+1 in a similar manner to that used for (R,S), because action pair (I,S) can be regarded as a special case of (R,S) with X(t)=0 (i.e., π “routes” zero customers to the RQ).
Case
6 ((π(t),π~(t))=(R,I)). Since a routing has occurred at the SQ under π, clearly we have X(t+1)<X~(t+1). Let ξ=X~(t)-X(t). To construct Y~′(t+1), we need to perform water-filling routing to Y~(t+1) with ξ+1 customers; however, we can alternatively construct Y(t+1) and Y~′(t+1) for comparison purposes as follows: (1)
Perform water-filling routing ofξ customers from X~(t) to Y~(t).(2)
Perform JSQ from bothX(t) and X~(t) so as to yield Y(t+1) and Y~′(t+1), respectively.
By induction hypothesis,Y(t) is weakly majorized by the resulting vector in step (1) which is Y~′(t). In step (2), JSQ has been performed equally on Y(t) and Y~′(t), and thus the weak majorization relation is preserved between the RQs. Thus, we have Y(t+1)≺wY~′(t+1).
Case
7 ((π(t),π~(t))=(S,I)). Since there is no change in the SQs, X(t+1)<X~(t+1) holds. Also, since a RQ has been served under π, we have(52)Yt+1≺wYt≺wY~′t=Y~′t+1;that is, the system is in WFM phase at time t+1.
Case
8 ((π(t),π~(t))=(I,R)). Irrespective of which RQ π~ routes a customer to, we have(53)Yt+1=Yt≺wY~′t≺wY~′t+1by induction hypothesis and the definition of Y~′(t). Thus, (41) holds at time t+1. The system may make the transition to either WFM phase or WM phase depending on the length of the SQs. If ξ=1, that is, X~(t)=X(t)+1, we have that X(t+1)=X~(t+1), and (53) implies that Y(t+1)≺wY~(t+1). Thus, the system makes the transition to WM phase at time t+1. Otherwise (ξ>1), from (53), the system remains at WFM phase.
Case
9 ((π(t),π~(t))=(S,R)). Using a similar argument to Case 8, we have(54)Yt+1≺wYt≺wY~′t≺wY~′t+1.Also, the system makes the transition to either WFM phase or WM phase. If X~(t)-X(t)=1, (54) implies Y(t+1)≺wY~(t+1), and thus the system is in WM phase at time t+1; otherwise, from (54), the system remains in WFM phase.


## 4.4. Proof and Remarks

We are now ready to prove Theorem3.Proof of Theorem3.
Lemmas6 and 8 imply that we can couple the queue length processes such that the system is either in WM phase or in WFM phase for all s≥t, by using forward induction [18]. If the system is in WM phase at time t, it is implied that (55)Xt+Yt≤X~t+Y~tbecause X(t)≤X~(t) and Y(t)≺wY~(t). If the system is in WFM phase at time t, we have that since Y(t)≺wY~′(t),(56)Yt≤Y~′t=Y~t+ξ=Y~t+X~t-Xt,which implies (55) as well. In conclusion, using the proposed coupling, we can construct sample paths under which (55) is satisfied for all t=0,1,2,…. This completes the proof of (3).Remark 9.
One could ask, can we construct direct coupling between the processes ofsum-queues which leads to delay optimality? That is, if we define Z(t)≔X(t)+Y(t) and Z~(t)≔X~(t)+Y~(t), can we directly couple Z(t) and Z~(t) to show optimality, instead of coupling the vectors of SQ and RQs as in our proof? We believe it is quite unlikely, because the information on individual queue lengths, which is lost if we take the sum of queue lengths, is vital in proving the optimality of JSQ-LCQ. For example, if we consider action pair (π,π~)=(R,S), the number of customers in the system reduces by one under π~; however it remains fixed under JSQ-LCQ. Thus π~ appears to get ahead of JSQ-LCQ in terms of reducing the sum-queue length. However, this is not true in the long term, as we have analyzed through coupling in WM and WFM phases which were defined based on the (weak) majorization of queue vectors. Importantly, in a half-duplex two-hop network, we route a customer at the expense of the opportunity to serve a RQ in that time slot and vice versa. Thus, routing and service are inherently in a tradeoff relation, and thus it is crucial that the scheduling and routing decisions properly balance queues so as to maximize the time-varying opportunity in channel connectivity. We have rigorously showed that JSQ-LCQ is able to capture those aspects and as a result achieves delay optimality in the stochastic ordering sense.


## 5. Simulation

In this section, we evaluate the performance of JSQ-LCQ via simulations. We used MATLAB as the discrete event simulator. A time-slotted system is simulated with the following parameters: the probability of a customer arriving at the source queue given byλ; the probability that a relay queue is in ON state given by p; the number of relay nodes given by n. The performance metric in our simulation is the average number of customers in the system. We compared JSQ-LCQ with the well-known backpressure (BP) scheduling algorithm. Note that the BP algorithm is known to be throughput optimal; however it does not guarantee delay optimality.Figure4 shows the performance of JSQ-LCQ and BP against n or the number of relay nodes. We vary n from 2 to 9, where the parameters p and λ are given by 0.14 and 0.1, respectively. We observe that JSQ-LCQ achieves the lower number of customers over all the values of n. We also observe that the average number of customers decreases with increasing n in both cases. This is because the overall service rate at n relays is given by 1-(1-p)n which increases in n. The rate of decrease in the number of customers is higher at lower values of n, which also can be explained from the dependency of service rate 1-(1-p)n on n; that is, the service rate increases faster for smaller n.Figure 4
Comparison of the average number of customers in the system versus the number of relay nodes.Figure5 shows the performance of JSQ-LCQ and BP against p which is the probability that a relay queue is in ON state. The parameters n and λ are given by 4 and 0.2, respectively. We observe that the number of customers is smaller with JSQ-LCQ over all the values of p. We also observe that the average number of customers decreases as a convex function of p similar to Figure 4; however, the rate of decrease is not as steep as that with respect to n, because the service rate 1-(1-p)n is a polynomial function of p in contrast to its exponential dependence in n.Figure 5
Comparison of the average number of customers in the system versus the connectivity probability of relays.Figure6 shows the performance of JSQ-LCQ and BP against the arrival rate λ. The parameters p and n are given by 0.8 and 4, respectively. We observe that JSQ-LCQ outperforms BP over all values of λ. We also observe that the number of customers increases with increasing λ. The number of customers will blow up as λ tightly approaches condition (2). In conclusion, the simulation results verify that JSQ-LCQ indeed achieves the smaller number of customers in the system over all simulated parameters, as is expected from our theoretical result on optimality.Figure 6
Comparison of the average number of customers in the system versus the arrival rates.


## 6. Conclusion

In this paper, we studied a delay-optimal policy for half-duplex two-hop relay networks with symmetric connectivity on the service. We showed that JSQ-LCQ policy is strongly optimal; that is, the total queue length under JSQ-LCQ is stochastically dominated by any other policy. Our future work includes devising simple policies for two-hop relay networks with asymmetric connectivity and studying delay optimality for cooperative relay networks with more than two hops. Under certain realistic conditions for time-varying channels, for example, fading due to the user mobility having power-law distributions [39], the i.i.d. assumption of channel connectivity over time may not hold, and JSQ-LCQ is not guaranteed to be delay-optimal. In fact, for many realistic channel models, it is difficult to guarantee delay optimality. The significance of our work is that, however, we have established the delay optimality of a two-hop network model with time-varying connectivity, albeit its simplicity, considering that there exists a limited amount of works on delay-optimal scheduling.



---

*Source: 4362652-2017-11-21.xml*