多波长光网络的动态路由等效算法

针对多波长光网络的特点，提出了一种动态路由和波长分配的等效算法。采用波长图、增加虚拟源节点和目的节点等技术，把多波长网络转化为等效的单波长网络，避免了求解路由和波长分配两个复杂子问题，简化了算法的程序设计。利用最短径算法进行路由和波长分配可以求得问题的最优解，从而有效地降低了网络阻塞率。仿真结果表明：与FAR-2D算法相比，在4和8波长的全波长转换网络中，采用等效算法阻塞率最大降幅分别达到0．02、0．025。     

稀疏波长变换的WDM光网络阻塞率的分析与计算

本文主要对具有稀疏波长变换的WDM全光网的阻塞率进行分析,首先提出一种模型分析了无波长变换器的L跳路径端到端阻塞率,接着对部分波长变换器的L跳路径的阻塞率进行求解,随后分析了全网的平均阻塞率。研究得到的主要结论是,波长变换器使用的有效性取决于网络的连接度。     

部分波长光网络中的动态波长分配算法

为适应网络中不同服务质量（QoS）的光路建立请求具有不同的优先级的情况,提出了一种用于部分波长可变网络中支持QoS的动态波长分配算法。该算法对网络中的业务请求分高、低两个优先级进行处理。对于高优先级的光路建立请求,通过充分利用网络中已配置的波长转换器实时改变可用波长集,以降低高优先级业务请求的阻塞率。对低优先级的光路建立请求,只考虑所选路径的当前位置是否有波长转换器来改变可用波长集,保证了低优先级的光路建立请求速度。仿真结果表明,该算法既能保证较高优先级的光路建立请求具有较低的阻塞率,又充分利用了有限的网络资源,实现了对波长转换器的最优利用。     

一种新型的动态路由和波长分配综合算法

讨论了WDM光网中，在动态业务流量和有限范围波长变换情况下的动态路由和波长分配问题。基于Moone-Dijkstra算法，考虑到动态波长变换的可能和限制，提出了一种新型的、可实现动态最小代价路由和最佳虚波长通道的综合启发式算法(DMC-OVWP)。该算法对路由子问题和波长分配子问题既相互独立，又相互结合，优化了RWA。以中国教育和科研计算机网(CERNET)为拓扑背景，基于本算法进行了计算机仿真，并对实验结果进行了比较分析，证明本算法可充分利用网络信息获取较低的阻塞率。     

一种联合优化的水声通信网路由算法设计

针对传统的无线网络路由建立算法在水下小型网络中时延及能耗代价高的问题,提出了改进的DSDV(Destination Sequenced Distance Vector)路由过程,并在此基础上设计出与拓扑结构、MAC层联合优化的算法。该算法建立了以改进的DSDV路由建立时间、能耗及路由信息的完整性为代价函数,以MAC层的包长度、包间隔、拓扑结构中的点和边数等为矢量参数的数学模型,并结合无向图的广度优先搜索算法及最短路径算法,提出了在上述矢量参数条件下代价函数的最优化设计,形成一套适用于小规模区域性观测应用背景的水声通信网的路由建立方法。仿真结果表明,在相同的物理层条件下,联合优化的算法与未优化的DSDV相比,在相同的时间内建立完整的全网路由的概率最大可提高30%。     

基于改进网络最大流的道路通行能力优化研究

基于图论网络最大流理论基础,建立了一种改进的网络最大流模型。首先,根据最基本的网络最大流模型,采用Ford-Fulkerson算法求解出理论最大通行能力为46人/s;其次,考虑通行的道路选择性,建立最短路模型,利用Dijkstra算法计算各个单源到各个单汇的最短路径,并通过A*算法排除与最短距离相差较大的路径,从而筛选出有效路径;然后,利用最短路模型结果加强原模型中的约束条件,利用单纯形法求解出实际最大通行能力为23人/s;最后,建立以道路扩宽成本最低为目标函数的线性规划模型对道路进行优化改造。研究结果表明,现有道路设计能够满足道路通行需求,若需提高道路通行能力且要求道路改造最小,可以适当扩宽路网中的关键道路。     

System Travel Time Reliability: A Measure of the Quality of Service of Networks

In this study, the travel time reliability of network systems is measured by travel time limitation as well as two‐terminal reliability. In the network, each arc is a binary random variable weighted by travel time as well as by operational probability. The performance index or QoS of a network system indicates the probability that the source node can successfully travel to the destination node, while satisfying the travel time limitation. Unlike existing literature that evaluated travel time reliability via a single optimization path, the proposed index focuses on the performance of the entire network system. This study presents an efficient decomposition method in computing QoS based on the Dijkstra shortest path method. We employ a small network to demonstrate the algorithm step by step. In addition, computational experiments conducted on a prototype network show that the proposed algorithm is superior to existing methods. Copyright © 2015 John Wiley & Sons, Ltd.     

双光纤波分复用网阻塞率研究

研究了双光纤波分复用互联网在不同网络容量使用率时的阻塞率,主要对单光纤网络使用波长变换器和双纤网络在波长数不同时对网络阻塞率的改善情况做了仿真比较,结果表明仅仅在低阻塞率时波长变换器给网络所带来的增益非常有限,双纤网络可以达到其效果。     

Analytical models of blocking probability for multi-granularity cross-connect-based optical networks

Multi-granularity optical cross-connect (MG-OXC)-based optical network is a promising optical network architecture as it is capable of flexible switching at different granularity levels. In MG-OXC-based optical networks, wavelength conversion (WC) capability and the number of usable add/drop ports of the nodes are two key factors affecting its performance. Two analytical models of blocking probability for MG-OXC-based optical networks both without WC capability and with sparse WC capability are proposed, exploiting Erlang?s loss formula and birth?death process. Based on the models and simulation, the impact of WC capability and the number of add/drop ports on the blocking probability are investigated. Three kinds of granularities (i.e. fibre, waveband and wavelength) are considered in MG-OXC nodes to reduce the complexity and size of switch fabric. Both the analytical and simulation results are given on two network topologies under dynamic traffic patterns. Simulation results show that the proposed models are accurate and effective for the analysis of blocking probability in MG-OXC-based optical networks.     

Efficient Routing Protection Algorithm Based on Optimized Network Topology

Network failures are unavoidable and occur frequently. When the network fails, intra-domain routing protocols deploying on the Internet need to undergo a long convergence process. During this period, a large number of messages are discarded, which results in a decline in the user experience and severely affects the quality of service of Internet Service Providers (ISP). Therefore, improving the availability of intra-domain routing is a trending research question to be solved. Industry usually employs routing protection algorithms to improve intra-domain routing availability. However, existing routing protection schemes compute as many backup paths as possible to reduce message loss due to network failures, which increases the cost of the network and impedes the methods deployed in practice. To address the issues, this study proposes an efficient routing protection algorithm based on optimized network topology (ERPBONT). ERPBONT adopts the optimized network topology to calculate a backup path with the minimum path coincidence degree with the shortest path for all source purposes. Firstly, the backup path with the minimum path coincidence with the shortest path is described as an integer programming problem. Then the simulated annealing algorithm ERPBONT is used to find the optimal solution. Finally, the algorithm is tested on the simulated topology and the real topology. The experimental results show that ERPBONT effectively reduces the path coincidence between the shortest path and the backup path, and significantly improves the routing availability.     

Shortest path calculation in large road networks

One of the basic problems in transportation planning systems is the calculation of the fastest route between two points in a road network. General shortest path algorithms, which examine a large part of the whole graph for each shortest path, are very slow if the road network is large. Since the road network does not change very often it is possible to calculate auxiliary information in a preprocessing step. I will present a preprocessing algorithm which requires linear storage. It is substantially faster than the general algorithms without preprocessing. Received: 17 July 1996 / Accepted: 22 April 1997     

Evolution of meso-structures and mechanical properties of granular materials under triaxial compression state from complex network perspective

The evolution of the network connection of granular materials is investigated by performing a series of numerical simulations in triaxial compression tests with different initial porosities by discrete element method (DEM). Results of evolution characteristics of complex network are reported for both dense and loose assembles. The simulation focuses on the influence of porosity on connectivity evolution, and reveals the correlation between the parameters in macro and mesoscale. Kinds of properties are studied, including degree and its distribution, clustering coefficient, network density and the average shortest path. The results demonstrate the phenomenon of dilataion due to shear deformation are able to be reflected by those mesocope parameters mentioned. Specifically, in the process of the dilatation, the rate of contact disintegration exceeds the rate of contact creation, which means the loss of connectivity, thus the values of some properties decrease, like degree, clustering coefficient and network density, but some increase like the average shortest path. Additionally, the bridging of macro and mesoscope are built regarding the parameters of the Cam-Clay model and complex network. From the results, the parameter M (determined by q?=?Mp′ at critical state) and the reference parameter \( {\text{T}} \) (\( T_{j}^{s} = L_{j}^{s} \left( {1 - \log_{{D_{j}^{s} }} t} \right) \), calculated according to the average degree \( D_{j}^{s} \) and shortest path \( L_{j}^{s} \) of the critical state) have a positive correlation. And a linear relationship between the slope of isotropic virgin-consolidation λ and the rate of decline of the average shortest path upon loading is represented as well. These achievements are the first step in an ongoing study of establishing the multi-scale constitutive from complex network perspective.     

一种结合网络编码的路径代价衡量方法

针对无线路由协议中的路径代价衡量问题,结合网络编码改善无线节点信息互换的思想,提出了一种结合网络编码的路径代价衡量方法--RMNC,其核心思想是利用流量参数反映信息流的网络编码"搭乘"程度和逐节点计算路径的代价.通过将传输流流量参数和路径中节点左右链路信息流流量参数进行运算,获得路径上的各个节点的传输代价;网络中某一条路径的代价等于组成这条路径的节点传输代价之和,通过比较不同路径的逐节点计算代价值,获得最短路径.分析和模拟测试结果表明,RMNC可以有效地获得结合网络编码的最短路径,达到提高传输性能的目的.尽管传输延时有所增加,但可以接受,方法可行.     

基于退火算法的物流配送网的求优研究

模拟退火算法是一种启发式算法,是受到加热紧缩的退火过程所启发而提出来一种求解组合优化问题的一种逼近算法。算法要优于传统的贪婪算法,避免了陷入局部最优的可能,从而达到全局最优解。在物流配送网络中经常为有一些寻求最短路径等问题出现,为了能够达到最短、最优、最经济等,需要进行物流配送路径寻优。文中采用模拟退火算法进行一个示例的验证,效果证明可行。     

Reservation signalling mechanism for reducing blocking probability in optical burst switching networks with limited wavelength conversion capabilities

First, the optical burst switching (OBS) network with limited wavelength conversion capability (LWCC) is decomposed into multiple wavelength continuous segments according to the position of wavelength converters. Based on the decomposed network model, two reservation signalling mechanisms for OBS-LWCC networks, namely wavelength-amend-on-demand (WAoD) and contention-based limited signalling protocol (CLSP), are proposed to reduce the blocking probability in the OBS-LWCC networks. In WAoD, the congested node sends a feedback message to the closest upstream switch with wavelength conversion capability. The notified switch will change the burst wavelength to the one assigned by the congested node to avoid collision in advance. Extensive simulation results indicate that by applying the wavelength reconfiguration method to the core nodes without wavelength conversion capability, the proposed WAoD scheme can improve the blocking performance in the OBS-LWCC networks significantly. Furthermore, CLSP, which combines the burst time-slot reconfiguration with the wavelength reconfiguration of WAoD, always has the lowest burst loss probability when compared with both the conventional and the proposed reservation mechanisms.     

An Efficient Algorithm for Global Path Optimization in MPLS Networks

This paper proposes an algorithm to solve the optimization of label switched paths (LSPs) in multiprotocol label switching (MPLS) networks. The underlying optimization problem in this task is the well-known unsplittable multicommodity flow problem equipped with practically relevant objective functions and specialized with hard technical requirements.The proposed heuristic algorithm is based on network flow theory. It incorporates iterative shortest path search and performs adaptive edge weight adjustments in order to successfully satisfy all the required traffic demands and to maximize user-defined objectives. The robust algorithm facilitates the incorporation of several strategic and optimization objectives and the fulfillment of certain hard technical requirements of the target problem domain as well. Novel features of the approach include a new adaptive path allocation/deallocation strategy based on the identification of bottleneck links, demand ordering and preprocessing phases, and a systematic path allocation control method.The efficiency of the method is empirically shown on randomly generated networks with practical sizes and topologies, and on a real-world IP (Internet Protocol) backbone network. The algorithm is able to successfully solve difficult problem instances comprising very large instances with 1000 nodes, 3500 edges and 999000 traffic demands. The computational tests demonstrate that the proposed approach can be efficiently applied to solve problem instances that embed MPLS specific hard technical requirements. Furthermore, it is shown that our algorithm offers significantly better performance than the straightforward adaptations of existing methods that were developed for related network optimization problems. Namely, our algorithm produces acceptable results quicker, it can solve problems that were not previously solvable, and it yields better results than the alternative methods. The extensive empirical tests demonstrate the combinatorial properties of the target problem and the performance aspects of the algorithm and its components as well.     

An algorithm for optimising the servicing of products with constrained,multiple defects

The twin pillars of sustainable development are the conservation of natural resources and the management of waste. Waste is generated whenever a product is serviced or repaired, or when it is ultimately discarded at the end of its useful life. In order to manage such waste, the servicing options and costs must first be ascertained. This paper presents an algorithm for the generation of optimal disassembly and re-assembly sequences for the servicing of products with multiple defects, subject to constraints such as inaccessible components. The multiple service action (MSA) algorithm determines the minimum total servicing cost for a product network based on Floyd's Algorithm, a shortest path algorithm. Well-established shortest path algorithms, which compute the shortest route between any pair of nodes in a network, are unable to handle multiple defects. The product network is first constructed, depicting the components and subassemblies as nodes, and embodying in directed arcs, the labour, materials and tooling costs associated with disassembly and re-assembly, as well as the cost to repair, reuse, recycle or dispose the defective components. The MSA algorithm was tested on seven different product networks representing multiple defective components that can be serviced by different feasible routes. For each feasible service route, associated costs were computed. It was established that the algorithm was able to generate optimum disassembly and re-assembly routes for the servicing of products with multiple defects subject to constraints.     

基于模拟退火法的组播路由算法(英文)

本文提出了一种基于模拟退火算法的延时约束最小代价组播路由算法(SADLMA)。首先,本算法使用Dijkstra第K最短路算法建立了从源节点到每个目的节点的候选集。然后生成了相应的邻居结构。当温度下降时,根据接收概率从邻居结构里把新解选择出来,并且代替旧解。仿真试验表明本算法对实际网络是有效的。     

Network reliability assessment using a cellular automata approach

Two cellular automata (CA) models that evaluate the s–t connectedness and shortest path in a network are presented. CA based algorithms enhance the performance of classical algorithms, since they allow a more reliable and straightforward parallel implementation resulting in a dynamic network evaluation, where changes in the connectivity and/or link costs can readily be incorporated avoiding recalculation from scratch. The paper also demonstrates how these algorithms can be applied for network reliability evaluation (based on Monte-Carlo approach) and for finding s–t path with maximal reliability.     

A priori least expected time paths in fuzzy,time-variant transportation networks

Dynamics and fuzziness are two significant characteristics of real-world transportation networks. To capture these two features theoretically, this article proposes the concept of a fuzzy, time-variant network characterized by a series of time-dependent fuzzy link travel times. To find an effective route guidance for travelers, the expected travel time is specifically adopted as an evaluation criterion to assess the route generation process. Then the shortest path problem is formulated as a multi-objective 0–1 optimization model for finding the least expected time path over the considered time horizon. Different from the shortest path problem in dynamic and random networks, an efficient method is proposed in this article to calculate the fuzzy expected travel time for each given path. A tabu search algorithm is designed for the problem to generate the best solution under the framework of linear weighted methods. Finally, two numerical experiments are performed to verify the effectiveness and efficiency of the model and algorithm.