ATM Routing Algorithms for Multimedia Traffic in Private ATM Networks

The goal of this paper is to recommend a good Private Network-to-Network Interface (PNNI) routing algorithm for private ATM networks. A good routing algorithm has to work well with multimedia traffic with several quality of service (QoS) requirements (such as cell loss ratio, cell delay and its variation etc.) in different networks under various traffic conditions. The multiplicity of QoS requirements makes the routing problem NP-complete, so our approach to the problem is based on large scale simulations involving several empirical algorithms (compliant with the PNNI routing specification) which have been tested for different network topologies and traffic scenarios. Based on analysis of tradeoffs involving performance metrics (such as blocking rate, complexity, load distribution) we recommend a consistently good routing algorithm for single domain ATM networks.     

ATM network design for corporate networks

Asynchronous transfer mode (ATM) networks play an important role in support of distributed applications and modern corporate systems. The applications that use these architectures transfer high volumes of data in high-speed bursts and have stringent delay requirements. To address these needs, network managers seek cost efficient network solutions that provide network capacity sufficient to support high-speed applications.In this paper we present a new formulation and solution procedure for designing ATM networks to support corporate applications. Given the locations of the application servers and multiple clients we would like to design a minimum cost ATM network by which the clients can access the servers. Most of the previous work done in this area separates the problem into a routing problem (virtual circuit routing) and an assignment (virtual path assignment) problem. Thus, the solutions tend to be sub-optimal in the combined problem. This research optimizes virtual path (VP) assignment and virtual circuit (VC) routing simultaneously. We formulate the combined problem explicitly and develop an effective solution method. The solution method provides the designer with virtual paths and virtual circuits over which the actual communication takes place. Computational results are provided.     

Optimal routing in non-geostationary satellite ATM networks with intersatellite link capacity constraints

The trend toward broadband communications in space is foreseeable, and its features predestine ATM as the basic mode of operation. Some of the low and medium earth orbit satellite concepts make use of intersatellite links (ISLs) to provide global connectivity with minimal usage of terrestrial fixed network resources. Interconnecting neighbouring satellites with ISLs results in a partially meshed switching subnetwork in space. The ISLs have a time-varying distance or may even lose sight of each other. This feature of the ISL topology dynamics significantly increases the complexity of connection-oriented network operation and routing. We deal with the routing problem to minimize the virtual path connection handover rate and path delay in the time-varying ISL subnetwork topology with ISL capacity constraints. A heuristic algorithm is proposed to deal with this problem, which is based on Lagrangean relaxation and dynamic programming. When there is sufficient capacity at every ISL, the algorithm produces an optimal solution easily using only dynamic programming. For evaluation of our algorithm, some computational results have been presented. These results show that our optimization algorithm can produce a solution close to an optimal solution when there exist ISL capacity constraints.     

基于交通流的多模糊时间窗车辆路径优化

研究了基于交通流的多模糊时间窗车辆路径问题,考虑了实际中不断变化的交通流以及客户具有多个模糊时间窗的情况,以最小化配送总成本和最大化客户满意度为目标,构建基于交通流的多模糊时间窗车辆路径模型。根据伊藤算法的基本原理,设计了求解该模型的改进伊藤算法,结合仿真算例进行了模拟计算,并与蚁群算法的计算结果进行了对比分析,结果表明,利用改进伊藤算法求解基于交通流的多模糊时间窗车辆路径问题,迭代次数小,效率更高,能够在较短的时间内收敛到全局最优解,可以有效的求解多模糊时间窗车辆路径问题。     

Approximate decomposition methods for the analysis of multicommodity flow routing in generalized queuing networks

In this study we deal with network routing decisions and approximate performance evaluation approaches for generalized open queuing networks (OQN), in which commodities enter the network, receive service at one or more arcs and then leave the network. Exact performance evaluation has been applied for the analysis of Jackson OQN, where the arrival and service processes of the commodities are assumed to be Poisson. However, the Poisson processes’ hypotheses are not a plausible or acceptable assumption for the analysis of generalized OQN, as their arrival and service processes can be much less variable than Poisson processes, resulting in overestimated system performance measures and inappropriate flow routing solutions. In this paper we merge network routing algorithms and network decomposition methods to solve multicommodity flow problems in generalized OQN. Our focus is on steady-state performance measures as average delays and waiting times in queue. The main contributions are twofold: (i) to highlight that solving the corresponding multicommodity flow problem by representing the generalized OQN as a Jackson OQN may be a poor approximation and may lead to inaccurate estimates of the system performance measures, and (ii) to present a multicommodity flow algorithm based on a routing step and on an approximate decomposition step, which leads to much more accurate solutions. Computational results are presented in order to show the effectiveness of the proposed approach.     

Solving the vehicle routing problem with time windows and multiple routes exactly using a pseudo-polynomial model

In this paper, we address a variant of the vehicle routing problem called the vehicle routing problem with time windows and multiple routes. It considers that a given vehicle can be assigned to more than one route per planning period. We propose a new exact algorithm for this problem. Our algorithm is iterative and it relies on a pseudo-polynomial network flow model whose nodes represent time instants, and whose arcs represent feasible vehicle routes. This algorithm was tested on a set of benchmark instances from the literature. The computational results show that our method is able to solve more instances than the only other exact method described so far in the literature, and it clearly outperforms this method in terms of computing time.     

Routing trains through a railway station based on a node packing model

In this paper, we describe the problem of routing trains through a railway station. This routing problem is a subproblem of the automatic generation of timetables for the Dutch railway system. The problem of routing trains through a railway station is the problem of assigning each of the involved trains to a route through the railway station, given the detailed layout of the railway network within the station and given the arrival and departure times of the trains. When solving this routing problem, several aspects such as capacity, safety, and customer service have to be taken into account. In this paper, we describe this routing problem in terms of a weighted node packing problem. Furthermore, we describe an algorithm for solving this routing problem to optimality. The algorithm is based on preprocessing, valid inequalities, and a branch-and-cut approach. The preprocessing techniques aim at identifying superfluous nodes which can be removed from the problem instance. The characteristics of the preprocessing techniques with respect to propagation are investigated. We also present the results of a computational study in which the model, the preprocessing techniques and the algorithm are tested based on data related to the railway stations Arnhem, Hoorn and Utrecht CS in the Netherlands.     

Routing of Railway Carriages

In the context of organizing timetables for railway companies the following railway carriage routing problem occurs. Given a timetable containing rail links with departure and destination times/stations and the composition of the trains, find a routing of railway carriages such that the required carriages are always available when a train departs. The problem is formulated as an integer multi-commodity network flow problem with nonlinear objective function. We will present a local search approach for this NP-hard problem. The approach uses structural properties of the integer multi-commodity network flow formulation of the problem. Computational results for a real world instance are given.     

Routing-efficient CDS construction in Disk-Containment Graphs

In wireless networks, Connected Dominating Sets (CDSs) are widely used as virtual backbones for communications. On one hand, reducing the backbone size will reduce the maintenance overhead. So how to minimize the CDS size is a critical issue. On the other hand, when evaluating the performance of a wireless network, the hop distance between two communication nodes, which reflect the energy consumption and response delay, is of great importance. Hence how to minimize the routing cost is also a key problem for constructing the network virtual backbone. In this paper, we study the problem of constructing applicable CDS in wireless networks in terms of size and routing cost. We formulate a wireless network as a Disk-Containment Graph (DCG), which is a generalization of the Unit-Disk Graph (UDG), and we develop an efficient algorithm to construct CDS in such kind of graphs. The algorithm contains two parts and is flexible to balance the performance between the two metrics. We also analyze the algorithm theoretically. It is shown that our algorithm has provable performance in minimizing the CDS size and reducing the communication distance for routing.     

On the computational complexity of continuous routing

We study the problem of routing and broadcasting messages in a network, in which messages are generated at processors at arbitrary times and each message must reach its destination by a specific deadline. We present distributed and global routing algorithms for some restricted continuous routing problems on arrays of processors. We show that distributed algorithms are unlikely to exist in more general situations by giving an NP-hardness proof for their corresponding feasibility problem; i.e., the problem of determining whether all messages can be routed without violating the constraints of the network. We also present a distributed algorithm for the continuous broadcasting problem.     

A column generation approach for an emission-oriented vehicle routing problem on a multigraph

In this work, an emission-minimizing vehicle routing problem with heterogeneous vehicles and a heterogeneous road and traffic network is considered as it is typical in urban areas. Depending on the load of the vehicle, there exist multiple emission-minimal arcs for traveling between two locations. To solve the vehicle routing problem efficiently, a column generation approach is presented. At the core of the procedure an emission-oriented elementary shortest path problem on a multigraph is solved by a backward labeling algorithm. It is shown that the labeling algorithm can be sped up by adjusting the dual master program and by restricting the number of labels propagated in the sub-problem. The column generation technique is used to setup a fast heuristic as well as a branch-and-price algorithm. Both procedures are evaluated based on test instances with up to 100 customers. It turns out that the heuristic approach is very effective and generates near-optimal solutions with gaps below 0.1% on average while only requiring a fraction of the runtime of the exact approach.     

Multi-period traffic routing in satellite networks

We introduce a traffic routing problem over an extended planning horizon that appears in geosynchronous satellite networks. Unlike terrestrial (e.g., fiber optic) networks, routing on a satellite network is not transparent to the customers. As a result, a route change is associated with significant monetary penalties that are usually in the form of discounts (up to 40%) offered by the satellite provider to the customer that is affected. The notion of these rerouting penalties requires the network planners to explicitly consider these penalties in their routing decisions over multiple time periods and introduces novel challenges that have not been considered previously in the literature. We develop a branch-and-price-and-cut procedure to solve this problem and describe an algorithm for the associated pricing problem. Our computational work demonstrates that the use of a multi-period optimization procedure as opposed to a myopic period-by-period approach can result in cost reductions up to 13% depending on problem characteristics and network size considered. These cost reductions correspond to potential savings of several hundred million dollars for large satellite providers.     

Computational experience with a difficult mixedinteger multicommodity flow problem

The following problem arises in the study of lightwave networks. Given a demand matrix containing amounts to be routed between corresponding nodes, we wish to design a network with certain topological features, and in this network, route all the demands, so that the maximum load (total flow) on any edge is minimized. As we show, even small instances of this combined design/routing problem are extremely intractable. We describe computational experience with a cutting plane algorithm for this problem.This research was partially supported by a Presidential Young Investigator Award and the Center for Telecommunications Research, Columbia University.Corresponding author.     

A traffic control algorithm for Clos network type ATM switches

This paper presents a new traffic control algorithm for asynchronous transfer mode (ATM) switches composed of Clos network type switch fabric. In most traffic control algorithms previously proposed, an ATM switch has been considered as a single node, although the switch fabric of an ATM switch is usually of a network type. In this paper, we suggest a new control algorithm that is designed not only for the ATM network but also for the switch fabric and that can maintain high speed even in cases where buffer capacity of the switch fabric is limited. Main modules of the suggested algorithm are a traffic status detection mechanism based on non-parametric statistical tests, a cell-loss detection mechanism, and a cluster-based fair share computation procedure. Results of simulation experiments show that the suggested algorithm satisfactorily adjusts traffic rate of available bit rate services according to changes in traffic rate used by quality of service (QoS) guaranteed services. The results also show that the algorithm prevents cell losses relatively well and keeps the delay time of QoS guaranteed services short enough.     

Virtual path layouts optimizing total hop count on ATM tree networks

This paper presents some algorithmic results concerning virtual path layouts for the one-to-many communication problem in ATM tree networks. The ATM network model is based on covering the network with a layout of virtual paths, under some constraints on the allowed load, namely, the number of paths that can share an edge. The quality measure used is the hop count, namely, the number of edges traversed between two vertices that need to communicate. Whereas most former results concerned the maximum hop count of the virtual path layout, our interest here is in measuring its total hop count, or alternatively its average hop count. The paper presents a dynamic programming algorithm for planning ATM network layouts with minimal total hop count for one-to-many requirements under load constraints over the class of tree networks.     

A new model and hybrid approach for large scale inventory routing problems

This paper studies an inventory routing problem (IRP) with split delivery and vehicle fleet size constraint. Due to the complexity of the IRP, it is very difficult to develop an exact algorithm that can solve large scale problems in a reasonable computation time. As an alternative, an approximate approach that can quickly and near-optimally solve the problem is developed based on an approximate model of the problem and Lagrangian relaxation. In the approach, the model is solved by using a Lagrangian relaxation method in which the relaxed problem is decomposed into an inventory problem and a routing problem that are solved by a linear programming algorithm and a minimum cost flow algorithm, respectively, and the dual problem is solved by using the surrogate subgradient method. The solution of the model obtained by the Lagrangian relaxation method is used to construct a near-optimal solution of the IRP by solving a series of assignment problems. Numerical experiments show that the proposed hybrid approach can find a high quality near-optimal solution for the IRP with up to 200 customers in a reasonable computation time.     

Optimizing flow rates in a queueing network with side constraints

In this paper, modified versions of the classical deterministic maximum flow and minimum cost network flow problems are presented in a stochastic queueing environment. In the maximum flow network model, the throughput rate in the network is maximized such that for each arc of the network the resulting probability of finding congestion along that arc in excess of a desirable threshold does not exceed an acceptable value. In the minimum cost network flow model, the minimum cost routing of a flow of given magnitude is determined under the same type of constraints on the arcs. After proper transformations, these models are solved by Ford and Fulkerson's labeling algorithm and out-of-kilter algorithm, respectively.     

An algorithm for node-capacitated ring routing

A strongly polynomial time algorithm is described to solve the node-capacitated routing problem in an undirected ring network.     

Increasing Internet Capacity Using Local Search

Open Shortest Path First (OSPF) is one of the most commonly used intra-domain internet routing protocol. Traffic flow is routed along shortest paths, splitting flow evenly at nodes where several outgoing links are on shortest paths to the destination. The weights of the links, and thereby the shortest path routes, can be changed by the network operator. The weights could be set proportional to the physical lengths of the links, but often the main goal is to avoid congestion, i.e. overloading of links, and the standard heuristic recommended by Cisco (a major router vendor) is to make the weight of a link inversely proportional to its capacity.We study the problem of optimizing OSPF weights for a given a set of projected demands so as to avoid congestion. We show this problem is NP-hard, even for approximation, and propose a local search heuristic to solve it. We also provide worst-case results about the performance of OSPF routing vs. an optimal multi-commodity flow routing. Our numerical experiments compare the results obtained with our local search heuristic to the optimal multi-commodity flow routing, as well as simple and commonly used heuristics for setting the weights. Experiments were done with a proposed next-generation AT&T WorldNet backbone as well as synthetic internetworks.     

Neural and delay based heuristics for the Steiner problem in networks

High speed networks such as the B-ISDN must be adequately equipped to handle multipoint communication in a fast and economical manner. Multicast applications include desktop video conferencing, distance learning, distributed database applications, etc. In networks employing the asynchronous transfer mode (ATM) technology, routing a multicast is achieved by constructing a tree that spans the source and all the destinations. For the purpose of routing, the network is modeled as a weighted, undirected graph. The graph-theoretic solution is to find a minimum Steiner tree for the graph given a set of destinations. This formulation suffices for building multicast trees with a single optimization constraint as would be the xcase for best effort transport. For real-time traffic, however, it is necessary to ensure that the delay between the sender and each of the receivers is bounded. In this case the network is modeled as an undirected graph, where the edges have both a cost and a delay associated with them. The graph-theoretic solution is then to find a constrained minimum Steiner tree such that the delay between the source and each of the destinations does not violate the specified bound. Both of these problems are NP-complete. In this paper we review prior work on the multipoint routing problem and discuss the formulation of the unconstrained and constrained Steiner problems. We use the random neural network (RNN) to significantly improve the quality of trees found by the two existing best heuristics for finding Steiner trees - the minimum spanning tree heuristic and the average distance heuristic. We also develop a new heuristic for finding delay constrained Steiner trees. Experimental results are presented which show that the new heuristics improve significantly over existing ones.