1 introduction
近年来，NTRA-DOMAIN流量工程已广受欢迎-好的流量工程工具可以极大地促进大型运营IP网络的管理和性能[4]，[23]。 流量工程的两个重要组成部分是了解流量，以及配置（和设计）路由协议。 这两个部分是相关的-对流量矩阵（TM）的良好理解和流量动态可以通过更适当的流量路由来更好地利用链路容量[11]，这已广为接受。 从理论上讲，如果TM确切已知，则可以通过求解相应的多商品流问题实例来获得针对它的最佳路由[18]。 通过使用最常用的域内路由协议OSPF / IS-IS，可以根据TM调整链路权重，以经常获得接近最佳的利用率[12]。 不幸的是，测量和预测交通需求是一个虚假的问题[4]，[23]。 在网络的所有链路和出口/入口点上很少进行流量测量，甚至更难估计起点-目的地流量集合。 此外，需求会随着时间的变化而变化-在昼夜周期中，并且由于网络内部或外部的特殊事件或故障而难以预测。 这些问题最近已通过模型和测量工具[7]，[10]，[11]，[17]，[21]解决，这些工具和工具可以推断和估算交通需求。
但是，似乎最大的希望就是对需求的大概了解，而不一定是非常当前的需求。 即使已知当前需求，它们的动态性质也带来了挑战：一方面，希望路由对当前流量需求有效，因此可以根据需求的变化进行调整。 另一方面，人们希望将更改限制在路由上，因为在系统达到一致状态时，更改可能会由于路径移动和收敛时间而导致服务中断。 对于OSPF / IS-IS路由，在[13]中探讨了这种折衷方案，该技术开发了一种技术，该技术可在TM更改时将更改量限制为OSPF / IS-IS链路权重（确定路由）。因此，良好的系统工程要求设计在一定条件下具有鲁棒性。 也就是说，可以针对各种适用的流量需求几乎最佳地执行路由。 我们的主要目标是探索这种路由的可行性，也就是说，在我们了解流量需求的范围内，了解可获得的路由质量的敏感性。 尽管对这两个基本的交通工程构建块，路由和TM估计都进行了深入研究，但对它们之间的相互作用及其潜在的性能折衷还没有很好地理解。
尽管人们普遍认为了解流量需求对于实现网络的良好利用是必不可少的[4]，[11]，[17]，[23]，但这种信念从未得到过仔细的量化：在对TM performance没有认知的情况下（ 或只有基本认知 (ballpark knowledge) 的情况下），如何设计路由性能？ 也就是说，为了保证良好的利用率，需要对流量需求进行估算的精度如何？ 当流量需求发生变化时，在某些性能保证范围内可容许的变化范围是多少？ 当实际流量需求偏离假定流量需求时，针对特定TM设计的最佳路由将如何执行？ 我们提出的问题涉及受管IP网络的基本限制和折衷-我们希望随着路由协议的发展，这些问题将继续存在-特别是在部署更复杂的OSPF / IS-IS权重调整时[12]，[13] ，并逐步部署了更灵活的协议，例如多协议标签交换（MPLS）协议[3]，[20]及其未来的后续产品。
为了寻求这些问题的答案，需要一种方法来衡量给定路由在一定范围的流量需求下的性能，以及一种设计在适当范围的流量需求下可以良好运行的路由的方法。 但是，尽管先前已知的算法可以为特定的TM（或一小部分TM）获得最佳路由，但是它们不能扩展为在广泛的TM上工作。 我们工作的核心是新颖的算法，在此算法的基础上，我们构建了可为一系列可能的TM生成最佳路由的软件。 该路由可以在TM范围内最佳地平衡负载-通过为该TM量身定制的最佳路由，可以最大程度地减小任何TM的最大链路利用率偏离最佳状态的程度。 我们的软件还使我们能够通过在适用的TM范围内计算每个路由获得的最差性能比来比较不同的路由。 我们的评估利用了Rocketfuel项目[16]，[22]和[17]中研究的测试网络提供的各种ISP的地图。
第II节中描述了数据，第III节中描述了我们的绩效指标和方法，随后在IV节中给出了评估结果。 我们使用的LP模型和相关理论在第V–VI节中进行了开发。 在第七节中，我们对一些简单的网络结构进行了渐进分析，对我们的评估进行了补充。
2 Data
我们描述了我们使用的测试拓扑。 不幸的是，ISP将其拓扑视为专有信息，直到最近，研究人员不得不为专有信息合成数据作好准备。 因此，结论通常缺乏通用性和可验证性。 Rocketfuel项目[22]最近取得了突破，该项目开发了一套新的测量技术，并发布了各种ISP的代表性集合的公开可用的近似路由器级拓扑。 我们使用启发式方法通过链接容量和流量矩阵来扩充此数据。
2.1 Topologies
我们使用来自Rocketfuel数据集的六个ISP映射，这些映射具有相应的OSPF / IS-IS权重[16]。 然后，我们折叠拓扑，以使“节点”对应于城市，以获取近似PoP到PoP（存在点）拓扑。 我们还包括在[17]中评估的14节点和25link的“第1层PoP到PoP拓扑”（在续篇中标记为“ N-14”）。 表I列出了研究的拓扑。
ROCKETFUEL（按名称和名称）和[17]（N-14）网络的拓扑。表中列出了我们称为PoP的路由器和链接的数量，城市和城市间链接的数量。 如果删除了1个连接的组件（“悬挂的树”），则最后两个列（减少的城市和链接）列出了剩余的城市和链接的数量。这些组件不会改变不同路由的相对质量（请参阅LEMMA 5.2）。 ，我们可以根据这些减少的图表更快地执行某些计算
2.2 Capacities
Rocketfuel和[17]中提供的拓扑不包括链接的容量，这是我们研究所必需的。 火箭燃料图确实包含派生的链路OSPF / IS-IS权重[16]，这些权重经计算以匹配观察到的路线。 在没有容量的其他信息的情况下，我们使用权重通过根据容量“转变” Cisco推荐的链路权重默认设置来关联希望兼容的能力：Cisco OSPF权重的默认设置为： 将每个链接的权重设置为与它的容量成反比例[8]。
2.3 TMs
通常无法提供准确的流量矩阵。 它们不仅被ISP视为专有，而且，如引言中所述，很难以合理的准确性获得它们。 因此，我们使用了两个合成交通矩阵族，我们将其称为Bimodal和Gravity TM。
- Bimodal TM：观察到只有一小部分的原产地（OD）对具有非常大的流量[6]。 该模型假设这些流量控制了拥塞点。 随机双峰分布随机抽样一小部分OD对，然后从某个范围内随机地均匀分配一个对。[17]中使用了随机双峰分布（和其他随机分布）。
- Gravity TM：由于在设计网络时会考虑一些流量需求，因此需要针对此类流量需求评估不同路由的性能。 我们使用了类似于[21]中建议的Gravity模型来生成“对应”网络的需求。 [21]中的工作提出了一种从对骨干网流入每个PoP的流量进行测量来推断completeTM的方法。 然后，外推法假设来自某个PoP的流量部分在其他PoP处所吸收的流量与在这些PoP处所吸收的总流量成比例。 根据[21]，这个简单的模型出奇地准确。 由于我们甚至没有这些更严格的流量值，因此我们使用了基于容量的启发式方法，该方法假设每个PoP的流入/流出流量与连接链路的总容量成比例。 然后，我们按照[21]中的引力模型来推算完整的TM。
3. METRICS AND METHODOLOGY
3.1 Routing
fa,b(i,j)是一个比例
3.2 Metrics
在一个TM上的指标
最优策略的得分
对策略的评分
一组TM上的评分
我们将性能比称为路由的oblivious performance ratio。 oblivious ratio是路由相对于所有TM而言最差的性能比率。 最小遗忘率的路由是最佳遗忘路由，其遗忘率是网络的最佳遗忘率。
为了更好地解释性能比，请注意，在集合或链路容量中TM的缩放比例下，它是不变的。 性能比构成了给定拓扑和一组TM上不同路由的比较度量，但是它并不是不同网络拓扑之间有意义的比较度量，它是相对于最小可能的最大链路利用率来定义的，但是 最小最大利用率本身随拓扑而变化。 还要注意，可能存在许多可能的最佳路由，并且它们在特定TM上的执行方式可能会有所不同。 第七节提供了一些简单网络上的最佳遗忘性能比的说明性示例和分析。
3.3 computing an optimal routing
直到最近，已知的工具都可以优化针对给定TM的路由，但是除了特定的高度结构化的拓扑（例如超立方网络）以外，关于如何有效地针对广泛的集合构建最佳路由的了解还很少 需求和最佳性能比率是多少。 Räcke[19]最近的一项突破性工作表明（存在）一个令人惊讶的上限：所有对称网络（即，两个方向上的链路容量相同的网络，通常在大型骨干网中都是这样）存在一个路由whose oblivious ratio是节点的对数的多项式。【一个最坏情况，也就是一个下界被bound住了】Räcke的存在边界触发了针对任何网络（对称与否）的最优遗忘路由[5]的多项式时间构造的发展。 文献[5]中的多项式时间算法基于将椭球算法应用于指数大小的LP模型，因此不适用于大型网络。 我们开发了一种新颖，简单，快速的算法（渐进式和实现式），用于计算基于多项式大小LP公式的最佳遗忘路由（请参见第VI节中的详细信息）。 然后，我们扩展模型以针对OD对要求的范围限制优化路由。 在我们的仿真中，我们使用==CPLEX LP解算器==[9]来解决这些LP（也可以应用其他公共领域LP解算器）。
3.4 Limitations
我们在本节结束时讨论了局限性。 我们的模型和指标无法捕获流量需求与最终实际吞吐量之间的相互作用，而是通过对所有需求的确进行路由而获得的最大链路利用率来比较不同的路由。 这是一个合理的指标，因为利用率越高，数据包丢失和拥塞的可能性就越大。 我们的评估重点是点对点（OD对）需求，而不是点对多点。 点对多点需求通常与大型ISP有关（例如，当有多个对等点指向不同的ISP，因此许多出口点中的任何一个都可以互换使用[11]）。 这种点对点“限制”主要是由于我们数据的局限性，原则上我们的技术和软件可以扩展到涵盖点对多点的需求。 我们针对最大链路利用率和性能比进行了优化。 在特定的实现上下文中，我们的方法可以考虑其他因素（例如，使用MPLS时，除了容量利用率外，可能还需要优化MPLS标签堆栈大小或预配置路径的数量。）。
4. Experiments and results
我们要解决的第一个问题是，在不了解流量需求的情况下，在我们的测试网络上可获得的最佳性能比保证是什么？ 表II列出了三种不同路由的遗忘性能比：最佳遗忘路由（使用6-C节中的LP公式计算）和另外两个自然路由-OSPF路由（使用数据集中提供的权重），以及 Gravity TM的最佳路由（通过求解多商品流LP计算）。 每个给定路由的性能比是使用第6-A节中的“slave 属LP”公式计算得出的。 评估的拓扑上的最佳遗忘性能比范围为1.425-1.972，这意味着这些网络具有的路由可确保在任何TM上具有最大链路利用率，最大可达最大表利用率的43％-97％。 为此TM量身定制的可能路由。 评估的其他两个路由的遗忘率明显更差（2-3位），这意味着在某些TM上，它们与定制的最佳路由相差很远。 这些差距表明，在不使用我们的优化工具的情况下，不可能以临时的方式获得接近最佳的遗忘性能比。
最大利用率的43％–97％（最坏的情况）开销对于正在运行的ISP而言是微不足道的-但是，好消息是，即使不了解流量需求也可以获得这样的保证。 然而，幸运的是，尽管通常很难获得TM的准确的当前估算值，但有关TM的信息还是很多的。 TM可以在某个已知范围内变化，或者可以估计到某个已知精度内。 在这种情况下，我们希望对处于一定范围内的所有TM提供性能保证。 我们要研究的下一个问题是可达到的性能比对已知TM的“误差范围”的敏感性。 （请注意，随着我们扩展针对其计算性能比率的TM集合，该比率只能增加。）
一些定义
error margin $\omega$
5. basic properties
我们建立一些基本属性。 我们将基本TM的最佳路由的性能作为余量的函数进行限制，并建立一些属性以减少实例所需的LP模型的大小。
5.1 Performance Deterioration as a Function of Margin
- Lemma 5.1
这是渐近严格的，也就是说，存在无限的实例家族，其中
5.2 Reducing the Problem Size
以下引理表明，出于计算性能比率的目的，我们可以“factor out”网络中无法实现路径diversity的部分（因此，所有路由都将执行相同的操作。）。我们使用此引理来减小输入拓扑的大小。
引理5.2：移除degree-one的节点不会影响网络的oblivious ratio。 同样，它不会影响任何一组TM的最佳性能比。
引理2是以下引理的推论。
引理5.3：网络的最佳遗忘率可以通过将网络划分为2个边缘连接的组件，并在这些组件上获取最大的遗忘率来计算。
证明：如果网络不是2边缘连接的，则可以将其划分为两个非空组件，并通过和边缘连接。 很容易看出，的最佳遗忘率至少是和的最大最佳遗忘率的比：对于仅在两个都存在的OD对上具有正需求的TM所获得的最佳性能比on分别 位于）等于（分别为）的最佳遗忘率。 要看到这一点，请注意所有离开/进入的流都必须经过边缘，因此将需求内部路由到边缘并流出边缘永远没有优势，因为该流将必须在同一边缘上返回并形成一个 流周期（对称参数表示）。 的最佳遗忘率至少是这些受限制的TM集合的最佳性能比率。
以下引理指出，对称TM上具有对称定向链路的网络的最佳遗忘率（即，两个方向上的链路容量均相等）与通过替换每个集合而得出的无向网络的遗忘率相同 由具有相同容量的单个无向链接组成的有向链接。
这个引理意味着无向图的已知边界会carry out到“real” backbone网络（链接是有向的和对称的）。 此引理还可用于减少LP模型的大小。
引理5.4：考虑一个无向网络G，以及一个由其衍生的直接网络G^’^，方法是用两个反平行弧替换每条边e，其容量与e相同。
- G^’^具有对称的最佳遗忘路由。
- （在所有TM上）的最佳遗忘率等于在所有对称TM上的最佳性能率。 此外，的最佳遗忘路由对应于对称TM的最佳路由。
证明：考虑对称有向网络和路由。 我们推导了一个对称路由，其最多具有与相同的遗忘性能比。 设为通过反转流向和OD对获得的“反向”路由。
我对这条引理的感觉就是 这是在证明 现实中backbone network (which 通常是双向对称的)的最佳oblivious routing可以通过这种方法降低计算复杂度
可以将引理概括为相对于对称的任何TM子集保持最佳性能比。 一个有趣的问题涉及定向对称网络上所有TM的最佳性能比与对称TM上的最佳性能比之间的关系。 不难看出前者至少是后者的，但最多是后者的两倍。 实际上，任何对称路由都使得其在常规TM上的性能比率最多是其在对称TM上的性能比率的两倍。 有趣的是，该比率是否以及何时可以接近2。
6. LP models
首先，我们回顾一下结果[5]，该结果表明可以在网络大小的多项式时间内计算出网络的最优遗忘路由（和遗忘率）。然后，我们开发了一个简化的LP模型，该模型可以实现更快的运行时间 ，并修改此模型以处理OD对要求的范围限制。
A. The LP Model of [5]
-1. questions
- CPLEX LP solver是什么
- 常用的功能
