WO2011144178A1

WO2011144178A1 - 联合优化的方法、装置和系统

Info

Publication number: WO2011144178A1
Application number: PCT/CN2011/075388
Authority: WO
Inventors: 张洪波; 施广宇; 文刘飞; 徐向阳
Original assignee: 华为技术有限公司
Priority date: 2010-10-30
Filing date: 2011-06-07
Publication date: 2011-11-24
Also published as: EP2515478A4; US20130117443A1; RU2520354C2; EP2515478A1; CN102130824A; BR112012022286A2; US9003029B2; RU2012137874A; EP2515478B1; CN102130824B

Abstract

本发明实施例公开了一种联合优化的方法、装置和系统，其中，联合优化方法包括：将全网的联合优化分解成在各个子网中执行联合优化，对子网外服务器的带宽需求看成对所述端口上的虚拟服务器的带宽需求，各子网迭代执行联合优化，将执行联合优化的结果应用到网络中。本发明实施例通过对子网外服务器的带宽需求看成对所述端口上的虚拟服务器的带宽需求，在各子网迭代执行联合优化，并将执行联合优化的结果应用到网络中，从而实现并行执行全网联合优化，同时提高网络的性能和用户使用网络时的体验。

Description

联合优化的方法、装置和系统

本申请要求于 2010 年 10 月 30 日提交中国专利局、申请号为 201010525399.7、发明名称为 "联合优化的方法、装置和系统" 的中国专利申请的优先权，其全部内容通过引用结合在本申请中。

技术领域

本发明涉及通信技术领域，尤其涉及一种联合优化的方法、装置和系统。

背景技术

ISP ( Internet Service Provider,互联网服务提供商 )的角色主要是提供互联网接入，需要解决流量工程（TE, Traffic Engineering )的问题，即为流量指定最优的路径以最小化网络的拥塞， CP ( Content Provider, 内容提供商）的角色是向用户提供所需的内容，需要解决服务器选择（SS, Server Selection ) 的问题，即为不同的用户指定最优的服务器以最小化端到端的时延。当 ISP和 CP 分别独立完成 TE和 SS时，从全网的角度看并不是一种全局最优的状态。

为了获得全网的最优性能，现在人们开始尝试 TE和 SS的联合优化（ Joint Optimization ), 利用博弈论中的纳什议价解（ NB S , Nash Bargain Solution )及凸优化技术对给定的 TE和 SS这两个最优化问题实现合作博弈，以期达到全局最优的平衡。

利用 NBS建立的 TE和 SS联合优化数学模型为一个带约束的凸优化问题，现有技术存在一种基于集中式方式的联合优化求解方法，该方案假定某个计算设备收集优化问题求解所需的全网状态信息，进而釆用集中式方式获取系统的最优解，并将最优解作用到网络，从而执行路由变更策略和新的服务器选择策略。但该方案扩展性较差，随着网络规模的扩大，收集信息和计算所耗费的时间将急剧增加，如果要将联合优化作用到规模较大的网络，如整个城域网甚至全国骨干网，则现有的联合优化方法对网络产生作用的实时性将很难得到保证。

发明内容

本发明实施例提供一种联合优化的方法、装置和系统，有效降低联合优化的计算量和复杂度，提高全网的性能和效率。

联合优化方法，包括：获得所述子网的链路信息、服务器及带宽信息、用户需求信息；所述服务器及带宽信息包括所述子网每个对外端口的虚拟服务器带宽，所述虚拟服务器带宽为所述子网通过所述对外端口对子网外服务器需求的带宽；

根据链路信息、服务器及带宽信息、用户需求信息得到所述子网的最优路由参数和服务器选择参数；

根据最优路由参数和服务器选择参数得到所述子网每个对外端口的优化入口带宽；

比较每个对外端口的优化入口带宽和虚拟服务器带宽，若所有对外端口的优化入口带宽和虚拟服务器带宽的比较结果均小于设定误差，则在所述子网中应用所述最优路由参数和服务器选择参数。

本发明实施例提供一种联合优化计算装置，包括：

参数釆集模块：用于获得所述子网的链路信息、服务器及带宽信息、用户需求信息；所述服务器及带宽信息包括所述子网每个对外端口的虚拟服务器带宽，所述虚拟服务器带宽为所述子网通过所述对外端口对子网外服务器的带宽需求；

计算模块：用于根据链路信息、服务器及带宽信息、用户需求信息得到所述子网的最优路由参数和服务器选择参数，根据最优路由参数和服务器选择参数得到所述子网每个对外端口的优化入口带宽；

输出模块：用于比较每个对外端口的优化入口带宽和虚拟服务器带宽，若所有对外端口的优化入口带宽和虚拟服务器带宽的比较结果均小于设定误差，则在所述子网中应用所述最优路由参数和服务器选择参数，并输出所述最优路由参数和服务器选择参数。

本发明实施例提供一种通信网络，包括：

联合优化系统获得子网的链路信息、服务器及带宽信息、用户需求信息；所述服务器及带宽信息包括所述子网每个对外端口的虚拟服务器带宽；

根据链路信息、服务器及带宽信息、用户需求信息计算出所述子网的最优路由参数和服务器选择参数，得到此子网每个对外端口的优化入口带宽；比较每个对外端口的优化入口带宽和此对外端口的虚拟服务器带宽，若比较结果 d、于设定误差，则在网络中应用所述最优路由参数和服务器选择参数。本发明实施例提供一种联合优化系统，包括：

联合优化计算装置，用于收集链路信息、服务器及带宽信息、用户需求信息；获得路由参数和服务器选择参数，获得每个对外端口的优化入口带宽和优化出口带宽；

内容路由引擎，用于将联合优化计算装置获得的路由参数和服务器选择参数转化为应用在所在网络的路由参数和服务器选择参数。

由上述本发明实施例提供的技术方案可以看出，本发明实施例通过在各个子网中并行进行联合优化计算，将子网外的服务器看成本子网的入口处的设备上的虚拟服务器，此虚拟服务器的带宽为此端口对端子网联合优化计算出的优化出口带宽和子网此端口上的入口带宽减去入口背景流量中的较小者，通过虚拟服务器的带宽也就是子网之间的带宽耦合，在各子网迭代进行联合优化计算，从而获得网络的路由选择策略和服务器选择策略，在网络中应用此路由选择策略和服务器选择策略使得网络的性能和利用率最高。

附图说明

为了更清楚地说明本发明实施例中的技术方案，下面将对实施例描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动性的前提下，还可以根据这些附图获得其他的附图。

图 1执行联合优化的网络分解为两层的实施例；

图 2执行联合优化的网络分解为三层的实施例；

图 3是联合优化计算装置的实施例；

图 4是联合优化数学模型进行两级分解的实施例；

图 5是全网联合优化执行流程的实施例；

图 6是联合优化控制系统的实施例。

具体实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。下面对本发明实施例应用的通信网络进行举例说明。

图 1 为将执行联合优化的网络分解为两层，第一层为接入层，以 BAS ( Broadband Access Server, 宽带接入服务器）为单位划分子网，即 BAS及其下面连接的交换机、 DSLAM ( , Digital Subscriber Line Access Multiplexer, 数字用户线路接入复用器）等组成一个子网， BAS 及其上面连接的边缘路由器 ( BR, Border Router )、核心路由器（ CR, Core Router )等组成一个上层子网。在接入层，以 BAS为单位划分子网是一种划分子网的方法，也可以以边缘路由器或其它设备为范围划分子网。

图 2是将执行联合优化的网络划分为三层的实施例，第一层为接入层，以 BAS、边缘路由器为单位划分为多个子网，在中间层，以地域为单位划分为不同的子网，最上层是一个子网，包括出口路由器等网络节点。

需要说明的是，网络的分解也不限于两层或三层，可以分解为多层，当分解为多层时，从下往上可以依次称作第一层子网，第二层子网，第三层子网， ... , 第 M层子网，最上层的网络也可以称作上层子网，第一层子网也可以称作底层子网。

图 3 是联合优化计算装置的实施例，联合优化计算装置包括参数釆集模块、计算模块和输出模块。

参数釆集模块负责收集网络状态信息、服务器信息、用户需求信息、以及邻接子网输出的优化输出带宽，将釆集到的输入提供给计算模块；其中的网络状态信息包括链路带宽、链路的服务质量 QoS、链路的成本等，用户需求信息包括用户的集合、用户对内容的需求等，服务器信息包括服务器集合，服务器带宽，服务器集合包括子网内的服务器和邻接子网入口处的虚拟服务器，邻接子网输出的优化出口带宽是邻接子网进行联合优化计算后可以提供的出口带宽，此带宽作为邻接子网入口处的虚拟服务器的带宽。

计算模块接收参数釆集模块收集的网络状态信息、服务器信息、用户信息、以及邻接子网输出的优化输出带宽，执行联合优化算法计算，计算出此子网可以提供的出口带宽、需要的入口带宽、以及相应的路由策略和服务器选策策略，将结果提供给输出模块。

输出模块接收计算模块计算出的最优结果并将计算模块的计算结果，并比较本子网需要的入口带宽和邻接子网所能提供的出口带宽，如果两者之差在误差范围内，则提供路由策略和服务器选择策略给内容路由引擎。同时提供此子网可以提供的出口带宽给内容路由引擎。

为了进一步理解上述联合优化装置的实现原理，下面进一步阐述邻接子网入口处的虚拟服务器的原理，以及建立联合优化数学模型的原理：

子网内的用户可能从本子网内的服务器上下载内容，也可能从其它子网或上层子网的服务器那里下载内容，子网内的用户请求子网外的服务器需经过本子网和其它子网相连接的出口，因此以一个子网为单位来看，可以认为子网外的服务器就是位于本子网的入口处的设备上的虚拟服务器，邻接子网内所有服务器能提供的带宽之和、邻接子网的最大出口带宽、本子网的最大入口带宽中最小者，作为本子网入口处的虚拟服务器能提供的带宽。邻接子网内所有服务器能提供的带宽之和、邻接子网的最大出口带宽中的最 d、者也称作邻接子网的优化出口带宽。本文中如果没有特别说明，所说的子网的最大出口带宽是指本子网出口带宽减去出口背景流量后的值，所说的子网的最大入口带宽是指本子网入口带宽减去入口背景流量后的值。

对于该子网，假定用户集合 T为该子网内所有请求 CP内容的那些用户的集合，服务器集合 S为子网内所有服务器以及入口处的设备上虚拟的服务器组成的集合。子网内的服务器带宽为所述服务器能提供的带宽，而入口处的设备上虚拟的服务器带宽为不大于该子网入口带宽减去入口背景流量后的某个值，初始计算时，该值可根据网络信息统计预测得出，当邻接子网输出优化出口带宽后，入口处的设备上虚拟的服务器带宽为邻接子网输出优化出口带宽、本子网入口带宽减去入口背景流量之中的最小者。背景流的起始节点集合 I为子网内请求背景流的那些节点组成的集合，终止节点集合 J为城域网的出口节点，站在子网的角度也即假定入口处的设备上有个虚拟的背景流终止节点。

在此子网内，利用凸优化技术和博弈论的 NBS ( Nash Bargaining Solution, 纳什议价解）建立联合优化算法的数学模型，即在考虑链路信息、服务器及带宽信息和用户需求信息等约束条件下建立一个带约束的联合优化问题。对该最优化问题进行求解，得到一组最优值，这组值反映了 TE的最优路由变更策略和 SS的最优服务器选择策略。根据这组最优值可以计算出用户对服务器的带宽需求，其中也包括了对子网外服务器的带宽需求，也即入口处的设备上虚拟服务器的带宽需求，该带宽需求和所述子网在此端口上的最大入口带宽减去背景流量后的较小值作为此子网在此端口上的优化入口带宽。根据这组最优值还可以计算出所述子网内服务器可以通过所述端口向外提供的剩余带宽，该带宽和所述子网在此端口上的最大出口带宽减去背景流量后的较小值作为此子网在此端口上的优化出口带宽。

图 4是联合优化求解的一种实施例，对联合优化原问题进行第一级分解后的 SS-画 TE-NBS两个子问题站在链路、服务器和背景流终点的角度作进一步的第二级分解，使其分解为更小的可解子问题，减少算法执行的时间。

分解原理如下：

首先对所述网络的联合优化数学模型按照对偶分解法做第一级分解，将其分解为 SS-NBS和 TE-NBS两个子问题，以及 DualTE-SS主问题，且主问题 Γ>Μα/7¾- 通过分解法引入的价格变量、和来控制 -A^ 和 7¾-A¾ 这两个子问题。由于 -ΛΦ 和 7¾-A¾ 两个子问题仍为带约束的最优化问题，因此有必要做进一步的分解。此时，针对 SS-A^ 子问题，以链路 /和服务器 S 为单位做第二级分解，分解为 SS-NBS-L 和 SS-NBS-S 两个子问题，以及 DimlSS-NBS主 ^且主问题 wa/ -A^ 通过第二级分解引入的价格变量、和来控制 SS-NBS-L和 SS-NBS-S这两个子问题。由于 SS-NBS-L和 SS-NBS-S 这两个子问题已是最小的可解子问题，因而不必继续分解，否则仍需釆用类似分解法继续分解，直到得到最小的可解子问题。同理，针对 7¾-A¾ 子问题，以链路 1和背景流终点 j为单位做第二级分解，分解为 TE-NBS-L和 TE-NBS-J 两个子问题，以及 DiialTE-NBS主问题 , 且主问题 DiialTE-NBS通过第二级分解引入的价格变量和来控制 TE-NBS-L 和 7¾-A¾ -J这两个子问题。由于 TE-NBS-L和 7¾-A¾ -J这两个子问题已是最小的可解子问题，因而不必继续分解，否则仍需釆用类似分解法继续分解，直到得到最小的可解子问题。

上述的两级分解过程进一步详细描述如下：

一、联合优化的原始问题

利用凸优化技术和博弈论中的 NBS , 建立子网中联合优化问题的数学模型如下所示： maximize log(rE₀ -∑ g, (/ _{+ ) +} l₀g_(1¾ - (/ + )) Subject to ∑ V/

∑ r - ∑ r卜 I , {i,j)^SxT, _V V\ i}

Variables xf >0; 0≤ rf < 1, V( ,y) iS T; f_t ^cp; f_t ^bg 式中，（rE。， 5¾)表示现状，即 TE和 SS单独优化时获得的最优值； &(·)和 (·)分别为联合优化的 TE和 SS取定的代价函数，均为链路 /的函数； / 和^^ 分别表示链路 /的背景流量和从 isp角度看链路 /上首选的 CP流量；和分别表示链路 I的 CP流量和从 CP角度看链路 I上首选的背景流量；表示 (s, 对在链路 /上产生的 CP流量； _¾和分别表示（ , ）对的背景流量和（ , ·)对在链路 /上产生的背景流比重； ς、和 A分别表示链路 /的容量、用户的需求和服务器 S的带宽；为指示函数，表示当节点 V为节点时该函数取 1, 为除节点和 ·外的其它节点时该函数取 0; 和的含义与 I 相同； / e In(v)和 I e Out(v)分别表示流量流进节点 V的链路和流量流出节点 V 的链路。变量、 ^r' . 和即为联合优化问题所要求解的最优化变量。

对上式作部分拉格朗日变换，可得：

+i。_g(SS。 -∑ +W)+Y f -in

ι ι

+∑uc_l-f -f_l ^bs)

= log(7E₀ -∑_g/(^ +^)) +∑( ^¾ -ν,/Γ ~U^bg)

₊iog(SS₀ - j f + ^g)+∑_Vl f - 利用对偶分解法，上式可分解为 SS-NBS和 SS-NBS两个子问题，其中这两个子问题受主问题 D_Ma/_r£__ss(4, ^,ν,)的控制。

(1.1)、

Subject to f_t ^cp = _jX, V/

Variable ≥ 0, (s,t) SxT; (1.2)、 TE-NBS子问题 rE _ NBSif , ^p ) maximize log(7E₀

Subject to j ^g = ^ V/

(i Sx-T

∑ r卜 ∑ =1 , (i,j)^SxT, v V\{i}

Variable 0 < r < 1, V (， j)^Sx T;

(1.3)、主问题 D / _ss(/l,,〃,，v,)

令 SS-A^ 子问题目标函数的最大值为 Hd^A) , 7¾-A¾ 子问题目标函数的最大值为 , 其中 ' ' ；

G( ,v,) = log(rE₀ +f )) +∑( _lfl^,g' -vj - )

/ / 。则主问题可表示为：

minimize Dual_TE__ss (A_z ,μ ν_}) = Η{λ_} , , ) + 0{λ_} ,μ ν_ι) + ^λ_ιϋ_ι

ι

Variable λ_} > 0; μ ν, (5) 通过分析 SS-NBS子问题和 TE-NBS千 m 发现这两个子问题可根据在 Link, Server和背景流量终点的角度进一步分解，使其分解为更小的可并行处理的子问题。

二、 -ΛΦ 子问题的进一步分解

(1.1)中的 SS-NBS子问题 - NBSix J,"⁸)可进一步表述如下：

maximize log(^_{0 +} -

I

Subject t。 j^cp ， V/

∑ ∑ VseS

∑ = ∑ ， Vv^{ ^}

Variable x > 0, V(s,t)eSxT; f_t 这里，表示服务器 s服务的用户的集合， s(o表示为某个用户服务的服务器的集合。最后一个约束条件表示对于非服务器和用户的中间节点 V, 流进 V的流量等于从 V流出的流量，即对中间节点 V而言，满足流量守恒定律。该式的成立显而易见，故在生成拉格朗日表达式时未予考虑。

对上式作拉格朗日变换，可得：

+ ∑ ∑ ^χι ~^Μ, io_g(SS₀ - f +Jn f - j^ -\f +_P n

+ ∑rA-∑v_tM_t 这里， /_eJL(w)表示从服务器 s到用户所经过的链路。

層《5子问题依据链路 I 和服务器 S 分为两类子问题^-N^S- 和

SS-NBS-S , 其中这两个子问题受主问题 Z¾/a/_ss_爾 (ρ,,^,τ^)的控制。

(2.1)、 SS-A^ - 子问题： SS-NBS-Lif^J^) 链路 /:

maximize logiSS^^h^ +f_l ^bg)) +∑(v r ~ '⁸ ~ °^P + Ρ,/Π

1 1

Variable f_t ^cp; J""

(2.2)、 -A^S ^子问题： SS-NBSK 服务器 maximize -∑ Ρ,Ο ∑ xf

Variable x > 0

(2.3)、 -A^ 主问题：

令 SS-NBS-L子问题目标函数的最大值为 L_SS—_MS— 、 , SS-NBS-S子问题目标函数的最大值为 SSS—NBS JS,";) , 其中爾—》 0¾ -∑w/ ' +7_l ^bs'))+∑(v_lf

-Mr +p r')

则主问题可表示为：

minimize Dual_ss—_NBS (p, ,γ,,η,) = L_SS__NBS__L (p, ) +∑ S_SS__NBS__S (p,,Y_s, _t) + ^ Y_SB_S - ]_tM_t

(10) Variable p_t; y_s; r\_t 三、 7¾-A¾ 子问题的进一步分解

( 1.²)中的 TE-NBS子问题 rE _ NBS(r;^j , 可进一步表述如下

maximize log(rE₀ (/ + / - - A,/ "

Subject to f ∑ = W

∑ r卜 \, (i,j)^SxT (11)

∑ r卜 ∑ r/, (i,j)^SxT, v V\{i,j} Variable 0 < r < 1， V ( ， j)^S T; f_t ^cp 最后一个约束条件表示对于非 i节点和 j节点的中间节点 V, 流进 V的背景流量等于从 V流出的背景流量，即满足流量守恒定律。该式的成立显而易见, 故在生成拉格朗日表达式时未予考虑。

对上式作拉格朗日变换，可得：

L_TE w , 7 , ^)= iog(¾ (f^ + j ))+∑ ( ^― v ― x ^ )

( ^s + 7r ))+∑ (P ^ - v - ^ + d )

ll I I≡L J 这里， I e L{i,j)表示从 i到 j所经过的链路。 rE-Nas子问题依据链路 I和背景流终点分为两类子问题 rE-N^s - 和

TE-NBS-J, 其中这两个子问题受主问题 Dual_{TE s} (ζ_ι , τ.. )的控制。

(3.1)、 TE-NBS-L

链路 /:

maximize Ιο_&(ΤΕ₀-∑_§Ι(^ +/^) +∑(^ -v ~ ^^bg +ζ^)

(13)

Variable / ； f,^cp (3.2), TE-NBS-J子 ^. 背景流终点 j': maximize

V l:l In(j) leL(iJ) (14)

Variable 0 < r < 1

(3.3)、 ΤΈ-ΛΦ 主问题： DuU ^ij) 令 TE-NBS-L子问题目标函数的最大值为 L_TE—_NBS—_L ^ , 7¾-A¾-J子问题目标函数的最大值为 ^ , 其中

则主问题可表示为：

minimize Dual_TE__NBS (ζ, ,τ..) = L_TE__NBS__L +

Variable ζ{, r_t 计算模块按照上述的分解过程将原问题分解为计算量较小的两个子问题，计算出最优结果后将回馈给输出模块，输出模块将计算结果输出给内容路由引擎，该结果作用于网络上将会改变路由策略和服务器选择策略。其中，路由变更策略将按最优方式为每条路径分配流量，从而解决流量工程问题；服务器选择策略将作用到服务器（包括子网内虚拟的服务器），指定服务器可分配的带宽及服务器所服务的新用户集合。

图 5是全网联合优化的执行流程，待联合优化的网络分解成多个子网，在每个子网中分别进行联合优化求解，各子网在第一次求解时如果没有从邻接网络获得优化出口带宽值，设定入口处的设备上虚拟的服务器带宽为一初始值，该初始值为不大于该子网入口带宽减去入口背景流量后的某个值，该值可根据网络信息统计预测得出，也可以在此范围内任意选择一个值，比如该子网入口带宽减去入口背景流量的二分之一，如果从邻接网络获得优化出口带宽值，选择邻接网络优化出口带宽、该子网入口带宽减去入口背景流量中的最小值作为设定入口处的设备上虚拟的服务器带宽。

在各子网迭代执行上述的联合优化，当最终所有子网和上层子网的优化问题均收敛到最优值，进而达到 Pareto最优。系统收敛后的路由变更策略和服务器选择策略发送给网络中的相关网元。

整个执行过程描述如下：

步骤一，对下层网络中的每个子网，设定初始的假设入口带宽，参数釆集模块釆集子网的网络状态信息（如链路信息等）、服务器及带宽信息、用户需求信息，计算模块按照图 4的分解方法求解出此子网的最优路由参数和服务器参数。得出此子网可以提供的优化出口带宽，此处优化出口带宽是指端口的最大出口带宽和子网内服务器能提供的最大带宽中的最小者。得出此子网的优化入口带宽，也就是需要子网外服务器提供的带宽；

步骤二，如果存在非最上层的中间层子网，中间层子网的联合优化系统的参数釆集模块釆集相邻的下层子网计算出的优化出口带宽、以及所述中间层子网的网络状态信息（如链路信息等）、服务器及带宽信息、用户需求信息，设定的初始的中间层子网和更上层子网接口的假设入口带宽，计算模块按照图 4 的分解方法求解出此中间层子网的最优路由参数和服务器参数。得出此子网向上层网络中的子网和下层网络中的子网提供的优化出口带宽，此处优化出口带宽是指端口的最大出口带宽和子网内服务器能提供的最大带宽中的最小者。得出此子网的优化入口带宽，也就是需要子网外服务器提供的带宽；

步骤三，对最上层子网，子网的联合优化系统的参数釆集模块釆集相邻的下层子网计算出的优化出口带宽、以及所述子网的网络状态信息（如链路信息等）、服务器及带宽信息，计算模块按照图 4的分解方法求解出此子网的最优路由参数和服务器参数。得出此子网向下层网络中的子网提供的优化出口带宽，此处优化出口带宽是指端口的最大出口带宽和子网内服务器能提供的最大带宽中的最小者。得出此子网的优化入口带宽，也就是需要子网外服务器提供的带宽；

步骤四，用步骤三计算出的和下层子网接口的优化出口带宽替换步骤二中设定的初始的假设入口带宽，执行步骤二，用步骤二计算出的和下层子网接口的优化出口带宽替换步骤一中的设定初始的假设入口带宽，执行步骤一，如果计算出的假设入口带宽和优化入口带宽在误差范围内，输出最优路由参数和服务器参数并作用于相应子网。否则再次重复执行步骤一、步骤二、步骤三、步骤四。

图 6是联合优化系统的一种实施例，联合优化系统包括了内容路由引擎、联合优化计算装置，联合优化计算装置的组成参考图 3 , 图 6中还包括了联合优化系统与代理模块、命名解析引擎、内容 GET/PUT适配器、流量统计汇总器、请求统计汇总器、对端子网联合优化系统、传输 /转发引擎、拓朴维护模块之间的连接关系。代理模块（ Proxy ): 作为用户的代理，它建立起用户终端和联合优化系统的桥梁，亦可用来聚集用户的请求。它可部署在网络边缘，如部署在 DSLAM 上。

内容路由引擎（ Content Routing Engine ): 它决定了如何获得所需的内容。当它发现所需的内容不在本地緩存设备上时，它会使用命名解析引擎（Name Resolution Engine )获得拥有该内容的节点列表，作为服务器信息输入给参数釆集模块。内容路由引擎从联合优化计算装置的输出模块获得路由变更策略和服务器选择策略，并转化为可部署实施的路由变更策略和服务器选择策略，前者输入给传输 /转发引擎以执行底层的路由策略，后者输入给拓朴维护模块以执行内容层的服务器选择。

命名解析引擎（ Name Resolution Engine ): 主要返回具有用户所需内容的合适的节点列表。

内容 GET/PUT适配器：它从本地緩存设备中索取内容路由引擎所需的内容并返回给内容路由引擎，以便内容路由引擎将内容路由给目的用户。

流量统计汇总器（ Traffic Statistics Collector ): 汇总背景流量信息、链路信息等，并报告给参数釆集模块。

请求统计汇总器（ Requests Statistics Collector ): 汇总用户需求并发送给参数釆集模块。

对端子网联合优化系统：获取本子网联合优化计算装置计算出的优化出口带宽，对端子网利用此优化出口带宽得到执行联合优化所需的假设入口带宽，此带宽作为入口处的设备上虚拟的服务器的带宽。

参数釆集模块：它主要釆集用户请求，服务器列表信息，流量的动态特性，以及对端子网的优化出口带宽信息。

计算模块：利用优化分解理论，计算出最优的（用户，服务器）对，同时得出每个（用户，服务器）对所形成的端到端路径及每条路径上的流量配比。

输出模块：输出模块负责接收计算模块的最优计算结果并输入给内容路由引擎。

传输 /转发引擎：接收内容路由引擎的 IP层的指令，执行流量的传输，实现底层的最优路由。拓朴维护模块：接收内容路由引擎的应用层的指令，执行服务器选择，实现内容层路由。

联合优化系统的交互过程如下：

1. 代理模块完成客户端用户对内容的请求收集；

2. 命名解析引擎根据请求的内容名执行内容解析，得知用户对内容的需求信息并输入给请求发生器；

3. 内容路由引擎获得服务器信息，首先通过内容 GET/PUT适配器获得本地緩存设备的服务器信息，当本地緩存设备没有所需的内容时，再通过命名解析引擎获得具有用户所需内容的节点列表信息；

4. 参数釆集模块从请求发生器获得用户的请求信息，从内容路由引擎获得服务器信息，从流量发生器获得网络的状态信息（如背景流信息、链路信息等），以及从对端子网接口获得对端子网的出口带宽信息和入口带宽信息；

5. 计算模块利用参数釆集模块获得的信息利用优化分解理论执行联合优化计算，得出最优的（用户，服务器）对，同时得出每个（用户，服务器）对所形成的端到端路径及每条路径上的流量配比；

6. 输出模块将计算模块的最优计算结果输入给内容路由引擎；

7. 内容路由引擎从输出模块获得最优解，并转化为可部署实施的路由变更策略和服务器选择策略，前者输入给传输 /转发引擎以执行底层的路由策略，后者输入给拓朴维护模块以执行内容层的服务器选择。此外还向对端子网输入更新出口带宽和入口带宽时所需的相关信息；

8.传输 /转发引擎从内容路由引擎接收路由变更策略，以便修改底层路由，执行 IP层的路由变更策略；

9. 拓朴维护模块从内容路由引擎接收服务器选择策略，以便执行应用层的服务器选择，从而建立用户和服务器之间的映射关系。

本实施例将一个全局网络优化问题等价转化为若干个子网优化问题，相对于全网的联合优化问题，子网内的联合优化模型变量和约束条件比较小，计算量小。本实施例还公开了求解子网内的联合优化模型的方法，根据链路、服务器和背景流终点分解原数学模型，使其分解为更小的可解子问题，减少算法执行的时间。由于各子网之间仅通过带宽进行耦合，因此耦合关系比较松，这利于优化问题的求解。

本领域普通技术人员可以理解：实现上述方法实施例的全部或部分步骤可以通过程序指令相关的硬件来完成，前述的程序可以存储于一计算机可读取存储介质中，该程序在执行时，执行包括上述方法实施例的步骤；而前述的存储介质包括： ROM、 RAM, 磁碟或者光盘等各种可以存储程序代码的介质。

最后所应说明的是：以上实施例仅用以说明本发明的技术方案，而非对本域的普通技术人员应当理解：其依然可以对本发明的技术方案进行修改或者等同替换，而这种修改或者等同替换并不脱离本发明技术方案的精神和范围。

Claims

权利要求

1、一种网络联合优化方法，所述网络包括多个子网，其特征在于：获得所述子网的链路信息、服务器及带宽信息、用户需求信息；所述服务器及带宽信息包括所述子网每个对外端口的虚拟服务器带宽，所述虚拟服务器带宽为所述子网通过所述对外端口对子网外服务器需求的带宽；

2、根据权利要求 1所述的方法，其特征在于：

若并非所有对外端口的优化入口带宽和虚拟服务器带宽的比较结果均小于设定误差，则重复获得优化入口带宽，并比较优化入口带宽和虚拟服务器带宽的过程，直到比较结果小于设定误差。

3、根据权利要求 1所述的方法，获得对外端口的虚拟服务器带宽的方法包括：

如果获得所述对外端口对应的邻接子网的优化出口带宽，则所述对外端口处的虚拟服务器带宽为所述优化出口带宽和所述对外端口可利用入口带宽的较小者；

如果未获得所述对外端口对应的邻接子网的优化出口带宽，则所述对外端口处的虚拟服务器带宽为小于所述对外端口可利用入口带宽的某个值。

4、根据权利要求 1所述的方法，所述方法还包括：

根据计算出的所述子网的最优路由参数和服务器选择参数，得到所述子网每个对外端口的优化出口带宽。

5、根据权利要求 1所述的方法，其特征在于，所述根据链路信息、服务器及带宽信息、用户需求信息得到所述子网的最优路由参数和服务器选择参数包括：建立所述子网的联合优化数学模型；

对所述联合优化数学模型进行第一级分解，得到 SS-NBS和 TE-NBS两个子问题；

根据链路、服务器和背景流终点对所述 SS-NBS和 TE-NBS两个子问题作第二级分解； SS-NBS子问题的第二级分解包括，以链路 1和服务器 s为单位做第二级分解，分解为 SS-NBS-L 和 SS-NBS-S 两个子问题，以及 DualSS-NBS主问题，且主问题 DualSS-NBS通过引入的价格变量 A、 ^和控制 SS-NBS-L和 SS-NBS-S两个子问题； TE-NBS子问题的分解包括，以链路 1 和背景流终点 j为单位做第二级分解，分解为 TE-NBS-L和 TE-NBS-J两个子问题，以及 DualTE-NBS主问题，且主问题 DualTE-NBS通过引入的价格变量和控制 TE-NBS-L和 TE-NBS-J两个子问题；

根据分解后的联合优化数学模型计算所述子网的最优路由参数和服务器选择参数。

6、根据权利要求 1所述的方法，其特征在于，根据最优路由参数和服务器选择参数得到所述子网每个对外端口的优化入口带宽包括：

应用所述子网的最优路由参数和服务器选择参数，计算出用户通过所述对外端口的虚拟服务器带宽需求，以所述虚拟服务器带宽需求和此对外端口上的可利用入口带宽的较小值作为所述子网在所述端口上的优化入口带宽。

7、根据权利要求 4所述的方法，其特征在于，根据计算出的所述子网的最优路由参数和服务器选择参数，得到所述子网每个对外端口的优化出口带宽的步骤包括：

应用所述子网的最优路由参数和服务器选择参数，计算出所述子网内服务器可以通过所述对外端口向外提供的剩余带宽，所述剩余带宽和此对外端口上的可利用出口带宽的较小值作为所述子网在所述端口上的优化出口带宽。

8、根据权利要求 1所述的方法，其特征在于，所述链路信息包括：链路带宽、链路的服务质量 QoS、链路的成本之中的至少一个。

9、根据权利要求 1所述的方法，其特征在于，所述服务器及带宽信息包括：

子网内服务器的集合、每个服务器所能提供的带宽之中的至少一个。

10、根据权利要求 1所述的方法，其特征在于，所述用户需求信息包括：用户的集合、用户对内容的需求之中的至少一个。

11、一种联合优化计算装置，包括：

12、一种通信网络，所述网络包括多个子网，每个子网包括联合优化系统，其特征在于：

根据链路信息、服务器及带宽信息、用户需求信息计算出所述子网的最优路由参数和服务器选择参数，得到此子网每个对外端口的优化入口带宽；

比较每个对外端口的优化入口带宽和此对外端口的虚拟服务器带宽，若比较结果 d、于设定误差，则在网络中应用所述最优路由参数和服务器选择参数。

13、根据权利要求 12所述的通信网络，其特征在于：

所述子网包括第一层子网和一个或多个上层子网，第一层子网包括至少一个和上一层子网的端口，上一层子网包括和其下层子网端口，和更上层子网的端口；

从第一层子网开始计算所述子网的最优路由参数和服务器选择参数，得到此子网每个对外端口的优化入口带宽，最后最上层子网计算最优路由参数和服务器选择参数，得到此子网每个对外端口的优化入口带宽；比较每个子网的每个对外端口的优化入口带宽和此对外端口的虚拟服务器带宽，若比较结果小于设定误差，则在网络中应用所述最优路由参数和服务器选择参数。

14、一种联合优化系统，包括：