Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userRules in Play: On the Complexity of Routing Tables and Firewalls
66
0
0.0
(
0
)
Added by
Ayush Shah
Publication date
2015
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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.
Reactive routing protocols are gaining popularity due to their event driven nature day by day. In this vary paper, reactive routing is studied precisely. Route request, route reply and route maintenance phases are modeled with respect to control overhead. Control overhead varies with respect to change in various parameters. Our model calculates these variations as well. Besides modeling, we chose three most favored reactive routing protocols as Ad-Hoc on Demand Distance Vector (AODV), Dynamic Source Routing (DSR) and Dynamic MANET on Demand (DYMO) for our experiments. We simulated these protocols using ns-2 for a detailed comparison and performance analysis with respect to mobility and scalability issues keeping metrics of throughput, route delay and control over head. Their performances and comparisons are extensively presented in last part of our work.
To ensure seamless communication in wireless multi-hop networks, certain classes of routing protocols are defined. This vary paper, is based upon proactive routing protocols for Wireless multihop networks. Initially, we discuss Destination Sequence Distance Vector (DSDV), Fish-eye State Routing (FSR) and Optimized Link State Routing (OLSR), precisely followed by mathematical frame work of control overhead regarding proactive natured routing protocols. Finally, extensive simulations are done using NS 2 respecting above mentioned routing protocols covering mobility and scalability issues. Said protocols are compared under mobile and dense environments to conclude our performance analysis.
In this paper, we design a greedy routing on networks of mobile agents. In the greedy routing algorithm, every time step a packet in agent $i$ is delivered to the agent $j$ whose distance from the destination is shortest among searched neighbors of agent $i$. Based on the greedy routing, we study the traffic dynamics and traffic-driven epidemic spreading on networks of mobile agents. We find that the transportation capacity of networks and the epidemic threshold increase as the communication radius increases. For moderate moving speed, the transportation capacity of networks is the highest and the epidemic threshold maintains a large value. These results can help controlling the traffic congestion and epidemic spreading on mobile networks.
Multi-channel wireless networks are increasingly being employed as infrastructure networks, e.g. in metro areas. Nodes in these networks frequently employ directional antennas to improve spatial throughput. In such networks, given a source and destination, it is of interest to compute an optimal path and channel assignment on every link in the path such that the path bandwidth is the same as that of the link bandwidth and such a path satisfies the constraint that no two consecutive links on the path are assigned the same channel, referred to as Channel Discontinuity Constraint (CDC). CDC-paths are also quite useful for TDMA system, where preferably every consecutive links along a path are assigned different time slots. This paper contains several contributions. We first present an $O(N^{2})$ distributed algorithm for discovering the shortest CDC-path between given source and destination. This improves the running time of the $O(N^{3})$ centralized algorithm of Ahuja et al. for finding the minimum-weight CDC-path. Our second result is a generalized $t$-spanner for CDC-path; For any $theta>0$ we show how to construct a sub-network containing only $O(frac{N}{theta})$ edges, such that that length of shortest CDC-paths between arbitrary sources and destinations increases by only a factor of at most $(1-2sin{tfrac{theta}{2}})^{-2}$. We propose a novel algorithm to compute the spanner in a distributed manner using only $O(nlog{n})$ messages. An important conclusion of this scheme is in the case of directional antennas are used. In this case, it is enough to consider only the two closest nodes in each cone.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
