- 1 -
一种光流交换网络中的流量疏导算法#
白云1，郁小松1，于一鸣1，赵永利1，张杰1，桂柯易2**
（1. 北京邮电大学信息光子学与光通信研究院，北京 100876；
2. 北京邮电大学，北京 100876） 5
摘要：随着 DWDM 在核心节点的使用，网络的灵活性，可靠性都有了很好的保障，带宽容
量也已经有了很大程度的提升。但是，这些年移动互联网飞速发展，各种新型业务层出不穷，
对于带宽带宽和大容量业务的传输需求不断增加，给现有的网络带来了前所未有的压力。光
流交换网络可以更好的适应这些业务。如何能够发挥光流交换网络高速处理的特点，从而高
效的利用频谱资源，渐渐的引起人们的关注。这篇文章介绍了一种基于光流交换网络的流量10
疏导算法（Optical Grooming with Priority，OG-P），在一定程度上可以更加充分的利用现有
资源，减少网络的阻塞率。仿真实验的结果证明这种算法可以实现上述目的，提升了网络性
能。
关键词：通信与信息系统；灵活栅格；光流交换网络；流量疏导
中图分类号： 15
An Algorithm of Optical Gromming in Optical Flow
Switching Network
Bai Yun1, Yu Xiaosong1, Yu Yiming1, Zhao Yongli1, Zhang Jie1, Gui Keyi2
(1. State Key Laboratory of Information Photonics and Optical Communications, Beijing 20
University of Posts and Telecommunications, Beijing 100876;
2. Beijing University of Posts and Telecommunications, Beijing 100876)
Abstract: With the application of DWDM in core nodes, bandwidth capacity has increased in a
large degree, while the flexibility and the reliability of networks have been guaranteed well. But,
in recent years, the challenges, such as rapid development of mobile Internet, emergence of all 25
kinds of new business and increasing demand for bandwidth and large capacity business
transmission, have brought the unprecedented pressure to the existing network. How to make full
use of high speed processing in optical flow switching network, in order to increase the spectrum
resources utilization rate, and implement traffic grooming, begins to draw more and more people's
attention. This paper introduces a kind of algorithm based on Optical Grooming with Priority, in 30
order to fully utilize the existing resources and reduce network blocking rates.
Keywords: communication system; flexible grid; optical switching network; optical grooming
0 引言
电路的分组交换在过去的时期内大大提高了资源的有效利用，并且电处理器件的技术也35
一直在进步。但是，这并不能满足用户日益增长的对大数据量业务的需求。持续增长的业务
需求需要对光纤带宽有更高的利用率，因此，基于灵活栅格光网络的 OFDM 近几年得到越
来越多关注[1,2]。在这样的网络中，DWDM 的刚性网格被划分为更加细小的频谱段，即通常
所说的频谱切片（slot）。根据数据的传输速率和传输距离需求，把这些 slot 进行合理分配，
可以实现更高的频谱利用率。 40
在灵活栅格光网络中，路由和频谱分配（RSA）问题开始凸显。原因有以下几点：首先，
网络中不同的连接请求需要不同的路径，占用不同数量的 slot；其次，即使是同样的请求，
随着时间的不同，所占用的 slot 数也会有显著的区别；再次，分配 slot 时不仅仅要遵循频谱
- 2 -
连续性约束，还需要满足频谱一致性的约束。在经历了 RSA 过程之后，整个可用的频谱资
源就剩下了很多细小的，不连续的频谱碎片，这些不连续的频谱碎片在之后的资源分配中就45
会因为不能被利用而浪费。另外，因为业务在到达和离去的时候，也会导致碎片增加[3,4]。
这些碎片导致频谱状态相当复杂，也增加了 RSA 的难度。为了解决以上这些问题，同时对
频谱资源的利用进行优化，我们基于光流交换的网络，提出了一种新的流量疏导的算法。
1 光流交换网络
当电处理的速度达到理论上的极限时，才可以达到光网络系统的速度。因此，传统的网50
络容量将被电子层的瓶颈所约束。在目前的网络中，一个典型的网络会包括三至四层不同的
电子复用和交换层，众多的层次降低了带宽的利用率，增加了时延，不利于 QoS 的保证。
并且，由于各层之间的独立性，某些网络业务的复用无法实现。
光流交换可以减少网络交换的复杂度。数据单元以流的方式在一段时间内持续的穿过网
络，沿着相同的波长信道和网络路径。这一点是有别于传统的电分组交换网络。在电分组交55
换中，处理的内容都作为数据单元的组成部分，这些数据单元各自独立的在网络中进行路由
和交换。与这种设计不同的地方在于，光流交换网络所有的数据队列在终端用户处排队，网
络的核心节点不再需要缓存功能。光流交换的流量在核心节点可以高效的聚合，对于静态拓
扑在大时间尺度上的变动也可以有充分的应对。因为在光流交换中，只有相关的接入网络和
出口网络才会进行通信，所以管理和控制的复杂度也大大降低了[1]。 60
光流交换网络中，会存在以下问题：
（1）资源规划（Resource Planning，RP）。RP 主要关注静态规划问题。一个需求矩
阵，给出了所有请求带宽，这时频谱资源应该规划一个最优的分配方案。通常，这样的线下
问题可以通过整数线性规划（ Integer Linear Programming，ILP）来解决。由于 ILP 规划不
能在短时间解决问题，所以，对于一个大型的网络来说效率就相对低下。因此，应该提出有65
效地频谱规划启发式算法。
（2）带宽分配（Bandwidth Assignment，BA）。带宽分配的目的是为了解决动态 RSA
问题。当请求到达并且必须实时处理，我们会使用一些带宽分配算法来为这些请求建立灵活
的光路。带宽分配算法应该满足一下条件：(a)根据请求速率弹性的分配合适的 slot 数；(b)
依据传输的距离，选择适当的调制格式；(c)有认知性，比如，物理损伤感知，客户服务感70
知。
（3）频谱重构 (Spectrum Defragmentation，SD) 。随着光路动态的建立和拆除，频谱
碎片越来越多，增加了路由和频谱分配的复杂性。为了减少碎片，在干扰业务和影响 QoS
（如时延，带宽，比特率等）最小的情况下，应该对用于连接的频谱进行重新分配。
（4）排队策略 (Queueing Policy，QP)。由于光流交换网络的特殊性，业务请求会在源75
节点排队，进行路由计算和资源规划。如何对这些排队业务进行调度，使其能够高效的利用
网络资源，也是有待解决的问题。
这篇文章主要针对在带宽分配过程中的流量疏导问题，基于光流交换网络业务排队的特
性，提出了一种新的疏导算法。
- 3 -
2 流量疏导算法 80
算法模型
由于波长选择器的缺陷，为了使相邻的光路上的业务相互之间没有干扰，需要在业务所
占频谱的两侧引入保护带宽（Guard Band）。基于灵活栅格光网络中 OFDM 信号的正交特
性，从同一个源节点产生的业务在光域能够被合并在一起，之间就可以不再需要有保护带宽
的存在[5]，这样，可以节省很多的频谱资源。另外，因为疏导的光路使用一段连续的频谱资85
源，也会减少频谱碎片化产生。在普通的网络中，如图 1 所示，没有疏导的情况下，业务请
求在 t1，t2，t3时刻到达，然后根据业务到达的前后，依照顺序进行 RSA 过程。每个业务在
经过了各自的持续时间（T1，T2，T3）的持续时间后，又在 t4，t5，t6 时刻离开网络。不可
避免的，在动态的网络中会有大量的频谱碎片产生。
timet1 t2 t3 t4 t5 t6
10G 20G 10G
T1 T3
T2
t
No Grooming
t0
90
图 1 正常情况对业务的处理
依照这样的情形，业务被疏导的可能性相对来说比较小，因为在动态的网络中，请求是
一个接一个到达并处理的。如果这些请求同时进入网络，疏导的可能性就会增加。为了进行
流量疏导，我们假设所有的业务请求能够容忍一定的等待时间，它们的 QoS 的优先级相同。95
如图 2 所示，首先，把在(t0，t]时间段内到达的业务存储在缓存内，然后根据一定的策略合
并，在 t 时刻进行处理。这里，t 叫做疏导时刻(Grooming Time，GT)，t-t0的值叫做疏导间
隔(Grooming Interval，GI)。
timet1 t2 t3 t8t7 t9
10G+20G+10G
T1
T3
T2
t
Grooming
t0
图 2 流量疏导的原理模型 100
假设业务在(t0，t]时间的到达服从业务量为 λ 的泊松分布，那么在 GI 时间段的业务可
以被看做是批量到达的。它们的到达时间服从确定分布，持续时间仍然服从指数分布。请求
满足下面的关系：
!
)]([])]()([ 0
)(
0
0
k
ttektNtNP
ktt −==−
−− λλ
k=0,1…, 105
这里， ])]()([ ktNtNP ij =− 表示当业务数为 k 时的概率值。
- 4 -
中国科技论文在线
算法模型
本文提出了加入了优先级的光流量疏导(Optical Grooming with Priority,OG-P)算法。根据
光流交换网络业务排队的特点，让业务到达后等待一段时间，再根据一定的策略把这些业务
进行分类合并，之后再统一进行处理。在 OG-P 算法中，ri表示第 i 个业务请求，s 表示业务110
源节点，p 表示业务路径，L 表示业务队列，RS,P 表示合并相同源节点和有共同路径的业务
序列，具体的算法步骤如下：
Step 1：当业务请求 ris在（0，GI）时间段内到达后不立刻进行 RSA，先用 D 算法进行
路由计算，得到该业务的最短路径后保存，将业务更新为 ris,p，然后按照到达的时间顺序把
业务存入缓存中的业务队列 L。 115
Setp 2：在 GI 时刻，对缓存中的业务按照 s 和 p 进行分类，把源节点相同和有共同路
径的业务合并入业务序列 Rs,p。
Setp 3：对 Rs,p中的业务进行优先级划分。先按照业务路径 p 对业务排序，路径越短的
业务优先级越高。然后，对于跳数相同的业务比较其所需要的频谱资源，对资源需求越少的
业务优先级越高。进行完优先级划分以后，在缓存队列中找出有相同源节点和有相同路径的120
若干个业务{rms,p，rns,p…}，把这些业务合并为 Rs,p。
Step 4：只需对 Rs,p的频谱两侧分配保护带宽，而在 Rs,p内部的{rms,p，rns,p…}不再需要，
然后对 Rs,p进行资源分配。这样，对相同源节点和有相同路径的业务合并可以减少保护带宽
的使用，减少资源占用。加入了优先级之后，短距离，窄带宽的业务可以优先进行资源分配，
有利于保证更多的业务传输，从而降低网络的阻塞率。 125
具体的流程图如图 3 所示。
图 3 OG-P 算法的流程图
3 仿真结果和讨论 130
我们的仿真使用 NSF 拓扑，每条双向链路假设有 128 个 slot，每个 slot 是 。连
接的请求服从泊松分布，每个连接的原和宿平均的分布在网络中。请求的带宽满足 2 到 10
个 slot 的均匀分布。为了验证加入优先级流量疏导算法的性能，我们完成了没有流量疏导(No
- 5 -
中国科技论文在线
Optical Grooming)，光疏导(Optical Grooming,OG)和加入了优先级的光疏导(Optical Grooming
with Priority,OG-P)三种情形的仿真。 135
图 4 显示了当疏导时间(GI)为 1 个单位单元时间，保护带宽在不同的负载(50 和 60 爱尔
朗)增长时，阻塞率的变化。可以明显的看出，三种算法的阻塞率随着保护带宽的增长而增
长，同时，没有疏导阻塞率最高，有疏导但是没有优先级的阻塞率次之，有疏导而且有优先
级的阻塞率最低。并且业务量如何，有一个共同的规律，就是随着保护带宽的增加，OG 和
OG-P 相对于不疏导所降低阻塞率的程度就越大，这是因为保护带宽越大，节省的 slot 也随140
之增加，阻塞率的减少也更加显著（当保护带宽为 6 时，OG-P 达到了 22%）。
1 2 3 4 5 6
60Erlang，No OG
60Erlang，OG
60Erlang，OG‐P
50Erlang，No OG
50Erlang，OG‐P
50Erlang，OG‐P
保护带宽(Slot)
阻塞率
图 4，阻塞率和保护带宽的关系
图 5 描述了随着业务量的变化，三种策略阻塞率的变化情况。这里，我们选定保护带宽145
固定为 4 个 slot，疏导时间为 1 个单位时间。可以看出随着业务量的增加，三种算法的阻塞
率都上升，但是 OG 和 OG-P 算法的阻塞率降低量也增大，并且 OG-P 算法明显的优于其他
两种算法，显著减少了阻塞率。这是因为在大负载的情形下，采用优先级，可以提高对频谱
资源的利用率。
40 45 50 55 60 65
No OG OG OG‐P
业务量(Erlang)
阻塞率
150
图 5，阻塞率和业务量的关系
- 6 -
中国科技论文在线
图 6 显示当保护带宽固定为 4 个 slot，随着疏导时间在不同的负载（50 和 60 爱尔朗）
增长时，阻塞率的变化。没有流量疏导的情形下，阻塞率保持一个固定值，其它两种算法的
结果则是波动的。这是因为当疏导时间相对来说比较小的时候，被放在一起疏导的请求数的
增长是同疏导时间相关的，可以节省的 slot 数也是这样。但是，当疏导时间变得很大时，越155
来越多的请求被疏导在一起，频谱必须在在同一时间对这么多请求分配资源。这会导致资源
约束的情况，使阻塞率增加。以 60 爱尔朗时的阻塞率为例，当疏导时间在（0,）变化时，
OG-P 算法是优于没有疏导的，并且在 单位时间时达到最优（减少了 27%）。这意味着
如果疏导时间设定一个合适的值，OG-P 算法可以获得最佳的效果。从图 6 也可以看出优化
的疏导时间的值也是随着负载的增长而降低。 160
60Erlang，No OG
60Erlang，OG
60Erlang，OG‐P
50Erlang，No OG
50Erlang，OG
50Erlang，OG‐P
疏导间隔（unit time）
阻塞率
图 6，阻塞率和疏导间隔的关系
4 结论
在这篇论文里，我们提出了在灵活栅格的光流交换网络中能够优化频谱资源利用一种流
量疏导算法。这种算法利用了光流交换网络业务排队的特性，对有相同源节点和路径的业务165
进行合并疏导。仿真的结果显示，进行流量疏导的网络优于没有流量疏导的网络，同时，在
对不同的业务进行优先级划分之后，优化的效果更进了一步，网络的性能得到进一步提升。
并且，当参数设为合适的值时，这种算法对于阻塞率的降低能够达到理想的效果。
[参考文献] (References) 170
[1] Ken-ichi Sato. Recent Developments in and Challenges of Elastic Optical Path Networking[A]. ECOC2011[C]
[2] M. Jinno, et -Efficient and Scalable Elastic Optical Path Network: Architecture, Benefits, and
Enabling Technologies[j]. IEEE Comm. Mag 47, 66-73(2009)
[3] K. Sone, et . Demonstration of Hitless Spectrum Defragmentation using Real-time Coherent Receivers
in Flexible Grid Optical Networks[A]. ECOC2012[C] 175
[4] X. Yu, et al. Spectrum Compactness based Defragmentation in Flexible Bandwidth Optical Networks[A].
OFC2012[C]
[5] G. Zhang, et al. Optical Grooming in OFDM-Based Elastic Optical Networks[A]. OFC2012[C]
