Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCharting the Complexity Landscape of Waypoint Routing
190
0
0.0
(
0
)
Added by
Klaus-Tycho Foerster
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Modern computer networks support interesting new routing models in which traffic flows from a source s to a destination t can be flexibly steered through a sequence of waypoints, such as (hardware) middleboxes or (virtualized) network functions, to create innovative network services like service chains or segment routing. While the benefits and technological challenges of providing such routing models have been articulated and studied intensively over the last years, much less is known about the underlying algorithmic traffic routing problems. This paper shows that the waypoint routing problem features a deep combinatorial structure, and we establish interesting connections to several classic graph theoretical problems. We find that the difficulty of the waypoint routing problem depends on the specific setting, and chart a comprehensive landscape of the computational complexity. In particular, we derive several NP-hardness results, but we also demonstrate that exact polynomial-time algorithms exist for a wide range of practically relevant scenarios.
rate research
Read More
Mobile Adhoc Network is a kind of wireless ad hoc network where nodes are connected wirelessly and the network is self configuring. MANET may work in a standalone manner or may be a part of another network. In this paper we have compared Random Walk Mobility Model and Random Waypoint Mobility Model over two reactive routing protocols Dynamic Source Routing (DSR) and Adhoc On-Demand Distance Vector Routing (AODV) protocol and one Proactive routing protocol Distance Sequenced Distance Vector Routing (DSDV) Our analysis showed that DSR, AODV & DSDV under Random Walk and Random Way Point Mobility models have similar results for similar inputs however as the pause time increases so does the difference in performance rises. They show that their motion, direction, angle of direction, speed is same under both mobility models. We have made their analysis on packet delivery ratio, throughput and routing overhead. We have tested them with different criteria like different number of nodes, speed and different maximum number of connections.
Network-wide traffic analytics are often needed for various network monitoring tasks. These measurements are often performed by collecting samples at network switches, which are then sent to the controller for aggregation. However, performing such analytics without ``overcounting flows or packets that traverse multiple measurement switches is challenging. Therefore, existing solutions often simplify the problem by making assumptions on the routing or measurement switch placement. We introduce AROMA, a measurement infrastructure that generates a uniform sample of packets and flows regardless of the topology, workload and routing. Therefore, AROMA can be deployed in many settings, and can also work in the data plane using programmable PISA switches. The AROMA infrastructure includes controller algorithms that approximate a variety of essential measurement tasks while providing formal accuracy guarantees. Using extensive simulations on real-world network traces, we show that our algorithms are competitively accurate compared to the best existing solutions despite the fact that they make no assumptions on the underlying network or the placement of measurement switches.
While operating communication networks adaptively may improve utilization and performance, frequent adjustments also introduce an algorithmic challenge: the re-optimization of traffic engineering solutions is time-consuming and may limit the granularity at which a network can be adjusted. This paper is motivated by question whether the reactivity of a network can be improved by re-optimizing solutions dynamically rather than from scratch, especially if inputs such as link weights do not change significantly. This paper explores to what extent dynamic algorithms can be used to speed up fundamental tasks in network operations. We specifically investigate optimizations related to traffic engineering (namely shortest paths and maximum flow computations), but also consider spanning tree and matching applications. While prior work on dynamic graph algorithms focuses on link insertions and deletions, we are interested in the practical problem of link weight changes. We revisit existing upper bounds in the weight-dynamic model, and present several novel lower bounds on the amortized runtime for recomputing solutions. In general, we find that the potential performance gains depend on the application, and there are also strict limitations on what can be achieved, even if link weights change only slightly.
A fundamental component of networking infras- tructure is the policy, used in routing tables and firewalls. Accordingly, there has been extensive study of policies. However, the theory of such policies indicates that the size of the decision tree for a policy is very large ( O((2n)d), where the policy has n rules and examines d features of packets). If this was indeed the case, the existing algorithms to detect anomalies, conflicts, and redundancies would not be tractable for practical policies (say, n = 1000 and d = 10). In this paper, we clear up this apparent paradox. Using the concept of rules in play, we calculate the actual upper bound on the size of the decision tree, and demonstrate how three other factors - narrow fields, singletons, and all-matches make the problem tractable in practice. We also show how this concept may be used to solve an open problem: pruning a policy to the minimum possible number of rules, without changing its meaning.
The network virtualization paradigm envisions an Internet where arbitrary virtual networks (VNets) can be specified and embedded over a shared substrate (e.g., the physical infrastructure). As VNets can be requested at short notice and for a desired time period only, the paradigm enables a flexible service deployment and an efficient resource utilization. This paper investigates the security implications of such an architecture. We consider a simple model where an attacker seeks to extract secret information about the substrate topology, by issuing repeated VNet embedding requests. We present a general framework that exploits basic properties of the VNet embedding relation to infer the entire topology. Our framework is based on a graph motif dictionary applicable for various graph classes. Moreover, we provide upper bounds on the request complexity, the number of requests needed by the attacker to succeed.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
