弹性光网络实验二、碎片感知的RSA算法解析与Java源码实现
(>>>>在公众号中输入文章最后彩蛋即可获取源代码)
开源项目：https://github.com/chenxhjeo，个人博客：http://blog.csdn.net/u013487761
技术QQ群名称：豆豆咨询，群号：625686304
微信公众号名称：豆豆咨询，微信公众号：douAsk
我的公众号：chen-jeo
初建日期：2017.06.03
一、实验目的
1、掌握弹性光网络（EON）下碎片感知的RSA算法核心思想及其实现。
二、实验内容
1、分析弹性光网络下的碎片感知的RSA核心算法。
2、实现碎片感知的RSA核心算法。
三、实验步骤及过程
1、碎片感知的RSA算法
在[Y. Yin, H.
Zhang, M. Zhang, M. Xia, Z Zhu, S. Dahlfort, and S. J. B. Yoo. Spectral and
Spatial 2D Fragmentation-Aware Routing and Spectrum Assignment Algorithms in
Elastic Optical Networks. J. OPT. COMMUN.NETW, 2013, 5(10).]提出了碎片感知的RSA算法（FA-RSA）以及拥塞避免的FA-RSA算法（CA-FA-RSA）。以下我们将分析其算法基本思想，并实现这些算法。
（1）算法由来
减少网络的资源碎片能够有效地提高网络请求的接收率，而网络的资源碎片来源于两部分：
第一部分，频谱资源碎片，即同一条链路中频谱资源分散在不同的区域，中间被占用的slot槽切割成独立的部分，这样即使整个slot槽能够满足要求，但是由于不满足连续性要求，网络请求将被拒绝分配资源。
第二部分，频谱空间资源碎片，即相邻的链路中资源slot槽不能满足紧邻性约束，即使不同的链路有足够的资源，但由于满足不了紧邻性约束而被拒绝分配资源。
如何减少这两部分的资源碎片成为RSA算法的关键所在。方法如下：
1）采用切代价（cut cost）来计算可选路径上的slot碎片，即如果某个分配分割了一条链路的可用资源，则切增加1，否则为0；计算这条路径上所有的切，并求和，则为路径上的切。
2）采用非对齐代价（misalignment cost）来计算可选路径上的分配对其它链路产生的影响，即计算相邻链路是否分割，如果分割了，则代价为1；否则为-1；把所有的相邻链路的非对齐代价，计算其总和。
如果切代价和非对齐代价较高，则说明分配方案不好，对资源碎片影响较大，产生较多的slot资源碎片；否则，说明分配方案对资源碎片影响较小，产生了较少的slot资源碎片。
（2）算法解析
1）FA-RSA算法（Fragmentation-Aware RSA）
a.计算k最短路径，把这些路径放入集合P中；
b.foreach(对于每条路径r)
c.foreach(对于每个候选分配c)
d.计算切Fc；
e.从选择方案中，选择最小切Fc的分配方案；
f.if(最小切Fc的分配方案只有一个) return该这种方案；
g.foreach(对于每个具有最小切Fc的方案)
h.计算misalignment的总和，记录为Fm；
i.选择最小Fm和最小Fc的RSA；
j.if(只有一个最小Fm和最小Fc的RSA方案)
k.return最小Fm和最小Fc的RSA方案；
l.return从可选方案中选择最短路径和first-fit频谱分配方案；
该算法的时间复杂度为O(kdnClogC)，k表示最短路径条数，d表示底层节点的最大度，n表示底层网络的节点数量，C表示单条链路slot槽数量。
2）FA-CA-RSA算法（Fragmentation-Aware RSA with congestion avoidance）
a.计算k最短路径，把这些路径放入集合P中；
b.foreach(对于每条路径r)
c.foreach(对于每个候选分配c)
d.计算切Fc；
e.计算misalignment的总和，记录为Fm；
f.计算路径上的链路剩余slot；
i.计算Fcmt，其公式为Fcmt=Fc+Fm/(S*N)+H*S/C；
j.选择最小的Fcmt的候选方案；
k.if(只有一个最小的Fcmt的候选方案)
l.return最小的Fcmt的候选方案；
m.return从可选方案中选择最短路径和first-fit频谱分配方案；
算法中，S表示请求的slots数量，N表示候选路径的邻接链路数量，H表示候选路径的的条数，C表示单条链路slot槽数量。
该算法的时间复杂度为O(kdnClogC)，k表示最短路径条数，d表示底层节点的最大度，n表示底层网络的节点数量，C表示单条链路slot槽数量。
（3）算法评价
算法在不同的Erlang下评估，即以请求数量变化在每个事件单元在[0.8，10]达到率的泊松分布下构造Erlang，每个请求的生存期为5个时间单元，请求范围在[1 slot, 10 slot]随机分布，
性能评价指标：带宽阻塞率，即拒绝的slot总量/请求的slot总量。
底层网络：14-node的NSFNET和24-node的USBN，每个频谱槽设置为12.5GHz，每个光纤链路有400个slots。
性能比较基准算法为：SP-FF(the
shortest path routing and first-fit spectrum assignment)和KSP-FF(the K-shortest path routing and first-fit spectrumassignment)
在14-node的NSFNET下，构造了[50,700]的Erlang下评估算法，BP在[0,0.35]范围内。
在28-node的USBN下，构造了[50-350]的Erlang下评估算法，BP在[0,0.3]范围内。
四、技术服务和源码下载
1、如果有疑问或者需要帮助，请加入QQ群（群名称：豆豆咨询，群号：625686304）；或者公众号douAsk，公众号名称为“豆豆咨询”。扫描以下二维码，关注“豆豆咨询”。
2、技术支持与源码下载：
技术QQ群名称：豆豆咨询，群号：625686304
在公众号里输入彩蛋号即可下载源码：
彩蛋号：2001。
