CS269I:Incentives in Computer Science 学习( 二 )


定理:在线性网络中,POA至多为4/3
4Over-(网络超额配置) 4.1
由于给网络增加容量是相对便宜的,因此在搭建网络的时候一个常用的方法是在网络内安装更多的负载,让网络中有一些冗余 。
研究表明,冗余节点的设置有许多好处——可拓展性,更低的延迟和丢包率 。它已经成为实现QoS( of )的一种手段 。
在这一节中,我们将建立理论来证明增加冗余节点可以提高网络性能 。
4.2 POAfor Over-
在使用M/M/1队列作为节点的处理序列时,网络延迟函数如下所示:(u_e为最大承载能力)
c e ( x ) = { 1 u e ? x if x < u e + ∞ + ∞ if x ≥ u e c_e(x)=\left\{ \begin{} \frac{1}{u_{e}-x} & \quad \text { if }\ \ xce?(x)=??????????ue??x1?+∞?ifx