在绿色光网络中,业务传输时隙分配策略和路由选择算法很大程度上决定了光网络的传输能耗大小.针对业务持续时间的传输能耗问题,提出了一种基于灵活时间带宽预留型业务带宽可变节能调度算法.通过构造业务的调度权值矩阵,计算不同备选传输路径在不同时隙内被各个业务选择的次数,并基于贪婪算法为业务选择最小能耗的传输时隙和路径;同时,为充分利用已建光路的可用带宽,还设计了一种带宽调整策略,能根据不同时隙内光路的可用带宽调整业务的传输带宽,最小化网络中光路的数目.仿真结果表明,提出的带宽可变节能调度算法可有效地降低网络的传输能耗和业务阻塞率,提升网络的性能.
In green optical networks, the transmission time-slot allocation strategy and routing algorithm have a greatly impact on the transmission energy consumption. Aiming at the transmission energy consumption problem, a bandwidth-variable energy efficient scheduling (BVEES) algorithm based on flexible-time scheduled traffic was proposed. By constructing a weight matrix, BVEES calculates the selected times of different path candidates in different slots. Based on the idea of greedy algorithm, BVEES selects the transmission paths and time slots with the minimum transmission energy consumption. In addition, a bandwidth adjustment strategy, which can adjust transmission bandwidth according to the available bandwidth in different slots, was designed for BVEES to minimize the number of lightpaths in optical networks. Simulations show that the BVEES can effectively reduce the transmission energy consumption and the blocking probability.
随着云计算、视频会议、多媒体远程教育等业务的快速发展，快速增长的网络能耗已成为制约网络发展主要因素[1]. 节能路由算法、设备休眠机制[2]、网络结构设计[3]等被提出来解决即时分配类业务的传输能耗问题[4]. 对传输起始时间或持续时长确定的带宽预留型业务，Chen等[5]针对灵活时间提出了一种资源分配模型，Chen等[6]基于此资源分配模型提出一种能量有效启发式路由(HEER，heuristic energy efficient routing)算法，Patel等[7]对业务传输带宽调度，提出了启发式带宽可变路由(HVBR，heuristic variable bandwidth routing)算法.
1 问题分析灵活时间传输的带宽预留型业务请求可表示为R(s，d，B，ts，te，th)，s为业务的源节点，d为目的节点，B为业务请求传输带宽，传输时间窗口开始时刻ts、结束时刻te和业务持续时间th需满足th≤te-ts. 网络需保证业务整个传输过程在传输时间窗口(ts，te)内完成，即业务实际传输开始时刻t满足ts≤t，且t+th≤te.
网络为业务请求分配带宽资源主要存在以下3种情况：1)所选路径存在已建光路且可用带宽充足，此路径对应传输时隙标记为带宽充足时隙；2)所选光路存在但可用带宽小于业务的传输带宽，此路径对应传输时隙标记为带宽不足时隙；3)所选路径不存在已建光路但波长资源充足，则新建光路，此路径对应传输时隙标记为新建光路时隙.
f=「(te-ts)/T⌉
(1)
h=「th/T⌉
(2)
Ba+∑Bi=Bh
(3)
由式(1)和式(2)可计算传输业务需要分配的单位时隙数f和持续时隙数h，T为单位时隙. 在式(3)中，待传输业务在时隙i经过带宽调整后的传输带宽大小为Bi，如果待传输业务带宽充足时隙数为a，式(4)表示分配业务传输时隙数目f不小于带宽充足时隙和带宽不足时隙传输的带宽总和. 其中，如果时隙i是带宽不足时隙，则λi为1；否则λi为0.
∑λi+a≤f
(4)
式(5)表示当所有带宽充足时隙光路可用带宽最小值大于B/a，则每个传输带宽充足时隙增大的传输带宽Badi都为B/a；否则，从可用带宽最少光路开始依次增大业务传输带宽，增加值为光路的剩余带宽Bsi. 式(6)表示带宽增大总额为B.
$\left. \matrix{
B_{ad}^i = B/a,\min \left( {B_s^i} \right) > B/a \hfill \cr
B_{ad}^i = B_s^i,\min \left( {B_s^i} \right) \le B/a \hfill \cr} \right\}$
(5)
∑Badi=B
(6)
针对业务持续时间确定的预留型业务的能耗和路径时隙灵活分配问题，提出了一种基于启发式算法且考虑业务持续时间要求的带宽可变节能调度(BVEES，bandwidth variable energy efficient scheduling)算法，该算法包括业务传输路径、时隙选择过程和带宽调整光路中一个业务到已建光路传输的过程. BVEES算法在为业务选择传输路径和时隙之前，首先要为各个业务请求构造调度权值矩阵.
BVEES算法构造调度权值矩阵的过程为：在网络拓扑上用最短路径算法为业务计算出K条链路分离的最短传输路径，K为网络节点平均度数，记录每条传输路径经过的节点和物理链路信息. 将系统时间划分为一组系统时隙. 根据划分好的系统时隙和待传输业务的传输窗口开始时刻ts，可找到对应的业务传输开始时隙编号v；同时，由式(1)和式(2)计算业务传输时间窗口需要的单位时隙数f和持续时隙数h，则业务调度权值矩阵为
$S = \left( {\matrix{
{{S_{1,v + 1}}} & {{S_{1,v + 2}}} & \cdots & {{S_{1,v + f}}} \cr
{{S_{2,v + 1}}} & {{S_{2,v + 2}}} & \cdots & {{S_{2,v + f}}} \cr
\vdots & \vdots & {{S_{i,v + j}}} & \vdots \cr
{{S_{k,v + 1}}} & {{S_{k,v + 2}}} & \cdots & {{S_{k,v + f}}} \cr
} } \right)$
(7)
构造业务的调度权值矩阵计算网络中不同备选传输路径在不同时隙内被业务选做传输路径的概率，为业务传输时隙和路径的选择提供依据. 业务请求传输时隙和传输路径的具体选择过程如下：
步骤1 将所有业务请求按照传输开始时隙编号v大小次序插入待传输业务请求链表L中；
步骤2 检测链表L是否为空，如果为空，算法结束；否则，转步骤3；
步骤3 取出链表L中存储待处理业务请求；
步骤4 选择调度权值矩阵式(7)中最大值元素，即选择调度权值最大的备选传输路径作为业务 传输路径，权值对应时隙(v+j)为分配业务传输时隙，权值对应行序号i为业务选择的第i条传输路径；
步骤5 在所选传输时隙内为传输路径分配带宽，并根据带宽分配情况对传输路径进行标记；
步骤6 根据式(3)判断此待传输业务传输路径和传输时隙选择是否完成，若完成，算法转步骤7；否则，算法转步骤4；如果在系统时隙内没有为业务找到足够的传输时隙和路径，则从链表L中删除此业务请求，业务请求被阻塞，转步骤2；
步骤7 在所选传输路径上删除已分配带宽资源，更新网络，并从链表L中删除业务，转步骤2.
2.2 业务传输带宽调整策略BVEES算法为业务所选传输路径时，优先选择已建光路，如果已建光路的可用带宽小于业务传输带宽，则新建一条光路. 为充分利用网络中已建光路的可用带宽，设计了一种带宽调整策略. 该策略通过增大带宽充足时隙的传输带宽，减小带宽不足时隙的传输带宽，最小化网络中已建光路数目.
业务传输带宽调整策略的主要步骤如下：
步骤1 检测传输路径中是否存在仅传输一个业务的潜在可拆除光路，标记该光路的业务为带宽待调整业务，记录带宽待调整业务请求和时隙带宽分配信息，按照业务传输开始时隙编号v从小到大顺序将所有带宽待调整业务插入带宽调整链表K中；
步骤2 判断链表K是否为空，如果不为空，转步骤3；否则，路径带宽调整过程结束；
步骤3 从链表K中取出带宽待调整业务；
步骤4 根据式(6)计算业务带宽充足时隙光路的可用带宽是否满足带宽调整条件，若满足，转步骤5；否则，从链表K中删除业务，转步骤2；
步骤5 根据式(5)选择带宽调整方式，并更新调整后的传输带宽和网络带宽资源，转步骤2.
3 仿真结果及分析为验证带宽可变节能调度算法的性能，BVEES算法在由14个节点和21条链路构成的如图 1所示的国家科学基金(NSFNET，national science fund network)网络中进行验证，图 1中的数字表示节点之间的距离，单位为km，光纤上每间隔80 km放置一个光放大器. 光纤链路波长数为8，波长信道容量为OC- 192，即10 Gbit/s；业务请求带宽按OC- 3:OC- 12:OC- 48=4: 4: 2产生. 端口和设备能耗模型使用文献[4]的模型.
 | 图1 NSFNET网络拓扑 |
图 2显示了网络总能耗与业务请求数的关系. 网络总能耗随着业务请求数的增加而不断增加，HVBR算法选择最小传输时延的传输路径，而最小传输时延不能保证最小化能耗，因而HVBR算法的能耗大. HEER算法通过指令层并行(ILP，instruction level parallelism)为业务找到最小能耗路径，能耗小. BVEES算法的传输路径和时隙选择机制使尽可能多的业务集中在相同路径和时隙内传输，减小了能耗.
 | 图2 网络总能耗与业务请求数的关系 |
图 3表示网络节点端口能耗与业务请求数的关系. BVEES算法和HEER算法都选择最小能耗的传输时隙和路径建立光路，其端口能耗小于HVBR算法；BVEES算法通过带宽调整策略，充分利用已建光路的可用带宽，减小新建光路数目，进一步减少端口能耗.
 | 图3 网络节点端口能耗与业务请求数的关系 |
图 4表示网络阻塞率与业务请求数的关系. HEER算法的阻塞率最高，HVBR算法次之，BVEES算法阻塞率最小. 因为HEER算法不调整业务传输带宽，不能充分利用已建光路的剩余带宽，新建光路消耗大量的波长，因而阻塞率最大. HVBR算法优先选择剩余带宽多的光路传输业务，使剩余带宽少的光路不被充分利用，增加了带宽碎片，因而阻塞率略高于BVEES算法. BVEES算法通过带宽调整策略，充分利用光路的剩余带宽，减小了阻塞率.
 | 图4 网络阻塞率与业务请求数的关系 |
图 5示出了网络阻塞率与单光纤配置波长数的关系. 可以看出，3种算法的网络阻塞率都随着单光纤配置的波长数的增加而减小. HEER算法不能根据光路的可用带宽来调整业务的传输带宽，波长资源利用率低，因而其阻塞率最高. 相比于BVEES算法，HVBR算法优先选择可用带宽大的光路传输业务请求. 在波长资源不充足时，选择剩余带宽较小的光路传输业务请求的概率大，所以阻塞率与BVEES算法相当. 但当光纤配置波长数继续增加 时，HVBR算法优先选择剩余带宽多的光路传输业务请求的概率增加，导致光路产生大量“带宽碎片”，因而其阻塞率相比BVEES算法有一定的增加.
 | 图5 网络阻塞率与单光纤配置波长数的关系 |
针对灵活时间预留型业务在波分复用(WDM，wavelength division multiplexing)光网络中的绿色节能问题，提出了一种带宽可变的传输时隙、路径选择和带宽分配的算法. 该算法选择最小能耗的光路和时隙传输业务，并通过带宽调整策略，充分利用已建光路的剩余带宽，减小网络中新建光路数目，同时降低网络能耗和阻塞率. 随着会议电话、视频点播等带宽预留业务的发展，能有效降低网络能耗和阻塞率的策略可进一步推动电信产业的可持续发展.
| [1] | Manousakis K, Angeletou A, Varvarigos E M. Energy efficient RWA strategies for WDM optical networks[J]. Journal of Optical Communications and Networking, 2013, 5(4):338-348.[引用本文:1] |
| [2] | 刘焕淋, 刘洋, 陈勇, 等. WDM光网络中带宽预留型业务的时间感知绿色疏导算法[J]. 北京邮电大学学报, 2014, 25(10):1906-1911. Liu Huanlin, Liu Yang, Chen Yong, et al. Time-aware green grooming algorithm for scheduled traffic in WDM networks[J]. Journal of Beijing University of Posts and Telecommunications, 2014, 25(10):1906-1911.[引用本文:1] |
| [3] | 陈勇, 籍慧琴, 刘焕淋, 等. 透明IP over WDM网络中一种能效链路控制策略[J]. 北京邮电大学学报, 2015, 38(6):41-46. Chen Yong, Ji Huiqin, Liu Huanlin, et al. An energy-efficiency link control strategy for transparent IP over WDM networks[J]. Journal of Beijing University of Posts and Telecommunications, 2015, 38(6):41-46.[引用本文:1] |
| [4] | Guo Lei, Hou Weigang, Wei Xuetao, et al. Power efficient grooming based on optical bypass reconfiguration in green optical networks[J]. Optik-International Journal for Light and Electron Optics, 2013, 124(5):437-445.[引用本文:2] |
| [5] | Chen Ying, Jaekel A, Bari A. A new model for allocating resources to scheduled lightpath demands[J]. Computer Networks, 2011, 55(13):2821-2837.[引用本文:1] |
| [6] | Chen Ying, Jaekel A. Energy-aware scheduling and resource allocation for periodic traffic demands[J]. IEEE/OSA Journal of Optical Communications and Networking, 2013, 5(4):261-270.[引用本文:1] |
| [7] | Patel A N, Jue J P. Routing and scheduling for variable bandwidth advance reservation[J]. Journal of Optical Communications and Networking, 2011, 3(12):912-923.[引用本文:1] |