Learning-Based Adaptive Dynamic Routing with Stability Guarantee for a Single-Origin-Single-Destination Network

Dynamic routing is a control scheme with extensive application in network systems including communications, manufacturing, transportation, etc [1, 2, 3, 4]. A primary objective of dynamic routing is to ensure stability, i.e. the boundedness of the long-time average of traffic state. The typical tool to approach this class of problems is the Lyapunov function method [5]. On top of this, a secondary objective is to minimize the system time experienced by each job. Queuing theorists have made efforts on characterization of the limiting distribution of the traffic state, but such results are usually complicated and non-scalable [6, 7, 8]. Recently, learning-based approaches have been proposed for dynamic routing. However, such approaches are usually purely numerical without explicit theoretical guarantees on traffic stability [9].

Motivated by the above challenge, we consider a dynamic routing scheme for single-origin-single-destination queuing networks that integrates Lyapunov function methods [10] and approximate dynamic programming [11]. We use a class of piecewise-linear (PL) functions that are increasing in traffic states to measure the travel cost of a path. An incoming job is routed to the path with the smallest cost, so the routing scheme can be viewed as a generalized shortest-path (GSP) strategy. We use the PL functions to construct a Lyapunov function for stability analysis, and we show that the resultant routing scheme is throughput-optimal. We also use the PL functions as proxies for action-value functions to obtain a policy iteration algorithm. This algorithm computes a suboptimal routing scheme that is guaranteed to be stabilizing. We also show that our scheme gives comparable performance (i.e., average system time) with respect to neural network-based methods but with a significant reduction in computational workload. This paper focuses on the bridge network in Fig. 1,

but our modeling, analysis, and computation approaches also provide hints for general networks.

Extensive results have been developed for traffic stabilization and throughput maximization [5, 12, 13, 14], which provide a basis for this paper. In terms of travel cost minimization, previous results are typically either restricted to simple scenarios (e.g., parallel queues) or based on numerical simulation [15, 16] or optimization methods without traffic stability analysis [17, 18]. In particular, reinforcement learning methods are proposed to compute optimal/suboptimal solutions to dynamic routing problems [19, 20]. Although learning methods usually give excellent performance, they focus on algorithm design and do not emphasize theoretical guarantees for stability/optimality. In addition, generic learning methods may be computationally inefficient for dynamic routing. In particular, Liu et al. proposed a mixed scheme that uses learning over a bounded set of states and uses a known stabilizing policy for the other states [21]; this notion of integration of learning and stability guarantee is aligned with the idea of this paper, but this paper makes such integration in a different manner.

We formulate our problem on the single-origin-single-destination queuing network in Fig. 1. Jobs arrive at the source node as a Poisson process. Each server has exponentially distributed service times. When a job arrives, the system operator assigns a path to the job, which will not be changed afterwards. Hence, every job belongs to a class that corresponds to the assigned path. The key of our routing scheme is a set of PL functions that approximate the expected travel times on each path. Such PL functions were introduced by Down and Meyn [10] to show positive Harris recurrence of the traffic state. Our previous work proposed an explicit construction of the parameters of the PL functions according to network topology, without solving model data-dependent inequalities [22]. In this paper, we further utilize the PL functions to bound the mean of the traffic state and to obtain our GSP routing policy.

We show that our GSP policy maximizes network throughput in the sense that it is stabilizing as long as the demand at the source is less than the min-cut capacity of the network (Theorem 1). The proof utilizes a critical insight about the PL functions: each linear regime corresponds to a particular configuration of bottlenecks. We construct a piecewise-quadratic Lyapunov function using the PL functions and show that the mean drift of the Lyapunov function is negative in heavy-traffic regimes. The drift condition also leads to a set of constraints on the PL parameters.

We then develop a policy iteration algorithm that learns the PL parameters (and thus the GSP policy). The policy iteration algorithm uses the PL functions as a proxy (as opposed to an immediate approximation) of the action-value functions; this connects the learning-based routing decisions with the above-mentioned theoretical properties. In each iteration, the current policy is evaluated using the PL function after a Monte-Carlo episode and improved by greedifying over the PL functions; the evaluation is done by an algorithm specifically designed for the PL functions. We compare our policy iteration algorithm with a standard neural-network dynamic programming algorithm. The implementation results indicate that our approach can attain a 1.9%-6.7% optimality gap with respect to the neural-network method with a 97.8%-99.8% reduction in training time.

In summary, our contributions are:

1. 1.

   A simple, insightful, and easy-to-implement dynamic routing scheme, i.e., the GSP policy.

2. 2.

   Theoretical guarantee on traffic stabilization and throughput maximization of the GSP policy over the bridge network.

3. 3.

   An efficient policy iteration algorithm for the GSP policy that attains comparable control performance but significantly reduces training time compared with neural network-based methods.

The rest of this paper is organized as follows. Section 2 introduces the network model and formulates the dynamic routing problem. Section 3 develops the stability guarantee for the GSP policy. Section 4 demonstrates the training algorithm for the GSP policy. Section 5 gives the concluding remarks.

Consider the single-origin-single-destination (SOSD) network of queuing servers with infinite buffer sizes in Fig. 1. Let $\mathcal{N}=\{1,2,3,4,5\}$ be the set of servers. Each server $n$ has an exponential service rate $\bar{\mu}_{n}$ and job number $x_{n}(t)$ at time $t$, $t\in\mathbb{R}_{\geq 0}$. Jobs arrive at origin $S$ according to a Poisson process of rate $\bar{\lambda}>0$. There are three $paths$ from the origin to the destination, $\mathcal{P}=\{(1,2),~{}(1,3,5),~{}(4,5)\}$. We denote $n\in p$ if server $n$ is on path $p.$

When a job arrives, it will go to one of the three paths according to a routing policy. The path of the job cannot be changed after it is decided at the origin. Thus, we divide the jobs into three classes according to their assigned paths. We use $x_{n}^{p}(t)$ to denote the jobs queuing in server $n$ and going on path $p\in\mathcal{P}$ at time $t$. For each server we have $x_{n}(t)=\sum_{n\in p}x_{n}^{p}(t)$. Thus we can define the state of the network as the vector $x=[x_{1}^{12},x_{1}^{135},x_{2}^{12},x_{3}^{135},x_{4}^{45},x_{5}^{135},x_{5}^{45}]^{T}$, and the state space is $\mathcal{X}=\mathbb{Z}_{\geq 0}^{7}$.

We consider two sets of actions, viz. $1)~{}routing$ and $2)~{}scheduling$. Routing refers to determining the path of each job upon its arrival, which only occurs at $S$. The routing action can be formulated as a vector

Scheduling refers to selecting a job from the queue to serve, which only occurs at Servers 1 and 5; preemptive priority is assumed at both servers. The scheduling action can also be formulated as a vector

where $m_{n}$ is the number of paths through server $n$.

This paper focuses on a particular class of control policies which we call the $generalized~{}shortest~{}path$ (GSP) policy, which is based on the following piecewise-linear (PL) functions of traffic states:

where $\beta>1$ is a design parameter. We then define the notion of bottlenecks as follows:

Intuitively, a bottleneck is a server that immediately contributes to $Q_{p}$, while the immediately downstream server, if it exists, does not contribute to $Q_{p}$. Let $B=(b_{12},b_{135},b_{45})$ be a combination of bottlenecks, where $b_{12}\in\{1,2\},b_{135}\in\{1,3,5\},b_{45}\in\{4,5\}$, and denote $n\in B$ if $n$ is a bottleneck in combination $B$. Let $\mathcal{B}$ be the set of possible combinations, which has 12 elements, each corresponding to a subset of $\mathcal{X}$ over which $\{Q_{p}\}$ are all linear in $x$.

The GSP policy essentially sends an incoming job to the path with the smallest $Q$ function. However, the $Q$ functions only capture the traffic states but do not consider the influence of the service rates, especially the service rate of the current bottleneck. To account for this, we introduce a second parameter $\gamma>1$ that allows the GSP policy to prioritize the path with a higher bottleneck service rate. To be specific, for a combination $B\in\mathcal{B}$, we first sort the paths according to their bottleneck service rates:

Then for $B\in\mathcal{B}$, define the weight of each path as

Now we are ready to formulate the GSP policy, with a slight abuse of notation, as follows: When there are no ties,

ties are broken randomly.

The above joint-routing-scheduling policy is called GSP, because the PL $Q$ function is a generalized measurement of the “temporal length” of each path. By this policy, server $n$ will prioritize the jobs from class $p$ if server $n$ is the bottleneck of path $p$. If server $n$ is the bottleneck of multiple paths, the GSP policy would further prioritize the jobs from the path with a larger $Q$ function. We also define

note that $1\leq|P^{*}|\leq 3$.

We say that the traffic in the network is $stable$ if there exists $C<\infty$ such that for any initial condition,

We say the network is $stabilizable$ if $\bar{\lambda}<\bar{\mu}$, where $\bar{\mu}$ is the min-cut capacity of the network. Note that $\bar{\lambda}<\bar{\mu}$ ensures the existence of a stabilizing Bernoulli routing policy.

In this section, we consider the stability condition under GSP policy for the bridge network.

To state the main result, let $\mathcal{M}$ be the set of cuts of the network, and define

one can show that $m>1$ if the network is stabilizable. Let $d_{n}$ be the number of links on the longest path from the origin to server $n$. For each $M\in\mathcal{M}$, let $\mu_{\max}^{M}=\max\limits_{n\in M}\bar{\mu}_{n}$, $\mu_{\min}^{M}=\min\limits_{n\in M}\bar{\mu}_{n}$, and define

where $\mathrm{sgn}(\cdot)$ (resp. $(\cdot)_{+}$) is the sign (resp. positive part) function. Also define

Then, we can state the main result as follows:

The above result includes two key points. First, the GSP policy is stabilizing if the queuing network is stabilizable; i.e., the GSP policy maximizes the throughput of the network. Second, constraints on the parameters for the GSP policy are given, which determine the feasible set for the subsequent learning-based optimization (Section 4).

The parameters $m$ and $\Delta_{G}$ indicate the relationships between the service rates and arrival rate, while the design parameters $\beta$ and $\gamma$ characterize the GSP policy’s “preference”. Note that $\lim_{\bar{\lambda}\uparrow{\bar{\mu}}}m=1$, which means each server and each path will be “equally emphasized” by the GSP policy as the network approaches saturation. The case when $\Delta_{G}=1$ indicates that the path with a stronger service ability has a bottleneck closer to the origin. Then the degree of “preference” should decrease and the constraints of $\beta$ and $\gamma$ should be stricter because even though with a weaker service ability, the other paths have the bottleneck closer to the destination, and jobs on these paths can get to the destination more quickly once they pass the bottleneck.

The proof of Theorem 1 uses a Lyapunov function constructed from the PL $Q$ functions:

The key technique is to utilize the connection between the locations of bottlenecks and the GSP policy to argue for the negative mean drift of the Lyapunov function. In particular, we show that there exist $\epsilon>0,~{}C<\infty$ such that for all $x\in\mathcal{X}$

where $\mathcal{L}$ is the infinitesimal generator of the network model under the GSP policy. (4) implies the boundedness of the 1-norm of the traffic state and thus the stability of the network, according to the Foster-Lyapunov criterion [10].

Proof of Theorem 1. Firstly, we consider the case when $Q_{p}=0$ for some $p\in\mathcal{P}$. Suppose $\mathcal{P}^{*}=\{(1,2)\}$ and $Q_{12}=0$, which implies the servers on path $(1,2)$ are all empty. According to the GSP policy, $\lambda_{12}(x)=\bar{\lambda},~{}\lambda_{135}(x)=\lambda_{45}(x)=0$. The jobs will be allocated to path $(1,2)$, thus it only makes finite positive contribution to the drift. While path $(1,3,5)$ and $(4,5)$ are not empty and keep serving jobs, they make negative contribution to the drift:

Thus we can infer that the Lyapunov drift of the network can only be negative or finite positive when there are empty paths in the network, which also covers the cases of $Q_{135}=0$ and $Q_{45}=0$.

The rest of this proof is devoted to the case where $Q_{p}>0,p\in\mathcal{P}$. Specifically, we consider five qualitatively different cases:
Case 1: $B=(2,5,5)$.

In this case, the $Q$ function of each path have the forms of:

Then we prove according to the different routing decision:

1. i)

   $P^{*}=\{(1,2)\}$

   Since $b_{135}=b_{45}=5,~{}b_{12}=2$, we have:

   	$\displaystyle\gamma_{12}(B)=1,\gamma_{135}(B)=\gamma_{45}(B)=\gamma$	$\displaystyle,\bar{\mu}_{b_{12}}>\bar{\mu}_{b_{135}}=\bar{\mu}_{b_{45}}$
   	$\displaystyle\gamma_{12}(B)=\gamma,\gamma_{135}(B)=\gamma_{45}(B)=1$	$\displaystyle,\bar{\mu}_{b_{135}}=\bar{\mu}_{b_{45}}>\bar{\mu}_{b_{12}}.$

   Then the new arriving job will go to path $(1,2)$ when:

   	$\displaystyle 1)~{}\gamma Q_{12}<Q_{135},Q_{45};$		(6a)
   	$\displaystyle 2)~{}Q_{12}<\gamma Q_{135},\gamma Q_{45}.$		(6b)

   The scheduling decision of server 1 and server 5 will be $\mu_{2}^{12}(x)=\bar{\mu}_{2}$ and $\mu_{5}^{45}(x)+\mu_{5}^{135}(x)=\bar{\mu}_{5},~{}\mu_{5}^{45}(x)\mu_{5}^{135}(x)=0$. Clearly (6a) can be transformed into $Q_{12}<Q_{135},Q_{45}$, then we have :

   	$\displaystyle\mathcal{L}V(x)<$	$\displaystyle 2\beta^{2}(\lambda-\mu_{2}^{12}(x))(x_{1}^{12}+x_{2}^{12})$
   		$\displaystyle-2\beta^{2}\mu_{5}^{45}(x)(x_{4}^{45}+x_{5}^{45})$
   		$\displaystyle-2\mu_{5}^{135}(x)(x_{1}^{135}+x_{3}^{135}+x_{5}^{135})+C$
   	$\displaystyle<$	$\displaystyle 2\beta(x_{1}^{12}+x_{2}^{12})\Big{(}\beta(\bar{\lambda}-\bar{\mu}_{2})-\bar{\mu}_{5}/\gamma\Big{)}+C.$

   The drift is naturally negative when $\bar{\lambda}-\bar{\mu}_{2}\leq 0$, and it remains negative since $1<\beta\gamma<\beta^{2}<m\leq\frac{\bar{\mu}_{5}}{\bar{\lambda}-\bar{\mu}_{2}}$ when $\bar{\lambda}-\bar{\mu}_{2}>0$ according to (2). Thus (4) holds.

2. ii)

   $P^{*}=\{(1,3,5)\}$

   Similarly, the jobs will go to path (1,3,5) when $\gamma Q_{135}<Q_{12},\gamma Q_{45}$ or $Q_{135}<\gamma Q_{12},Q_{45}$. We have the drift:

   	$\displaystyle\mathcal{L}V(x)<$	$\displaystyle 2(x_{1}^{135}+x_{3}^{135}+x_{5}^{135})(\bar{\lambda}-\beta\bar{\mu}_{2}/\gamma-\beta\bar{\mu}_{5})$
   		$\displaystyle+C.$

3. iii)

   $P^{*}=\{(4,5)\}$

   $\displaystyle\mathcal{L}V(x)<$

   $\displaystyle 2\beta(x_{4}^{45}+x_{5}^{45})(\beta\lambda-\beta\bar{\mu}_{2}/\gamma-\bar{\mu}_{5})+C.$

   Since $\gamma<\beta<\sqrt{m}$, the drift satisfies (4).

For other cases when there are ties and $|P^{*}|>1$, since a job can only take a single path, the cases can be proved analogously.
Case 2: $B=(1,5,5)$.

When $P^{*}=\{(1,2)\}$, the maximal coefficient of $x_{1}^{12}$ exists when $\bar{\mu}_{1}>\bar{\mu}_{5}$ and $Q_{12}<\gamma Q_{135},\gamma Q_{45}$, the drift turns to be:

Since $d_{1}=1,d_{5}=3$ and the two nodes belong to the same cut, we have $\Delta_{G}=1$ and $1<\gamma<\beta<m^{\frac{1}{3}}$, which make (4) stands. The proof of other forms of $P^{*}$ is analogous with case 1.
Case 3: $B=(2,5,4)$.

We only show the case where $P^{*}=\{(1,2)\}$, the other cases can be proved analogously. For the diverse possible values of $\gamma_{p}(B)$, the drift has the form of:

According to the GSP policy, we have the scaled ratio:

Thus the possible maximal coefficient of $x_{1}^{12}+x_{2}^{12}$ exists when:

We have:

Since there are $d_{2}=2,d_{4}=1,d_{5}=3$ and $\Delta_{G}=1$ when $\bar{\mu}_{2}>\bar{\mu}_{4}>\bar{\mu}_{5}$, we have $1<\beta\gamma^{2}<m$. Thus the (4) can be proved. The case when $B=(1,5,4)$ can be proved analogously.
Case 4: $B=(2,3,4).$

We discuss when $P^{*}=\{(4,5)\}$. When the possible maximal coefficient of $x^{45}_{4}$ exists, the drift is:

Since $d_{2}=2,d_{4}=1,d_{3}=2$ and $\Delta_{G}=1$ when $\bar{\mu}_{4}>\bar{\mu}_{2}>\bar{\mu}_{3}$ or $\bar{\mu}_{4}>\bar{\mu}_{3}>\bar{\mu}_{2}$, thus we have $1<\beta\gamma^{2}<\beta^{3}<m$ and (4) holds. The cases of other forms of $P^{*}$ when $B=(2,3,4)$ and $B=(2,3,5)$ can be proved analogously.
Case 5: $B=(1,3,5).$

Considering $P^{*}=\{(1,2)\}$, when the possible maximal coefficient of $x^{12}_{1}$ exists, the drift satisfies:

We have $d_{1}=1,d_{3}=2,d_{5}=3$, and there is $\Delta_{G}=1$ when $\bar{\mu}_{1}>\bar{\mu}_{3}>\bar{\mu}_{5}$. Thus there is $1<\beta\gamma^{2}<\beta^{3}<m$, and (4) stands. The other forms of $P^{*}$ of case $B=(1,3,5)$ and $B=(1,3,4)$ can be proved analogously. The proof is the same for other cases of $B=(1,1,4)$, $B=(1,1,5)$, $B=(2,1,4)$, $B=(2,1,5)$.

In conclusion, we show that the mean drift always satisfies (4), which ensures the stability of the network. $\square$

In this section, we develop a policy iteration (PI) algorithm that computes the parameters for the GSP policy. In particular, theorem 1 gives a set of values for $\beta$ and $\gamma$ that ensure stability; the goal of the PI algorithm is to search the aforementioned set for a specific combination of $\beta$ and $\gamma$ that attains near-optimal traffic efficiency. In addition, the PI algorithm does not require a priori knowledge of the arrival and service rate. We also compare the performance of the GSP PI algorithm with three benchmark policies, viz. neural network (NN)-based PI, simple shortest path, and optimized Bernoulli.

We formulate the joint routing-scheduling problem as a Markov decision process (MDP) with state space $\mathcal{X}=\mathbb{Z}_{\geq 0}^{7}$. Since the routing and scheduling decision will only be made when an arrival or a departure occurs (i.e., at transition epochs [23, p.72]), the problem can be formulated as a discrete-time (DT) MDP. We denote the state and action of the DT MDP as $x[k]$ and $a[k]$, respectively. With a slight abuse of notation, $x[k]=x(t_{k})$, where $t_{k}$ is the $k$-th transition epoch of the continuous-time process. Similarly, the action is given by $a[k]=(\lambda[k],\mu[k])$, where $\lambda[k]\in\{0,\bar{\lambda}\}^{3}$ and $\mu[k]\in\prod_{n\in\mathcal{N}}\{0,\bar{\mu}_{n}\}^{m_{n}}$ are the route-specific arrival rates and service rates, respectively.

As indicated in Section 2, both the routing and the scheduling decisions can be parameterized via design variables $\beta$ and $\gamma$; by Theorem 1, $\beta$ and $\gamma$ should satisfy (2). Thus, the action is given by the policy

The transition probability $p(x^{\prime}|x,a)$ of the DT process can be derived from the network model defined in Section 2 in a straightforward manner. The one-step cost of the MDP is given by

The total cost over one episode of the MDP is thus given by

where $K\in\mathbb{Z}_{>0}$ is the length (i.e., number of transition epochs) of one episode.

In this article, we focus on a class of control policies for a single-origin-single-destination network, which we call the generalized shortest-path policy. We design a set of piecewise-linear functions as a proxy of the travel cost on the path over the network. We use the piecewise-linear functions to construct a Lyapunov function to derive theoretical guarantee on the stability of the traffic state. We also develop a policy iteration algorithm to learn the parameters for the proposed policy. Then we implement and compare the algorithm with three other benchmarks including a standard neural network-based algorithm. The experimental results showed that our policy and PI algorithm can perform efficiently and steadily when significantly reducing the computation cost as well, which is cost-effective. Future work may include (i) extension of the theoretical results as well as PI algorithm to general single-origin-single-destination acyclic networks and (ii) refinement of the PI algorithm to develop more efficient temporal-difference algorithms.