# Dynamic Request Routing for Online Video-on-Demand Service: A Markov Decision Process Approach

Authors: Jianxiong Wan; Limin Liu; Jianwei Guo
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

We investigate the request routing problem in the CDN-based Video-on-Demand system. We model the system as a controlled queueing system including a dispatcher and several edge servers. The system is formulated as a Markov decision process (MDP). Since the MDP formulation suffers from the so-called “the curse of dimensionality” problem, we then develop a greedy heuristic algorithm, which is simple and can be implemented online, to approximately solve the MDP model. However, we do not know how far it deviates from the optimal solution. To address this problem, we further aggregate the state space of the original MDP model and use the bounded-parameter MDP (BMDP) to reformulate the system. This allows us to obtain a suboptimal solution with a known performance bound. The effectiveness of two approaches is evaluated in a simulation study.


---

## Body

## 1. Introduction

The advancements of Internet technology have remarkably improved the capacity of both core networks and access networks and enable complex bandwidth-consuming applications which are far beyond simple text-based web page browsing. Among all these applications, Video-on-Demand (VoD) service has gained great popularity over the past decade. According to the report of the world’s largest content delivery network (CDN) provider, Akamai, the global average connection speed experienced over 20% growth during 2010 [1], partially due to the surging video content transferring via the Internet.Nowadays, commercial VoD services on the Internet like YouTube [2] and Hulu [3] are typically supported by CDNs. In RFC 3466, Internet Engineering Task Force (IETF) defined CDN as a type of content network which is a virtual network on top of a generic IP network. CDNs contain many infrastructures (edge servers) distributed across vast geographical areas. Clients can fetch the video streaming data from edge servers instead of the source server, avoiding the network congestion and source server overloaded efficiency.Modern CDN providers often build their system over cloud infrastructures to reduce the deployment and maintenance cost while extending the system scalability. From this sense, Lenk et al. [4] categorized Amazon’s CDN service CloudFront and Akamai’s EdgePlatform as higher infrastructure services. There is vast number of literatures concentrated on cloud-based CDN system. The recent AirLift system [5] and the CALMS system [6] demonstrated the feasibility of deploying video streaming applications in cloud-based CDN. Li et al. [7] regarded network congestion at cloud egress and latency to client as one of the major challenges for the current cloud system. They proposed an architecture which integrates CDN with cloud where global load balancing can be achieved with CDN. An experiment in the Microsoft Windows Azure public cloud demonstrated the effectiveness of their idea. Tran et al. [8] developed a content distribution network cloud architecture (CDNCA) based on quality of service (QoS) and quality of experience (QoE) criterions. Jin et al. [9] proposed a content-delivery-as-a-service (CoDaaS) framework to enable on-demand virtual content delivery service (vCDS) for user-generated content (UGC). Chia-Feng et al. [10] presented a cloud-based CDN (CCDN) platform which provides content delivery features with cloud storage and platform as a service in cloud computing field. Chen et al. [11] investigated a joint problem of building distribution paths and placing Web server replicas in CDNs driven by storage cloud to minimize the cost. Clearly, the techniques to migrate CDN service from traditional distributed computing systems to the cloud are an active research area.There are also many research efforts in industry focused on this area. A number of major enterprises develop their own cloud-based CDN systems. For example, Amazon CloudFront [12] is a web service for content delivery. It uses Amazon S3 (a cloud storage service) or EC2 (an infrastructure-as-a-service) as the underlying storage servers and edge servers. Akamai NetStorage [13] is another example of cloud storage service built for Akamai’s CDN. It is a geographically distributed cloud storage system which provides multiple terabytes of storage capacity. Limelight Networks [14] also builds many data centers by itself all over the world to support its CDN service.One of the key challenges for CDN providers is to design an appropriate request routing strategy so that CDN providers can obtain as much profit as possible while preserving good performance. In this paper, we investigate the request routing problem in the CDN-based VoD system. The system of our interest is shown in Figure1. It contains a dispatcher and a number of edge servers. Like Amazon CloudFront, our system can be implemented on a cloud infrastructure. CDN providers can rent virtual machines (VMs) from geographically distributed cloud providers or build their own distributed data centers (DCs). These VMs or DCs act as edge servers which directly transfer VoD streaming data to the clients. The load balance component from cloud system and the geo-aware request routing component from CDN system are integrated into the dispatcher. We assume the dispatcher works in a time-slotted fashion.Figure 1
A typical CDN-based VoD service system. The request routing task is fulfilled by the dispatcher. The request routing contains4 steps: (1) client requests arrive at the dispatcher; (2) the dispatcher samples the state of the servers and computes the request routing strategy; (3) the dispatcher returns the destination edge server information to the clients; (4) client requests are redirected to appropriate edge servers.Request routing problem is one of the most fundamental issues in the distributed online service providing system. It has received much attention in various environments over the years [15–18]. Among these works, some focused on probing for the design principles behind proprietary request routing algorithm of commercial enterprise and evaluating their effectiveness by using a measurement methodology [19, 20] and others preferred to treat the problem in a more analytical way [21–24]. Xu and Li [25, 26] used decomposition techniques in optimization theory to investigate the request routing problem in various settings. Tran et al. [27] developed a request routing scheme based on the QoE criterion. Qian and Rabinovich [28] developed a heuristic algorithm called permutation prefix clustering to solve the joint application placement and request routing problem. Dealer system [29] abstracts multilayer application into a directed graph where the vertices are application components and the edges are communications between vertices. Dealer tries to minimize response time by searching for a better combination approach of application components. CloudGPS system [30] and NetPaaS system [31] deal with the request routing problem in ISP-P2P and ISP-CDN environments. The highlight of the distributed cooperative request routing algorithms behind these systems is that they can benefit all entities (CDN, ISP, and P2P end user) within the system. In our work, we use the Markov decision process (MDP) [32] rather than static optimization techniques [33, 34] to model the system, since the dynamic nature of MDP can potentially yield remarkable performance improvements [21].Load balance factors must be considered while designing a request routing strategy; it has been intensively studied by the researchers [35–40]. An unbalanced load allocation may cause network congestion and deplete server computational resources and thus greatly degrade user experience. However, starting from the perspective of load balance alone is not enough, since the final goal of the VoD provider is to earn as much profit as possible, rather than only to guarantee the user experience. In a practical CDN-based VoD service system, local costs in different geographical regions, for example, the bandwidth rental cost and the server maintenance cost, are not equal. How to select appropriate server for a request so that the profit is maximized is our focus.There are many researches concentrated on reward-based dynamic request routing in web-based applications [22–24]. Unfortunately, neither of them can be directly applied to the VoD service for following reasons: (1) a video request will take up the resources of VoD servers throughout the whole viewing period, which is several orders of magnitude longer than a web-based request; (2) as long as a client begins to receive data from an edge server, it cannot be redirected to other edge servers arbitrarily, since this will disturb the continuity of the playback process and degrade the user experience.In this paper, we investigate the request routing problem in the VoD service by formulating it as a standard MDP, which can be theoretically solved by the classical algorithms like value iteration, policy iteration, or their variations. However, this MDP formulation is practically intractable due to the so-called the curse of dimensionality; that is, the problem size grows exponentially with the underling parameters. To address this issue, we propose two alternative approaches to approximately solve the problem. The first approach is to use a greedy strategy, that is, to focus on maximizing the reward which can be earned in current time slot, instead of the accumulated reward in the long run. The advantage of the greedy approach is its simplicity; for example, it can be implemented online. The drawback of this approach is that the performance deviation between the optimal strategy and the greedy strategy is unknown. To overcome it, we turn to the second approach—bounded-parameter Markov decision processes (BMDP). The BMDP was proposed by Givan et al. [41, 42] to approximately solve the MDP with a large state space. We use state aggregation technique to partition the overall state space and reformulate the request routing problem as a BMDP. The BMDP formulation has two advantages. (1) we can derive a B-optimal strategy aiming at maximizing the attainable reward in a BMDP model; (2) the upper bound value of the B-optimal strategy is the highest reward a feasible strategy can achieve in the original MDP model, so it can be served as a cornerstone to evaluate other strategies, for example, the greedy strategy. We further conduct experimental study to evaluate the effectiveness of these two algorithms. Simulation results show that the B-optimal strategy is a close-to-optimal request routing solution.This paper proceeds as follows. Section2 depicts the model in detail; Section 3 presents the MDP formulation of the request routing problem; in Section 4 we first provide a greedy algorithm to approximately solve the MDP and then reformulate the problem as a BMDP. The interval value iteration (IVI) algorithm is presented thereafter, and a comparison of the IVI algorithm with the traditional value iteration algorithm from the perspective of computational complexity is conducted; a numerical analysis is given in Section 5 followed by conclusions in Section 6.


## 2. System Model

We use a discrete time controlled queueing model to describe the VoD service system. The model is shown in Figure2. It consisted of a dispatcher and several edge servers located across a geographic region (e.g., a country). The dispatcher is a centralized controller which collects video requests and redirects them to appropriate edge servers. At a given time slot, the VoD edge servers transmit the video streaming data to each of its clients. At the end of a time slot, some clients close their streaming sessions and leave the system, while others prefer to stay and wait for receiving video stream in the next time slot. Upon each accepted request, the CDN provider can get rewards. Our focus is to find the optimal strategy which maximizes such rewards. Notations are summarized in Notation section.Figure 2
System model for a CDN-based VoD service.


### 2.1. Customer Model

Customer categorization is a common approach for studying the online service providing system. In this paper, we regard the partition by the video file that the clients are asking for as impractical since there may be hundreds of thousands of video files in a VoD system. As explained in the following section, the increase of customer types will dramatically raise the state space and action space of the problem, making it hard to solve. We use an alternative approach, that is, categorizing the customer according to (1) the expected viewing time length and (2) the average bitrates. The first standard ensures that all requests in a given time have the same departure probability (as we can see later), and the second one implies that they consume the same amount of resources. This categorization can be achieved by the following steps.(i)
Measure the expected viewing time for each video file.
(ii)
Group video files which have (approximately) the same expected viewing time and bitrates.
(iii)
If a customer asks for a video file which belongs to theith group, mark this request as type i.The usage of average bitrate is not an exact model since VoD providers sometimes employ a variable bit rate (VBR) approach like MPEG-4 to encode video files for reduction of the file size. This may induce the system to run out of resources if all requests achieve their peak rate at the same time. However, we believe that this impreciseness does not affect our overall model that much for two reasons: (1) the video streaming itself can tolerate packet losses or delay jitters to some extent and (2) the alignment of the peak rate periods of the video streams is rare [43]; we can use some moderate resource reservation strategies to effectively avoid the resource depletion in most cases.In each time slot, the number of typei video requests arriving at the dispatcher, that is, λ
i, is a random variable, which can be reasonably viewed as subject to some stationary probability distribution in VoD service. To avoid infinite state space problem, we assume that λ
i is a bounded nonnegative integer random variable.


### 2.2. Server Model

Each VoD edge server is modeled by a discrete time queueing system. The resource capacity of edge serverj, that is, output bandwidth, and so forth, is C
j. We assume that a type i request consumes ω
i unit of bandwidth. The resource consumption of all requests in a server cannot exceed its capacity limitation.In the VoD service, customers’ requests tend to “reside in” the system since the playback time of a video file is several orders of magnitude longer than the one in web-based application. We assume each accepted request must stay in the system for at least one time slot, and all departures happen at the end of a time slot. Each edge server does not log the state of an individual request, that is, the time a request has spent in the system, because this scheme is too resource consuming and not scalable as the number of requests grows. Therefore, we consider the probability that a request leaves the systemp
i is equal in every time slot. We have the following result.Lemma 1.
Suppose a typei request can stay in the system for at most T
-
i of time or K
=
⌈
T
-
i
/
Γ
⌉ of time slot; then
(1)
1
p
i
-
(
K
p
i
+
1
)
(
1
-
p
i
)
K
p
i
=
⌈
T
i
Γ
⌉
,
where Γ is the slot length and T
i is the average sojourn time of type i request in the system.Proof.
The proof is simply a calculation of expected sojourn time provided that a typei request can stay for at most K slots in the system. Consider
(2)
∑
k
=
1
K
‍
{
p
i
·
(
1
-
p
i
)
k
-
1
·
k
Γ
}
=
p
i
Γ
{
∑
k
=
1
∞
‍
k
(
1
-
p
i
)
k
-
1
-
∑
k
=
K
+
1
∞
‍
k
(
1
-
p
i
)
k
-
1
}
=
p
i
Γ
{
1
p
i
2
-
(
K
p
i
+
1
)
(
1
-
p
i
)
K
p
i
2
}
=
T
i
,
completing the proof.It is not easy to get the analytical solution ofp
i from (1). We propose the following methods to get numerical value of p
i.(i)
WhenK is small, we can plot the left hand side of (1) with p
i as a variable and locate p
i directly from the figure, as illustrated in Figure 3.
(ii)
WhenK is large, the second term in the left hand side of (1) tends to 0 and can be omitted, yielding an approximation of
(3)
p
i
≈
⌈
Γ
T
i
⌉
.Figure 3
An example to find departure probability with a smallK
=
10. T
i
=
50
s, Γ
=
10
s. The upper bound of sojourn time is 100
s. We obtain that p
i
≈
0.25 in this scenario.


## 2.1. Customer Model

Customer categorization is a common approach for studying the online service providing system. In this paper, we regard the partition by the video file that the clients are asking for as impractical since there may be hundreds of thousands of video files in a VoD system. As explained in the following section, the increase of customer types will dramatically raise the state space and action space of the problem, making it hard to solve. We use an alternative approach, that is, categorizing the customer according to (1) the expected viewing time length and (2) the average bitrates. The first standard ensures that all requests in a given time have the same departure probability (as we can see later), and the second one implies that they consume the same amount of resources. This categorization can be achieved by the following steps.(i)
Measure the expected viewing time for each video file.
(ii)
Group video files which have (approximately) the same expected viewing time and bitrates.
(iii)
If a customer asks for a video file which belongs to theith group, mark this request as type i.The usage of average bitrate is not an exact model since VoD providers sometimes employ a variable bit rate (VBR) approach like MPEG-4 to encode video files for reduction of the file size. This may induce the system to run out of resources if all requests achieve their peak rate at the same time. However, we believe that this impreciseness does not affect our overall model that much for two reasons: (1) the video streaming itself can tolerate packet losses or delay jitters to some extent and (2) the alignment of the peak rate periods of the video streams is rare [43]; we can use some moderate resource reservation strategies to effectively avoid the resource depletion in most cases.In each time slot, the number of typei video requests arriving at the dispatcher, that is, λ
i, is a random variable, which can be reasonably viewed as subject to some stationary probability distribution in VoD service. To avoid infinite state space problem, we assume that λ
i is a bounded nonnegative integer random variable.


## 2.2. Server Model

Each VoD edge server is modeled by a discrete time queueing system. The resource capacity of edge serverj, that is, output bandwidth, and so forth, is C
j. We assume that a type i request consumes ω
i unit of bandwidth. The resource consumption of all requests in a server cannot exceed its capacity limitation.In the VoD service, customers’ requests tend to “reside in” the system since the playback time of a video file is several orders of magnitude longer than the one in web-based application. We assume each accepted request must stay in the system for at least one time slot, and all departures happen at the end of a time slot. Each edge server does not log the state of an individual request, that is, the time a request has spent in the system, because this scheme is too resource consuming and not scalable as the number of requests grows. Therefore, we consider the probability that a request leaves the systemp
i is equal in every time slot. We have the following result.Lemma 1.
Suppose a typei request can stay in the system for at most T
-
i of time or K
=
⌈
T
-
i
/
Γ
⌉ of time slot; then
(1)
1
p
i
-
(
K
p
i
+
1
)
(
1
-
p
i
)
K
p
i
=
⌈
T
i
Γ
⌉
,
where Γ is the slot length and T
i is the average sojourn time of type i request in the system.Proof.
The proof is simply a calculation of expected sojourn time provided that a typei request can stay for at most K slots in the system. Consider
(2)
∑
k
=
1
K
‍
{
p
i
·
(
1
-
p
i
)
k
-
1
·
k
Γ
}
=
p
i
Γ
{
∑
k
=
1
∞
‍
k
(
1
-
p
i
)
k
-
1
-
∑
k
=
K
+
1
∞
‍
k
(
1
-
p
i
)
k
-
1
}
=
p
i
Γ
{
1
p
i
2
-
(
K
p
i
+
1
)
(
1
-
p
i
)
K
p
i
2
}
=
T
i
,
completing the proof.It is not easy to get the analytical solution ofp
i from (1). We propose the following methods to get numerical value of p
i.(i)
WhenK is small, we can plot the left hand side of (1) with p
i as a variable and locate p
i directly from the figure, as illustrated in Figure 3.
(ii)
WhenK is large, the second term in the left hand side of (1) tends to 0 and can be omitted, yielding an approximation of
(3)
p
i
≈
⌈
Γ
T
i
⌉
.Figure 3
An example to find departure probability with a smallK
=
10. T
i
=
50
s, Γ
=
10
s. The upper bound of sojourn time is 100
s. We obtain that p
i
≈
0.25 in this scenario.


## 3. Problem Formulation

The above model can be formulated as a standard discrete time Markov decision process (MDP). We illustrate the system dynamics in Table1. During (
t
-
1
,
t
) the dispatcher buffers the incoming requests in its waiting queue. In time point t, the dispatcher samples the system state including(1)
the arrival vectorλ
(
t
)
=
{
λ
i
(
t
)
},  i
∈
I, which describes the number of type i requests in the waiting queue;
(2)
the server load matrixN
(
t
)
=
{
n
i
j
(
t
)
},  i
∈
I and j
∈
J, which describes the number of type i requests in edge server j,and then it makes a decision. The action is a matrix a
(
t
)
=
{
a
i
j
(
t
)
} denoting the number of type i requests forwarded to edge server j. The system then proceeds to the time (
t
+
1
)
-, where a reward of R
(
N
(
t
)
,
a
(
t
)
) is received and some requests leave the system. The system transits to another state. The MDP formulation of the problem is given as follows.Table 1
System dynamics.
Time
Event
t
The dispatcher samples the system state(
λ
(
t
)
,
N
(
t
)
), and make the decision a
(
t
) forwarding the buffered requests to appropriate edge servers (or rejecting some requests).
(
t
,
t
+
1
)
Requests arrive and are buffered in the dispatcher's waiting queue.
(
t
+
1
)
-
Some requests in the service queue leave the system, and the system transits to the next state.States. Denote the state space by S and denote one element in S by (
N
,
λ
). We view the actual state is a function of time, that is, (
N
(
t
)
,
λ
(
t
)
). Note that λ can be fully observed by the dispatcher.Decision Epoch. Decision epoch t is at the start of a slot with length Γ; namely, t
∈
{
0
,
Γ
,
2
Γ
,
…
,
n
Γ
,
…
}.Actions. At the beginning of the tth slot, the dispatcher can make a deterministic action a
(
t
) subject to the following constraints:
(4)
∑
j
∈
J
‍
a
i
j
(
t
)
≤
λ
i
(
t
)
,
∀
i
∈
I
(5)
∑
i
∈
I
‍
ω
i
(
a
i
j
(
t
)
+
n
i
j
(
t
)
)
≤
C
j
,
∀
j
∈
J
,
where (4) is the flow conservation constraint representing the forwarded requests which cannot exceed the arrived (and if forwarded requests are less than the arrived, some requests must be rejected) and (5) implies the bandwidth constraints.Transition Probability. Since the arrival vector is a stochastic vector and is independent with the server load matrix, we focus mainly on the changes of the latter one. The following dynamic equation can be obtained immediately:
(6)
N
(
t
+
1
)
=
N
(
t
)
+
a
(
t
)
-
y
(
t
)
,
where y
(
t
)
=
{
y
i
j
(
t
)
}, with 0
≤
y
i
j
(
t
)
≤
N
i
j
(
t
)
+
a
i
j
(
t
), i
∈
I, and j
∈
J, denotes the number of type i departures in server j at the end of tth time slot. Let g
i
j
t
(
n
) be the probability distribution function of y
i
j
(
t
); namely, g
i
j
t
(
n
)
=
Pr
(
y
i
j
(
t
)
=
n
), and the explicit expression of g
i
j
t
(
n
) is
(7)
g
i
j
t
(
n
)
=
{
(
n
i
j
(
t
)
+
a
i
j
(
t
)
n
)
(
1
-
p
i
)
n
i
j
(
t
)
+
a
i
j
(
t
)
-
n
p
i
n
,
n
≤
n
i
j
(
t
)
+
a
i
j
(
t
)
0
,
otherwise
.
Let λ
i be subject to some discrete probability distribution function f
i
(
x
); that is, Pr
(
λ
i
=
n
)
=
f
i
(
n
); then the transition probability of the system is given by
(8)
P
(
N
(
t
+
1
)
,
λ
(
t
+
1
)
∣
N
(
t
)
,
λ
(
t
)
,
a
(
t
)
)
=
{
0
,
if
∀
j
,
n
i
j
(
t
+
1
)
>
n
i
j
+
a
i
j
(
t
)
∏
i
∈
I
‍
f
i
(
λ
i
(
t
+
1
)
)
·
∏
j
∈
J
‍
∏
i
∈
I
‍
g
i
j
t
(
n
i
j
(
t
)
+
a
i
j
(
t
)
-
n
i
j
(
t
+
1
)
)
,
otherwise
.Rewards. The reward is defined by the VoD service provider, often in the form of r
-
c, where r and c are the revenue and the cost for serving a request, respectively. These two parameters can be defined from different perspectives. For example, from per request perspective, they can be earned right after a request is accepted (pay-per-view); from temporal perspective, they depend upon the sojourn time in the system of each request. In this paper we adopt the latter one. This is reasonable since the more time the client spends in the system, the more profits the VoD provider can potentially earn (e.g., by means of periodically popping up the embedded advertisements). The rewards earned in the tth slot are
(9)
R
(
N
(
t
)
,
λ
(
t
)
,
a
(
t
)
)
=
∑
i
∈
I
‍
∑
j
∈
J
‍
(
n
i
j
(
t
)
+
a
i
j
(
t
)
)
×
(
r
i
-
c
i
j
)
,
where n
i
j
(
t
)
+
a
i
j
(
t
) is the number of type i clients in server j during the t
th slot and r
i
-
c
i
j is the net gain for a type i request being served in server j.Optimization Objective. The optimization objective is to maximize the expected accumulated long term system rewards. In practice the system is actually a finite horizon MDP since the arrival distribution is stationary only in a certain period (let us call itstationary period). However, we could use an infinite horizon MDP with discounted object function
(10)
E
{
∑
t
=
0
∞
‍
δ
t
R
(
N
(
t
)
,
λ
(
t
)
,
a
(
t
)
)
}
to approximate it, where 0
≤
δ
≤
1 is the discounted factor, because the length of the stationary period (often in the order of several hours) is much longer than the length of the time slot (often in the order of seconds). This form of objective function is also used in [22]. Consider
(11)
V
(
N
(
t
)
,
λ
(
t
)
)
=
max
⁡
a
(
t
)
{
∑
(
N
(
t
+
1
)
,
λ
(
t
+
1
)
)
∈
S
P
(
N
(
t
+
1
)
,
λ
(
t
+
1
)
∣
N
(
t
)
,
λ
(
t
)
,
a
(
t
)
)
‍
R
(
N
(
t
)
,
λ
(
t
)
,
a
(
t
)
)
mmmmmi
+
δ
∑
(
N
(
t
+
1
)
,
λ
(
t
+
1
)
)
∈
S
P
(
λ
(
t
+
1
)
∣
N
(
t
)
,
λ
(
t
)
,
a
(
t
)
N
(
t
+
1
)
,
‍
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
i
λ
(
t
+
1
)
∣
N
(
t
)
,
λ
(
t
)
,
m
m
m
m
m
m
m
m
m
m
m
m
m
m
i
m
m
a
(
t
)
)
·
V
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
×
(
N
(
t
+
1
)
,
λ
(
t
+
1
)
)
∑
(
N
(
t
+
1
)
,
λ
(
t
+
1
)
)
∈
S
P
(
N
(
t
+
1
)
,
λ
(
t
+
1
)
∣
N
(
t
)
,
λ
(
t
)
,
a
(
t
)
)
‍
}
.The value function can be established as (11), and classical algorithms like value iteration or policy iteration can be used to solve this MDP. However, the above MDP model obviously suffers from the so-called state space explosion problem. To see that, suppose a system with p kinds of requests, q edge servers, and capacity r for each edge server; the total number of states with respect to N is
(12)
(
∑
i
=
0
r
‍
(
i
+
p
-
1
i
)
)
q
.
The computational cost of traditional algorithm, in which all states must be visited in each iteration, will be prohibitive. Therefore we need alternative approaches to obtain approximate solutions.


## 4. Solving the MDP Model Approximately

In this section we present two approaches to approximately solve the above MDP model of request routing problem. The first approach is the greedy strategy, which is an integer linear programming problem aiming at maximizing the reward in current time slot. The second approach is the bounded-parameter MDP (BMDP) strategy, which aggregates the state space of the original MDP model and applies the interval value iteration algorithm on the aggregated model to obtain the B-optimal solution. We finally discuss the computational complexity of the BMDP strategy.


### 4.1. A Greedy Approximation Strategy

One of the simplest approximations is the greedy strategy, which focuses on maximizing the reward in each current slot instead of the cumulative reward in the long run. The problem can be summarized as an integer linear programming as follows:(13)
max
⁡
a
(
t
)
∑
i
∈
I
‍
∑
j
∈
J
‍
a
i
j
(
t
)
(
r
i
-
c
i
j
)
subject to constraints (4) and (5).The idea behind the greedy strategy is straightforward: ignore the arrival pattern of requests and accept as many profitable requests as possible in a current slot. In fact, the greedy strategy does not require the server stateN. Instead, it only needs to keep track of the total load of each individual server as
(14)
L
=
{
L
j
}
,
j
∈
J
,
where
L
j
=
∑
i
∈
I
‍
n
i
j
(
t
)
.
We will evaluate the greedy strategy in Section 5.The greatest advantage of the greedy strategy is its simplicity. Since it involves no iteration operations as in the classical iterative algorithm, its computational time is much smaller and thus can be implemented online. However, the biggest flaw of greedy strategy is that we do not know how far the profits of the greedy strategy deviate from the profits of the optimal strategy. This motivates us to find another approach which can provide some bounding information. In the following subsection, we provide the BMDP approach, which satisfies this property.


### 4.2. The Bounded-Parameter MDP (BMDP) Approximation Strategy

The BMDP was introduced by Givan et al. [41, 42] to provide an approximate approach for solving the MDP with a large state space; it can be categorized into a more general class known as Markov decision processed with imprecisely known transition probabilities (MDPIPs).


#### 4.2.1. BMDP Preliminaries

A BMDPM
↕ is a four-tuple {
S
,
A
,
R
↕
,
P
↕
}. It is different from traditional MDP (also calledexact MDP) in the sense that the reward function in each state R
↕
(
s
) and the transition probability P
↕
(
s
′
∣
s
,
a
) are specified by closed intervals [
R
↓
(
p
)
,
R
↑
(
p
)
] and [
P
↓
(
s
′
∣
s
,
a
)
,
P
↑
(
s
′
∣
s
,
a
)
], respectively, rather than exact point values. An exact MDP M
=
{
S
′
,
A
′
,
R
′
,
P
′
} is said to be contained in a BMDP M
↕ (M
∈
M
↕) as long as S
′
=
S, A
′
=
A, R
′
∈
R
↕, and P
′
∈
P
↕.Given a policyπ, the interval value function V
↕
π is defined by
(15)
V
↕
π
(
s
)
=
[
min
⁡
M
∈
M
↕
V
M
,
π
(
s
)
,
max
⁡
M
∈
M
↕
V
M
,
π
(
s
)
]
,
where V
M
,
π
(
s
)
=
R
M
(
s
)
+
δ
∑
s
′
∈
S
‍
P
M
(
s
′
∣
s
,
a
)
V
M
,
π
(
s
′
) is the traditional value function for a specific exact MDP M
∈
M
↕. It can be proved that (see reference [41]) there exists a MDP M
∈
M
↕ which maximizes/minimizes V
M
,
π
(
s
) for all s
∈
S simultaneously. We call such MDP π
-
m
a
x
i
m
i
z
i
n
g/π
-
m
i
n
i
m
i
z
i
n
g MDP.The interval value functions cannot be compared using traditional MDP standard, which focuses on point values. To evaluate how “good" a policyπ can achieve, we must define a scheme to compare interval value functions. In this paper we define the interval greater operator ≳ given by
(16)
V
↕
1
≳
V
↕
2
⟺
V
↑
1
≥
V
↑
2
∨
(
V
↑
1
=
V
↑
2
∧
V
↓
1
≥
V
↓
2
)
.The interval value iteration (IVI) algorithms with provable convergence property can be used to obtain the optimal solution to the BDMP; that is,(17)
IV
I
↕
opt
(
V
↕
)
(
s
)
=
max
⁡
a
∈
A
(
s
)
[
min
⁡
M
∈
M
↕
V
I
M
,
a
(
V
↓
)
(
s
)
,
max
⁡
M
∈
M
↕
V
I
M
,
a
(
V
↑
)
(
s
)
]
with V
I
M
,
a
(
V
)
(
s
)
=
R
M
(
s
)
+
δ
∑
s
′
∈
S
‍
P
M
(
s
′
∣
s
,
a
)
V
(
s
′
).The IVI algorithm (17) starts with an arbitrary interval value function V
↕
=
[
V
↓
,
V
↑
] with V
↓
≤
V
↑. The operation of finding exact MDPs M
∈
M
↕ inside the square bracket is equivalent to searching for order-maximizingMDPs with respect to state order sequences of decreasing V
↑ and increasing V
↓. Formal definition of the order-maximizing MDP for a specific state order sequence O
=
s
1
s
2
⋯
s
n is given by the following definition.Definition 2.
The order-maximizing indexr for state s and action a with respect to order O is
(18)
arg
max
⁡
1
≤
r
≤
n
{
∑
i
=
1
r
-
1
‍
P
↑
(
s
i
∣
s
,
a
)
+
∑
i
=
r
n
‍
P
↓
(
s
i
∣
s
,
a
)
}
.
The order-maximizing MDP is an exact MDP M
O
∈
M
↕ satisfying
(19)
P
M
O
(
s
i
∣
s
,
a
)
=
{
P
↑
(
s
i
∣
s
,
a
)
,
if
i
<
r
,
P
↓
(
s
i
∣
s
,
a
)
,
if
i
>
r
,
P
M
O
(
s
r
∣
s
,
a
)
=
1
-
∑
i
=
1
,
i
≠
r
i
=
n
‍
P
M
O
(
s
i
∣
s
,
a
)
.Note that themax
⁡ operator in (17) uses (16) to compare interval value functions. It can be proved (see [41]) that the IVI algorithm will finally converge to an interval value function [
V
↓
opt
,
V
↑
opt
] and an associated solution which we call B-optimal policy. The upper bound of interval value function V
↑
opt for the B-optimal policy is the possible best reward one can get from the BMDP M
↕; therefore, it can serve as a cornerstone to evaluate how far the value of a given strategy deviates from the one of possible optimal strategies for any exact MDP M
∈
M
↕. V
↓
opt is the possible worst case performance of the B-optimal strategy.In our application, states in the BMDPM
↕ can be viewed as aggregations of states in the exact MDP M. The parameter intervals in M
↕ represent the parameter ranges of states in M which belong to the same BMDP state. From this viewpoint M
↕ is a “smaller” approximation to the original M.


#### 4.2.2. Model Reduction

The intuition behind our aggregation scheme is to overlook the request type in the server load matrixN. We can construct an aggregate state space S
′ with an element (
L
,
λ
), where L is the server load vector specified in (14). The system dynamics equation becomes
(20)
L
(
t
+
1
)
=
L
(
t
)
+
a
(
t
)
·
e
-
Y
(
t
)
,
where e is a j-dimension unit vector and Y is the total departures vector. Equation (20) means that the change of server state only depends upon the number of requests assigned to and departing from the server regardless of their types. With this abstraction, the number of state spaces with respect to L is r
q, a great reduction compared to (12).


#### 4.2.3. The BMDP Reformulation

First we present the following lemma which is used to obtain the interval transition function of the BMDP formulation.Lemma 3.
Suppose the system is in a particular aggregated state(
L
(
t
)
,
λ
(
t
)
) at the tth slot; the probability of n clients leaving edge server j in this slot, namely, P
r
(
Y
j
(
t
)
=
n
), can be bounded by
(21)
[
(
L
j
(
t
)
+
∑
i
∈
I
a
i
j
(
t
)
n
)
p
min
⁡
n
(
1
-
p
max
⁡
)
L
j
(
t
)
+
∑
i
∈
I
‍
a
i
j
(
t
)
-
n
,
(
L
j
(
t
)
+
∑
i
∈
I
a
i
j
(
t
)
n
)
p
max
⁡
n
(
1
-
p
min
⁡
)
L
j
(
t
)
+
∑
i
∈
I
‍
a
i
j
(
t
)
-
n
]
provided that n
≤
L
j
(
t
)
+
∑
i
∈
I
‍
a
i
j
(
t
), where p
max
⁡
=
max
⁡
i
∈
I
p
i and p
min
⁡
=
min
⁡
i
∈
I
p
i.Proof.
We show how to derive the upper bound; the lower bound can be obtained using the same idea. Pick any exact MDP state(
N
(
t
)
,
λ
(
t
)
) which belongs to the aggregated state (
L
(
t
)
,
λ
(
t
)
); that is, ∑
i
∈
I
‍
n
i
j
(
t
)
=
L
j
(
t
). For server j in state (
N
(
t
)
,
λ
(
t
)
), there are a total (
L
j
(
t
)
+
∑
i
∈
I
‍
a
i
j
(
t
)
n
) number of cases such that n clients leave server j. Choose a particular case where the number of type i requests that leave server j is k
i
j; we have ∑
i
∈
I
‍
k
i
j
(
t
)
=
n. The probability of the occurrence of this case is
(22)
∏
i
∈
I
‍
p
i
k
i
j
×
∏
i
∈
I
‍
(
1
-
p
i
)
n
i
j
(
t
)
+
a
i
j
(
t
)
-
k
i
j
≤
p
max
⁡
∑
i
∈
I
‍
k
i
j
(
1
-
p
min
⁡
)
∑
i
∈
I
‍
n
i
j
(
t
)
+
a
i
j
(
t
)
-
k
i
j
=
p
max
⁡
n
(
1
-
p
min
⁡
)
L
j
(
t
)
+
∑
i
∈
I
‍
a
i
j
(
t
)
-
n
.
The results can be followed immediately.We can now reformulate the problem with the BMDP.States. The aggregated state space is S
′, with an element denoted by (
L
,
λ
).Decision Epoch and Actions. Decision epoch and actions are the same as in the original MDP model.Interval Transition Probability. Note that, in the BMDP formulation, the transition probability is a closed interval. First observe that
(23)
P
(
L
(
t
+
1
)
,
λ
(
t
+
1
)
∣
L
(
t
)
,
λ
(
t
)
,
a
(
t
)
)
=
∏
i
∈
I
‍
f
i
(
λ
i
(
t
+
1
)
)
·
∏
j
∈
J
‍
P
(
L
j
(
t
+
1
)
∣
L
j
(
t
)
,
λ
(
t
)
,
a
(
t
)
)
=
∏
i
∈
I
‍
f
i
(
λ
i
(
t
+
1
)
)
mmmmi
·
∏
j
∈
J
‍
P
(
Y
j
(
t
)
=
L
j
(
t
)
+
∑
i
∈
I
‍
a
i
j
(
t
)
-
L
j
(
t
+
1
)
)
.
Combining with Lemma 3, the transition probability in (23) can be bounded by the interval transition shown in (24) with Θ
j
(
t
)
=
L
j
(
t
)
+
∑
i
∈
I
‍
a
i
j
(
t
) and Y
j
(
t
)
=
L
j
(
t
)
+
∑
i
∈
I
‍
a
i
j
(
t
)
-
L
j
(
t
+
1
) denoting the number of requests and the number of departures in t
th slot in server j regardless of their types, respectively. Consider
(24)
P
↕
(
L
(
t
+
1
)
,
λ
(
t
+
1
)
∣
L
(
t
)
,
λ
(
t
)
,
a
(
t
)
)
=
{
[
0,0
]
,
if
L
j
(
t
)
+
∑
i
∈
I
a
i
j
(
t
)
≤
L
j
(
t
+
1
)
[
∏
i
∈
I
‍
p
min
⁡
∑
j
∈
J
‍
Y
j
(
t
)
(
1
-
p
max
⁡
)
∑
j
∈
J
‍
L
j
(
t
+
1
)
m
×
∏
i
∈
I
‍
f
i
(
λ
i
(
t
+
1
)
)
∏
j
∈
J
(
Θ
j
(
t
)
Y
j
(
t
)
)
‍
,
m
p
max
⁡
∑
j
∈
J
‍
Y
j
(
t
)
(
1
-
p
min
⁡
)
∑
j
∈
J
‍
L
j
(
t
+
1
)
m
×
∏
i
∈
I
‍
f
i
(
λ
i
(
t
+
1
)
)
∏
j
∈
J
‍
(
Θ
j
(
t
)
Y
j
(
t
)
)
]
,
otherwise
.Interval Rewards. The reward consists of two parts. The first part is the reward for the action a
(
t
), which is a fixed value given by ∑
j
∈
j
‍
∑
i
∈
I
‍
a
i
j
(
t
)
(
r
i
-
c
i
j
). The second part is a closed interval [
m
L
(
t
)
,
M
L
(
t
)
], with
(25)
M
=
max
⁡
i
∈
I
,
j
∈
J
{
r
i
-
c
i
j
}
,
m
=
min
⁡
i
∈
I
,
j
∈
J
{
r
i
-
c
i
j
}
.
The interval reward function can then be expressed by
(26)
R
↕
(
L
(
t
)
,
λ
(
t
)
,
a
(
t
)
)
=
[
m
L
(
t
)
+
∑
j
∈
j
‍
∑
i
∈
I
‍
a
i
j
(
t
)
(
r
i
-
c
i
j
)
,
m
m
m
i
M
L
(
t
)
+
∑
j
∈
j
‍
∑
i
∈
I
‍
a
i
j
(
t
)
(
r
i
-
c
i
j
)
]
.


#### 4.2.4. The Interval Value Iteration (IVI) Algorithm

We illustrate the IVI algorithm in detail in Algorithms1 and 2.Algorithm 1:Solutions to the BMDP formulation.
Input: a BMDP M
↕
=
{
S
,
A
,
P
↕
,
R
↕
}
Output:  V
↕ and π
(1) Createπ; {
π holds the strategy in each iteration.}
(2) CreateV
↕; {
V
↕ is an initial interval value function.}
(3)loop
(4)V
↕
=
IVI
↕
opt
(
M
↕
,
V
↕
,
&
π
);
(5)end loopAlgorithm 2:Interval value iteration (IVI
↕) algorithm.
Input: a BMDP M
↕, a value function V
↕, and a place π for holding the policy in current iteration
Output:  V
↕
opt
′ and π
opt
(1)Create O
up, O
down;  {
O
up and O
down hold order sequence of states in M
↕, i.e., s
1
s
2
,
…
,
s
n
.
}
(2)Create P
up
′, P
down
′; {
P
up
′ and P
down
′ hold the transition probabilities for the order-maximizing MDP with respect
to order O
up and O
down, respectively.}
(3)Create r
up, r
down; {
r
up and r
down is the order-maximizing index for order sequences O
up and O
down, respectively.}
(4)Create i; {
i is the index into an ordering O.}
(5)
O
up
=
Sort_Decreasing_Order
(
V
↑
);
(6)
O
down
=
Sort_Increasing_Order
(
V
↓
);
(7)
for all  s
∈
S  do
(8) for all  a
∈
A  do
(9)  r
up
=
Order_Maximizing_Ind
(
M
↕
,
O
up
,
s
,
a
);
(10)r
down
=
Order_Maximizing_Ind
(
M
↕
,
O
down
,
s
,
a
);
{find order-maximizing index for transition probability in state s under action a according to (18).}
(11)for  i
=
1 to n  do
(12)    UpdateP
up
′
(
s
O
down
(
i
)
∣
s
,
a
) and P
down
′
(
s
O
up
(
i
)
∣
s
,
a
) according to (19);
(13)end for
(14)end for
(15)V
↑
′
=
max
a
⊆
A
(
s
)
⁡
R
↑
(
s
,
a
)
+
δ
∑
s
′
∈
S
‍
P
up
′
(
s
′
s
,
a
)
V
↑
(
s
′
);(*)
(16)if  |
a
|
=
1 and a
=
{
a
}  then
(17)V
↓
′
=
R
↓
(
s
,
a
)
+
δ
∑
s
′
∈
S
‍
P
down
′
(
s
′
s
,
a
)
V
↓
(
s
′
);
(18)π
(
s
)
=
a;
(19)else
(20)V
↓
′
=
max
a
∈
a
⁡
R
↓
(
s
,
a
)
+
δ
∑
s
′
∈
S
‍
P
down
′
(
s
′
s
,
a
)
V
↓
(
s
′
);(**)
(21)π
(
s
)
=
a;
(22)end if
(23)end ifAlgorithm1 takes the above BMDP model M
↕ as input. It first chooses an initial interval value function V
↕ and then iteratively calls function IVI. The algorithm finishes with an interval value function V
↕ and a corresponding policy π.Algorithm2 captures the essence of (17). The increasing state order of V
↑ and the decreasing state order of V
↓ are stored in O
up and O
down. For each state s and action a, the algorithm computes the order-maximizing indices r
up and r
down for order sequences O
up and O
down and forms two order-maximizing MDPs with transition probabilities P
up
′ and P
down
′. Using P
up
′, the set of actions a which maximizes the upper bound V
↑
′ is identified. If a contains only one element, for example, a
=
{
a
}, then a is the B-optimal action in this state and the lower bound can be obtained immediately. Otherwise, an action a
∈
a which maximizes the lower bound V
↓
′ is chosen as the B-optimal action.


#### 4.2.5. A Word on Computational Complexity

(i)
Space Complexity. Although the memory consumption of a single state in the BMDP model is a bit larger than the one in the MDP model due to the interval transition probability and the interval reward, but since the aggregation scheme in our BMDP formulation dramatically reduces the state space of edge servers from (
∑
i
=
0
r
(
i
+
p
-
1
i
)
)
q to r
q, the total memory space needed for storing the BMDP model is significantly less than the MDP model. On the other hand, the IVI algorithm only needs additional O
up and O
down to store order sequences in BMDP model, r
up and r
down to store order-maximizing indices, and P
up
′ and P
down
′ to store transition probabilities for the π
-maximizing MDP and the π
-minimizing MDP, respectively. In all, the memory space needed to store the BMDP model and implement the IVI algorithm decreases greatly compared with the memory space needed for the MDP model.
(ii)
Time Complexity. In the IVI algorithm, the first optimization problem (*) is much easier than problem (11) in traditional value iteration algorithm since the computation of the expectation in the Bellman equation involves much less states. There are three extra computational burdens in the IVI algorithm: (1) sorting states to obtain O
up and O
down (lines 5 and 6 in Algorithm 2), which take O
(
2
n
2
) in worst case using Quicksort algorithm; (2) finding the order-maximizing indices and computing the transition probabilities for the π
-maximizing MDP and the π
-minimizing MDP (lines 9, 10, and 12 in Algorithm 2), which take O
(
4
n
) in worst case; (3) finding a unique solution a
∈
a to the problem (*
*) which maximizes the lower bound V
↓ (line 20 in Algorithm 2). In this step we use the exhaustive search, so the time complexity is O
(
|
a
|
). However, regarding a which is usually a small set, it will not take too long to complete the search. Thus, the total extra time complexity is O
(
2
n
2
+
4
n
+
|
a
|
).


## 4.1. A Greedy Approximation Strategy

One of the simplest approximations is the greedy strategy, which focuses on maximizing the reward in each current slot instead of the cumulative reward in the long run. The problem can be summarized as an integer linear programming as follows:(13)
max
⁡
a
(
t
)
∑
i
∈
I
‍
∑
j
∈
J
‍
a
i
j
(
t
)
(
r
i
-
c
i
j
)
subject to constraints (4) and (5).The idea behind the greedy strategy is straightforward: ignore the arrival pattern of requests and accept as many profitable requests as possible in a current slot. In fact, the greedy strategy does not require the server stateN. Instead, it only needs to keep track of the total load of each individual server as
(14)
L
=
{
L
j
}
,
j
∈
J
,
where
L
j
=
∑
i
∈
I
‍
n
i
j
(
t
)
.
We will evaluate the greedy strategy in Section 5.The greatest advantage of the greedy strategy is its simplicity. Since it involves no iteration operations as in the classical iterative algorithm, its computational time is much smaller and thus can be implemented online. However, the biggest flaw of greedy strategy is that we do not know how far the profits of the greedy strategy deviate from the profits of the optimal strategy. This motivates us to find another approach which can provide some bounding information. In the following subsection, we provide the BMDP approach, which satisfies this property.


## 4.2. The Bounded-Parameter MDP (BMDP) Approximation Strategy

The BMDP was introduced by Givan et al. [41, 42] to provide an approximate approach for solving the MDP with a large state space; it can be categorized into a more general class known as Markov decision processed with imprecisely known transition probabilities (MDPIPs).


### 4.2.1. BMDP Preliminaries

A BMDPM
↕ is a four-tuple {
S
,
A
,
R
↕
,
P
↕
}. It is different from traditional MDP (also calledexact MDP) in the sense that the reward function in each state R
↕
(
s
) and the transition probability P
↕
(
s
′
∣
s
,
a
) are specified by closed intervals [
R
↓
(
p
)
,
R
↑
(
p
)
] and [
P
↓
(
s
′
∣
s
,
a
)
,
P
↑
(
s
′
∣
s
,
a
)
], respectively, rather than exact point values. An exact MDP M
=
{
S
′
,
A
′
,
R
′
,
P
′
} is said to be contained in a BMDP M
↕ (M
∈
M
↕) as long as S
′
=
S, A
′
=
A, R
′
∈
R
↕, and P
′
∈
P
↕.Given a policyπ, the interval value function V
↕
π is defined by
(15)
V
↕
π
(
s
)
=
[
min
⁡
M
∈
M
↕
V
M
,
π
(
s
)
,
max
⁡
M
∈
M
↕
V
M
,
π
(
s
)
]
,
where V
M
,
π
(
s
)
=
R
M
(
s
)
+
δ
∑
s
′
∈
S
‍
P
M
(
s
′
∣
s
,
a
)
V
M
,
π
(
s
′
) is the traditional value function for a specific exact MDP M
∈
M
↕. It can be proved that (see reference [41]) there exists a MDP M
∈
M
↕ which maximizes/minimizes V
M
,
π
(
s
) for all s
∈
S simultaneously. We call such MDP π
-
m
a
x
i
m
i
z
i
n
g/π
-
m
i
n
i
m
i
z
i
n
g MDP.The interval value functions cannot be compared using traditional MDP standard, which focuses on point values. To evaluate how “good" a policyπ can achieve, we must define a scheme to compare interval value functions. In this paper we define the interval greater operator ≳ given by
(16)
V
↕
1
≳
V
↕
2
⟺
V
↑
1
≥
V
↑
2
∨
(
V
↑
1
=
V
↑
2
∧
V
↓
1
≥
V
↓
2
)
.The interval value iteration (IVI) algorithms with provable convergence property can be used to obtain the optimal solution to the BDMP; that is,(17)
IV
I
↕
opt
(
V
↕
)
(
s
)
=
max
⁡
a
∈
A
(
s
)
[
min
⁡
M
∈
M
↕
V
I
M
,
a
(
V
↓
)
(
s
)
,
max
⁡
M
∈
M
↕
V
I
M
,
a
(
V
↑
)
(
s
)
]
with V
I
M
,
a
(
V
)
(
s
)
=
R
M
(
s
)
+
δ
∑
s
′
∈
S
‍
P
M
(
s
′
∣
s
,
a
)
V
(
s
′
).The IVI algorithm (17) starts with an arbitrary interval value function V
↕
=
[
V
↓
,
V
↑
] with V
↓
≤
V
↑. The operation of finding exact MDPs M
∈
M
↕ inside the square bracket is equivalent to searching for order-maximizingMDPs with respect to state order sequences of decreasing V
↑ and increasing V
↓. Formal definition of the order-maximizing MDP for a specific state order sequence O
=
s
1
s
2
⋯
s
n is given by the following definition.Definition 2.
The order-maximizing indexr for state s and action a with respect to order O is
(18)
arg
max
⁡
1
≤
r
≤
n
{
∑
i
=
1
r
-
1
‍
P
↑
(
s
i
∣
s
,
a
)
+
∑
i
=
r
n
‍
P
↓
(
s
i
∣
s
,
a
)
}
.
The order-maximizing MDP is an exact MDP M
O
∈
M
↕ satisfying
(19)
P
M
O
(
s
i
∣
s
,
a
)
=
{
P
↑
(
s
i
∣
s
,
a
)
,
if
i
<
r
,
P
↓
(
s
i
∣
s
,
a
)
,
if
i
>
r
,
P
M
O
(
s
r
∣
s
,
a
)
=
1
-
∑
i
=
1
,
i
≠
r
i
=
n
‍
P
M
O
(
s
i
∣
s
,
a
)
.Note that themax
⁡ operator in (17) uses (16) to compare interval value functions. It can be proved (see [41]) that the IVI algorithm will finally converge to an interval value function [
V
↓
opt
,
V
↑
opt
] and an associated solution which we call B-optimal policy. The upper bound of interval value function V
↑
opt for the B-optimal policy is the possible best reward one can get from the BMDP M
↕; therefore, it can serve as a cornerstone to evaluate how far the value of a given strategy deviates from the one of possible optimal strategies for any exact MDP M
∈
M
↕. V
↓
opt is the possible worst case performance of the B-optimal strategy.In our application, states in the BMDPM
↕ can be viewed as aggregations of states in the exact MDP M. The parameter intervals in M
↕ represent the parameter ranges of states in M which belong to the same BMDP state. From this viewpoint M
↕ is a “smaller” approximation to the original M.


### 4.2.2. Model Reduction

The intuition behind our aggregation scheme is to overlook the request type in the server load matrixN. We can construct an aggregate state space S
′ with an element (
L
,
λ
), where L is the server load vector specified in (14). The system dynamics equation becomes
(20)
L
(
t
+
1
)
=
L
(
t
)
+
a
(
t
)
·
e
-
Y
(
t
)
,
where e is a j-dimension unit vector and Y is the total departures vector. Equation (20) means that the change of server state only depends upon the number of requests assigned to and departing from the server regardless of their types. With this abstraction, the number of state spaces with respect to L is r
q, a great reduction compared to (12).


### 4.2.3. The BMDP Reformulation

First we present the following lemma which is used to obtain the interval transition function of the BMDP formulation.Lemma 3.
Suppose the system is in a particular aggregated state(
L
(
t
)
,
λ
(
t
)
) at the tth slot; the probability of n clients leaving edge server j in this slot, namely, P
r
(
Y
j
(
t
)
=
n
), can be bounded by
(21)
[
(
L
j
(
t
)
+
∑
i
∈
I
a
i
j
(
t
)
n
)
p
min
⁡
n
(
1
-
p
max
⁡
)
L
j
(
t
)
+
∑
i
∈
I
‍
a
i
j
(
t
)
-
n
,
(
L
j
(
t
)
+
∑
i
∈
I
a
i
j
(
t
)
n
)
p
max
⁡
n
(
1
-
p
min
⁡
)
L
j
(
t
)
+
∑
i
∈
I
‍
a
i
j
(
t
)
-
n
]
provided that n
≤
L
j
(
t
)
+
∑
i
∈
I
‍
a
i
j
(
t
), where p
max
⁡
=
max
⁡
i
∈
I
p
i and p
min
⁡
=
min
⁡
i
∈
I
p
i.Proof.
We show how to derive the upper bound; the lower bound can be obtained using the same idea. Pick any exact MDP state(
N
(
t
)
,
λ
(
t
)
) which belongs to the aggregated state (
L
(
t
)
,
λ
(
t
)
); that is, ∑
i
∈
I
‍
n
i
j
(
t
)
=
L
j
(
t
). For server j in state (
N
(
t
)
,
λ
(
t
)
), there are a total (
L
j
(
t
)
+
∑
i
∈
I
‍
a
i
j
(
t
)
n
) number of cases such that n clients leave server j. Choose a particular case where the number of type i requests that leave server j is k
i
j; we have ∑
i
∈
I
‍
k
i
j
(
t
)
=
n. The probability of the occurrence of this case is
(22)
∏
i
∈
I
‍
p
i
k
i
j
×
∏
i
∈
I
‍
(
1
-
p
i
)
n
i
j
(
t
)
+
a
i
j
(
t
)
-
k
i
j
≤
p
max
⁡
∑
i
∈
I
‍
k
i
j
(
1
-
p
min
⁡
)
∑
i
∈
I
‍
n
i
j
(
t
)
+
a
i
j
(
t
)
-
k
i
j
=
p
max
⁡
n
(
1
-
p
min
⁡
)
L
j
(
t
)
+
∑
i
∈
I
‍
a
i
j
(
t
)
-
n
.
The results can be followed immediately.We can now reformulate the problem with the BMDP.States. The aggregated state space is S
′, with an element denoted by (
L
,
λ
).Decision Epoch and Actions. Decision epoch and actions are the same as in the original MDP model.Interval Transition Probability. Note that, in the BMDP formulation, the transition probability is a closed interval. First observe that
(23)
P
(
L
(
t
+
1
)
,
λ
(
t
+
1
)
∣
L
(
t
)
,
λ
(
t
)
,
a
(
t
)
)
=
∏
i
∈
I
‍
f
i
(
λ
i
(
t
+
1
)
)
·
∏
j
∈
J
‍
P
(
L
j
(
t
+
1
)
∣
L
j
(
t
)
,
λ
(
t
)
,
a
(
t
)
)
=
∏
i
∈
I
‍
f
i
(
λ
i
(
t
+
1
)
)
mmmmi
·
∏
j
∈
J
‍
P
(
Y
j
(
t
)
=
L
j
(
t
)
+
∑
i
∈
I
‍
a
i
j
(
t
)
-
L
j
(
t
+
1
)
)
.
Combining with Lemma 3, the transition probability in (23) can be bounded by the interval transition shown in (24) with Θ
j
(
t
)
=
L
j
(
t
)
+
∑
i
∈
I
‍
a
i
j
(
t
) and Y
j
(
t
)
=
L
j
(
t
)
+
∑
i
∈
I
‍
a
i
j
(
t
)
-
L
j
(
t
+
1
) denoting the number of requests and the number of departures in t
th slot in server j regardless of their types, respectively. Consider
(24)
P
↕
(
L
(
t
+
1
)
,
λ
(
t
+
1
)
∣
L
(
t
)
,
λ
(
t
)
,
a
(
t
)
)
=
{
[
0,0
]
,
if
L
j
(
t
)
+
∑
i
∈
I
a
i
j
(
t
)
≤
L
j
(
t
+
1
)
[
∏
i
∈
I
‍
p
min
⁡
∑
j
∈
J
‍
Y
j
(
t
)
(
1
-
p
max
⁡
)
∑
j
∈
J
‍
L
j
(
t
+
1
)
m
×
∏
i
∈
I
‍
f
i
(
λ
i
(
t
+
1
)
)
∏
j
∈
J
(
Θ
j
(
t
)
Y
j
(
t
)
)
‍
,
m
p
max
⁡
∑
j
∈
J
‍
Y
j
(
t
)
(
1
-
p
min
⁡
)
∑
j
∈
J
‍
L
j
(
t
+
1
)
m
×
∏
i
∈
I
‍
f
i
(
λ
i
(
t
+
1
)
)
∏
j
∈
J
‍
(
Θ
j
(
t
)
Y
j
(
t
)
)
]
,
otherwise
.Interval Rewards. The reward consists of two parts. The first part is the reward for the action a
(
t
), which is a fixed value given by ∑
j
∈
j
‍
∑
i
∈
I
‍
a
i
j
(
t
)
(
r
i
-
c
i
j
). The second part is a closed interval [
m
L
(
t
)
,
M
L
(
t
)
], with
(25)
M
=
max
⁡
i
∈
I
,
j
∈
J
{
r
i
-
c
i
j
}
,
m
=
min
⁡
i
∈
I
,
j
∈
J
{
r
i
-
c
i
j
}
.
The interval reward function can then be expressed by
(26)
R
↕
(
L
(
t
)
,
λ
(
t
)
,
a
(
t
)
)
=
[
m
L
(
t
)
+
∑
j
∈
j
‍
∑
i
∈
I
‍
a
i
j
(
t
)
(
r
i
-
c
i
j
)
,
m
m
m
i
M
L
(
t
)
+
∑
j
∈
j
‍
∑
i
∈
I
‍
a
i
j
(
t
)
(
r
i
-
c
i
j
)
]
.


### 4.2.4. The Interval Value Iteration (IVI) Algorithm

We illustrate the IVI algorithm in detail in Algorithms1 and 2.Algorithm 1:Solutions to the BMDP formulation.
Input: a BMDP M
↕
=
{
S
,
A
,
P
↕
,
R
↕
}
Output:  V
↕ and π
(1) Createπ; {
π holds the strategy in each iteration.}
(2) CreateV
↕; {
V
↕ is an initial interval value function.}
(3)loop
(4)V
↕
=
IVI
↕
opt
(
M
↕
,
V
↕
,
&
π
);
(5)end loopAlgorithm 2:Interval value iteration (IVI
↕) algorithm.
Input: a BMDP M
↕, a value function V
↕, and a place π for holding the policy in current iteration
Output:  V
↕
opt
′ and π
opt
(1)Create O
up, O
down;  {
O
up and O
down hold order sequence of states in M
↕, i.e., s
1
s
2
,
…
,
s
n
.
}
(2)Create P
up
′, P
down
′; {
P
up
′ and P
down
′ hold the transition probabilities for the order-maximizing MDP with respect
to order O
up and O
down, respectively.}
(3)Create r
up, r
down; {
r
up and r
down is the order-maximizing index for order sequences O
up and O
down, respectively.}
(4)Create i; {
i is the index into an ordering O.}
(5)
O
up
=
Sort_Decreasing_Order
(
V
↑
);
(6)
O
down
=
Sort_Increasing_Order
(
V
↓
);
(7)
for all  s
∈
S  do
(8) for all  a
∈
A  do
(9)  r
up
=
Order_Maximizing_Ind
(
M
↕
,
O
up
,
s
,
a
);
(10)r
down
=
Order_Maximizing_Ind
(
M
↕
,
O
down
,
s
,
a
);
{find order-maximizing index for transition probability in state s under action a according to (18).}
(11)for  i
=
1 to n  do
(12)    UpdateP
up
′
(
s
O
down
(
i
)
∣
s
,
a
) and P
down
′
(
s
O
up
(
i
)
∣
s
,
a
) according to (19);
(13)end for
(14)end for
(15)V
↑
′
=
max
a
⊆
A
(
s
)
⁡
R
↑
(
s
,
a
)
+
δ
∑
s
′
∈
S
‍
P
up
′
(
s
′
s
,
a
)
V
↑
(
s
′
);(*)
(16)if  |
a
|
=
1 and a
=
{
a
}  then
(17)V
↓
′
=
R
↓
(
s
,
a
)
+
δ
∑
s
′
∈
S
‍
P
down
′
(
s
′
s
,
a
)
V
↓
(
s
′
);
(18)π
(
s
)
=
a;
(19)else
(20)V
↓
′
=
max
a
∈
a
⁡
R
↓
(
s
,
a
)
+
δ
∑
s
′
∈
S
‍
P
down
′
(
s
′
s
,
a
)
V
↓
(
s
′
);(**)
(21)π
(
s
)
=
a;
(22)end if
(23)end ifAlgorithm1 takes the above BMDP model M
↕ as input. It first chooses an initial interval value function V
↕ and then iteratively calls function IVI. The algorithm finishes with an interval value function V
↕ and a corresponding policy π.Algorithm2 captures the essence of (17). The increasing state order of V
↑ and the decreasing state order of V
↓ are stored in O
up and O
down. For each state s and action a, the algorithm computes the order-maximizing indices r
up and r
down for order sequences O
up and O
down and forms two order-maximizing MDPs with transition probabilities P
up
′ and P
down
′. Using P
up
′, the set of actions a which maximizes the upper bound V
↑
′ is identified. If a contains only one element, for example, a
=
{
a
}, then a is the B-optimal action in this state and the lower bound can be obtained immediately. Otherwise, an action a
∈
a which maximizes the lower bound V
↓
′ is chosen as the B-optimal action.


### 4.2.5. A Word on Computational Complexity

(i)
Space Complexity. Although the memory consumption of a single state in the BMDP model is a bit larger than the one in the MDP model due to the interval transition probability and the interval reward, but since the aggregation scheme in our BMDP formulation dramatically reduces the state space of edge servers from (
∑
i
=
0
r
(
i
+
p
-
1
i
)
)
q to r
q, the total memory space needed for storing the BMDP model is significantly less than the MDP model. On the other hand, the IVI algorithm only needs additional O
up and O
down to store order sequences in BMDP model, r
up and r
down to store order-maximizing indices, and P
up
′ and P
down
′ to store transition probabilities for the π
-maximizing MDP and the π
-minimizing MDP, respectively. In all, the memory space needed to store the BMDP model and implement the IVI algorithm decreases greatly compared with the memory space needed for the MDP model.
(ii)
Time Complexity. In the IVI algorithm, the first optimization problem (*) is much easier than problem (11) in traditional value iteration algorithm since the computation of the expectation in the Bellman equation involves much less states. There are three extra computational burdens in the IVI algorithm: (1) sorting states to obtain O
up and O
down (lines 5 and 6 in Algorithm 2), which take O
(
2
n
2
) in worst case using Quicksort algorithm; (2) finding the order-maximizing indices and computing the transition probabilities for the π
-maximizing MDP and the π
-minimizing MDP (lines 9, 10, and 12 in Algorithm 2), which take O
(
4
n
) in worst case; (3) finding a unique solution a
∈
a to the problem (*
*) which maximizes the lower bound V
↓ (line 20 in Algorithm 2). In this step we use the exhaustive search, so the time complexity is O
(
|
a
|
). However, regarding a which is usually a small set, it will not take too long to complete the search. Thus, the total extra time complexity is O
(
2
n
2
+
4
n
+
|
a
|
).


## 4.2.1. BMDP Preliminaries

A BMDPM
↕ is a four-tuple {
S
,
A
,
R
↕
,
P
↕
}. It is different from traditional MDP (also calledexact MDP) in the sense that the reward function in each state R
↕
(
s
) and the transition probability P
↕
(
s
′
∣
s
,
a
) are specified by closed intervals [
R
↓
(
p
)
,
R
↑
(
p
)
] and [
P
↓
(
s
′
∣
s
,
a
)
,
P
↑
(
s
′
∣
s
,
a
)
], respectively, rather than exact point values. An exact MDP M
=
{
S
′
,
A
′
,
R
′
,
P
′
} is said to be contained in a BMDP M
↕ (M
∈
M
↕) as long as S
′
=
S, A
′
=
A, R
′
∈
R
↕, and P
′
∈
P
↕.Given a policyπ, the interval value function V
↕
π is defined by
(15)
V
↕
π
(
s
)
=
[
min
⁡
M
∈
M
↕
V
M
,
π
(
s
)
,
max
⁡
M
∈
M
↕
V
M
,
π
(
s
)
]
,
where V
M
,
π
(
s
)
=
R
M
(
s
)
+
δ
∑
s
′
∈
S
‍
P
M
(
s
′
∣
s
,
a
)
V
M
,
π
(
s
′
) is the traditional value function for a specific exact MDP M
∈
M
↕. It can be proved that (see reference [41]) there exists a MDP M
∈
M
↕ which maximizes/minimizes V
M
,
π
(
s
) for all s
∈
S simultaneously. We call such MDP π
-
m
a
x
i
m
i
z
i
n
g/π
-
m
i
n
i
m
i
z
i
n
g MDP.The interval value functions cannot be compared using traditional MDP standard, which focuses on point values. To evaluate how “good" a policyπ can achieve, we must define a scheme to compare interval value functions. In this paper we define the interval greater operator ≳ given by
(16)
V
↕
1
≳
V
↕
2
⟺
V
↑
1
≥
V
↑
2
∨
(
V
↑
1
=
V
↑
2
∧
V
↓
1
≥
V
↓
2
)
.The interval value iteration (IVI) algorithms with provable convergence property can be used to obtain the optimal solution to the BDMP; that is,(17)
IV
I
↕
opt
(
V
↕
)
(
s
)
=
max
⁡
a
∈
A
(
s
)
[
min
⁡
M
∈
M
↕
V
I
M
,
a
(
V
↓
)
(
s
)
,
max
⁡
M
∈
M
↕
V
I
M
,
a
(
V
↑
)
(
s
)
]
with V
I
M
,
a
(
V
)
(
s
)
=
R
M
(
s
)
+
δ
∑
s
′
∈
S
‍
P
M
(
s
′
∣
s
,
a
)
V
(
s
′
).The IVI algorithm (17) starts with an arbitrary interval value function V
↕
=
[
V
↓
,
V
↑
] with V
↓
≤
V
↑. The operation of finding exact MDPs M
∈
M
↕ inside the square bracket is equivalent to searching for order-maximizingMDPs with respect to state order sequences of decreasing V
↑ and increasing V
↓. Formal definition of the order-maximizing MDP for a specific state order sequence O
=
s
1
s
2
⋯
s
n is given by the following definition.Definition 2.
The order-maximizing indexr for state s and action a with respect to order O is
(18)
arg
max
⁡
1
≤
r
≤
n
{
∑
i
=
1
r
-
1
‍
P
↑
(
s
i
∣
s
,
a
)
+
∑
i
=
r
n
‍
P
↓
(
s
i
∣
s
,
a
)
}
.
The order-maximizing MDP is an exact MDP M
O
∈
M
↕ satisfying
(19)
P
M
O
(
s
i
∣
s
,
a
)
=
{
P
↑
(
s
i
∣
s
,
a
)
,
if
i
<
r
,
P
↓
(
s
i
∣
s
,
a
)
,
if
i
>
r
,
P
M
O
(
s
r
∣
s
,
a
)
=
1
-
∑
i
=
1
,
i
≠
r
i
=
n
‍
P
M
O
(
s
i
∣
s
,
a
)
.Note that themax
⁡ operator in (17) uses (16) to compare interval value functions. It can be proved (see [41]) that the IVI algorithm will finally converge to an interval value function [
V
↓
opt
,
V
↑
opt
] and an associated solution which we call B-optimal policy. The upper bound of interval value function V
↑
opt for the B-optimal policy is the possible best reward one can get from the BMDP M
↕; therefore, it can serve as a cornerstone to evaluate how far the value of a given strategy deviates from the one of possible optimal strategies for any exact MDP M
∈
M
↕. V
↓
opt is the possible worst case performance of the B-optimal strategy.In our application, states in the BMDPM
↕ can be viewed as aggregations of states in the exact MDP M. The parameter intervals in M
↕ represent the parameter ranges of states in M which belong to the same BMDP state. From this viewpoint M
↕ is a “smaller” approximation to the original M.


## 4.2.2. Model Reduction

The intuition behind our aggregation scheme is to overlook the request type in the server load matrixN. We can construct an aggregate state space S
′ with an element (
L
,
λ
), where L is the server load vector specified in (14). The system dynamics equation becomes
(20)
L
(
t
+
1
)
=
L
(
t
)
+
a
(
t
)
·
e
-
Y
(
t
)
,
where e is a j-dimension unit vector and Y is the total departures vector. Equation (20) means that the change of server state only depends upon the number of requests assigned to and departing from the server regardless of their types. With this abstraction, the number of state spaces with respect to L is r
q, a great reduction compared to (12).


## 4.2.3. The BMDP Reformulation

First we present the following lemma which is used to obtain the interval transition function of the BMDP formulation.Lemma 3.
Suppose the system is in a particular aggregated state(
L
(
t
)
,
λ
(
t
)
) at the tth slot; the probability of n clients leaving edge server j in this slot, namely, P
r
(
Y
j
(
t
)
=
n
), can be bounded by
(21)
[
(
L
j
(
t
)
+
∑
i
∈
I
a
i
j
(
t
)
n
)
p
min
⁡
n
(
1
-
p
max
⁡
)
L
j
(
t
)
+
∑
i
∈
I
‍
a
i
j
(
t
)
-
n
,
(
L
j
(
t
)
+
∑
i
∈
I
a
i
j
(
t
)
n
)
p
max
⁡
n
(
1
-
p
min
⁡
)
L
j
(
t
)
+
∑
i
∈
I
‍
a
i
j
(
t
)
-
n
]
provided that n
≤
L
j
(
t
)
+
∑
i
∈
I
‍
a
i
j
(
t
), where p
max
⁡
=
max
⁡
i
∈
I
p
i and p
min
⁡
=
min
⁡
i
∈
I
p
i.Proof.
We show how to derive the upper bound; the lower bound can be obtained using the same idea. Pick any exact MDP state(
N
(
t
)
,
λ
(
t
)
) which belongs to the aggregated state (
L
(
t
)
,
λ
(
t
)
); that is, ∑
i
∈
I
‍
n
i
j
(
t
)
=
L
j
(
t
). For server j in state (
N
(
t
)
,
λ
(
t
)
), there are a total (
L
j
(
t
)
+
∑
i
∈
I
‍
a
i
j
(
t
)
n
) number of cases such that n clients leave server j. Choose a particular case where the number of type i requests that leave server j is k
i
j; we have ∑
i
∈
I
‍
k
i
j
(
t
)
=
n. The probability of the occurrence of this case is
(22)
∏
i
∈
I
‍
p
i
k
i
j
×
∏
i
∈
I
‍
(
1
-
p
i
)
n
i
j
(
t
)
+
a
i
j
(
t
)
-
k
i
j
≤
p
max
⁡
∑
i
∈
I
‍
k
i
j
(
1
-
p
min
⁡
)
∑
i
∈
I
‍
n
i
j
(
t
)
+
a
i
j
(
t
)
-
k
i
j
=
p
max
⁡
n
(
1
-
p
min
⁡
)
L
j
(
t
)
+
∑
i
∈
I
‍
a
i
j
(
t
)
-
n
.
The results can be followed immediately.We can now reformulate the problem with the BMDP.States. The aggregated state space is S
′, with an element denoted by (
L
,
λ
).Decision Epoch and Actions. Decision epoch and actions are the same as in the original MDP model.Interval Transition Probability. Note that, in the BMDP formulation, the transition probability is a closed interval. First observe that
(23)
P
(
L
(
t
+
1
)
,
λ
(
t
+
1
)
∣
L
(
t
)
,
λ
(
t
)
,
a
(
t
)
)
=
∏
i
∈
I
‍
f
i
(
λ
i
(
t
+
1
)
)
·
∏
j
∈
J
‍
P
(
L
j
(
t
+
1
)
∣
L
j
(
t
)
,
λ
(
t
)
,
a
(
t
)
)
=
∏
i
∈
I
‍
f
i
(
λ
i
(
t
+
1
)
)
mmmmi
·
∏
j
∈
J
‍
P
(
Y
j
(
t
)
=
L
j
(
t
)
+
∑
i
∈
I
‍
a
i
j
(
t
)
-
L
j
(
t
+
1
)
)
.
Combining with Lemma 3, the transition probability in (23) can be bounded by the interval transition shown in (24) with Θ
j
(
t
)
=
L
j
(
t
)
+
∑
i
∈
I
‍
a
i
j
(
t
) and Y
j
(
t
)
=
L
j
(
t
)
+
∑
i
∈
I
‍
a
i
j
(
t
)
-
L
j
(
t
+
1
) denoting the number of requests and the number of departures in t
th slot in server j regardless of their types, respectively. Consider
(24)
P
↕
(
L
(
t
+
1
)
,
λ
(
t
+
1
)
∣
L
(
t
)
,
λ
(
t
)
,
a
(
t
)
)
=
{
[
0,0
]
,
if
L
j
(
t
)
+
∑
i
∈
I
a
i
j
(
t
)
≤
L
j
(
t
+
1
)
[
∏
i
∈
I
‍
p
min
⁡
∑
j
∈
J
‍
Y
j
(
t
)
(
1
-
p
max
⁡
)
∑
j
∈
J
‍
L
j
(
t
+
1
)
m
×
∏
i
∈
I
‍
f
i
(
λ
i
(
t
+
1
)
)
∏
j
∈
J
(
Θ
j
(
t
)
Y
j
(
t
)
)
‍
,
m
p
max
⁡
∑
j
∈
J
‍
Y
j
(
t
)
(
1
-
p
min
⁡
)
∑
j
∈
J
‍
L
j
(
t
+
1
)
m
×
∏
i
∈
I
‍
f
i
(
λ
i
(
t
+
1
)
)
∏
j
∈
J
‍
(
Θ
j
(
t
)
Y
j
(
t
)
)
]
,
otherwise
.Interval Rewards. The reward consists of two parts. The first part is the reward for the action a
(
t
), which is a fixed value given by ∑
j
∈
j
‍
∑
i
∈
I
‍
a
i
j
(
t
)
(
r
i
-
c
i
j
). The second part is a closed interval [
m
L
(
t
)
,
M
L
(
t
)
], with
(25)
M
=
max
⁡
i
∈
I
,
j
∈
J
{
r
i
-
c
i
j
}
,
m
=
min
⁡
i
∈
I
,
j
∈
J
{
r
i
-
c
i
j
}
.
The interval reward function can then be expressed by
(26)
R
↕
(
L
(
t
)
,
λ
(
t
)
,
a
(
t
)
)
=
[
m
L
(
t
)
+
∑
j
∈
j
‍
∑
i
∈
I
‍
a
i
j
(
t
)
(
r
i
-
c
i
j
)
,
m
m
m
i
M
L
(
t
)
+
∑
j
∈
j
‍
∑
i
∈
I
‍
a
i
j
(
t
)
(
r
i
-
c
i
j
)
]
.


## 4.2.4. The Interval Value Iteration (IVI) Algorithm

We illustrate the IVI algorithm in detail in Algorithms1 and 2.Algorithm 1:Solutions to the BMDP formulation.
Input: a BMDP M
↕
=
{
S
,
A
,
P
↕
,
R
↕
}
Output:  V
↕ and π
(1) Createπ; {
π holds the strategy in each iteration.}
(2) CreateV
↕; {
V
↕ is an initial interval value function.}
(3)loop
(4)V
↕
=
IVI
↕
opt
(
M
↕
,
V
↕
,
&
π
);
(5)end loopAlgorithm 2:Interval value iteration (IVI
↕) algorithm.
Input: a BMDP M
↕, a value function V
↕, and a place π for holding the policy in current iteration
Output:  V
↕
opt
′ and π
opt
(1)Create O
up, O
down;  {
O
up and O
down hold order sequence of states in M
↕, i.e., s
1
s
2
,
…
,
s
n
.
}
(2)Create P
up
′, P
down
′; {
P
up
′ and P
down
′ hold the transition probabilities for the order-maximizing MDP with respect
to order O
up and O
down, respectively.}
(3)Create r
up, r
down; {
r
up and r
down is the order-maximizing index for order sequences O
up and O
down, respectively.}
(4)Create i; {
i is the index into an ordering O.}
(5)
O
up
=
Sort_Decreasing_Order
(
V
↑
);
(6)
O
down
=
Sort_Increasing_Order
(
V
↓
);
(7)
for all  s
∈
S  do
(8) for all  a
∈
A  do
(9)  r
up
=
Order_Maximizing_Ind
(
M
↕
,
O
up
,
s
,
a
);
(10)r
down
=
Order_Maximizing_Ind
(
M
↕
,
O
down
,
s
,
a
);
{find order-maximizing index for transition probability in state s under action a according to (18).}
(11)for  i
=
1 to n  do
(12)    UpdateP
up
′
(
s
O
down
(
i
)
∣
s
,
a
) and P
down
′
(
s
O
up
(
i
)
∣
s
,
a
) according to (19);
(13)end for
(14)end for
(15)V
↑
′
=
max
a
⊆
A
(
s
)
⁡
R
↑
(
s
,
a
)
+
δ
∑
s
′
∈
S
‍
P
up
′
(
s
′
s
,
a
)
V
↑
(
s
′
);(*)
(16)if  |
a
|
=
1 and a
=
{
a
}  then
(17)V
↓
′
=
R
↓
(
s
,
a
)
+
δ
∑
s
′
∈
S
‍
P
down
′
(
s
′
s
,
a
)
V
↓
(
s
′
);
(18)π
(
s
)
=
a;
(19)else
(20)V
↓
′
=
max
a
∈
a
⁡
R
↓
(
s
,
a
)
+
δ
∑
s
′
∈
S
‍
P
down
′
(
s
′
s
,
a
)
V
↓
(
s
′
);(**)
(21)π
(
s
)
=
a;
(22)end if
(23)end ifAlgorithm1 takes the above BMDP model M
↕ as input. It first chooses an initial interval value function V
↕ and then iteratively calls function IVI. The algorithm finishes with an interval value function V
↕ and a corresponding policy π.Algorithm2 captures the essence of (17). The increasing state order of V
↑ and the decreasing state order of V
↓ are stored in O
up and O
down. For each state s and action a, the algorithm computes the order-maximizing indices r
up and r
down for order sequences O
up and O
down and forms two order-maximizing MDPs with transition probabilities P
up
′ and P
down
′. Using P
up
′, the set of actions a which maximizes the upper bound V
↑
′ is identified. If a contains only one element, for example, a
=
{
a
}, then a is the B-optimal action in this state and the lower bound can be obtained immediately. Otherwise, an action a
∈
a which maximizes the lower bound V
↓
′ is chosen as the B-optimal action.


## 4.2.5. A Word on Computational Complexity

(i)
Space Complexity. Although the memory consumption of a single state in the BMDP model is a bit larger than the one in the MDP model due to the interval transition probability and the interval reward, but since the aggregation scheme in our BMDP formulation dramatically reduces the state space of edge servers from (
∑
i
=
0
r
(
i
+
p
-
1
i
)
)
q to r
q, the total memory space needed for storing the BMDP model is significantly less than the MDP model. On the other hand, the IVI algorithm only needs additional O
up and O
down to store order sequences in BMDP model, r
up and r
down to store order-maximizing indices, and P
up
′ and P
down
′ to store transition probabilities for the π
-maximizing MDP and the π
-minimizing MDP, respectively. In all, the memory space needed to store the BMDP model and implement the IVI algorithm decreases greatly compared with the memory space needed for the MDP model.
(ii)
Time Complexity. In the IVI algorithm, the first optimization problem (*) is much easier than problem (11) in traditional value iteration algorithm since the computation of the expectation in the Bellman equation involves much less states. There are three extra computational burdens in the IVI algorithm: (1) sorting states to obtain O
up and O
down (lines 5 and 6 in Algorithm 2), which take O
(
2
n
2
) in worst case using Quicksort algorithm; (2) finding the order-maximizing indices and computing the transition probabilities for the π
-maximizing MDP and the π
-minimizing MDP (lines 9, 10, and 12 in Algorithm 2), which take O
(
4
n
) in worst case; (3) finding a unique solution a
∈
a to the problem (*
*) which maximizes the lower bound V
↓ (line 20 in Algorithm 2). In this step we use the exhaustive search, so the time complexity is O
(
|
a
|
). However, regarding a which is usually a small set, it will not take too long to complete the search. Thus, the total extra time complexity is O
(
2
n
2
+
4
n
+
|
a
|
).


## 5. Numerical Analysis

In this section we study an illustrative system with two video request types and two edge servers. To alleviate the computational and simulation burden, we use a small scale system parameterization. We initially set the server capacityC
1
=
C
2
=
5. The expected sojourn time of type 1 and type 2 requests (T
1 and T
2) is 2000 s and 1000 s, respectively. According to (3), the departure probabilities can be computed as p
2
=
0.0025 and p
1
=
0.005 if we set the length of the time slot to 5
s. Other parameters are summarized in Table 2.Table 2
Parameters setting.
Type 1 request
Type 2 request
Server 1
Server 2
Server 1
Server 2
Cost
2
2.5
1
2
Reward
12
10
Expected sojourn time
2000
1000
Upper bound of sojourn time
2500
1200


### 5.1. Problem State Space

First we will see the effectiveness of the state aggregation scheme of the proposed BMDP formulation. We compare the state space of a single server here with respect to MDP formulation and BMDP formulation. The results are shown in Figure4.Problem state space size of MDP and BMDP formulations.
(a)
State size versus number of request types, with server capacity = 5
(b)
State size versus server capacity, with number of request types = 2In Figure4(a), we fix the server capacity to 5 and vary the number of request types. In Figure 4(b), we fix the number of request types to 2 and vary the server capacity. The state space of the BMDP formulation does not change with the number of request types and grows linearly with the server capacity. In contrast, the state space of the MDP formulation increases exponentially with both the number of request types and the server capacity. There are over 3000 states when the number of request type reaches 10, demonstrating that the MDP model is practically intractable.On the other hand, although the state space of a single server in the BMDP formulation is greatly reduced compared to the counterpart in the MDP formulation, the state space of the whole system in the BMDP formulation still grows exponentially as the number of edge servers increases. This problem can be addressed by further aggregation of the state space of a single server. However, the greater the degree of aggregation is, the more the transition probability information is lost, which may degrade the performance of the generated solution. In practice, the CDN provider must make tradeoff between the quality of the generated solution and the computational cost. We leave this issue in our future works.


### 5.2. Convergence and Application of the IVI Algorithm

We initially set the interval value function for all states to[
0,0
] and other parameters are defined in Tables 2 and 3. The interval value function of state [
0
,
0
] in each iteration is plotted in Figure 5. It converges after about 600 iterations.Table 3
Arrival and departure distribution.
Type 1 request
Type 2 request
Number of arrivals
0
1
0
1
Arrival probability
0.8
0.2
0.9
0.1
Departure probability
0.0025
0.005Figure 5
Convergence of IVI algorithm.The IVI algorithm is not suitable for online scheduling since it involves time-consuming iterative steps, which cannot cope with variations of online request arrival pattern. However, like the Internet traffic, the Internet video streaming also demonstrates a strongtemporal pattern [44]. We could divide a day into several parts according to the request arrival patterns obtained by network measurement and compute a particular strategy for each part offline. The dispatcher can adopt the associated strategy in a given time interval to yield close-to-optimal rewards.


### 5.3. Performance for the Greedy Strategy and the B-Optimal Strategy

We evaluate the greedy strategy and the B-optimal strategy in two ways.(1)
The value functionV
greedy for the greedy strategy in the MDP model and the interval value function [
V
↓
opt
,
V
↑
opt
] for the B-optimal strategy in the BMDP model, which is plotted in Figure 6.
(2)
The ratio ofV
↓
opt
/
V
↑
opt and V
greedy
/
V
↑
opt, which is plotted in Figure 7.In both Figures 6 and 7 we vary the arrival probability of two request types from 0.01 to 0.2.Figure 6
Upper bound and lower bound versus arrival probability.Figure 7
V
↓
opt
/
V
↑
opt
=
lower
bound
/
upper
bound and V
greedy
/
V
↑
opt  =  greedy/upper
bound versus arrival probability.The first observation from Figure6 is that as the arrival traffic grows heavier, the upper bound and the lower bound of the B-optimal strategy, as well as the value of the greedy strategy, all tend to a steady state. This is because the system approaches to a saturated state. Another phenomenon is that the B-optimal strategy always outperforms the greedy strategy since even the lower bound of the B-optimal strategy is greater than the greedy strategy, meaning that the B-optimal algorithm is effective in this system.We can have a clearer view of the quality of the proposed strategies in Figure7. The lower bound of performance V
↓
opt in the worst case for B-optimal strategy can attain around 80% to over 95% of the upper bound V
↑
opt. For the greedy strategy, V
greedy can attain around 65% to 80% of the upper bound V
↑
opt. An interesting finding is that there exists a conspicuous “jumping line” which divides V
↓
opt
/
V
↑
opt into two parts (a light load part and a heavy load part). The ratio V
↓
opt
/
V
↑
opt grows in the light load part, surges to the peak at the jumping line, and begins to decline slowly in the heavy load part, as the request arrival probabilities increase. The heavy load part of V
↓
opt
/
V
↑
opt still stands beyond 90%, suggesting that the B-optimal strategy has an outstanding performance under heavy load even in the worst case. On the other hand V
greedy
/
V
↑
opt reaches the trough at two positions: (1) extreme light load; (2) nearly the same load region of the jumping line of V
↓
opt
/
V
↑
opt, indicating that the performance of the greedy strategy may degrade at these load regions. However, in most of cases, V
greedy
/
V
↑
opt remains flat (around 80%).


## 5.1. Problem State Space

First we will see the effectiveness of the state aggregation scheme of the proposed BMDP formulation. We compare the state space of a single server here with respect to MDP formulation and BMDP formulation. The results are shown in Figure4.Problem state space size of MDP and BMDP formulations.
(a)
State size versus number of request types, with server capacity = 5
(b)
State size versus server capacity, with number of request types = 2In Figure4(a), we fix the server capacity to 5 and vary the number of request types. In Figure 4(b), we fix the number of request types to 2 and vary the server capacity. The state space of the BMDP formulation does not change with the number of request types and grows linearly with the server capacity. In contrast, the state space of the MDP formulation increases exponentially with both the number of request types and the server capacity. There are over 3000 states when the number of request type reaches 10, demonstrating that the MDP model is practically intractable.On the other hand, although the state space of a single server in the BMDP formulation is greatly reduced compared to the counterpart in the MDP formulation, the state space of the whole system in the BMDP formulation still grows exponentially as the number of edge servers increases. This problem can be addressed by further aggregation of the state space of a single server. However, the greater the degree of aggregation is, the more the transition probability information is lost, which may degrade the performance of the generated solution. In practice, the CDN provider must make tradeoff between the quality of the generated solution and the computational cost. We leave this issue in our future works.


## 5.2. Convergence and Application of the IVI Algorithm

We initially set the interval value function for all states to[
0,0
] and other parameters are defined in Tables 2 and 3. The interval value function of state [
0
,
0
] in each iteration is plotted in Figure 5. It converges after about 600 iterations.Table 3
Arrival and departure distribution.
Type 1 request
Type 2 request
Number of arrivals
0
1
0
1
Arrival probability
0.8
0.2
0.9
0.1
Departure probability
0.0025
0.005Figure 5
Convergence of IVI algorithm.The IVI algorithm is not suitable for online scheduling since it involves time-consuming iterative steps, which cannot cope with variations of online request arrival pattern. However, like the Internet traffic, the Internet video streaming also demonstrates a strongtemporal pattern [44]. We could divide a day into several parts according to the request arrival patterns obtained by network measurement and compute a particular strategy for each part offline. The dispatcher can adopt the associated strategy in a given time interval to yield close-to-optimal rewards.


## 5.3. Performance for the Greedy Strategy and the B-Optimal Strategy

We evaluate the greedy strategy and the B-optimal strategy in two ways.(1)
The value functionV
greedy for the greedy strategy in the MDP model and the interval value function [
V
↓
opt
,
V
↑
opt
] for the B-optimal strategy in the BMDP model, which is plotted in Figure 6.
(2)
The ratio ofV
↓
opt
/
V
↑
opt and V
greedy
/
V
↑
opt, which is plotted in Figure 7.In both Figures 6 and 7 we vary the arrival probability of two request types from 0.01 to 0.2.Figure 6
Upper bound and lower bound versus arrival probability.Figure 7
V
↓
opt
/
V
↑
opt
=
lower
bound
/
upper
bound and V
greedy
/
V
↑
opt  =  greedy/upper
bound versus arrival probability.The first observation from Figure6 is that as the arrival traffic grows heavier, the upper bound and the lower bound of the B-optimal strategy, as well as the value of the greedy strategy, all tend to a steady state. This is because the system approaches to a saturated state. Another phenomenon is that the B-optimal strategy always outperforms the greedy strategy since even the lower bound of the B-optimal strategy is greater than the greedy strategy, meaning that the B-optimal algorithm is effective in this system.We can have a clearer view of the quality of the proposed strategies in Figure7. The lower bound of performance V
↓
opt in the worst case for B-optimal strategy can attain around 80% to over 95% of the upper bound V
↑
opt. For the greedy strategy, V
greedy can attain around 65% to 80% of the upper bound V
↑
opt. An interesting finding is that there exists a conspicuous “jumping line” which divides V
↓
opt
/
V
↑
opt into two parts (a light load part and a heavy load part). The ratio V
↓
opt
/
V
↑
opt grows in the light load part, surges to the peak at the jumping line, and begins to decline slowly in the heavy load part, as the request arrival probabilities increase. The heavy load part of V
↓
opt
/
V
↑
opt still stands beyond 90%, suggesting that the B-optimal strategy has an outstanding performance under heavy load even in the worst case. On the other hand V
greedy
/
V
↑
opt reaches the trough at two positions: (1) extreme light load; (2) nearly the same load region of the jumping line of V
↓
opt
/
V
↑
opt, indicating that the performance of the greedy strategy may degrade at these load regions. However, in most of cases, V
greedy
/
V
↑
opt remains flat (around 80%).


## 6. Concluding Remarks

In this paper we consider the dynamic request routing issue in the Video-on-Demand system. We classify video requests by the expected viewing time and the average bitrates of the video files. The system can be abstracted into a controlled queueing system containing one dispatcher with its waiting queue and several VoD edge servers with their service queues. Our goal is to find the decision policy of the dispatcher which yields the highest reward. The dynamic request routing problem can be formulated as a Markov decision process, and classical iterative algorithm can be used to obtain the optimal solution.However, the MDP formulation has its intrinsic drawback of the curse of dimensionality, which makes the problem intractable in practical scenario. To address this issue, we present two alternative approaches, that is, the greedy strategy and the bounded-parameter MDP reformulation, to approximately compute the suboptimal solution. These two approximation schemes start from different points: the greedy strategy ignores the request arrival patterns in the future and the BMDP reformulation overlooks the types of request in the server load. Although the greedy strategy is much simpler, the numerical results show that the B-optimal strategy can generate a higher reward than the greedy strategy. Our future research will concentrate on the distributed implementation of dynamic request routing strategy for VoD service.



---

*Source: 920829-2014-06-01.xml*