传输网络中相互作用的优化问题建模和分析—理论计算机科学电子笔记141.

理论计算机科学电子笔记141（2005）97-114www.elsevier.com/locate/entcs传输网络中的相互作用奈杰尔·沃克1马克·温宁克2英国电信研究，B54，141，AdastralPark，Ipswich，IP53RE，英国摘要我们提出了一个模型，捕捉发生在运输网络中的基本相互作用，包括路由和流量控制。许多网络过程可以被看作是解决优化问题，或者在相互竞争的利益之间寻求平衡。 问题的结构是通过说明 一个“组件图”，它规定了系统不同部分之间的通信和交互模式。我们展示了如何同样的形式主义也捕捉电路中的相互作用。关键词：优化，路由，拉格朗日对偶，相互作用，图形模型。1介绍我们感兴趣的是开发技术来建模和指定通信网络中发生的过程和交互，主要是传输网络，但最终共享基础设施的其他组件，其中大部分还包含网络功能的元素在这种情况下，交互可以跨越许多不同的“轴”（不同的用户之间，用户和运营商之间，节点之间或网络层之间，流量和成本之间）以及非常不同的每个过程或相互作用都发生在一个更大的空间和时间环境中。许多网络过程可以被看作是解决某种优化问题（例如，最小成本路由），或者更一般地，作为寻求平衡-1电子邮件：nigel.g. bt.com2电子邮件：marc. bt.com1571-0661 © 2005 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2005.05.018N. 沃克，M。Wennink/Electronic Notes in Theoretical Computer Science 141（2005）9798竞争利益之间的竞争（例如共享可用容量）。从计算的角度来看，问题是找到系统中达到这种最佳或平衡点的参数（变量）值这必须动态完成，并且通常作为分布式计算，以响应环境的变化例如，路由协议必须不断响应链路可用性的变化，相应地调整路由虽然我们在本文中没有直接报告，但我们相信，开发高级（编程）语言来分析和组织网络功能和结构将有很大的价值我们预计这种方法的优势包括更好地陈述管理信息，暴露不同协议的选项，在公共语言框架内比较不同的设计选项，以及网络状态量，变量数量和命名结构等方面的精确性在这里，我们只把注意力限制在一个相互作用的模型上，这个模型应该是这样一种语言的基础。我们借鉴了优化的数学，这使我们的工作与其他最近的工作并行使用优化理论在网络和协议的设计和分析[9，11]。我们的一般方法概述如下。首先将寻求分布式解决方案的网络任务表述为数学优化问题，涉及目标函数和一些约束。然后，通过将约束纳入目标函数来放松问题。修改后的目标函数被称为拉格朗日函数，并且是优化理论中的标准[4]。它取决于原始目标函数的变量，以及量化违反约束的成本的一组额外的对偶变量然后，问题变成找到这个新函数的鞍点，而不是最小值或最大值。拉格朗日量通常可以写成不同分量的和，其结构可以描述为突出显示这些分量之间的连接的图。这个图从几个方面说明了原始问题的结构：它允许分解，图的不同部分被认为是子问题;然后可以通过将这些子问题分配到网络中的不同节点或处理器来分配这些子问题;它指定了子问题之间必须支持的通信通道;它建议分布式算法;它的结构揭示了系统中相互作用和反馈的不同轴组件图的不同分解导致不同的算法，并且以这种方式布置用于解决原始问题的设计空间我们通过一个基于简单网络中最短路径路由的例子来我们提出了这个问题的拉格朗日N. 沃克，M。Wennink/Electronic Notes in Theoretical Computer Science 141（2005）9799并展示了分解过程如何导致Bellman-Ford算法的分布式版本我们还提出了第二个算法，基于动力系统方程，收敛到鞍点的任何differentiable拉格朗日满足凹凸性质。然后，我们扩展我们的最短路径的例子来展示如何在这个框架中的路由控制之间的相互作用许多具有实际意义的网络问题，包括路由和网络流控制问题，我们在本文中讨论，可以捕获的凹凸拉格朗日。然而，一些组合问题不具有这种性质，我们将在第7节讨论这种限制的含义。2鞍点与对偶正如刚才提到的，我们模型的一般数学设置实际上比优化更一般我们研究的问题找到一个典型的许多实值变量的凹凸函数的鞍点我们通常称这个（实值）函数L为拉格朗日量，因为它经常（但不总是）可以从优化问题的拉格朗日松弛中导出在本节中，我们首先介绍一般的鞍点条件，然后将其专门用于从线性规划导出的拉格朗日函数的光滑近似。L的自变量被分成原始决策变量，x =（x1，.，xn）和对偶决策变量y =（yi，.，ym）。定义在域X×Y上的拉格朗日量L是凸-凹的当且仅当• 对任意x1∈X，x2∈X，y∈Y和0 ≤α≤1，我们有αx2+（1−α）x1∈X，且L（αx2+（1−α）x1，y）≤αL（x2，y）+（1−α）L（x1，y）• 对任意y1∈Y，y2∈Y，x∈X且0≤β≤ 1，我们有βy2+（1−β）y1∈Y，且L（x，βy2+（1−β）y1）≥βL（x，y2）+（1 −β）L（x，y1）一个点（x∈，y∈）是L（x，y）的鞍点，如果(1)L（x≠，y）≤ L（x≠，y≠）≤ L（x，y≠）<$x ∈ X，<$y ∈ Y.鞍点可以被解释为一个博弈的均衡配置原始变量试图最小化拉格朗日量的值，而对偶变量试图最大化它。相互冲突的利益在一个鞍点上达成和解线性规划所对应的拉格朗日量是凹凸的，许多网络问题可以表述为线性规划[1]。设A是m×n-矩阵，b和y是m-向量，c和x是n-向量.线性N. 沃克，M。Wennink/Electronic Notes in Theoretical Computer Science 141（2005）97100形式的程序mincxs. t. Ax = b，x≥ 0有一个相应的拉格朗日函数(3)L（x，y）= cx-yAx+ yb，x≥ 0。如果（x∈，y∈）是（3）中L（x，y）的鞍点，则x∈是相应线性规划（2）的最优解。更一般地说，凹凸拉格朗日量可以与任何凸优化问题相关联，而不仅仅是那些线性规划。以这种方式导出的拉格朗日量的鞍点由著名的Karush-Kuhn-Tucker条件[4]表征。在第四节中，我们将介绍动力系统方程和一个算法，要求拉格朗日在其鞍点区域可微即使拉格朗日函数看起来是可微分的，这个条件也可以仍然失败，如果鞍点位于其域的边界上例如，如果（3）中的非负性条件x≥0之一是紧的（即，对于某个分量xi，xi= 0）。为了避免这个问题，我们可以引入障碍函数。这个想法是在拉格朗日量中添加一个（可微分）分量，当x接近它的领域。然后，修改后的拉格朗日的鞍点将位于距离域边界的某个有限距离处这种方法类似于内点法[4]，内点法同样直接向优化问题的目标函数（而不是其拉格朗日函数）添加障碍，以确保它在其最小值（或最大值）的区域内是可微分的。最受欢迎的选择是对数障碍函数。因此约束z >0将通过添加一个分量−Rln（z）来遵守。通过为每个这样的障碍函数选择非常小的值，修改后的问题（决策变量的值和目标函数的值）任意精确地逼近原始问题的值内点法通过寻找一系列λ值的最小目标来进行，直到获得所需的精度我们使用固定的障碍函数，通过这种修改，（3）变为卢恩（四）L（x，y）=cx−yAx+yb−j=1n（x，j）， x > 0.其中，j> 0，j = 1. n. 现在，要求（五）Lxj= 0，j =1，...，nL阿吉岛= 0，i = 1，. ， m在（x，y），这是一个鞍点。当αj的值减小时，（4）的鞍点更接近（3）的鞍点。如果我们开始N. 沃克，M。Wennink/Electronic Notes in Theoretical Computer Science 141（2005）97101线性规划的形式(6)mincxs. t. Ax≥b，x≥ 0代替（2），则拉格朗日量（3）也将被限制为y≥ 0并且障碍函数+ δiln（yj），i = 1，. ，m将被添加到（4）。3分解与分布为了解释鞍点问题是如何分布的，我们引入了一个运行的例子。我们在通信网络中寻找到达给定目的地的最短路径，它可以用标准的方式表示为最小费用的最小线性规划，拉格朗日量的形式为（3）。链路j上的带宽由原始决策变量xj确定，而对偶变量yi变为从节点i到目的地节点的距离（或成本）。在链路j处施加每单位带宽cj的成本，并且将带宽bi注入到节点j中。I.如果i是m−1个入口节点之一，则我们可以选择bi= 1，并且bi= 1−m，在目的地节点i接收所有的下行链路。矩阵A是网络的关联矩阵;如果节点i是链路j的源，则Aij= 1;如果节点i是链路j的目标，则Aij= −1;否则Aij= 0假设网络已连接。解在对偶变量中是退化的，这通常通过要求目的地节点设置yi= 0来处理拉格朗日函数可以写成各个分量之和，其结构可以用图形表示我们在图1中展示了一个5节点（=m）、7链路（=n）的小型网络。原始变量用圆圈圈起来，对偶变量用正方形圈起来。拉格朗日函数的一个分量由一个blob表示，该blob连接到它所依赖的变量通信网络中的每个链路对应于关联矩阵的一例如图1，xa参与两个组成部分-从关联矩阵导出的元素−y1xa和+y2xa，以及成本分量caxa和显式对数屏障分量−kaln（xa），讨论了上面，我们用一个开放的圆圈表示。这种图形表示与信念传播网络中的因子图、解码理论中的Tanner图和约束编程中的约束图[2，3]有关。我们用“分量图”这个名字来强调它是从拉格朗日函数的直接平移而来的。一个很好的特性是，对于这个问题公式化，它自然地反映了底层的网络拓扑。在第5节中，我们将看到同样的情况也适用于从电路导出的分量图我们可以通过划分分量图来分配寻找鞍点的问题图1显示了最短路径问题的这种划分。每个节点N. 沃克，M。Wennink/Electronic Notes in Theoretical Computer Science 141（2005）97102ccxcy2b2y3b3y2−y2xcXC+y3xcy3+y2xa+y x+y3xf2e−y x3dcaxaXaXeXfxdcd−y1xacexecfxf−y4xe−y x+y5xd4Fy−y1xb+y4xb1XBy4Xgy+y4xg−y5xg5黄蓝5 5C xB b黄蓝4 4C xG gXDy1b1Fig. 1.最短路径路由的组件图，显示底层网络结构，以及Bellman-Ford算法的分解。变量用于每个出站链路，一个双变量用于距离标签。对于每个节点，我们可以通过收集涉及该节点所拥有的任何变量的所有分量来获得局部感知的拉格朗日量例如，对于节点L4（xe，xf，y4）=（ce+y2）xe+（cf+y3）xf−y4xe−y4xf（七）+y4（b4+xb+xg）−eln（xe）−fln（xf）其中我们使用符号yi和xj来指示变量由另一个节点拥有因此，从节点4的角度来看，y2被认为是强制性的。一个局部感知的拉格朗日变化时，邻近节点改变其决策变量的值。如果一个节点已经找到了它的局部拉格朗日量的鞍点，那么关于它所拥有的变量的导数（5）为零。由于全局拉格朗日量中的每个决策变量都只属于一个节点，因此当且仅当所有节点同时处于其局部拉格朗日量的鞍点时，网络作为一个整体处于鞍点每个局部鞍点问题在形式上类似于全局鞍点问题，并且分解成子问题通常可以递归地继续。上面的讨论提出了一种直接的分布式方法来寻找网络鞍点：在一个节点收到关于其邻居变量值的新信息后，它解决了它的在最短路径问题的情况下，这个过程收敛到一个解决方案。在我们的示例网络中由节点4执行的操作可以总结如下N. 沃克，M。Wennink/Electronic Notes in Theoretical Computer Science 141（2005）97103• 维护从下游邻居节点2和3接收的距离标签y2和y3的表• 维护从上游邻居节点B和G接收的流值Xb和Xg的表。• 定期执行以下操作· 将其距离标签更新为在每个输出链路上发送所述数据流的成本中的最小值。因此y4= min（y2+ce，y3+cf）。· 在成本最低的输出链路上发送所有的输入流。 如果这如果是链路f，则设置xf=xb+xg且xe= 0，如果是链路e，则设置xe=xb+xg且xf= 0。· 向上游节点1和5发送新的距离标签y4· 分别向下游相邻节点（节点2和3）发送下行值xe和xf其他非目的地节点执行类似的操作。如果我们忽略路由变量的值，并且只记录使用了哪一个输出链路，那么这些操作重新创建了Bellman-Ford算法的分布式异步版本，该算法是距离矢量协议（例如RIP）的核心，广泛用于互联网[8]。上面描述的过程，其中暗示由单个节点（或解决这个问题的一个明显的权宜之计是增量地调整决策变量的值。这条推理路线导致一个动态系统方程，在下一节中描述，其中决策变量收敛到任何可微分严格凹凸拉格朗日的全局鞍点4作为动态系统的在这里，我们假设变量的值连续变化，并且以一定的速率变化，使得交换消息时产生的传播延迟可以忽略不计。我们稍后讨论这些假设。它还假定拉格朗日量至少有一次可微分。下面的动力学方程可以作为寻找鞍点的直观方法，即：关于x的拉格朗日量的最小值和关于y的拉格朗日量的最大值，（八）DXdt= −λ。 贝克斯湖，dydt= + μ。埃默里湖，N. 沃克，M。Wennink/Electronic Notes in Theoretical Computer Science 141（2005）97104.y2其中x∈Rn和y∈Rm是包含决策变量值的向量，λ∈Rn×n和μ∈Rm×m是正定矩阵，通常假定为对角矩阵，并且λxL和λyL分别是L关于原始变量和对偶变量在接下来的时间里第二节给出了一个李雅普诺夫函数，证明了该动力学方程的收敛性，并讨论了一个基于该函数的消息传递算法。假设拉格朗日量是严格凹凸的。它有一个唯一的鞍点（x，y）。我们想知道，当t→ ∞时，（8）的解（x（t），y（t））收敛于（x∞，y∞）。我们可以通过构造一个李雅普诺夫函数来实现。假设拉格朗日函数的鞍点（x，y）在原点（0， 0），并定义（九）φ= 1。xt. λ−1.x+2yt. μ−1Σ其中，x、y以及因此φ是时变量，并且Xt表示x的转置。注意，λ和μ是正定矩阵，因此可以求逆。然后dφ(10)=−xt。 L + yt. Ldtx y如果L（x，y）是一次可微的，则由于它的严格凸性，L（x2，y）−L（x1，y）>（x2−x1）t。[xxL]（x1，y）（十一）L（x，y2）− L（x，y1）<（y2− y1）t. [x，y1]（x，y1）对于所有的x，y和x1 x2，y1/=y2[4]。 设置x1=x，y1=y，x2=x= 0，y 在（11）中=y= 0，并在（10）中代入，得到（十二）dφ

下载后可阅读完整内容，剩余1页未读，立即下载