Matching Items (4)
Filtering by
- Genre: Masters Thesis
Description
New OpenFlow switches support a wide range of network applications, such as firewalls, load balancers, routers, and traffic monitoring. While ternary content addressable memory (TCAM) allows switches to process packets at high speed based on multiple header fields, today's commodity switches support just thousands to tens of thousands of forwarding rules. To allow for finer-grained policies on this hardware, efficient ways to support the abstraction of a switch are needed with arbitrarily large rule tables. To do so, a hardware-software hybrid switch is designed that relies on rule caching to provide large rule tables at low cost. Unlike traditional caching solutions, neither individual rules are cached (to respect rule dependencies) nor compressed (to preserve the per-rule traffic counts). Instead long dependency chains are ``spliced'' to cache smaller groups of rules while preserving the semantics of the network policy. The proposed hybrid switch design satisfies three criteria: (1) responsiveness, to allow rapid changes to the cache with minimal effect on traffic throughput; (2) transparency, to faithfully support native OpenFlow semantics; (3) correctness, to cache rules while preserving the semantics of the original policy. The evaluation of the hybrid switch on large rule tables suggest that it can effectively expose the benefits of both hardware and software switches to the controller and to applications running on top of it.
ContributorsAlipourfard, Omid (Author) / Syrotiuk, Violet R. (Thesis advisor) / Richa, Andréa W. (Committee member) / Xue, Guoliang (Committee member) / Arizona State University (Publisher)
Created2014
Description
Exhaustive testing is generally infeasible except in the smallest of systems. Research
has shown that testing the interactions among fewer (up to 6) components is generally
sufficient while retaining the capability to detect up to 99% of defects. This leads to a
substantial decrease in the number of tests. Covering arrays are combinatorial objects
that guarantee that every interaction is tested at least once.
In the absence of direct constructions, forming small covering arrays is generally
an expensive computational task. Algorithms to generate covering arrays have been
extensively studied yet no single algorithm provides the smallest solution. More
recently research has been directed towards a new technique called post-optimization.
These algorithms take an existing covering array and attempt to reduce its size.
This thesis presents a new idea for post-optimization by representing covering
arrays as graphs. Some properties of these graphs are established and the results are
contrasted with existing post-optimization algorithms. The idea is then generalized to
close variants of covering arrays with surprising results which in some cases reduce
the size by 30%. Applications of the method to generation and test prioritization are
studied and some interesting results are reported.
has shown that testing the interactions among fewer (up to 6) components is generally
sufficient while retaining the capability to detect up to 99% of defects. This leads to a
substantial decrease in the number of tests. Covering arrays are combinatorial objects
that guarantee that every interaction is tested at least once.
In the absence of direct constructions, forming small covering arrays is generally
an expensive computational task. Algorithms to generate covering arrays have been
extensively studied yet no single algorithm provides the smallest solution. More
recently research has been directed towards a new technique called post-optimization.
These algorithms take an existing covering array and attempt to reduce its size.
This thesis presents a new idea for post-optimization by representing covering
arrays as graphs. Some properties of these graphs are established and the results are
contrasted with existing post-optimization algorithms. The idea is then generalized to
close variants of covering arrays with surprising results which in some cases reduce
the size by 30%. Applications of the method to generation and test prioritization are
studied and some interesting results are reported.
ContributorsKaria, Rushang Vinod (Author) / Colbourn, Charles J (Thesis advisor) / Syrotiuk, Violet (Committee member) / Richa, Andréa W. (Committee member) / Arizona State University (Publisher)
Created2015
Description
In a multi-robot system, locating a team robot is an important issue. If robots
can refer to the location of team robots based on information through passive action
recognition without explicit communication, various advantages (e.g. improving security
for military purposes) can be obtained. Specifically, when team robots follow
the same motion rule based on information about adjacent robots, associations can
be found between robot actions. If the association can be analyzed, this can be a clue
to the remote robot. Using these clues, it is possible to infer remote robots which are
outside of the sensor range.
In this paper, a multi-robot system is constructed using a combination of Thymio
II robotic platforms and Raspberry pi controllers. Robots moving in chain-formation
take action using motion rules based on information obtained through passive action
recognition. To find associations between robots, a regression model is created using
Deep Neural Network (DNN) and Long Short-Term Memory (LSTM), one of state-of-art technologies.
The input data of the regression model is divided into historical data, which
are consecutive positions of the robot, and observed data, which is information about the
observed robot. Historical data is sequence data that is analyzed through the LSTM
layer. The accuracy of the regression model designed using DNN can vary depending
on the quantity and quality of the input. In this thesis, three different input situations
are assumed for comparison. First, the amount of observed data is different, second, the
type of observed data is different, and third, the history length is different. Comparative
models are constructed for each case, and prediction accuracy is compared to analyze
the effect of input data on the regression model. This exploration validates that these
methods from deep learning can reduce the communication demands in coordinated
motion of multi-robot systems
can refer to the location of team robots based on information through passive action
recognition without explicit communication, various advantages (e.g. improving security
for military purposes) can be obtained. Specifically, when team robots follow
the same motion rule based on information about adjacent robots, associations can
be found between robot actions. If the association can be analyzed, this can be a clue
to the remote robot. Using these clues, it is possible to infer remote robots which are
outside of the sensor range.
In this paper, a multi-robot system is constructed using a combination of Thymio
II robotic platforms and Raspberry pi controllers. Robots moving in chain-formation
take action using motion rules based on information obtained through passive action
recognition. To find associations between robots, a regression model is created using
Deep Neural Network (DNN) and Long Short-Term Memory (LSTM), one of state-of-art technologies.
The input data of the regression model is divided into historical data, which
are consecutive positions of the robot, and observed data, which is information about the
observed robot. Historical data is sequence data that is analyzed through the LSTM
layer. The accuracy of the regression model designed using DNN can vary depending
on the quantity and quality of the input. In this thesis, three different input situations
are assumed for comparison. First, the amount of observed data is different, second, the
type of observed data is different, and third, the history length is different. Comparative
models are constructed for each case, and prediction accuracy is compared to analyze
the effect of input data on the regression model. This exploration validates that these
methods from deep learning can reduce the communication demands in coordinated
motion of multi-robot systems
ContributorsKang, Sehyeok (Author) / Pavlic, Theodore P (Thesis advisor) / Richa, Andréa W. (Committee member) / Yang, Yezhou (Committee member) / Arizona State University (Publisher)
Created2020
Description
This thesis addresses the following fundamental maximum throughput routing problem: Given an arbitrary edge-capacitated n-node directed network and a set of k commodities, with source-destination pairs (s_i,t_i) and demands d_i> 0, admit and route the largest possible number of commodities -- i.e., the maximum throughput -- to satisfy their demands.
The main contributions of this thesis are three-fold: First, a bi-criteria approximation algorithm is presented for this all-or-nothing multicommodity flow (ANF) problem. This algorithm is the first to achieve a constant approximation of the maximum throughput with an edge capacity violation ratio that is at most logarithmic in n, with high probability. The approach used is based on a version of randomized rounding that keeps splittable flows, rather than approximating those via a non-splittable path for each commodity: This allows it to work for arbitrary directed edge-capacitated graphs, unlike most of the prior work on the ANF problem. The algorithm also works if a weighted throughput is considered, where the benefit gained by fully satisfying the demand for commodity i is determined by a given weight w_i>0. Second, a derandomization of the algorithm is presented that maintains the same approximation bounds, using novel pessimistic estimators for Bernstein's inequality. In addition, it is shown how the framework can be adapted to achieve a polylogarithmic fraction of the maximum throughput while maintaining a constant edge capacity violation, if the network capacity is large enough. Lastly, one important aspect of the randomized and derandomized algorithms is their simplicity, which lends to efficient implementations in practice. The implementations of both randomized rounding and derandomized algorithms for the ANF problem are presented and show their efficiency in practice.
The main contributions of this thesis are three-fold: First, a bi-criteria approximation algorithm is presented for this all-or-nothing multicommodity flow (ANF) problem. This algorithm is the first to achieve a constant approximation of the maximum throughput with an edge capacity violation ratio that is at most logarithmic in n, with high probability. The approach used is based on a version of randomized rounding that keeps splittable flows, rather than approximating those via a non-splittable path for each commodity: This allows it to work for arbitrary directed edge-capacitated graphs, unlike most of the prior work on the ANF problem. The algorithm also works if a weighted throughput is considered, where the benefit gained by fully satisfying the demand for commodity i is determined by a given weight w_i>0. Second, a derandomization of the algorithm is presented that maintains the same approximation bounds, using novel pessimistic estimators for Bernstein's inequality. In addition, it is shown how the framework can be adapted to achieve a polylogarithmic fraction of the maximum throughput while maintaining a constant edge capacity violation, if the network capacity is large enough. Lastly, one important aspect of the randomized and derandomized algorithms is their simplicity, which lends to efficient implementations in practice. The implementations of both randomized rounding and derandomized algorithms for the ANF problem are presented and show their efficiency in practice.
ContributorsChaturvedi, Anya (Author) / Richa, Andréa W. (Thesis advisor) / Sen, Arunabha (Committee member) / Schmid, Stefan (Committee member) / Arizona State University (Publisher)
Created2020