可变带宽光网络路由与资源分配研究

基金项目：国家重点基础研究发展(“973”)规划(2010CB328205)；国家自然科学基金(60736002)

    当前，数据业务爆炸式增长，计算机互联网流量迅猛增加，人们对网络带宽和容量的需求持续快速增长。通信网络所承载的业务逐渐从文件传输(FTP)、网页浏览(WWW)等通信方式转变成P2P下载、网络视频点播等传输容量大、带宽需求高的通信方式。为了满足带宽和容量指数增长的需求，各种光复用技术被广泛应用。

    光复用技术主要有波分复用、光时分复用和光码分复用技术。本文主要研究灵活速率光信道数据单元(ODUflex)、波分复用(WDM)和带宽可变光正交频分复用(OFDM)3种光网络，其中ODUflex采用光时分复用技术。ODUflex可根据业务速率进行匹配，使得客户信号正好映射进入载荷区，占用高阶k级光信道数据单元(ODUk)中最少数量的时隙，使剩下的时隙能够承载其他业务，有效提高网络带宽利用率。混合速率WDM光网络采用波分复用技术，相比单速率WDM网络，混合速率WDM网络能提供10G、40G和100G 3种信道速率可供选择，具有一定的灵活性。带宽可变光OFDM网络采用类似于波分复用的多子载波调制技术，将高速数据信号分成多路低速数据信号，并调制到正交子载波上进行并行传输，能够明显提高系统频谱利用率。带宽可变光OFDM子载波数量根据业务请求大小动态调整，具有良好的颗粒度和灵活性。

    伴随着传输流量爆炸式地增长，通信网络系统能耗急剧增长。在不久的将来，通信网络的能耗问题将成为世界范围内亟待解决的问题。巨大的能耗不仅会消耗地球上紧缺的资源，引起环境污染和气候变化，同时会对网络运营商的成本支出产生很大影响。如何更好地规划网络资源，在满足业务需求的情况下降低能耗，是重要的研究课题[1-10]。

1 ODUflex光网络
    光信道数据单元(ODU)是光传送网中装载单元信号的容器。在光传送网中，客户信号首先映射进入ODUk，然后在插入传输头部后在合适的波长上进行传输。传统ODU根据速率不同分为3种：2.5 Gbit/s(k =1)、10 Gbit/s(k =2)、40 Gbit/s(k =3)。为了能够更好地传输各种新老客户信号，引入了ODU0、ODU4以及能够灵活调整带宽的ODUflex，使得复用层次由原先的两层复用结构：ODU1—0DU2—ODU3更新成为4层复用结构：ODU0—ODU1—ODU2—ODU3—ODU4。

    随着网络的高速发展，出现了大量新的客户信号，且其中的大多数都不能直接映射进入现有ODUk，不产生明显的带宽损失，而每次定义一个新的ODU是不实际的。ODUflex能通过调节自身容器的大小，与业务速率进行匹配，仅占用高阶ODUk最少数量的时隙，使剩下的时隙能够承载其他业务，有效提高了带宽利用率。

1.1 路由与速率分配问题
    当业务请求到达时，光传送网需要首先为每条业务分配路由和每条路由上的速率，然后由光传送网的信令负责光通路的建立，达到传送业务的目的。一般可将路由和速率分配问题分成两个阶段：在源节点和目的节点之间分配路由，为每条路由分配速率。

    路由与速率分配问题线性规划的最优化目标：假设系统总能耗由调制能耗和传输能耗两部分组成，总能耗=调制能耗+传输能耗，并假设调制能耗和节点输出速率成正比，传输能耗和节点输出速率和光路长度成正比。

1.2 路由选择策略
    路由选择策略主要有3种：

    (1)固定路由
    固定路由选路策略的思路是对任意节点对间确定一条固定的可用路由，可通过线下计算确定，一般由最短路径算法确定，如Floyd算法和Dijkstra算法。

    当业务达到时，在固定路由上分配速率或频谱，若无可用速率或频谱，则该业务请求被阻塞。这种方案的优点是分配速度快，缺点是阻塞率高，并且因为没有可替代路由，不具备链路故障恢复能力。

    (2)固定备用路由
    固定备用路由选路策略的思路是对任意节点对间确定多条可用路由，其中一条为主路由，其他为备用路由，并按规则进行优先级排序，一般为最短路优先。

    当业务达到时，首先使用主路由，当其阻塞时，再依次使用备用路由。相对于固定路由选择策略，这种方案分配速度同样比较快，相对不太容易阻塞。因为具备可替代路由，具备链路故障恢复能力。

    (3)自适应性路由
    自适应性路由选路策略的思路是根据当前网络状态动态的选择路由，有两种实现方案：

    (a)受限的自适应路由。预先确定一组无序的备选路由，根据业务请求和当前的网络状态选择其中一条最适合的路由。

    (b)非受限的自适应路由。无备选路由，完全动态地选择路由。相对于前两种路由选择策略，这种方案的阻塞率最低，具有链路故障恢复能力，但时间复杂度也大大提高。

1.3 路由与速率分配问题启发式算法
    在启发式算法中首先对业务进行排序，然后按照排序为每条业务请求分配路由和速率。路由分配采用固定备用路由策略。业务排序策略有：按业务流量进行排序、按业务路经进行排序。

    (1)按业务流量进行排序
    按业务流量进行排序通常按业务的流量从大到小进行排序。首先满足流量较大的业务，对其分配路由和网络资源。

    该策略优势在于分配成功率高，开始阶段网络资源较多，适合大流量业务分配；随着业务的分配，网络资源逐渐变少，适合小流量业务分配，整体而言阻塞率较低。

    (2)按业务路经进行排序
    按业务流量进行排序通常按业务最短路路由长度或跳数从大到小进行排序。首先满足路由长度长或跳数多的业务，对其分配路由和网络资源。

    该策略优势在于路由长度较长或跳数较多的业务对网络资源的占用要求比较高，应当预先使其得到满足，同样，整体而言阻塞率较低。

    路由与速率分配问题的启发式算法主要分为4步：

    步骤1——采用Dijkstra算法计算每对节点对间的主路由和备用路由。

    步骤2——按照业务流量和业务路经对每对节点间的业务从大到小进行排序。

    步骤3——按照业务排序依次为每条业务先按照主路由分配路由和速率。若阻塞，则使用备用路由，如果全部备用路由使用失败，则报错并返回，否则执行步骤4。

    步骤4——计算系统总能耗。

    启发式策略包括3种：

    启发式策略1——按业务流量对业务进行排序。

    启发式策略2——按业务主路由长度对业务进行排序。

    启发式策略3——按业务各路由链路的使用频率对业务进行排序。

1.4 仿真结果
    (1)ODUflex 4点网络拓扑

    图1所示为4点拓扑网络。图2所示为路由与速率分配问题4点拓扑网络仿真结果示意图。

    路由与速率分配问题4点拓扑网络仿真结果分析：

    (a)当流量较小时，各种启发式策略均能得到全局最优解。这是因为各项业务均分配均能满足最短路径路由分配而不产生阻塞。

    (b)当流量较大时，各种启发式策略增幅较小(不超过20%)。启发式策略1和启发式3相对较好。

    (2)ODUflex 24点拓扑网络仿真
    图3所示为24点拓扑网络。图4所示为路由与速率分配问题24点拓扑网络仿真结果示意图。
路由与速率分配问题24点拓扑网络仿真结果分析：

    (a)当流量较小时，各种启发式策略计算结果均相同，推测为全局最优解。因为此时各项业务平均分配均能满足最短路径路由分配而不产生阻塞。

    (b)当流量较大时，启发式策略1计算能耗最小，策略2、策略3均有较小增幅。当流量增大时策略3相对于策略1和2不容易阻塞，阻塞概率比较低。

    (c)启发式算法平均运算时间为66 ms，运算效率高。

2 带宽可变光OFDM网络
    当前，互联网IP爆炸式的增长趋势对传输容量和带宽需求提出了更高要求。为了满足爆炸式增长的业务，波分复用(WDM)技术被广泛应用于提高光纤的传输容量。常见的混合速率WDM有10G、40G、100G。相比单速率WDM，混合速率WDM网络能够提供10G、40G、100G 3种信道速率进行选择，因此具有一定的灵活性，但是带宽粒度仍然较大。网络中每个波长提供了极高容量，但没有被利用的带宽资源却是一种极大的浪费。带宽可变光OFDM网络能够很好地解决这个问题。OFDM使用多子载波调制。在发送端首先把高速数据信号转换成并行的低速子数据流，然后调制到每个子信道上进行传输，并保证每个子信道之间的正交性；在接收端通过相关技术实现子信道的分离。其作为一种数字调制格式，由于每个子信道带宽仅为原信道带宽的一小部分，因此极大提高了网络的频谱利用率和系统的传输效率。

2.1 路由与波长分配问题
    路由与波长分配问题主要包括两个子问题：在源节点和目的节点之间分配路由、为每条路由分配波长。系统能耗的假设与前文相同。WDM光网络需要考虑波长连续性，分配更加复杂。波长连续性是指因光交叉节点(OXC)通常没有波长转换能力，从而要求一条光路在OXC的入链路和出链路上分配相同的波长。问题主要分为3步：首先对业务进行排序，然后依次为业务分配路由，最后为分配的路由分配波长。

    具体到实际的WDM网络，假设使用偏振(Polarization)正交移相键控(QPSK)调制方式，则10G、40G和100G 3种速率的实际使用带宽分别为2.5 GHz、10 GHz和25 GHz。因为WDM的信道间隔频率是50 GHz，所以这3种速率的所需占用带宽均为50 GHz。

2.2 路由与频谱分配问题
    与路由与波长分配问题类似，路由与频谱分配问题主要包括两个子问题：在源节点和目的节点之间分配路由、为每条路由分配频谱。问题主要可以分为3步解决：首先对业务进行排序，然后依次为业务分配路由，最后为分配的路由分配频谱。频谱分配策略有：随机适应法、首次适应算法和最佳适应法。
和WDM中的光交叉连接相同，带宽可变的光交叉连接一般没有频谱搬移能力，因此需要考虑频谱连续性约束。

    本文假设带宽可变光交叉连接均不具备频谱搬移能力。如果分配不能满足频谱连续性限制，连接请求将被阻塞。

    具体到实际的光OFDM网络，本文采用文献[11]中提出的正交频段复用OFDM网络。文献中将OFDM信号分成多个子频段，同时保证这些子频段之间的正交性。光OFDM网络每个子频段的频谱是6.4 GHz，提供21.4 Gbit/s数据速率，可以通过调整子频段的数目产生与业务流量匹配的信号速率。根据ITU-T G.694.1中规定的WDM信道分配标准，信道的频谱间隔为50 GHz，在C-Band中将有80个信道。假设每条光纤链路上可供分配的频谱资源为4 000 GHz，则每条光纤链路上子频率段的数目为625个。

2.3 路由与频谱分配问题启发式算法
    在启发式算法中首先对业务进行排序，然后按照业务排序依次为每条业务请求分配路由和频谱。业务排序策略与路由与速率分配问题中的3种策略相同。频谱分配策略主要包括3种。

    (1)随机适应法
    随机适应法首先遍历所有可用资源，确定在选定路由上的可用资源的集合，再等概率地随机选取一段。算法的时间复杂度低，但没有考虑当前的网络状态。

    (2)首次适应算法
    首次适应算法将所有资源进行统一编号，再依次搜索，直到选择第一段能满足业务需求的资源来分配。该算法倾向于使用靠前的一段资源，保留了靠后的大块空闲区便于以后分配。

    (3)最佳适应算法
    最佳适应算法将所有资源进行统一编号，再选取其中一段能满足业务需求的且编号最小的资源来分配。该算法倾向于使用最小的一段资源，保留了完整的大块空闲区便于以后分配。

    路由与频谱分配问题的启发式算法包括6个步骤：

    步骤1——采用Dijkstra算法计算每对节点对间的主路由和备用路由。

    步骤2——按照业务流量和业务路经对每对节点对间的业务从大到小进行排序。

    步骤3——按照业务排序依次为每条业务按主路由分配路由，尽可能满足业务所需带宽，若分配失败，记录分配失败的流量。

    步骤4——判断业务分配成功否，若存在分配失败的流量，按照主路由集合分配路由；若分配失败，记录分配失败的流量。

    步骤5——判断业务分配成功否，若存在分配失败的流量，按照备用路由顺序分配路由；若全部备用路由分配失败，则报错并返回，否则执行步骤6。

    步骤6——计算系统总能耗。

    启发式策略包括6种：

    策略1A——采用频谱分配首次适应法，并且按业务流量对业务进行排序。

    策略2A——采用频谱分配首次适应法，并且按业务主路由长度对业务进行排序。

    策略3A——采用频谱分配首次适应法，并且按业务各路由链路的使用频率对业务进行排序。

    策略1B——采用频谱分配最佳适应法，并且按业务流量对业务进行排序。

    策略2B——采用频谱分配最佳适应法，并且按业务主路由长度对业务进行排序。

    策略3B——采用频谱分配最佳适应法，并按业务各路由链路的使用频率对业务进行排序。

2.4 仿真结果
    (1)波分复用与带宽可变光OFDM比较

    图5所示为WDM光网络与带宽可变光OFDM网络带宽利用率比较。图6所示为WDM光网络与带宽可变光OFDM网络能耗比较。

    仿真结果分析：

    (a)在频谱利用率方面带宽可变光OFDM网络具有绝对优势。

    (b)在能耗方面WDM光网络具有一定微弱优势。

    (c)因为在光传输网中频谱是相对紧缺的资源，应首先考虑。OFDM比WDM更具优势。

    (2)带宽可变光OFDM 4点拓扑网络仿真

    图7所示为路由与频谱分配问题各种算法4点拓扑网络仿真结果。

    路由与频谱分配问题4点拓扑网络仿真结果分析：

    (a)当流量较小时，各种启发式策略均能得到全局最优解，这是因为各项业务分配均能满足最短路径路由分配而不产生阻塞。

    (b)当流量较大时，各种启发式策略增幅较小(不超过15%)。综合而言，采用按各路由链路的使用频率对业务进行排序效果较好，各种频谱分配方法对计算结果影响不大。

    (c)最优化平均运算时间为117 s，启发式算法平均运算时间为168 μs，运算速度约为最优化的7×105倍，运算效率极高。

    (3)带宽可变光OFDM 24点拓扑网络仿真

    图8所示为带宽可变光OFDM 24点拓扑网络仿真结果。

    路由与频谱分配问题24点拓扑网络仿真结果分析：

    (a)当流量较小时，各种启发式策略计算结果均相同，推测为全局最优解，因为此时各项业务分配均能满足最短路径路由分配而不产生阻塞。

    (b)当流量较大时，各种启发式策略阻塞概率大致相同，同时使用按业务各路由链路的使用频率对业务进行排序和首次适应算法相对较好。

    (c)启发式算法平均运算时间为89 ms，运算效率高。

3 结束语
    当前，随着数据业务爆炸式的增长和各种新业务的出现，计算机互联网面临两大问题，即带宽和容量的需求持续快速增长和各种业务的不同粒度和传输信道带宽容量难以匹配。ODUflex光网络和带宽可变光OFDM网络能够较好地解决这两大问题，是本文研究的重点。伴随着传输流量的急剧增长，网络能耗增加迅猛，如何优化网络资源分配，降低能耗是本文研究的核心。

    本文针对ODUflex以及带宽可变光OFDM两种光网络分别提出路由与速率分配问题和路由与频谱分配问题，给出了最优化及启发式算法的仿真比较。

4 参考文献
[1] 顾畹仪, 张杰, 王健全, 等. 光传送网 [M]. 北京: 机械工业出版社, 2003.
[2] 杨淑雯. 全光光纤通信网 [M]. 北京: 科学出版社, 2004.
[3] 刘国辉. 光传送网原理与技术 [M]. 北京: 北京邮电大学出版社, 2004.
[4] 郑威. 带宽可变光网络资源分配优化研究 [D]. 上海: 上海交通大学, 2011.
[5] MUKHERJEE B. Optical WDM networks [J]. New York, NY,USA: Springer, 2006.
[6] CHRISTODOULOPOULOS K, MANOUSAKIS K, VARVARIGOS E A. Offline routing and wavelength assignment in transparent WDM networks [J]. IEEE/ACM Transactions on Networking, 2010,18(5):1557-1570.
[7] CHRISTODOULOPOULOS K, TOMKOS I, VARVARIGOS E A. Routing and spectrum allocation in OFDM-based optical networks with elastic bandwidth allocation [C]//Proceedings of the IEEE Global Telecommunications Conference (GLOBECOM'10), Dec 6-10,2010, Miami, FL, USA. Piscataway, NJ,USA: IEEE, 2010:6p.
[8] ZHENG W, JIN Y, SUN W, et al. On the spectrum-efficiency of bandwidth-variable optical OFDM transport networks [C]//Proceedings of the Optical Fiber Communication/ National Fiber Optic Engineers Conference (OFC/NFOEC’10), Mar 21-25, 2010, San Diego, CA, USA. Piscataway, NJ,USA: IEEE, 2010:3p.
[9] LOWERY A, DU L B, ARMSTRONG J. Performance of optical OFDM in ultralong-haul WDM lightwave systems [J]. Journal of Lightwave Technology, 2007,25(1):131-138.
[10] LOWERY A, ARMSTRONG J. Orthogonal frequency division multiplexing for dispersion compensation of long-haul optical systems [J]. Optics Express, 2006,14(6):2079-2084.
[11] YAN Tang and WILLIAM S. Coherent Optical OFDM Transmission Up to 1 Tbit/s per Channel [J]. Journal of Lightwave Technology, 2009,27(16): 128-13.

收稿日期：2011-09-08

[摘要] 文章针对灵活速率光信道数据单元(ODUflex)以及带宽可变光正交频分复用(OFDM)两种光网络分别提出路由与速率分配和路由与频谱分配课题。该课题将降低系统总能耗作为最优化目标，采用最优化软件ILOG CPLEX进行仿真，分别提出了相应的启发式算法，并将最优化结果同启发式算法的结果进行了性能上的比较与讨论。

[关键词] 带宽可变光正交频分复用；路由与频谱分配；路由与波长分配

[Abstract] This paper describes routing and rate allocation for optical data unit flex (ODUflex), and it also describes routing and spectral allocation for variable-bandwidth orthogonal frequency division multiplexing (OFDM). To reduce power consumption in routing and rate allocation, and in routing and spectrum allocation, ILOG CPLEX is used to complete the optimization simulation, and heuristic algorithm is also proposed. In this paper, simulation results of optimized performance and heuristic algorithms are discussed.

[Keywords] bandwidth-variable optical orthogonal frequency-division multiplexing; routing and rate allocation; routing and spectrum allocation