waashk/dblp huggingface dataset:
distributed resource allocation for synchronous fork and join processing networks. many emerging information processing applications require applying various fork and join type operations such as correlation, aggregation, and encoding/decoding to data streams in real-time. each operation will require one or more simultaneous input data streams and produce one or more output streams, where the processing may shrink or expand the data rates upon completion. multiple tasks can be co-located on the same server and compete for limited resources. effective in-network processing and resource management in a distributed heterogeneous environment is critical to achieving better scalability and provision of quality of service. in this paper, we study the distributed resource allocation problem for a synchronous fork and join processing network, with the goal of achieving the maximum total utility of output streams. using primal and dual based optimization techniques, we propose several decentralized iterative algorithms to solve the problem, and design protocols that implement these algorithms. these algorithms have different strengths in practical implementation and can be tailored to take full advantage of the computing capabilities of individual servers. we show that our algorithms guarantee optimality and demonstrate through simulation that they can adapt quickly to dynamically changing environments.
pricing and incentives in peer-to-peer networks. peer-to-peer (p2p) networks offer a cost effective and easily deployable framework for sharing user-generated content. however, intrinsic incentive problems reside in p2p networks as the transfer of content incurs costs both to uploaders and to downloaders while the benefit accrues only to downloaders. we investigate the issues of incentives in content production and sharing over p2p networks using a game theoretic model. peers do not share produced content at all at noncooperative equilibria whereas pareto efficiency requires peers to fully share produced content. there is also a divergence in the total amount of produced content between non-cooperative equilibria and pareto efficiency. by imposing full sharing, we decompose the inefficiency of non-cooperative equilibria into two parts, inefficiency due to no sharing and inefficiency due to underproduction. as a method to remedy the incentive problems in p2p networks, two classes of pricing schemes, mp pricing schemes and linear pricing schemes, are proposed. we show that the proposed pricing schemes can achieve pareto efficiency as non-cooperative equilibria. we also examine a linear pricing scheme that maximizes the revenue of the network manager.
max-contribution: on optimal resource allocation in delay tolerant networks. this is by far the first paper considering joint optimization of link scheduling, routing and replication for disruption-tolerant networks (dtns). the optimization problems for resource allocation in dtns are typically solved using dynamic programming which requires knowledge of future events such as meeting schedules and durations. this paper defines a new notion of optimality for dtns, called snapshot optimality where nodes are not clairvoyant, i.e., cannot look ahead into future events, and thus decisions are made using only contemporarily available knowledge. unfortunately, the optimal solution for snapshot optimality still requires solving an nphard problem of maximum weight independent set and a global knowledge of who currently owns a copy and what their delivery probabilities are. this paper presents a new efficient approximation algorithm, called distributed max-contribution (dmc) that performs greedy scheduling, routing and replication based only on locally and contemporarily available information. through a simulation study based on real gps traces tracking over 4000 taxies for about 30 days in a large city, dmc outperforms existing heuristically engineered resource allocation algorithms for dtns.
mis: malicious nodes identification scheme in network-coding-based peer-to-peer streaming. network coding has been shown to be capable of greatly improving quality of service in p2p live streaming systems (e.g., iptv). however, network coding is vulnerable to pollution attacks where malicious nodes inject into the network bogus data blocks that are combined with other legitimate blocks at downstream nodes, leading to incapability of decoding the original blocks and substantial degradation of network performance. in this paper, we propose a novel approach to limiting pollution attacks by rapidly identifying malicious nodes. our scheme can fully satisfy the requirements of live streaming systems, and achieves much higher efficiency than previous schemes. each node in our scheme only needs to perform several hash computations for an incoming block, incurring very small computational latency. the space overhead added to each block is only 20 bytes. the verification information given to each node is independent of the streaming content and thus does not need to be redistributed. the simulation results based on real pplive channel overlays show that the process of identifying malicious nodes only takes a few seconds even in the presence of a large number of malicious nodes.
phishnet: predictive blacklisting to detect phishing attacks. phishing has been easy and effective way for trickery and deception on the internet. while solutions such as url blacklisting have been effective to some degree, their reliance on exact match with the blacklisted entries makes it easy for attackers to evade. we start with the observation that attackers often employ simple modifications (e.g., changing top level domain) to urls. our system, phishnet, exploits this observation using two components. in the first component, we propose five heuristics to enumerate simple combinations of known phishing sites to discover new phishing urls. the second component consists of an approximate matching algorithm that dissects a url into multiple components that are matched individually against entries in the blacklist. in our evaluation with real-time blacklist feeds, we discovered around 18,000 new phishing urls from a set of 6,000 new blacklist entries. we also show that our approximate matching algorithm leads to very few false positives (3%) and negatives (5%).
on the age of pseudonyms in mobile ad hoc networks. in many envisioned mobile ad hoc networks, nodes are expected to periodically beacon to advertise their presence. in this way, they can receive messages addressed to them or participate in routing operations. yet, these beacons leak information about the nodes and thus hamper their privacy. a classic remedy consists in each node making use of (certified) pseudonyms and changing its pseudonym in specific locations called mix zones. of course, privacy is then higher if the pseudonyms are short-lived (i.e., nodes have a short distance to confusion), but pseudonyms can be costly, as they are usually obtained from an external authority. in this paper, we provide a detailed analytical evaluation of the age of pseudonyms based on differential equations. we corroborate this model by a set of simulations. this paper thus provides a detailed quantitative framework for selecting the parameters of a pseudonym-based privacy system in peer-to-peer wireless networks.
diversity-rate trade-off in erasure networks. this paper addresses a fundamental trade-off between rate and the diversity gain of an end-to-end connection in an erasure network. the erasure network is modeled by a directed graph whose links are orthogonal erasure channels. furthermore, the erasure network is assumed to be nonergodic, meaning that the erasure status of the links are assumed to be fixed during each block of transmission and change independently from block to block. the erasure status of the links is assumed to be known only by the destination node. first, we study the homogeneous erasure networks in which the links have the same erasure probability and capacity. we derive the optimum trade-off between diversity gain and the end-to-end rate and prove that a variant of the conventional routing strategy combined with an appropriate forward error correction at the end-nodes achieves the optimum diversity-rate trade-off. next, we consider the general erasure networks in which different links may have different values of erasure probability and capacity. we prove that there exist general erasure networks for which any conventional routing strategy fails to achieve the optimum diversity-rate trade-off. however, for any general erasure graph, we show that there exists a linear network coding strategy which achieves the optimum diversity-rate trade-off. unlike the previous works which suggest the potential benefit of linear network coding in the error-free multicast scenario (in terms of the achievable rate), our result introduces the benefit of linear network coding in the erasure single-source singledestination scenario (in terms of the diversity gain). finally, we study the diversity-rate trade-off through simulations. the erasure graphs are constructed according to the barabasi-albert random model which is known to capture the scale-free property of the practical packet switched networks like the internet. the error probability is depicted for different network strategies and different rate values. the depicted results confirm the trade-off between the rate and the diversity gain for each network strategy. moreover, the diversity gain is plotted versus the rate for different conventional routing and the linear network coding strategies. it is observed that linear network coding outperforms all conventional routing strategies in terms of the diversity gain.
scalable modulation for scalable wireless videocast. in conventional wireless systems with layered architectures, the physical layer treats all data streams from upper layers equally and apply the same modulation and coding schemes. newer systems such as digital video broadcast start to introduce hierarchical modulation schemes with superposition coding (spc) and support data streams of different priorities. however, spc requires specialized hardware and has high complexity beyond most existing handheld devices. we thus propose scalable modulation (s-mod) by reusing the current mainstream modulation schemes with software-based bit-remapping. in this paper, we study how to optimize the configuration of the physical layer s-mod and coding schemes to maximize the utility of videocast with scalable video coding (svc). simulation results demonstrate significant performance gains using s-mod and the cross-layer optimization, indicating s-mod and svc is a good combination for wireless video multicast and unicast.
twister networks and their applications to load-balanced switches. inspired by the recent development of optical queueing theory, in this paper we study a class of multistage interconnection networks (mins), called twister networks. unlike the usual recursive constructions of mins (either by two-stage expansion or by three-stage expansion), twister networks are constructed directly by a concatenation of bipartite networks. moreover, the biadjacency matrices of these bipartite networks are sums of subsets of the powers of the circular shift matrix. though mins have been studied extensively in the literature, we show there are several distinct properties for twister networks, including routability and conditionally nonblocking properties. in particular, we show that a twister network satisfying (a1) in the paper is routable, and packets can be self-routed through the twister network by using the c-transform developed in optical queueing theory. moreover, we define an n-modulo distance and use it to show that a twister network satisfying (a2) in the paper is conditionally nonblocking if the n-modulo distance between any two outputs is not greater than two times of the n-modulo distance between the corresponding two inputs. such a conditionally nonblocking property allows us to show that a twister network with n inputs/outputs can be used as a p × p rotator and a p × p symmetric tdm switch for any 2 ≤ p ≤ n. as such, one can use a twister network as the switch fabric for a two-stage load balanced switch that is capable of providing incremental update of the number of linecards.
an interaction-based mobility model for dynamic hot spot analysis. in this paper, we analyze phenomena related to user clumps and hot spots occuring in mobile networks at the occasion of large urban mass gatherings. our analysis is based on observations made on mobility traces of gsm users in several large cities. classical mobility models, such as the random waypoint, do not allow one to represent the observed dynamics of clumps in a proper manner. this motivates the introduction and the mathematical analysis of a new interaction-based mobility model, which is the main contribution of the present paper. this model is shown to allow one to describe the dynamics of clumps and in particular to predict key phenomena such as the building of hot spots and the scattering between hot spots, which play a key role in the engineering of wireless networks. we show how to obtain the main parameters of this model from simple communication activity measurements and we illustrate this calibration process on real cases.
routing and scheduling for energy and delay minimization in the powerdown model. energy conservation is drawing increasing attention in data networking. one school of thought believes that a dominant amount of energy saving comes from turning off network elements. the difficulty is that transitioning between the active and sleeping modes consumes considerable energy and time. this results in an obvious trade-off between saving energy and provisioning performance guarantees such as end-toend delays. we study the following routing and scheduling problem in a network in which each network element either operates in the full-rate active mode or the zero-rate sleeping mode. for a given network and traffic matrix, routing determines the path along which each traffic stream traverses. for frame-based periodic scheduling, a schedule determines the active period per element within each frame and prioritizes packets within each active period. for a line topology, we present a schedule with close-tominimum delay for a minimum active period per element. for an arbitrary topology, we partition the network into a collection of lines and utilize the near-optimal schedule along each line. additional delay is incurred only when a path switches from one line to another. by minimizing the number of switchings via routing, we show a logarithmic approximation for both energy consumption and end-to-end delays. if routing is given as input, we present two schedules one of which has active period proportional to the traffic load per network element, and the other proportional to the maximum load over all elements. the end-to-end delay of the latter is much improved compared to the delay for the former. this demonstrates the trade-off between energy and delay.
privacy-preserving public auditing for data storage security in cloud computing. cloud computing is the long dreamed vision of computing as a utility, where users can remotely store their data into the cloud so as to enjoy the on-demand high quality applications and services from a shared pool of configurable computing resources. by data outsourcing, users can be relieved from the burden of local data storage and maintenance. however, the fact that users no longer have physical possession of the possibly large size of outsourced data makes the data integrity protection in cloud computing a very challenging and potentially formidable task, especially for users with constrained computing resources and capabilities. thus, enabling public auditability for cloud data storage security is of critical importance so that users can resort to an external audit party to check the integrity of outsourced data when needed. to securely introduce an effective third party auditor (tpa), the following two fundamental requirements have to be met: 1) tpa should be able to efficiently audit the cloud data storage without demanding the local copy of data, and introduce no additional on-line burden to the cloud user; 2) the third party auditing process should bring in no new vulnerabilities towards user data privacy. in this paper, we utilize and uniquely combine the public key based homomorphic authenticator with random masking to achieve the privacy-preserving public cloud data auditing system, which meets all above requirements. to support efficient handling of multiple auditing tasks, we further explore the technique of bilinear aggregate signature to extend our main result into a multi-user setting, where tpa can perform multiple auditing tasks simultaneously. extensive security and performance analysis shows the proposed schemes are provably secure and highly efficient.
safeguarding data delivery by decoupling path propagation and adoption. false routing announcements are a serious security problem, which can lead to widespread service disruptions in the internet. a number of detection systems have been proposed and implemented recently, however, it takes time to detect attacks, notify operators, and stop false announcements. thus detection systems should be complemented by a mitigation scheme that can protect data delivery before the attack is resolved. we propose such a mitigation scheme, qbgp, which decouples the propagation of a path and the adoption of a path for data forwarding. qbgp does not use suspicious paths to forward data traffic, but still propagates them in the routing system to facilitate attack detection. it can protect data delivery from routing announcements of false sub-prefixes, false origins, false nodes and false links. qbgp incurs overhead only when there are suspicious paths, which happen infrequently in real bgp traces. results from large scale simulations and bgp trace analysis show that qbgp is light-weight yet effective, and it converges faster and incurs less overhead than pretty good bgp.
delay tolerant event collection in sensor networks with mobile sink. we are interested in event collection in a 2d region where sensors are deployed to detect and collect interested events. using traditional multi-hop routing in wireless sensor networks to report events to a sink node or base station, will result in severe imbalanced energy consumption of static sensors. in addition, full connectivity among all the static sensors may not be possible in some cases since generally the sensors are randomly deployed in the target region. in this paper, we exploit a mobile sensor as the sink node to assist the event collection by controlling the movement of the mobile sink to collect static sensor readings. a key observation of our work is that an event has spatial-temporal correlation. specifically, the same event can be detected by multiple nearby sensors within a period of time. thus, it is more energy-efficient if the mobile sink can selectively communicate with only a portion of static sensors, while still collecting all the interested events. in this paper, we discuss the event collection problem by leveraging the mobility of the sink node and the spatial-temporal correlation of the event, in favor of maximizing the network lifetime with a guaranteed event collection rate. we first model the problem as sensor selection problem and show that it could be solved in polynomial time, if global knowledge of events is available and there is no velocity constraints on mobile sink. we also analyze the design of a feasible movement route for mobile sink to minimize the velocity requirements for a practical system. an online scheme is then proposed to relax the assumption about global knowledge of events and we prove that the expected event collection rate can be guaranteed in theory. through comprehensive simulation on real trace data, we demonstrate that the network lifetime can be significantly extended, comparing to some other schemes.
low-complexity scheduling algorithms for multi-channel downlink wireless networks. this paper considers the problem of designing scheduling algorithms for multi-channel (e.g., ofdm) wireless downlink networks with n users/ofdm sub-channels. for this system, while the classical maxweight algorithm is known to be throughput-optimal, its buffer-overflow performance is very poor (formally, we show it has zero rate function in our setting). to address this, we propose a class of algorithms called ihlqf (iterated heaviest matching with longest queues first) that is shown to be throughput optimal for a general class of arrival/channel processes, and also rate-function optimal (i.e., exponentially small buffer overflow probability) for certain arrival/channel processes. ihlqf however has higher complexity than maxweight (n4 vs. n2 respectively). to overcome this issue, we propose a new algorithm called ssg (server-side greedy). we show that ssg is throughput optimal, results in a much better per-user buffer overflow performance than the maxweight algorithm (positive rate function for certain arrival/channel processes), and has a computational complexity (n2) that is comparable to the maxweight algorithm. thus, it provides a nice trade-off between buffer-overflow performance and computational complexity. these results are validated by both analysis and simulations.
a formal study of trust-based routing in wireless ad hoc networks. recently, trust-based routing has received much attention as an effective way to improve security of wireless ad hoc networks (wanets). although various trust metrics have been designed and incorporated into the routing metrics, as far as we know, none of the existing works have used mathematical tools such as routing algebra to analyze the compatibility of trust related routing metrics and routing protocols in wanets. in this paper, we first identify unique features of trust metrics compared with qos-based routing metrics. then, we provide a systematic analysis of the relationship between trust metrics and trust-based routing protocols by identifying the basic algebraic properties that a trust metric must have in order to work correctly and optimally with different generalized distance-vector or link-state routing protocols in wanets. moreover, we extend our framework to model the interactions between different trustbased routing protocols. finally, our results are applied to check the compatibility of the trust metrics proposed in previous literature and the popular routing protocols used in wanets.
channel-based unidirectional stream protocol (cusp). this paper presents a novel transport protocol, cusp, specifically designed with complex and dynamic network applications in mind. peer-to-peer applications benefit in particular, as their requirements are met by neither udp nor tcp. while other modern transports like sctp or sst have also tried to combine the advantages of tcp and udp, cusp overcomes their technical and conceptual shortcomings. cusp makes it possible to directly express application logic in the message flow. modern applications need a mixture of request-response, request-multiple-response, publish-subscribe, and message-passing. all of these operations can be conveniently implemented using cusp's unidirectional streams. we separate low-level packet management from streams into reusable channels. a channel connects two applications providing negotiation, congestion control, and cryptography. developers operate on the stream level, sending messages as reliable and ordered byte-streams. although they may share a common channel, a stall or loss in one stream does not block the others.