基于稳定淘汰演化和博弈的通信量疏导模式

提出一种IP over WDM光Internet中的基于稳定淘汰演化和博弈的通信量疏导模式.该模式基于分层图,采用评价函数,引入考虑种群个体多样性的进化策略和杂交操作,在每一代淘汰最差个体,寻找优化的通信量疏导方案,最小化网络相对成本,最大化用户通信量请求总体延迟满意度.仿真实现了该模式,在实际网络拓扑上进行了性能评价,并且与已有通信量疏导模式进行了对比.仿真结果表明,该模式是可行和有效的,具有较好的性能.     

一种基于博弈论的智能QoS静态通信量疏导模式

支持服务质量与提高带宽利用率是IP/DWDM光Internet需要解决的主要问题之一。该文引入博弈论知识和分层图思想,以最小化网络资源占用率和最大化总体QoS满意度为目标,设计了一种基于人工免疫算法的静态通信量疏导模式,支持网络提供方效用与用户效用的Nash均衡。仿真研究表明,该模式是可行的和有效的。     

基于捕食搜索策略的网格任务调度算法

为解决网格任务调度难题,设计了一种模仿动物捕食策略的网格任务调度算法SAPS(Scheduling Algorithm Based onPredatory Search)。该算法首先确定待搜索区域,将待搜索区域划分为若干子区域,然后对子区域依次进行区域搜索,在搜索过程中如在某个子区域发现较优解,则对此子区域进行精密搜索,如未发现较优解,则转到下一个子区域,直至遍历所有子区域。SAPS算法具有较好的全局搜索和局部搜索的能力,克服了Min-min算法单纯追求局部最优而缺少全局意识的缺点。试验结果表明,该算法能更有效地解决网格任务调度问题。     

IP/DWDM光Internet中通信量动态疏导算法

研究IP/DWDM光Internet中网状拓扑下的动态通信量疏导问题。网状拓扑下的通信量疏导问题已证明是NP难问题,需要采用启发式算法或智能优化算法来解决。针对动态通信量疏导问题,建立了网络和数学模型,提出了求解该问题的人工免疫算法,为新到达的通信量请求路由和分配带宽等网络资源,同时最小化满足该通信量请求的网络费用。为验证算法的可行性和有效性,用VC++6.0开发了一个仿真环境,同时以美国自然科学基金网NSFNET、中国教育和科研计算机网CERNET1和CERNET2以及欧洲巨人网GéANT等的骨干网拓扑为仿真用实例,与现有启发式算法进行性能比较,并对网络参数对算法的影响进行了分析。实验表明,提出的算法可以获取比现有启发式算法更加优化的解。     

基于捕食搜索策略的遗传算法研究*

针对标准遗传算法易陷入局部最优而出现早熟,提出了一种基于捕食搜索策略的遗传算法。该算法在进化中模拟动物捕食搜索的过程,并根据种群中个体最优适应值来动态改变交叉和变异概率,从而加强算法的全局搜索和局部优化的能力。仿真实验表明该算法是有效的。     

基于博弈理论的节能疏导算法

多粒度传送网作为下一代骨干传输网的核心部分,其高带宽和节能优势受到广泛关注。但是,由于用户不断激增的带宽需求和全球电力资源日趋紧张的现状,需要对网络传输系统的容量和性能作进一步的提高。对多粒度传送网能够快速提供新链路和删除旧链路的特点进行了研究,并将博弈均衡的思想引入业务量疏导的选路过程中,设计了一种基于博弈理论的多粒度传送网节能疏导算法。该算法不仅降低了业务阻塞率,而且节省了网络能耗。在拓扑EON和CERNet2下对算法进行了评估,仿真结果表明该算法具有可行性和有效性。     

基于捕食搜索策略的模拟退火优化算法

针对传统模拟退火算法初始温度和降温函数难以确定以及接收劣质解同时容易遗失当前最优解等缺陷,将禁忌搜索算法的禁忌表功能引入SA算法,避免遗失最优解和对某个解进行多次重复地搜索;根据函数的复杂程度确定初始温度,并定义新的降温函数,提高算法的搜索效率和精度;引入捕食搜索策略,平衡算法搜索能力和开发能力,避免陷入局部最优。通过对5个典型的基准测试函数的仿真表明,改进算法具有较强的全局搜索能力,同时寻优精度和收敛速度比原算法也有较大的提高。     

IP/DWDM光Internet中通信量疏导机制的研究

在IP/DWDM光Internet中,用户的一个通信量请求所需要的带宽往往小于网络中一个波长信道的容量。如果为每个带宽需求小于波长粒度的通信量请求分配一个独立的波长信道,会造成网络带宽资源的浪费。为此,引入了通信量疏导机制。它是一种将低速通信流组合到高速波长信道上的技术,可以极大地提高Internet的带宽资源利用率。本文分析了通信量疏导问题的国内外研究现状,并对该问题的几个热点研究方向进行了讨论。     

基于PVM的博弈树的网络并行搜索

通过分析博弈理论和a-b剪枝搜索过程,提出了使用PVM构造并行搜索网络.设计和实现了基于PVM的博弈树并行搜索过程.在博弈树搜索中通过构造的并行搜索网络和使用分而治之的策略把搜索过程分布在多个计算机上同时进行,在叶计算机结点的搜索中,通过a-b剪枝技术,剪枝了大量的搜索结点.全局并行搜索和局部剪枝技术的使用,加快了搜索的速度,解决了使用单计算机搜索速度和时间不可行的问题.该博弈并行搜索模型,适用于一般的博弈树搜索问题.     

基于捕食搜索策略遗传算法的SVM参数优化方法

基于支持向量机(SVM)模型的泛化能力和拟合精度与其相关参数的选取有关,提出将捕食搜索策略的遗传算法(PSGA)运用到SVM的参数选取中。该算法以最小化输出量的拟合误差为目标,以SVM的3个参数作为决策变量。通过对谷氨酸发酵过程建模的实验表明,该方法可以提高谷氨酸浓度的训练精度及预测精度,是一种优化SVM参数的有效方法。     

Two-level iterated local search for WDM network design problem with traffic grooming

Two important problems arise in WDM network planning: network design to minimize the operation cost and traffic grooming to maximize the usage of the high capacity channels. In practice, however, these two problems are usually simultaneously tackled, denoted as the network design problem with traffic grooming (NDG). In this paper, a mathematical formulation of the NDG problem is first presented. Then, this paper proposes a new metaheuristic algorithm based on two-level iterated local search (TL-ILS) to solve the NDG problem, where a novel tree search based neighborhood construction and a fast evaluation method are proposed, which not only enhance the algorithm's search efficiency but also provide a new perspective in designing neighborhoods for problems with graph structures. Our algorithm is tested on a set of benchmarks generated according to real application scenarios. We also propose a strengthening formulation of the original problem and a method to obtain the lower bound of the NDG problem. Computational results in comparison with the commercial software CPLEX and the lower bounds show the effectiveness of the proposed algorithm.     

A traffic grooming problem considering hub location for synchronous optical network-wavelength division multiplexing networks

In this paper, we deal with a traffic demand clustering problem for designing SONET-WDM rings. The objective is to minimize the total cost of optical add-drop multiplexers (OADMs) and inter-ring hub equipments, while satisfying intra-ring and inter-ring capacities. Also, the minimum number of nodes, for example three, for each ring should be satisfied. We develop an integer programming (IP) formulation for the problem and develop some valid inequalities that provide a tight lower bound for the problem. Dealing with the inherent computational complexity of the problem, we also devise an effective tabu search procedure for finding a feasible solution of good quality within reasonable computing time. Computational results are provided to demonstrate the efficacy of the lower and upper bound procedures for solving the problem.     

Policy-Based Grooming in Optical Networks

This work presents a discussion about policies and architecture to aggregate Internet Protocol/Multiprotocol Label Switching (IP/MPLS) traffics within lightpaths. The scenario is that of IP/MPLS client networks over an optical network. It is well known that aggregating lower traffic flows (e.g., packet-based LSPs—Label Switched Path) within higher traffic flows (e.g., lambda-based LSPs) is considered an effective way to maximize the use of the optical network resources. In this work, the policies are divided into two groups. The first one, which solely considers the class of the flow (High Priority—HP or Low Priority—LP), consists of simple policies meant to aggregate packet-based LSPs within lightpaths. In this group, the policies we have defined intend to reduce the optical network overhead to remove and reroute LP LSPs. The second group presents more sophisticated policies taking into account the possibility of having to deal with further transport faults. In this case, the grooming is better planned and the defined policies tend to reduce the negative impact when a failure is detected in the optical transport network. Our approach has been implemented to validate the policies and the results for each group are showed and discussed.     

Traffic grooming, routing, and wavelength assignment in WDM transport networks with sparse grooming resources

While a single fiber strand in wavelength division multiplexing (WDM) has over a terabit-per-second bandwidth and a wavelength channel has over a gigabit-per-second transmission speed, the network may still be required to support traffic requests at rates that are lower than the full wavelength capacity. To avoid assigning an entire lightpath to a small request, many researchers have looked at adding traffic grooming to the routing and wavelength assignment (RWA) problem. In this work, we consider the RWA problem with traffic grooming (GRWA) for mesh networks under static and dynamic lightpath connection requests. The GRWA problem is NP-Complete since it is a generalization of the RWA problem which is known to be NP-Complete. We propose an integer linear programming (ILP) model that accurately depicts the GRWA problem. Because it is very hard to find a solution for large networks using ILP, we solve the GRWA problem by proposing two novel heuristics. The strength of the proposed heuristics stems from their simplicity, efficiency, and applicability to large-scale networks. Our simulation results demonstrate that deploying traffic grooming resources on the edge of optical networks is more cost effective and results in a similar blocking performance to that obtained when distributing the grooming resources throughout the optical network domain.     

Multiple link failures survivability of optical networks with traffic grooming capability

This paper investigates the problem of survivable traffic grooming (STG) in shared mesh optical networks and proposes different frameworks for improving the survivability of low speed demands against multiple near simultaneous failures. Spare capacity reprovisioning has recently been considered for improving the overall network restorability in the event of dual failures; here, after the recovery form the first failure, some connections in the network may become unprotected and exposed to new failures. Capacity reprovisioning then allocates protection resources to unprotected and vulnerable connections so that the network can withstand a future failure. In this paper, we propose two different reprovisioning schemes (lightpath level reprovisioning, LLR, and connection level reprovisioning, CLR); they differ in the granularity at which protection resources are reprovisioned. Further, each of these schemes is suitable for a different survivable grooming policy. While LLR provides collective reprovisioning of connections at the lightpath level, CLR reprovisions spare bandwidth for lower speed connections instead. We use simulation methods to study the performance of these schemes under two grooming policies (PAL and PAC), and we show that while CLR reprovisions substantially many more connections than LLR (i.e., potentially more management overhead) CLR yields a much better network robustness to simultaneous failures due to its superior flexibility in using network resources.     

一种光传送网分层结构及其业务量疏导优化模型

提出一种包括IP、SDH和WDM三种网络层次的光传送网分层结构及其业务量疏导优化模型。IP和SDH层的逻辑拓扑由优化模型根据这两层的业务请求矩阵生成,IP和SDH层以多种带宽颗粒度串路承栽具有不同请求带宽的业务流,模型以最大化网络流量为目标,定义了三种网络层次上不同颗粒度串路之间和串路与业务流之间的相关性约束。在不同网络资源配置下,利用Lingo优化软件对模型的求解结果验证了模型的有效性。     

WDM网状网络中静态流量疏导的收发器节约辅助图模型

对于WDM光网络中的静态流量疏导,提出了一种收发器节约的辅助图形（TSAG）模型。基于辅助图提出了一种收发器节约的方法（TSABAG）,针对不同的流量可以给辅助图中不同的边分配不同的权值,以实现不同的疏导策略。仿真试验证明,TSAG模型极大地节约了占用的收发器资源,而且拥有较高的吞吐量。     

On the complexity and algorithm of grooming regular traffic in WDM optical networks

In SONET/WDM networks, a high-speed wavelength channel is usually shared by multiple low-rate traffic demands to make efficient use of the wavelength capacity. The multiplexing is known as traffic grooming and performed by SONET Add-Drop Multiplexers (SADM). The maximum number of low-rate traffic demands that can be multiplexed into one wavelength channel is called grooming factor. Since SADMs are expensive, a key optimization goal of traffic grooming is to minimize the total number of SADMs in order to satisfy a given set of traffic demands. As an important communication traffic pattern, all-to-all traffic has been widely studied for the traffic grooming problem. In this paper, we study the regular traffic pattern, which is considered as a generalization of the all-to-all traffic pattern. We focus on the Unidirectional Path-Switched Ring (UPSR) networks. We prove that the traffic grooming problem is NP-hard for the regular traffic pattern in UPSR networks, and show that the problem does not admit a Fully Polynomial Time Approximation Scheme (FPTAS). We further prove that the problem remains NP-hard even if the grooming factor is any fixed value chosen from a subset of integers. We also propose a performance guaranteed algorithm to minimize the total number of required SADMs, and show that the algorithm achieves a better upper bound than previous algorithms. Extensive simulations are conducted, and the empirical results validate that our algorithm outperforms the previous ones in most cases. In addition, our algorithm always uses the minimum number of wavelengths, which are precious resources as well in optical networks.