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

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