毕业设计（论文）-灵活栅格光网络中的资源优化技术研究.docx

北京林业大学本科毕业论文(设计)灵活栅格光网络中的资源优化技术研究全套设计加扣3012250582 摘要随着宽带业务和互联网的飞速发展，特别是现在4G移动网络的兴起，作为数据传送主力的光网络面临着更大的挑战。扩大容量与增加灵活性成为当今光网络研究的主要趋势。传统光网络WDM（Wavelength Division Multiplex）的频谱资源分配方式是基于固定栅格的，由于固定栅格的限制使得光网络渐渐在高宽带，高灵活，低延时方面不能满足人们的需求了。应运而生的灵活栅格的光网络成为现在数据光网络研究的热点问题。灵活栅格光网络的出现在帮助频谱资源更灵活应用的同时也伴随着频谱资源碎片的问题。因此，频谱资源优化技术研究成为当务之急。本文首先对频谱碎片的产生机制以及现有的主要解决办法进行了分析与讨论,在已有的研究基础上提出来一种新的基于业务感知的频谱碎片评估方案，实现可以对网络中的碎片程度进行量化表现。然后以其为基础设计了一种新的基于频谱碎片感知的路由频谱分配算法。最后，在实验平台上设计并验证了该算法，并对所得结果进行分析，仿真结果显示本文所提出的算法能够一定程度解决频谱碎片问题。关键词：灵活栅格光网络，路由与频谱分配，碎片评估Research On Resource Optimization Technology in Flexible Grid Optical Networksabstract With the rapid development of broadband services, the Internet, especially the rise of modern 4G mobile networks, optical network as the data transmission network is facing a bigger challenge. To expand the capacity and be more flexibility has become a major trend in todays optical networking research. Traditional WDM (Wavelength Division Multiplex) optical network ,whos spectrum resource allocation method is based on a fixed grid, as a result of the limitation of the flexible grid optical network gradually cant satisfy peoples needs in high broadband, more flexibility and low latency ways.Arises at the historic moment, optical networks with flexible grid become a hot issue in the research on optical network. Although the appearance of flexible grid optical network is helpful in making spectrum resources application be more flexible,at the same time ,its also associated with a problem in spectrum fragments. Therefore, the research about spectrum optimization technique is becoming the urgent matter.Firstly, this paper introduces the key cause and terms of settlement in resource fragmentation, we present a traffic aware fragment degree method for evaluate the fragment degree of the network.Then by using the new fragment degree research we proposed a new routing and spectrum allocation which can help us reduce the degree of spectrum program when we set up a new light rout.Finally,through the experimental platform we get the simulation results，the experimental results demonstrate the ability of the proposed algorithm to solve the problem of spectrum defragmentation in flex grid optical networks on some level.KEYWORDS: flexible grid optical networks, routing and spectrum allocation, spectrum assessment目录1 绪论11.1研究背景11.1.1对光网络的需求增长11.1.2光网络所处窘境11.2光网络技术研究趋势及研究现状21.2.1光网络改进所依托的创新技术21.2.2灵活可变灵活栅格光网络31.2.3关键问题及解决方向42灵活栅格光网络资源特性与优化62.1频谱碎片问题62.1.1碎片问题的产生62.1.2碎片问题的解决方法72.2频谱碎片评估模型82.2.1基于频隙状态的频谱碎片评估模型82.2.2基于链路状态的频谱碎片评估模型102.3路由与频谱分配问题103基于频谱碎片感知的路由与频谱分配优化技术123.1 基于业务感知的频谱碎片评估方案123.1.1业务概率的动态计算模型133.1.2 路径对业务的承载能力143.1.3 网络对业务的承载能力163.2 基于频谱碎片感知的路由频谱动态分配173.2.1 路径频谱碎片感知的PFT-RSA173.2.2 网络频谱碎片感知的NFT-RSA184 实验仿真与结果分析204.1仿真环境204.2仿真结果215 总结与展望245.1论文总结245.2未来工作展望24致谢25参考文献26 IV1 绪论近年来宽带业务不断增长，互联网需求指数增加，4G手机成为新主流，4G移动网络、云计算等高速发展使得数据传输主流光网络不能满足于固定栅格的WDM光网络，新型灵活栅格光网络以其高灵活，高频谱利用率，高传输效率为研究者所重视，成为未来光网络的主流趋势。本章接下来会简单介绍现在对光网络的需求现状及其显现出来的不足之处，然后引出新型的灵活栅格光网络，简介它的主要架构和特性并反映出伴随出现的资源优化问题，从而引出本文对解决该问题的研究。1.1研究背景现代互联网技术不断发展，网络规模不断增大，同时人们对信息的需求也急剧增加，导致业务呈现爆炸式的增长，作为数据传输主载的光网络在大容量传输方面也面临着极大的考验。毋庸置疑，基于固定栅格的传统WDM光网络在超信道和自适应传输速率方面无法满足需求，灵活栅格光网络便应运而生。灵活栅格光网络不但要满足传统WDM光网络中频谱一致性的约束，同时还要满足频谱连续性。也正是由于频谱连续性的约束以及业务的随机性与不确定性，导致灵活栅格光网络必须面对频谱碎片问题。频谱碎片问题的存在会导致频谱利用率降低，从而容易产生网络阻塞现象降低网络传输性能。频谱资源的优化分配能够有效降低频谱碎片程度，进而提高频谱资源利用率并提升网络性能。1.1.1对光网络的需求增长全球互联网自上世纪九十年代进入商用以来迅速拓展，越来越多的新型产物依托互联网推陈出新，光纤通信以其突出的传输特性，带宽特性尤其是其高性能的性价比而成为现在数据传输的主流网络。根据中国互联网络信息中心发布的最新互联网使用报告1，截止2014年12月，中国网民规模达6.49亿，全年共计新增网民3117万人。互联网普及率为47.9%，较2013年底提升了2.1个百分点。手机网民规模达5.57亿，较2013年底增加5672万人，提升至85.8%。由此可见互联网使用需求持续上涨，通信地位日益上升，因此对光网络在数据传输上大容量高效率等方面的需求也逐渐增加。 1.1.2光网络所处窘境（1） 表现形式分析随着互联网需求的增加，4G移动网络与宽带的需求处于高速增长状态，因此采用固定栅格的传统WDM光网络的网络承载能力逐渐显现出吃力，已经渐渐不能满足互联网高速发展产生的对数据传输在超宽带，超信道方面的要求。现在生活面向信息化不断加速深化，人们对信息的需求在数据、语音以及视频等方面都在急速增长，随着高清视频和高速宽带的发展和普及，用户的IP业务流量基本在每两年就会翻一番，以上因素都使得网络所面对的业务信息量呈爆炸式增长2。（2） 深入根本分析传统WDM光网络技术由于采用固定栅格，不能灵活的实现资源利用，这成为制约光网络发展的关键问题。问题一，固定栅格降低了频谱利用率，光通道常见的频谱间隔为50GHz,这个频谱间隔在传输速率为100Gb/s的光通道里是高效率的3，可是在光通道传输速率低的光通道例如10Gb/s时，就导致了频谱资源的浪费。问题二，还有一些地方是需要传输大量数据，如网络运营商的核心网与各城市间的数据传输，这时就希望用于传输数据的光网络可以支持超级信道来使得传输更具高效性和低延时性，可是固定栅格下的50GHz显然是无法承担的。问题三，随着光网络中业务的粒度不同，并且是动态的，固定栅格的WDM无法进行灵活的频谱资源分配，这必将导致频谱资源的浪费从而降低网络传输性能。总的来说，面对网络发展初期的信息传输要求，传统的WDM网络在各方面都是能够满足的，但随着信息时代的不断发展，基于固定栅格的传统光网络便开始捉襟见肘，人们的目光也自然转向更具有适应性的新型灵活栅格光网络。1.2光网络技术研究趋势及研究现状从发展的角度来看，新型高频谱利用率的灵活栅格光网络的研究方向主要包括：（1）灵活栅格光网络中频谱资源的分配，包括频谱资源分配算法和算法的生存性策略研究；（2）灵活栅格光网络中控制平面关于灵活频谱交换模式的精细有效扩展，即在控制平面，通过对多粒度、多维度频谱资源进行精细掌控，达到可以对每个使用中频谱的所载信息的计算、定位与调度。本论文便从上述第一类方向中的灵活栅格光网络的频谱资源分配优化方向进行展开研究。在路由与频谱分配优化研究方面，我国已有多所包括北京邮电大学在内的高校以及相关研究机构都有相关的前期研究，并已经通过将线性规划方法应用到静态灵活栅格光网络的规划等问题分析，提出了基于滤波器保护间隔带宽以降低频谱使用率的路由与频谱分配算法4；在生存性策略研究方面，日本NTT实验室也有相关研究成果，他们提出带宽压缩恢复概念，并将这种方法来保护和恢复网络上不同服务质量（Quality of Sever, QoS)等级的业务5。1.2.1光网络改进所依托的创新技术支撑光网络改进的创新技术主要从调制格式、全光交换器件、信号复用模式三个方面出发为新一代网络架构的出现铺平了道路。其中调制格式是向更灵活的方向改变，新型调制格式类型可以按照调制原理分为三类，分别为基于强度调制原理的开关键控（On-Off Keying，OOK）系列、基于相位调制原理的预共享密钥模式(Pre-Shared Key，PSK)系列、基于偏振调制原理的PSK系列6。其中光通信技术光正交频分复用技术（Optical-Orthogonal Frequency Division Muliplxing，OOFDDM）将正交频分复用（Orthogonal Frequency Division Multiplexing,OFDM）技术应用在光纤通信中7，将包括远距离传输在内的许多问题较好地解决了，成为相关研究的热点方向。 全光交换器件在面向宽带可变趋势上，也应时代需求涌现出多种新型的全光交换器件，其中包括带宽可变的光收发机、带宽可变光选择开关（Bandwidth Variable-Wavelength Selective Switch,BV-WSS）等适应宽带可变需求的器件8。信号复用模式也是向着更灵活的方向进展，光传送网（Optical Transport Network,OTN）中的信号装载容器(Oracle Database Unloader,ODU)，传统的容量固定的ODUk（k=0,1,2,2e,3,4），不能随着业务粒度改变而灵活改变自身容量。针对该问题，国际电信联盟远程通信标准化组织（ITU-T for ITU Telecommunication Standardization Sector,ITU-T)提出来可以实现任意比特率业务的传送的ODU-flex技术9等，有效地解决了相关问题，在进一步提高对动态信息适应的时变性能以及资源使用效率方面做出贡献。1.2.2灵活可变灵活栅格光网络在以上新型技术的支撑下，日本、欧盟、美国等各国研究人员分别推出了多种新型的灵活栅格网络架构例如图1.1，成为现在研究的热点。基于OOFDM的灵活栅格光网络使得带宽可变的收发机可以弹性分配足够的频谱资源来传递相应业务10。由图1.2可以一目了然地看出，多个OOFDM信道可以组成一个超级信道，并且光路上的节点也都配置带宽可变的光器件来建造端到端的光链路。1.1 灵活栅格光网络的架构示意图10Fig.1.1 Flexible grid optical network architecture diagram10图1.2显示了基于OOFDM的灵活栅格光网络和传统固定栅格WDM网络在频谱利用方面的不同。传统固定栅格的WDM光网络在频谱利用时需要满足波长不重叠限制和波长一致性限制，即同一频谱资源只能分配给一个连接使用以及一个连接在不同链路上必须使用同一波长；灵活栅格光网络在频谱利用时则需满足频谱不重叠限制、频谱一致性限制和频谱连续性限制，正由于频谱连续性的限制也引发了接下来将要介绍的频谱碎片问题。 1.2 灵活栅格和传统WDM网络在频谱利用方面区别Fig.1.2 The difference in the use of spectrum between flexible grid and traditional WDM network1.2.3关键问题及解决方向新型光网络的出现不是一蹴而就的，会伴随许多的问题。下图1.3中表示了三种栅格模式，其中1.3（a）是传统WDM网络中所使用的固定栅格,其栅格间隙一般为50GHz;灵活栅格光网络中现使用图1.3（b）所示的微栅格模式，将栅格间距降低到12.5GHz或者6.25GHz，传输中一个频谱可以跨越多个栅格频隙，这样的灵活性帮助网络可以支持超级信道的实现；图1.3（c）所示的无栅格模式是网络传输栅格的理想模式，不存在固定的中心频率，可根据需要而定，目前还未能实现。也正是由于灵活栅格所使用的微栅格模式，在进行业务传输过程中，不可避免地会出现一些频谱碎片。尤其随着时间的推长，即经过较长时间的运行后，频谱资源会产生较高的碎片分散度，碎片在频谱上产生的空隙导致了大量的不能承载大业务的非连续频谱资源，这样在粒度较大的业务到来时便由于频谱资源不足，造成了网络阻塞。为解决碎片问题现已存在很多前期研究，目前的解决办法主要有开发更灵活高效的资源分配算法和碎片整理两种，最终结果都能一定程度上缓解频谱碎片问题，降低频谱碎片程度从而降低网络阻塞率提升网络性能。目前，在开发更灵活高效的资源分配算法以及碎片整理方向都有很多创新性的构想，现在也才形成了一定规模的研究体系，我们在第二章会具体介绍。相信在不久的将来会，研究人员们可以成功开发出成型的碎片资源优化体系，为灵活栅格光网络保驾护航，更好地迎接信息化时代。 （a）固定栅格 （b）微栅格 （c）无栅格1.3 三种栅格模式Fig.1.3 Three grid pattrens2灵活栅格光网络资源特性与优化在灵活栅格光网络中较为成功地解决了固定栅格光网络中的一些弊端，它打破了传统固定栅格光网络的固定波长栅格的限制，实现了在频域将频谱资源细分化的目的，更小的频隙资源帮助光网络能够更灵活地进行资源分配。但在灵活栅格光网络的频谱资源划分更精细的同时，人们也不得不面对网络对业务进行一段时间地传输后，频谱资源中可用资源与空闲资源的杂乱分配的问题即频谱碎片问题。若不对频谱碎片问题进行解决则易产生网络阻塞现象从而大幅度地影响网络传输性能，因此，网络碎片问题的解决势在必行。2.1频谱碎片问题新型灵活栅格光网络使得作为数据传输主载的光网络更好地适应了极速发展的数据传输需求。但因为灵活栅格光网络中将频谱资源更加细化，使其在传输业务时更加有灵活性，所以随之而来的频谱碎片问题也更加显著。简单来说，频谱碎片问题是指在粒度较大的业务请求到来时，因为空闲的频谱资源分配杂乱未能满足其频谱连续性限制，所以不能分配给该业务使用，使得该业务发生阻塞现象。如果不对频谱碎片问题进行解决，势必将造成链路中无法及时分配给业务相应频谱资源，大量的空间离散频谱碎片无法得到利用，最终结果便是频谱利用率降低并且产生网络阻塞现象降低网络性能。现有的频谱碎片问题解决方向大致分为碎片整理和资源分配优化，下面我们也对其具体实现机制进行相应简单描述。2.1.1碎片问题的产生细化地讲，光网络在工作时所面对的业务是实时的也是多变的，其到达时间和离去时间以及传输时间同样也是未知的。在业务请求到来时，光网络为其分配一定的频谱资源，建立连接，让其完成传输，随后业务处理完毕，相应频谱资源也便会被释放。追其根本的形成原因：由于光网络对业务的传输必须满足频谱连续性限制，即对业务进行传输的频谱资源必须是连续的，不能是分散的。所以，随着时间流逝及时间和空间上随机发生的大量粒度不定业务不断地到达（链路为其分配可用频谱资源，连接建立）与离开（连接断开并且链路释放相应的频谱资源），链路上的可用频谱资源会分布的杂乱无章，形成空闲频谱资源分散分布的现象，即频谱碎片问题。产生的结果便是，当粒度较大的业务请求到来时很容易不能被链路分配可用频谱资源并建立连接，从而产生网络阻塞现象并降低了网络的传输效率。2.1.2碎片问题的解决方法在灵活栅格光网络在传输方面带来众多好处的同时，我们也必须面对其所产生的频谱碎片问题。在绪论中我们已经提到碎片问题的解决方法大致分为两种：碎片整理与资源分配优化。下面我们将简单描述两种方法的具体实施。（1）碎片整理机制简单来说，碎片整理机制即对频谱资源进行重新分配，也称为频谱重构技术。其实现原理是将正在传输中的业务进行频谱搬移，将使用中的频谱资源进行整理，最终实现频谱碎片很大程度地整合起来形成频谱连续的可利用资源11。图2.1是一种简单的碎片整理示意图，未被进行整理时，我们看到即使链路上存在空闲的频谱资源，但由于频谱连续性的限制而导致该空闲资源不能被利用。通过对现存在的业务进行频谱搬移即碎片整理之后，有效的解决了其所导致的网络阻塞现象。2.1 碎片整理示意图Fig2.1 Schematic diagram of pectrum defragmentation虽然通过碎片整理可以很大程度上提高频谱资源的利用率从而降低网络阻塞率，但是在进行碎片整理时需要将网络中正在传输的业务进行终止，从而一定程度上降低了网络传输速率。因而在进行碎片整理时需要考虑的很关键的问题便是何时进行重构以及如何进行重构。何时进行碎片整理也就是碎片整理的触发机制，适时的触发才能达到优化网络传输性能的目的。当碎片整理触发机制所依据的触发阈值过低时，对网络进行碎片整理的频率便会很高，导致网络传输速率降低；当触发阈值过高时，又会导致进行碎片整理的频率过低，未能及时进行资源整理，达不到解决碎片问题的目的。所以，一个合适的碎片整理触发机制起着至关重要的作用。现在为止根据触发对象分类，碎片整理机制可以分为两种：一种为基于业务受阻的碎片整理触发；另外一个是基于整个网络的碎片整理触发。前者可根据某一业务受阻情况来决定何时进行碎片整理，后者可以根据某一网络性能来决定何时进行碎片整理或者定时进行整理12。如何进行碎片整理，即对频谱碎片整理算法的研究。最好的碎片整理算法应当满足可以依据网络的整体或部分的频谱使用现状，进行对网络性能影响最小同时有效降低频谱碎片程度的整理调度。（2）资源分配优化机制资源分配优化包括路由分配优化和频谱分配优化。简单讲，是在业务请求到来后按照一定的路由与频谱分配算法为其分配更加有利于降低频谱碎片问题的路径和频谱资源，这样在对业务建立连接的时候便达到了降低频谱碎片的目的，能有效的降低网络的阻塞率。路由与频谱资源分配问题按照不同的参考标准可以分为不同类别。此处暂且介绍按照参考对象分类，大致可以分为两种：第一种是针对单个业务，将其作为处理对象进行路由和频谱资源分配；第二种是针对多个业务将其“合”为一个业务，然后将其作为处理对象进行路由和频谱资源的分配，或者反过来讲一个业务“拆”为多个子业务，然后在作为对象进行处理分配13。由于本文所提出的频谱碎片评估模型是针对单个业务的，所以最后提出的路由与频谱分配算法同样也是针对单个业务的，但在后期也可以将业务整合或拆分考虑进去。2.2频谱碎片评估模型通过解决碎片问题来提高光网络的数据传输性能已经成为现在光网络研究的一个热门方向。在解决碎片问题时很重要的一点便是频谱碎片评估模型的建立，成熟的频谱碎片评估模型能够及时有效地对网络频谱碎片程度进行量化的体现，进而为碎片问题的解决提供相应判断依据。现在已有频谱碎片评估方案可以大致分为基于频隙状态的频谱碎片评估和基于链路状态的链路评估。2.2.1基于频隙状态的频谱碎片评估模型该频谱碎片评估模型主要依据每个频隙的使用情况来对链路以及整个网络进行碎片程度的评估，这就不得不提到典型的频谱使用熵Utilization Entropy,UE的概念14-15。以下便是具体的评估步骤：（1）计算每条链路频谱使用熵（UE_link）首先，对每条链路频谱资源按照位置高低依次标记频隙使用情况，被使用则标记为1，未被使用则标记为0。其次，计算每条链路的UE_link。即将每条链路频隙使用的标记进行异或计算（XOR，11=0，10=1，01=1，00=0）。得出的UK_link便反应了该链路上频隙使用状态改变次数。最后，对结果进行归一化处理，使其更有可读性。如图2.2所示具体实例可知，当链路上频隙使用情况较为简单时，如状态（a）和状态（f），则相应的UE_link值也较小；反之，链路上频隙使用情况复杂时，如状态（d），则相应的UE_link值也较大。因此链路频率使用熵UE_link的值能反映出该链路频隙使用情况的复杂程度，即反映了链路上频谱的连续性，及其碎片性。图2.2 不同频率使用状态下UE_link值的计算13Fig.2.2 Calculation of UE_link value in different frequency using condition13（2）计算一条路径的频谱使用熵（UE_path）与计算每条链路的频谱使用熵不同，计算路径的频谱使用熵时是针对组成路径的所有链路上的同一位置频隙使用情况进行类似标记，然后进行异或计算。最后将所得结果进行平均便得到该路径的频谱使用熵。如下图2.3所示：图2.3 路径使用熵的计算方法Fig.2.3 Calculation method of path using entropy（3） 计算整个网络的频谱使用熵（UE_network）采用由浅入深地方式，想要计算整个网络的频谱使用熵，我们可以将整个网络看作一条较长的路径。路径中每个链路的先后顺序并不会影响结果。然后我们按照步骤（2）中的计算方法得出该路径的频谱使用熵UE_path,即可表示整个网络的频谱使用熵UE_network。2.2.2基于链路状态的频谱碎片评估模型基于链路状态的频谱碎片评估模型依据的是链路上被使用的频谱块和未被使用的频谱块之间的数目及相互位置关系的综合。这就不得不提到频谱紧密度(Spectrum Compactness,CS)概念，其结果用Clink来表示,具体公式2.1如下： （2.1）公式2.1中表示所有状态在使用中的频谱的最大位置；则表示在使用状态的频谱的最小位置；k表示在频谱位于与中的未被使用的频隙的数量；表示频谱资源中第i个频隙是否被占用，被使用则为1,未被使用则为015。图2.4是对链路进行CS计算的简单示例。图2.4 链路频谱紧密度计算示例Fig.2.4 Calculating example of link spectrum tightness2.3路由与频谱分配问题路由与频谱分配问题（Routing and Spectrum Assignment,RSA）,即自适应业务宽带需求方式建立一条端到端的传输路径，并为光路径分配合适的通信参数，是灵活栅格光网络中一项非常重要的问题16。RSA问题可以分为两部分即R-路由分配及SA-频谱分配，与传统光网络的路径和波长分配算法（Routing and Wavelength Allocation, RWA）问题相比都需要一定的约束限制，但RSA问题17-18比RWA约束更加严格。传统固定栅格的WDM网络的RWA只需要满足波长不重叠和波长一致性约束条件，但RSA的约束条件更为复杂，需要满足：1.频谱一致性限制，即沿路由每条上分配相同的频谱资源；2.频谱不重叠限制，即每个连接请求在频谱资源上所占用带宽之间必须隔离，也就是说在频谱轴上分配频谱资源时，每个连接请求之间所占用的频谱资源之间必须存在一定间隔-保护带宽；3.频谱连续性限制。在图2.5中可以一目了然地看到灵活栅格光网络中业务传输时，RSA要满足的三个约束条件的具体化。图2.5 RSA算法约束条件Fig.2.5 Constraint of RSA algorithm目前对RSA问题的研究可以大致三类：静态路由与频谱资源的分配规划，准静态路由与频谱资源的评估以及动态路径的建立与频谱分配方法。其中，静态路由与频谱资源分配问题已经被证明为NP-完全问题，其衡量的标准为对频谱资源的利用率19；在文献20中提到准静态路由与频谱分配问题，在准静态RSA算法中将路由资源分配与频谱资源分配分开处理，并用首次命中算法解决频谱资源分配问题；在动态路由与频谱资源分配问题上，由于业务请求的到来于离开在时间和空间上都是随机的，其粒度大小也多是不固定的，所以面临产生频谱碎片问题，频谱碎片程度也成为动态RSA问题必须考虑的重要指标。3基于频谱碎片感知的路由与频谱分配优化技术传统的光网络只是完成了基本传输数据的任务，对接入的业务采取一视同仁的服务策略，只关心任务的源节点与目的节点以及业务传递所需的带宽等最基本的信息，而对其业务粒度、优先级别等都未有考虑。在新型灵活栅格光网络中，由于频谱碎片问题的显现使得人们不得不在进行频谱资源分配时对到来业务的粒度进行考虑。基于此，本章提出了一种新的基于业务感知的频谱碎片评估模型，利用该模型对网络碎片程度达到量化目的。最后，以其为参考提出本文的最终成果即基于频谱碎片感知的路由与频谱分配算法，用来进行频谱资源分配的优化，达到通过对频谱资源合理分配来解决频谱碎片问题的目的。3.1 基于业务感知的频谱碎片评估方案现在已成型的频谱碎片评估方案有多种，典型的有上一章提到的基于链路状况的频谱碎片评估方案和基于频谱使用程度的频谱碎片评估方案。前者主要将资源占用与空缺的比例考虑进去，没有考虑到频谱资源连续性问题；后者重视频谱占用变化频率并重点考虑了频谱的连续性作为频谱碎片评估的标准，但是没有考虑频谱资源的分布及占用状况。文献20中有提出一种基于碎片融合度（Fragment Fusion Degree,FFD）的评估方案来进行频谱碎片程度的评估，将碎片与网络状态联系在一起，是频谱碎片评估方案的一种新路径。对于同一个网络拓扑并且资源占用状况相同时，会因为请求的业务粒度的大小不同而对网络造成不同的阻塞程度。所以当两个相同网络面对差别很大的业务粒度时，它们对碎片的容忍程度是不同的；同时，由于业务是动态的，所以网络对碎片的容忍程度；理论上也应该随时间产生动态的变化。针对以上因素考虑，我们提出了一种新的基于考虑动态业务粒度变化的频谱碎片评估方案基于业务感知的频谱碎片评估 （Fragment Traffic Degree,FTD ）模型。参数介绍 :详述该频谱碎片评估模型之前首先需要介绍所涉及到的变量和符号，使用最普遍的定义为GV,E,S的网络拓扑模型。其中网络交换节点（点）的集合为V，网络中链路（边）的集合为E，每条管线链路上的频率资源集合我们用S来表示。表3.1 TAFG算法模型中所用符号及其表示含义Table.3.1 TAFG algorithm used in model symbols and their meaning符号符号表示含义V表示网络拓扑中节点v 的集合E表示网络拓扑内链路e 的集合p表示网络拓扑中相邻链路e 组成路径的集合R表示业务请求需要粒度r 的集合Ev表示与节点v 相接连的链路e 的集合Tv表示与节点v 相接连的链路集合中，所有由两两链路组成的路径的集合Dv表示节点v 的度数sx i其中x 按情况可以是e、v、p，分别表示se、sv、sp 里的第i个频隙是否被使用，当被使用时则为1，为被使用时则为0se表示链路e上的频隙资源数组，并用sei表示其数组元素sv表示节点v上的频隙资源数组，其数组元素为节点ve相连的所有链路s值进行“或”所得的结果sp表示路径p上的频隙资源数组，数组元素为路径p上所有链路sv进行“或”所得结果Pr表示粒度r的业务请求到达的概率Cr表示粒度r 的业务请求到达的计数AxrAx 为数组表示对业务的承载能力（其中x 可为p、v ）。数组元素为Axr，其值反应对请求业务的粒度为r 时的承载能力，其取值范围为01Ap为数组，表示路径p 面对不同粒度的业务请求时的承载能力Av为数组，表示节点v 面对不同粒度的业务请求时的承载能力3.1.1业务概率的动态计算模型基于业务感知的频谱碎片评估中获得业务的出现概率很重要，因为在灵活栅格光网络中的业务是实时的也是不固定的，所以在更多的时候我们对将要面对的业务请求是未知的。 如果我们仅对当前网络中的业务进行统计来确定业务出现概率，存在的问题是：网络处理的业务中可能要处理的主要业务粒度类型其周期很短，每次统计时未被统计进去，而一些不常出现的业务粒度由于其存在周期很长，所以每次计数都会被统计进去。因此这种简单的统计方法存在很大不足，缺乏实时性。在本文中提出一种新对业务出现概率进行统计的方法即利用动态可变长队列。队列的特点是先入后出，我们记录的是每次请求的业务，网络的规模用队列的长度来表示，如图3.2所示，其中Cr表示粒度大小为r的业务在队列中的数量，再知道队列中总的任务数便可以算出相应业务类型的出现概率Pr。其中（a）状态为初始状态；（b）状态为业务粒度为3的业务请求到来并成功入列；（c）的状态为有业务完成时，对队列前端的业务执行出列操作；（d）状态表示业务粒度为4的请求到来，因为频谱资源不足等原因而被阻塞掉，但还是要进行相应的入列、出列操作，并对相应的C4进行更新操作。通过图3.2可以看出，我们关注的不是网络实际处理的业务，而是对业务的请求趋势进行记录。很容易得出业务概率的计算方法Pr如下式： (3.1)图3.2 任务请求队列具体变化Fig.3.2 Specific changes of task request queue3.1.2 路径对业务的承载能力我们用FTD-P来表示路径对业务的承载能力，下面我们将逐步得出路径P对业务的承载能力。（1） 首先，要得出及时的业务请求概率有关业务概率的计算方法我们在3.1.1中已经得出，在此，我们需要对Cr和队列进行更新操作，完成更新后便可以计算出相应业务出现概率Pr。在计算多条路径的Pr时，若网络状态并未发生改变，则对队列和Cr只进行一次更新操作便可。（2） 然后，是对路径频谱使用状况的计算由表3.1已经提出链路频谱使用状态的数组Sel=ue,1,ue,2,ue,s,一条路径可由多条链路组成。由于灵活栅格光网络中的RSA需要满足频谱一致性约束，所以我们通过“或运算”来计算某路径中存在的可用频谱资源的位置，即路径频谱使用状况Spj如公式3.2所示： (3.2)以图3.3为例，路径P由链路se1,se2,se3组成，经过“或运算”得出路径的频谱使用状况即所有链路频谱资源中的可分配位置。图3.3 路径频谱使用状况Fig.3.3 Using of path spectrum（3） 再然后，关于路径频谱对不同业务承载能力的计算在3.1.1中我们已经得到不同粒度业务的出现概率Pr，接下来我们需要计算每条路径对不同粒度业务的承载能力。以图3.3为例，路径P对业务粒度r为1的分配方式有5种，空载下的分配方式有12种，即相应的业务承载能力AP1= 5/12；路径P对业务粒度r为2的分配方式有3种，空载下的分配方式有11种，即相应的业务承载能力AP2= 3/11，以此类推，路径P对业务r的承载能力可由公式3.3得出 （3.3）其中APr的取值范围为0至1，当其取值为0时则表示该路径P对业务粒度为r的承载能力为零，即无法对其分配资源；当APr取值为1时则表示该路径为空载状态，其资源占用为空，表示能最大限度地进行资源分配。（4） 最后，对FTD_P进行计算在前文中我们已经对不同粒度业务请求出现的概率Pr以及路径P对相应业务的承载能力Apr进行了计算，所以，我们求出Ap的期望值，便为路径P的频谱碎片程度评估值即FTDPATH(p)，其计算见公式3.4 （3.4）FTD_P所表示的是路径P对网络业务的承载能力，其值越大表明对业务的承载能力越强，其值越小表明对业务承载能力越差，随后进行路径分配时，我们优先将业务安排到承载能力较强的路径中。3.1.3 网络对业务的承载能力仅仅计算路径对业务的承载能力是不够的，因为路径对业务的承载能力只反映出相邻节点之间的链路的频谱资源使用情况，我们需要进一步计算以网络节点为中心的并能够反映整个网络的频谱碎片程度（FTD-NW）的模型。与路径的频谱碎片程度计算类似：（1） 首先，对节点关于业务的承载能力进行计算在表3.1中，我们提出Ev，即与节点v 相接的链路e 集合；Tv，即与节点v 相连接的Ev （链路集合）中，由两两链路组成的所有路径的集合。我们先对Tv中的全部路径求出它们的FTD_P，然后得出均值便反映了该节点的承载能力FTDNODE，见式3.5。 (3.5)上式中,表示与节点v相连的任意两条链路组成路径的所有可能，以图3.4为例，节点v的度D其值为3，,Tv=p1,2、p1,3、p2,3,节点v的FTD_NODE值可用对这三条路径所得的FTD_P取平均值得出。图3.4 节点v业务承载能力计算Fig.3.4 The calculation of business carrying on node v（2） 最后，对整体网络进行业务承载能力的计算在上文中，我们先对路径的业务承载能力进行计算，然后由浅入深得出了节点的业务承载能力的计算，现在，我们对利用对所有节点的业务承载能力的平均来得出整体网络对业务的承载能力FTD_NW，见公式3.6： (3.6)在网络中，最小路径包含的链路个数为2，即网络中基本的路径即长度为2的路径，因为路径长为2时，网络若不能对相应业务进行承载，那路径长度增加时，便肯定也不能对业务进行承载。换而言之，整体网络对业务的承载能力用路径长为2时进行的网络对业务承载能力的计算便能很好地反映出来。3.2 基于频谱碎片感知的路由频谱动态分配 在本论文的绪论部分我们已经提到，通过碎片整理的方法来对网络资源进行优化时会导致业务的中断，从而影响网络的传输效率。因此另一种优化思路，即在进行资源分配时便进行碎片优化受到越来越多学者的研究，本文提出一种新的基于动态业务感知的路由频谱分配算法（Fragmentation-Traffic RSA,FT-RSA）,来实现在业务分配时考虑当时的频谱使用情况，进而减少分配之后产生的网络频谱碎片，实现资源优化目的。3.2.1 路径频谱碎片感知的PFT-RSA在3.1节中我们由浅入深地分别得出了基于动态业务的路径频谱碎片评估模型，节点频谱碎片评估模型以及网络频谱碎片评估模型，在本节，我们将以上频谱碎片评估模型应用到路由与频谱的分配算法中。路径频谱碎片感知的PFT-RSA算法主要步骤如下所示（当网络有任务请求到来，设其粒度大小为r）：（1）构建最简可用网络拓扑利用遍历的方法将网络拓扑G(V,E)中无法承载粒度为r的任务的链路去掉，即将链路中最大连续空闲频谱不足r个的链路去除掉，这样便可以初步除去多余的节点以及链路，从而得到更为简化的网络拓扑G(V,E)。此步便也得到了更简化的频隙资源数组se,sv,sp，目的是提高后续的计算效率，从而提高资源分配效率。（2）计算最短路径利用上述步骤得出的更简化的网络拓扑进行最短路径计算，得出k条最短路径（KSP算法21），其中的k值随拓扑大小而定。因上步已经将多余的链路去掉，所以这里可以直接用KSP算法得出k条最短路径。得出只包含这k条路径上的频隙资源数组sp。（3）计算路径的业务承载能力FTD_P，得出最优路径在（2）中我们已经得出k条最短路径，即集合P，现在我们对k条最短路径逐条计算相应的FTD_P值，并得出FTD值最大的路径（若不止一条则选取频谱位置较低的一条）。记录最优路径及其频隙位置。具体算法 我们用图3.5所示的流程图来表示：图3.5 最优路径得出算法流程图Fig.3.5 Algorithm flow chart to get optimal path（4）对业务请求队列进行刷新在3.1节中我们已经有所介绍，该算法的特点是针对业务请求概率为基础，所以无论业务是否成功被建路我们都要将它记录下来。对业务请求概率进行更新，应用到下一次的RSA计算中去。即更新相应Cr以及队列，相应业务请求概率Pr同时更新。3.2.2 网络频谱碎片感知的NFT-RSA与路径频谱碎片感知的PFT-RSA相似，网络频谱碎片感知的NFT-RSA是将前者计算过程中所依据的频谱碎片评估模型由FTD_P换成FTD_NW,从而能够更全面迎合整体网络的具体情况，得出更可靠结果。同样针对粒度为r的任务到来，步骤如下：（1） 构建最简可用网络拓扑同样利用遍历的方法将网络拓扑G(V,E)中无法承载粒度为r的任务的链路去掉，即将链路中最大连续频谱不足r个的链路去掉，这样便可初步除去多余节点和链路，得到更为简化的网络拓扑G(V,E)。此步的目的是提高后续计算效率，从而提高资源分配效率。（2） 计算最短路径利用上述步骤得出的网络拓扑G进行最短路径计算，得出k条最短路径（通过KSP算法），同样的，其中的k值随拓扑G的大小而定。（3） 计算网络的业务承载能力FTD_NW，得出最优路径 与计算路径的业务承载能力来得出最优路径的过程类似，通过上述步骤（2）的KSP算法得出k条最短路径，然后采取逐条路径虚拟其资源被使用、计算此时网络的业务承载能力即FTD_NW值并记录、释放虚拟被使用的资源，最终选取使得网络的业务承载能力最大的路径即为最优路径。（4） 对请求业务队列进行刷新同样，无论最后是否成功对请求业务进行传输建立，最后都要对请求业务队列进行刷新，得出最新的业务请求概率，为下次的路径和频谱资源分配做准备。无论是对路径感知的PFT-RSA算法还是对网络感知的NFT-RSA算法，其大致的处理思路都是类似的。两者的主要区别在于最优路径的选取是基于使得路径对业务的承载能力最大还是网络对业务的承载能力最大。其整体算法流程图见图3.5。图3.5 基于频谱碎片感知的FT-RSA算法流程图Fig.3.5 Algorithm flow chart basing on the debris perception of FT-RSA4 实验仿真与结果分析首先我们验证本文提出来的FTD是否能有效地反映网络的频谱碎片程度，然后将本文提出的PFT-RSA算法和NFT-RSA算法与KSP路径计算后采用首次命中资源使用（First-Fit,FF）方式算法比较，验证PFT-RSA和NFT-RSA能否有效降低网络碎片程度从而降低网络阻塞率。4.1仿真环境 本节针对两种典型的网络拓扑进行数值仿真，分别为有14个节点和21条链路的NSFNET网络以及有11个节点和26条链路的COST239网络。如图4.1所