"On the Complexity of Optimal Request Routing and Content Caching in Heterogeneous Cache Networks"
University of Massachusetts Amherst
结合论文来分析
1.论文
-
Objective：
minimize the delay
where
delay=delay(hit)+delay(miss)+delay(server)
x*p*delay(hit)+(1-x)*p*delay(miss)+(1-p)*delay(server)
其中，作者假设
delay(hit)<delay(server)<delay(miss) -
Variable:
contentplacement x+ routing p
这里的routing设置很巧妙：对于routing policy, 作者定义了p(i,j,m)denotes the the fraction of the requests of user i for content j sent to cache m - s.t.
0<=p(i,j,m)<=1
sum x(f,m)<=Capacity(m)
x(f,m)={0,1}
min delay
s.t. x={0,1}
0=<p<=1 -
Optimization
convex optimization -
Deal with two varibales
因为两个变量，要知道凸优化是可以直接解决的，这是凸优化的优势。
文中的处理方式：
step1：给定x，求p.
在x给定的情况下，将目标函数delay表示成含有x的fucnction：delay(p;x)。且delay(p;x)为凸函数(单调递减)。问题变成：
min delay(p:x)
s.t. 0=<p<=1
既然，给定x，目标函数为凸，直接求最优p即可(即：delay(p;x) is convex and can be solved in polynomial time)。
step2:在求得p后，进一步求解x。
由于x={0,1}，且目标函数为"单调"递减的凸函数。{可由哑膜函数性质倒推，边际效益越来越小+increasing-->原函数为decreasing 的凸函数}
step3：将目标函数转换为哑膜函数标准。 -
哑膜函数的特征
主要包含两个因素: matriod + margin function + approximation with guarantee + greedy
2. 哑膜函数
gaurantee
The greedy algorithm for maximizing a monotone submodular set function with matroid constraints yield a (1-1/e)-approximation-
matroid
通常分为几类，但这里只讲论文里常见的。still call matroid，哈哈哈哈哈。。。
matroid.png
证明过程中抓住以下几点：
1). ground set S
S denote the set of all possible files that could be placed in caches.
S={S1,S2,...,Sm}，Si denote the set of all possible files that could be placed in cache i.
2). I 的定义
I 实际等同于X，即content placement。
X=X1∪X2∪...∪Xm。Xi denote the set that files stored in cache i.
其中，
|Xm|<Capcity(m)
为方便描述，这里()表示下标。
基于此，
论文中的s.t.为matroid on S. 表达为X belong to I.
因此，(S,I) define a matroid. function
给定X，分别考虑f(X∪ef)-f(X)
f(Y∪ef)-f(Y)
其中ef 不属于Y
1). monotone
2). increasing
f(Y)-f(X)>=0
3). submodular
1). increasing，2). monotone，3). submodular function.
1). D(server)-delay---->添加负号，目标函数由decreasing转换为increasing；
2). 本来就是
image.png
