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

4.4我们给出了QoS度量上的dd约束，以便完全得到约束路径的模型。4.1从SP Proble m s到SCLP程序，我们假设使用一个图G=(N，E)，其中从节点p到节点q(p，q∈N)的每个定向弧E∈E都关联了一个标记，该标记表示从p到q的弧的代价，如图3所示。如果节点与网络设备（路由器和主机）相关联，并且arcs与网络连接相关联，则可以使用该图来表示网络。对于任何SP问题，我们都可以建立一个SCLP程序，如下所示：对于每个arc，我们有两个子句：一个描述arc，另一个描述它的成本。更准确地说，fiefrst子句r的开头表示起始节点，其正文包含fiefrst节点和谓词，比如表示弧的代价的谓词c。然后，第二个子句是一个与谓词c相关联的事实（它是一个半环元素）。即使在本节中，成本的c oncept是相当普遍的，我们也认为，根据这一事实，我们表示了弧上的QoS度量值(SEESEC.3)。例如，如果我们考虑从p到q的cost为2的弧，我们有eclausep：-cpq,q.和fac tcpq：-2。最后，我们必须编写代码，我们希望v成为路径的节点。这是通过添加一个形式为v：-0的子句来完成的。还请注意，任何节点都可以被定义为fiffnal节点，而不仅仅是那些没有输出弧s的节点（就像这个例子中的v）。整个程序与FIG中的SP问题有关。为了表示经典的SP问题，我们考虑半环S=hN,min,+,+∞,0i下的SCLP问题，这是一个适当的框架来表示约束问题，其中人们希望最小化解的成本之和。例如，我们可以想象弧上的代价代表我们在RELATED链路上经历的平均延迟（以几十毫秒为单位）。为了计算SP问题的解，对SCLP框架进行查询就足够了；例如，如果我们想要计算从r到v的路径的开销，我们必须执行查询：-r。对于该查询，我们获得valueACM日记名称vol。V,no.N,20yy。软约束逻辑编程的单播和组播QoS路由·13表II。表示图中SP问题的SCLP程序。3.P:-cpq，Q。CPQ:-2，P:-cpr，R。心肺复苏：-3。问：-cqs,S。CQS:-3.R:-crq，Q。CRQ:-7.R:-crt，T。CRT:-1，R:-cru，U。CRU:-3。S:-csp,P。CSP：-1.S：-csr,R.CSR:-2.S:-csv,V.csv:-2.T:-cts,S.CTS：-3。U：-杯，第2页。杯子：-3。U：-切，T。切:-2.U:-cuv，V:cuv:-3.V:-0.PSVutrqabacbaaacbcbaFig。4.一个带标号弧的SP问题。6,它代表了从r到v的最佳路径的代价，用这种方法优化了从r到v的路径上所经历的总延迟。明确地说，选择半环扫描来表示半环扫描度量的组成参数，我们将在Se C中看到更好的结果。4.2通过提出带宽作为描述链路成本的第二个度量。注意，为了在SCLP中描述经典的SP问题，我们不需要任何变量。因此，所得结果是正确的。然而，这个程序虽然给出了最短路径的代价，但并没有给我们任何关于形成这种路径的弧的信息。这个信息可以通过为每个谓词提供一个参数来获得，这个参数表示在每个步骤中选择的一个rc。图4显示了图中相同的SP问题。3在每个结点出口的弧线上都有标记来标记它们。这样的标签可以将d编码到相应的SCLP程序中，以“记住”在通往解决方案的路径中所经过的弧。例如，clausep：-cpq,q.将被改写为asp(a):-cpq,q(X)。V,没有。

N，20yy.14·Stefano Bistarelli et al.这里常数a表示从p中走出的一个弧：到q的一个弧。如果所有子句s都以类似的方式重写，那么像-r(X)这样的目标的答案将是一个半环值（在我们的例子6中）和X的替换。这个替换将识别从r到v的最短路径的第一个弧。例如，如果我们有vex=b，这意味着这个弧是从r到t的那个弧。为了找出最短路径，我们只需要比较与每个实例化目标相关联的半环值，从fr到om r。例如，在我们的例子中（对于g oal-x.r(X))，我们认为目标的答案是X=C，半环值为6。因此，我们知道从r到v的最短pa可以从r到u的弧开始。为了了解这条路径的下面的弧，我们比较了u(a)、u(b)和u(c)的引出值。结果是u(c)具有smallestvalue，即3。因此，我们正在构造的最短路径的第二个弧是从u到v的弧。路径现在被定义了，因为我们重新定义了v,这是我们的最终目的地。注意，即使程序中不允许变量，也可以找到最短路径，但需要做更多的工作。事实上，我们需要比较与表示从certainnode开始的可供选择的弧可到达的节点的谓词相关的值，并将它们和这些弧的代价，而不是compa环di-hyling di-hyling di-hyling di-hyling di-hyling instantiations。例如，我们不必比较p(a)和p(b)的va lue（图4)，而必须比较q+2和ofr+3的va lue s（图3）。计算最短路径的第三种选择，不仅是它的成本，是对使用者的：用clausep([aT]):-cxy，q(T)替换formp:-cxy，q.的每个c lause。在计算过程中，我们还建立了包含构成c或响应路径的所有弧的列表。因此，通过给出目标:-p(L).我们将得到最短路径的Ecost和由列表L表示的s hortest路径本身。SCLP中SP问题的另一种表示形式，可能对CLP用户来说更熟悉，是o ne，其中有以下事实：c（p,q):-2…c（u,v):-3。对图进行建模，并有两个小节path(X,Y):-c(X,Y).path(X,Y):-c(X,Z)，path(Z,Y):-c(X,Z)，path(Z,Y).对长度为一个或多个的pa进行建模。在这个表示中，要确定从p到v的最短路径的代价的目标是:-path(p,v）。这个表示显然比表II中的表示更为紧凑，并且具有等价的结果和性质。然而，在下一节中，我们将继续使用表II中使用的更简单的表示法，其中所有子句在主体中至多有一个谓词。用仅包含此类子句的SCLP程序来表示SP问题的可能性是很重要的，因为它将允许我们使用e（？）cient算法来计算此类程序的语义（更多细节请参见[Bistarelli et al.2002]）。用软约束逻辑编程的单播和组播QoS路由·15<3,1><3,4><1,3><3,2><2,1><3,4><2,1>PSVUTRQ<7,3><3,3><2,4><1,1><2,2><3,3>图。5.多准则SP问题4.2偏序SP问题有时，弧的代价不是全序集的元素。对于r多准则SP问题，给出了一个典型的例子。例如图中所示的多准则SP pro blem。5：每个arc都有相关联的apair，它们表示arc在使用成本和平均延迟方面的权重（即两个可能的QoS度量）；因此，这些值是hcost,de la yi形式的。在给定节点p的情况下，我们希望从m p到v（如果存在的话）找到一条最小化两个条件的路径。在本例中，可能存在两个弧的标签不兼容的情况，如h5，20i和h7，15i，因为在第一对中成本更好，而在第二对中延迟更低。

一般说来，当我们有一个部分给定的代价集时，可能有几条路径是可能的，所有这些路径都不受其他路径的支配，但它们具有不可比的代价（参见第6节）。我们可以将这个SP问题翻译成图。5进入相应的SCLP程序表III。该程序在半线性上工作，min′，+′，h+∞，+∞i，h0,0ii,其中min′，+′是经典的min，+，适当地推广到对。这个半环是通过笛卡尔积把两个C-半环的实例hN,min,+,+∞,0i组合在一起得到的（我们记得两个C-半环的笛卡尔积也是C-半环[Bistare lli et al.1997b])。其中一个例子用于处理代价准则，另一个例子用于处理延迟准则。通过对组合半环的研究，我们可以同时处理这两个准则：偏序将告诉我们什么时候一个hcost,delayi对比另一个更好，也告诉我们什么时候它们不是比较的。为了给出另一个偏序问题的实际应用，只要考虑网络路由问题，我们需要根据以下准则进行优化：最小化延迟、最小化代价、最小化遍历弧数和最大化ba ndwidth。这三个判据对应于同一个半环，即hN，min，+，+∞，0i，而第四个判据可以用se miring hB，max，min，0，+∞i来表征，其中B是可能的带宽值的se t（在第5.1节中，我们将更好地研究这些半环）。在这个例子中，我们必须研究一个半环，它是通过向量化所有这四个半环而得到的。每个半环都是完全有序的，但结果是ACM杂志名称，卷。V，No.N，20YY.16·Stefano Bistarelli et al.表II，I.表示图中多准则SP问题的SCLP程序。5.P:-cpq，Q。CPQ:-<2,4>。P：-cpr,R。CPR:-<3,1>。Q:-cqs,S。CQS:-<3,3>。R：-crq,Q。CRQ:-<7,3>。R:-crt,T。CRT:-<1,3>R:-cru,U。CRU:-<3,4>，S:-csp,P。CSP:-<1,1>.S:-csr,R。CSR:-<2,2>.S:-csv,V.csv:-<2,1>.T:-cts,S.CTS:-<3,2>，U:-cup,P。杯:-<3,3>。U：-切，T。cut:-<2,1>.u:-cuv,v:-cuv,v:-<3,4>.v:-<0,0>.半环的元素是四元组的，半环是部分有序的。4.3基于模态的SP问题现在我们已经考虑了用代价标记弧的情况，是一个元素还是一个元组，就像在多准则的情况一样。然而，有时，与每条弧线相关联的信息也可能是有用的。例如，将图形中的弧线解释为城市之间的联系，我们可能想要模拟这样一个事实，即我们可以用汽车、火车或飞机覆盖这样一条弧线。另一个例子可以是我们覆盖弧线的一天中的时间，比如早上、下午和晚上。再举一个例子，这一次与本文的主题有关，可以用与网络链路相关联的模式来表示，如有线、无线或VPN，如果在其上有一个虚拟专用网络的话。因此，该模式可以用于路由的策略（即，用于策略路由）。在所有这些例子中，弧的形状可能取决于它的模态，需要注意的一件重要的事情是，路径可以由不一定都覆盖着相同模态的弧构成。例如，同一公司的两个遥远的建筑之间的网络连接可以由许多跳组成，其中一些跳覆盖无线模式，另一些跳覆盖有线模式。此外，可以是di hen erent弧具有di hen erent modalities集。例如，从节点n到节点n，我们可以使用有线和无线连接，从节点n到节点n，我们只能使用VPN。

因此，不能简单地通过选择一个弧的子集（所有具有相同模态的弧）来处理模态。一个SP问题的例子有三种模态，它们表示在链路(c)（有线或无线）、有线/无加密(w)和无线/无加密(l)上具有加密GR aphic服务的网络。6.这里的问题是找出从任何节点到v（目的地）的最短路径，并知道它的延迟和它的弧的模态。这个SP问题可以通过表IV中的CLP程序进行建模。在这个程序中，变量表示modalities.acm日记名称vol。单播和组播QoS路由软约束逻辑编程·17WLCWWCWWWWCLCCCCLWWPSVUTRQFIG。6.与模式有关的SP问题。用图中的模态表示SP问题的SCLP程序。6.P(X):-cpq(X)，q(X)。cpq(w):-2。P(X):-cpr(X),r(X)。cpq(l):-3.Q(X):-cqs(X),s(X)。cpr(c):-3.R(X):-crq(X)，q(X)。cqs(l):-3.R(X):-crt(X)，t(X)。crq(c):-7.R(X):-cru(X)，u(X)。crt(w):-1.S(X):-csp(X),p(X)。cru(c):-3.S(X):-csr(X),r(X)。csp(c):-1.S(X):-csv(X),v(X)。csp(w):-7.T(X):-cts(X),s(X)。csr(w):-2.U(X):-cup(X)，p(X)。csv(w):-2.U(X):-cut(X)，t(X)。csv(c):-3.U(X):-cuv(X),v(X)。cts(l):-3.V(X):-0。cts(w):-3.cup(c):-3.cup(w):-1.cut(w):-2.cuv(w):-3.cuv(c):-2.如果我们询问查询:-p(c)，这意味着我们想知道使用与加密服务的链接从p到v的路由的最小延迟。在我们的e xample中，这个查询的结果是p(c)=8（使用路径p-r-u-v）。IV对要找到的最短路径设置了一些可能不希望的约束。事实上，通过在一个规则的所有谓词中使用相同的变量，我们可以确保在整个路径中使用相同的模态（在我们的例子中称为运输平均）。相反，如果我们希望在路径的di e erent弧中允许di e erent模态，那么我们只需要通过在每个规则的最后一个谓词上添加一个新变量来改变规则。例如，Tab中的规则。IVp(X):-cpq(X)，q(X)。将成为EP(X):-cpq(X)，q(Y)。V,no.N,20yy.18·Stefano Bistarelli等人。现在我们可以用一个模态来表示从p到q的弧，另一个模态来表示下弧。在这个新的pro gram中，请求查询：-p(c)。这意味着我们想知道从p到v的行程的最小延迟，使用firerstarc中的cr yptographic服务。在这类SCLP程序中也可以使用前几节中用于搜索最短路径的方法，或者在偏序情况下搜索非占优路径的方法。因此，我们可以在谓词中添加额外的变量来表示出相应结点的替代弧，并且我们可以转移到包含代价的s ets的半环上，以找到一个非支配路径。特别地，类似于p(X):-cpq(X),q(Y).的c lause将被改写为asp(X，a):-cpq(X),q(Y，Z)。4.4增加了对SP问题的约束，如SEC中所见。3.1一个MCOP比一个SP pr oblem更需要解决，即NP完全。到目前为止，我们只考虑了SP问题的几个方面（局部的或基于模态的），但我们的目标是为单播QoS路由提供一个完整的模型。因此，除了实现成本优化之外，我们还需要考虑QoS指标的约束。在我们的例子中，我们再次考虑了图中的多准则图。5：每个弧都有一个对应的对，这个对可以代表弧的使用成本和平均延迟的权重。然而，在这种情况下，我们的目标是最小化成本，并保证平均延迟小于或等于8(80msec)，因此我们希望增加boo le a约束延迟≤8。我们选择在CIAO Prolog[Buenoet al.1997]中用一个prog ram来重新发送约束路径，该系统支持ISO-Prolog的完整Prolog系统，但同时它的模块化设计允许对basic语言进行修改和扩展。

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,没有。

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星（图）。

8)，对于一个可能的马ximal数o f2n-1子集（其中N是图中节点集的基数），即排除空集；在秒内。8我们将看到如何最小化这种指数增长。因此，所有以nias为输入节点的连接器都是(ni，nj)，(ni，nk)，(ni，nz)，(ni，nk，nj)，(ni，nk，nz)，(ni，nk，nz)，(ni，nj，nz)，ni，nj，nz)和(ni，nj，nk，nz)。在节点的连接器元组排序中，输入节点位于figurrst位置，输出节点（当多于一个时）遵循图中相关箭头的方向。8.简化图。8b中，直接连接两个节点的ar cs表示1-连接器(ni，nj)、(ni，nk)和(ni，nz)，而弯曲定向直线表示n-连接器s(n>1)，其中它们的输出节点集对应于穿越弧的输出节点。用re spect到ni，图中。8我们有一条曲线，标有a对应于(ni，nk，nj，nz)，b对应于(ni，nk，nj)，c对应于(ni，nj，nz)，在la st，d对应于(ni，nk，nz)。为了清楚地了解，图中的网络链接。9A ar面向“朝向”接收器，因此我们只将cor响应连接器置于INFIG。9b.在我们这里提出的例子中，我们感兴趣的是只涉及带宽和成本的QoS链路状态信息。因此，ne twork的每一个环节都可以用一个二维成本来标记，因为pa ir h7，3i告诉我们，ACM期刊名称，Vol。V，No.N，20YY.22·Stefano Bistarelli等。该特定链路的最大带宽为70Mbps，代价为30E。通常，我们可以用n维向量来表示代价，其中n是在计算最佳分布树时要考虑的度量数。由于我们希望在and-or图中保持这种链路状态信息，所以我们使用相同的值元组（图9）。在一个连接器代表多个网络链路的情况下（即n≥2的nconnector）,它的成本是通过将这些链路的COSTs与comp osition op ERENTION进行组合来决定的，该comp osition op ERENTION采用与连接器所代表的链路数量一样多的n维向量作为操作数。当然，我们针对用于表示QoS的特定类型的成本实例化此操作：对于本节中给出的示例，其结果是最小带宽和最高成本（也可以是链路所有成本的总和），因此，最差QoS度量值:^(hb，ci，hb，ci，..，hbn，cni)-→hmin(b，b，..，bn)，max(c，c，.，cn)，Ifig中连接器的成本(n，n，n)。9b将是h7，3i，因为连接器(n，n)和(n，n)的成本分别是h7，2i a nd h10，3i:ut(h7，2i，h10，3i)=h7，3ito简化图。9b中，我们只插入了1-Co nnec连接器的成本，但其他连接器的成本可以很容易地通过“退出”操作计算，并在标签中报告。vi.到目前为止，我们能够用acorres po nding和-或加权图来翻译整个网络的QoS值，但我们仍然需要一些代数框架来建模我们对链路的偏好，以便在最佳tr EE中使用。为此，我们使用半环的tructure（第2节）。在[Mohri 2002；Ta rjan 1979]中，我们对最短距离nc e问题的半框架方法给出了详尽的解释。例如，如果我们对最大化分布树的ba ND Width感兴趣，我们可以得到半环SbandWidth=hBé{0,+∞},max,min,0,+∞i；否则，如果我们打算使用一条已经很忙的链路，以便保留其他未被删除的链路供将来使用，我们可以使用hBé{0,+∞},max,min,+∞,0i来最小化全局带宽（即。如果我们需要使树的总成本最小化，我们可以使用smoney=hN,min,+,+∞,0i来表示货币成本。

带宽值集）可以通过收集网络c上的信息、当前的状态和关于链路的技术信息来获得。由于c-半环的组成仍然是一个c-半环[Bistarelli et al.1997b],Snetwork=hhBé{0,+∞},Ni,+′,×′,h0,+∞i,h+∞,0iii,其中+′和×′与c-半环中的+和×ope的向量n有关：给定b,b∈bé{0,+∞}和c,c∈n,hb,ci+′hb,ci=hmax（b,b）,min（c,c）ihb,ci×′hb,ci=hmin（b,b）,ci=hmin（b,b）,ci=hmin（b,b）,ci=hmin（b,b）,因为带宽和成本必须得到优化。我们认为标准是独立的ACM期刊名称，卷。用软约束逻辑编程的单播和组播QoS路由·23subnetworka）b)<10,1><3,6><1,5><7,2><3,5><2,9><8,1><5,3><10,3><2,9><7,<2,3><7,2>图。9.一个网络实例和相应的与或图表示。否则，它们不能被重新表述为一个单一的准则。因此，connec节点的多维代价不是一个全序集的元素，可以得到几棵树，所有这些树都不受其他树的支配，而是具有不可比的代价。对于每个接收节点，它的输出0-连接器的代价总是包含在到达它的每棵树中。提醒一下，0-Connector只有一个输入节点，而没有目的地节点。如果我们把一个接收者看作一个普通节点，我们可以将代价设置为所采用的C-半环的1个元素（1是×的单位元素），因为到达该节点的代价已经完全被终止于该节点的分支的其他连接器所占用：实际上，我们将最高的QoSvalue s与该0-连接器相关联，在这种情况下是带宽和空代价。另外，我们可以将接收机想象为一个更复杂的子网络（如图9中的节点n)，因此，我们可以将0-连接器的成本设置为在该子网络中的节点n之后的0-连接器的成本h2,3i），以防我们不希望或不能考虑子网络的拓扑结构，例如。出于安全考虑。5.2与或图使用SCLPIn这一节，我们用SCLP中的程序表示与或图。利用该框架，我们可以很容易地解决FIG中关于multicastQoS网络的多准则示例。9b.正如证券交易委员会已经提议的那样。4,为了表示SCLP中的CONNEC tors,我们可以写c(ni,[nj,nk]):-h10,3i,说明该图具有来自nito节点njand nk，带宽代价为100Mbps,代价为30E的连接器。其他SCLP子句可以适当地将rib e树的结构desc为searchACM Journal Name,Vol.V,No.N,20YY.24·Stefano Bistarelli等人在图上。原因与SEC中曝光的相同。4.4,我们在CIAO Prolog中用一个程序发送了一个与或图[Bueno et al.1997]。作为一个例子，从图中的加权与或图pr oblem。9b我们可以构建表VI相应的CIAO程序，如下所示。网络边（或1-连接器）的集合在Tab中突出显示为边。vi.每个事实都有结构边缘（源码、[dest节点]、[带宽、成本])。fa c t边（n,[n],[10,1])表示图（n,n）的1-连接器，带宽为l～100Mbps，代价为10e。标签中的规则1。VI用于将边（即1-连接器）组合在一起，以便通过使用c omposition运算符聚合1-c onnector的成本，来筛选n≥1的所有可能的n-连接器，如SEC中所述。5.1（组成D1连接器的带宽最低，成本最高）。

因此，使用这些ECLAUS（在规则1中），我们可以自动生成来自所考虑节点的所有connectorsoutgoing的集合（在表VI中，nocontainsx和insertlast areCIAO谓词用于构建格式良好的连接器）。表中的叶子代表0-连接器（1000代表带宽的∞值）。表VI中的plusand times规则分别模拟了SEC中半环支柱osed的+和×操作。5.1:Snetwork=hhBé{0,+∞},Ni,+′,×′,h0,+∞i,h+∞,0ii,其中+′等于hmax,mini,×′等于hmin,+i，以秒为单位。5.1.最后，第2-3-4-5条规则。描述我们要在图上搜索的路线的结构。规则2表示仅由一个叶节点组成的路由，规则3表示由一个连接器加上一个根节点在连接器的目的地节点的列表中的子路由组成的路由，规则4是规则5的终止，规则4需要管理不相交的子路由与列表[XXs]的连接；显然，当目标节点的列表[XXs]包含不止一个节点时，这意味着我们正在寻找一个多播路由。当我们组合seconnectors或tree（规则2和规则5)，我们使用时间规则将它们的成本组合在一起。在规则5中，append是一个CIAO谓词，用于在查询请求组播路由时将目标节点的多个链路连接在一起。最后给出了SEC中的谓词。5.1收集查询的所有结果，并在plus预测的帮助下返回选择的解决方案。5.1是用Prolog c lausesinside规则5来建模的，当组成多个1-连接器时，请注意tab中附加pr e dic的复杂性。VI可以通过使用di hensed erence列表来减少。但是，请参见SEC。8的复杂缺点。使程序在Ta B。VI尽可能易读，我们省略了两个谓词：排序谓词，需要对连接器和树的destinationnodes列表中的元素进行排序（否则，查询路由（n,[n，n,n,N]，[B，C])和路由(n，[n，n,n,n],[B,C])将产生di-erent结果），如果rea可使用di-erent连接器（否则，例如树n，[n,n,n8,n9]将是一个有效的r-erult）,则使用交集谓词来检查同一节点的多次出现是否出现在目标节点的同一列表中。为了解决与或g问题，用prologlanguage执行查询就足够了：例如，如果我们要计算所有根在nand且具有as的树的代价，则节点将表示所有接收者（即。{n,n,n,n}），ACM期刊名称，卷。V,No.N,20yy。软约束逻辑编程的单播和组播QoS路由。25表六。表示Fi G中加权与或图问题的最佳结果树的CIAO程序。9b.:-模块(multicastnetwork，_，_)。：-use_module（库（聚合））。：-use_module(library（lists））.max([X,Y]，X):-X>=y.max([X,Y]，Y):-X<Y.min([X,Y]，X):-X<Y.min([X,Y]，Y):-X>=Y.乘以([B1,C1]，[B2，C2]，[B，C]):-min([B1,B2]，B）,C是(C1+C2)。加上([]，最好的，最好）。加上([[B，c]休息]，[B1,C1]，Max):-Max([B,b1]，BMax)，min([C,C1],DMin)，加上（休息，[BMax，dmin]，最大）。路由(X，Y,BestQoS):-findall([B,C]，树(X,Y,[B,C])，L1)，plus(L1,[0，100],BestQoS）。树(X,[X],[B,C]):-leaf([X],[B,C])。树(X,Z,[B,C]):-connector(X,W,[B1,C1])，treeList（W,Z,[B2,C2])，times([B1,C1]，[B2,C2]，[B,C])，treeList([],[],[100,0])。树ist([XXs]，Z，[B,（X,Z1,[B1,C1]),附加(Z1,Z2,Z),树列(Xs,Z2,[B2,C2]),次([B1,C1],[B2,C2],[B,C])。边(n0,[n1],[10,1])。边(n1,[n2],[3,6])。边(n1,[n3],[7,2])。边(n1,[n4],[10,3])。边(n2,[n4],[1,5])。边(n3,[n5],[2,9])。边(n3,[n6],[3,5])。边(n4,[n5],[4,2])。边(n4,[n9],[5,3])。边(n5,[n7],[8,1])。边(n5,[n8],[7,1])。叶([n0],[100,0])。

叶([n1],[100,0])。叶([n2],[100,0])。叶([n3],[100,0])。叶([n4],[100,0])。叶([n5],[100,0])。叶([n6],[100,0])。叶([n7],[100,0])。叶([n8],[100,0])。叶子([n9],[2,3])。1）2）3）4）时间plusleavesedgesconnector（X,[Y],L,[B,C]):-edge（X,[Y],[B,C])，nocontainsx(L,Y).连接器(X,[Y],[B1,c2]):-edge（X,[Y],[B1,c2])，nocontainsx(L,Y)，insert_last（L,Y,Z)，connector（X,Ys,Z,[B2,c2])，min([B1,B2]，B)，max([C1,c2]).5）路,n,n,n],[B,C]),其中B和Cvariables将用所找到的树的带宽和代价实例化。此查询的CIAO程序的输出对应于INFIG树的开销。11，即。h2，16I。对于此查询，请使用Tab中的pr图的输出。VI是在无花果中展示的。10.无花果中的树。11是图INFIG的解决方案树（见第5.1节）。9b,映射函数g:g(n′)=n,g(n′)=n,g(n′)=n,g(n′)=n,g(n′)=n,g(n′)=n,g(n′)=n,g(n′)=n,g(n′)=n,g(n′)=n,g(n′)=n,g(n′)=n,g(n′)=n,g(n′)=n,g(n′)=n,g(n′)=n,g(n′)=n。..,nik），则其成本为ci=FR(ci，...,cik）其中fris功能成本与连接器相关联，andci，..cikare根植于节点ni，.的子树的代价。..,NIK.ACM杂志名称，卷。V，第N号，20YY.26·Stefano Bistarelli et al.ciao-prolog 1.10#5:2004年8月6日星期五19:01:54？-路线(n0,[n6,n7,n8,N9],[B,C])。B=2,C=16？.不？无花果。10.Tab中程序的CIAO输出。V.对于n,n,n,n,ndestins n\'0n\'1n\'3n\'6n\'4n\'9n\'5n\'8n\'7<10,1><7,3><4,3><7,1><3,5><2,3><0,0>8<0,0>8<0,0>8<0。11.用表六中的程序可以找到最好的组播distr ibution树。用CIAO progr am得到的结果与用×\'解frcost函数得到的结果是等价的。从n′源节点和代价为h10,1i的连接器(n′,n′)出发，树的总代价为cn′iscn′=fr(cn′)=h10,1i×\'cn′，如果被问的查询只包括一个目的节点，例如路由（n,[n],[B,C])，该框架也可以用来解决单播问题。5.3本节基于模态的Steiner树问题，如我们在Se C中所提供的。4.3对于普通路径，我们改进了树搜索，包括考虑与超弧使用相关的一些模态的poss资格。即使在这种情况下，正确的定义也很容易，因为有时与每个超弧联系起来也可能有用，因为它还包括关于用于遍历该特定超弧的模态的信息。在这一节中，我们仅用美国证券交易委员会的三个模式中的两个来展示一个例子。4.3：无encr yptionservice(w)的有线链路和无加密服务的无线链路(l)。其他类可以收集首选使用网络链路的白天时间片段（例如。toACM杂志名称，卷。用软约束逻辑编程的单播和组播QoS路由·27a)b)<7,2><3,5><2,9><10,3><4,2>nnnn0123n0n1n3<3,5><2,9>4N<10,3><4,2>8<0,8<0,7>2>4nwlwwwn2{w}{w}{w}{l}{w,l}<7,3>4nwlwwwn2{w}{w,l}{w,l}<7,3>图。12.a）具有与链接相关联的模态的网络，以及b）对应的超图。更好地支持tra的峰值，或者支持特殊的使用条件，例如支持“夜间备份”或“黑掉”事件。在图12中，我们展示了如何通过模态从网络传递到对应的hypergraph（从图12a到图12b)的示例：通过使用与连接器所代表的每个链接相关联的模态集上的联合操作器（即，在图12的示例中，找到与连接器相关联的模态。