崔潇宇，沈庆国

（陆军工程大学，江苏 南京，210000）

0 引 言

多协议标记交换（MLPS）网络是专为IP流提供端到端的服务质量而设计的。QoS很重要，如对于交互式音频应用程序，动态流的准入控制是网络中基于QoS需求和可用资源接受或拒绝一个新流程的核心机制。如果没有这种机制，网络会不断允许新的数据流通过，以致过载一条或多条链路，导致一些流程的服务质量下降。此环境中，业务路由选择也是一种寻找到达目的路由器的路径的重要机制，同时遵循QoS约束。准入控制可以利用路由的结果，但是它也可能从路由中独立出来。比如，即使存在一条平滑的路径，准入控制可能根据流量监控拒绝一个流。不过，大多数准入控制机制是基于路由的。

通常，QoS约束包括两方面：线性约束和路径约束。线性约束适用于本地链接，而路径约束是端到端的。路径约束主要有端到端的延迟、丢包率、抖动和带宽，这些约束也可以被用于本地链接。

准入控制可以是集中式[1-2]或分布式[3-4]的，前者是服务器通过在网络中聚集信息作出决策，后者是边缘路由器在网络上保留完整或部分信息，在入口结点处作出决策。这意味着核心服务器在建立时可能产生高时延，而区分的方法会受到非最优决策的影响。另外，准入控制可以是基于预留[1]或是测量的[5]。

目前，许多学者从事这个领域的研究，大部分已提出的机制想要满足新需求的端到端延迟或丢包率约束，但明显没有考虑已经允许的流。当前，尚没有提出不经过重路由能解决所有流的端到端延迟或是丢包率约束的解决方法。本文中，“重路由”表示为一个流寻找一条新的路径，并通过它将所有数据包聚集成这个流。由于重路由可能影响服务质量，因此需要尽量避免。

本文提出了两种MPLS网络中业务流在联合路由和准入控制（JRAC）问题方面的模型。联合路由和准入控制意味着这个决策不能和路由过程同时允许一个新流，也就是说，这个新流要寻找一条到达目的端的标签交换路径（LSPs）。第一个模型满足端到端的时延约束，第二个模型满足丢包约束。这些约束不仅针对新的业务流，也对所有已经允许通过的流。目标函数是求一个新业务流端到端时延的最小值。

1 准备工作

1.1 符号表示

1.1.1 集合

N表示路由结点的集合；M 表示单向链接的集合；L表示单向LSPs的集合；hP表示由至多h条LSPs组成的连接所有源结点和目的结点的路径集合；T表示已经允许通过的流的集合。其中，一个流Tt∈在结点NtO∈)(开始、NtD∈)(结束，它的通信量需求为tα（单位：b/s），最大时延限制为tβ（单位：s），最大端到端的丢包率限制为tφ。

1.1.2 常量

令为0-1常量，满足当且仅当流t∈T通过链路为0-1常量，满足当且仅当LbaLSP∈),(通过链路Mji∈),(。

1.1.3 时延和丢包率函数

令dij( fij)为链路(i, j)上的时延，pij( fij)为链路(i, j)上的丢包率，rij( fij)为链路(i, j)上数据包的传送速率，即本文使用M/M/1/k排队模型，因此：

其中，是链路(i, j)上的平均到达速率（单位：包/秒）；ρ是链路(i, j)的平均利用率；k是缓冲区的大小（单位：包）；l是平均包长（单位：bit）；cij是链路(i, j)的容量（单位：b/s）；fij是链路(i, j)的最终通信量（单位：b/s）；aij是链路(i, j)上的传输时延与在结点i∈N的过程时延（单位：s）。

本文选择这个模型，主要是因为它便于分析，且任何时延和丢包率模型都可以和已提出的JRAC模型结合使用。实际上，时延和丢包率参数仅仅是JRAC模型的输入参数。实际网络中，一条链路上的时延和丢包率可以通过路由测定，且只需使用增量参数即可，如随机模型。

1.1.4 变量

令xab是0-1变量，满足xab=1当且仅当新流通过LSP(a,b)；yij是0-1变量，当且仅当新流通过链路 (i, j)。

1.2 问题公式化及预处理

本文提出的联合路由和准入控制问题在于考虑网络中已经允许通过的流，为从源结点o到目的结点d的新流寻找一条路径，且满足流量需求α、端到端的时延限制β和丢包率限制∅。如果这种路径不存在，那么新的流将被阻塞。

我们认为一种合理的拓扑结构已经建立。这种拓扑由边缘结点之间的LSPs组成。本文中，每一对边缘结点间都有一条LSP。拓扑中，一条LSP被视作一跳。LSPs的路径选择使用Dijkstra最短路径算法，带宽根据接受的新流调整，可以根据一些协议如RSVP[6]来调整LSPs的带宽。既然一个流可以使用多种LSPs，那么在一条LSP终止时检查IP头部，计算当前的结点是否是目的结点或者数据包是否需要继续通过另一条LSP。

为了将数学模型公式化，预处理十分必要。注意，如果一个新流不通过链路(i, j)，那么这条链路上的通信量为：

链路(i, j)上的时延丢包率为数据包的交换率为Rij=1-Pij。否则，链路上的通信量为：

链路(i,j)上的时延为丢包率为数据包的传输速率为

类似地，如果新流不通过LSP(a,b)，端到端时延、传输速率和丢包率分别为：

否则，如果新流通过LSP(a,b)，那么：

2 模型建立

2.1 时延约束的准入控制

MPLS网络中不发生重路由，满足端到端的时延约束的联合路由和准入控制的数学模型，可表示为JRAC-D（Joint Routing and Admission Control with Delay Constraints），给出JRAC-D：

JRAC-D的目标函数（13）是求新流的端到端时延的最小值，约束条件（14）表示变量yij等于新流通过链路(i, j)时利用的LSPs的数量，且这个数量小于等于1，也就是说新流只能至多通过链路一次。注意，yij可以从模型中消去（即约束条件（14）和约束条件（15）可以合并，那么式（17）中的yij由约束条件（14）表示。通过变量约束条件（16）限制路径中新流使用的LSPs数量至多为h，模型更加易于理解。这些限制条件使准入控制过程更加容易实现，只需要使用基于路径的方法。相比于在准入控制过程中观测每一个流，只需要观测由1,2,…h条LSPs组成的可能路径。约束条件（17）表示网络中每一条已经被允许通过的流遵循端到端的时延限制，约束条件（18）表示新流也遵循端到端的时延限制。约束条件（17）和约束条件（18）很重要，因为它们使得所有流都遵循QoS需求。条件（19）表示流的守恒约束，约束条件（20）是完整性约束。

JRAC-D是NP难题[7]（Non-deterministic Polynomialtime Hard），由最短权重的路径约束问题转化而来。因为整数变量的数量很少，JRAC-D模型可以在极短的时间使问题的实际大小变得最优。

2.2 丢包约束的准入控制

MPLS网络中不发生重路由，满足端到端的丢包约束的联合路由和准入控制的数学模型，可表示为JRAC-P（Joint Routing and Admission Control with Packet Loss Constraints），如下给出。

满足式（14）～式（16）、式（19）式（20）和：

JRAC-P的目标函数（21）是求新流的端到端时延的最小值，使用这个目标函数是因为时延是衡量大多数应用的一个重要的QoS参数。约束条件（22）和约束条件（23）使得所有流都遵循丢包需求，这些线性约束是通过对数转换算法得到的。为了使这些约束条件成立，预处理中应该证明对任意t∈T，有1＜φ和1＜tφ；对任意Mji∈),（，有对任意(a,b)∈L，有

相对于JRAC-D模型，JRAC-P也是NP问题，同时能够进一步证明它得到实际情况下问题的最优解所需要的计算时间更少。

3 结 语

本文提出在MPLS网络中关于业务流的联合路由和准入控制问题的两种数学模型。第一种模型满足端到端的时延约束，第二种模型满足端到端的丢包约束。这些端到端的QoS约束不仅针对网络中的新流，也针对所有已经允许通过的流。目标函数是求一个新流使用路径的端到端时延的最小值。通过准入控制策略，这些模型能够预处理后准确地解答。对于这个问题，还有一些其他研究方法。可以优先考虑其他目标函数，如收益函数。一般通过有效探索，快速寻找拟最优解。在多重约束模型中，试验将会是有意义的。

[1] Antonio C,Luigi F,Fabio M.Dynamic Routing of Bandwidth Guaranteed Connections in MPLS Networks[J].International Journal on Wireless & Optical Communications,2012,1(01):75-86.

[2] Widyono R.The Design and Evaluation of Routing Algorithms for Real-time Channels[D].Berkeley:University of California,1994.

[3] Ali N A,Mouftah H T,Gazor S.Online Distributed Statistical-delay MBAC with QoS Guarantees for VPLS Connections[C].International Conference on Telecommunications IEEE,2005(02):383-390.

[4] Reeves D S,Salama H F.A Distributed Algorithm for Delay-constrained Unicast Routing[J].IEEE/ACM Transactions on Networking,1997,8(02):239-250.

[5] Uzunalioglu H,Houck J D,Wang T Y.Call Admission Control for Voice over IP[J].International Journal of Communication Systems,2010,19(04):363-380.

[6] Zhang L,Berson S,Herzog S,et al.Resource ReSerVation Protocol(RSVP)--Version 1 Functional Specification[J].Ietf Rfc,1997,40(05):116-127.

[7] Garey M R,Johnson D S.Computers and Intractability:A Guide to the Theory of NP-Completeness[J].1979,23(02):555-565.