虚拟化光无线融合接入网多路径可靠传输机制

邹 虹，陈 霄

(重庆邮电大学 光通信与网络重点实验室，重庆 400065)

光无线(Fiber-Wireless， FiWi)融合接入网是由前端无线网状网(Wireless Mesh Network，WMN)和后端无源光网络(Passive Optical Network， PON)组成[1]，具有PON的高带宽、低损耗、传输稳定和WMN的易部署、支持移动性等优点，能够以更加灵活的方式为用户提供更高质量的接入服务．随着FiWi网络规模的逐步扩大，网络承载的业务种类也更加多样化，这些都对FiWi接入网的可靠性设计提出了更高的技术要求[2-3]．因此，设计合理的可靠性保障机制，在保证网络可靠性的同时减少预留资源使用，提高网络资源利用率，成为FiWi网络的一大研究热点[4]．

近年来，FiWi接入网中业务的可靠性传输问题受到广泛关注．文献[5]提出一种基于辅助图的保障机制，解决了故障恢复过程中最大流最小跳问题，提高了资源利用率．文献[6]对光网络单元(Optical Network Unit， ONU)故障级的恢复路由进行了改进，通过建立备用无线路径以确保故障ONU到其可替代ONU之间存在有效路径．以上机制在一定程度上提高了业务传输的可靠性，但数据转发路径均由本地节点获知的部分网络信息决定，无法根据全局节点状态综合选择最优路径，导致时延增大，影响业务质量．文献[7]利用网络虚拟化在控制平面完成对拓扑路径及虚拟节点的最优分配利用，但是其采用加权轮询算法对资源进行调度，并没有利用虚拟化的全局视角优势对不同服务质量(Quality of Service， QoS)需求的数据流采用不同的权重分配方法．文献[8]提出多路径映射，将虚拟链路映射到多条物理路径上，提高了网络资源利用率．但其不区分业务大小，将业务全部通过多路径传输，增大了额外开销，无法均衡链路负载与链路传输开销之间的关系．文献[9]通过对链路采用全备份保护，虽然生存性得到了保障，但备份资源在主链路无故障的状况下长期处于闲置状态，导致了资源浪费．

针对上述问题，笔者在网络虚拟化的基础上综合考虑节点和链路的资源利用率及多径传输开销，提出一种按比例分配备份资源的多路径可靠虚拟网络映射(Multipath Reliable Virtual Network Embedding， MRVNE)算法．首先根据节点及链路的总资源与可用资源的比值选择节点及链路，有效保障了资源的负载均衡．其次，预留虚拟链路需求资源的一部分作为备份，提高了单链路故障的生存性及多链路故障状况下的高可靠性．最后，对网络资源需求不同的业务采用不同的方式进行资源分配，避免了对所有业务都进行多路径传输造成的资源竞争，减少了额外时延，提高了网络服务性能．

1 FiWi资源虚拟化

网络虚拟化技术将数据传输平面和控制平面分离，打破了物理网络和业务之间的强耦合．应用虚拟化方法对FiWi接入网进行资源抽象，使控制平面对整个网络资源进行集中控制调配．与传统FiWi网络相比，控制平面可以更加准确地获知节点和链路容量、当前负载及节点、链路故障情况等参数，进而更加合理地实现数据分流及多路径选择，同时有效避开网络中的故障节点和链路，极大地提高了网络资源利用率及传输可靠性[10]．

FiWi接入网虚拟化的过程就是将网络的物理资源抽象成虚拟资源的过程．通过抽象物理节点和链路ID、位置、功能属性、非功能属性等资源，屏蔽FiWi接入网中光域和无线域拓扑结构、链路带宽等网性能的差异．图1为融合网络虚拟化的整体架构，文中将虚拟化FiWi分为3层: 基础设施层(InFrastructure， InF)、虚拟化管理层(Virtualization Management， VM)以及网络服务层(Service Provider， SP)．其中InF层负责部署、管理和维护底层物理网络资源，主要包括光链路终端(Optical Linear Terminal， OLT)、ONU、无线路由器、链路等，通过虚拟化技术将底层物理资源抽象成功能实体为上层提供统一编程接口，屏蔽底层基础设施的差异．VM层负责组建虚拟网络并提供优化管理、资源回收等服务．SP层根据服务请求的特点生成面向虚拟化管理层的虚拟网请求．

图1 融合网络虚拟化模型

设备供应商作为基础设施层，其功能是为虚拟化管理层提供物理网络资源，并将资源信息抽象为加权无向图GS= (NS，ES)的方式同步到虚拟化管理层，其中，NS表示所有物理设备的集合，ES表示所有物理链路的集合;虚拟化管理层将抽象得到的虚拟资源表示为GV= (NV，EV)，进而管理虚拟资源．其中，NV表示所有虚拟节点的集合，EV表示所有虚拟链路的集合; 业务提供商作为网络服务层负责接收业务请求，当有业务到达时，SP根据业务特点生成面向虚拟化管理层的虚拟网请求，VM根据虚拟网请求组建虚拟网络．然后将组建好的虚拟网络反馈给SP．最后，通过开放的编程接口定制路由协议，将虚拟网络映射到物理网络进行传输．

2 最小化备份资源的多路径传输算法

2.1 多路径选取数学模型

网络虚拟化的资源集中控制及屏蔽异构性等优势为融合网络的多路径选择提供了更加准确的网络状态信息[11]．为有效减轻无线域网络对FiWi接入网吞吐量的限制，笔者提出一种线性优化算法MRVNE-OP，将业务在无线侧通过k条不相交路径进行传输，而PON侧由于光纤链路带宽资源较大，将业务通过单条链路传输．并在无线侧为其分配Breq/k带宽资源作为备份保护，而PON侧相邻ONU之间互为备份，以提高网络传输可靠性．将同一目的地址的业务按比例均分为k-1 条数据流，并为每条数据流分配标有顺序号的新数据包头进行传输．考虑到FiWi接入网中光纤一侧与无线一侧带宽的差异，选择ONU作为聚合节点，对数据流进行重组．令ps为虚拟链路ev分流后映射到物理网络的路径集合，假设虚拟链路ev∈EV有映射关系:

M(ev)=(f1，f2，…，fk) ,

(1)

物理链路es的剩余带宽为该链路总带宽与分流映射到该链路的各业务占用带宽之差，即

(2)

其中，B(es)指链路总带宽，b(fm)指各业务占用的链路带宽．

端到端路径可承受的带宽请求由该路径上最小的链路可用带宽决定，即

(3)

多路径传输会减少备份资源的使用，然而传输路径增多带来的额外开销也会随之增大，因此需要均衡传输路径的数量和开销．同时，每条路径的拆分都会产生路由列表的更新、源节点和目的节点的缓存及额外时延等开销．关于虚拟网络映射开销，从以下3方面进行考虑．

(4)

其中，C(ns)指物理节点的中央处理器(Central Processing Unit，CPU)处理能力，r(ns)指节点可用处理能力，s(ns)指节点ns转发数据占用的内存开销，权重因子的约束使算法优先选择负载较小的节点进行数据转发，保证了节点的负载均衡．

(2) 节点分流与合流开销．主要是指将虚拟链路映射为多条路径传输时，映射到底层网络的源节点和目的节点分裂与聚合k条路径转换占用的内存．用d1(ns，k)和d2(ns，k)分别表示在物理节点ns∈NS处分流与合流的开销，则节点的分流与合流开销为

d(ns，k)=d1(ns，k)+d2(ns，k) ,

(5)

虚拟链路分流与合流的总开销为

(6)

(3) 链路传输开销．该开销主要考虑物理链路的带宽和链路的质量，根据业务的不同要求，链路质量q(es)由链路稳定性、丢包率、故障率等指标进行衡量，q(es)∈ [0，1]．链路质量越差，q(es)值越低．同时，考虑到负载均衡，仍将链路总带宽与链路可用带宽的比值作为权重因子用以链路的选择．综合考虑链路质量、链路可用带宽及业务需求带宽因素，其开销为

(7)

其中，r(es)为当前该链路的可用带宽．由于k条路径中要预留一条路径作为备份，因此每条路径占用的带宽为b(ev)/ (k-1)．链路质量根据业务的QoS需求动态地作为权重进行衡量．

为了使用户在最小化备份资源保障网络可靠性的同时，以较小代价获得较优的网络服务，文中将上述3种开销之和最小化作为优化的目标函数，则

(8)

由于S(ev，ps)和D(ev，ps，k)是CPU执行速度单位MIPS，而L(ev，ps，k)的单位是Mbit/s，为统一单位，式中为S(ev，ps)和D(ev，ps，k)分别乘以一个权重因子α．目标函数最小，即使S(ev，ps)、D(ev，ps，k)、L(ev，ps，k)三者最小，目标函数越小，数据流在融合网络中传输越均衡，故障率越小，所需开销也越少．

约束条件物理节点的CPU资源必须能够满足虚拟节点的能力需求，即映射到物理节点上的所有虚拟节点资源请求应不超过物理节点的处理能力，即

(9)

并且在同一个虚拟网络中，每一个虚拟节点nv在基础设施层都有且只有一个物理节点与其对应，而一个物理节点至多被一个虚拟节点映射，因此有

(10)

同样，映射到链路上所有虚拟网络的带宽请求应不大于该条链路的总带宽．即对于所有包含该条链路的映射路径，其占用带宽之和应小于或等于该条链路的总带宽，即

上式是对链路可用带宽的要求，即源节点至目的节点间物理路径的可用带宽应不小于虚拟链路分流后的请求带宽．为简化计算过程，提高搜索效率，文中将虚拟链路带宽平均分配，以均分后的值作为参考．

2.2 启发式业务分流可靠传输

上述混合线性规划MRVNE-OP对于小规模网络可快速找到问题的最优解，但随着虚拟网络规模增大，计算时间变得让人难以接受．因此，对于大规模网络，笔者提出一种可扩展的贪婪算法MRVNE用于业务多路径传输．该算法通过构建广度优先搜索树寻找映射节点，通过最短路径法寻找链路的方式获得次优解．

算法首先构建一个广度优先搜索树GV，根节点是虚拟网络中最大CPU能力请求节点．然后将节点以CPU请求的大小递减的方式进行排序，并对每个虚拟节点建立满足条件的物理网络候选映射节点集合．且集合中元素也按照CPU能力递减的方式进行排序．最后以广度优先的方式将虚拟节点映射到两节点间存在k条最短路径 (k≥2) 的物理节点上．

在进行链路映射时，研究表明导致网络拥塞的业务量可能只占10%，这些业务的流量占总流量的90%，被称为“大象流”．而网络中90%的业务量，几乎只占总流量的10%，被称为“老鼠流”[11]．当FiWi接入网中存在大量并发业务时，对所有业务采用多路径传输会增大传输时延及乱序、丢包等不利因素．受文献[11]的启发，根据业务所需带宽大小的不同将业务进行动态区分，对“大象流”通过多路径传输而对“老鼠流”采取单路径方式传输，以减小各数据流对网络资源的竞争．虚拟化管理层根据虚拟请求及约束条件找到源节点与相应ONU间的k条路径后，记录每条路径的可用带宽容量，然后将其值降序排列．为了保证业务传输过程中始终有满足条件的路径作为备份保护，文中将降序排列后的可用带宽次大值作为区分大象流和老鼠流的标准．即

(13)

(14)

2.3 算法复杂度分析

在最小化备份资源的多路径传输算法中，针对小规模网络与大规模网络的不同特性，文中分别使用线性规划算法与启发式算法进行具体分析．

在基于线性规划的多路径选取模型中，假设网络中有n个节点，节点之间的连接概率为0.5．从期望意义上来说，在节点数目为n的网络中，任意源、目的节点间的中继节点数目为 logn级别，而在每次中继决策过程中，共有n种选择．因此，源、目的节点间总的路径数量为nlog n．此外，在节点选择与链路选择过程中，加入了限制条件，在每次选择过程中，选取整体开销最小的节点与链路，即每次从n个节点或链路中选择最优的1个节点或1条链路．根据上述分析，可得文中基于线性规划的多路径选取模型的时间复杂度为O(nnlog n)．

针对启发式业务分流可靠传输算法，首先，在节点选择过程中，使用广度优先搜索算法，其算法时间复杂度为O(n+e)，其中，n为物理节点的数量，e为节点间连接的链路数量．然后按照CPU请求大小对节点进行排序，经典排序算法的最优时间复杂度为O(nlogn)．因此，节点选择过程的整体时间复杂度为O(nlogn+n+e)．其次，在链路映射过程中，文中使用最短路径法寻找满足条件的路径集合，经过分析可知，最短路径法的整体时间复杂度为O(e(nlogn+e))．最后，故障恢复策略的整体时间复杂度为O(e)．根据上述分析，可得文中启发式业务分流可靠传输算法的整体时间复杂度为O((n+e+nlogn)(e(nlogn+e))+e)．相比于链路选择过程的时间复杂度，故障恢复过程的时间复杂度可忽略不计，因此，经过合理简化的启发式业务分流可靠传输算法的整体时间复杂度为O((n+e+nlogn)(e(nlogn+e)))．

根据上述分析可知，基于线性规划的多路径选取模型的时间复杂度为O(nnlog n)，即非多项式时间，而启发式业务分流可靠传输算法的时间复杂度为O((n+e+nlogn)(e(nlogn+e)))，其算法时间复杂度的最高指数形式为常值，远小于 logn，即为多项式时间．因此，其算法时间复杂度远低于基于线性规划的多路径选取模型的时间复杂度．

3 仿真分析

3.1 仿真环境设定

笔者使用NS2(Network Simulator 2)仿真平台验证所提机制性能，对比机制为文献[7]提出的全备份保护算法(Full Backup Scheme， FBS)和文献[12]提出的共享备份保护算法(Shared Backup Scheme， SBS)．网络拓扑由GT-ITM工具随机产生[13]，包括1个OLT，8个ONU，64个路由器．其中光纤链路带宽为 1 000 Mbit/s，无线侧带宽为 54 Mbit/s; 节点分流与合流开销均设为10单位，节点转发开销设为5单位，节点资源请求服从 [5 GHz，15 GHz] 均匀分布，链路带宽请求服从 [5 Mbit/s，50 Mbit/s] 均匀分布，网络请求服从λ= 0.05的泊松分布[14]．其中，每个ONU都有内置的无线通信模块，连接PON和mesh网络．虚拟节点间有虚拟链路的概率为50%，即n个节点的虚拟网络平均含有n(n-1)/4 条链路．每一个虚拟网络请求的存续时间满足均值为 1 000 个时间单位的指数分布．整个网络抽象后得到的物理资源由虚拟管理层统一调度．

图2 不同网络负载的网络接受率

3.2 仿真结果与分析

图2和图3表示不同负载时4种算法的接受率和备份带宽的关系．由图2可见，随着负载增大网络接受率均下降．负载较小时流量都是“老鼠流”，MRVNE、MRVNE-OP与FBS传输方式相似，备份资源占用较多．而SBS是备份资源共享，可用于传输的链路资源较多且接受率最高．随着负载增大，MRVNE及MRVNE-OP开始多路径传输，更有效地利用底层资源，表现出更高的请求接受率．而FBS和SBS不能很好的利用资源切片，当负载增大时其接受率下降较快．图3给出了备份资源分配情况，由于FBS进行1∶1备份保护，备份资源比例大于0.5．而SBS备份资源共享，其备份资源比例最小．MRVNE原则上随着路径增多备份资源比例无限减小．然而，由于资源开销的限制，k不可能无限增大，因此，其备份资源先下降后逐渐趋于稳定并接近SBS，比FBS方式节约了40%～50%的备份资源．图4给出了不同故障等级时的网络故障率．其中，故障等级为链路故障率与网络请求到达率之比(即γ=λF/λV)．由图可见，随着故障等级增加，故障率随之增大．其中，MRVNE-OP和MRVNE将业务通过多条路径传输，只有当虚拟链路映射的多条物理路径全故障时，虚拟链路才故障，因此，其故障率最低．FBS算法由于采用1∶1备份保护，故障时可以将其转移到备份路径，因此故障等级较小时，其性能表现优于MRVNE算法．随着故障等级增加，新生成的虚拟网络造成故障又会影响到已存在的网络，单路径传输的劣势使其故障率逐渐高于MRVNE算法．而SBS采取共享备份，当故障出现时，备份资源可能已被占用，因此故障率最大几乎是MRVNE-OP的两倍．

图3 不同负载备份资源比例图4 不同故障等级的网络故障率

文中所提机制的特点是传输路径越多，所需备份资源越少．然而传输路径增多带来的额外资源开销也会随之增大，因此要在路径条数和资源开销之间进行权衡．为了确定合适的路径条数k值，将一条虚拟链路在不同负载及路径条数下进行传输计算其开销．结果如图5所示，初始时，开销均随着k值增大而减小，这是因为当k=2 时相当于FBS情况，备份资源占用比例较大，同时考虑负载均衡导致链路开销较大．从k=4 之后，开销随着路径条数的增大而增大，这是因为路径的增多带来的节点转发，数据传输及分流与合流的额外开销随之增大．当路径超过6条之后，增加更加明显．并且当路径条数超出8时，较大的时延导致传输质量严重下降而无法进行仿真．图6给出了3种算法的平均传输开销．由图可见，FBS、SBS算法的开销相差不大，而MRVNE算法的开销几乎是前两者的2～3倍．这是因为FBS、SBS算法均是通过单路径传输，而MRVNE算法是多路径传输，额外占用的节点及链路增大了其传输开销．但这些额外开销使得网络负载均衡得到较好的实现，同时网络生存性得到了更好的保障，使网络具有更高的接受率，因此带来了更大的网络收益．

图5 不同链路的传输开销图6 不同网络负载时的平均传输开销

4 结 束 语

通过将FiWi接入网虚拟化，笔者利用虚拟管理层资源集中管理的优势，统一调度FiWi网络资源为用户提供服务．首先提出了FiWi网络虚拟化抽象模型，描述了各层之间的关联及各自职能．然后在虚拟化的基础上提出了一种按比例分配备份资源的多路径传输算法．最后通过仿真验证所提算法在网络可靠性及网络接受率方面均获得良好的性能．相比于FBS、SBS保护方案，文中所提算法用更少的备份资源保障了单链路故障的可恢复性及多链路故障的可生存性，并且有效地实现了负载均衡，提高了网络资源利用率．