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

1528

收藏 2022-04-14

摘要翻译：
提出了一个形式化模型来表示和解决具有服务质量（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)

马上下载

扫码加我拉你入群

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

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

全部回复

可人4

2022-4-14 16:06:22

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网络中，所有用户获得完全相同的待遇。

扫码加我拉你入群

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

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

可人4

2022-4-14 16:06:29

然而，现在的网络应用，如企业资源计划(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被两个半环运算所代替。

扫码加我拉你入群

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

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

可人4

2022-4-14 16:06:36

该框架最大的特点是：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路由进行建模和求解，并考虑了多维代价（即。

扫码加我拉你入群

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

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

可人4

2022-4-14 16:06:42

多准则问题），并基于与网络链路相关联的使用模式：例如，如果我们需要通过仅使用无线、和/或有线和/或经解密的链路（即。第五节概述了一个类似的框架，基于超图和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]问题。

扫码加我拉你入群

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

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

kedemingshi

2022-4-14 16:06:49

从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中聚合在一起的度量，例如。

扫码加我拉你入群

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

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

点击查看更多内容…

nandehutu2022

2022-4-14 16:06:55

利用图中连接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值的最大值或最小值。经典的例子是带宽，这意味着路径的带宽由具有最小可用带宽的链路决定，即路径的瓶颈。

扫码加我拉你入群

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

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

nandehutu2022

2022-4-14 16:07:02

其他凹的度量可以被重新定义，例如，通过路径上的路由器的包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.

扫码加我拉你入群

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

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

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

大多数88

2022-4-14 16:07:50

C IAO Prolog也有一个fuzzy扩展，但由于它不完全符合[B istarelli et al.1997a]中SCLP的语义（由于在fuzzy集的区间内插），我们决定使用约束(<and≤)之间的CIAO算子，用它们来建模C-半环的×算子。由于这个原因，我们在条款的标题中插入了边缘的成本，直接从SCLP cla的使用中删除，这些使用在条款的正文中有成本。在其他著作中也有类似的研究成果[R\'Egin et al.2000].在Tab中。V表示CIAO prog ram，表示图中的图形。5：这里边（即表V中的所有边事实）的形式是：边（源节点，目的节点，[Link Cost,Lin k Delay])。此外，我们可以看到两个说明路径结构的子句：规则1和规则2分别代表基本（或终止）情况，其中pathis只是一条边，递归cas e需要向路径添加一条边。为了避免递归，从而避免cra shing程序，我们需要通过考虑已经访问的节点列表来处理graphloops，以防止search访问它们两次。此外，我们在ACM期刊名称vol的标题中插入了一个变量。采用软约束逻辑编程的单播和组播QoS路由。19表五。CIAO程序表示图中所有的路径。5,延迟≤8:-module（路径,_,_）.:-use_module（库（列表））.时间([C1,D1],[C2,D2],[C3,D3]):-C3=C1+C2,D3=D1+D2.边（p,q,[2,4])。边（p,r,[3,1])。边（q,s,[3,3])。边（r,q,[7,3])。边（r,t,[1,3])。边（r,u,[3,4])。边（s,p,[1,1])。边（s,r,[2,2])。边（s,v,[2,1])。边（t,s,[3,2])。边（u,p,[3,3])。边（u,t,[2,1])。edge（u,v,[3,4]).path（X,Y,[X,Y],_,[C,D],L）：-edge（X,Y,[XT],v,[C,D],L）：-edge（X,Z,[C1,d1]),nocontainsx（v,Z）,path（Z,Y,T,[ZV],[C2,d2],L）,times([C1,d1],[C2,d2],[C,D]),D=<L.edges1)2)timespath子句要重新成员，在最后，该路径的所有访问节点：此列表将按照正确的顺序存储节点这次访问。最后，子句head的最后一个变量用于只检索总延迟e qual或小于传递值的路径。因此，path子句头的形式是：path（源码，目的地N ode,P ath节点，已经V isis ted节点，[P ath cost,P ath Delay],P ath M ax Delay）。聚合子句模拟了半环的×操作（即+extendedto对，如第4.2节所示），因此它组成了edgestogether的全局代价、带有代价的边缘代价和带有延迟的边缘延迟。所有延迟≤8的路径和相对的查询路径（P,V,P,[P]，[C，D]，8)如图所示。10.路径的p源节点，必须从一开始就包含在被访问节点的lis中。图10将po nds与CIAO prog ram在TAB中的输出进行了比较。对于所找到的三条路径中的每一条，它都显示了可变的P和C-D对，前者存储路径中节点的序列，后者对应于路径的总代价，即hcost delay.我们注意到fr函数的表达性，因为布尔函数可以很容易地添加到查询中，而不是直接硬编码在Program中。例如，对于类似path（p,v,p,[p],[C,D])的查询，D<8返回延迟值小于8.5的所有路径。扩展模型以处理组播QOS路由现在我们扩展了SEC中给出的fra mework。4以便还管理multicastdelivery架构。第一步是使用超图而不是简单的图来表示的，因为我们需要一种方法来在同一时间将一个节点连接到多个目的地（即当同一数据包必须在双链路上路由时）。V,没有。

扫码加我拉你入群

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

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

mingdashike22

2022-4-14 16:07:58

N，20yy.20·Stefano Bistarelli et al.ciao-prolog 1.10#5:2004年8月6日星期五19:01:54？-路径（p,v,p,[p],[C,D],8).C=2+(3+2),D=4+(3+1),p=[p,q,s,v]？.C=3+(7+(3+2)),D=1+(3+(3+1)),P=[P,r,q,s,V]？.C=3+(1+(3+2)),D=1+(3+(2+1)),P=[P,r,t,s,V]？.不？无花果。7.Tab中程序的CIAO输出。第5.1节给出了从网络到与图的一个简单的转换过程，并说明了如何从超弧和相关半环中找出代价。5.2给出了SCLP方案，实现了multicastQoS路由的实现和解决。在秒内。5.3我们将模态与超弧联系起来，就像我们在SEC中所做的那样。4.3对于从网络到超图的路径5.1本节我们将解释一种方法，将具有QoS请求的多个网络的表示（图9a)转换为corr e sponding加权and-orgraph[Martelli a nd Montanari，1978]（图9b)。他的过程可以分为三个不同的步骤，分别侧重于用QoS度量表示i）网络节点，ii)网络链路和iii）链路成本。与或图[Martelli和Montanari，1978]本质上被定义为超图。也就是说，不是连接节点s对的弧，而是连接n个节点元组(n=1,2,3,..）的超弧。超弧称为connect或sand，它们必须被认为是从它们的figurrst节点定向到所有其他节点的。Formallyan与或图是一对G=(N,C）,w这里N是一组结点，C是一组连接器sc N×k[i=0ni。注意，这一规定允许0-连接器，即只有一个输入节点而没有输出节点的连接器。0-连接器表示为以平方e结束的线（图9b)。在下面的解释中，我们还将使用and树的概念[Martelli和Montanari1978]:给定一个与或图G，如果有一个函数G映射G的Hinto节点，使得：-H的根映射在nr中，-if（ni,ni,）。..,nik）是H的连接器，那么(g(ni)，g(ni)，...,g(nik)）是g的一个连接器。换句话说，一个与或图的解树类似于一个普通图的路径：它可以通过为每个节点精确地选择一个输出连接器来获得。每个网络节点可以很容易地在相应的与或图中转换为一个单一的图节点：因此，图中的每个节点可以表示一个interconACM日志名称，Vol。采用软约束逻辑编程的单播和组播QoS路由·21nnnnnikjza)b)nznjnkabcdnifig。8.a）九个节点的F星和b）用连接件表示的F星。路由器），或者充当多播通信源（在网络中注入分组）的节点，或者，确切地说，属于非多播组并参与通信的接收器。在秒内。5.2在寻找最优树解时，将最优树的根映射到表示组播通信源的节点上；以同样的方式，接收器将由产生的and树的叶子建模。在转换接收机时，我们增加了一个输出的0-连接器来模拟通信的端点，其成本很低。假设{n,n,...,n}。9a是网络节点的IDENTI，为了对链路建模，我们检查网络中每个节点的前向星（即从a no de输出的弧集）：我们认为链路是定向的，因为从节点nito njj发送数据包的代价可以从发送fr om njto ni的代价中得到（一个非定向链路可以很容易地被两个定向链路所取代）。假设节点ni的f星包括弧(ni，nj)、(ni，nk)和(ni，nz)，我们通过构造从nito指向目标节点{j，k，z}的每个子集的一个连接器来翻译该f星（图）。

扫码加我拉你入群

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

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

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

扫码加我 拉你入群

扫码加我 拉你入群

扫码加我 拉你入群

扫码加我 拉你入群

扫码加我 拉你入群

扫码加我 拉你入群

扫码加我 拉你入群

扫码加我 拉你入群

扫码加我 拉你入群

扫码加我 拉你入群

扫码加我 拉你入群

扫码加我 拉你入群

扫码加我 拉你入群

扫码加我 拉你入群

扫码加我 拉你入群

扫码加我 拉你入群

扫码加我 拉你入群

扫码加我 拉你入群

扫码加我 拉你入群

扫码加我 拉你入群

扫码加我 拉你入群

扫码加我 拉你入群

扫码加我 拉你入群

扫码加我 拉你入群

扫码加我 拉你入群

扫码加我 拉你入群

扫码加我 拉你入群

扫码加我 拉你入群

扫码加我 拉你入群

扫码加我 拉你入群

分享

扫码加好友，拉您进群

扫码加我拉你入群

扫码加我拉你入群

扫码加我拉你入群

扫码加我拉你入群

扫码加我拉你入群

扫码加我拉你入群

扫码加我拉你入群

扫码加我拉你入群

扫码加我拉你入群

扫码加我拉你入群

扫码加我拉你入群

扫码加我拉你入群

扫码加我拉你入群

扫码加我拉你入群

扫码加我拉你入群

扫码加我拉你入群

扫码加我拉你入群

扫码加我拉你入群

扫码加我拉你入群

扫码加我拉你入群

扫码加我拉你入群

扫码加我拉你入群

扫码加我拉你入群

扫码加我拉你入群

扫码加我拉你入群

扫码加我拉你入群

扫码加我拉你入群

扫码加我拉你入群

扫码加我拉你入群

扫码加我拉你入群