Matching Items (25)
Filtering by
- All Subjects: Algorithms
- All Subjects: Creative Project
- Creators: School of Mathematical and Statistical Sciences
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
In the realm of network science, many topics can be abstracted as graph problems, such as routing, connectivity enhancement, resource/frequency allocation and so on. Though most of them are NP-hard to solve, heuristics as well as approximation algorithms are proposed to achieve reasonably good results. Accordingly, this dissertation studies graph related problems encountered in real applications. Two problems studied in this dissertation are derived from wireless network, two more problems studied are under scenarios of FIWI and optical network, one more problem is in Radio- Frequency Identification (RFID) domain and the last problem is inspired by satellite deployment.
The objective of most of relay nodes placement problems, is to place the fewest number of relay nodes in the deployment area so that the network, formed by the sensors and the relay nodes, is connected. Under the fixed budget scenario, the expense involved in procuring the minimum number of relay nodes to make the network connected, may exceed the budget. In this dissertation, we study a family of problems whose goal is to design a network with “maximal connectedness” or “minimal disconnectedness”, subject to a fixed budget constraint. Apart from “connectivity”, we also study relay node problem in which degree constraint is considered. The balance of reducing the degree of the network while maximizing communication forms the basis of our d-degree minimum arrangement(d-MA) problem. In this dissertation, we look at several approaches to solving the generalized d-MA problem where we embed a graph onto a subgraph of a given degree.
In recent years, considerable research has been conducted on optical and FIWI networks. Utilizing a recently proposed concept “candidate trees” in optical network, this dissertation studies counting problem on complete graphs. Closed form expressions are given for certain cases and a polynomial counting algorithm for general cases is also presented. Routing plays a major role in FiWi networks. Accordingly to a novel path length metric which emphasizes on “heaviest edge”, this dissertation proposes a polynomial algorithm on single path computation. NP-completeness proof as well as approximation algorithm are presented for multi-path routing.
Radio-frequency identification (RFID) technology is extensively used at present for identification and tracking of a multitude of objects. In many configurations, simultaneous activation of two readers may cause a “reader collision” when tags are present in the intersection of the sensing ranges of both readers. This dissertation ad- dresses slotted time access for Readers and tries to provide a collision-free scheduling scheme while minimizing total reading time.
Finally, this dissertation studies a monitoring problem on the surface of the earth for significant environmental, social/political and extreme events using satellites as sensors. It is assumed that the impact of a significant event spills into neighboring regions and there will be corresponding indicators. Careful deployment of sensors, utilizing “Identifying Codes”, can ensure that even though the number of deployed sensors is fewer than the number of regions, it may be possible to uniquely identify the region where the event has taken place.
The objective of most of relay nodes placement problems, is to place the fewest number of relay nodes in the deployment area so that the network, formed by the sensors and the relay nodes, is connected. Under the fixed budget scenario, the expense involved in procuring the minimum number of relay nodes to make the network connected, may exceed the budget. In this dissertation, we study a family of problems whose goal is to design a network with “maximal connectedness” or “minimal disconnectedness”, subject to a fixed budget constraint. Apart from “connectivity”, we also study relay node problem in which degree constraint is considered. The balance of reducing the degree of the network while maximizing communication forms the basis of our d-degree minimum arrangement(d-MA) problem. In this dissertation, we look at several approaches to solving the generalized d-MA problem where we embed a graph onto a subgraph of a given degree.
In recent years, considerable research has been conducted on optical and FIWI networks. Utilizing a recently proposed concept “candidate trees” in optical network, this dissertation studies counting problem on complete graphs. Closed form expressions are given for certain cases and a polynomial counting algorithm for general cases is also presented. Routing plays a major role in FiWi networks. Accordingly to a novel path length metric which emphasizes on “heaviest edge”, this dissertation proposes a polynomial algorithm on single path computation. NP-completeness proof as well as approximation algorithm are presented for multi-path routing.
Radio-frequency identification (RFID) technology is extensively used at present for identification and tracking of a multitude of objects. In many configurations, simultaneous activation of two readers may cause a “reader collision” when tags are present in the intersection of the sensing ranges of both readers. This dissertation ad- dresses slotted time access for Readers and tries to provide a collision-free scheduling scheme while minimizing total reading time.
Finally, this dissertation studies a monitoring problem on the surface of the earth for significant environmental, social/political and extreme events using satellites as sensors. It is assumed that the impact of a significant event spills into neighboring regions and there will be corresponding indicators. Careful deployment of sensors, utilizing “Identifying Codes”, can ensure that even though the number of deployed sensors is fewer than the number of regions, it may be possible to uniquely identify the region where the event has taken place.
ContributorsZhou, Chenyang (Author) / Richa, Andrea (Thesis advisor) / Sen, Arunabha (Thesis advisor) / Xue, Guoliang (Committee member) / Walkowiak, Krzysztof (Committee member) / Arizona State University (Publisher)
Created2019
Description
We created an Android application, Impromp2, which allows users to search for and save events of interest to them in the Phoenix area. The backend, built on the Parse platform, gathers events daily using Web services and stores them in a database. Impromp2 was designed to improve upon similarly-purposed apps available for Android devices in several key ways, especially in user interface design and data interaction capability. This is a full-stack software project that explores databases and their performance considerations, Web services, user interface design, and the challenges of app development for a mobile platform.
ContributorsNorth, Joseph Robert (Author) / Balasooriya, Janaka (Thesis director) / Nakamura, Mutsumi (Committee member) / Faucon, Philippe (Committee member) / Barrett, The Honors College (Contributor) / Computer Science and Engineering Program (Contributor) / School of Mathematical and Statistical Sciences (Contributor)
Created2015-05
Description
"The Legal Adventures of Frankie and Rosie" is a creative project that explores the nontraditional format of comics to express creative nonfiction. The project is a set of 30 independent comics that focuses on two primary college-going students who are based off of the authors. The characters, Frankie and Rosie narrate their stories through dialogue. The authors use this narrative model to archive their college experience at ASU. Representing creative nonfiction through comics yields an amalgamated format that can be challenging for both the writers to produce as well as for the readers to consume. Ultimately, the project serves as an attempt to test whether or not the comic medium can stand by itself as an appropriate format to express creative nonfictional narratives without becoming a diluted combination of its purer predecessors.
ContributorsBennewitz, Dana (Co-author) / Ray, Payel (Co-author) / Martin, Thomas (Thesis director) / Scott Lynch, Jacquelyn (Committee member) / Civil, Environmental and Sustainable Engineering Programs (Contributor) / Barrett, The Honors College (Contributor) / School of Geographical Sciences and Urban Planning (Contributor) / Electrical Engineering Program (Contributor) / School of Social Transformation (Contributor) / School of Mathematical and Statistical Sciences (Contributor)
Created2015-05
Description
Covering subsequences with sets of permutations arises in many applications, including event-sequence testing. Given a set of subsequences to cover, one is often interested in knowing the fewest number of permutations required to cover each subsequence, and in finding an explicit construction of such a set of permutations that has size close to or equal to the minimum possible. The construction of such permutation coverings has proven to be computationally difficult. While many examples for permutations of small length have been found, and strong asymptotic behavior is known, there are few explicit constructions for permutations of intermediate lengths. Most of these are generated from scratch using greedy algorithms. We explore a different approach here. Starting with a set of permutations with the desired coverage properties, we compute local changes to individual permutations that retain the total coverage of the set. By choosing these local changes so as to make one permutation less "essential" in maintaining the coverage of the set, our method attempts to make a permutation completely non-essential, so it can be removed without sacrificing total coverage. We develop a post-optimization method to do this and present results on sequence covering arrays and other types of permutation covering problems demonstrating that it is surprisingly effective.
ContributorsMurray, Patrick Charles (Author) / Colbourn, Charles (Thesis director) / Czygrinow, Andrzej (Committee member) / Barrett, The Honors College (Contributor) / School of Mathematical and Statistical Sciences (Contributor) / Department of Physics (Contributor)
Created2014-12
Description
Rainbow Connection is an integrated choir with members on and off the autism spectrum. It was founded in the spring of 2012 by Barrett students Ali Friedman, Megan Howell, and Victoria Gilman as part of an honors thesis creative project. Rainbow Connection uses the rehearsal process and other creative endeavors to foster natural relationship building across social gaps. A process-oriented choir, Rainbow Connection's main goals concern the connections made throughout the experience rather than the final musical product. The authors believe that individual, non-hierarchical relationships are the keys to breaking down systemized gaps between identity groups and that music is an ideal facilitator for fostering such relationships. Rainbow Connection operates under the premise that, like colors in a rainbow, choir members create something beautiful not by melding into one homogenous group, but by collaboratively showcasing their individual gifts. This paper will highlight the basic premise and structure of Rainbow Connection, outline the process of enacting the choir, and describe the authors' personal reactions and takeaways from the project.
ContributorsFriedman, Alexandra (Co-author) / Gilman, Victoria (Co-author) / Howell, Megan (Co-author) / Rio, Robin (Thesis director) / Schildkret, David (Committee member) / Barrett, The Honors College (Contributor) / School of Music (Contributor) / School of Mathematical and Statistical Sciences (Contributor)
Created2014-12
Description
The title means nothing because the stories have little in common, aside from the fact that I wrote them. The common theme of anxiety was unintentional, though it is prevalent in the stories, poetry and my life. Each story is written from a different style, with a different interest in mind. The poetry that breaks up the stories is mine, and also free of common bonds. People whom I love inspired some of them; others stem from people with whom I was (or still am) angry. Some of them are just me trying to write poetry like other successful poets, who seem to know something I don't. I wrote this set of stories and poems because I wanted to see if I could do it. I wanted to challenge myself in a new medium (two new mediums really, if you separate literature and poetry). I wanted to prove to myself that I could do it, if I really set my mind to it. I wanted to have some wealth of words, which I could record myself reading. Overall, I hope that you enjoy these stories and words. I wrote them to entertain myself, and they seem to do that pretty well. If you don't like them, stop reading. If you do like them, keep reading and tell everyone you know about this collection. I'm proud of my work here, so anything beyond that is icing on my cake.
ContributorsRagatz, Zachariah Edward (Author) / Scott, Jason Davids (Thesis director) / Espinosa, Micha (Committee member) / Barrett, The Honors College (Contributor) / School of Mathematical and Statistical Sciences (Contributor) / School of Film, Dance and Theatre (Contributor)
Created2015-05
Description
Since the acceptance of Einstein's special theory of relativity by the scientific community, authors of science fiction have used the concept of time dilation to permit seemingly impossible feats. Simple spacecraft acceleration schemes involving time dilation have been considered by scientists and fiction writers alike. Using an original Java program based upon the differential equations for special relativistic kinematics, several scenarios for round trip excursions at relativistic speeds are calculated and compared, with particular attention to energy budget and relativistic time passage in all relevant frames.
ContributorsAlfson, Jonathan William (Author) / Jacob, Richard (Thesis director) / Covatto, Carl (Committee member) / Foy, Joseph (Committee member) / Barrett, The Honors College (Contributor) / School of Mathematical and Statistical Sciences (Contributor) / Department of Physics (Contributor)
Created2015-05
Description
This creative project centers on creating evaluative writing about film, in the form of a film review blog. Preliminary writing was done, in which the distinction was made between critical film writing and movie reviewing, as well as an analysis of how film critics have honed in their criticism and what makes their content effective for their audience. The rest of the writing for this project consists of a total of 15 reviews for 15 different movies released in 2017 and 2018. In these reviews, there is a brief introduction of the plot and context in which the film is made, followed by an evaluative analysis of what made the film effective or ineffective in achieving its artistic goals. The reviews involve an amalgamation of the content and topics taught in the Film and Media Studies program at Arizona State University, from screenwriting to cinematography. This process of writing reviews and being edited by the Director and Second Reader allows for the opportunity to find a unique writing voice and create content that is accessible for the wide audience that would be reading the work. All of the writing completed for this project (except for the "My Favorite Film Critics" piece) is compiled together in a WordPress blog, in an easily readable and accessible format. The blog itself serves as a way to reach the desired audience, as well as entice them to engage with the writing and the films being written about. This includes providing images and trailers for each respective film, to add a visual component to the writing. The final product is a unique way to engage with the content taught in the Film and Media Studies program, while simultaneously building a portfolio of writing that will be expanded upon and continued in the future.
ContributorsPolich, Brennan Taylor (Author) / Green, Michael (Thesis director) / Bernstein, Gregory (Committee member) / Department of English (Contributor) / School of Mathematical and Statistical Sciences (Contributor) / Barrett, The Honors College (Contributor)
Created2018-05
Description
In many systems, it is difficult or impossible to measure the phase of a signal. Direct recovery from magnitude is an ill-posed problem. Nevertheless, with a sufficiently large set of magnitude measurements, it is often possible to reconstruct the original signal using algorithms that implicitly impose regularization conditions on this ill-posed problem. Two such algorithms were examined: alternating projections, utilizing iterative Fourier transforms with manipulations performed in each domain on every iteration, and phase lifting, converting the problem to that of trace minimization, allowing for the use of convex optimization algorithms to perform the signal recovery. These recovery algorithms were compared on a basis of robustness as a function of signal-to-noise ratio. A second problem examined was that of unimodular polyphase radar waveform design. Under a finite signal energy constraint, the maximal energy return of a scene operator is obtained by transmitting the eigenvector of the scene Gramian associated with the largest eigenvalue. It is shown that if instead the problem is considered under a power constraint, a unimodular signal can be constructed starting from such an eigenvector that will have a greater return.
ContributorsJones, Scott Robert (Author) / Cochran, Douglas (Thesis director) / Diaz, Rodolfo (Committee member) / Barrett, The Honors College (Contributor) / Electrical Engineering Program (Contributor) / School of Mathematical and Statistical Sciences (Contributor)
Created2014-05