理论计算机科学电子笔记190（2007）111-127www.elsevier.com/locate/entcs基于与或图最佳树搜索和软约束逻辑编程的多播QoS路由建模Stefano Bistarelli1，2，3G大学科学系乌戈·蒙塔纳里4意大利比萨比萨大学计算机科学系Francesca Rossi弗朗西斯·罗西2，5意大利帕多瓦帕多瓦大学纯数学与应用数学系Francesco Santini弗朗西斯科·桑蒂尼1，2，6IMT卢卡-高级研究学院，卢卡，意大利摘要我们提出了一个形式化的模型来表示和解决多播网络中的多播路由问题。为了实现这一点，我们对网络进行建模，使其适应加权与或图，其中连接器上的权重对应于在该连接器建模的网络链路上发送数据包的成本。然后我们使用软约束逻辑编程（SCLP）框架作为方便的声明性编程环境，在其中指定相关问题。特别地，我们展示了SCLP程序的语义如何计算相应的与或图中的最佳树：可以采用该结果来从给定源节点找到具有最小成本并且到达多播通信的所有目的地节点的多播分发树。连接器上的成本也可以被描述为矢量（多个矢量）。维度成本），每个组成部分表示不同的服务质量度量值。因此，最佳树的构造可能涉及一组标准，所有这些标准都将被优化（多标准问题），例如，在单个链路上可以经历的最大全局带宽和最小延迟关键词：与或图，多播，服务质量，路由，软约束逻辑编程。1571-0661 © 2007 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2007.07.008112S. 比斯塔雷利等人理论计算机科学电子笔记190（2007）1111动机和主要思想多播是一种重要的带宽节约技术，它通过同时向多个接收者传送单个信息流来减少传输。因此，在节省资源的同时，多播非常适合代表要求一定的交付及时性的应用程序并发地分发内容：因此，多播路由已经自然地扩展到保证服务质量（QoS）要求[22]。在本文中，我们提出了一个形式化的模型来表示和解决多播网络中的QoS多播路由问题。对于表示，我们使用与或图[15]来对网络和SCLP程序[2，4，12]进行建模，以根据QoS标准计算最佳树给定一组接收节点和一组优化目标函数，多播路由问题是建立优化这些函数的多播树的过程，通常表达最小化 树如果我们正在处理QoS要求，则还给出一组约束：约束的形式为例如端到端延迟界限、抖动界限、路径的最小带宽或其他QoS度量。所得到的组播树必须提供从源到所有目的地的可达性，并满足QoS约束。首先，我们将描述如何在相应的与或图中表示网络配置，将网络节点映射到与或图节点和链路to graph图形connectors连接器. QoS链路成本将转换为连接器的成本。一般来说，与或图被用于对问题解决过程进行建模，并且与最小成本解决方案图一起在人工智能中被广泛研究[19]。之后，我们将提出软约束逻辑编程（SCLP）框架[2，4，12]作为一个方便的声明式编程环境，在其中指定和解决这样的问题。SCLP程序是使用逻辑编程的常规约束逻辑编程（CLP）[14]程序的扩展与软约束相结合，也就是说，可以满足的约束一定程度上。特别是，我们将展示如何表示一个与或图作为一个SCLP程序，以及如何在相应的加权与或图的语义计算最好的树。 因此，找到的最好的树以这种方式，可以用于形成优化的多播树，以确保相应网络上的QoS要求。由于多个QoS参数同时表示链路的成本，因此该问题可以作为多标准问题来解决[6]，其中成本的组合通过比通常的以下和更一般的算子来完成：1由意大利2由MIUR PRIN 2005-0154913电子邮件：bista@sci.unich.it4电子邮件：ugo@di.unipi.it5电子邮件地址：frossi@math.unipd.it6电子邮件：f. imtlucca.itS. 比斯塔雷利等人理论计算机科学电子笔记190（2007）111113××链接权重。这个扩展可以很容易地在SCLP编程框架中转换，因为它基于具有两个操作（和+）的半环的一般结构。然后，用于合并成本，而由+运算定义的偏序（见第4节）用于比较成本。本文的工作推广了文[5]和[6]中关于最短路问题的一些结果。在这两部著作中，主要思想涉及在SCLP中使用非线性子句，即在其主体中具有多于一个原子的子句。在本文中，我们使用更接近逻辑编程的instead子句， 我们用树来代替路径。处理QoS的相关形式化方法，例如[18]和[13]，也采用了与半环结合的超图模型，但是两个节点之间的最小路径（因此，不是在整个树上）经由图形演算而不是SCLP来计算。本文的组织如下：在第二节。2，我们提出了一些一般的背景信息，组播路由，包括它的QoS扩展，然后在第二节。3我们描述了在与或图中寻找最佳加权树的问题。第4节介绍了SCLP框架，而Sec.5描述了如何用与或图表示网络环境。 最后，在SEC。6我们描述的方式将与或图的语义传递给SCLP程序，表明SCLP程序能够计算相应与或图中的最佳树。此树表示解决方案：优化QoS要求的多播树。第7节得出了最后的结论，并概述了未来工作的意图2具有QoS扩展的给定生成分组的节点，我们可以将网络数据传递模式分为三种主要类型：i）单播，当数据从一个发送者传递到一个特定接收者时，提供一对一的传递，ii）广播，当数据被传递到所有主机时，提供一对所有的传递，以及最后，iii）多播，当数据被传递到所有表示感兴趣的选定主机时;因此，这最后一种方法提供一对多传递。在本文中，我们集中在第三种模式，因为我们的目的是提供一个解决方案，从一个源传输数据包的问题K接收器在其最简单的实现中，可以使用多个单播传输来提供多播，但是使用该解决方案，相同的分组可以多次遍历相同的链路。因此，网络必须在本地提供此服务。多播地址也称为“多播组地址”，路由器可以使用该地址定位并向组中的所有成员发送数据包。 组成员是表示有兴趣接收发送到特定组地址的数据包的主机。组成员有时也被称为接收者或监听者。多播源是将目的地址设置为多播组的数据包发送给多播组的主机。为了只将数据传递给相关方，网络中的路由器构建了一个多播（或分发）树（图1）。 每个包含至少一个感兴趣的侦听器的子网是树的叶子树的分支，路由器114S. 比斯塔雷利等人理论计算机科学电子笔记190（2007）111源路由器主机接收器复制数据并向每个分支发送单个数据包。 没有一个环节数据包的复制流，因为数据包仅在路径分叉处在网络中复制，从而减少了全局传输。Fig. 1.一个建立在网络上的多播分发树的例子：有向弧突出显示树（方向是下游），而虚线对应于没有被多播遍历的链接利用多播路由的应用包括例如视频会议、公司通信、远程学习、分布式仿真、资源发现、软件分发、股票报价、新闻以及娱乐应用，例如视频点播、游戏、交互式聊天和因特网点播。由于许多需要多播分发的应用程序也需要一定的交付时效性（实时应用程序），因此多播路由已明确扩展到包括并保证QoS要求;[24]中给出了QoS的全局图。在这种情况下，基于约束的多播路由，问题是找到最佳的分布树相对于某些性能相关的约束，以更好地利用网络资源，并支持应用的QoS要求。基于约束的路由（CBR）表示一类路由算法，除了目的地之外，还将路径选择决策基于一组要求或约束：约束可以由管理策略或QoS需求施加[25]。CBR的另一个目的是提高网络的利用率（CBR是Tra Boc Engineering的工具[24，25]），并且是提供Internet QoS的全球框架的一部分 [24]。多播问题已经用几种算法和变体进行了研究，例如最短路径树（SPT），最小生成树（MST），Steiner树（ST），约束Steiner树（CST）和其他杂项树[22]。基于SPT的算法（例如Dijkstra或Bellman-Ford [11]）旨在最小化S. 比斯塔雷利等人理论计算机科学电子笔记190（2007）111115从源到每个接收器的链路上的权重，并且如果所有链路都花费一个单位，则所得到的树是最少跳的树。MST（例如Prim算法[11]）跨越多播组中的所有接收器，同时最小化树的总权重;在每一步中，树都用一条边进行扩充，该边对树的总成本贡献最小，因此该算法是贪婪的。ST [23]是一棵树，它跨越图中给定的顶点子集，其边缘上的如果子集匹配整个组播组，ST问题归结为MST问题。ST已扩展到CST，包括侧约束QoS指标。ST和CST是NP完全问题[23]，并且已经提出了许多算法来有效地处理它们[22，23]。组播路由的最流行的解决方案涉及树构造。基于树的高效多播路由有两个原因：i）数据可以沿着树的分支并行传输到各个目的地，以及ii）传输数据的最小数量的副本多播QoS路由通常比单播QoS路由更复杂，因此在该领域中阐述的建议较少[25]。 相对对于单播，额外的复杂性源于支持共享和异构预留类型（针对不同的组成员）以及分发单播的全局接入控制的需要。一些方法使用Steiner树公式[1]或扩展现有算法来优化延迟（MOSPF [17]是 经典OSPF的多播版本），而延迟变化多播算法（DVMA）[21]计算具有有界延迟和有界抖动的多播树。此外，延迟受限和成本优化的多播路由可以被公式化为Steiner树：一个示例方法是QoS感知多播路由协议[10]（QMRP）。其他多播QoS路由算法和相关问题（需要稳定性，鲁棒性和可扩展性）在[25]中给出，由于篇幅有限，我们没有在这里包括它们我们的解决方案，在第5节和第6节中描述，而是一个正式的模型，基于网络到相应的与或图的转换，以及通过SCLP子句对图的描述，可以解决图上的组播树。解决方案表示的树的成本，在QoS度量值。3与或图与最佳解树与或图[15]本质上被定义为超图。 在每个节点上，我们可以有几个选择（in或），每个选择都可以由多个同时的选择（in和）组成。代替连接节点对的弧，存在连接节点的n元组（n= 1，2，3，.. . ）.超弧被称为连接器，它们必须被认为是从它们的第一个节点指向所有其他节点。 形式上，一个与或图是一个对G=（N，C），其中N是一组节点 C是一组连接器KCN ×N i.i=0时116S. 比斯塔雷利等人理论计算机科学电子笔记190（2007）111≥0每个k-连接器（n i0，n i1，.， n ik）是有序（k +1）元组，其中n i0是输入节点和n i1，...， N ik是k个输出节点。我们说ni0是的n i1，.， n ik，这些节点是n i的后继节点。请注意，当C2我们有一个通常的图，它的弧是1-连通线。请注意，0-连接器，即，连接器有一个输入，没有输出节点。在图2中，我们给出了一个与或图的例子，其节点是n0，...，n8. 0-连接线表示为以正方形结束的线，而k-连接线（k0）表示为连接在一起的k条有向线。例如，（n0，n1）和（n0，n5，n4）分别是1-连接器和2-连接器，输入节点为n0。 表示连接符的元组中的输出节点（当多于一个时）的顺序由表示与或图中的连接符的箭头的方向决定：即，考虑图2中的连接符（n0，n5，n4），箭头从n5到n4，因此在元组中n5在n4之前与-树是与-或图的一种特殊情况，其中每个节点在连接器集合C中恰好出现两次，一次作为某个连接器的输入节点，一次作为另一个连接器的输出节点。唯一的例外是一个称为root的节点，它只出现一次，作为某个连接器的输入节点。与树的叶子节点是0-连接线的输入节点.图3给出了一个根为NJ2的与树的例子.这里nj7，nj8和NJ8J是叶子.n1f1，3=7n3n83图二.加权与或图问题。给定一个与或图G，与树H是G的一个解树，其起始结点为nr，如果存在函数g，将H的节点映射到G的节点，使得：• H的根映射在nr中。• 如果（n i0，n i1，...，n ik）是H的连通子，则（g（n i0），g（n i1），.，g（nik））是一个常数，Fn0的0,1=3个F0，5，4=2f1，2=3n2ff2，3=12,5,4 =3个n 4f4，5=2f4，8=2f3，6，5=1n5f5，6=3f5，7，8=2n6f6，7，8=3n74S. 比斯塔雷利等人理论计算机科学电子笔记190（2007）111117n'2n'4n'8'n'83图三. 图2中的图的最小成本解和-树，起始节点为nr=n2。nector ofG.非正式地，与或图的解树类似于普通图的路径。它可以通过为每个节点选择一个输出连接器来获得。例如，图3中的与-树是图3中的图的解树。2且起始结点为nr=n2，如果我们令g（nj2）=n2，g（nj4）=n4，g（nj5）=n5，g（nj7）=n7，g（nj8）=n8，g（NJ8J）=n8.注意，树的不同节点可以映射到图的相同节点图2中的与或图在与每个k-连接器相关联的实数（成本函数）上具有k-adic函数，因此被定义为函数加权与或图。特别地，常数与每个0-连接器相关联。很容易看出，如果函数加权图是与树H，则可以给它一个成本，只需评估与其连接器相关联的函数递归地，对于H的每个具有根节点ni0的子树，成本ci0如下给出• 如果ni0是一个叶子，那么它的成本就是相关的常数。• 如果n i0是连接器（n i0，n i1，.，n ik），则其成本为c i0=fr（c i1，...，其中，fr是与连接器相关联的函数成本，并且ci1，...，c ik是以节点n i1，...，我也是。一般的优化问题可以表述如下：给定一个函数加权与或图，找到一个起始节点为n r的最小成本解树。 用于为k-连接器（n i0，n i1，...，...）的输入节点n i0赋值的函数。n ik）的形式为fr（c i1，...，c ik）= a r+c i1+. 其中r是与连接器相关联的常数，并且c i1，.，c ik是以节点n i1，...，我也是。因此，图3中的树的成本（具有根节点NJ2）是17。在接下来的章节中，我们将展示这个成本函数是一个基于c-半环的概念[2，3].3n'522n'743118S. 比斯塔雷利等人理论计算机科学电子笔记190（2007）111××∈××≤⟨ ×⟩--⟨ ∞ ⟩4软约束逻辑程序设计SCLP框架[2，4，12]是基于在[3，8]中引入的c-半环的概念。一个c-半环S是一个元组A，+，，0， 1，其中A是一个具有两个特殊元素（0， 1A）和两个运算+和满足某些性质的集合：+被定义在A的元素集合上（可能是无限的），因此是交换的，结合的，幂等的，它是封闭的，0是它的单位元素，1是它的吸收元素;是封闭的，结合的，交换的，分布在+上，1是它的单位元素，0是它的吸收元素（详尽的定义，请参见[8]）。+运算定义了A上的偏序≤S，使得a≤Sb i ≠a +b=b;我们说a≤Sb，如果b表示一个比a好的值。与这两个运算相关的其他性质是+和×在≤S上是单调的，0是它的最小值，1是它的最大值，<$A，≤S <$A是一个完备格，+是它的lub。最后，如果×是幂等元，则+分布在×上，<$A， ≤S <$A是完全分配格，且×是它的glb。基于半环的约束满足问题（SCSP）是一种约束问题，其中每个变量实例都与C-半环A的一个元素相关联（可以解释为成本、偏好水平、. . . ），并且约束通过运算被组合并且通过S排序被比较。改变集合A和+和运算的含义，我们可以表示许多不同类型的问题，具有模糊性，概率和优化等特征。此外，在[8]中我们证明了两个c-半环的卡巴拉积是另一个c-半环，这可以有效地用来描述多准则约束满足和优化问题。约束逻辑编程[14]通过用约束替换项等式和用约束求解替换统一来扩展逻辑编程。SCLP框架扩展了经典的CLP形式主义，以便能够处理SCSP [3，8]问题。在从CLP到SCLP语言的传递中，我们用更一般的SCSP约束替换了经典约束，在SCSP约束中，我们能够为每个实例化约束（即基础原子）分配一个优先级。 为了做到这一点，我们还修改了解释，模型，模型交集等概念，因为我们必须考虑半环运算，而不是通常的CLP运算。事实上，我们必须结合几个反驳路径时，我们有一个半环的元素之间的偏序（而不是一个总的），可以卓有成效地使用在本文的上下文中，当我们有一个与或图的问题与不可比较的成本相关联的连接器。事实上，在偏序的情况下，寻找最佳树的问题的解决方案应该包括所有那些成本不被在半环N，min，+，+，0上的SCLP程序的一个简单例子，其中N是非负整数的集合，D=a，b，c，在表1中表示。这个半环的选择允许我们表示约束优化问题，其中半环元素是实例化原子的成本到S. 比斯塔雷利等人理论计算机科学电子笔记190（2007）111119表1一个简单的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。为了更好地理解这个表，我们简要回顾一下SCLP语法：一个程序是一个集合每一个分句都由一个头和一个身组成。头只是一个原子，而体或者是原子的集合，或者是半环的值，或者是一个特殊的符号（Q）来表示它是空的。 子句，其中主体为空或它只是一个半环元素，被称为事实，并定义了表示约束的谓词。当body为空时，我们将其解释为具有最佳半环元素（即1）。与原子r（a）（在表1中）相关联的半环值（如3）的直观含义是r（a）花费3个单位。因此，集合N包含所有可能的成本，选择min和+这两个操作意味着我们要使成本之和最小化。这使我们有可能选择总体成本最低的原子实例化。给定这个程序的目标s（x），操作语义收集x的替代（在本例中，x=a）和半环值（在本例中，2），它表示s（x）的所有推导的成本中的最小成本为了找到其中一个解决方案，它从目标开始，并像逻辑编程中一样使用子句，除了在每一步积累两个项目并与当前状态组合：替换和半环值（两者都由used子句提供 这两项与当前目标中包含的内容的组合是通过通常的替换组合（对于替换部分）和半环的乘法运算（对于半环值部分）完成的，在这个例子中是+。因此，在目标s（X）的例子中，我们得到了两个可能的解，都有替换X=a，但有两个不同的半环值：2和3。然后，这两个解通过min运算的组合给出了半环值2。5用与或图表示QoS组播网络在本节中，我们解释了一种方法，将具有QoS要求的多播网络的表示（图5a）转换为相应的加权与或图模型（图5b）。该过程可以分为三个不同的步骤，分别集中于i）网络节点，ii）网络链路和iii）根据QoS度量的链路成本的表示网络节点中的每一个可以容易地在对应的与或图中被转换为单个图节点：因此，图中的每一个节点可以表示互连的网络节点。120S. 比斯塔雷利等人理论计算机科学电子笔记190（2007）111nkC一BD--−--⟨⟩n设备（例如路由器），或者充当多播通信源（在网络中注入分组）的节点，或者，最终，属于多播组并参与通信的接收器。 节中 6、当我们寻找最佳树的解决方案时，最佳与-树的根将被映射到代表组播通信源的节点;以同样的方式，接收者将由结果与-树的叶子建模。当我们转换一个接收器时，我们添加一个输出0-连接器（图5b），其含义（成本）将在下面解释。假设n0，n1，.，图5a中的n 9是网络节点的标识符。为了对链路进行建模，我们检查了网络中每个节点的前向星（f-star）（即，从节点输出的弧的集合）：我们认为链路是定向的，因为从节点n1到nj发送分组的成本可以不同于从nj到n1发送分组的成本（一个非定向链路可以容易地被两个定向链路替换假设节点ni的f星包括弧（ni，nj），（ni，nk）和（ni，nz），我们通过构造一个从ni指向目的节点j，k，z的每个子集的连接器来转换这个f星（图4），总共有2n 1个子集，不包括空集。 因此，以ni作为输入节点的所有所得连接器是（ni，nj）、（ni，nk）、（ni，nz）、（ni，nk，nj）、（ni，nk，nz）、（ni，nj，nz）和（ni，nj，nk，nz）。如第3节所述，在节点的元组排序中，输入节点位于第一个位置，输出节点（当多于一个时）遵循图4中相关箭头的方向。为了简化图4b，直接链接两个节点的弧表示1-连接器（ni，nj）、（ni，nk）和（ni，nz），而弯曲定向线表示n-连接器（其中n>1），其中它们的输出节点的集合对应于遍历弧的输出节点。关于ni，在图4中，我们有一条曲线，用a标记，对应于（ni，nk，nj，nz），b对应于（ni，nk，nj），c对应于（ni，nj，nz），最后，d对应于（ni，nk，nz）。为了使图更清晰，图5a中的网络链路是ni nzzninjnjnka)b）、见图4。 a）N1个网络节点的F星和b）其用连接器的表示。在我们这里提出的例子中，我们感兴趣的QoS链路状态信息只涉及带宽和延迟。因此，网络的每条链路都可以用二维成本来标记，例如，对7， 3告诉我们，该特定链路上的最大带宽为70 Mbps，最大延迟为S. 比斯塔雷利等人理论计算机科学电子笔记190（2007）111121◦≥◦◦DB{∞} ∞ D {∞} ∞BB30毫秒一般来说，我们可以用n维向量表示成本，其中n是计算最佳分布树时要考虑的度量的数量。由于我们希望即使在与或图中也能维护此链接状态信息，因此我们用相同的值元组标记相应的连接器（图5）。在连接器表示多于一个网络链路的情况下（即，n为2的n-连接器），其成本通过用合成操作组装这些链路的成本来确定，该合成操作将与连接器表示的链路的数量一样多的n自然，我们可以针对用于表示QoS的特定类型的成本来实例化该操作：对于本节中给出的示例，的结果是最小带宽和最高延迟，因此，最差QoS度量值：◦（b1，d 1，b2，d2，.，b n，d n b n），max（d1，d2，.， d n）图5b中的连接器（n1，n3，n4）的成本将是10.7，3万美元，因为连接器（n1，n3）和（n1，n4）的成本分别是10.7，2万美元和10.10，3万美元：◦（107， 2， 1010， 3）= 107， 3为了简化图5b，我们只插入了1-连接器的成本，对于其他连接器，可以通过操作轻松计算，并在表2中报告。到目前为止，我们能够将具有QoS要求的整个网络转换为相应的与或加权图，但我们仍然需要一些代数框架来建模我们对最佳树中使用的链路的偏好。为此目的，我们使用半环结构（Sec. 4）.在[16]中给出了对最短距离问题的半环框架方法例如，如果我们对最大化分布树的带宽感兴趣，我们可以使用c-半环SBandwidth=0，+，max， min，0，+（否则，我们可能对最小化全局带宽感兴趣，0、+、最大值、最小值、+、0。 如果我们需要最小化可以经历的最大延迟，我们可以使用SDelay=0，+， min， max，+，在一个单一的链接。 有了这个结果和最终树的深度，我们可以计算出端到端延迟的上限可以通过收集关于网络配置、当前传输状态和关于链路的技术信息的信息来获得（即，带宽值的集合）和（即，延迟值的集合）的元素由于c-半环的合成仍然是c-半环[8]，S网络= B其中+J和×J对应于两个c-半环中+和×运算的向量化：给定b1，b2∈ B <${0，+∞}和d1，d2∈ D <${0，+∞}，b1，d1122S. 比斯塔雷利等人理论计算机科学电子笔记190（2007）111n1<10，1><7.2><3，6>n3n2<3，5> 10，3>n4<1，5>n62，9> 5，3><4，2>n5<8.1>子网络<7.1>n98×⟨⟩7b1，d1显然，找到最佳分发树的问题是多标准的，因为带宽和延迟都必须优化。我们认为这些标准是相互独立的，否则可以将它们改为单一标准。因此，连接符的多维成本不是全序集的元素，并且可以获得几棵树，所有这些树都不受其他树的支配，但是它们具有不同的不可比较的成本。对于每个接收节点，其输出0-连接器的成本将总是包含在到达它的每个树中。如果我们将接收者视为普通节点，则我们可以将成本设置为所采用的c-半环的1个元素（1是 ），由于 到达该节点的成本已经完全由其他连接器描述 在这个节点结束的树枝：实际上，我们关联最高的可能性， 将QoS值分配给此0连接器，在本例中为有限带宽和零延迟。否则，我们可以将接收器想象为更复杂的子网络（作为节点在图5中的n9），因此我们可以将0-连接器的成本设置为最终到达该子网中的节点所需的成本（如图5b中的节点n9之后的0-连接器的成本2，3），以防我们不想或不能显示子网的拓扑，例如出于安全原因。图5示出了图1的网络到对应的与或图的变换。对通信不感兴趣的组成员不被表示，因为分发树不必到达他们。在图5a中，一个接收器（节点n9）已经被替换为子网络，相对于图5b，1.一、不不nn9<2，3>nn8<，0>a)b）、图五、 一个网络例子和相应的与或图表示。<10，1>n1<7.2><3，6>n3n2<3.5><10，3><1，5>6<2，9>n<4，2>4<5，3><，0>n 5<7.1><8.1>n8n7<，0>88S. 比斯塔雷利等人理论计算机科学电子笔记190（2007）111123≤×−⟨⟩6使用SCLP的与或在这一节中，我们用下面的公式来表示一个与或图，就像第5节中的那样，SCLP中的程序。这一决定源于该编程框架的两个重要特征：第一个是SCLP是一个声明式编程环境，因此相对容易指定许多不同的问题;第二个是c-半环结构是一个非常参数化的工具，可以表示几个不同的成本模型，相对于QoS度量。使用这个框架，我们可以很容易地解决多准则的例子有关的多播QoS网络图。5b.正如在[5]和[6]中已经提出的，为了表示SCLP中的连接器，我们可以写子句likec（ni，[nj，nk]）：10，3，说明该图具有从n0到节点nj和nk的连接器，带宽成本为100 Mbps，延迟为30毫秒。其他SCLP子句可以正确地描述我们希望在图上搜索的树的结构。我们选择用CIAO Prolog[9]中的程序来表示与或图，CIAO Prolog [9]是一个支持ISO-Prolog的完整Prolog系统，但同时其模块化设计允许限制和扩展基本语言。因此，它允许与Prolog的子集一起工作，并与实现函数的编程扩展一起工作，高阶（具有谓词抽象），约束，对象，并发，并行和分布式计算，套接字，接口到其他编程语言（C，Java，Tcl/Tk）和关系数据库等等。CIAO Prolog也有一个模糊扩展，但由于它不完全符合[4]中定义的SCLP的语义（由于模糊集的区间内插），我们决定在约束之间使用CIAO运算符（如和<），并用它们来模拟c-半环的算子。出于这个原因，我们将连接器的成本插入到条款的头部，这与SCLP条款的成本在条款的主体中作为一个例子，从图5b中的加权与或图问题，我们可以构建表2的相应CIAO程序，如下所示。首先，我们用以下事实描述图的连接器：connector （ source node ， [list of destination nodes] ， [link bandwidth ， linkdelay]）例如，事实连接符（n1，[n2，n3，n4]，[3， 6]）表示具有30Mbps带宽和60msec延迟 的 图 （ n1 ， n2 ， n3 ， n4 ） 的 连 接 符 。 连 接 器 事 实 集 在 表 2 中 突 出 显 示 为Connectors。不管我们在第3节和第5节中声明了什么，在这里，当我们必须编写程序子句时，我们为连接器元组中的节点选择不同的顺序：输入节点再次是（如在在前面的章节中）位于表示子句中连接器的列表的第一个位置，但是在本节中，我们决定按字典顺序排列输出节点（即，n0先于n1，n1先于n2，依此类推）。这个决定是由编写程序和查询时的简化决定的，因为排序的节点可以很容易地记住。124S. 比斯塔雷利等人理论计算机科学电子笔记190（2007）111∞|---− −⟨ ⟩×0表2的叶表示Prolog规则的终止，并且它们的成本是相关联的0-连接器的成本（值100表示带宽）。聚合器规则， 倍 在 表 2， 模仿 的 × 操作 的 C-半环 提出 在第5节中：S网络=网络B ∪ {0， +∞}， D{0， +∞}，+J， ×J， 0， +∞， +∞， 0，其中×J等于min， max，+J等于最大，最小，如第5节所定义。最后，规则1 2 3表2中的第4行描述了我们我想在图上找一下。规则1表示一棵树只有一个叶子节点，规则2描述了一棵树，它由一个连接器和一系列具有根节点的子树组成在连接器的目的节点的列表中，规则3是规则4的终止，并且需要规则4来管理列表[X Xs]中具有根的不相交子树的连接。 当我们组合连接器和树时（规则2和规则4），我们使用聚合器来组合它们的成本。为了使表2中的程序尽可能可读，我们省略了两个谓词：排序谓词，需要对连接器和树的目的节点列表中的元素进行排序（否则，查询树（n0，[n6，n7，n8，n9]，[B，D]）和树（n0，[n9，n7，n8，n6]，[B，D]）将产生不同的结果），以及交叉谓词，用于检查如果从不同的连接器可达，同一节点的多次出现不会出现在同一目的节点列表中（否则，例如，树n0，[n7，n7，n8，n 9]将是有效的结果）.为了解决与或图问题，在Prolog语言中执行查询就足够了：例如，如果我们想计算所有以n0为根的树的成本，并将代表接收者的节点作为叶子（在这种情况下，n6，n7，n8，n9），我们必须执行查询树（n0，[n6，n7，n8，n9]，[B，D]），其中B和D变量将用找到的树的带宽和延迟成本来实例化。CIAO程序针对该查询的输出之一对应于图6中的树，即2， 5，因为J计算连接器的最小带宽-最大延迟用CIAO程序得到的树的最终成本等于一个可以通过使用×J来定义Sec中给出的fr3 .第三章。从源节点NJ0和连接器（NJ0，NJ1）开始，成本为10，1，树cnJ是cnJ0=fr（cnJ1）=10，1×JcnJ17结论我们描述了一种与或图和SCLP编程相结合的方法来表示和解决多播QoS问题：与或图上的最佳树对应于由图建模的最佳多播分发树。最优树优化了一些关于QoS性能的目标，例如最小化全局带宽消耗或减少延迟。c-半环的结构定义了对链路代价进行建模的代数框架，SCLP框架描述并解决了SCSP问题（最佳树）。S. 比斯塔雷利等人理论计算机科学电子笔记190（2007）111125表2CIAO程序表示图 1 中 的加权与或图问题上 的所有与树。 5b.宣告式的 由于几个不同的标准必须全部优化（成本的弧包括不同的QoS度量值），最佳树问题属于多准则问题类。第一个未来的改进可能是使用动态编程技术，例如记忆化，以减少在表示网络的图上搜索多播树期间的指数爆炸。 然而，在未来，我们计划进行一些实验，直接测试我们的框架的计算复杂度。此外，我们计划通过使用软并发约束编程[7]来丰富这个框架，以处理路由设备和接收器之间的交互，因此，我们希望引入新的“软”操作（例如，约束的撤销）以释放由多播接收器保留的资源，从而引入约束存储的非单调演变未来的研究还可以解决由于网络状态的不断变化，包括多播组的请求，最佳树的重构。126S. 比斯塔雷利等人理论计算机科学电子笔记190（2007）111<10，1>n'1<7.3>n'3n'4<3.5><4，3>n'5<7.1>n'7n'8<，0><，0>8n'0n'6<，0>n'9<2，3>图六、其中的组播分发树可以用表2中的程序找到.由于网络必须有效地用于同时传输多个数据流，因此即使在本文中，我们已经在与或图上应用SCLP程序来找到最佳组播分发树，也可以使用相同的框架为了解决决策表上的问题[20]，通过将它们转换为与或图，或者其他的动态规划问题。决策表广泛用于许多数据处理应用程序中，用于指定必须采取哪种动作来执行某个穷举集合中的任何条件。每个条件都由一组条件测试的结果组合来表征。 一个重要问题是从一个表中导出一个在某种特定意义上是最优的决策树引用[1] 伯曼湖L. Kou和G.Markowsky，Steiner树的快速算法，Acta Informatica15（1979），pp.141-145[2] Bistarelli，S.，“Semirings for Soft Constraint Solving and Programming,” Lecture Notes inComputer Science[3] Bistarelli，S.，联合Montanari和F.Rossi，半环上的约束求解，在：Proc. IJCAI95（MorganKaufman）（1995），pp. 624-630[4] Bistarelli，S.，联合Montanari和F. Rossi，基于半环的约束逻辑编程，在：Proc.IJCAI97（MorganKaufman）（1997），pp. 352-357[5] Bistarelli，S.，联合Montanari和F.Rossi，（多准则）最短路径问题的SCLP语义，in：Informal Proc.CP-AI-OR[6] Bistarelli，S.，联合Montanari和F. Rossi，Soft constraint logic programming and generalized shortestpath problems，Journal of Heuristics8（2002），pp.25比41[7] Bistarelli，S.，联合Montanari和F.陈晓，软并发约束程序设计，北京大学出版社。逻辑7（2006），pp.563-58988S. 比斯塔雷利等人理论计算机科学电子笔记190（2007）111127[8] Bistarelli，S.，联合Montanari和F. Rossi，基于半环的约束求解与优化，Journal of the ACM44（March1997），pp.201-236[9] Alberto，F.，D. Ca beza，M. Carro，M. 赫梅内吉尔多山口 L'opez-Gar c'ıa和G. 普埃布拉，《计算机程序系统：参考手册》，技术报告CLIP 3/97.1，马德里技术大学计算机科学学院（UPM）（1997年）。[10] 陈淑仪，K. Nahrstedt和Y. Shavitt，A QoS感知多播路由协议，在：IEEE计算机和通信学会的INFOCOM联合会议（3）（2000），pp. 1594-1603年。[11] Cormen，T. T.，C. E. Leiserson和R. L. Rivest，[12] Georget，Y.和P. Codognet，Compiling semi-ring-based constraints with clp（FD，S），in：CP205-219.[13] Hirsch，D.和E. Tuosto，SHReQ：协调应用级QoS，在：SEFM425-434.[14] Ja Padar，J.和M.J. Maher，约束逻辑程序设计：综述，逻辑程序设计杂志19/20（1994），pp. 503-581[15] Martelli，A.和联合Montanari，Optimizing decision trees through experimentally guided search，Commun.ACM21（1978），pp. 1025-1039[16] Mohri，M.，最短距离问题的半环框架和算法，J。自动浪Comb.7（2002），pp. 321-350.[17] Moy，J.，OSPF版本2，RFC 2328（IETF标准）（1998）。URLhttp://www.ietf.org/rfc/rfc2328.txt[18] 尼古拉河D、G. L.法拉利，美国蒙塔纳里河Pugliese和E. Tuosto，推理的形式基础在可编程QoS上，在：N中。Dershowitz，Verification：Theory and Practice，Lecture Notes in Computer Science2772（2003），pp.436-479[19] Nilsson，N.J.， 美国加利福尼亚州旧金山，198
