共查询到20条相似文献,搜索用时 31 毫秒
1.
In telecommunication networks packets are carried from a source s to a destination t on a path that is determined by the underlying routing protocol. Most routing protocols belong to the class of shortest path routing protocols. In such protocols, the network operator assigns a length to each link. A packet going from s to t follows a shortest path according to these lengths. For better protection and efficiency, one wishes to use multiple (shortest) paths between two nodes. Therefore the routing protocol must determine how the traffic from s to t is distributed among the shortest paths. In the protocol called OSPF-ECMP (for Open Shortest Path First-Equal Cost Multiple Path) the traffic incoming at every node is uniformly balanced on all outgoing links that are on shortest paths. In that context, the operator task is to determine the “best” link lengths, toward a goal such as maximizing the network throughput for given link capacities.In this work, we show that the problem of maximizing even a single commodity flow for the OSPF-ECMP protocol cannot be approximated within any constant factor ratio. Besides this main theorem, we derive some positive results which include polynomial-time approximations and an exponential-time exact algorithm. We also prove that despite their weakness, our approximation and exact algorithms are, in a sense, the best possible. 相似文献
2.
Ayşegül Altın Bernard Fortz Mikkel Thorup Hakan Ümit 《4OR: A Quarterly Journal of Operations Research》2009,7(4):301-335
Throughout the last decade, extensive deployment of popular intra-domain routing protocols such as open shortest path first
and intermediate system–intermediate system, has drawn an ever increasing attention to Internet traffic engineering. This
paper reviews optimization techniques that have been deployed for managing intra-domain routing in networks operated with
shortest path routing protocols, and the state-of-the-art research that has been carried out in this direction. 相似文献
3.
Ayşegül Altın Bernard Fortz Mikkel Thorup Hakan Ümit 《Annals of Operations Research》2013,204(1):65-95
Throughout the last decade, extensive deployment of popular intra-domain routing protocols such as open shortest path first (OSPF) and intermediate system–intermediate system (IS-IS), has drawn an ever increasing attention to internet traffic engineering. This paper reviews optimization techniques that have been deployed for managing intra-domain routing in networks operated with shortest path routing protocols, and the state-of-the-art research that has been carried out in this direction. 相似文献
4.
5.
Antonio Polimeni Antonino Vitetta 《Journal of Optimization Theory and Applications》2013,156(3):805-818
In this paper, the relationship between waiting at nodes and the path cost in a transport network is analysed. An exact solution algorithm for generating the shortest path with optimal waiting at the nodes is proposed. The general case is examined, considering a time-dependent network (time influences the cost). To develop a full application, the algorithm is applied in the case of a vehicle routing problem on a real network. 相似文献
6.
Wilson Wang-Kit Thong Guanrong Chen 《Communications in Nonlinear Science & Numerical Simulation》2013,18(3):616-624
This paper reports a study of random deflection routing protocol and its impact on delay-jitter over packet networks. In case of congestion, routers with a random deflection routing protocol can forward incoming packets to links laying off shortest paths; namely, packets can be “deflected” away from their original paths. However, random deflection routing may send packets to several different paths, thereby introducing packet re-ordering. This could affect the quality of receptions, it could also impair the overall performance in transporting data traffic. Nevertheless, the present study reveals that deflection routing could actually reduce delay-jitter when the traffic loading on the network is not heavy. 相似文献
7.
Constrained shortest path problems have many applications in areas like network routing, investments planning and project evaluation as well as in some classical combinatorial problems with high duality gaps where even obtaining feasible solutions is a difficult task in general.We present in this paper a systematic method for obtaining good feasible solutions to hard (doubly constrained) shortest path problems. The algorithm is based essentially on the concept of efficient solutions which can be obtained via parametric shortest path calculations. The computational results obtained show that the approach proposed here leads to optimal or very good near optimal solutions for all the problems studied.From a theoretical point of view, the most important contribution of the paper is the statement of a pseudopolynomial algorithm for generating the efficient solutions and, more generally, for solving the parametric shortest path problem. 相似文献
8.
Martin Behnke Thomas Kirschstein Christian Bierwirth 《European Journal of Operational Research》2021,288(3):794-809
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. 相似文献
9.
Giacomo Nannicini Philippe Baptiste Gilles Barbier Daniel Krob Leo Liberti 《Computational Optimization and Applications》2010,45(1):143-158
Efficiently computing fast paths in large-scale dynamic road networks (where dynamic traffic information is known over a part
of the network) is a practical problem faced by traffic information service providers who wish to offer a realistic fast path
computation to GPS terminal enabled vehicles. The heuristic solution method we propose is based on a highway hierarchy-based
shortest path algorithm for static large-scale networks; we maintain a static highway hierarchy and perform each query on
the dynamically evaluated network, using a simple algorithm to propagate available dynamic traffic information over a larger
part of the road network. We provide computational results that show the efficacy of our approach. 相似文献
10.
We consider the 2-Way Multi Modal Shortest Path Problem (2WMMSPP). Its goal is to find two multi modal paths with total minimal cost, an outgoing path and a return path. The main difficulty lies in the fact that if a private car or bicycle is used during the outgoing path, it has to be picked up during the return path. The shortest return path is typically not equal to the shortest outgoing path as traffic conditions and timetables of public transportation vary throughout the day. In this paper we propose an efficient algorithm based on bi-directional search and provide experimental results on a realistic multi modal transportation network. 相似文献
11.
Matthew J Henchey Rajan Batta Alan Blatt Marie Flanigan Kevin Majka 《The Journal of the Operational Research Society》2015,66(4):570-578
This paper presents tests conducted on routes determined from a Dijkstra-based shortest path problem and a Variance-Constrained Shortest Path problem under varying conditions of traffic and weather in a simulated ‘smart environment’. Utilizing envisioned future advanced transportation systems’ real-time information on traffic parameters allows data fusion techniques to provide situation awareness to its users. Taking advantage of this real-time data, the routing methodologies and data capture techniques studied in this paper provides Emergency Medical Services with better routes when responding to a vehicular crash. Comparing the performance of both routing methodologies in terms of both their ability to provide better routes as well as computation times demonstrates two alternatives for aiding in future emergency response. 相似文献
12.
B. Boffey Francisco Ramón Fernández García Gilbert Laporte Juan A. Mesa Blas Pelegrín Pelegrín 《TOP》1995,3(2):167-220
Summary Many network routing problems, particularly where the transportation of hazardous materials is involved, are multiobjective
in nature; that is, it is desired to optimise not only physical path length but other features as well. Several such problems
are defined here and a general framework for multiobjective routing problems is proposed. The notion of “efficient solution”
is defined and it is demonstrated, by means of an example, that a problem may have very many solutions which are efficient.
Next, potentially useful solution methods for multiobjective routing problems are discussed with emphasis being placed on
the use of shortest/k-shortest path techniques. Finally, some directions for possible further research are indicated.
Invited by B. Pelegrin 相似文献
13.
We study a system of several identical servers in parallel, where a routing decision must be made immediately on a job’s arrival.
Jobs arrive according to a Poisson process, with their processing times following a discrete distribution with finite support.
The processing time of a job is known on arrival and may be used in the routing decision. We propose a policy consisting of
multi-layered round robin routing followed by shortest remaining processing time scheduling at the servers. This policy is
shown to have a heavy traffic limit that is identical to one in which there is a single queue (no routing) and optimal heavy
traffic scheduling. In light traffic, we show that the performance of this policy is worse than round robin routing followed
by shortest remaining processing time scheduling. We also quantify the difference between round robin and multi-layered round
robin routing, which in turn yields insights on the relative importance of routing versus (local) scheduling in such systems.
AMS subject classifications: 68M20 · 60K25
(Work done while both authors were visitors at EURANDOM, P.O. Box 513, 5600 MB Eindhoven, The Netherlands.) 相似文献
14.
谢治州 《数学的实践与认识》2013,43(1)
基于CUMCM-2011 B题中关于嫌疑犯的封堵问题的研究.通过建立描述市区交通网络图的权矩阵,采用求最短路的Dijstra算法求出市区任意两节点的最短路径及路长,构作最佳路径阵和距离矩阵,以此为基点建立封堵路口的最优调度方案模型,再在此基础上建立封堵住嫌疑犯的最优模型,并设计了模型求解的算法.将算法应用于CUMCM-2011 B题中关于嫌疑犯的封堵问题,获得最优封堵方案. 相似文献
15.
Increasing Internet Capacity Using Local Search 总被引:2,自引:0,他引:2
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. 相似文献
16.
移位交换网的最优路由算法 总被引:1,自引:1,他引:0
移位交换网是重要的互联网络之一 ,在并行计算中有着广泛应用 .然而 ,它缺少任意点对间的最短路由算法 .已有的路由算法都不能保证其任意节点对间都是最短路由 .文中给出了一个最短路由算法 ,也是最优路由算法 ,它使得从源节点到目的节点的任何信息都是沿最短路由传输 .同时 ,我们还得到了任意节点对间的距离公式 相似文献
17.
A New Multiobjective Dynamic Routing Method for Multiservice Networks: Modelling and Performance 总被引:1,自引:0,他引:1
There are potential advantages in formulating the routing problems in modern multiservice networks as multiple objective problems. This paper presents a novel hierarchical bi-level multiobjective dynamic routing model for multiservice networks. It is based on a bi-objective shortest path algorithm, with dynamically adapted soft-constraints, to compute alternative paths for each node pair and on a heuristic to synchronously select alternative routing plans for the network in a dynamic alternative routing context. It is a routing method which periodically changes alternative paths as a function of periodic updates of certain QoS related parameters obtained from real-time measurements. The performance of the proposed routing method is compared with two reference dynamic routing methods namely RTNR and DAR by means of a discrete-event simulator.A previous short version of this work was presented at INOC’03 (International Network Optimisation Conference). Work partially supported by programme POSI of the III EC programme cosponsored by FEDER and national funds. 相似文献
18.
We introduce the generalized elementary shortest path problem (GESPP) where in addition to the features of the shortest path problem, nodes belong to predefined non-disjoint clusters. Each cluster is associated to a profit to the cost function, obtained if at least one element in the cluster appears in the path. Several applications can be considered as school bus routing, pricing problems, or telecommunication network design. Thus, depending on the case, clusters could be interpreted as groups of nodes with linking features as, for example, being easily reachable from each other, or some kind of coverage guarantee. We compare the GESPP to similar problems in the literature and we propose a two-phase heuristic algorithm for graphs including negative cycles. Tests on random instances with up to 100 nodes show an average gap of 0.3% to the best known solutions computed in 2.8s in average. 相似文献
19.
In Multi-Protocol Label Switching (MPLS) networks, traffic demands can be routed along tunnels called Label Switched Paths (LSPs). A tunnel is characterized by a path in the network and a reserved bandwidth. These tunnels can be created and deleted dynamically, depending on traffic demand arrivals or departures. After several operations of this type, the network resource utilization can be unsatisfactory, with congestion or too long routing paths for instance. One way to improve it is to reroute tunnels; the rerouting process depends on the LSP Quality of Service (QoS) requirements. 相似文献
20.
Changyong Zhang 《The Journal of the Operational Research Society》2017,68(8):935-951
Link weights are the main parameters of shortest path routing protocols, the most commonly used protocols for IP networks. The problem of optimally setting link weights for unique shortest path routing is addressed. Due to the complexity of the constraints involved, there exist challenges to formulate the problem in such a way based on which a more efficient solution algorithm than the existing ones may be developed. In this paper, an exact formulation is first introduced and then mathematically proved correct. It is further illustrated that the formulation has advantages over a prior one in terms of both constraint structure and model size for a proposed decomposition method to solve the problem. 相似文献