基于MPLmS的轮转循环调度算法

1 目前的IP QoS (Quality of Service, 服务质量) 状况

Internet的最初设计目的是进行高效的数据传输, 因此采用的是“尽力而为”的转发机制。主要思想是当用户提出服务请求时, 网络不会拒绝用户的服务请求, 不过服务的质量要根据当时网络的状况而定, 数据的丢失率、出错率、时延以及抖动等是无法保证的。这种机制并不适合于实时多媒体业务的传输[1]。因为在网络发生拥塞时, 可能会导致数据丢失, 或是出现较大的时间延迟以及抖动, 所提供的服务会随着网络的拥塞情况而发生变化。这是实时多媒体业务所无法接受的[2]。这些业务通常需要网络能够提供一定的QoS保证, 如比较小的时间延迟。同时IP网络已经从单纯传输数据的网络演变到可以传输数据、语音、图形图像、视频等多媒体信息的网络。要传输这些多媒体信息, IP的QoS问题就成为IP网络进一步发展所必须解决的关键问题[3]。

2 MPLmS实现QoS的体系结构

MPLmS是一个综合了第二层交换和第三层路由技术的特点, 其方法是直接采用第一层 (光波长级) 的交换来处理第三层的IP路由转发, 将标签与WDM波长信道关联起来, 其分立波长或光纤信道类似于标签, 并通过MPLmS信令来指配光信道。MPLmS技术的成功之处在于它在无连接的IP网络中引入了面向连接的机制, 采用短的、定长度的“标签”, 利用标签交换机制, 而不是分析IP包头再转发的机制来完成分组转发[4]。

MPLmS的标签有32位组成, 是一个在上游路由器的发送端口和下游路由器的接收端口之间有意义的标识符。标签的封装是在链路层头和网络传输层头之间。在LER (Label Edge Router, 标记边缘路由器) , MPLmS使用FEC将输入的数据流映射到一条LSP上。FEC就是一组有相同处理过程的分组, 这就意味着所有FEC相同的分组可以映射到同一个标签中, 但属于同一个FEC的分组可以映射到不同的标签。在网络内部一个具有MPLmS能力的路由器在转发包时只检查标签, 通过交换标签来实现转发。当分组离开MPLmS时, 分组的标签被去掉继续按照IP包的路由方式到达目的地。

MPLmS实现QoS基本思想是:在边缘路由器, 将具有不同QoS的业务进行分类, 在核心路由器根据不同的类型进行不同的服务。如果QoS的分配融入MPLmS的标签分配过程中, 那么MPLmS的标签就具有QoS能力[5]。MPLmS的QoS实现是由LER和LSR共同完成的。MPLmS QoS的具体实现过程如图1所示。

3 算法思想

流量工程是实现网络中QoS服务的一个重要方法, 其核心是流量控制和资源管理, 其性能指针分为流量导向和资源导向两个方面。流量导向的性能决定网络对流量的处理和服务能力, 主要目标包括最小分组丢失率, 最小传输延迟, 最大吞吐量, 服务水平约定等;资源导向针对的是优化资源使用, 目标是合理使用资源和优化资源配置, 尤其希望避免网络的一部分超负荷使用而另一分未充分使用。流量工程是一个反复进行网络规划和网络优化的过程, 从而优化资源使用效率和网络性能。

通常网络延迟=分组处理延迟+排队延迟+传输延迟+传播延迟。前两个延迟具有很大的不确定性, 对于后两个延迟, 一旦给定了端口和传输介质, 就成了确定因素。在不确定因素中, 排队延迟是分组交换网中的主要延迟, 它指的是数据包在传输路径上每交换一次所引起的缓冲延迟的集合。若分组交换临时过载, 第一个数据包的目的输出端口上可能有许多分组排队。队列中位于数据包前的每个分组会产生一个等于传送延迟的附加延迟。在先进先出队列机制的交换中, 新到达的分组的排队延迟等于已在该输出端口上排队的所有分组传送延迟的总和。

4 排队模型分析

当业务流到达路由器时如图2所示, 首先通过交换结构, 根据业务流的优先级把业务流放到具有相同优先级别的队列中排队, 调度器根据一定的算法, 把等待队列中的分组输出去。以一定的规则在等待服务服务的分组中选择服务对象的过程就是分组调度, 这是一种至关重要的支持QoS的技术。

在路由器中, 到达中间节点的分组都要被暂存和处理, 以确定通往下一节点的恰当的传输链路。假设在一个设计比较好的网络中很少发生阻塞或者数据包很少丢失, 那么这个网络就可以近似地认为具有无限大缓冲队列的延迟系统, 因此队列延迟模型可以用M/M/1队列来模拟。

设队列的到达过程为参数是λ的泊松到达过程, 则在t秒间隔内有k次到达的概率可表示为:Pk (t) = (λt) ke-λtk!

由此可以推得泊松过程的均值和方差:

令E[t]为在时间间隔长度t内到达的均值, 则:

同理可得方差σn2为:

由此可得顾客到达的概率密度为:α (t) =λe-λt。

这说明顾客平均到达率为λ服从泊松分布, 平均服务服从指数分布服务。

用表示业务的强度, 也就是系统负荷与系统容量之比。从而推导出下面的公式:

在排队系统中已知到达率和平均等待时间E (W) 的情况下平均排队长度E (X) 由Little公式给出:E (X) =E (W) 所以有:

上面E (X) 表示排队中的平均排队分组数, 包括正在服务的一个。上式展示了已经阐述了的排队现象。当系统上的负荷相当轻的时候, 即当ρ<<1的时候, 正好是服务时间, 因此用在排队的时间很少, 时延几乎全部由服务时间和传输时间引起。

通常通常情况下, 一个好的调度算法应能够合理分配链路带宽, 既要优先考虑高优先级分组的调度, 又要防止低优先的分组因长期得不到调度而形成超时被丢弃, 这就是公平性。最重要的还要保证良好的时延性能。

轮转 (Round Robin) 调度算法, 就是调度器循环地对每个队列进行轮流服务, 不需进行时标比较, 它的操作简单, 也能够实现公平的目的。它的算法描述如下。

单服务系统, 服务速率为µ0, 该系统有n类顾客, 第i (i=1, 2, 3…, n) 类顾客按照过程Ai到达系统, 进入队列Qi, 第i类顾客的权为λi, 表示它能够获得的系统服务的份额。服务员以周期c轮转循环为各类顾客服务。在每个服务同期中, Qi队列获得的服务时间为cλi。当到达Qi队列的服务时间时, 服务员按照系统规定的次序 (如:FIFO) 中断Qi-1对队列的服务, 此时有三种情况:

(1) Qi>0, 服务员为第i类顾客服务, 直到队列为空转入 (2) 或者服务时间到转入 (3) 。

(2) Qi=0, 服务员等待, 直到有第i类顾客到达就转入 (1) 或者服务时间到转入 (3) 。

(3) 服务员中断对Qi队列的服务, 转向Qi+1队列。

5 仿真试验

为了研究改进后的排队性能改善情况, 设计了如下实验。

链路速率为2Mbit/s共有10个业务流, 到达速率为2Mbit/s, 分组长度在[0, Lmax]内均匀分布, 仿真时间为30s。表1为统计结果。发送分组的总长度是指业务流在仿真时间内经过链路输出的分组长度的总和, 通过速率等于发送分组总长度除以仿真时间。

从表1中可以看出, 各个业务流的的分组总长度和通过速率几乎与它们的一轮服务量成正比, 这个表明轮转循环调度算法的公平性得到体现。同时可以从表中看出除业务流0以外, 其它所有业务流的最大时延和平均时延都比小, 具有很好的服务质量。业务流0是个最低优先级的业务, 虽然最大时延和平均时延都比较大, 但是它能满足业务流0的服务要求。

摘要：通过引入多协议标签交换 (MPLS) 流量工程控制技术与光交叉连接相结合的一种新型光互联技术——多协议波长标签交换 (MPLmS) , 本文分析了MPLmS网络的基本原理, 为了能在标签的分配中更好地体现QoS, 重点对标签的分配策略进行分析和设计, 提出了一种新的轮转调度算法。

关键词：多协议波长标签交换,调度算法,服务质量

参考文献

[1] Jon Anderson, James S.Manchester.Protocols and Architec-tures for IP optical networking[J].Belllabs Tech.Journal, 1999 (1) :104～124.

[2] Ghani N.On IP-over-WDM integration[J].IEEEComm.Mag, 2000, 38 (3) :72～84.

[3] Uyless Black Optical Network:Third Generation Transport Systems[M].Pearson Education, Inc, 2002:134～180.

[4] Peter Tomsu, Christian Schmutzer:Next Generation Optical Networks:The Convergence of IP Intelligence and Optical Technologies[M].Pearson Education, Inc, 2002:224～250.

[5] 黄建辉, 钱德沛, 王胜灵.结合集成服务、差分服务和MPLS实现端到端QoS保证[J].微电子学与计算机, 2006, 23 (4) :115～121.