Priority-Based Data Transmission in Wireless Networks using Network Coding
Genre
Thesis/DissertationDate
2015Author
Ostovari, PouyaAdvisor
Wu, JieCommittee member
Ji, BoSrinivasan, Avinash
Bai, Li
Department
Computer and Information ScienceSubject
Computer ScienceNetwork Coding
Performance Evaluation
Triangular Network Coding
Unequal Data Protection
Wireless Networks
Permanent link to this record
http://hdl.handle.net/20.500.12613/3369Metadata
Show full item recordDOI
http://dx.doi.org/10.34944/dspace/3351Abstract
With the rapid development of mobile devices technology, they are becoming very popular and a part of our everyday lives. These devices, which are equipped with wireless radios, such as cellular and WiFi radios, affect almost every aspect of our lives. People use smartphone and tablets to access the Internet, watch videos, chat with their friends, and etc. The wireless connections that these devices provide is more convenient than the wired connections. However, there are two main challenges in wireless networks: error-prone wireless links and network resources limitation. Network coding is widely used to provide reliable data transmission and to use the network resources efficiently. Network coding is a technique in which the original packets are mixed together using algebraic operations. In this dissertation, we study the applications of network coding in making the wireless transmissions robust against transmission errors and in efficient resource management. In many types of data, the importance of different parts of the data are different. For instance, in the case of numeric data, the importance of the data decreases from the most significant to the least significant bit. Also, in multi-layer videos, the importance of the packets in different layers of the videos are not the same. We propose novel data transmission methods in wireless networks that considers the unequal importance of the different parts of the data. In order to provide robust data transmissions and use the limited resources efficiently, we use random linear network coding technique, which is a type of network coding. In the first part of this dissertation, we study the application of network coding in resource management. In order to use the the limited storage of cache nodes efficiently, we propose to use triangular network coding for content distribution. We also design a scalable video-on-demand system, which uses helper nodes and network coding to provide users with their desired video quality. In the second part, we investigate the application of network coding in providing robust wireless transmissions. We propose symbol-level network coding, in which each packet is partitioned to symbols with different importance. We also propose a method that uses network coding to make multi-layer videos robust against transmission errors.ADA compliance
For Americans with Disabilities Act (ADA) accommodation, including help with reading this content, please contact scholarshare@temple.eduCollections
Related items
Showing items related by title, author, creator and subject.
-
Latency Tradeoffs in Distributed Storage AccessThe performance of storage systems is central to handling the huge amount of data being generated from a variety of sources including scientific experiments, social media, crowdsourcing, and from an increasing variety of cyber-physical systems. The emerging high-speed storage technologies enable the ingestion of and access to such large volumes of data efficiently. However, the combination of high data volume requirements of new applications that largely generate unstructured and semistructured streams of data combined with the emerging high-speed storage technologies pose a number of new challenges, including the low latency handling of such data and ensuring that the network providing access to the data does not become the bottleneck. The traditional relational model is not well suited for efficiently storing and retrieving unstructured and semi-structured data. An alternate mechanism, popularly known as Key-Value Store (KVS) has been investigated over the last decade to handle such data. A KVS store only needs a 'key' to uniquely identify the data record, which may be of variable length and may or may not have further structure in the form of predefined fields. Most of the KVS in existence have been designed for hard-disk based storage (before the SSDs gain popularity) where avoiding random accesses is crucial for good performance. Unfortunately, as the modern solid-state drives become the norm as the data center storage, the HDD-based KV structures result in high read, write, and space amplifications which becomes detrimental to both the SSD’s performance and endurance. Also note that regardless of how the storage systems are deployed, access to large amounts of storage by many nodes must necessarily go over the network. At the same time, the emerging storage technologies such as Flash, 3D-crosspoint, phase change memory (PCM), etc. coupled with highly efficient access protocols such as NVMe are capable of ingesting and reading data at rates that challenge even the leading edge networking technologies such as 100Gb/sec Ethernet. At the same time, some of the higher-end storage technologies (e.g., Intel Optane storage based on 3-D crosspoint technology, PCM, etc.) coupled with lean protocols like NVMe are capable of providing storage access latencies in the 10-20$\mu s$ range, which means that the additional latency due to network congestion could become significant. The purpose of this thesis is to addresses some of the aforementioned issues. We propose a new hash-based and SSD-friendly key-value store (KVS) architecture called FlashKey which is especially designed for SSDs to provide low access latencies, low read and write amplification, and the ability to easily trade-off latencies for any sequential access, for example, range queries. Through detailed experimental evaluation of FlashKey against the two most popular KVs, namely, RocksDB and LevelDB, we demonstrate that even as an initial implementation we are able to achieve substantially better write amplification, average, and tail latency at a similar or better space amplification. Next, we try to deal with network congestion by dynamically replicating the data items that are heavily used. The tradeoff here is between the latency and the replication or migration overhead. It is important to reverse the replication or migration as the congestion fades away since our observation tells that placing data and applications (that access the data) together in a consolidated fashion would significantly reduce the propagation delay and increase the network energy-saving opportunities which is required as the data center network nowadays are equipped with high-speed and power-hungry network infrastructures. Finally, we designed a tradeoff between network consolidation and congestion. Here, we have traded off the latency to save power. During the quiet hours, we consolidate the traffic is fewer links and use different sleep modes for the unused links to save powers. However, as the traffic increases, we reactively start to spread out traffic to avoid congestion due to the upcoming traffic surge. There are numerous studies in the area of network energy management that uses similar approaches, however, most of them do energy management at a coarser time granularity (e.g. 24 hours or beyond). As opposed to that, our mechanism tries to steal all the small to medium time gaps in traffic and invoke network energy management without causing a significant increase in latency.
-
Log Linear Models for Prediction and Analysis of NetworksThe heightened research activity in the interdisciplinary field of network science can be attributed to the emergence of the social network computer applications. Researchers understood early on that data describing how entities interconnect is highly valuable and that it offers a deeper understanding about the entities themselves. This is why there were so many studies done about various kinds of networks in the last 10-15 years. The study of the networks from the perspective of computer science usually has two objectives. The first objective is to develop statistical mechanisms capable of accurately describing and modeling observed real-world networks. A good fit of such mechanism suggests the correctness of the model's assumptions and leads to better understanding of the network. A second goal is more practical, a well performing model can be used to predict what will happen to the network in the future. Also, such model can be leveraged to use the information gleaned from network to predict what will happen to the networks entities. One important leitmotif of network research and analysis is wide adaptation of log linear models. In this work we apply this philosophy for study and evaluation of log-linear statistical models in various types of networks. We begin with proposal of the new Temporal Exponential Random Graph Model (tERGM) for the analysis and predictions in the binary temporal social networks. We then extended the model for applications in partially observed networks that change over time. Lastly, we generalize the tERGM model to predict the real-valued weighted links in the temporal non-social networks. The log-linear models are not limited to networks that change over time but can also be applied to networks that are static. One such static network is a social network composed of patients undergoing hemodialysis. Hemodialysis is prescribed to people suffering from the end stage renal disease; the treatment necessitates the attendance, on non-changing schedule, of the hemodialysis clinic for a prolonged time period and this is how the social ties are formed. The new log-linear Social Latent Vectors (SLV) model was applied to study such static social networks. The results obtained from SLV experiments suggest that social relationships formed by patients bear influence on individual patients clinical outcome. The study demonstrates how social network analysis can be applied to better understand the network constituents.
-
SOCIAL NETWORK ARCHITECTURES AND APPLICATIONSRather than being randomly wired together, the components of complex network systems are recently reported to represent a scale-free architecture, in which the node degree distribution follows power-law. While social networks are scale-free, it is natural to utilize their structural properties in some social network applications. As a result, this dissertation explores social network architectures, and in turn, leverages these architectures to facilitate some influence and information propagation applications. Social network architectures are analyzed in two different aspects. The first aspect focuses on the node degree snowballing effects (i.e., degree growth effects) in social networks, which is based on an age-sensitive preferential attachment model. The impact of the initial links is explored, in terms of accelerating the node degree snowballing effects. The second aspect focuses on Nested Scale-Free Architectures (NSFAs) for social networks. The scale-free architecture is a classic concept, which means that the node degree distribution follows the power-law distribution. `Nested' indicates that the scale-free architecture is preserved when low-degree nodes and their associated connections are iteratively removed. NSFA has a bounded hierarchy. Based on the social network structure, this dissertation explores two influence propagation applications for the Social Influence Maximization Problem (SIMP). The first application is a friend recommendation strategy with the perspective of social influence maximization. For the system provider, the objective is to recommend a fixed number of new friends to a given user, such that the given user can maximize his/her social influence through making new friends. This problem is proved to be NP-hard by reduction from the SIMP. A greedy friend recommendation algorithm with an approximation ratio of $1-e^{-1}$ is proposed. The second application studies the SIMP with the crowd influence, which is NP-hard, monotone, non-submodular, and inapproximable in general graphs. However, since user connections in Online Social Networks (OSNs) are not random, approximations can be obtained by leveraging the structural properties of OSNs. The modularity, denoted by $\Delta$, is proposed to measure to what degree this problem violates the submodularity. Two approximation algorithms are proposed with ratios of $\frac{1}{\Delta+2}$ and $1-e^{-1/(\Delta+1)}$, respectively. Beside the influence propagation applications, this dissertation further explores three different information propagation applications. The first application is a social network quarantine strategy, which can eliminate epidemic outbreaks with minimal isolation costs. This problem is NP-hard. An approximation algorithm with a ratio of 2 is proposed through utilizing the problem properties of feasibility and minimality. The second application is a rating prediction scheme, called DynFluid, based on the fluid dynamics. DynFluid analogizes the rating reference among the users in OSNs to the fluid flow among containers. The third application is an information cascade prediction framework: given the social current cascade and social topology, the number of propagated users at a future time slot is predicted. To reduce prediction time complexities, the spatiotemporal cascade information (a larger size of data) is decomposed to user characteristics (a smaller size of data) for subsequent predictions. All these three applications are based on the social network structure.
