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