一种基于碎片处理的公平路由与频谱分配方法
一种基于碎片处理的公平路由与频谱分配方法
【技术领域】
[0001] 本发明属于弹性光网络路由与频谱分配技术领域，设及一种基于碎片处理的公平 路由与频谱分配方法。
【背景技术】
[0002] 随着高清视频、云计算等带宽密集型业务的大量涌现，W光网络为基础的信息传 输设施在高带宽方面承受着越来越大的压力。由于现有的波分复用光网络(Wavelength Division Multiplexing,WDM)采用固定通道间隔，即将光层的带宽资源粗糖、均匀、刚性地 限制在一个波长量级上(一般为50GHz)，导致WDM光网络灵活性低、带宽浪费严重，难W支持 超100G业务的应用，已不能适应未来大容量、高带宽、可扩展的灵活传输需要。为此，基于正 交频分复用技术（〇：rthogonal Frequenc^y Division Multiplexing,OFDM)的弹性光网络 化lastic Optical化tworks，EONs)于2009年被提出。EON使用OFDM技术将光层的带宽分配 粒度降低到副载波信道的亚波长量级(6.25G化或12.5G化），即光层信号传输的基本单元不 再是粗粒度的波长，而是更精细粒度的"频隙"（Frequency Slot,FS)。当带宽需求不同的混 合粒度业务出现时，只要为其分配所需数目的FS。从而有效实现了光层资源的虚拟化和按 需配置，大大提高了网络带宽利用率和灵活率，W致其能够支持ITb/s的业务传输。
[0003] 路由与频谱分配(Routing and Spectrum Assi即ment,RSA)是实现弹性光网络高 带宽传输的最基本问题。弹性光网络特有的资源细粒度化为带宽分配带来了新的挑战，包 括如何满足频谱邻接性和频谱连续性的双重约束，如何降低频谱碎片对资源利用率的影响 及如何保证公平性等。文献[Jinno M,Kozicki B,Takara H,et al.Distance-adaptive spectrum resource allocation in spectrum-sliced elastic optical path network [J]. I邸E Communications Magazine，2010,48(8): 138-145.]从满足RSA双重约束的角度 出发，提出了一种距离自适应频谱资源分配方法W确保使用的频谱数目最少，频谱效率较 高，但也带来复杂度过高的问题。文献[化ristodoulopoulos K,Tomkos LVarvarigos E A.Elastic bandwidth allocation in flexible OFDM-based optical networks[J] .Journal of Li 曲 twave Technology,2011,29(9) :1354-1366.]将路由与频谱分配方法分 解为路由、调制和频谱分配两阶段分别处理，并采用模拟退火方法对业务排序优化，达到降 低计算复杂度、提高频谱利用率的目的，但并没有考虑频谱碎片的影响。为此，文献[Castro A,Velasco L,Ruiz M,et al.Dynamic routing and spectrum(re)allocation in future flexgrid optical networks[J].Computer 化 tworks,2012,56(12) :2869-2883.]提出频 谱重构方法为业务动态地提供所需的频隙，从而减少频谱碎片的产生、降低网络的阻塞率。 虽然W上文献针对弹性光网络路由与频谱分配问题上提出了不同的解决方案，但是都未考 虑不同粒度业务RSA的公平性问题。弹性光网络资源的充分利用和灵活调度是W牺牲公平 性为代价的，频谱粒度的细化使得业务的粒度稍大就可能不满足频谱邻接性和连续性的约 束，从而发生阻塞。而运种情况在W波长为基本分配单元的WDM光网络就没那么突出。可见， 带宽单位的细化导致混合粒度业务的阻塞率存在较大差异，运对弹性光网络中大粒度业务 带来严重影响，造成了网络总体性能的恶化。
[0004] 为此，文献[Fujii S,Hi;rotaY,Murakami K,et al .Path division method for fairness in dynamic elastic optical path networks[C]//2012International Conference on Photonics in Switching(PS2012),Ajaccio.France: IEEE press,2012: 1-3.]利用路径距离与调制的关系，将长跳业务分为几个短跳，并逐跳寻路的方法来避免单 个业务阻塞，达到降低网络阻塞率的效果。然而运种设计仅针对单个业务，缺少对混合粒度 业务间差距的处理。文献[Ma S,Wang Y,Guo B,et al.A fairness-aware dynamic spectrum allocation scheme in elastic optical networks[C]//0ptoElectronics and Communications Conference and Photonics in Switching(0ECC/PS2013),Kyoto 化pan: IE邸press ,2013:1-2.]首先将网络中频谱均匀分为几个区域，随后将阻塞率相差 最大的区域进行处理，从而提高公平性。但并未考虑频谱利用率。文献[马松威，郭秉礼，陈 新，等.弹性光网络中基于效用的公平性感知动态频谱分配方案（英文）[J].光子学报， 2014,43(7) :1-5.]利用效用函数来缩小不同粒度业务之间阻塞率差距，从而平衡公平性和 阻塞率之间的矛盾。但缺少对频谱碎片的处理，影响网络性能。文献[Bonani LH，dos Santos Tozetti A,Callegati F,et al.Routing issues on spectrum sharing and partitioning for flexible optical networks[C]//201416th International Conference on Transparent Optical Networks (ICT0N2014),Graz , Austria : IEEE press, 2014:1-4.]将网络平均分配为n个大小相同的区域，并在每个频谱区域传输相同粒 度的业务，从而降低频谱碎片形成的概率，但由于不同粒度业务需要的频隙数目不同，为不 同粒度业务分配大小相同资源可能会带来不公平的问题。文献[Callegati F，Bonani L， Lezama F,et al.Trunk Reservation for Fair Utilization in Flexible Optical 化tworks[J]. IE邸 Communication Letters,2014,18(5): 1-4.]将干线预留机制（Trunk Reservation，TR)引入到弹性光网络来处理公平性问题，即如果业务粒度超出口限，则阻塞 该业务。通过设定口限能够很好地实现不同粒度业务间的公平性，但公平性与阻塞率相惇， 因而方法保证公平性使得阻塞率较高。
【发明内容】
[0005] 有鉴于此，本发明的目的在于提供一种基于碎片处理的公平路由与频谱分配方 法，该方法通过考虑业务持续时间，能够W当前网络整体情形为依据，统筹考虑业务达到时 与业务离开后网络中资源的使用情况。
[0006] 为达到上述目的，本发明提供如下技术方案：
[0007] -种基于碎片处理的公平路由与频谱分配方法，在该方法中，将路由和频谱等网 络资源虚拟为"资源池"，通过利用二维矩形化eking模型求解满足频谱双重约束条件的"小 矩形块"；通过感知业务持续时间，计算业务的离开时间，为离开时间相近的业务分配邻近 的频谱资源，降低频谱碎片的产生;构建混合粒度业务的公平性模型，将相同粒度业务打包 成"小矩形块"来进行路由与频谱分配。
[000引进一步，在本方法中，所述由业务持续时间计算出业务离开时间为：tleaving = tarrivalWholding，其中tleaving、tarrival和tholding分别为业务的离开时间、达到时间和持续时间；
[0009]网络中可能存在多个离开时间相同的已分配业务，为确定优化路径，进行优化路 径选择法(Optimal Path SelectedPolicy,OPSP)，具体包括W下步骤：
[0010] 步骤1:在离开时间最接近的已分配业务附近寻找可用频隙，如果存在，则确定为 优化路径；
[0011] 步骤2:若步骤1得到的路径不唯一，则选择业务离去后释放连续频隙最大的；
[0012] 步骤3:优化路径若仍不唯一，选择频谱连续程度高的进行分配;频谱连续程度定 义为:Maxmize(2*x+y)，t含tieave，其中，x、y依次为业务离开产生在横轴和纵 轴的连续度。
[0013] 进一步，所述路由与频谱分配的方法为：首先根据混合粒度公平性模型将不同粒 度业务打包为传输块，然后通过KSP方法得到K条备选路径，再通过业务持续时间感知，根据 0PSP得到优化路径，若此时优化路径不唯一，根据二维矩形化eking模型基本原则尽可能选 择左下角的位置，进行紧凑布局，具体包括W下步骤：
[0014] 步骤1:将业务打包成传输块；
[0015] 步骤2:对每个传输块，通过k最短路径方法化-shodest-path, KSP)确定k条备选 路径集合;对于块内每个业务，依据0PSP步骤一选择路径，如果该路径唯一，则确定其为优 化路径;若存在多条运样的路径，则跳到步骤3;若存在一个业务无法找到优化路径，贝峭巧。 步骤5;
[0016] 步骤3:依据0PSP步骤二选出优化路径;如果存在多条优化路径，贝峭巧Ij步骤4;若 无法找到运样的路径，则跳到步骤5;
[0017] 步骤4:为确定优化路径，通过0PSP步骤Ξ进行筛选;若筛选结果唯一，则确定其为 优化路径;如果仍无法确定，则根据二维矩形化eking模型基本原则，尽可能选择左下角频 谱;否则，跳到步骤5;
[0018] 步骤5:阻塞该传输块内所有业务，方法结束。
[0019] 本发明的有益效果在于:本发明所述方法将路由和频谱等网络资源虚拟为"资源 池"，通过利用二维矩形化eking理论求解满足频谱双重约束条件的"小矩形块"；通过感知 业务持续时间，为离开时间相近的业务分配邻近的频谱资源，降低频谱碎片的产生;构建混 合粒度业务的公平性模型，将相同粒度业务打包成"小矩形块"来进行路由与频谱分配。
【附图说明】
[0020] 为了使本发明的目的、技术方案和有益效果更加清楚，本发明提供如下附图进行 说明：
[0021] 图1为二维矩形化eking示意图；
[0022] 图2为连续度示意图；
[0023] 图3为频谱分配示意图；
[0024] 图4为本发明所述方法的流程示意图。
【具体实施方式】
[0025] 下面将结合附图，对本发明的优选实施例进行详细的描述。
[0026] 图4为本发明所述方法的流程示意图，在该方法中，将路由和频谱等网络资源虚拟 为"资源池"，通过利用二维矩形化eking模型求解满足频谱双重约束条件的"小矩形块"；通 过感知业务持续时间，计算业务的离开时间，为离开时间相近的业务分配邻近的频谱资源， 降低频谱碎片的产生；构建混合粒度业务的公平性模型，将相同粒度业务打包成"小矩形 块"来进行路由与频谱分配。
[0027] 具体来说：
[0028] 由于本发明旨在加强网络资源分配的公平性、减小网络频谱碎片。相关概念及衡 量手段如下：
[0029] 一、公平性
[0030] 公平性是用来处理网络资源分配的平均性问题，适用于判断资源是否W-种平均 的方式分配给业务。弹性光网络的按需分配加剧了混合粒度业务阻塞率的差异，进而影响 业务的公平性。在本发明中定义公平性为判断资源对不同粒度业务的阻塞是否公平。
[0031 ] 为对公平性进行量化评估，提出公平因子(Fairness Index,FI)的概念。在此基础 上，针对混合粒度业务的公平性量化问题，提出混合粒度业务公平因子。为方便衡量，将粒 度相同的业务分为同一类，不同类别业务的公平性判断如下所示：
[0032] 定义1:混合粒度业务公平因子，即不同粒度业务类别间公平性的度量，如
巧示。1?表示m类业务阻塞率。η'表示网络中存在的业务类别数 目。FImulti-granularity为混合松度业务公平因子。
[0033] 其中，m类业务的阻塞率及斯可由
为阻塞 的m类业务数，而
为所有m类业务数。
[0034] Fie [0，1]表示公平性具有有界性，其值越接近1，表示公平性越好。反之，表示公 平性需要改善。如果各类业务阻塞率相同，即满足=/?，公平性最好，此时FI值 为1。如果各类业务阻塞率不一致，公平性会随着不一致程度的加剧而恶化。
[0035] 定理1:各类业务阻塞率越接近，公平性越好，当各类业务阻塞率完全相同时，公平 性最好。下面给出证明。
[0045] 可见当各类业务阻塞率完全相同时公平性优化。
[0046] 通过上述阐述可知，为提高混合粒度业务公平性，需尽可能减小各类业务阻塞率 差距。然而，弹性光网络的RSA过程需要满足频谱邻接性与连续性的约束。同时，业务在不断 地建立与拆除的过程中产生大量的频谱碎片，恶化了业务的阻塞率。为此，引入二维矩形 Packing模型、业务持续时间依次解决上述问题。最后，通过混合粒度业务公平性模型减小 不同粒度业务间阻塞率的差值。
[0047] 二、二维矩形化eking模型
[004引弹性光网络中频谱单位为FS，为满足混合粒度业务的传输要求，在RSA过程中需要 满足频谱连续性与邻接性的双重约束。为此，可将路由资源和频谱资源统一视为网络资源 良Γ资源池"，根据邻接性和连续性的约束条件，放入虚拟的"资源池"来一体化完成路由选 择和频谱分配。为此，引入二维矩形化eking模型。
[0049] 二维矩形化eking指在一个长、宽任意给定的大矩形框和有限个长、宽分别任意给 定的小矩形块，要求将运些小矩形块尽可能多地放入大矩形框内，使框的面积利用率达到 最大。类似的，可将大矩形框视为一个盛放网络资源的"资源池"，如图1(a)所示。该资源池 由不同路径矩形框组成，如图1(b)所示。其中，横轴为网络中所有的链路，纵轴为频谱。然 而，传统二维矩形化eking模型的特点为，小矩形块直接置入大矩形框;小矩形块的横轴、纵 轴都具有任意性。而本发明实施的二维矩形化eking模型，业务在业务矩形框，而不是大矩 形框内传输;正是由于运个原因，横轴，即传输路径是固定的。只有纵轴，即频谱是灵活可变 的。
[0050] 在业务确定路径后，将大矩形框中的对应链路取出组成业务矩形框，如图1(b)所 示。可见，只需保证业务横轴的连续即可满足频谱邻接性限制要求。同时，纵轴上的连续能 够保证频谱连续性约束得到满足。如此，便将RSA过程中满足两个约束条件的问题转化为解 决二维矩形化eking了。二维矩形化eking的基本原则为"先占角，后占边，最后占中屯、"，由 此决定在分配频谱时尽可能从各个业务矩形框的左下角开始进行分配。
[0051] 将网络资源分配问题转化为求解二维矩形化eking,能够保证频谱邻接性与连续 性的约束。通过二维矩形化eking基本原则能够保证分配的"紧凑性"。然而，不同于传统二 维矩形化eking中小矩形是已存在的，待分配业务是动态到来的，可能随时到达和离开。为 此，在进行路由选择和频谱分配时，必须要把业务持续时间考虑进来，W实现动态的小矩形 块填充大矩形框。
[0052] Ξ、业务持续时间的感知
[0053] 二维矩形化eking模型能较好地映射频谱双重约束。但需进一步考虑如何确定动 态业务的优化路径。为此，引入业务持续时间的概念。业务持续时间是指某个业务在网络中 存在的时长。而路径计算单元(Path Computation Element,PCE)技术及通用多协议标志交 换协议(Generalized Multi-Protocol Label Switching,GMPLS)的快速发展，使得网络在 线服务水平大幅提升，在业务达到后，可W有效感知到该业务的持续时间。可见，为使"资源 池"更有效地容纳动态业务，通过业务到达时间、业务持续时间计算出业务离开时间，并为 离开时间最接近的业务分配相邻频谱，从而尽可能使扮演"资源池"角色的大矩形框填入更 多的小矩形块(即业务），从而达到降低阻塞率、减小频谱碎片的目的。
[0054] 由业务持续时间可W计算出业务离开时间为: t leaving - tarrival + tholding ? ^ ψ tleaving、tarrival和tholding分别为业务的离开时间、达到时间和持续时间。网络中可能存在多 个离开时间相同的已分配业务，为确定优化路径，提出优化路径选择法（Optimal Path SelectedPolicy,0PSP)〇
[0055] 步骤1:在离开时间最接近的已分配业务附近寻找可用频隙，如果存在，则确定为 优化路径。
[0056] 步骤2:若步骤1得到的路径不唯一，则选择业务离去后释放连续频隙最大的。
[0057] 步骤3:优化路径若仍不唯一，选择频谱连续程度高的进行分配。频谱连续程度定 义为:Maxmize(巧x+y)，t含tieave。其中，x、y依次为业务离开产生在横轴和纵轴的连续度，如 图2所示。图2(a)中虚线内业务离开后如2(b)所示，此时，产生的连续度为3*x+4*2*y。
[0058] 业务持续时间根据现下网络状况选择备选路径。同时依据业务离开时 刻产生最大 可用频隙确定优化路径。正是由于运种最大可用频隙的选择，达到减小频谱碎片、提高资源 利用率的目的。然而，混合粒度的公平性的问题仍未解决。
[0059] 四、混合粒度公平性模型
[0060] 通过业务持续时间的引入避免当下频谱分配影响后续分配。但是，相较于WDM光网 络，弹性光网络的细粒度性及频谱碎片导致网络公平性下降，因而，混合粒度业务公平性问 题亟待解决。为此，提出混合粒度公平性模型W保证弹性光网络中混合粒度业务的公平性。 [0061 ] 假设网络中存在η'类粒度不同的业务，即G={Gi，G2L Gn'KGn'表示第η'类粒度相 同的业务。正如巧《 = (妓碱L游]表示每类业务包含j '个大小相同的业务。妨表示第m类业 务中的第j'个业务。现从各类业务中取出第j个业务组成传输块Bj，如B={Bi，B2L BJ与 Α = ·(巧，巧L巧所示。B={Bi，B2L BJ表示网络中包含j个传输块。Α = ·{Χ/，巧L巧;}表示每 个传输块包含η '个业务，&表示第j个传输块，其包含η '类业务中下标为j的业务。当某类业 务中不存在某一标号的业务时，用:0.'表不。
[0062] 业务达到后，依据W上过程完成传输块的划分。若对业务逐一处理，由于业务粒度 的不同，导致不同粒度业务间阻塞率的差异。现将不同粒度业务组成传输块，当块内某(个） 些业务无法传输则阻塞该传输块内所有业务。如此，避免了大粒度业务与小粒度业务阻塞 率的差异，保证了混合粒度业务的公平性。
[0063] 综上所述，混合粒度公平性能够减小混合粒度间阻塞率的差异，保证EONs中混合 粒度业务的公平性。
[0064] 五、路由与频谱分配方法
[0065] RSA问题的基本思路为:首先根据混合粒度公平性模型将不同粒度业务打包为传 输块。然后通过KSP方法得到K条备选路径，再通过业务持续时间感知，根据0PSP得到优化路 径，若此时优化路径不唯一，根据二维矩形化eking模型基本原则尽可能选择左下角的位 置，进行紧凑布局。下面具体阐述此方法的实现步骤。
[0066] 步骤1:将业务打包成传输块。
[0067] 步骤2:对每个传输块，通过k最短路径方法化-shodest-path,KSP)确定k条备选 路径集合。对于块内每个业务，依据0PSP步骤一选择路径，如果该路径唯一，则确定其为优 化路径。若存在多条运样的路径，则跳到步骤3。若存在一个业务无法找到优化路径，贝峭巧。 步骤5。
[0068] 步骤3:依据0PSP步骤二选出优化路径。如果存在多条优化路径，贝峭巧Ij步骤4。若 无法找到运样的路径，则跳到步骤5。
[0069] 步骤4:为确定优化路径，通过0PSP步骤Ξ进行筛选。若筛选结果唯一，则确定其为 优化路径。如果仍无法确定，则根据二维矩形化eking模型基本原则，尽可能选择左下角频 谱。否则，跳到步骤5。
[0070] 步骤5:阻塞该传输块内所有业务。
[0071] 步骤6:方法结束。
[0072] 下面W图3为例进行详细说明。假设网络中存在4条链路，每条链路包含8个频隙。 已存在8个业务:N1-N8。待处理业务为N9,大小为1FS，备选路径为C-F-G、C-B-G。各业务离开 时间如表1、表2所示。
[0073] 表1 业务N1-N4离开时间
[0074]
[00巧]表2业务N5-N9离开时间
[0076]
[0077]
[0078] 图3(a)为"资源池"，方便观察整个网络中各链路的使用情况。图3(b)-3(g)依次对 应根据式0PSP选择优化路径的过程，图3 (i)为根据二维矩形化eking基本原则选优化路径 的过程。图3(b)中，首先确定2、4、6为可用频隙，而图3(C)中没有与N9离开时间相同的业务， 因而确定优化路径为C-F-G。再结合离开时间，图3(b)中，N1和N2与N9同时离开，依据0PSP步 骤一选定N1、N2之间的频隙2。图3 (d)中，可用频隙为2、6、8。通过离开时间可知业务N1、N3、 N9同时离开。图3(e)中，可用频隙为2、4、6。通过离开时间可知业务N5、N9同时离开。此时，根 据0PSP步骤二进行选择。图3(d)中放在2、6号位置将依次产生5、7个可用频隙，而图3(e)中， 在2号位置将产生4个可用频隙。因而确定C-F-G为优化路径，并选定6号频谱位置。图3(f) 中，可用位置为2、6，同时N1、N4、N9恰好一同离开，并且产生的频隙均为6FSs。而图3(g)中， 可用位置只有2号位置，同时N5、N9-同离开，产生的频隙为4FSs。此时，根据OPSP步骤Ξ可 确定优化路径为C-F-G，由于位置6产生的频隙块更完整，选定6号频谱。图3化）中，可用位置 为2、6。根据式(6)-(8)确定2号位置最佳。在图3(i)中，可用位置为1、4,并确定1号位置最 佳。由于1号位置相较于2号位置更符合"左下"位置的原则，因而确定优化路径为C-B-G，优 化位置为1。
[0079]最后说明的是，W上优选实施例仅用W说明本发明的技术方案而非限制，尽管通 过上述优选实施例已经对本发明进行了详细的描述，但本领域技术人员应当理解，可W在 形式上和细节上对其作出各种各样的改变，而不偏离本发明权利要求书所限定的范围。
【主权项】
1. 一种基于碎片处理的公平路由与频谱分配方法，其特征在于:在该方法中，将路由和 频谱等网络资源虚拟为"资源池"，通过利用二维矩形Packing模型求解满足频谱双重约束 条件的"小矩形块"；通过感知业务持续时间，计算业务的离开时间，为离开时间相近的业务 分配邻近的频谱资源，降低频谱碎片的产生;构建混合粒度业务的公平性模型，将相同粒度 业务打包成"小矩形块"来进行路由与频谱分配。2. 根据权利要求1所述的一种基于碎片处理的公平路由与频谱分配方法，其特征在于： 在本方法中，所述由业务持续时间计算出业务离开时间为：tleaving=tarrival+tholding，其中 tleaving、tarrival和tholding分别为业务的尚开时间、达到时间和持续时间； 网络中可能存在多个离开时间相同的已分配业务，为确定优化路径，进行优化路径选 择法(OptimalPathSelectedPolicy，OPSP)，具体包括以下步骤： 步骤1:在离开时间最接近的已分配业务附近寻找可用频隙，如果存在，则确定为优化 路径； 步骤2:若步骤1得到的路径不唯一，则选择业务离去后释放连续频隙最大的； 步骤3:优化路径若仍不唯一，选择频谱连续程度高的进行分配;频谱连续程度定义为：Maxmize(2*x+y)，t2tieave，其中，X、y依次为业务离开产生在横轴和纵轴的连续度。3. 根据权利要求1所述的一种基于碎片处理的公平路由与频谱分配方法，其特征在于： 所述路由与频谱分配的方法为:首先根据混合粒度公平性模型将不同粒度业务打包为传输 块，然后通过KSP方法得到K条备选路径，再通过业务持续时间感知，根据0PSP得到优化路 径，若此时优化路径不唯一，根据二维矩形Packing模型基本原则尽可能选择左下角的位 置，进行紧凑布局，具体包括以下步骤： 步骤1:将业务打包成传输块； 步骤2:对每个传输块，通过k最短路径方法(k-shortest-path，KSP)确定k条备选路径 集合;对于块内每个业务，依据0PSP步骤一选择路径，如果该路径唯一，则确定其为优化路 径;若存在多条这样的路径，则跳到步骤3;若存在一个业务无法找到优化路径，则跳到步骤 5； 步骤3:依据0PSP步骤二选出优化路径;如果存在多条优化路径，则跳到步骤4;若无法 找到这样的路径，则跳到步骤5; 步骤4:为确定优化路径，通过0PSP步骤三进行筛选;若筛选结果唯一，则确定其为优化 路径;如果仍无法确定，则根据二维矩形Packing模型基本原则，尽可能选择左下角频谱;否 贝1J，跳到步骤5; 步骤5:阻塞该传输块内所有业务，方法结束。
【专利摘要】本发明涉及一种基于碎片处理的公平路由与频谱分配方法，属于弹性光网络路由与频谱分配技术领域。在该方法中，将路由和频谱等网络资源虚拟为“资源池”，通过利用二维矩形Packing模型求解满足频谱双重约束条件的“小矩形块”；通过感知业务持续时间，计算业务的离开时间，为离开时间相近的业务分配邻近的频谱资源，降低频谱碎片的产生；构建混合粒度业务的公平性模型，将相同粒度业务打包成“小矩形块”来进行路由与频谱分配。本方法能够满足频谱邻接性和连续性的双重约束，避免造成阻塞，提升了网络的整体性能。
【IPC分类】H04L12/721, H04L12/707, H04L12/927, H04Q11/00
【公开号】CN105490934
【申请号】CN201610049605
【发明人】熊余, 范雪, 刘书鸣, 王汝言
【申请人】重庆邮电大学
【公开日】2016年4月13日
【申请日】2016年1月25日
【技术领域】
[0001] 本发明属于弹性光网络路由与频谱分配技术领域，设及一种基于碎片处理的公平 路由与频谱分配方法。
【背景技术】
[0002] 随着高清视频、云计算等带宽密集型业务的大量涌现，W光网络为基础的信息传 输设施在高带宽方面承受着越来越大的压力。由于现有的波分复用光网络(Wavelength Division Multiplexing,WDM)采用固定通道间隔，即将光层的带宽资源粗糖、均匀、刚性地 限制在一个波长量级上(一般为50GHz)，导致WDM光网络灵活性低、带宽浪费严重，难W支持 超100G业务的应用，已不能适应未来大容量、高带宽、可扩展的灵活传输需要。为此，基于正 交频分复用技术（〇：rthogonal Frequenc^y Division Multiplexing,OFDM)的弹性光网络 化lastic Optical化tworks，EONs)于2009年被提出。EON使用OFDM技术将光层的带宽分配 粒度降低到副载波信道的亚波长量级(6.25G化或12.5G化），即光层信号传输的基本单元不 再是粗粒度的波长，而是更精细粒度的"频隙"（Frequency Slot,FS)。当带宽需求不同的混 合粒度业务出现时，只要为其分配所需数目的FS。从而有效实现了光层资源的虚拟化和按 需配置，大大提高了网络带宽利用率和灵活率，W致其能够支持ITb/s的业务传输。
[0003] 路由与频谱分配(Routing and Spectrum Assi即ment,RSA)是实现弹性光网络高 带宽传输的最基本问题。弹性光网络特有的资源细粒度化为带宽分配带来了新的挑战，包 括如何满足频谱邻接性和频谱连续性的双重约束，如何降低频谱碎片对资源利用率的影响 及如何保证公平性等。文献[Jinno M,Kozicki B,Takara H,et al.Distance-adaptive spectrum resource allocation in spectrum-sliced elastic optical path network [J]. I邸E Communications Magazine，2010,48(8): 138-145.]从满足RSA双重约束的角度 出发，提出了一种距离自适应频谱资源分配方法W确保使用的频谱数目最少，频谱效率较 高，但也带来复杂度过高的问题。文献[化ristodoulopoulos K,Tomkos LVarvarigos E A.Elastic bandwidth allocation in flexible OFDM-based optical networks[J] .Journal of Li 曲 twave Technology,2011,29(9) :1354-1366.]将路由与频谱分配方法分 解为路由、调制和频谱分配两阶段分别处理，并采用模拟退火方法对业务排序优化，达到降 低计算复杂度、提高频谱利用率的目的，但并没有考虑频谱碎片的影响。为此，文献[Castro A,Velasco L,Ruiz M,et al.Dynamic routing and spectrum(re)allocation in future flexgrid optical networks[J].Computer 化 tworks,2012,56(12) :2869-2883.]提出频 谱重构方法为业务动态地提供所需的频隙，从而减少频谱碎片的产生、降低网络的阻塞率。 虽然W上文献针对弹性光网络路由与频谱分配问题上提出了不同的解决方案，但是都未考 虑不同粒度业务RSA的公平性问题。弹性光网络资源的充分利用和灵活调度是W牺牲公平 性为代价的，频谱粒度的细化使得业务的粒度稍大就可能不满足频谱邻接性和连续性的约 束，从而发生阻塞。而运种情况在W波长为基本分配单元的WDM光网络就没那么突出。可见， 带宽单位的细化导致混合粒度业务的阻塞率存在较大差异，运对弹性光网络中大粒度业务 带来严重影响，造成了网络总体性能的恶化。
[0004] 为此，文献[Fujii S,Hi;rotaY,Murakami K,et al .Path division method for fairness in dynamic elastic optical path networks[C]//2012International Conference on Photonics in Switching(PS2012),Ajaccio.France: IEEE press,2012: 1-3.]利用路径距离与调制的关系，将长跳业务分为几个短跳，并逐跳寻路的方法来避免单 个业务阻塞，达到降低网络阻塞率的效果。然而运种设计仅针对单个业务，缺少对混合粒度 业务间差距的处理。文献[Ma S,Wang Y,Guo B,et al.A fairness-aware dynamic spectrum allocation scheme in elastic optical networks[C]//0ptoElectronics and Communications Conference and Photonics in Switching(0ECC/PS2013),Kyoto 化pan: IE邸press ,2013:1-2.]首先将网络中频谱均匀分为几个区域，随后将阻塞率相差 最大的区域进行处理，从而提高公平性。但并未考虑频谱利用率。文献[马松威，郭秉礼，陈 新，等.弹性光网络中基于效用的公平性感知动态频谱分配方案（英文）[J].光子学报， 2014,43(7) :1-5.]利用效用函数来缩小不同粒度业务之间阻塞率差距，从而平衡公平性和 阻塞率之间的矛盾。但缺少对频谱碎片的处理，影响网络性能。文献[Bonani LH，dos Santos Tozetti A,Callegati F,et al.Routing issues on spectrum sharing and partitioning for flexible optical networks[C]//201416th International Conference on Transparent Optical Networks (ICT0N2014),Graz , Austria : IEEE press, 2014:1-4.]将网络平均分配为n个大小相同的区域，并在每个频谱区域传输相同粒 度的业务，从而降低频谱碎片形成的概率，但由于不同粒度业务需要的频隙数目不同，为不 同粒度业务分配大小相同资源可能会带来不公平的问题。文献[Callegati F，Bonani L， Lezama F,et al.Trunk Reservation for Fair Utilization in Flexible Optical 化tworks[J]. IE邸 Communication Letters,2014,18(5): 1-4.]将干线预留机制（Trunk Reservation，TR)引入到弹性光网络来处理公平性问题，即如果业务粒度超出口限，则阻塞 该业务。通过设定口限能够很好地实现不同粒度业务间的公平性，但公平性与阻塞率相惇， 因而方法保证公平性使得阻塞率较高。
【发明内容】
[0005] 有鉴于此，本发明的目的在于提供一种基于碎片处理的公平路由与频谱分配方 法，该方法通过考虑业务持续时间，能够W当前网络整体情形为依据，统筹考虑业务达到时 与业务离开后网络中资源的使用情况。
[0006] 为达到上述目的，本发明提供如下技术方案：
[0007] -种基于碎片处理的公平路由与频谱分配方法，在该方法中，将路由和频谱等网 络资源虚拟为"资源池"，通过利用二维矩形化eking模型求解满足频谱双重约束条件的"小 矩形块"；通过感知业务持续时间，计算业务的离开时间，为离开时间相近的业务分配邻近 的频谱资源，降低频谱碎片的产生;构建混合粒度业务的公平性模型，将相同粒度业务打包 成"小矩形块"来进行路由与频谱分配。
[000引进一步，在本方法中，所述由业务持续时间计算出业务离开时间为：tleaving = tarrivalWholding，其中tleaving、tarrival和tholding分别为业务的离开时间、达到时间和持续时间；
[0009]网络中可能存在多个离开时间相同的已分配业务，为确定优化路径，进行优化路 径选择法(Optimal Path SelectedPolicy,OPSP)，具体包括W下步骤：
[0010] 步骤1:在离开时间最接近的已分配业务附近寻找可用频隙，如果存在，则确定为 优化路径；
[0011] 步骤2:若步骤1得到的路径不唯一，则选择业务离去后释放连续频隙最大的；
[0012] 步骤3:优化路径若仍不唯一，选择频谱连续程度高的进行分配;频谱连续程度定 义为:Maxmize(2*x+y)，t含tieave，其中，x、y依次为业务离开产生在横轴和纵 轴的连续度。
[0013] 进一步，所述路由与频谱分配的方法为：首先根据混合粒度公平性模型将不同粒 度业务打包为传输块，然后通过KSP方法得到K条备选路径，再通过业务持续时间感知，根据 0PSP得到优化路径，若此时优化路径不唯一，根据二维矩形化eking模型基本原则尽可能选 择左下角的位置，进行紧凑布局，具体包括W下步骤：
[0014] 步骤1:将业务打包成传输块；
[0015] 步骤2:对每个传输块，通过k最短路径方法化-shodest-path, KSP)确定k条备选 路径集合;对于块内每个业务，依据0PSP步骤一选择路径，如果该路径唯一，则确定其为优 化路径;若存在多条运样的路径，则跳到步骤3;若存在一个业务无法找到优化路径，贝峭巧。 步骤5;
[0016] 步骤3:依据0PSP步骤二选出优化路径;如果存在多条优化路径，贝峭巧Ij步骤4;若 无法找到运样的路径，则跳到步骤5;
[0017] 步骤4:为确定优化路径，通过0PSP步骤Ξ进行筛选;若筛选结果唯一，则确定其为 优化路径;如果仍无法确定，则根据二维矩形化eking模型基本原则，尽可能选择左下角频 谱;否则，跳到步骤5;
[0018] 步骤5:阻塞该传输块内所有业务，方法结束。
[0019] 本发明的有益效果在于:本发明所述方法将路由和频谱等网络资源虚拟为"资源 池"，通过利用二维矩形化eking理论求解满足频谱双重约束条件的"小矩形块"；通过感知 业务持续时间，为离开时间相近的业务分配邻近的频谱资源，降低频谱碎片的产生;构建混 合粒度业务的公平性模型，将相同粒度业务打包成"小矩形块"来进行路由与频谱分配。
【附图说明】
[0020] 为了使本发明的目的、技术方案和有益效果更加清楚，本发明提供如下附图进行 说明：
[0021] 图1为二维矩形化eking示意图；
[0022] 图2为连续度示意图；
[0023] 图3为频谱分配示意图；
[0024] 图4为本发明所述方法的流程示意图。
【具体实施方式】
[0025] 下面将结合附图，对本发明的优选实施例进行详细的描述。
[0026] 图4为本发明所述方法的流程示意图，在该方法中，将路由和频谱等网络资源虚拟 为"资源池"，通过利用二维矩形化eking模型求解满足频谱双重约束条件的"小矩形块"；通 过感知业务持续时间，计算业务的离开时间，为离开时间相近的业务分配邻近的频谱资源， 降低频谱碎片的产生；构建混合粒度业务的公平性模型，将相同粒度业务打包成"小矩形 块"来进行路由与频谱分配。
[0027] 具体来说：
[0028] 由于本发明旨在加强网络资源分配的公平性、减小网络频谱碎片。相关概念及衡 量手段如下：
[0029] 一、公平性
[0030] 公平性是用来处理网络资源分配的平均性问题，适用于判断资源是否W-种平均 的方式分配给业务。弹性光网络的按需分配加剧了混合粒度业务阻塞率的差异，进而影响 业务的公平性。在本发明中定义公平性为判断资源对不同粒度业务的阻塞是否公平。
[0031 ] 为对公平性进行量化评估，提出公平因子(Fairness Index,FI)的概念。在此基础 上，针对混合粒度业务的公平性量化问题，提出混合粒度业务公平因子。为方便衡量，将粒 度相同的业务分为同一类，不同类别业务的公平性判断如下所示：
[0032] 定义1:混合粒度业务公平因子，即不同粒度业务类别间公平性的度量，如
巧示。1?表示m类业务阻塞率。η'表示网络中存在的业务类别数 目。FImulti-granularity为混合松度业务公平因子。
[0033] 其中，m类业务的阻塞率及斯可由
为阻塞 的m类业务数，而
为所有m类业务数。
[0034] Fie [0，1]表示公平性具有有界性，其值越接近1，表示公平性越好。反之，表示公 平性需要改善。如果各类业务阻塞率相同，即满足=/?，公平性最好，此时FI值 为1。如果各类业务阻塞率不一致，公平性会随着不一致程度的加剧而恶化。
[0035] 定理1:各类业务阻塞率越接近，公平性越好，当各类业务阻塞率完全相同时，公平 性最好。下面给出证明。
[0045] 可见当各类业务阻塞率完全相同时公平性优化。
[0046] 通过上述阐述可知，为提高混合粒度业务公平性，需尽可能减小各类业务阻塞率 差距。然而，弹性光网络的RSA过程需要满足频谱邻接性与连续性的约束。同时，业务在不断 地建立与拆除的过程中产生大量的频谱碎片，恶化了业务的阻塞率。为此，引入二维矩形 Packing模型、业务持续时间依次解决上述问题。最后，通过混合粒度业务公平性模型减小 不同粒度业务间阻塞率的差值。
[0047] 二、二维矩形化eking模型
[004引弹性光网络中频谱单位为FS，为满足混合粒度业务的传输要求，在RSA过程中需要 满足频谱连续性与邻接性的双重约束。为此，可将路由资源和频谱资源统一视为网络资源 良Γ资源池"，根据邻接性和连续性的约束条件，放入虚拟的"资源池"来一体化完成路由选 择和频谱分配。为此，引入二维矩形化eking模型。
[0049] 二维矩形化eking指在一个长、宽任意给定的大矩形框和有限个长、宽分别任意给 定的小矩形块，要求将运些小矩形块尽可能多地放入大矩形框内，使框的面积利用率达到 最大。类似的，可将大矩形框视为一个盛放网络资源的"资源池"，如图1(a)所示。该资源池 由不同路径矩形框组成，如图1(b)所示。其中，横轴为网络中所有的链路，纵轴为频谱。然 而，传统二维矩形化eking模型的特点为，小矩形块直接置入大矩形框;小矩形块的横轴、纵 轴都具有任意性。而本发明实施的二维矩形化eking模型，业务在业务矩形框，而不是大矩 形框内传输;正是由于运个原因，横轴，即传输路径是固定的。只有纵轴，即频谱是灵活可变 的。
[0050] 在业务确定路径后，将大矩形框中的对应链路取出组成业务矩形框，如图1(b)所 示。可见，只需保证业务横轴的连续即可满足频谱邻接性限制要求。同时，纵轴上的连续能 够保证频谱连续性约束得到满足。如此，便将RSA过程中满足两个约束条件的问题转化为解 决二维矩形化eking了。二维矩形化eking的基本原则为"先占角，后占边，最后占中屯、"，由 此决定在分配频谱时尽可能从各个业务矩形框的左下角开始进行分配。
[0051] 将网络资源分配问题转化为求解二维矩形化eking,能够保证频谱邻接性与连续 性的约束。通过二维矩形化eking基本原则能够保证分配的"紧凑性"。然而，不同于传统二 维矩形化eking中小矩形是已存在的，待分配业务是动态到来的，可能随时到达和离开。为 此，在进行路由选择和频谱分配时，必须要把业务持续时间考虑进来，W实现动态的小矩形 块填充大矩形框。
[0052] Ξ、业务持续时间的感知
[0053] 二维矩形化eking模型能较好地映射频谱双重约束。但需进一步考虑如何确定动 态业务的优化路径。为此，引入业务持续时间的概念。业务持续时间是指某个业务在网络中 存在的时长。而路径计算单元(Path Computation Element,PCE)技术及通用多协议标志交 换协议(Generalized Multi-Protocol Label Switching,GMPLS)的快速发展，使得网络在 线服务水平大幅提升，在业务达到后，可W有效感知到该业务的持续时间。可见，为使"资源 池"更有效地容纳动态业务，通过业务到达时间、业务持续时间计算出业务离开时间，并为 离开时间最接近的业务分配相邻频谱，从而尽可能使扮演"资源池"角色的大矩形框填入更 多的小矩形块(即业务），从而达到降低阻塞率、减小频谱碎片的目的。
[0054] 由业务持续时间可W计算出业务离开时间为: t leaving - tarrival + tholding ? ^ ψ tleaving、tarrival和tholding分别为业务的离开时间、达到时间和持续时间。网络中可能存在多 个离开时间相同的已分配业务，为确定优化路径，提出优化路径选择法（Optimal Path SelectedPolicy,0PSP)〇
[0055] 步骤1:在离开时间最接近的已分配业务附近寻找可用频隙，如果存在，则确定为 优化路径。
[0056] 步骤2:若步骤1得到的路径不唯一，则选择业务离去后释放连续频隙最大的。
[0057] 步骤3:优化路径若仍不唯一，选择频谱连续程度高的进行分配。频谱连续程度定 义为:Maxmize(巧x+y)，t含tieave。其中，x、y依次为业务离开产生在横轴和纵轴的连续度，如 图2所示。图2(a)中虚线内业务离开后如2(b)所示，此时，产生的连续度为3*x+4*2*y。
[0058] 业务持续时间根据现下网络状况选择备选路径。同时依据业务离开时 刻产生最大 可用频隙确定优化路径。正是由于运种最大可用频隙的选择，达到减小频谱碎片、提高资源 利用率的目的。然而，混合粒度的公平性的问题仍未解决。
[0059] 四、混合粒度公平性模型
[0060] 通过业务持续时间的引入避免当下频谱分配影响后续分配。但是，相较于WDM光网 络，弹性光网络的细粒度性及频谱碎片导致网络公平性下降，因而，混合粒度业务公平性问 题亟待解决。为此，提出混合粒度公平性模型W保证弹性光网络中混合粒度业务的公平性。 [0061 ] 假设网络中存在η'类粒度不同的业务，即G={Gi，G2L Gn'KGn'表示第η'类粒度相 同的业务。正如巧《 = (妓碱L游]表示每类业务包含j '个大小相同的业务。妨表示第m类业 务中的第j'个业务。现从各类业务中取出第j个业务组成传输块Bj，如B={Bi，B2L BJ与 Α = ·(巧，巧L巧所示。B={Bi，B2L BJ表示网络中包含j个传输块。Α = ·{Χ/，巧L巧;}表示每 个传输块包含η '个业务，&表示第j个传输块，其包含η '类业务中下标为j的业务。当某类业 务中不存在某一标号的业务时，用:0.'表不。
[0062] 业务达到后，依据W上过程完成传输块的划分。若对业务逐一处理，由于业务粒度 的不同，导致不同粒度业务间阻塞率的差异。现将不同粒度业务组成传输块，当块内某(个） 些业务无法传输则阻塞该传输块内所有业务。如此，避免了大粒度业务与小粒度业务阻塞 率的差异，保证了混合粒度业务的公平性。
[0063] 综上所述，混合粒度公平性能够减小混合粒度间阻塞率的差异，保证EONs中混合 粒度业务的公平性。
[0064] 五、路由与频谱分配方法
[0065] RSA问题的基本思路为:首先根据混合粒度公平性模型将不同粒度业务打包为传 输块。然后通过KSP方法得到K条备选路径，再通过业务持续时间感知，根据0PSP得到优化路 径，若此时优化路径不唯一，根据二维矩形化eking模型基本原则尽可能选择左下角的位 置，进行紧凑布局。下面具体阐述此方法的实现步骤。
[0066] 步骤1:将业务打包成传输块。
[0067] 步骤2:对每个传输块，通过k最短路径方法化-shodest-path,KSP)确定k条备选 路径集合。对于块内每个业务，依据0PSP步骤一选择路径，如果该路径唯一，则确定其为优 化路径。若存在多条运样的路径，则跳到步骤3。若存在一个业务无法找到优化路径，贝峭巧。 步骤5。
[0068] 步骤3:依据0PSP步骤二选出优化路径。如果存在多条优化路径，贝峭巧Ij步骤4。若 无法找到运样的路径，则跳到步骤5。
[0069] 步骤4:为确定优化路径，通过0PSP步骤Ξ进行筛选。若筛选结果唯一，则确定其为 优化路径。如果仍无法确定，则根据二维矩形化eking模型基本原则，尽可能选择左下角频 谱。否则，跳到步骤5。
[0070] 步骤5:阻塞该传输块内所有业务。
[0071] 步骤6:方法结束。
[0072] 下面W图3为例进行详细说明。假设网络中存在4条链路，每条链路包含8个频隙。 已存在8个业务:N1-N8。待处理业务为N9,大小为1FS，备选路径为C-F-G、C-B-G。各业务离开 时间如表1、表2所示。
[0073] 表1 业务N1-N4离开时间
[0074]
[00巧]表2业务N5-N9离开时间
[0076]
[0077]
[0078] 图3(a)为"资源池"，方便观察整个网络中各链路的使用情况。图3(b)-3(g)依次对 应根据式0PSP选择优化路径的过程，图3 (i)为根据二维矩形化eking基本原则选优化路径 的过程。图3(b)中，首先确定2、4、6为可用频隙，而图3(C)中没有与N9离开时间相同的业务， 因而确定优化路径为C-F-G。再结合离开时间，图3(b)中，N1和N2与N9同时离开，依据0PSP步 骤一选定N1、N2之间的频隙2。图3 (d)中，可用频隙为2、6、8。通过离开时间可知业务N1、N3、 N9同时离开。图3(e)中，可用频隙为2、4、6。通过离开时间可知业务N5、N9同时离开。此时，根 据0PSP步骤二进行选择。图3(d)中放在2、6号位置将依次产生5、7个可用频隙，而图3(e)中， 在2号位置将产生4个可用频隙。因而确定C-F-G为优化路径，并选定6号频谱位置。图3(f) 中，可用位置为2、6，同时N1、N4、N9恰好一同离开，并且产生的频隙均为6FSs。而图3(g)中， 可用位置只有2号位置，同时N5、N9-同离开，产生的频隙为4FSs。此时，根据OPSP步骤Ξ可 确定优化路径为C-F-G，由于位置6产生的频隙块更完整，选定6号频谱。图3化）中，可用位置 为2、6。根据式(6)-(8)确定2号位置最佳。在图3(i)中，可用位置为1、4,并确定1号位置最 佳。由于1号位置相较于2号位置更符合"左下"位置的原则，因而确定优化路径为C-B-G，优 化位置为1。
[0079]最后说明的是，W上优选实施例仅用W说明本发明的技术方案而非限制，尽管通 过上述优选实施例已经对本发明进行了详细的描述，但本领域技术人员应当理解，可W在 形式上和细节上对其作出各种各样的改变，而不偏离本发明权利要求书所限定的范围。
【主权项】
1. 一种基于碎片处理的公平路由与频谱分配方法，其特征在于:在该方法中，将路由和 频谱等网络资源虚拟为"资源池"，通过利用二维矩形Packing模型求解满足频谱双重约束 条件的"小矩形块"；通过感知业务持续时间，计算业务的离开时间，为离开时间相近的业务 分配邻近的频谱资源，降低频谱碎片的产生;构建混合粒度业务的公平性模型，将相同粒度 业务打包成"小矩形块"来进行路由与频谱分配。2. 根据权利要求1所述的一种基于碎片处理的公平路由与频谱分配方法，其特征在于： 在本方法中，所述由业务持续时间计算出业务离开时间为：tleaving=tarrival+tholding，其中 tleaving、tarrival和tholding分别为业务的尚开时间、达到时间和持续时间； 网络中可能存在多个离开时间相同的已分配业务，为确定优化路径，进行优化路径选 择法(OptimalPathSelectedPolicy，OPSP)，具体包括以下步骤： 步骤1:在离开时间最接近的已分配业务附近寻找可用频隙，如果存在，则确定为优化 路径； 步骤2:若步骤1得到的路径不唯一，则选择业务离去后释放连续频隙最大的； 步骤3:优化路径若仍不唯一，选择频谱连续程度高的进行分配;频谱连续程度定义为：Maxmize(2*x+y)，t2tieave，其中，X、y依次为业务离开产生在横轴和纵轴的连续度。3. 根据权利要求1所述的一种基于碎片处理的公平路由与频谱分配方法，其特征在于： 所述路由与频谱分配的方法为:首先根据混合粒度公平性模型将不同粒度业务打包为传输 块，然后通过KSP方法得到K条备选路径，再通过业务持续时间感知，根据0PSP得到优化路 径，若此时优化路径不唯一，根据二维矩形Packing模型基本原则尽可能选择左下角的位 置，进行紧凑布局，具体包括以下步骤： 步骤1:将业务打包成传输块； 步骤2:对每个传输块，通过k最短路径方法(k-shortest-path，KSP)确定k条备选路径 集合;对于块内每个业务，依据0PSP步骤一选择路径，如果该路径唯一，则确定其为优化路 径;若存在多条这样的路径，则跳到步骤3;若存在一个业务无法找到优化路径，则跳到步骤 5； 步骤3:依据0PSP步骤二选出优化路径;如果存在多条优化路径，则跳到步骤4;若无法 找到这样的路径，则跳到步骤5; 步骤4:为确定优化路径，通过0PSP步骤三进行筛选;若筛选结果唯一，则确定其为优化 路径;如果仍无法确定，则根据二维矩形Packing模型基本原则，尽可能选择左下角频谱;否 贝1J，跳到步骤5; 步骤5:阻塞该传输块内所有业务，方法结束。
【专利摘要】本发明涉及一种基于碎片处理的公平路由与频谱分配方法，属于弹性光网络路由与频谱分配技术领域。在该方法中，将路由和频谱等网络资源虚拟为“资源池”，通过利用二维矩形Packing模型求解满足频谱双重约束条件的“小矩形块”；通过感知业务持续时间，计算业务的离开时间，为离开时间相近的业务分配邻近的频谱资源，降低频谱碎片的产生；构建混合粒度业务的公平性模型，将相同粒度业务打包成“小矩形块”来进行路由与频谱分配。本方法能够满足频谱邻接性和连续性的双重约束，避免造成阻塞，提升了网络的整体性能。
【IPC分类】H04L12/721, H04L12/707, H04L12/927, H04Q11/00
【公开号】CN105490934
【申请号】CN201610049605
【发明人】熊余, 范雪, 刘书鸣, 王汝言
【申请人】重庆邮电大学
【公开日】2016年4月13日
【申请日】2016年1月25日
最新回复(0)