拉格朗日松弛

《Resource Optimization for Content Distribution Networks in Shared Infrastructure Environment》

应用背景：CDN网络，通过租赁带宽、服务器存储容量等相关资源形成

本文网络基本性能

• 网络供应商控制物理服务器与网络构架
• 服务供应商租赁资源
• 可动态分配资源

困难与挑战

• 内容存储选择与请求管理
• 资源分配与调度策略
• 资源有价

本文模型：混合整型规划问题--NP-Hard问题

解决方法：拉格朗日松弛法+贪婪搜寻启发式算法

CDN供给框架

• 虚拟CDN服务器：计算资源 存储资源 带宽资源
• 服务器位置影响传输时延
• 虚拟链路：用于软件分发，内容复制与更新，后台通信
• 拓扑设计：考虑潜在服务器位置，资源租赁花销与容量限制，用户需求及空间分布，服务性能要求

CDN供给模型

• 假设：只考虑内容传输带来的带宽损耗（不考虑内容分布和更新）；每个服务器的计算能力、带宽用量与花销和处理的请求量线性相关
• 用户节点产出请求；潜在服务器节点提供资源，建立代理服务器
• 限定时间元内可处理的请求数
• 节点间距离已知；默认选择最短路径
• K个内容热门程度已知，内容大小，所需计算资源和带宽资源。时间元内某节点对于某内容的请求量
• 花销：站点建立花销，存储花销，带宽花销，计算花销
• 可接受QoS阈值：T时间下每个内容的平均距离要求
• 供给问题：配置优化问题（满足QoS指标同时最小化花销）

 

• 变量定义：  带宽和计算的总花销

• 线性规划模型：

  • QoS阈值
  • 若内容已经存储，则必须服务
  • NP-hard问题（选址问题）
  • 启发式算法求解
  • 所有用户的总请求
• 用户节点可认为是一个用户集群，不止一个用户

问题求解

拉格朗日启发式算法

用于松弛限制：→是拉格朗日乘子

松弛后目标函数：

两个子问题

• （二进制变量问题）
  • 对于每个地点i,问题变为：
• （连续变量问题，标准线性规划问题，用最优包裹求解器求解）

启发式算法

用次梯度算法调节拉格朗日乘子，求收敛

启发式贪婪算法

若基站等拓扑已定，则站点建立的花销为固定值，则问题可简化为：

（对每个内容k而言）即，有性能约束的选址问题

两级贪婪启发式搜寻法

• 第一级：找备选拓扑
  • 所有服务器全开算总价
  • 当节点i移除，计算当下拓扑的总价
  • 若有花销节省，关闭花销最多的那个节点
  • 返回第二步直到没有花销可以节省
• • 第二级：找该拓扑下最佳存储（复制）方案（确定内容复制方案后，问题转化为单纯的传输问题）
     

    *每种可能拓扑的价格

• 按照需求量将所有目标内容降序排列
• 对每个内容k
  • 将内容k存储于所有服务器计算当下花销（约束传输问题）
  • 对每个复制内容，若被移除则通过再优化该问题寻找节约花销
  • 丢弃提供最大节省的复制内容
  • 重复丢弃直至没有优化余地
• 更新每个服务器剩余资源考虑下一个内容

实验执行

不同网络拓扑生成：GT-ITM拓扑产生器

 

 

 

 

转载：https://blog.csdn.net/Star_Drift0/article/details/102502400