waashk/dblp huggingface dataset:
bargaining and price-of-anarchy in repeated inter-session network coding games. most of the previous work on network coding has assumed that the users are not selfish and always follow the designed coding schemes. however, recent results have shown that selfish users do not have the incentive to participate in inter-session network coding in a static non-cooperative game setting. as a result, the worst-case network efficiency (i.e., the price-of-anarchy) can be as low as 22%. in this paper, we show that if the same game is played repeatedly, then the price-of-anarchy can be significantly improved to 48%. we propose a grim-trigger strategy that encourages users to cooperate and participate in the inter-session network coding. a key challenge is to determine a common cooperative coding rate that the users should mutually agree on. we propose to resolve the conflict of interest among the users through a bargaining process. we derive a tight upper bound for the price-of-anarchy which is valid for any bargaining scheme. moreover, we propose a simple and efficient min-max bargaining solution that can achieve this upper bound. our results represent one of the first steps towards designing practical inter-session network coding schemes that can achieve reasonable performance for selfish users.
improving qos in bittorrent-like vod systems. in recent years a number of research efforts have focused on effective use of p2p-based systems in providing large scale video streaming services. in particular, live streaming and video-on-demand (vod) systems have attracted much interest. while previous efforts mainly focused on the common challenges faced by both types of applications, there are still a number of fundamental open questions in designing p2p-based vod systems, which is the focus of our effort. specifically, in this paper, we consider a bittorrent-like vod system and focus on the following questions: (1) how the lack of load balance, which typically exists in a p2p-based vod system, affects the performance and what steps can be taken to remedy that, and (2) is a fcfs approach to serving requests at a peer sufficient or whether a deadline-aware scheduling (das) approach can lead to performance improvements. given the deadline considerations that exist in vod systems, we also investigate approaches to avoiding unnecessary queueing time. for each of these questions, we first illustrate deficiencies of current approaches in adequately meeting streaming quality of service requirements. motivated by this, we propose several practical schemes aimed at addressing these questions. to illustrate the benefits of our approach, we present an extensive simulation-based performance study.
deterministic broadcast on multiple access channels. we study broadcasting on multiple access channels by deterministic distributed protocols. data arrivals are governed by an adversary. the power of the adversary is constrained by the average rate of data injection and a bound on the number of different packets that can be injected in one round. the injection rate is at most 1, which forbids the adversary from overloading the channel. we consider a number of deterministic protocols. for each of them we give an upper bound on the worst-case packet latency, as a function of the constraints imposed on the adversary. we present results of experiments by simulations to compare packet latency of the deterministic protocols and of backoff-type randomized protocols. the experiments are carried out in a simulation environment that captures the burstiness of data injection and the resulting traffic by admissibility condition defined by the fraction of active stations and the rate of changing the status of active versus passive among the stations.
predicting prefix availability in the internet. the border gateway protocol (bgp) maintains inter-domain routing information by announcing and withdrawing ip prefixes, possibly resulting in temporary prefix unreachability. prefix availability observed from different vantage points in the internet can be lower than standards promised by service level agreements (slas). in this paper, we develop a framework for predicting long-term prefix availability, given short-duration prefix information from publicly available bgp routing databases. we compare three prediction models, and find that bagged decision trees perform the best when predicting for long future durations, whereas a simple model works well for short prediction durations. we show that mean time to failure and to recovery outperform past availability in terms of their importance for predicting availability for long durations. we also find that predictability is higher in the year 2009, compared to four years earlier. our models allow isps to adjust bgp routing policies if predicted availability is low, and the models are useful for cloud computing systems, p2p, and voip applications.
linear programming models for multi-channel p2p streaming systems. most of the commercial p2p video streaming deployments support hundreds of channels and are referred to as multichannel systems. measurement studies show that bandwidth resources of different channels are highly unbalanced and thus recent research studies have proposed various protocols to improve the streaming qualities for all channels by enabling cross-channel cooperation among multiple channels. however, there is no general framework for comparing existing and potential designs for multi-channel p2p systems. the goal of this paper is to establish tractable models for answering the fundamental question in multi-channel system designs: under what circumstances, should a particular design be used to achieve the desired streaming quality with the lowest implementation complexity? to achieve this goal, we first classify existing and potential designs into three categories, namely naive bandwidth allocation approach (nba), passive channel-aware bandwidth allocation approach (pca) and active channel-aware bandwidth allocation approach (aca). then, we define the bandwidth satisfaction ratio as a performance metric to develop linear programming models for the three designs. the proposed models are independent of implementations and can be efficiently solved due to the linear property, which provides a way of numerically exploring the design space of multi-channel systems and developing closedform solutions for special systems.
fuzzy keyword search over encrypted data in cloud computing. as cloud computing becomes prevalent, more and more sensitive information are being centralized into the cloud. for the protection of data privacy, sensitive data usually have to be encrypted before outsourcing, which makes effective data utilization a very challenging task. although traditional searchable encryption schemes allow a user to securely search over encrypted data through keywords and selectively retrieve files of interest, these techniques support only exact keyword search. that is, there is no tolerance of minor typos and format inconsistencies which, on the other hand, are typical user searching behavior and happen very frequently. this significant drawback makes existing techniques unsuitable in cloud computing as it greatly affects system usability, rendering user searching experiences very frustrating and system efficacy very low. in this paper, for the first time we formalize and solve the problem of effective fuzzy keyword search over encrypted cloud data while maintaining keyword privacy. fuzzy keyword search greatly enhances system usability by returning the matching files when users' searching inputs exactly match the predefined keywords or the closest possible matching files based on keyword similarity semantics, when exact match fails. in our solution, we exploit edit distance to quantify keywords similarity and develop an advanced technique on constructing fuzzy keyword sets, which greatly reduces the storage and representation overheads. through rigorous security analysis, we show that our proposed solution is secure and privacy-preserving, while correctly realizing the goal of fuzzy keyword search.
file fragmentation over an unreliable channel. it has been recently discovered that heavy-tailed file completion time can result from protocol interaction even when file sizes are light-tailed. a key to this phenomenon is the restart feature where if a file transfer is interrupted before it is completed, the transfer needs to restart from the beginning. in this paper, we show that independent or bounded fragmentation guarantees light-tailed file completion time as long as the file size is light-tailed, i.e., in this case, heavy-tailed file completion time can only originate from heavy-tailed file sizes. if the file size is heavy-tailed, then the file completion time is necessarily heavy-tailed. for this case, we show that when the file size distribution is regularly varying, then under independent or bounded fragmentation, the completion time tail distribution function is asymptotically upper bounded by that of the original file size stretched by a constant factor. we then prove that if the failure distribution has non-decreasing failure rate, the expected completion time is minimized by dividing the file into equal sized fragments; this optimal fragment size is unique but depends on the file size. we also present a simple blind fragmentation policy where the fragment sizes are constant and independent of the file size and prove that it is asymptotically optimal. finally, we bound the error in expected completion time due to error in modeling of the failure process.
link homophily in the application layer and its usage in traffic classification. we address the following questions. is there link homophily in the application layer traffic? if so, can it be used to accurately classify traffic in network trace data without relying on payloads or properties at the flow level? our research shows that the answers to both of these questions are affirmative in real network trace data. specifically, we define link homophily to be the tendency for flows with common ip hosts to have the same application (p2p, web, etc.) compared to randomly selected flows. the presence of link homophily in trace data provides us with statistical dependencies between flows that share common ip hosts. we utilize these dependencies to classify application layer traffic without relying on payloads or properties at the flow level. in particular, we introduce a new statistical relational learning algorithm, called neighboring link classifier with relaxation labeling (nlc+rl). our algorithm has no training phase and does not require features to be constructed. all that it needs to start the classification process is traffic information on a small portion of the initial flows, which we refer to as seeds. in all our traces, nlc+rl achieves above 90% accuracy with less than 5% seed size; it is robust to errors in the seeds and various seed-selection biases; and it is able to accurately classify challenging traffic such as p2p with over 90% precision and recall.
non-asymptotic delay bounds for networks with heavy-tailed traffic. traffic with self-similar and heavy-tailed characteristics has been widely reported in networks, yet, only few analytical results are available for predicting the delay performance of such networks. we address a particularly difficult type of heavy-tailed traffic where only the first moment can be computed, and present the first non-asymptotic end-to-end delay bounds for such traffic. the derived performance bounds are non-asymptotic in that they do not assume a steady state, large buffer, or many sources regime. our analysis considers a multihop path of fixed-capacity links with heavy-tailed self-similar cross traffic at each node. a key contribution of the analysis is a probabilistic sample-path bound for heavy-tailed arrival and service processes, which is based on a scale-free sampling method. we explore how delays scale as a function of the length of the path, and compare them with lower bounds. a comparison with simulations illustrates pitfalls when simulating self-similar heavytailed traffic, providing further evidence for the need of analytical bounds.
a privacy-preserving scheme for online social networks with efficient revocation. online social networks (osns) are attractive applications which enable a group of users to share data and stay connected. facebook, myspace, and twitter are among the most popular applications of osns where personal information is shared among group contacts. due to the private nature of the shared information, data privacy is an indispensable security requirement in osn applications. in this paper, we propose a privacy-preserving scheme for data sharing in osns, with efficient revocation for deterring a contact's access right to the private data once the contact is removed from the social group. in addition, the proposed scheme offers advanced features such as efficient search over encrypted data files and dynamic changes to group membership. with slight modification, we extend the application of the proposed scheme to anonymous online social networks of different security and functional requirements. the proposed scheme is demonstrated to be secure, effective, and efficient.
optimal waveband switching in optical ring networks. waveband switching saves port costs in optical crossconnects by grouping together a set of consecutive wavelengths and switching them as a single waveband. previous work has focused on either uniform band sizes or non-uniform band sizes considering a single node. in this paper, we show that such solutions are inadequate when considering the entire network, and present a novel framework for optimizing the number of wavebands in a ring network for deterministic traffic. we then consider a specific type of traffic, namely, all-to-all traffic and present bounds and heuristic solutions for the problem. our results show that the number of ports can be reduced by a large amount using waveband switching compared to wavelength switching. we also numerically evaluate the performance of our waveband design algorithms under dynamic stochastic traffic.
pattern mutation in wireless sensor deployment. in this paper, we study the optimal deployment pattern problem in wireless sensor networks (wsns). we propose a new set of patterns, particularly when sensors' communication range (rc) is relatively small compared with their sensing range (rs), and prove their optimality among regular patterns. in this study, we discover a surprising and interesting phenomenon-- pattern mutation. this phenomenon contradicts the conjecture presented in a previous work that there exists a universal elemental pattern among optimal pattern evolution and that pattern evolution is continuous. for example, we find mutation happens among the patterns for full-coverage and 3-connectivity when rc/rs = 1.0459, among the patterns for full-coverage and 4- connectivity when rc/rs = 1.3903, and among the patterns for full-coverage and 5-connectivity when rc/rs = 1.0406. to the best of our knowledge, this is the first time that mutation in pattern evolution has been discovered. also, our work further completes the exploration of optimal patterns in wsns.
on the aggregatability of router forwarding tables. the rapid growth of global routing tables has raised concerns among many internet service providers. the most immediate concern regarding routing scalability is the size of the forwarding information base (fib), which seems to be growing at a faster pace than router hardware can support. this paper focuses on one potential solution to this problem - fib aggregation, i.e., aggregating fib entries without affecting the forwarding paths taken by data traffic. compared with alternative solutions to the routing scalability problem, fib aggregation is particularly appealing because it is a purely local software optimization limited within a router, requiring no changes to routing protocols or router hardware. to understand the feasibility of using fib aggregation to extend router lifetime, we present several fib aggregation algorithms and evaluate their performance using routing tables and updates from tens of networks. we find that fib aggregation can reduce the fib table size by as much as 70% with small computational overhead. we also show that the computational overhead can be controlled through various mechanisms.
secure wireless communication with dynamic secrets. this paper introduces a set of low-complexity algorithms that when coupled with link layer retransmission mechanisms, strengthen wireless communication security. our basic idea is to generate a series of secrets from inevitable transmission errors and other random factors in wireless communications. because these secrets are constantly extracted from the communication process in realtime, we call them dynamic secrets. dynamic secrets have interesting security properties. they offer a complementary mechanism to existing security protocols. even if the adversary exploits a vulnerability and steals the underlying system secret, security can be automatically replenished. in many scenarios, it is also possible to bootstrap a secure communication with the dynamic secrets.
an opportunistic batch bundle authentication scheme for energy constrained dtns. bundle authentication is a critical security service in delay tolerant networks (dtns) that ensures authenticity and integrity of bundles during multi-hop transmissions. public key signatures, which have been suggested in existing bundle security protocol specification, achieve bundle authentication at the cost of an increased computational, transmission overhead and a higher energy consumption, which is not desirable for energy-constrained dtns. on the other hand, the unique "store-carry-and-forward" transmission characteristic of dtns implies that bundles from distinct/common senders can be buffered opportunistically at some common intermediate nodes. this "buffering" characteristic distinguishes dtn from any other traditional wireless networks, for which an intermediate cache is not supported. to exploit such a buffering characteristic, in this paper, we propose an opportunistic batch bundle authentication scheme (obba) to achieve efficient bundle authentication. the proposed scheme adopts batch verification techniques, allowing a computational overhead to be bounded by the number of opportunistic contacts instead of the number of messages. furthermore, we introduce a novel concept of a fragment authentication tree to minimize communication cost by choosing an optimal tree height. finally, we implement obba in a specific dtn scenario setting: pocket-switched networks on campus. the simulation results in terms of computation time, transmission overhead and power consumption are given to demonstrate the efficiency and effectiveness of the proposed schemes.
an auction framework for spectrum allocation with interference constraint in cognitive radio networks. extensive research in recent years has shown the benefits of cognitive radio technologies to improve the flexibility and efficiency of spectrum utilization. this new communication paradigm, however, requires a well-designed spectrum allocation mechanism. in this paper, we propose an auction framework for cognitive radio networks to allow unlicensed secondary users (sus) to share the available spectrum of licensed primary users (pus) fairly and efficiently, subject to the interference temperature constraint at each pu. to study the competition among sus, we formulate a non-cooperative multiple-pu multiple-su auction game and study the structure of the resulting equilibrium by solving a non-continuous two-dimensional optimization problem. a distributed algorithm is developed in which each su updates its strategy based on local information to converge to the equilibrium. we then extend the proposed auction framework to the more challenging scenario with free spectrum bands. we develop an algorithm based on the no-regret learning to reach a correlated equilibrium of the auction game. the proposed algorithm, which can be implemented distributedly based on local observation, is especially suited in decentralized adaptive learning environments as cognitive radio networks. finally, through numerical experiments, we demonstrate the effectiveness of the proposed auction framework in achieving high efficiency and fairness in spectrum allocation.
compactdfa: generic state machine compression for scalable pattern matching. pattern matching algorithms lie at the core of all contemporary intrusion detection systems (ids), making it intrinsic to reduce their speed and memory requirements. this paper focuses on the most popular class of pattern-matching algorithms, the aho-corasick-like algorithms, which are based on constructing and traversing a deterministic finite automaton (dfa), representing the patterns. while this approach ensures deterministic time guarantees, modern idss need to deal with hundreds of patterns, thus requiring to store very large dfas which usually do not fit in fast memory. this results in a major bottleneck on the throughput of the ids, as well as its power consumption and cost. we propose a novel method to compress dfas by observing that the name of the states is meaningless. while regular dfas store separately each transition between two states, we use this degree of freedom and encode states in such a way that all transitions to a specific state can be represented by a single prefix that defines a set of current states. our technique applies to a large class of automata, which can be categorized by simple properties. then, the problem of pattern matching is reduced to the well-studied problem of longest prefix matching (lpm) that can be solved either in tcam, in commercially available ip-lookup chips, or in software. specifically, we show that with a tcam our scheme can reach a throughput of 10 gbps with low power consumption.
resource allocation in multi-cell ofdma-based relay networks. cooperative relay networks combined with orthogonal frequency division multiplexing access (ofdma) technology has been widely recognized as a promising candidate for future cellular infrastructure due to the performance enhancement by flexible resource allocation schemes. the majority of the existing schemes aim to optimize single cell performance gain. however, the higher frequency reuse factor and smaller cell size requirement lead to severe inter-cell interference problem. therefore, the multi-cell resource allocation of subcarrier, time scheduling and power should be jointly considered to alleviate the severe inter-cell interference problem. in this paper, the joint resource allocation problem is formulated. considering the high complexity of the optimal solution, a two-stage resource allocation scheme is proposed. in the first stage, all of the users in each cell are selected sequentially and the joint subcarrier allocation and scheduling is conducted for the selected users without considering the interference. in the second stage, the optimal power control is performed by geometric programming method. simulation results show that the proposed the interference-aware resource allocation scheme improves the system capacity compared with existing schemes. especially, the edge users achieve more benefit.
counting rfid tags efficiently and anonymously. radio frequency identification (rfid) technology has attracted much attention due to its variety of applications, e.g., inventory control and object tracking. one important problem in rfid systems is how to quickly estimate the number of distinct tags without reading each tag individually. this problem plays a crucial role in many real-time monitoring and privacy-preserving applications. in this paper, we present an efficient and anonymous scheme for tag population estimation. this scheme leverages the position of the first reply from a group of tags in a frame. results from mathematical analysis and extensive simulation demonstrate that our scheme outperforms other protocols proposed in the previous work.