On Braess's paradox and routing algorithms Vieira, Luiz F. M.; Vieira, Marcos A. M.
Internet technology letters,
May/June 2022, 2022-05-00, Volume:
5, Issue:
3
Journal Article
Peer reviewed
In road traffic networks, famous Braess's Paradox demonstrated that the addition of resources can cause the traffic network performance to decrease. The addition of a new route can cause drivers to ...use this new road and end up reaching a Nash equilibrium which increases the overall travel time. Unlike previous studies that have investigated the paradox in the context of game theory, road traffic network, and latency edge data network, in this paper we show the novel issue of how the addition of resources can lead to a decrease in data network performance while using certain routing algorithm (ie, shortest widest path—used for quality‐of‐service routing, quickest path, geographic routing, quality‐of‐service energy‐aware routing), without even considering congestion. We demonstrate the idea for any network size and describe the fundamental issue. Finally, we describe solutions based on current network's technology.
Network topolgy with capacity and propagation delay with more resources.
In this paper, a routing method based on reinforcement learning (RL) under software-defined networks (SDN), namely the Q-learning widest-path routing algorithm (Q-WPRA), is proposed. This algorithm ...processes the reward function according to the link bandwidth in the execution environment to find the optimal (i.e., widest) transmission path with the maximum bandwidth between the source and the destination through RL. The experimental results reveal that the Q-WPRA is outperformance than Dijkstra’s algorithm and Dijkstra’s widest-path algorithm to find the widest transmission path in SDN environment under different bandwidths, loss rates, and background traffic.
In this paper, the generalized widest path problem (or generalized maximum capacity problem) is studied. This problem is denoted by the GWPP. The classical widest path problem is to find a path from ...a source (s) to a sink (t) with the highest capacity among all possible s-t paths. The GWPP takes into account the presence of loss/gain factors on arcs as well. The GWPP aims to find an s-t path considering the loss/gain factors while satisfying the capacity constraints. For solving the GWPP, three strongly polynomial time algorithms are presented. Two algorithms only work in the case of losses. The first one is less efficient than the second one on a CPU, but it proves to be more efficient on large networks if it parallelized on GPUs. The third algorithm is able to deal with the more general case of losses/gains on arcs. An example is considered to illustrate how each algorithm works. Experiments on large networks are conducted to compare the efficiency of the algorithms proposed.
Edge computing is one of the emerging technologies aiming to enable timely computation at the network edge. With virtualization technologies, the role of the traditional edge providers is separated ...into two: edge infrastructure providers (EIPs), who manage the physical edge infrastructure, and edge service providers (ESPs), who purchase slices of physical resources (e.g., CPU, bandwidth, memory space, disk storage) from EIPs and then cache service entities to offer their own value-added services to end users. These value-added services are also called virtual network function or VNF. As we know, edge computing environments are dynamic, and the requirements of edge service for computing resources usually fluctuate over time. Thus, when the demand of a VNF cannot be satisfied, we need to design the strategies for migrating the VNF so as to meet its demand and retain the network performance. In this paper, we concentrate on migrating VNFs efficiently (MV), such that the migration can meet the bandwidth requirement for data transmission. We prove that MV is NP-complete. We present several exact and heuristic solutions to tackle it. Extensive simulations demonstrate that the proposed heuristics are efficient and effective.
Online energy aware routing in wireless networks is the problem of finding energy efficient routes that maximize the network lifetime without the knowledge of future message flows. To maximize ...network lifetime, the paths for message flows are chosen in such a way that the total energy consumed along the path is minimized while avoiding energy depleted nodes. Finding paths which consume minimum energy and finding paths which do not use energy depleted nodes lead to conflicting objectives. In this paper, we propose two-phased energy aware routing strategies that balance these two conflicting objectives by transforming the routing problem into a multi-metric widest path problem. We find that the proposed approaches outperform the best-known algorithms in the literature. We also demonstrate a simple but insightful relationship between the total energy required along a path and the minimum remaining energy of a node along the path. We further exploit this relationship to show that staying within the solution space of paths with high residual energy
and low total energy provides much improved lifetimes in general.
User-controlled circuit-switched optical networks are gaining popularity in an effort to fulfill the insatiable data transport needs of the online community. In this paper we consider the resource ...allocation challenges that arise in such networks, in particular problems related to construction of end-to-end lightpaths for carrying large multimedia streams. Specifically, we discuss variations of the least cost and widest path problems that address two unique aspects of the user-controlled environment. First, since network resources are exposed for user-control using a service-oriented software control plane, each lightpath is subject to an expiry time. Second, because Wavelength Division Multiplexing (WDM) and resource partitioning introduces multiple redundant paths, classic least cost path computations tend to yield multiple optimal solutions, and so it is useful to break ties among these in a judicious manner. We present polynomial-time path selection techniques that address these issues using efficient data structures. We also show the benefit of breaking ties in shortest path computations in a manner that reduces harmful fragmentation of capacity.
Telecommunication services are pervasive in today's human activity and are required to offer reliable and quality-of-service(QoS)-aware guaranteed services. In global path protection, the working ...path between a source and a destination can be protected by a backup path, which ensures data transfer in the event of a failure that makes the working path to be unavailable. Multipath and disjoint routing may require the calculation of disjoint paths maximizing the total bandwidth of the path pair (or set of paths) or the calculation of maximum-bandwidth disjoint paths. In this paper, a lexicographic optimization problem for obtaining maximum-bandwidth disjoint paths, and then maximizing the bandwidth of the widest path in the pair, is formalized. An effective heuristic for addressing this problem is presented.
Wireless Sensor Network (WSN) comprises the less power consuming, light weight and effective Sensor Nodes (SNs) for higher network performance. ZigBee is the real time application for the WSN used ...for low-cost data and energy consumption characteristics. ZigBee is a robust network certain application of which has come out with a critically low designation for less data rate, long delivery delay and packet loss as well in order to lower the cost. However, ZigBee devices have many potential features to make a splendid wireless network. Hence, putting an improvement analogy inside the performance parameter is a way to overcome the limitations of ZigBee usage in certain scales. ZigBee follows a model for its node distribution, traffic routing and Quality of Service (QoS). The QoS indicates the efficiency and performance of any network. The increase in efficiency of QoS on the ZigBee network lies in the realization of maximizing throughput of the network. This paper is destined to represent the improved QoS in the ZigBee network applying Stochastic and Widest Path models. Riverbed Simulator v17.5 is used to investigate foremost QoS parameters in the ZigBee network. The optimized result of this study will be handy in the application field of the ZigBee network. And it also best fits for the deployment of the large-scale device to device communication.
Large cascade blackouts are generally catastrophic both economically and socially, when they occur. In this work, a transmission constrained, 5-bus power grid was simulated using PowerWorld and the ...impact of lines outages on the violation of loading capacities of network links was studied. We use the Widest Path Algorithm(WPA) and Power Flow Redistribution Algorithm(PFRA) to redistribute power flow in the network, using lines residual capacity and thermal capacity as criteria for redistribution. In cases, where (WPA) and (PFRA) could not reduce line loading, such path gives indication of where transmission should be reinforced. In this work, we propose a new and innovative techniques for mitigation of cascade blackout and well as network reinforcement.
The widest k -set of disjoint paths problem Ribeiro, Marco Antônio; Carvalho, Iago Augusto; Pereira, Armando Honório
R.A.I.R.O. Recherche opérationnelle,
01/2023, Volume:
57, Issue:
1
Journal Article
Peer reviewed
Open access
Finding disjoint and widest paths are key problems in telecommunication networks. In this paper, we study the Widest k -set of Disjoint Paths Problem (WKDPP), an NP -Hard optimization problem that ...considers both aspects. Given a digraph G = ( N , A ), WKDPP consists of computing k arc-disjoint paths between two nodes such that the sum of its minimum capacity arcs is maximized. We present three mathematical formulations for WKDPP, a symmetry-breaking inequality set, and propose two heuristic algorithms. Computational experiments compare the proposed heuristics with another from the literature to show the effectiveness of the proposed methods.
PDF
