软约束逻辑编程的单播和组播Qos路由

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

摘要翻译：
提出了一个形式化模型来表示和解决具有服务质量（QoS）要求的网络中的单播/组播路由问题。为了达到这一目的，首先我们将网络转换为一个加权图（单播）或与或图（多播），其中连接器上的权重对应于在相关网络链路上发送分组的多维代价：权重向量的每个分量表示不同的QoS度量值（例如带宽、代价、延迟、分组丢失）。第二步是用软约束逻辑编程(SCLP)把这个图写成一个程序：这个框架的引擎可以通过优化路径/树的代价和解决强加给它们的约束（例如延迟<40msec)来找到最佳路径/树，从而找到QoS路由问题的解决方案。此外，C-半环结构是一种方便的QoS度量建模工具。最后，我们给出了该框架在无标度网络上的一个实现，并提出了如何改进该框架的性能。
---
英文标题：
《Unicast and Multicast Qos Routing with Soft Constraint Logic Programming》
---
作者：
Stefano Bistarelli, Ugo Montanari, Francesca Rossi, Francesco Santini
---
最新提交年份：
2008
---
分类信息：

一级分类：Computer Science        计算机科学
二级分类：Logic in Computer Science        计算机科学中的逻辑
分类描述：Covers all aspects of logic in computer science, including finite model theory, logics of programs, modal logic, and program verification. Programming language semantics should have Programming Languages as the primary subject area. Roughly includes material in ACM Subject Classes D.2.4, F.3.1, F.4.0, F.4.1, and F.4.2; some material in F.4.3 (formal languages) may also be appropriate here, although Computational Complexity is typically the more appropriate subject area.
涵盖计算机科学中逻辑的所有方面，包括有限模型理论，程序逻辑，模态逻辑和程序验证。程序设计语言语义学应该把程序设计语言作为主要的学科领域。大致包括ACM学科类D.2.4、F.3.1、F.4.0、F.4.1和F.4.2中的材料；F.4.3（形式语言）中的一些材料在这里也可能是合适的，尽管计算复杂性通常是更合适的主题领域。
--
一级分类：Computer Science        计算机科学
二级分类：Artificial Intelligence        人工智能
分类描述：Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域，除了视觉、机器人、机器学习、多智能体系统以及计算和语言（自然语言处理），这些领域有独立的学科领域。特别地，包括专家系统，定理证明（尽管这可能与计算机科学中的逻辑重叠），知识表示，规划，和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--
一级分类：Computer Science        计算机科学
二级分类：Networking and Internet Architecture        网络和因特网体系结构
分类描述：Covers all aspects of computer communication networks, including network architecture and design, network protocols, and internetwork standards (like TCP/IP). Also includes topics, such as web caching, that are directly relevant to Internet architecture and performance. Roughly includes all of ACM Subject Class C.2 except C.2.4, which is more likely to have Distributed, Parallel, and Cluster Computing as the primary subject area.
涵盖计算机通信网络的所有方面，包括网络体系结构和设计、网络协议和网络间标准（如TCP/IP）。还包括与Internet体系结构和性能直接相关的主题，如web缓存。大致包括除C.2.4以外的所有ACM主题类C.2，后者更有可能将分布式、并行和集群计算作为主要主题领域。
--

---
英文摘要：
  We present a formal model to represent and solve the unicast/multicast routing problem in networks with Quality of Service (QoS) requirements. To attain this, first we translate the network adapting it to a weighted graph (unicast) or and-or graph (multicast), where the weight on a connector corresponds to the multidimensional cost of sending a packet on the related network link: each component of the weights vector represents a different QoS metric value (e.g. bandwidth, cost, delay, packet loss). The second step consists in writing this graph as a program in Soft Constraint Logic Programming (SCLP): the engine of this framework is then able to find the best paths/trees by optimizing their costs and solving the constraints imposed on them (e.g. delay < 40msec), thus finding a solution to QoS routing problems. Moreover, c-semiring structures are a convenient tool to model QoS metrics. At last, we provide an implementation of the framework over scale-free networks and we suggest how the performance can be improved.
---
PDF下载：
--> English_Paper.pdf (573.41 KB)

2022-4-14 16:06:15 上传

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：QOS 软约束 服务质量 连接器 SCL

SoftConstraint逻辑编程的单播和组播QoS路由Stefano BistarelliUniversit\'a Chieti-Pescara,Istituto di Informatica e TelematicaUGO MontanariUniversit\'a di PisaFRANCESCA RossiUniversit\'a di PisaFRANCESCA RossiUniversita\'a di PisaFRANCESCA a di PisaFRANCESCA di PossiUniversity and francesco SANTINIIMT-Informatica e TelematicaWe-Advanced Studies,Istituto di为了实现这一点，我们将网络适配转换为一个加权图（单播）或与或图（多播），其中aconnector上的权值对应于在r elated网络链路上发送数据包的多维成本：权值向量的每个分量代表一个直接的QoS m度量值（例如带宽、成本、延迟、数据包丢失）。第二步是把这个图写成软约束逻辑编程(SCLP)的程序：这个框架的引擎然后能够通过优化路径/树的代价和解决强加给它们的约束（例如延迟≤40msec)来找到最佳路径/树，从而找到Q oS路由问题的解决方案。此外，C-半环结构是一种方便的QoS度量建模工具。最后，我们给出了该框架在无标度网络上的实现，并提出了如何提高性能的建议。类别和主题描述符:D.3.2[程序设计语言]:语言类别-约束和逻辑c语言；D.3.3[编程语言]:语言结构和特性-约束；C.2.3[计算机通信网络]:网络操作。网络管理；F.4.1[数理逻辑和形式语言]:数理逻辑。逻辑和约束编程通用术语：语言、测量、理论作者地址：Stefano Bistarelli,Dipartimento di Scienze,Universit`a di Chieti-Pescara,VialePindaro 42,Pescara,65127,意大利。bista@sci.unich.it。-信息学和远程信息学研究所，通过G.Moruzzi，意大利比萨，56100。Stefano.bistarelli@iit.cnr.it.Ugo Montanari,Dipartimento di Informatica,U Niversit`a di Pisa,Largo Bruno Pontecorvo 3,Pi sa,56127,意大利。Ugo@di.unipi.itfrancesca Rossi,Dipartimento di Matematica Pura e Applicata,Universit`a di Padova,Via Trieste63 35121 Padova,意大利。Itfrancesco Santini,IMT-Institute for Advanced Studies,Piazza San Ponziano 6,55100 Lucca,意大利。f.santini@imtlucca.it。-信息学和远程信息学研究所，通过G.Moruzzi 1561 00比萨，意大利。francesco.santini@iit.cnr.it.允许免费制作本材料的全部或部分的数字/硬拷贝供个人或课堂使用，前提是这些拷贝不是为了实用或商业利益而制作或分发的，ACM版权/服务器通知、出版物的标题和日期出现，并通知复制是由ACM公司许可的。否则复制、重新发布、在服务器上张贴或重新分发到列表需要事先的特殊许可和/或费用。C 20YY ACM 0000-0000/YY/00-0001$5.00 ACM Journal Name,Vol.V，第N号，20YY，第1-0页？？.2·Stefano Bistarelli et al.1。90年代后半期，Internet工程任务组(IETF)和rese arch社区提出了许多服务模型和机制[Xiao and Ni 1999；Paul and Raghavan2002]，以满足对网络服务质量（QoS）的需求。原因是传统的nal网络无法识别与数据相关的pr资历，因为它们以最佳的原则处理网络tr a？c。根据这种处理方法，网络不提供任何保证，以保证的QoS水平或某一优先级（由于充血）来帮助传输数据或辅助使用r。在最优的ORT网络中，所有用户获得完全相同的待遇。

然而，现在的网络应用，如企业资源计划(ERP)、数据挖掘、远程学习、资源发现、电子商务以及多媒体内容、股票报价和新闻的分发，都需要一定的“及时性”（即。由于所有这些原因，路由协议自然而然地扩展到包括和保证QoS要求[Younis and Fahmy2003；Xiao and Ni 1999；Paul and Raghavan 2002]，c onsequently通常缩写为QoS例程。如[Crawley et al.1998]中，QoS是“网络在传输一个服务流时要满足的一组服务要求”，其中一个服务流是“从源到目的地（单播或多播）的一个包流，具有相关的服务质量（QoS）”。要实现和改进，服务要求必须用一些可测量的QoS指标来表示，如包的宽度、跳数、延迟、抖动、成本和丢失概率。本文结合并扩展了[Bistarelli et al.2002]和[Bistarelli et al.2002]中的两个工作。2007].首先，我们详细描述了描述和求解普通Shor测试路径(SP)的建模过程[Cormen et al.1990]软约束逻辑程序设计的问题（见SEC。2）我们考虑了从经典问题到多准则问题（即。许多优化成本），从偏序问题到那些基于与弧的使用相关联的模态的问题（即。并给出了如何通过SCLP程序来解决这些问题。其基本思想是路径表示网络路由，边缘代价表示QoS度量值，目标是在满足QoS要求的同时优化路由代价，从而保证所发现的单播路由的QoS要求。然后，对单播方案进行了扩展，提出了一个形式化模型来表示和解决需要QoS支持的组播网络（即支持组播传输的网络）中的组播路由问题。对于这里的tta，我们绘制了使它适应于加权与或图[Martelli and Montanari，1978]，其中连接器上的权重对应于在由该连接器建模的网络链路上发送数据包的成本。然后，在aSCLP程序中对超图进行了翻译，并说明了该程序的语义是如何在相应的and-or图中计算besttree的。我们将这一结果应用于从网络中的一个给定节点出发，找出代价最小且到达组播通信所有目的节点的组播分发树。TheACM杂志名称，卷。单播和组播QoS路由的软约束逻辑编程。3个连接器的代价可以用向量（多维代价）来描述，每个分量代表一个给定的QoS度量值。我们还展示了如何在组播问题中添加模块，以及如何降低该框架的计算复杂度。因此，本文提出了一个完整的形式化模型来表示和求解单播/组播QoS路由问题。SCLP程序是一个逻辑表，其中每个基本原子都可以作为一个实例化的软约束[Bistarelli et al.1995；1997b]，它可以与一个集合中的一个元素相关联。从形式上讲，这个集合是一个C-半环[Bistarelli2004]（以下简称为半环），即一个集合加上两个运算+和×，这两个运算基本上说明了如何组合cons traint和如何比较它们。这两个运算的前提允许用一个更一般的代数来代替逻辑程序设计中通常的布尔代数，其中逻辑与和logicalor被两个半环运算所代替。

该框架最大的特点是：SCLP是一个声明性的编程环境，因此可以相对容易地指定从路径到树的大量直接问题，而软约束机制则提供了一个自然的工具来指定和组合问题，而软约束机制则提供了更强的可扩展性和可约束性，因此SCLP框架的最大特点是：SCLP是一个声明性的编程环境，因此它可以相对容易地指定从路径到树的大量直接问题。该模型可以用来简单地指定问题，然后用快速求解器翻译和解决问题；然而，我们的目标是提高我们的实现的性能。这是因为s emiring s tructure是一个非常容易使用的参数化工具，它可以在QoS度量方面给出几个独立的c ost模型；显然，相同的SCLP pro gramming环境和操作语义引擎可以用于所有这些独立的半环。最后，由于QoS路由问题在一般情况下是NP完全的，因此SCLP由于具有解决c ombinatorial问题的能力（如[Georget and Codognet1998]所示）而成为一个很好的工具。1.1相关工作在[de Nicola et al.2003]和[Hirsch and Tuosto2005]中，作者也采用了与半环相结合的超图模型，但两个节点之间的最小径（因此不是在整个树上）是通过graphicalcalculous来计算的。目前，从计算性能的角度来看，所有这些框架都无法比较，因为它们还没有实现。即使[Mammeri2004]中的工作也提出了一些一般的代数算子来处理网络中的QoS，但没有任何实际的结果。我们只将我们的工作与其他理论框架进行比较，因为我们的研究只考虑了一般的路由约束来解决一些问题：由于QoS路由的复杂性，最先进的实用解决方案（第3.2和3.3节中提出的）只处理度量和约束的子集。另一方面，一个更多的基因ral框架可以帮助从全球的角度分析问题，而不是与特定的算法相关联。使用声明式路由[Looet al.2005]，路由协议是通过用adeclarative查询语言编写一个简单查询来实现的（如[Loo et al.2005]中的Datalog），然后在so me或所有节点上以分布式方式执行该查询。它是基于这样的观察，即递归查询语言是表达例程的一种自然的方法。V，No.N，20YY.4·Stefano Bistarelli et al.protocols。然而，[Loo et al.2005]的作者对QoS特性的建模并不深入，我们认为THA-C-Semirings代表了一个很好的方法来实现这些度量。更进一步，除了SCLP fra mework所带来的优雅的形式化之外，我们建立了一个真正实现模型的桥梁（Sec.7.2)，并有几个改进经验性能的ideasto。该工具可用于快速原型化和测试直接路由路径。因此，我们的论文从理论到实际，从纵向上覆盖了这个问题，没有达到现有路由算法在路由器内部实现的性能，但深入而富有表现力地面对这个问题。据我们所知，其他形式的表示完全没有这种实践l实现。1.2论文的结构。本文的其余部分组织如下。在秒内。2我们对SCLPframework进行了分片，而在SEC中。3我们通过引入组播/单播QoS路由来完成背景：我们证明了必须优化且受QoS指标约束的路由规划问题通常是一个NP完全问题。然后，我们重新介绍了一些解决方案，主要是通过启发式，在现实世界中给出的。第4节提出了如何用SCLP对单播QoS路由进行建模和求解，并考虑了多维代价（即。

多准则问题），并基于与网络链路相关联的使用模式：例如，如果我们需要通过仅使用无线、和/或有线和/或经解密的链路（即。第五节概述了一个类似的框架，基于超图和SCLP来管理组播QoS路由：我们展示了如何在相应的与或图中转换网络，然后利用SCLP计算最佳分布树。即使在这种情况下，我们也扩展了模型以包括带有模态的问题。第6节给出了一些关于半环的重要证明，当网络链路的cos ts是多维偏序的时，这是一个常见的情况，因为Qo ss的e----度量必然涉及一个度量的集合。我们还展示了如何用特殊半环来限制偏序so lutions的数目，这些半环通过遵循一组满足用户要求的权重，对cost va lue s元组应用totalorder。第七节通过无标度问题的求解[Barabasi和Albert1999]ne tworks给出了该模型的一个实际实现，它很好地模拟了Internet的拓扑结构。开发此实现是为了证明性能改进是必要的。这些改进可以通过在SEC中解释的机制来实现。8所示，如tablish和branch-and-bound所示（正如我们在ECLiPSe中的实现[Apt和Walla CE2007]所示）。最后，Se C。最后，对全文进行了总结，并对今后的工作进行了展望。SOFT CONST RAINT LOGIC Programming the SCLP framework[Bistarelli 2004；Bistarelli et al.1997a；Georget and Codognet1998]基于[Bistarelli et al.1995；1997b]中引入的c-半环的概念（在本文中，c-半环和半环术语将用作同义词）。半环S是元组hA,+,×,0,1i,其中a是具有两个spe c ial元素(0,1∈a)和两个满足某些性质的操作+和×的集合:+ACM Journal Name,vol.用软约束逻辑编程的单播和组播QoS路由在A的元素集合上（可能是在A的元素集合上）定义，因而是交换的、相联的、幂等的，它是闭的，0是它的单元元素，1是它的abso RbingElements；×是闭的、结合的、交换的，分布在+上，1是它的单元元素，0是它的吸收元素（详尽的理解请参考[Bistarelli et al.1997b])。+ope rition d a partia l阶≤sover a,使得a≤sb i而a+b=b；如果b代表一个比a好的值，我们说a≤sb。与这两个运算有关的其他性质是：+和×在≤s上是单调的，0是它的极小值，1是它的极大值，hA，≤si是一个完备格，+是它的lub。最后，如果×是幂等的，则+分布在×上，hA，≤Si是一个c多态分配格，而×是它的GLB。基于半环的约束满足问题(SCSPs)[Bistarelli 2004]是一个约束问题，其中每个变量实例化都与c-半环a的一个元素相关联（可以解释为代价、偏好程度...），约束通过×操作组合并通过≤sordering进行比较。通过改变这两个C-半环的笛卡尔积是一个C-半环[Bistarelliet al.1997b]，这可以有效地用于多准则约束满足和优化问题的求解。约束逻辑规划(CLP)[Ja-Ar，Maher，1994]通过用约束代替项等式，用约束求解代替统一，从而达到逻辑规划的目的。SCLP框架扩展了经典的CLP形式，以便也能处理SCSP[Bistarelli et al.1995；1997b]问题。

从CLP语言到SCLP语言，我们用SCSP约束来代替经典约束，在这里我们能够标记每个实例化约束（即一个基原子）的优先级。为了做到这一点，我们还修改了解释、模型、模型交等概念，因为我们必须考虑半环操作而不是通常的CLP操作。当我们在半环的元素之间有一个分序（而不是一个tota l）时，我们必须结合se veral反驳路径，这一事实可以在本文的上下文中得到结果，当我们有一个与边/连接符相关的不可Compa代价的图/Hyperg raph proble ms时。事实上，在偏序的情况下，最佳路径/树的解应该由所有代价不被其他路径“支配”的路径/树组成。表一。SCLP程序的一个简单例子。S(X):-p（X,Y）。p（a,b):-q(a).p（a,c):-r(a).q(a):-t(a).t(a):-2.r(a):-3.半环hN,min,+,+∞,0i上的SCLP程序的一个简单例子，其中N是非neg整数的集合，D={a,b,c}。V，No.N，20YY.6·Stefano Bistarelli et al.Ta ble I。这个半环的选择使我们可以表示约束优化问题，其中半环元素是实例化原子的代价。为了更好地理解这一点，我们回顾一下SCLP语法：progr am是一组子句，每个cla用法都由head和body省略。头部只是anatom，而主体要么是原子的集合，要么是半环的va lue，或者是表示它是空的aspecial符号（）。正文为空或只是半环元素的子句被称为事实和反谓词，它们表示约束。当物体是空的时，我们把它解释为具有最好的半环元素（即1）。与原子r(a)(inTa ble I）相关联的半环值如3的直观意义是r(a)花费3个单位。因此，集合N包含所有可能的co，选择min和+这两个操作意味着我们打算使成本之和最小化。这给了我们选择ato m实例化的可能性，它给出了最小的总体成本。对于这个程序，给定一个像s(x)这样的目标，操作语义收集x的s ubs值（在这个cas e中，x=a)和一个半环值（在这个例子中，2),它代表s(x)的所有派生的最小代价。为了了解其中的一个解决方案，它从goal开始，像逻辑编程中通常一样使用子句，除了在每个步骤中积累两个项并与curre nt状态组合：一个替换和一个miring值（两者都由used子句提供）。这两个项目与c urrent目标中的c的组合是通过替换（对于替换部分）和半环（对于半环值部分）的乘法运算来完成的，在本例中，半环是+。因此，在目标s(X)的例子中，我们得到了两个可能的解，都用代换X=邻接两个半环值：2和3。n，这两个解通过最小运算的组合给出了半环值2。为了推广这一表示，我们引入了半环值[Wilson2004]，它是在交换环中取值的约束满足问题，其中的序是传递关系a≤BI→→a+C=b。求和算子的无幂等性导致了一种比吸收性更弱的结构，这种结构在计算解的个数时被证明是有用的。即使在整篇论文中，我们将使用半环估值givenin[Bista relli et al.1995；1997b]（即用幂等+)，半环估值扫描也用于那些需要从di i-herentsolutions中聚合在一起的度量，例如。

利用图中连接p和v的所有可能连接路径的概率，计算了两个节点p和v之间的丢包概率。然而，由于增加约束条件不会导致解的恶化，相关的re-bovelexive和transival关系≤satis具有相对较少的性质，从而形成了一个非单调框架[Wilson2004]3。QOS路由基于常量Raint的路由(CBR)指的是一类路由算法，除了目的地标准之外，还根据一组要求或约束来决定路径选择。这些约束可能是由管理策略（即策略路由）或QoS r e quirements（即QoS路由，如第1节所述）施加的，因此它们可以分为两个c lass。V,No.N,20yy。软约束逻辑编程的单播和组播QoS路由。CBR的目的是减少为实现TRA？C工程目标所需的人工控制和干预[Rosen et al.2001]；为此，CBR通过资源预留感知和需求驱动等特性增强了传统路由的性能，将与管理决策相关的路由称为策略路由（或基于策略的路由），其任务是选择符合管理规则和服务提供者与客户端之间规定的服务水平协议的路径。这样，路由决策不仅基于目的地位置，而且还基于其他因素，如应用程序或协议，分组的大小，通信实体的身份，或者通常是与业务相关的决策。策略约束可以帮助提高网络的全局安全性：c约束可以用来阻止大量用户试图窃取协议中未包含的资源，从而破坏协议的服务供应和安全。QoS路由试图同时满足实时应用所请求的多个QoS需求：这些需求通常用延迟和带宽等度量来表示。相反，策略r路由（或基于策略的路由）用于选择符合强制管理规则的路径。这样，路由决策不仅可以基于目标地址，还可以基于诸如使用的应用程序和协议、数据包的大小或源端系统和目标端系统的标识等因素。策略约束可以提高网络基础设施的全局安全性，并能够实现与业务相关的决策。传统上，QoS指标可以被组织成三个不同的类，这取决于它们如何沿着一条路径组合：它们可以是i）加法，ii）乘法或iii）凹形[Wang and Crowcroft，1996]。它们的定义如下:withn，n，n。..,ni,nj表示网络节点，设m（n,n）是连接n和n的链路的度量值。对于任何路径P=(n,n,...,ni,nj）,其度量为：-加法，如果m(P)=m(n,n)+m(n,n)+...+m(ni,nj）,则一条路径的加法度量是构成该路径的所有链路的度量之和。例如延迟、抖动（网络路径上的延迟变化）、代价和跳数。-乘性的，如果m(P)=m(n，n)×m(n，n)··×m(n，nj)。例如可靠性或损失概率。-凹，如果m(P)=max/min{m(n，n)，m(n，n)，...，m(n，nj)}。一条路径的凹值是该路径中所有链路上的metr ic值的最大值或最小值。经典的例子是带宽，这意味着路径的带宽由具有最小可用带宽的链路决定，即路径的瓶颈。

其他凹的度量可以被重新定义，例如，通过路径上的路由器的包bu或CPU使用率，或者，然而，在“最弱的链路”上需要最大化和挂起的东西。即使通常为路径引入度量类，大多数情况下它们也适用于树：例如，考虑一下，如果我们需要收集一个全球costACM日志名称，Vol。V，no.N，20yy.8·Stefano Bistarelli等通过求和树边的所有权值（即。添加剂），或者如果我们想最大化bo ttreneck链路的带宽（即。给定一个节点产生数据包，我们可以将网络数据传送模式分为三个主要类别：i）单播，当数据从一个发送者传送到一个特定的接收者时，提供一对一的传送；ii）广播，当数据相反地传送到所有主机时，提供一对一的传送；以及iii）多播，当数据传送到所有表示感兴趣的选定主机时；因此，最后一种方法提供了一对多交付。3.1两个NP完全问题当我们使用多个QoS度量时，一个典型的场景涉及独立的资源并允许取实数或无界整数值[Kompella a Ndawduche2001]。例如，可能有必要以成本最小化为目标（即定量约束，优化度量），并同时受制于路径延迟≤40ms ec（即布尔约束，即无论路径是否可行），因此我们将有约束集C=(delay≤40,min（cost））。在这样的情况下，满足两个布尔约束，或一个布尔约束和一个q-uantiative（优化）约束是NP完全的[Younis and Fahmy2003]。如果除一个资源外的所有资源都取有界整数值，或者其他资源是相依的，则可以在非多项式时间内求解proble ms[Chen and Nahrstedt1998]。在这一领域，大多数提出的d算法都采用启发式算法来减少co的复杂性，我们将在SEC中看到这一点。3.2和3.3.单播和多播QoS路由可以归结为两个众所周知的更普遍的问题：Multi-Constrained Path(MCP)[Korkmaz和Krunz2001；Paul和Raghavan2002]和Steiner Tree(ST)[Winter1987；Paul Andraghavan2002]问题。在MCP中，从图中的节点s tonode t中找出一条路径，其中每个链路都与k个非负加性权相关联，同时满足这些权的一组约束C。在图G(N，E)中可能有多条满足约束集的双路径。据说这样的道路是可行的。然而，通常可能需要根据一些准则，并尊重约束所施加的界限d来检索n条最优路径。这一问题被称为多约束最优路径(MCOP)问题。显然，由于pathsmust是根据成本标准优化的，MCOP与ShorttestPath问题相交，MCP问题是一个NP完全问题。[Garey and Johnson1979]的作者很有资格将MCP问题的许多度量m=2列为NP完全的，但他们没有给出一个证明。Wang和Crowcroft在[Wang和Crowcroft 1996]和[Wang 1999]中对m≥2提供了这种证明，其基本内容是将m=2的MCP问题归结为一个Partition proble m的实例，这是一个著名的NP-co mplete问题[Garey和J Ohnson1979]。2001年；奎珀塞特阿尔山。2004年；Younis和Fahmy2003]表明在某些可能的情况下，QoS路由实际上是可处理的。在ST proble m中，给定图G=(V，E)中的一组顶点S，一个解决方案通过一个最小权值的图将它们互连，其中权值是所有边的权值之和。如果S=V，则ST问题归结为MinimumACM Journal Name,Vol.V,No.

N，20yy。软约束逻辑编程的单播和组播QoS路由·9SourceRouterHostReceiverfig。1.源和接收端之间的单播dis分枝的一个示例。有向的arcshighlight路径，而虚线对应于未被图生成树(MST)问题遍历的链接[Cormen et al.1990]。本文将Steiner树转化为约束Steiner树(CST)，以包含约束链路权重的约束；例如，如果我们想要从源s到每个le af s∈s的每个pa thp的度量值之和小于一个选定的极限。ST和CSTA是NP完全问题[Winter1987]，因为se cond可以被简化为firerst问题。可以看出，与组播相关的问题既继承了多个约束度量的约束性，又继承了在同一时刻重启多个端节点的约束性。3.2具有QoS扩展的单播路由。1我们展示了一个在源、产生数据和唯一一个接收者（即通信的目的地）之间的单播通信的例子：粗的定向线突出了包的方向，而虚线则护送到未被穿越的链路。现在我们给出了一些单播QoS路由建议，每个建议都旨在优化可能的QoS度量的一个小子集或使用启发式，因为，如SEC中所述。3.1，该问题一般是NP-完全的。例如，对于带宽受限的路由问题，已经提出了几种解决方案：在[Ma and Steenkiste1997]中提出了一种有趣的方法，它利用资源之间的依赖关系，如可用带宽、延迟和Bu-er空间来简化问题；然后，利用改进的Bellman-Ford算法对该问题进行求解。同时满足带宽和延迟边界的一种方法是对所有不满足带宽要求的链路进行修剪。然后应用Dijkstras最短路径算法来寻找一条可行的路径，如果有的话，满足延迟要求。V,No.N,20YY.10·Stefano Bistarelli et al.ments[Wang and Crowcroft，1996].根据算法优先选择跳数最小的路径（即最宽的最短路径），还是优先选择带宽最大的路径（即最短的最宽路径）[Wa ng and Crowcroft1996],优化ba Ndwidth和延迟c的问题可以作为最宽的最短路径问题或最短的最宽路径问题来解决。正如[Ma和Steenkiste1997；Korkmaz和Krunz2001]所描述的那样，多约束路由的目标是同时满足cons traint的aset。在[Kor kmaz和Krunz2001]中提出了一种求解多约束最优路径问题的启发式方法，该方法对非线性函数（可行性）和主函数（最优性）进行优化。还有带宽和代价有界路由的解决方案，通常将代价或带宽映射到一个有界整数值，然后使用扩展版本的Bellman-Ford或Dijkstra算法解决多项式时间问题[Chen和Nahrstedt，1998]。3.3带QoS扩展的多播路由sMulticast是一种重要的带宽节约技术，它减少了TRA4 Cby同时向多个接收者传递单个信息流（如图2所示）。因此，在节省资源的同时，组播非常适合于代表要求一定传递及时性的应用程序并发分发内容：因此，组播路由也自然地被用于保证QoS要求[Wang and Hou 2000]。在其最重要的实现中，可以使用多个单播传输（即源将负责它们）来提供多播，但在这种解决方案中，相同的数据包可以多次遍历s ame链路，从而增加了网络的tra？c。

因此，网络必须通过创建组播（组）地址和让路由器只在分发树有选择性地分叉时复制数据包来本地提供这种服务。这样，s ource节点只能知道所有目的地的一个全局地址，网络（即路由器）可以最优地“分割”向接收者发送信息，同时也知道如何发送这些信息：源节点不能拥有这些信息。组播地址也称为组播组地址，用户可以使用该地址定位并向组中的所有成员发送数据包。groupmembe r是一个对接收发送到特定Group地址的数据包感兴趣的主机。组成员有时也被称为接受者或倾听者。Amulticast源是向Amulticast组发送具有设置的目的地址的数据包的主机。为了只向感兴趣的各方传送数据，网络中的路由器建立了一个多播（o r分布）树（图2）。包含至少一个感兴趣的侦听器的每个子网络都是树的一片叶子。在树分支的地方，路由器复制数据并向每个分支发送单个数据包。由于数据包在网络中只在路径发散的地方被复制，因此没有一条链路能够携带重复的数据包，从而减少了全局的tra？c.组播问题已经用几种算法和变体进行了研究，如最短路径树(SPT)、MST、ST、CST（见第3节）和其他混合算法[Wang and Ho u 2000]。基于SPT的算法（例如Dijkstra或BellmanFord[Cormen et al.1990])旨在最小化从so urce到每个r e ceiver的链接上的权重之和，如果所有链接花费一个单位，则产生treeACM期刊名称，Vol.采用软约束逻辑编程的单播和组播QoS路由·11SourceRouterHostReceiverfig。2.在网络上构建组播树的一个例子：定向弧突出树（方向是下游），而虚线对应于不被组播穿越的链路。是最短跳的。组播QoS路由通常比单播QoS路由更复杂，因此本文中较少阐述的建议是a[Younis and Fahmy2003；Paul and Ra Ghavan2002]。在RE spe c t到单播的情况下，额外的复杂性源于需要支持shar ed和异构保留风格（针对不同的组成员）以及distr IBUTION CUNOW的全局接纳控制。一些appr算法使用Steiner tr ee公式[Berman et al.1979]或扩展现有算法来优化时延（即MOSP F[Moy1998]是经典OSPF的多播版本），而延迟变化组播算法(DVMA)[Rouskas and Baldine1997]计算时延和抖动都有界的组播树。同时，时延受限和代价优化的组播路由可以被描述为Steiner树：一个例子是QoS-awareMulticast路由协议[Chen et al.2000](QMRP)。在[Younis and Fahmy2003]中提出了其他组播QoS路由算法和相关问题（包括稳定性、鲁棒性和可扩展性）。用SCLP编程查找单播QOS路由本节将介绍如何用SCLP表示和求解单播QOS路由。在开始时，我们将只从成本优化的角度来处理这个问题，即作为一个SP问题，而在la st部分，我们将给出一个如何在路径上添加约束的例子（即解决MCOP问题，见第3.2节）。4.1将SP问题转化为SCLP程序，而在SEC中。4.2 samemodel被扩展用于多准则优化，从而具有costson边向量，而不是单个值。秒。4.3 des cribe的情况下，每个弧也存储有关模式的信息，以用于遍历弧。最后，ACM杂志名称，卷。V,No.N,20YY.12·Stefano Bistarelli et al.Psvutrqfig.3.证券交易委员会的SP问题。