On open shortest path first related network optimisation problems

The paper deals with flow allocation problems in IP networks using open shortest path first (OSPF) routing. Its main purpose is to discuss and propose methods for finding settlements of OSPF link weight system realising the assumed demand pattern for the given network resources (links capacities). Such settlements can result in a significantly better network performance, as compared with the simplified weight setting heuristics typically used nowadays. Although the configuration of the link weight system is primarily done in the network planning phase, still additional re-optimisations are feasible, and in fact essential, in order to cope with major changes in traffic conditions and with major resources’ failures and rearrangements.

The paper formulates a relevant OSPF routing optimisation problem, proves its NP-completeness, and discusses possible heuristic approaches and related optimisation methods for solving it. Two basic approaches are considered (the direct approach and the two-phase approach) and the resulting optimisation algorithms are presented. The considerations are illustrated with numerical results.     

PTN网络的二次断纤链路规划算法

在PTN（PacketTransportNetwork）网络规划建设中,需要对光纤链路留出备份带宽,以保证部分光纤断开时,受影响业务有足够的容量进行路由重组。这也是提高网络生存性的有效方法之一。文中首先遍历网络双链路的失效状态,然后断开网络中任意两条链路,通过逐次增加链路容量来保证失效业务能够重组路由;最后提出二次断纤链路容量规划算法并进行试验仿真。结果表明,该算法在节约网络带宽、降低建造成本以及故障容错方面有着良好性能,能够很好应用于传送网络的链路规划中。     

A Study on Network Design Problems for Multi-modal Networks by Probit-based Stochastic User Equilibrium

This paper develops a multi-modal transport network model considering various travel modes including railway, bus, auto, and walking. Travellers are assumed to choose their multi-modal routes so as to minimise their perceived disutilities of travel following the Probit Stochastic User Equilibrium (SUE) condition. Factors influencing the disutility of a multi-modal route include actual travel times, discomfort on transit systems, expected waiting times, fares, and constants specific to transport modes. The paper then deals with the multi-modal network design problem (NDP). The paper employs the method of sensitivity analysis to define linear approximation functions between the Probit SUE link flows and the design parameters, which are then used as constraints in the sub-problem of the NDP instead of the original SUE condition. Based on this reformulated NDP, an efficient algorithm for solving the problem is proposed in the paper. Two instances of this general NDP formulation are then presented in the paper: the optimal frequency design problem for public transport services (FDP), and the anti-freezing admixture dispersion problem (AADP).     

Network routing control with G-networks

The aim of this paper is to detail a control scheme for packet computer networks whose purpose is to minimise a quality-of-service oriented performance metric by re-routing the traffic. The model is based on G-networks with triggered customer movement to represent traffic re-routing, and on a gradient descent based optimisation algorithm. The model and the algorithm are presented and we show that the gradient descent algorithm is of computational complexity O(N³) where N is the number of nodes in the packet network. Via the use of multiple classes of normal traffic and multiple classes of triggers, our approach allows one not only to evaluate the effect of the control, but also to incorporate the overhead that the control traffic will induce, and the consequences of the delays or possible losses of the control traffic. Similarly, these effects will naturally be incorporated when one considers both the impact of the control traffic on the cost function, and the details of this control traffic in the control algorithm itself.     

A new stochastic approach for a reliable p-hub covering location problem

A hub location problem (HLP) is a fertile research field, in the aspect of interdisciplinary studies, such as transportation, operation research, network design, telecommunication and economics. The location of hub facilities and allocation of non-hub nodes to hubs configure the backbone of HLPs. This study presents a new mathematical model for a reliable HLP by a new stochastic approach to minimize the total transportation cost and obtain maximum flows that the network can carry, when its link capacities are subject to stochastic degradations, as in a form of daily traffic, earthquake, flood, etc. We consider the road capacity reliability as a probability that ensures the maximum network capacity is greater than or equal to the total incoming flow to the network by considering the road capacity as random variable. As a result, this paper assumes that link capacities satisfy in a Truncated Erlang $(\mathit{TErl})$ distribution function. Due to complexity of the HLP, a meta-heuristic algorithm, namely differential evolution (DE) algorithm, is applied on the problem in order to achieve near-optimal solutions. Furthermore, the performance of the proposed algorithm (i.e., DE) is evaluated by the performance of the genetic algorithm (GA) applied on the given problem. Some computational experiments are presented to illustrate the effectiveness of the presented model and proposed algorithm. Finally the conclusion is provided.     

Path selection with preemption and re-routing control for multi-protocol label switching networks

Multi Protocol Label Switching (MPLS) networks enhance the services of conventional best-effort IP networks by providing end-to-end Quality of Service (QoS) guaranteed Label Switched Paths (LSP) between customer sites. The LSP has to be set up in advance before carrying the traffic. Contention for network resources may happen if many LSPs try to use a common network link with limited bandwidth. In this paper, we investigate the problem of providing services to high priority LSPs whereby existing LSPs with lower priority may be preempted. The consequent interruption of the services of preempted LSPs would detrimentally affect users’ perception on the QoS provided. Therefore, the preemption strategies may incorporate additional re-routing mechanisms to provide alternative paths for the LSPs which are to-be-preempted so that their services remain unaffected. A newly arrived high priority LSP in an MPLS network may find M possible paths between its source and destination. It may select the shortest path which may trigger preemption or choose a longer path which however utilizes more resources. We begin by formulating preemption strategies with global re-routing. Our investigations include the effects of routing of high priority LSPs on the shortest path and its alternative paths. We show that by persistently routing the high priority LSP on the shortest path, more preempted LSPs can be re-routed which would reduce the negative effects of preemption. However, as excessive re-routing may degrade the network performance as well, a re-routing control strategy is proposed to constrain the length of these re-routed paths. Finally, a decentralized preemption strategy with local re-routing is also presented to approximate the performance of the proposed strategy with significantly lower control overheads. Simulations show that with this approach, high priority LSPs can gain better access to network resources while simultaneously ensuring that, as compared to the existing preemption strategies, the network throughput and the ongoing connection services are not adversely affected.     

计算机网络链路容量分配的新方法

网络链路的容量和时延是设计计算机网络拓扑结构中的主要问题 ,大量的网络拓扑结构设计需要这方面的研究而结果将在这一领域得到应用 .现在已经提出了多种不同的计算方法 .本文在 L.Kleinroek's的基础上给出了一种新的分配网络链路容量的方法 ,所建立的模型不同于已有的 Bernd Meister,Carol A.Niznik的算法 ,避免了α参数的引入及分组算法 ,并始终进行定量分析 ,给出了严格的综合性数学模型 .利用此算法可得到满足链路时延差异和链路容量限制条件下的具有最小网络时延的链路容量分配结果     

The Price of Selfish Routing

We study the problem of routing traffic through a congested network. We focus on the simplest caseof a network consisting of m parallel links. We assume a collection of n network users; each user employs a mixed strategy, which is a probability distribution over links, to control the shipping of its own assigned traffic. Given a capacity for each link specifying the rate at which the link processes traffic, the objective is to route traffic so that the maximum (over all links) latency is minimized. We consider both uniform and arbitrary link capacities. How much decrease in global performace is necessary due to the absence of some central authority to regulate network traffic and implement an optimal assignment of traffic to links? We investigate this fundamental question in the context of Nash equilibria for such a system, where each network user selfishly routes its traffic only on those links available to it that minimize its expected latency cost, given the network congestion caused by the other users. We use the Coordination Ratio, originally defined by Koutsoupias and Papadimitriou, as a measure of the cost of lack of coordination among the users; roughly speaking, the Coordination Ratio is the ratio of the expectation of the maximum (over all links) latency in the worst possible Nash equilibrium, over the least possible maximum latency had global regulation been available. Our chief instrument is a set of combinatorial Minimum Expected Latency Cost Equations, one per user, that characterize the Nash equilibria of this system. These are linear equations in the minimum expected latency costs, involving the user traffics, the link capacities, and the routing pattern determined by the mixed strategies. In turn, we solve these equations in the case of fully mixed strategies, where each user assigns its traffic with a strictly positive probability to every link, to derive the firstexistence and uniqueness results for fully mixed Nash equilibria in this setting. Through a thorough analysisand characterization of fully mixed Nash equilibria, we obtain tight upper bounds of no worse than O(ln n/ln ln n) on the Coordination Ratio for (i) the case of uniform capacities and arbitrary traffics and (ii) the case of arbitrary capacities and identical traffics.     

Multi-layer MPLS network design: The impact of statistical multiplexing

The possibility of adding multi protocol label switching (MPLS) support to transport networks is considered an important opportunity by telecom carriers that want to add packet services and applications to their networks. However, the question arises whether it is suitable to have MPLS nodes just at the edge of the network to collect packet traffic from users, or to introduce also MPLS facilities on a subset of the core nodes in order to exploit packet switching flexibility and multiplexing, thus inducing a better bandwidth allocation. In this paper, we propose a mathematical programming model for the design of two-layer networks where MPLS is considered on top of transport networks (SDH or WDM depending on required link speed). Our models take into account the tradeoff between the cost of adding MPLS support in the core nodes and the savings in the link bandwidth allocation due to the statistical multiplexing and the traffic grooming effects induced by MPLS nodes. The traffic matrix specifies for each point-to-point request a pair of values: a mean traffic value and an additional one. Using this traffic model, the effect of statistical multiplexing on a link allows to allocate a capacity equal to the sum of all the mean values of the traffic demands routed on the link and only the highest additional one. We propose a path-based Mixed Integer Programming (MIP) model for the problem of optimizing the number and location of MPLS nodes in the network and the link capacities. We apply Lagrangian relaxation to this model and use the subgradient method to obtain a lower bound of the network cost. As the number of path variables used to model the routing grows exponentially with the graph size, we use an initially limited number of variables and a column generation approach. We also introduce a heuristic approach to get a good feasible solution. Computational results are reported for small size and real-world instances.     

Computation and application of the paired combinatorial logit stochastic user equilibrium problem

The paired combinatorial logit (PCL) model is one of the recent extended logit models adapted to resolve the overlapping problem in the route choice problem, while keeping the analytical tractability of the logit choice probability function. However, the development of efficient algorithms for solving the PCL model under congested and realistic networks is quite challenging, since it has large-dimensional solution variables as well as a complex objective function. In this paper, we examine the computation and application of the PCL stochastic user equilibrium (SUE) problem under congested and realistic networks. Specifically, we develop an improved path-based partial linearization algorithm for solving the PCL SUE problem by incorporating recent advances in line search strategies to enhance the computational efficiency required to determine a suitable stepsize that guarantees convergence. A real network in the city of Winnipeg is applied to examine the computational efficiency of the proposed algorithm and the robustness of various line search strategies. In addition, in order to acquire the practical implications of the PCL SUE model, we investigate the effectiveness of how the PCL model handles the effects of congestion, stochasticity, and similarity in comparison with the multinomial logit stochastic traffic equilibrium problem and the deterministic traffic equilibrium problem.     

An efficient and robust design optimisation of multi-state flow network for multiple commodities using generalised reliability evaluation algorithm and edge reduction method

The network of delivering commodities has been an important design problem in our daily lives and many transportation applications. The reliability of delivering commodities from a source node to a sink node in the network is maximised to find the optimal routing. However, the design problem is not simple due to randomly distributed attributes in each path, multiple commodities with variable path capacities and the allowable time constraints for delivery. This paper presents the design optimisation of the multi-state flow network (MSFN) for multiple commodities. We propose an efficient and robust approach to evaluate the system reliability in the MSFN with respect to randomly distributed path attributes and to find the optimal routing subject to the allowable time constraints. The delivery rates of the path segments are evaluated and the minimal-speed arcs are eliminated to reduce the complexity of the MSFN. Accordingly, the correct optimal routing is found and the worst-case reliability is evaluated. The reliability of the optimal routing is at least higher than worst-case measure. Three benchmark examples are utilised to demonstrate the proposed method. The comparisons between the original and the reduced networks show that the proposed method is very efficient.     

Optimal resource assignment to maximize multistate network reliability for a computer network

Computer network is a major tool to transmit data in our modern society. How to evaluate and enhance network reliability is thus an important issue for organizations, especially to maximize network reliability. A computer network is a multistate network in which each edge has several possible capacities with a probability distribution and may fail. The multistate network reliability is the probability that the maximal flow is no less than a given demand. From the standpoint of quality management, a further problem is to reassign the existing resources for maximizing multistate network reliability without changing the network topology. Hence, this paper focuses on the resource assignment problem to propose an efficient approach based on the simple genetic algorithm. In which, a resource assignment is represented as a chromosome and the corresponding multistate network reliability is the fitness value of the chromosome. The experimental results show that the proposed algorithm can derive the optimal resource assignment in a reasonable time.     

基于rLFA技术的性能优化及重路由选择算法研究

为进一步提高网络单故障快速恢复能力,基于改进的Remote Loop-Free Alternates(rLFA)重路由技术,提出一种采用混沌粒子群并考虑网络物理传输代价和拥塞代价的重路由选择算法.首先基于rLFA的隧道建立方法对其进行改进,结合引入隧道技术的链路增补方法来实现故障全覆盖,通过设置权重因子来保证在不同业务量下的重路由选择针对性.实验表明,改进的rLFA能进一步提高网络单故障覆盖率,同时结合链路增补方法在保证故障完全覆盖的情况下能够大幅度减少链路增补数量;路由选择算法能够动态选择不同业务量下的重路由路径,在提高网络单故障环境下的传输效率的同时也实现了负载均衡.     

Link weight assignment and loop-free routing table update for link state routing protocols in energy-aware internet

In order to lessen the greenhouse effects and diminish environmental pollution, reducing energy usage is important in designing next generation networks. Shutting down the network devices that carry light load and redirecting their traffic flows to other routes is the most common way to reduce network energy consumption. Since traffic demands among node pairs vary in different time periods, an energy efficient network has to dynamically determine the optimal active links to adapt itself to network traffic changes. However, in current IP networks, shutting down and/or turning on links would trigger link state routing protocols to reconverge to a new topology. Since the convergence time would take tens of seconds, routing table inconsistencies among routers would result in network disconnection and even worse, generating traffic loops during the convergence interval. Removing routing images inconsistent among routers to prevent loops is a critical issue in energy efficient network and this issue is still not considered in the green network design yet. The contribution of the paper is presented in two parts. First, we propose a comprehensive approach to determine a network topology and a link metric for each time period. Traffic engineering is considered in our design such that flows going on the energy-aware network are within a predetermined percentage of the link capacity such that no congestion occurs in a statistical manner. Second, to avoid transient loops during time period changes, we propose a Distributed Loop-free Routing Update (DLRU) scheme to determine the correct sequence for updating the routing table. A scrupulous proof was also presented to ensure the loop-free property of the DLRU. In this paper, we formulate an integer linear programming to determine this multi-topology and link weight assignment problem. Due to its NP-hard property, we propose an efficient algorithm, termed Lagrangian Relaxation and Harmonic Series (LR&HS) heuristic. Numerical results demonstrate that the proposed LRHS approach outperforms the other approaches on several benchmark networks and random networks by providing up to 35%-50% additional energy saving in our experimental cases.     

Energy optimization for proactive unicast route maintenance in MANETs under end-to-end reliability requirements

Many time-critical applications for Mobile Ad hoc NETworks (MANETs), such as the military applications and disaster response, call for proactive link and route maintenance to ensure low latency for reliable data delivery. The goal of this paper is to minimize the energy overhead due to the high control traffic caused by the periodic route and link maintenance operations in the proactive routing protocols for MANETs. This paper — (i) categorizes the proactive protocols based on the maintenance operations performed; (ii) derives analytical estimates of the optimum route and link update periods for the different protocol classes by considering (a) the data traffic intensity, (b) link dynamics, (c) target reliability, measured in terms of Packet Delivery Ratio (PDR), and (d) the network size; and (iii) proposes a network layer dynamic Optimization of Periodic Timers (OPT) method based on the analytical estimates to locally vary the update periods in the distributed nodes. Simulation results show that DSDV-Opt, a variation of DSDV protocol using OPT, — (i) achieves the target PDR with 98.7% accuracy while minimizing the overhead energy; (ii) improves the protocol scalability; and (iii) reduces the control traffic for low data traffic intensity.     

A system for the design of packet-switched communication networks with economic tradeoffs

This paper studies the problem of designing a packet-switched communication network with tradeoffs between link costs and response time to users. It consists of assigning capacities to links in the network and determining the routes used by messages for all communicating node pairs in order to minimize total link fixed and variable costs. A tradeoff between link costs and response time to users is achieved by including a constraint that sets an upper limit on the average link queueing delay in the network. The topology of the network and the end-to-end traffic requirements are given. The problem is formulated as a nonlinear integer programming model. Unlike most of previous models, where the best route for a communicating node pair is restricted to a set of prespecified candidate routes, our model considers all possible routes for every communicating node pair. An efficient heuristic based on a Lagrangean relaxation of the problem is developed to generate feasible solutions. The results of extensive computational experiments across a variety of previously used networks are reported. These results indicate that the solution procedure is effective for a wide range of traffic loads and cost structures.     

A multiple-objective grouping genetic algorithm for the cell formation problem with alternative routings

This paper addresses the cell formation problem with alternative part routings, considering machine capacity constraints. Given processes, machine capacities and quantities of parts to produce, the problem consists in defining the preferential routing for each part optimising the grouping of machines into manufacturing cells. The main objective is to minimise the inter-cellular traffic, while respecting machine capacity constraints. To solve this problem, the authors propose an integrated approach based on a multiple-objective grouping genetic algorithm for the preferential routing selection of each part (by solving an associated resource planning problem) and an integrated heuristic for the cell formation problem.     

数据中心网络中相关感知流量整合算法

随着大数据、云计算不断融入人们的日常生活,作为支撑其发展的基础设施--数据中心网络的能耗也在急剧增长。为了解决这个问题,学术界提出了能量感知路由（Energy-Aware Routing,EAR）。EAR的主要思想是通过将流量需求聚集在网络链路的子集,并睡眠未使用的网络设备以节省能量。但是在流量低谷时期频繁地切换网络设备模式可能会导致网络振荡甚至网络性能下降。因此提出了一种相关感知流量整合（Correlation-Aware Traffic Consolidation,CATC）算法。提出了基于软件定义网络（Software Defined Network,SDN）的CATC模型,即在流量整合时考虑了流之间的相关性,并结合链路速率来实现更高的节能。在流量约束和链路容量约束下将CATC模型转换为一个最优流量分配问题,并提出CATC算法来求解。仿真结果显示,与现有的节能算法相比,CATC算法在仅仅增加极少网络延迟的同时可以为数据中心网络节省大约45%的能量。     

Simultaneous Departure Time/Route Choices in Queuing Networks and a Novel Paradox

In this paper, we establish an exact expression of the dynamic traffic assignment (DTA) problem with simultaneous departure time and route (SDR) choices in transportation networks with bottlenecks, where both link and path capacities are time-dependent. Using this expression, closed form of dynamic user equilibrium solutions can be obtained in some special networks. Furthermore, we investigate the DTA-SDR problem in the classical Braess’s network with closed form equilibrium solutions. The explicit results show that an inappropriately added new link could deteriorate the existing network in terms of the increase of individual and system travel costs. The mechanism of this new paradox is quite different from that of the previously discovered ones, and it is the first paradox caused by the simultaneous departure time/route competitions among individuals.     

Robust Optimization Model for a Dynamic Network Design Problem Under Demand Uncertainty

This paper describes a robust optimization approach for a network design problem explicitly incorporating traffic dynamics and demand uncertainty. In particular, we consider a cell transmission model based network design problem of the linear programming type and use box uncertainty sets to characterize the demand uncertainty. The major contribution of this paper is to formulate such a robust network design problem as a tractable linear programming model and demonstrate the model robustness by comparing its solution performance with the nominal solution from the corresponding deterministic model. The results of the numerical experiments justify the modeling advantage of the robust optimization approach and provide useful managerial insights for enacting capacity expansion policies under demand uncertainty.