王浩学，姜明，付吉

（1.解放军信息工程大学，河南 郑州 450001；2.杭州电子科技大学 计算机学院，浙江 杭州 310018）

1 引言

面对大量差异化业务的规模化应用，现有网络构建方法因协议刚性分层、服务能力单一而无法适应，问题日趋凸现。 面向服务提供的一体化承载网络研究[1,2]摆脱传统网络技术体系束缚，以用户业务需求为驱动，构建逻辑承载网(LCN, logical carrying network)，提供多样化的网络服务。

逻辑承载网构建是通过全网综合管理系统，将网络服务需求映射到物理网络资源的过程，思想与虚拟网构建[3]有相似之处。虚拟网构建分虚节点映射和虚链路映射2个步骤，即将虚节点映射到具有最大可用资源的基础节点上[4,5]，以及将每个虚链路映射到 2个物理网节点间的最短路径上[5～7]，但算法只考虑此次映射成功率，未考虑网络整体负载状态，影响后续虚拟网的构建，尤其在物理资源比较分散时，无法充分利用粒度较小的物理资源。本文基于路径分割将建网需求映射到片资源，计算网络负载状态，以均衡利用物理资源，构建尽可能多的逻辑承载网，取得最大收益。

2 网络模型及问题描述

物理网络用无向多重图GS表示，GS无自环，顶点集合V( GS)为网络中的路由交换平台集合，边集E( GS)为链路集合。逻辑承载网是GS的子图GU，边集和顶点集分别记为E( GU)和V( GU)。逻辑承载网构建是将LCN构建需求映射到一个GU，即根据LCN的需求约束找到相应的E( GU)和V( GU)。

多个逻辑承载网建网需求到达时，研究问题抽象为多源多汇问题来求解，即在源、目节点对(si, ti)(i=1,…,N)间寻求满足建网需求的节点、链路集合。……