waashk/dblp huggingface dataset:
uusee: large-scale operational on-demand streaming with random network coding. since the inception of network coding in information theory, we have witnessed a sharp increase of research interest in its applications in communications and networking, where the focus has been on more practical aspects. however, thus far, network coding has not been deployed in real-world commercial systems in operation at a large scale, and in a production setting. in this paper, we present the objectives, rationale, and design in the first production deployment of random network coding, where it has been used in the past year as the cornerstone of a large-scale production on-demand streaming system, operated by uusee inc., delivering thousands of on-demand video channels to millions of unique visitors each month. to achieve a thorough understanding of the performance of network coding, we have collected 200 gigabytes worth of real-world traces throughout the 17-day summer olympic games in august 2008, and present our lessons learned after an in-depth trace-driven analysis.
a framework for joint network coding and transmission rate control in wireless networks. network coding has been proposed as a technique that can potentially increase the transport capacity of a wireless network via processing and mixing of data packets at intermediate routers. however, most previous studies either assume a fixed transmission rate or do not consider the impact of using diverse rates on the network coding gain. since in many cases, network coding implicitly relies on overhearing, the choice of the transmission rate has a big impact on the achievable gains. the use of higher rates works in favor of increasing the native throughput; however, it may in many cases work against effective overhearing. in other words, there is a tension between the achievable network coding gain and the inherent rate gain possible on a link. in this paper1, our goal is to drive the network towards achieving the best trade-off between these two contradictory effects. towards this, we design a distributed framework that (a) facilitates the choice of the best rate on each link while considering the need for overhearing and (b) dictates the choice of which decoding recipient will acknowledge the reception of an encoded packet. we demonstrate that both of these features contribute significantly towards gains in throughput. we extensively simulate our framework in a variety of topological settings. we also fully implement it on real hardware and demonstrate its applicability and performance gains via proof-of-concept experiments on our wireless testbed. we show that our framework yields throughput gains of up to 390% as compared to what is achieved in a rate-unaware network coding framework.
distributed coordination with deaf neighbors: efficient medium access for 60 ghz mesh networks. multi-gigabit outdoor mesh networks operating in the unlicensed 60 ghz "millimeter (mm) wave" band, offer the possibility of a quickly deployable broadband extension of the internet. we consider mesh nodes with electronically steerable antenna arrays, with both the transmitter and receiver synthesizing narrow beams that compensate for the higher path loss at mm-wave frequencies, achieving ranges on the order of 100 meters using the relatively low transmit powers attainable with low-cost silicon implementations. such highly directional networking differs from wifi networks at lower carrier frequencies in two ways that have a crucial impact on protocol design: (1) directionality drastically reduces spatial interference, so that pseudowired link abstractions form an excellent basis for protocol design; (2) directionality induces deafness, which makes medium access control (mac) based on carrier sensing infeasible. interference analysis in our prior work shows that, in such a setting, coordination between transmitters and receivers, rather than interference management, becomes the key mac performance bottleneck. however, the question of whether such coordination can be achieved in a distributed fashion while achieving high medium utilization, was left open. in this paper, we answer this question in the affirmative, presenting a distributed mac protocol that employs memory to achieve approximate time division multiplexed (tdm) schedules without explicit coordination or resource allocation. the efficacy of the protocol is demonstrated via packet level simulations, while a markov chain fixed-point analysis provides insight into the effect of parameter choices.
improving the scalability of data center networks with traffic-aware virtual machine placement. the scalability of modern data centers has become a practical concern and has attracted significant attention in recent years. in contrast to existing solutions that require changes in the network architecture and the routing protocols, this paper proposes using traffic-aware virtual machine (vm) placement to improve the network scalability. by optimizing the placement of vms on host machines, traffic patterns among vms can be better aligned with the communication distance between them, e.g. vms with large mutual bandwidth usage are assigned to host machines in close proximity. we formulate the vm placement as an optimization problem and prove its hardness. we design a two-tier approximate algorithm that efficiently solves the vm placement problem for very large problem sizes. given the significant difference in the traffic patterns seen in current data centers and the structural differences of the recently proposed data center architectures, we further conduct a comparative analysis on the impact of the traffic patterns and the network architectures on the potential performance gain of traffic-aware vm placement. we use traffic traces collected from production data centers to evaluate our proposed vm placement algorithm, and we show a significant performance improvement compared to existing generic methods that do not take advantage of traffic patterns and data center network characteristics.
throughput analysis of multiple access relay channel under collision model. despite much research on the throughput of relaying networks under idealized interference models, many practical wireless networks rely on physical-layer protocols that preclude the concurrent reception of multiple transmissions. in this work, we develop analytical frameworks for the uplink of a multisource single-channel relay-aided wireless system where transmissions are scheduled to avoid collisions. we study amplify-and-forward and decode-and-forward strategies, in both time-sharing and network-coded variants, and provide mathematical models to investigate their achievable rate regions. both general and optimal power allocations are considered. we also find the cut-set outer bounds for the rate regions. moreover, we present a comparison between these methods with the simple time sharing scheme. our numerical results reveal that optimizing power allocation favors the time sharing scheme significantly more than it does the relaying schemes, so that time sharing under some circumstances can provide higher maximum sum rates, even if the links to the relay have strong channel gains. the proposed analysis provides a means to quantitatively evaluate the efficacy of relaying under the collision model, leading to pragmatic design guidelines.
tree-structured data regeneration in distributed storage systems with regenerating codes. distributed storage systems provide large-scale reliable data storage by storing a certain degree of redundancy in a decentralized fashion on a group of storage nodes. to recover from data losses due to the instability of these nodes, whenever a node leaves the system, additional redundancy should be regenerated to compensate such losses. in this context, the general objective is to minimize the volume of actual network traffic caused by such regenerations. a class of codes, called regenerating codes, has been proposed to achieve an optimal trade-off curve between the amount of storage space required for storing redundancy and the network traffic during the regeneration. in this paper, we jointly consider the choices of regenerating codes and network topologies. we propose a new design, referred to as rctree, that combines the advantage of regenerating codes with a tree-structured regeneration topology. our focus is the efficient utilization of network links, in addition to the reduction of the regeneration traffic. with the extensive analysis and quantitative evaluations, we show that rctree is able to achieve a both fast and stable regeneration, even with departures of storage nodes during the regeneration.
random walks on digraphs: a theoretical framework for estimating transmission costs in wireless routing. in this paper we develop a unified theoretical framework for estimating various transmission costs of packet forwarding in wireless networks. our framework can be applied to the three routing paradigms-best path routing, opportunistic routing, and stateless routing-to which nearly all existing routing protocols belong.we illustrate how packet forwarding under each paradigm can be modeled as random walks on directed graphs (digraphs). by generalizing the theory of random walks that has primarily been developed for undirected graphs to digraphs, we show how various transmission costs can be formulated in terms of hitting times and hitting costs of random walks on digraphs. as representative examples, we apply the theory to three specific routing protocols, one under each paradigm. extensive simulations demonstrate that the proposed digraph based analytical model can achieve more accurate transmission cost estimation over existing methods.
a bit-stuffing algorithm for crosstalk avoidance in high speed switching. motivated by the design of high speed switching fabrics, in this paper we propose a bit-stuffing algorithm for generating forbidden transition codes to mitigate the crosstalk effect between adjacent wires in long on-chip buses. we first model a bus with forbidden transition constraints as a forbidden transition channel, and derive the shannon capacity of such a channel. then we perform a worst case analysis and a probabilistic analysis for the bit-stuffing algorithm. we show by both theoretic analysis and simulations that the coding rate of the bit stuffing encoding scheme for independent and identically distributed (i.i.d.) bernoulli input traffic is quite close to the shannon capacity, and hence is much better than those of the existing forbidden transition codes in the literature, including the fibonacci representation.
enhancing wireless tcp: a serialized-timer approach. in wireless networks, tcp performs unsatisfactorily since packet reordering and random losses may be falsely interpreted as congestive losses. this causes tcp to trigger fast retransmission and fast recovery spuriously, leading to under-utilization of available network resources. in this paper, we propose a novel tcp variant, known as tcp for noncongestive loss (tcp-ncl), to adapt tcp to wireless networks by using more reliable signals of packet loss and network overload for activating packet retransmission and congestion response, separately. tcp-ncl can thus serve as a unified solution for effective congestion control, sequencing control, and loss recovery. different from the existing unified solutions, the modifications involved in the proposed variant are limited to sender-side tcp only, thereby facilitating possible future wide deployment. the two signals employed are the expirations of two serialized timers. a smart tcp sender model has been developed for optimizing the timer expiration periods. our simulation studies reveal that tcp-ncl is robust against packet reordering as well as random packet loss while maintaining responsiveness against situations with purely congestive loss.
achieving secure, scalable, and fine-grained data access control in cloud computing. cloud computing is an emerging computing paradigm in which resources of the computing infrastructure are provided as services over the internet. as promising as it is, this paradigm also brings forth many new challenges for data security and access control when users outsource sensitive data for sharing on cloud servers, which are not within the same trusted domain as data owners. to keep sensitive user data confidential against untrusted servers, existing solutions usually apply cryptographic methods by disclosing data decryption keys only to authorized users. however, in doing so, these solutions inevitably introduce a heavy computation overhead on the data owner for key distribution and data management when fine-grained data access control is desired, and thus do not scale well. the problem of simultaneously achieving fine-grainedness, scalability, and data confidentiality of access control actually still remains unresolved. this paper addresses this challenging open issue by, on one hand, defining and enforcing access policies based on data attributes, and, on the other hand, allowing the data owner to delegate most of the computation tasks involved in fine-grained data access control to untrusted cloud servers without disclosing the underlying data contents. we achieve this goal by exploiting and uniquely combining techniques of attribute-based encryption (abe), proxy re-encryption, and lazy re-encryption. our proposed scheme also has salient properties of user access privilege confidentiality and user secret key accountability. extensive analysis shows that our proposed scheme is highly efficient and provably secure under existing security models.
netscope: practical network loss tomography. we present netscope, a tomographic technique that infers the loss rates of network links from unicast endto-end measurements. netscope uses a novel combination of first- and second-order moments of end-to-end measurements to identify and characterize the links that cannot be (accurately) characterized through existing practical tomographic techniques. using both analytical and experimental tools, we show that netscope enables scalable, accurate link-loss inference: in a simulation scenario involving 4000 links, 20% of them lossy, netscope correctly identifies 94% of the lossy links with a false positive rate of 16%--a significant improvement over the existing alternatives. netscope is robust in the sense that it requires no parameter tuning, moreover its advantage over the alternatives widens when the number of lossy links increases. we also validate netscope's performance on an "internet tomographer" that we deployed on an overlay of 400 planetlab nodes.
csma-based distributed scheduling in multi-hop mimo networks under sinr model. we study the problem of distributed scheduling in multi-hop mimo networks. we first develop a "mimo-pipe" model that provides the upper layers a set of rates and sinr requirements, which capture the rate-reliability tradeoff in mimo communications. the main thrust of this study is then dedicated to developing csma-based mimo-pipe scheduling under the sinr model. we choose the sinr model over the extensively studied matching or protocol-based interference models because it more naturally captures the impact of interference in wireless networks. the coupling among the links caused by the interference makes the problem of devising distributed scheduling algorithms particularly challenging. to that end, we explore csma-based mimo-pipe scheduling, from two perspectives. first, we consider an idealized continuous time csma network. we propose a dual-band approach in which control messages are exchanged instantaneously over a channel separate from the data channel, and show that csma-based scheduling can achieve throughput optimality under the sinr model. next, we consider a discrete time csma network. to tackle the challenge due to the coupling caused by interference, we propose a "conservative" scheduling algorithm in which more stringent sinr constraints are imposed based on the mimo-pipe model. we show that this suboptimal distributed scheduling can achieve an efficiency ratio bounded from below.
flashtrie: hash-based prefix-compressed trie for ip route lookup beyond 100gbps. it is becoming apparent that the next generation ip route lookup architecture needs to achieve speeds of 100- gbps and beyond while supporting both ipv4 and ipv6 with fast real-time updates to accommodate ever-growing routing tables. some of the proposed multibit-trie based schemes, such as tree bitmap [1], have been used in today's high-end routers. however, their large data structure often requires multiple external memory accesses for each route lookup. a pipelining technique is widely used to achieve high-speed lookup with a cost of using many external memory chips. pipelining also often leads to poor memory load-balancing. in this paper, we propose a new ip route lookup architecture called flashtrie that overcomes the shortcomings of the multibit-trie based approach. we use a hash-based membership query to limit off-chip memory accesses per lookup to one and to balance memory utilization among the memory modules. we also develop a new data structure called prefix-compressed trie that reduces the size of a bitmap by more than 80%. our simulation and implementation results show that flashtrie can achieve 160-gbps worst-case throughput while simultaneously supporting 2-m prefixes for ipv4 and 279-k prefixes for ipv6 using one fpga chip and four ddr3 sdram chips. flashtrie also supports incremental real-time updates.
multi-channel assignment in wireless sensor networks: a game theoretic approach. in this paper, we formulate multi-channel assignment in wireless sensor networks (wsns) as an optimization problem and show it is np-hard. we then propose a distributed game based channel assignment algorithm (gbca) to solve the problem. gbca takes into account both the network topology information and transmission routing information. we prove that there exists at least one nash equilibrium in the channel assignment game. furthermore, we analyze the sub-optimality of nash equilibrium and the convergence of the best response in the game. simulation results are given to demonstrate that gbca can reduce interference significantly and achieve satisfactory network performance in terms of delivery ratio, throughput, channel access delay and energy consumption.
improved multi-criteria spanners for ad-hoc networks under energy and distance metrics. this paper studies the problem of topology control in random wireless ad-hoc networks through power assignment for n nodes uniformly distributed in a unit square. in particular, we are interested in asymmetric power assignments so that the induced communication graph has a good distance and energy stretch simultaneously, with additional optimization objectives: both minimizing the total energy consumption, interference level, hop-diameter, and maximizing the network lifetime. we present several power assignments with varying construction time complexity. the probability of our results converges to one as the number of network nodes, n, increases. to the best of our knowledge, these are the first results for spanner construction in wireless ad-hoc networks with provable bounds for both, energy and distance, metrics simultaneously.
sybil attacks against mobile users: friends and foes to the rescue. collaborative applications for co-located mobile users can be severely disrupted by a sybil attack to the point of being unusable. existing decentralized defences have largely been designed for peer-to-peer networks but not for mobile networks. that is why we propose a new decentralized defence for portable devices and call it mobid. the idea is that a device manages two small networks in which it stores information about the devices it meets: its network of friends contains honest devices, and its network of foes contains suspicious devices. by reasoning on these two networks, the device is then able to determine whether an unknown individual is carrying out a sybil attack or not. we evaluate the extent to which mobid reduces the number of interactions with sybil attackers and consequently enables collaborative applications.we do so using real mobility and social network data. we also assess computational and communication costs of mobid on mobile phones.
distributed caching algorithms for content distribution networks. the delivery of video content is expected to gain huge momentum, fueled by the popularity of user-generated clips, growth of vod libraries, and wide-spread deployment of iptv services with features such as catchup/pauselive tv and npvr capabilities. the 'time-shifted' nature of these personalized applications defies the broadcast paradigm underlying conventional tv networks, and increases the overall bandwidth demands by orders of magnitude. caching strategies provide an effective mechanism for mitigating these massive bandwidth requirements by replicating the most popular content closer to the network edge, rather than storing it in a central site. the reduction in the traffic load lessens the required transport capacity and capital expense, and alleviates performance bottlenecks. in the present paper, we develop light-weight cooperative cache management algorithms aimed at maximizing the traffic volume served from cache and minimizing the bandwidth cost. as a canonical scenario, we focus on a cluster of distributed caches, either connected directly or via a parent node, and formulate the content placement problem as a linear program in order to benchmark the globally optimal performance. under certain symmetry assumptions, the optimal solution of the linear program is shown to have a rather simple structure. besides interesting in its own right, the optimal structure offers valuable guidance for the design of low-complexity cache management and replacement algorithms. we establish that the performance of the proposed algorithms is guaranteed to be within a constant factor from the globally optimal performance, with far more benign worstcase ratios than in prior work, even in asymmetric scenarios. numerical experiments for typical popularity distributions reveal that the actual performance is far better than the worst-case conditions indicate.
on constructing efficient shared decision trees for multiple packet filters. multiple packet filters serving different purposes (e.g., firewalling, qos) and different virtual routers are often deployed on a single physical router. the hypercuts decision tree is one efficient data structure for performing packet filter matching in software. constructing a separate hypercuts decision tree for each packet filter is not memory efficient. a natural alternative is to construct shared hypercuts decision trees to more efficiently support multiple packet filters. however, we experimentally show that naively classifying packet filters into shared hypercuts decision trees may significantly increase the memory consumption and the height of the trees. to help decide which subset of packet filters should share a hypercuts decision tree, we first identify a number of important factors that collectively impact the efficiency of the resulted shared hypercuts decision tree. based on the identified factors, we then propose to use machine learning techniques to predict whether any pair of packet filters should share a tree. given the pair-wise prediction matrix, a greedy heuristic algorithm is used to classify packets filters into a number of shared hypercuts decision trees. our experiments using both real packets filters and synthetic packet filters show that the shared hypercuts decision trees consume considerably less memory.