[翻译] Multihoming成本及性能的优化.pdf

Multihoming 成本及性能的优化成本及性能的优化 摘要 摘要 大型企业及英特网服务提供商常用 multihoming 技术来接入 Internet 在本文中 我们设 计了一系列新颖的算法 smart routing 为 multihoming 用户在成本及性能上进行优化 通过分析和模拟现实收费模式 通信需求 性能数据及网络拓朴 我们评估了该算法 评估 结果显示该算法能非常有效地在减少成本的同时提升性能 我们进一步地检测了 smart routing 对全局网络均衡性的影响 发现 smart routing 用户能在不对其他用户造成明显影响的 情况下提升自己的性能 分类及主题 分类及主题 C2 6 计算机通信网络 网络 英特网 通用术语通用术语 算法 性能 关键字 关键字 Multihoming Smart Routing 优化 算法 1 引述引述 Multihoming 31 由于其可靠性 成本及性能上的优势 常被大型企业和英特网服务提供 商用以接入 Internet 一个客户或 ISP 网络 也可以叫做用户 有着多个外部连接 或一个 ISP 或者多个服务提供商 即可被说成 multihomed 31 一个用户如果能有效地控制其通信 量在多个外部连接上的分布 就可以说成实现了 smart routing Smart routing 也可被指为路 由优化或者智能路由控制 Smart routing 有如下几个优点 首先 smart routing 可以提升网络性能及其可靠性 最 近研究显示 27 32 33 与理想路由相比 网络级路由由于路由体系和 BGP 路由规则会导 致用户性能的优化被置于次要的地位 设备的瘫痪 短暂的不可靠和网络拥塞同样会影响到 用户性能 Smart routing 提供了一种由最终用户控制路由选择的办法 在 1 Akella et al 量 化了 smart routing 的益处 显示出选择有效的提供商能带来性能的提升 在 2 Akella et al 发现连接到三个ISP带来的延迟和吞吐量超过与3个multihoming连接的路由覆盖的5 15 其次 若考虑到特定收费模式 smart routing 能有效降低用户费用 最近的一份经济分析表 明 smart routing 不仅能减少最终用户费用 也能降低服务提供商的成本 由于 smart routing 潜在的益处及大量的 multihomed 用户 许多公司正积极开发着实现了 smart routing 的软件 e g 12 19 21 24 然而 由于这些是商业产品 它们的技术细节是 保密的 它们在 Internet 上的性能和影响也不能被很好的评测 还有一些对 smart routing 的 探索研究 e g 1 11 这些研究的重点仅在提升网络的性能 而用户费用作为使用 multihoming 的另一推动因素却被忽视了 此外 先前研究重点在潜在性能益处 而不在于 算法的实现 潜在的益处如何得以实现仍然是一个公开的问题 第 1 页 共 28 页 在本文中 我们开发了一系列优化 multihomed 用户成本及及性能的算法 从而实现了 smart routing 的部分益处 我们首先论证了单独优化网络性能会大大增加用户费用 导致 smart routing 使用价值的下降 为了说明这一点 我们提出新的离线和在线路由算法来减少 用户在通常收费模式下的费用 参考大学及企业的实际收费价格和通信需求 我们得出在不 考虑通信波动的情况下 与专用连接或利用轮询或同等时间片划分算法实现的间接连接相 比 我们的在线算法能显著地减少用户费用 我们同样设计了在线与离线算法在成本有限的 情况下为 smart routing 用户优化网络性能 参考实际收费价格 及对通信需求与延迟的追踪 我们发现在线算法能达到经过优化的离线算法性能的 10 20 在本文中 我们假设用户与一组 ISP 连接 是 multihomed 因此 我们重点在如何在这 一组 ISP 之间动态分配通信流量来优化成本及网络性能 是否运用 multihoming 及选择哪一 家 ISP 这本身就非常复杂 可能会牵扯到很多技术性的和非技术性的因素 这些我们将不 在本文中进行阐述 我们同样也假设用户只对成本及网络性能感兴趣 然而对于许多实际的 Internet 服务 例如虚拟私有网络 VPNS 仅对成本及性能进行优化是不够的 其他因素 例如易管理 易查错 安全性及服务质量 QoS 同样在用户的商业决定中起着关键职责 所以我们的技术在这些方面并不直接适用 然而 为了更好地理解在未来网络中smart routing 的潜在作用 我们相信应从先前以性能为中心的的研究转到将成本及性能放到同等地位加以 优化的优化构架中来 除了开发技术对成本及性能加以优化外 我们也评估了这些优化对网络全局的影响 我 们发现由于每一个独立的 smart routing 用户选择适当的路由以优化自身而不考虑对网络的 影响 smart routing 变成一个自私的路由方案 这些改变影响了网络性能 可能会导致自干 扰或与其他 smart routing 或正常通信产生干扰 Smart routing 能否在这些干扰中仍然保证其 性能优势 这要等以后才能知晓 我们通过大量的模拟研究了 smart routing 的全局影响 我们首先检查了 smart routing 在 自影响中的均衡性 即 smart routing 用户的路由决定改变了网络性能 网络性能的改变反过 来亦影响了路由决定 结果表明即使在自影响中 我们的算法仍能取得好的性能均衡接着 我们评估了 smart routing 通信如何影响了其他 smart routing 通信或单用户通信 评估是建立 在内部网络拓扑和现实通信中用户需求的基础上的 结果显示 smart routing 能在不降低其他 通信性能的基础上增加自身性能 我们关键性的贡献可概述为以下几点 我们设计了离线与在线算法以在现实收费模式的基础上降低成本 我们设计了离线与在线算法以在成本有限的基础上优化网络性能 我们在实际通信和性能数据的基础上进行分析与模拟 显示出我们的算法会产生高 性能 低成本 我们评估了当多个用户 自私 地优化他们自己的成本与性能时的 smart routing 性 能 我们发现在该情况下 smart routing 通信能很好地与其他通信相互影响 保持 通信均衡 本文剩余部分组织如下 在第二部分 我们回顾了相关工作 在第三部分 我们讨论了 实际的网络及收费模式 在第四部分 我们引出成本优化的重要性并展示了新颖的成本 优化算法 在第五部分 我们在现有成本限制的基础上优化网络延迟 在第六部分 我 们展示了评估的方法与结果 第七部分 我们研究了 smart routing 的全局影响并评估了 其他通信的影响 在第八部分 我们总结并讨论了以后的工作 2 相关工作相关工作 第 2 页 共 28 页 一些最近的研究 如 4 27 32 33 显示 Internet 路由常常导致用户性能的优化被置于次 要地位 有很多因素会导致这一现象 比如路由体系 路由方针 对网络拥塞或网络错误 如 果发生的话 的较慢的反应等 而 BGP 路由的不稳定性会进一步加深这一问题 这些观察 结果使得人们为使最终用户在路由选择上有更多的控制投入相当大的研究 例如在 24 27 中 作者们建议利用超负荷路由来提升用户性能 但要在实际中大规模部署这一方针还是具 有挑战性的 因为在多个部门间协调可不那么容易 Multihoming 为用户控制路由提供了另一种办法 许多大型企业 ISPs 甚至一些小的公 司早已通过 multihoming 方式来接入 Internet 先前关于 multihoming 的研究更多的是集中在如何设计协议来实现 multihoming 如 5 7 11 30 举几个例子 5 7 12 24 30 的作者们利用点对点 BGP 来作为实现手段 而在 9 21 中 作者们则利用 DNS 或 NAT 来实现 我们的工作和以上不同 我们工作重点不在于如何 实现 而在于设计算法以使用户决定在什么时候 分配多少通信量给不同的 ISP 以使优化用 户自身的成本及性能 总体上讲 我们的工作是对以上工作的补充 有许多文献评估了 smart routing 带来的益处 如 8 28 29 最近 在 1 中 Akella 等又 根据实际网络流量评测了使用 multihoming 的益处 他们的研究结果显示出 smart routing 在 大多数情况下有能力为 2 multihomed 用户带来至少 25 的性能提升 当有 4 个提供商时 带来的益处是最大的 被这些研究结果所触动 我们开发路由体系以在实际上获得这些益处 此外 我们还研究了多个 smart routing 用户相互影响下的未协调路由优化的结果 最后 有许多研究 如 1 15 17 研究了 smart routing 的算法设计 如在 1 中 Orda 和 Rom 调查了在哪儿放置 multihoming 用户 结果说明该问题是 NP 难度的 Cao 等在 6 中建议使用哈希函数来取得多连接之间的均衡 在 11 中 作者在本地网络中比较了多种路 由选择方案 结果显示使用哈希函数取得的性能提升与使用负载敏感的路由选择有的一拼 我们的工作与这些研究不同 我们的兴趣在于既提升性能 又要降低成本 我们也研究了多 smart routing 用户之间的影响及 smart routing 用户与 single homed 用户之间的影响 3 网络与收费模式网络与收费模式 在本段 我们描述了网络模式 ISP 收费模式及日常所使用的对性能的度量 3 1 网络模式网络模式 图 1 一个用户与 K 个服务提供商的例子 在图 1 中 一个 multihomed 用户有多路连接到 Internet 进行收发通信 分布式通信连接 中输入与输出通信的实现是不一样的 对于输出通信 用户网络中的边界路由能有效控制通 第 3 页 共 28 页 信如何被分布 对于输入通信 用户能用 NAT 或 DNS 来控制路由 读者可参考 1 5 7 11 30 其中有关于实现的更细致的探讨 应注意到我们讨论重点在于决定何时及在每条连接上应分配多少通信量 所以 multihoming 的实现仅是对我们研究的补充 因此 我们的算法能被应用在广泛的 multihoming 的实现及输入输出通信上 由于正如下面所描述 我们的通信轨迹仅由输出部 分组成 所以在本文中我们也就仅评估通信的输出部分 3 2 收费模式收费模式 用户由于 ISP 的相关服务而付以相应费用 费用一般由用户的通信量决定 例如 cost c x 其中由用户通信量来决定 我们用术语 charging volume 表示 c 是一个非减函数 将 x 映射到相应的成本上 不同收费模式由于各自 charging volume 及费用函数 c 的选择不 同而不同 通常 费用函数 c 是一个分段的线性非减函数 我们将在设计与评估中用到 Charging volume x 可由多种方式来决定 通常用到百分比收费方式与总量收费方式 百分比收费方式 这是一种现在被 ISP 所使用的典型的 usage based 收费方式 在 该方式中 ISP 每五分钟记录一次用户的通信量 在最后收费期间 所有每五分钟 通信量的第 q 被用来当着 charging volume x 的 q 收费 更具体的讲 ISP 将收 费期间的每五分钟的通信量以生序进行排列 然后以第 q I 的量作为 charging volume x 其中 I 是收费期间每五分钟的间隔总数 举个例子 假如 q 为 95 收费期间为 30 天 那么就以排序后第 8208 个间隔断的通信量来收费 95 30 24 60 5 8208 总通信量收费方式 这是一个较直观的收费模式 其中 x 是用户在总收费期间的总 通信量 在本文中 我们主要关注百分比收费方式 在附录 C 中 我们描述如何处理基于总通 信量的收费方式 在评测中 我们将使用到两组价格函数 一组是较简单的 如果通信量为 0 则价格也为 0 否则 价格是一个常数 我们从表 1 中取得价格值 表 1 发表在 25 中 在该表中 间或连接 Burstable 的价格基于百分比收费方式 而满连接 Full rate 也可 以说的专用连接有着与通信用量无关的固定价格 为评估我们的算法对价格函数的敏感度 我们也使用了另一组价格函数 见图 2 这些函数是较复杂一点的分布函数 DS3 的 24Mbps 的价格及 OC3 的 100Mbps 的价格与表 1 相符合 价格曲线的整体趋势反映了随着带宽的增 加价格的增量逐渐减少 这也与我们在 3 18 中所知道的价格曲线相一致 第 4 页 共 28 页 3 3 网络性能度量网络性能度量 可有多种方式来度量网络性能 在评估中 我们使用端到端的延迟作为度量手段 正如 在 24 中所述 延迟能反映出网络的响应时间 而且由于用户经常以较大延迟或快速增加的 延迟作为潜在的可靠性标示 延迟也被用来评测网络可靠性 我们的算法能很容易地扩展以 适应不同的度量方法 如延迟与丢失率的混合 latency w log 1 1lossRate 其中 w 是丢 失率相关的量 4 最小化总成本最小化总成本 由于先前的研究仅基于提升网络性能 而没有考虑到成本问题 我们首先将提出优化成 本的必要性 我们发现 通过仅仅优化性能可能导致用户成本的增加 既然基于百分比的收 费方式被普遍采用 我们将在下面通过该模式下的一个简单例子来阐述我们的观点 在第六 部分 使用实际数据所得出的性能结果将更进一步证实这一观点 假设一个用户有到 K 个 ISP 的 K 个相同的连接 再假设用户在每个间隔期间有一个单 位的通信量传输 每个间隔每个连接的延迟均在一个共同范围内 为了减少延迟 在每个间 隔期间用户在延迟最短的那个连接上传输其所有通信 而其他连接无任何通信 由于不同连 接上的延迟是同等分布的 每个连接接受通信大约是间隔的 1 K 所以当 K 小于 20 时 如 K 4 那么每个连接的 95 就是 1 也就是说通过优化性能 用户所付费用是单连接用户费用 第 5 页 共 28 页 的 K 倍 费用增加 K 倍对大多用户而言显然是不能接受的 给出了费用可能大幅增加的可能性 在本段中我们将研究如何设计有效的 smart routing 算法来优化费用 如在第三段所讲 我们重点在基于百分比的收费模式 在附录 C 中 我 们给出了基于总通信量的收费模式的算法 4 1 问题说明问题说明 我们首先介绍以下符号 K ISP 的数量 我们用 K 作索引 CK ISP k的价格函数 不是一般性 我们假设Ck是一个分段线性非减函数 I 收费期间的时间间隔数 用 i 作索引 F 流的个数 我们用 f 作索引 i fv 第 i 个时间间隔中流 f 的通信量 v i 第i个时间间隔中总通信量 亦即 v i fvf i 时间序列V v i 1 i I i kt 在第i个时间间隔中分配给ISP k的通信量 时间序列Tk tk i 1 i I 注意到 V kTk 向量和 qk ISP k的收费百分比 如如果ISP以 95 收费 则qk 0 95 qt X q Xsorted中第个的值 如果q 0 则为 0 其中Xsorted是x以非递减方式排序 X 是X中元素数目 pk ISP k的收费量 即Pk qt Tk qk 例如如果ISP k以 95 收费 那么pk就是分配 给ISP k通信的 95 现在我们正式提出流分配问题 给定价格函数Ck 流分配问题就是要求找除合适的tk i 使 总费用最小 我们考虑两种情况 fractional流分配及integral流分配 在fractional流分配中 流是无限 可分的 相反 integral流分配假设在每个时间间隔中每股流仅分配给一个ISP 后者中 当 用BGP来实现smart routing时 流可以很自然地用目的地址前缀来确定 流分配问题 不管是fractional或者是integral 可以更进一步地分为两类 离线与在线 离线型假设vf i 事先给定 然而在线型需要预测vf i 并处理预测错误 在线integral算法更实际 且面对较低控制 离线fractional算法同样重要 因为它们提供了较低的成本 且可进一步作 为设计我们在线算法的基础 4 2离线离线fractional流分配流分配 我们从解决离线fractional流分配问题开始 首先我们展示一个在ISP没有容量限制情况 下来优化流分配的有效算法 接着我们补充该算法来处理有容量限制的情况 4 2 1没有容量限制下基于百分比收费模式的优化算法 优化成本的一个关键处在于决定charging volume 比如 若ISP用95 的收费模式 我们 第 6 页 共 28 页 则需要为每个ISP计算95 下的通信量 一旦知道了每个ISP的charging volume 我们就可以 分配流量以保证ISP k的服务比其通信收费量多的时间间隔数不超过 1 qk I 如95 的收 费模式为5 I 基于以上观察 我们开发出一个有效的算法来分两步计算一个优化的流分配 i 计算 每个ISP的charging volume ii 根据charging volume分配流量 4 2 2计算charging volume 在本段中 描述了如何计算优化charging volumes以使总成本最低 我们展示了charging volumes可被分为两步 i 计算charging volume总值 即 kpk ii 根据总值来计算单个pk值 4 2 2 1计算charging volume总值 首先来展示如何计算总charging volumes以使总成本最低 这是基于以下两个重要观察 这两个观察我们将在下面进行证明 第一个观察是关于charging volume总量 总费用有一个 单一特性 这个单一特性即是指套优化总成本 kpk 我们需要最小化 kpk的值 第二个观 察是最小化 kpk的值等同于qt V 1 k 1 pk 举个例子 有4个ISP 它们都是基于95 的量 进行收费 那么最小化 kpk即等于总通信量的80 1 4 1 95 0 80 这两点观察说明了 要优化成本 我们需有 kpk qt V 1 k 1 pk 其中的V与qk很容易算出 现在我们正式证明这两点观察 定义Cmin s min kCk pk kpk s 则有 定理1 如果S0 S1 0 那么Cmin S0 Cmin S1 证明 根据 kpk S0 pk集最小化 kCk pk 则有Cmin S0 kCk pk kCk pk S1 S0 Cmin kpk S1 S0 Cmin S1 其中第一个不等式是由于价值函数Ck是单调非减函数的 第二个不 等式是根据Cmin的定义 第二点观察 书面表述如定理2 确定了 kpk可达的最低下限 定理2 要证明该定理 我们将用刀以下lemma lemma的证明见附录A LEMMA 3 quantile inequality 给定K等长时间序列 其 中n Tk 且0 ak 1 则有 综述上述lemma 我们可证明定理如下 在上述证明中 我们隐式地假设qk I都为整数 其中I V 当qk I不为整数 我们可 以通过重新调整qk为来保证其整型值 清楚地看出 这样的调整不会影响 的结果 即 其中I V 在以下 本文中 我们 假设已事先对每一个qk作了这样的调整 例如 当讨论一周收费期间以95 收费 即 I 7 24 60 5 2016 我们实际上用qk 与 qk 0 95 1915 2 2016相反 第 7 页 共 28 页 4 2 2 2 计算单个charging volumes 一旦V0确定了 接下来一步就是计算最小化趋向的优化的 charging volumes pk 从定理4可以很容易看出当所有的Ck均concave 优化的charging volume Pk可很容易被 求出 证明忽略了较短时间部分 定理4 如果所有的价值函数Ck是concave 那么优化结果为除了一个ISP外 其余所有 charging volumes为0 更具体地讲 让k0 argmink ck V0 ck 0 定义当k k0时pk V 0 否 则为0 对于每个满足 kpk V0的pk有 kCk Pk kCk pk 对于一般的价值函数 如非增分段函数 更难决定优化的charging volumes pk 其最 小化 kCn pk 趋于 kpk V0 下面我们来介绍一个动态编程算法来解决该问题 设定opt v k 是期限的k个ISP服务器通信量的优化后的费用 有 根据上面的 递归关系 我们可以从opt v 1 起来计算opt v k 同能追踪出相应分配量opt v0 k 的值 可得出优化费用 而其相应分配量则决定了pk 算法的时间复杂度为O K V0 2 空间复杂度为 O K V0 以上算法假设期望精度为1 由于价格曲线的点也是很粗糙地取得的 所以在实际 中不必如此精确 当然谨慎点可以取得任意的期望精度 例如 如果要V0和Pk精确到100 我 们仅需要计算opt v k 其中V是100的倍数 这同时降低了时间复杂度和空间复杂度 更准 确地说 对于精度P 时间与空间复杂度分别为和 实际上 我们一般仅需要处理K 10和v0 p 1000的情况 所以算法复杂度是相当低的 4 2 3给定charging volumes来分配通信量 给定charging volumes 对于ISP k取名为pk 下面我们来描述如何在各个时间段来分配 通信量 通信量分配的目的在于确保pk是ISP k的通信量 也就是说 在qk I个间隔内 分配 给ISP k的通信量将小于或等于pk 并且ISP k仅被允许在剩下的 1 qk I个时间间隔内提供 比pk多的服务 这点可以通过将时间间隔划分为非高峰时间间隔和高峰时间间隔来达到 根据V0的定义 在总通信量不大于V0的时间间隔内 所有的通信可在任何一个ISP接受的 通信量不多于其charging volume的情况下来能成 因此 我们称这些时间间隔为非高峰时 间间隔 对剩下的间隔 至少有一个ISP要实际承担比其charging volume要多的通信量 正 因为如此 我们称剩下的间隔为高峰时间间隔 我们将用下本文下面部分这两个术语 根据上面对高峰和非高峰时间间隔的定义 我们根据以下方法来分配通信量 如果时间 间隔是非高峰的 我们分配给ISP k的通信量将小于等于pk 有多种分配方法可实现以上限 制的分配 并且这些分配方法的成本是一样的 所有我们任取一个 在di五段 我们将利用 这点灵活性来提高性能 对于高峰时间间隔 将随机挑选一个ISP k来超标 即 分配给他 的通信量将超过pk 这通过分配给剩下的ISPs各自的pk 然后将剩余的通信量统统分配给超 标的那个ISP 在我们所假设的ISPs没有容量限制的情况下 这样分配是合理的 我们将研 究ISPs有容量限制的情况下的流量分配情况 总结以上研究 我们即得出图3中对可分流成本降低的算法 很容易看出 pk肯定是ISP k 的charging volume 因为ISP k在 1 qk I时间间隔内接受的通信量多于pk 由于根据定理 2 pk的总和等于V0 则该算法实现了最低成本 第 8 页 共 28 页 图3 在基于百分比的收费模式 没有容量限制的情况下 对可分流分配的一个离线优化算法 4 2 4处理容量限制 前面算法假设ISPs没有容量限制 即 他们可在时间间隔内传送所有的通信量 这个 假设是合理的 因为multihoming常被用来提供高可靠性的服务 即使其他所有的ISP s都断 了 用来还能使用剩下的哪个ISP s 然而单个的ISP也可能没有足够的容量来处理所有的通 信 图4 整体分流离线分配算法 GFA offline 一个基于百分比收费模式 并在容量限制 情况下的算法 成本函数ck x 假设当x超过ISP k的容量时将达到无穷大 常量在我们搜 索f时控制步进大小 为高峰时间间隔的最大部分 在我们的评估中 0 01 我们利用图4中的算法来处理容量限制的情况 其基本思想是选择高峰时间间隔 记为f 因此在每个高峰时间间隔期间有多个ISPs一起提供足够的容量来传送所有的通信 更一般 地 给 定 d 和 相 应 的 V0及 pk 在 图 4 的 while loop 中 计 算 我 们 需 要 知 道 即 分配给不同的ISPs f I高峰时间间隔是否满足 i 没有ISP k服务了超过 1 qk I个时间间隔 ii 在每个高峰间隔期间有足够的总容量 将能在任意高峰时间间隔内能处理通信的ISPs集合记为g 一个g的足够情况是 其中Ck连接k的容量 maxload是收费期间的最大负担 tg记为组g中ISPs承担负载的时间间隔数 G记为所有 2 k 可能ISP组 当满足下面情况 将 存在一个高峰时间间隔 且将返回真 下面是些说明 首先 K一般很小 如 小于10 因此变量的个数是可管理的 第二 上面条件是充分不必要的 因为即使高峰时期承担的通信量总是最大通信量 我们仍能分配 然而 既然高峰时间间隔间分配的通信量总是低于最大分配量 如 95 的分配小于最大分 配量 那么即使上面情形不满足 仍然能进行高峰分配 当最大分配量与最小分配量差不 第 9 页 共 28 页 多时 状况就很紧了 第三 所有这些限制是线性的 因此我们可以通过解决一个整型编程 问题来决定存在的最大负载的分配 既然间隔的数目巨大 在实践中我们首先解决没有整型 限制的情形 然后通过变园来得出结果 我们称这个分配算法为全局部分离线分配 GFA offline 4 3在线整式分配算法 4 3在线整式分配算法 上一段离线部分分配算法假设通信模式事先已知 并且通信流是可以划分的 在实际中 通信模式不会事先给定 更进一步 也许人们倾向于不可分的流 为了减少控制 如实际中 使用的BGP 在本段中 我们展示在线整式分配算法来处理两种这情况 我们的解决办法由