基于路径估计的网络接纳控制研究

邱恭安，徐晨，章国安,2，包志华

(1. 南通大学 电子信息学院，江苏 南通 226019；2. 东南大学 移动通信国家重点实验室，江苏 南京 210096)

1 引言

未来宽度网络将综合承载语音、多媒体和数据业务，在为时延敏感业务提供时延保障的基础上，为非实时弹性业务提供基本吞吐量。要在相同网络上提供不同业务的差异化性能，可通过链路资源冗余方式，或应用接纳控制策略[1]。然而，要在整个网络中保持较低的端到端阻塞率，带宽冗余是极其浪费的，网络接纳控制是有效方式[2,3]。通常链路接纳控制仅计算下游链路对接入业务的资源保障，而不考虑网络路径后端瓶颈链路状态，不能有效保障实时业务的端到端时延要求。网络接纳控制(NAC,network admission control)[4]评价既定网络传输路径资源能够支持多少可保证QoS (quality of service)请求的应用，在多条链路构成的路径上提供一致的接纳判决。因此，网络接纳判决的准确性取决于传输路径状态信息的有效性，然而传输延迟或网络资源节省使得基于测量或路由表获取的路径状态信息具有陈旧性[5]，不再能描述网络的真实状态[6]，因此，获取实时或准实时的传输路径状态信息成为网络接纳控制的关键。

2 相关工作

根据接纳判决方式，网络接纳控制分为基于预算的网络接纳控制(BNAC, budget based network admission control)和基于反馈的网络接纳控制(FNAC, feedback based network admission control)两大类[7]。其中BNAC应用虚拟的路径容量预算策略进行接纳判决，而FNAC则根据返回的路径测量信息作出判决，共同特点是基于流进行接纳控制。FNAC首先从源端发送一个或几个探测分组测量传输路径负载状态，根据返回分组的QoS指标判断是否接纳请求业务流，存在着测量准确性和网络状态陈旧性问题。而且，需要占用一定的网络资源用于测量，链路资源效率存在着瓶颈上限。

BNAC需要与路径相关所有链路虚拟容量预算均满足业务请求时才接纳该业务，由于网络承载状态的动态变化，BNAC容量预算不能准确反映路径当前状态，容易导致链路资源效率低下或后端瓶颈链路拥塞。根据容量预算类型不同，BNAC分为基于链路预算的网络接纳控制(LB NAC, link budget based network admission control)、基于输入端输出端预算的网络接纳控制(IB/EB NAC, ingress and egress budget based network admission control)和基于边到边预算的网络接纳控制(BBB NAC, border to border budget based network admission control)3种方法。LB NAC在路径上的每条链路上执行接纳判决，状态信息在沿途各个路由器中保留，存在可扩展性问题。IB/EB NAC在业务流路径两端执行接纳判决，实现了核心无状态，但可能会因网络中间链路失效而引起拥塞。BBB NAC在输入端执行判决，不要网络内部状态，但使用虚拟通道进行资源预留，网络节点额外开销过多。

基于业务识别的流感知策略利用协议上层隐性的连接建立过程执行业务接入判决，而公平调度算法本身的隐性测量功能可获取本地链路实时状态，结合路由广播信息中的陈旧路径状态信息，可应用证据理论[8]推理出网络路径状态的准实时状态值。以此估计的准实时状态作为网络接纳控制的判决条件，可以提高判决结果的准确性。

3 基于证据理论的网络路径态势估计

对于网络路径态势估计来说，命题即是网络可能呈现的不同承载状态。设网络路径态势集为{轻载、重载、过载}3种假设，而本地状态指标和陈旧路径状态指标对网络态势的估计作为证据体。因此，路径态势估计的实质就是在当前态势分类的条件下，将本地状态指标和陈旧路径状态指标的不同估计值合成一个证据体，完成对态势集中样本进行识别的过程。

3.1 证据体及其基本概率赋值

在流感知网络中，本地链路状态指标为优先队列队长和当前链路公平速率，分别描述优先业务和弹性业务的承载状态，而路由算法中的路径参量则描述了网络路径的陈旧状态。因此，本地链路状态和陈旧路径状态指标合成后的基本概率赋值描述了网络路径态势的估计，则可将最大置信度命题作为备选命题。可见，由两类状态指标推理得到对不同态势类的基本概率赋值是路径态势估计的关键。

鉴于多业务区分过程中的模糊性，模糊流感知[9]将业务区分界值模糊化为边界区间来处理此模糊性，以适应网络状态的动态变化。设链路状态指标对链路态势的估计为{O,H,L}，分别表示链路处于{过载，重载，轻载}3种态势类，则状态指标的模糊子集可以使用三角形和梯形实现对事件状态的量化，如图1所示。

图1 链路状态指标的模糊子集

设优先队列队长为Q，拥塞门限为QT，队列转发门限为QFT，最大缓存容限为B，若取队长Q=x,QT=xL, QFT=xU，并取x上限为B，则使用队长模糊子集的隶属函数对队列指标的基本概率赋值函数mQ={q3, q2, q1}进行量化，如式(1)～式(3)，其中qi,i=3,2,1分别表示链路当前{O, H, L}3种状态的基本概率赋值，且xM=(xU-xL)/2。

同样，设节点下游链路当前公平速率为RF，拥塞门限为RT，拥塞告警门限为RCT，链路速率为C，若取变量RF=x, RT=xL, RCT=xU，并取x上限为C，则隶属函数(1)～(3)能够对公平速率指标的基本概率赋值函数mR={R1, R2, R3}进行量化，其中Ri, i=1, 2,3分别表示链路当前{O, H, L}3种承载状态的基本概率赋值。于是，本地链路状态的基本概率赋值函数 mL由优先队列指标和公平速率指标的正交和得到如下：

多业务网络中，时延敏感实时业务通常选择最短路径优先策略以减少路径传输时延，而路径有效带宽最大化作为第二路由规则，即使用最宽最短路由算法(W-S, widest-shortest path algorithm)。由于所有选择路径均为最短路径，传输路径上的有效带宽反映了实时业务的最优路径拥塞状态，故可用有效带宽描述实时业务的路径拥塞度。路径有效带宽定义为传输路径上所有链路有效带宽的最小值。若链路容量为C，链路进程承载的优先业务流和弹性流分别为(Ns, Ne)，优先业务流平均恒定速率为Rs，则有效带宽r为链路弹性流的平均有效速率：

对响应时间敏感的弹性流希望选择有效带宽最大路径传输数据，而路由跳数最短作为次要条件，即使用最短最宽路由算法(S-W, shortest-widest path algorithm)，则路由跳数差Δh可以描述弹性流的路径拥塞度，其中Δh为流当前选择路径的路由跳数与最短路径路由跳数之差，路由跳数可由路由算法本身测量获得。根据不同类型业务的路径拥塞指标，定义如下路径效用函数(utility function)[10]对网络的路径拥塞状态进行描述。

其中，G∈(0,∞)为比例增益常数，默认为1，r为路径P的有效带宽。效用函数U随有效带宽r递增而增大，随路由跳数差Δh增加而线性递减，当G=0时，效用函数退化为弹性流的有效带宽最大路由算法(widest path algorithm)的选路标准；当G=∞时，效用函数又变为优先业务流的最短路径路由算法(minimum-hop path algorithm)的选路标准。因此，效用函数能够反映多业务网络传输路径的拥塞状态。

由效用函数得到的路径状态是过时的，仅作为网络路径态势估计的路径状态基本概率赋值函数的输入值。当r≤RT时，路径处于拥塞状态，路由算法选择最短路径有效，即Δh=0，效用函数仅是有效带宽的对数值，定义为效用函数的拥塞门限UT=lnRT。当r∈(RT, RCT]时，路径处于重载状态，为减小网络阻塞率，弹性流尽量选择最短路径传送分组，定义为效用函数的拥塞告警门限UCT=lnRCT。当r＞RCT时，路径处于轻载，弹性流将优先选择S-W路由算法，路径P的效用函数为UP=lnr-Δh, G=1。若路径指标对路径态势的估计为{O, H, L}3种态势，则路径指标的模糊子集可量化实现为图2所示，其中UM=(UCT-UT)/2。

图2 效用函数的模糊子集

设路径态势估计的基本概率赋值函数为mP={A1, A2, A3}，其中Ai, i=1, 2, 3分别表示链路当前{O, H, L}3种态势的基本概率赋值{μO(u), μH(u),μL(u)}，由模糊子集可分别量化为

3.2 网络路径态势估计

网络路径态势估计结果的正确性依赖于本地链路状态和路径状态指标的周期性测量与更新，在测量本地链路状态指标的基础上，量化得到链路状态的基本概率赋值 mL和路径效用函数的基本概率赋值mP后，根据图 3推理过程对网络路径态势进行估计。

图3 路径态势估计中的信息融合

设路径态势估计的辨识框架共有 3个命题，本地L表示本地链路状态在t时刻对不同命题的判断结果集。路径P表示陈旧路径状态在t时刻对不同命题的判断结果集，mL(Ai)/mP(Ai), i=1,2,3为对命题Ai的基本概率赋值，m(Ai)为经过Dempster合成后得到网络路径的新基本概率赋值m(Ai), i=1,2,3，且有：

路径状态的新基本概率赋值 m(Ai)描述了根据最新测量数据推理得到的网络路径不同态势的置信度（概率值）。路径状态的更新则随路径指标的周期性测量而由预计算模块进行更新，但在同一测量周期内路径态势集中样本保持不变。

对于估计的网络路径态势集及相应态势样本的概率赋值，设集合中不确定性概率 ()mΘ大于门限ε2，若某态势A1具有最大概率赋值，且与其他态势样本的概率赋值差大于门限ε1，则取态势A1作为传输路径的准实时态势值。即：

若态势集样本A1同时满足下列不等式：

其中，ε1、ε2是预先设定的门限值。则路径态势计算模块判决输出 A1为路径下一周期准实时路径承载状态。

4 基于路径估计网络接纳控制算法

基于估计的当前路径状态，算法执行两级接纳判决。首先进行粗粒度的路径接纳判决，并根据其判决结果决定是否进行本地链路接纳判决。

4.1 路径接纳判决

当估计路径态势为过载时，节点直接丢弃业务请求分组而无需进行二次判决；当路径态势为重载时，为降低优先业务的阻塞率并保证其低时延性能，本地网络节点直接丢弃感知为弹性流的业务请求分组，仅对优先业务流执行本地链路判决。当路径态势为轻载时，所有业务流均被无区分接入，无需进行二次接纳判决，仅由调度机制对接入的业务流进行区分转发。

其中，Reject为对请求业务流的拒绝判决，Accept为接纳请求业务流，而LD则是对请求业务流的本地链路接纳判决(LD, local decision)，仅在路径重载时对具有优先权的优先业务进行区分控制。

4.2 链路接纳判决

本地链路接纳判决仅在优先队列小于其拥塞门限，且网络路径重载时执行。当优先业务重载而弹性业务轻载时，优先业务的接入必然增大优先队列长度，则以与队长相关的概率拒绝优先业务的接入。设拒绝概率为P1，且定义为

其中，队长敏感指数k1描述了拒绝概率P1对队长Q变化状态的敏感程度。若k1较小，则增加队长会显著地增大拒绝概率，能有效抑制网络路径过载发生。同时，冗余了更多的网络资源，将降低路径资源利用率，因此，k1取值可根据实际应用要求进行设置。

当优先业务轻载而弹性业务重载时，接入优先业务会降低链路公平速率，恶化弹性流的基本吞吐量，因此，以与链路公平速率相关概率接纳优先业务。设接纳概率为P2，且：

其中，速率敏感指数 k2描述了接纳概率 P2对链路公平速率R变化的敏感程度。若k2较大，则接纳概率能较快地响应链路公平速率的变化，有益于链路效率的提高。但是P2频繁地改变增大了链路流量的动态性。

当所有类型业务均处于重载时，上述两类影响均存在，因此，接入概率为

则在网络路径重载时，可得网络接纳控制二次本地接纳判决集为

与IB/EB NAC不同，基于路径估计的网络接纳控制(PA NAC, path assessment based network admission control)虽然仅在网络输入端执行本地接纳判决，但在路径判决时考虑了构成网络路径的所有链路状态，能以高概率避免网络后端链路瓶颈遗漏问题。与BBB NAC不同，PA NAC虽然需要路径状态信息，但不需要网络内部链路参与，通过增加边缘节点的预计算来实现网络核心状态无关。

5 算法复杂度分析

设网络输入输出端节点数分别为 D、E，网络中链路总数为N，则由IB/EB NAC算法原理可知，其分别在业务接入端和输出端各执行一次接纳判决，故接纳判决过程中需要两次计算条件表达式是否满足要求。针对每个判决条件，节点需要计算链路资源预算。对于每一个可能的路径，需要独立计算各节点及相应链路的预算资源，因此总共计算量为(D+E)+N，而且预算资源的计算量会随源/宿端的增加而增加。

PA NAC仅在业务输入端进行接纳判决，对于被拒绝的业务流仅作出一次判决，因此为每个业务流作出判决的平均次数小于两次。在一个允许接入的完整接纳判决过程中，算法先后需要进行两次搜索查表工作，而两次独立查表复杂度均为O(1)，故一次判决过程的计算复杂度为O(1)，但计算量不会随端点增加而增加。

PA NAC计算量在两级判决过程中均有不同程度地减少，简化了接纳控制模块的复杂度。系统所增加的路径态势推理和本地链路状态测量的计算由额外的模块独立进行，这正是应用并行计算减小网络操作机制计算量的目的。

6 仿真计算

网络接纳控制机制在网络重载时保护承载业务请求性能限，防止网络过载的发生。在网络轻载时，链路冗余本身能够满足接入业务端到端请求的性能限，执行严格的接纳判决导致业务性能的提高非常有限，因此仿真仅在重载条件下进行。

网络模型使用简单的多跳网络仿真拓扑，如图4所示，路径链路参数如图4所示。为简化计算，取敏感指数 k1=k2=1，仿真比较了 PA NAC与IB/EBNAC算法统计结果。PA NAC仅在源端网络节点上进行判决，而IB/EBNAC则同时在源端和宿端 2个节点上使用各自的判决条件不等式进行决策，其网络路径资源的占用统计使用 Kaufman-Roberts algorithm (KRA)计算[11]。网络态势估计预计算和本地链路状态测量分别由额外模块辅助预计算，而预计算得到的状态变量则由节点负责维护更新，其计算周期、状态参数及路径态势估计更新周期与公平调度算法的测量周期同步，优先业务和弹性业务路由分别使用WSP和SWP算法[12]。

图4 多跳网络仿真拓扑

仿真统计了低速语音流的阻塞率指标和链路效率曲线，分别如图5和图6所示。语音流阻塞率曲线显示 PA NAC在重载时的阻塞率一直小于IB/EB NAC算法，因为在路径态势估计下的一次接纳判决仅仅允许速率较低的优先业务流接入网络，进行了多业务的接入区分。而IB/EB NAC算法同等对待所有请求业务流，但这并不能实质性地增加弹性流的吞吐量，因为链路重载时进一步接纳高速业务会恶化网络路径状态，增大分组丢失率，造成大量分组重传，浪费了网络资源。

图5 64kbit/s语音流阻塞率

图6 链路效率曲线

图6中2种算法的链路效率证明了上述结论，链路效率定义为统计时间内接收端完成流传输字节数与源端发送字节数之比的均值。在路径链路重载时，IB/EBNAC算法链路效率低下，最大约为26%左右，而PA NAC明显具有较高的链路效率，最大可达 67%左右，因为它不仅对多业务进行了接入区分，还进行了转发区分，对网络资源进行了相对严格的管理。当然，IB/EBNAC算法的资源利用率在3种BNAC算法中本身也是最低的，但其他算法付出的代价是要进行更多的判决决策，需要节点具备高性能计算能力和高效的资源分配策略。其中 LBNAC算法计算复杂度会随源/宿端节点增多呈非线性增大，从而不能应用于实际的大规模网络管理和控制。BBBNAC算法则增大了网络路径状态信息的维护和更新开销，路径状态信息的传播时延和链路效率将随网络节点的增多而恶化。相反，当网络节点增多时，PA NAC仅仅增加了路径态势估计的预计算量和节点管理路径状态的缓存开销，但在二级本地接纳判决时，它简化了判决计算复杂度。

7 结束语

为保障不同业务差异化的端到端性能，平滑和抑制潜在的随机拥塞，需要网络接纳控制实现业务接入区分。而待传输路径的实时状态信息决定了网络接纳控制的有效性，通过边缘节点智能计算得到的路径态势估计有效减少了网络核心状态的复杂度。在估计的路径状态下执行一级网络接纳判决，以判断网络是否需要进行二级接纳判决。二级判决仅在链路重载时执行，由本地链路状态实现业务区分接入。PA NAC算法通过分解网络接纳判决过程实现计算简化和网络核心状态无关，克服了BNAC计算繁杂和应用可扩展性问题，仿真显示其更适合共同承载不同速率分布的多业务网络。

[1] WRIGHT S. Admission control in multi-service IP networks: a tutorial[J]. IEEE Communications Surveys & Tutorials, 2007, 9(2):72-87.

[2] CHO I K, OKAMURA K. A centralized resource and admission control scheme for NGN core networks[A]. International Conference on Information Networking[C]. Chiang Mai, Thailand, 2009. 1 - 5.

[3] MARTIN R, MENTH M, CHARZINSKI J. Comparison of border-to-border budget based network admission control and capacity overprovisioning[A]. The 4th International IFIP-TC6 Networking Conference[C]. Waterloo, Canada, 2005. 1056-1068.

[4] MENTH M, KOPF S, MILBRANDT J. A performance evaluation framework for network admission control methods[A]. IEEE/IFIP Network Operations and Management Symposium[C]. Seoul, Korea,2004. 307- 320.

[5] 徐恪, 吴建平, 徐明伟. 高等计算机网络——体系结构、协议机制、算法设计与路由器技术[M]. 北京: 机械工业出版社, 2005.175-235.XU K, WU J P, XU M W. Advanced Computer Network-System Ar-chitecture, Protocol, Algorithm and Router Technology[M]. Beijing:Machine Industry Press, 2005. 175-235.

[6] CHENG G, ANSARI N. Minimizing the impact of stale link state information on QoS routing[A]. IEEE Global Telecommunications Conference[C]. Missouri, USA, 2005.5 - 9.

[7] MENTH M. Efficient Admission Control and Routing for Resilient Communication Networks[D]. University Wuerzburg, 2004.

[8] 贲可荣, 张彦铎. 人工智能[M]. 北京: 清华大学出版社, 2006.142-181.BEN K R, ZHANG Y D. Artificial Intelligence[M]. Beijing: Tsinghua University Press, 2006. 142 - 181.

[9] 邱恭安, 张顺颐, 胡隽. 基于模糊流感知的动态优先公平调度算法[J]. 电子与信息学报, 2009, 31(2): 467-471.QIU G A, ZHANG S Y, HU J. Fuzzy flow awareness based dynamical priority fair scheduling algorithm[J]. Journal of Electronics & Information Technology, 2009, 31(2): 467-471.

[10] OUESLATI S, ROBERTS J. A new direction for quality of service:flow-aware networking[A]. Next Generation Internet Networks[C].Roma, Italy, 2005. 226-232.

[11] TOELLE D, KNORR R. Performance evaluation of potential and management based network admission control methods[A]. IEEE International Conference on Communications[C]. Istanbul, Turkey, 2006.754-759.

[12] HORNG M F, KUO Y H. An effective approach to adaptive bandwidth allocation with QoS enhanced on IP networks[A]. The 3rd International Conference on Ubiquitous Information Management and Communication[C]. Suwon, South Korea, 2009. 260-264.