2018-12-13

作者: w蕾丝 | 来源:发表于2018-12-14 12:23 被阅读0次

Sets

$V$ set of $n$ vertices representing the network nodes
$A$ set of $m$ arcs representing network directed links
$P$ set of $q$ anycast connections(requests) in the network.(只要客户的请求能通过某个路径到达网络中的任何一个servers就说这个anycast connection能被建立)
$\Pi_p=[\pi_p^1,...,\pi_p^{k_p}]$ set of candidate paths of anycast request $i$
$K_p$ the index set of candidate routes(paths) for anycast connection $p$ , 包含了该anycast connection $p$ 的client到网络中所有servers的全部可能路径的索引。
$X$ A route selection set. 指示出了当前为所有anycast requests所选的routes， $X={(\bigcup_{p,k:x_p^k=1}\{ x_p^k\})}$ ，只包含binary variable中取值为1的那些。

Constants

$\delta_{pa}^k$ =1，if arc $a$ belongs to route $k$ realizing connection $p$ ; 0 otherwise.
$Q_p$ estimated bandwidth requirement of connection $p$ . 用向量表示 $\underline{Q}=[Q_1,...,Q_q]$ 所有anycast requests的bandwidth requirements。
$c_a$ capacity of arc a.
$\gamma$ total message arrival rate (message/s)

Variables

$x_p^k$ =1, if route having index $k \in K_p$ is selected for connection $p$ ; 0 otherwise.
$f_a$ flow of arc a.

Anycast Flow Assignment Problem

$\begin{aligned} &\min_X \quad Delay(X)=\frac{1}{\gamma}\sum_{a \in A}\frac{f_a}{c_a-f_a}\\&s.t. \quad \sum_{k \in K_k}x_p^k=1,p \in P \\ &\quad \quad \quad x_p^k\in\{0,1\},p\in P,k\in K_p,\\ &\quad \quad \quad f_a=\sum_{p\in P}\sum_{k\in K_k}\delta_{pa}^k x_p^kQ_p,\\ &\quad \quad \quad f_a \leqslant c_a,a\in A \end{aligned}$

Heuristic Algorithm anyCast Flow Deviation_DELay(CFD_DEL)

image.png

网友评论

本文标题：2018-12-13

本文链接：https://www.haomeiwen.com/subject/zlovhqtx.html

延伸阅读

深度阅读

您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！