waashk/dblp huggingface dataset:
multicast scaling laws with hierarchical cooperation. a new class of scheduling policies for multicast traffic are proposed in this paper. by utilizing hierarchical cooperative mimo transmission, our new policies can obtain an aggregate throughput of ω(n/k)1-ε) for any ε gt; 0. this achieves a gain of nearly√n/k compared with non-cooperative scheme in [19]. between the two cooperative strategies in our paper, the converge-based one is superior to the other on delay, while the throughput and energy consumption performances are nearly the same. moreover, to schedule the traffic in a converge multicast manner instead of the simple multicast, we can dramatically reduce the delay by a factor nearly (n/k)h/2, where h gt; 1 is the number of the hierarchical layers. our optimal cooperative strategy achieves an approximate delay-throughput tradeoff d(n, k)/t (n, k) = θ(k) when h ∞. this tradeoff ratio is identical to that of non-cooperative scheme, while the throughput performance is greatly improved. besides, for certain k and h, the tradeoff ratio is even better than that of unicast.
chorus: collision resolution for efficient wireless broadcast. traditional wireless broadcast protocols rely heavily on the 802.11-based csma/ca model, which avoids interference and collision by conservatively scheduling transmissions. while csma/ca is amenable to multiple concurrent unicasts, it tends to degrade broadcast performance, especially when there are a large number of nodes and links are lossy. in this paper, we propose a new, drastically different protocol called chorus that improves the efficiency and scalability of broadcast service with a mac layer that allows packet collisions. chorus is built upon the observation that packets carrying the same data can be effectively detected and decoded, even when they overlap in time and have comparable signal strength. it performs collision resolution using symbol-level iterative decoding, and then combines the resolved symbols to reconstruct the packet. this collision-tolerant mechanism significantly improves the transmission diversity and spatial reuse in wireless broadcast, providing an asymptotic broadcast delay that is proportional to the network radius. this advantage is exploited further by chorus's mac-layer cognitive sensing and scheduling scheme. we evaluate chorus with symbol-level simulation, and validate its network-level performance via ns-2, in comparison with a typical csma/ca broadcast protocol.
malicious hubs: detecting abnormally malicious autonomous systems. while many attacks are distributed across botnets, investigators and network operators have recently targeted malicious networks through high profile autonomous system (as) de-peerings and network shut-downs. in this paper, we explore whether some ases indeed are safe havens for malicious activity. we look for isps and ases that exhibit disproportionately high malicious behavior using 12 popular blacklists. we find that some ases have over 80% of their routable ip address space blacklisted and others account for large fractions of blacklisted ips. overall, we conclude that examining malicious activity at the as granularity can unearth networks with lax security or those that harbor cybercrime.
a general algorithm for interference alignment and cancellation in wireless networks. physical layer techniques have come a long way and can achieve close to shannon capacity for single point to-point transmissions. it is apparent that, to further improve network capacity significantly, we have to resort to concurrent transmissions. multiple concurrent transmission techniques (e.g., zero forcing, interference alignment and distributed mimo) are proposed in which multiple senders jointly encode signals to multiple receivers so that interference is aligned or canceled and each receiver is able to decode its desired information. in this paper, we formulate the interference alignment and cancellation problem in multi-hop mesh networks. we show that the problem is np-hard in general. we then propose a convex programming based algorithm to identify interference alignment and cancellation opportunities. our algorithm effectively utilizes knowledge of both local network topology and overheard packets at the sender side as well as the receiver side. we implement our system using gnu radio to evaluate key practical implementation issues.
minimizing the worst-case playback delay in vod services over passive optical networks. minimizing the worst-case playback delay (wpd) in vod services is both critical and challenging. given a fixed amount of bandwidth for broadcasting and patching, there is no prior work on determining the minimum wpd, let alone guaranteeing it. in this work, we propose novel schemes that leverage the unique properties of a tdm-based passive optical network (pon) by performing rebroadcasting and patching at its optical network unit (onus). for a given bandwidth available for vod services in the pon, we derive the minimum worst-case playback delay (wpd), and also design optimal patch scheduling algorithm as well as onu rebroadcast and patching channel assignment to guarantee such minimum wpd. numerical results confirm the superiority of the proposed schemes over the existing ones in terms of both worst-case and average performance.
haste: practical online network coding in a multicast switch. the use of network coding has been shown to improve throughput in input-queued multicast switches, but not without costs of computational complexity and delays. in this paper, we investigate the design of efficient online network coding algorithms in a switch with multicast traffic. we present haste, an online opportunistic coding algorithm designed to streamline the computation when network coding is involved in a network switch with multicast traffic. haste enjoys the advantage of incurring no decoding delays, which reduces packet delays compared with existing network coding algorithms on switches. we have conducted extensive simulations to show the efficiency of haste, and implemented an emulation framework to emulate input-queued switches using asynchronous network sockets. our emulation framework is able to process actual udp traffic using haste with online network coding, and to show convincing evidence that haste is suitable for practical use, and is beneficial in multicast switches.
the capacity of ad hoc networks with heterogeneous traffic using cooperation. we study the scaling laws for wireless ad hoc networks in which the distribution of n nodes in the network is homogeneous but the traffic they carry is heterogeneous. more specifically, we consider the case in which a given node is the data-gathering sink for k sources sending different information to it, while the rest of the s = n-k nodes participate in unicast sessions with random destinations chosen uniformly. we present a separation theorem for heterogeneous traffic showing that the optimum order throughput capacity can be attained in a wireless network in which traffic classes are distributed uniformly by endowing each node with multiple radios, each operating in a separate orthogonal channel, and by allocating a radio per node to each traffic class. based on this theorem, we show how this order capacity can be attained for the unicast and data-gathering traffic classes by extending cooperative communication schemes that have been proposed previously.
mobicent: a credit-based incentive system for disruption tolerant network. when disruption tolerant network (dtn) is used in commercial environments, incentive mechanism should be employed to encourage cooperation among selfish mobile users. key challenges in the design of an incentive scheme for dtn are that disconnections among nodes are the norm rather than exception and network topology is time varying. thus, it is difficult to detect selfish actions that can be launched by mobile users or to pre-determine the routing path to be used. in this paper, we propose mobicent, a credit-based incentive system for dtn. while mobicent allows the underlying routing protocol to discover the most efficient paths, it is also incentive compatible. therefore, using mobicent, rational nodes will not purposely waste transfer opportunity or cheat by creating non-existing contacts to increase their rewards. mobicent also provides different payment mechanisms to cater to client that wants to minimize either payment or data delivery delay.
q-csma: queue-length based csma/ca algorithms for achieving maximum throughput and low delay in wireless networks. recently, it has been shown that csma-type random access algorithms can achieve the maximum possible throughput in ad hoc wireless networks. however, these algorithms assume an idealized continuous-time csma protocol where collisions can never occur. in addition, simulation results indicate that the delay performance of these algorithms can be quite bad. on the other hand, although some simple heuristics (such as distributed approximations of greedy maximal scheduling) can yield much better delay performance for a large set of arrival rates, they may only achieve a fraction of the capacity region in general. in this paper, we propose a discrete-time version of the csma algorithm. central to our results is a discrete-time distributed randomized algorithm which is based on a generalization of the so-called glauber dynamics from statistical physics, where multiple links are allowed to update their states in a single time slot. the algorithm generates collision-free transmission schedules while explicitly taking collisions into account during the control phase of the protocol, thus relaxing the perfect csma assumption. more importantly, the algorithm allows us to incorporate delay-reduction mechanisms which lead to very good delay performance while retaining the throughput-optimality property.
tracking quantiles of network data streams with dynamic operations. quantiles are very useful in characterizing the data distribution of an evolving dataset in the process of data mining or network monitoring. the method of stochastic approximation (sa) tracks quantiles online by incrementally deriving and updating local approximations of the underly distribution function at the quantiles of interest. in this paper, we propose a generalization of the sa method for quantile estimation that allows not only data insertions, but also dynamic data operations such as deletions and updates.
mobile real-time group communication service. a scalable framework for mobile real-time group communication services is developed in this paper. examples for possible applications of this framework are mobile social networks, mobile conference calls, mobile instant messaging services, and mobile multi-player on-line games. a key requirement for enabling a real-time group communication service is the tight constraint imposed on the call delivery delay. since establishing such communication service for a group of independent mobile users under a tight delay constraint is np-hard, a two-tier architecture is proposed, that can meet the delay constraint imposed by the real-time service requirement for many independent mobile clients in a scalable manner. the time and memory complexity associated with the group services provided by the proposed framework are o(n) for each service, where n is the number of nodes being served, while a distributed scheme requires o(n2) for both time and memory complexity.
safeq: secure and efficient query processing in sensor networks. the architecture of two-tiered sensor networks, where storage nodes serve as an intermediate tier between sensors and a sink for storing data and processing queries, has been widely adopted because of the benefits of power and storage saving for sensors as well as the efficiency of query processing. however, the importance of storage nodes also makes them attractive to attackers. in this paper, we propose safeq, a protocol that prevents attackers from gaining information from both sensor collected data and sink issued queries. safeq also allows a sink to detect compromised storage nodes when they misbehave. to preserve privacy, safeq uses a novel technique to encode both data and queries such that a storage node can correctly process encoded queries over encoded data without knowing their values. to preserve integrity, we propose a new data structure called neighborhood chains that allows a sink to verify whether the result of a query contains exactly the data items that satisfy the query. in addition, we propose a solution to adapt safeq for event-driven sensor networks.
measurouting: a framework for routing assisted traffic monitoring. monitoring transit traffic at one or more points in a network is of interest to network operators for reasons of traffic accounting, debugging or troubleshooting, forensics, and traffic engineering. previous research in the area has focused on deriving a placement of monitors across the network towards the end of maximizing the monitoring utility of the network operator for a given traffic routing. however, both traffic characteristics and measurement objectives can dynamically change over time, rendering a previously optimal placement of monitors suboptimal. it is not feasible to dynamically redeploy/reconfigure measurement infrastructure to cater to such evolving measurement requirements. we address this problem by strategically routing traffic sub-populations over fixed monitors. we refer to this approach as measurouting. the main challenge for measurouting is to work within the constraints of existing intra-domain traffic engineering operations that are geared for efficiently utilizing bandwidth resources, or meeting quality of service (qos) constraints, or both. a fundamental feature of intra-domain routing, that makes measurouting feasible, is that intra-domain routing is often specified for aggregate flows. measurouting, can therefore, differentially route components of an aggregate flow while ensuring that the aggregate placement is compliant to original traffic engineering objectives. in this paper we present a theoretical framework for measurouting. furthermore, as proofs-of-concept, we present synthetic and practical monitoring applications to showcase the utility enhancement achieved with measurouting.
fair scheduling in cellular systems in the presence of noncooperative mobiles. we consider the problem of centrally controlled 'fair' scheduling of resources to one of the many mobile stations connected to a base station (bs). the bs is the only entity making decisions in this framework based on truthful information from the mobiles on their radio channel. we study the well-known family of parametric a-fair scheduling problems from a game-theoretic perspective in which some of the mobiles may be noncooperative. we first show that if the bs is unaware of the noncooperative behavior from the mobiles, the noncooperative mobiles become successful in snatching the resources from the other cooperative mobiles, resulting in unfair allocations. if the bs is aware of the noncooperative mobiles, a new game arises with bs as an additional player. it can then do better by neglecting the signals from the noncooperative mobiles. the bs, however, becomes successful in eliciting the truthful signals from the mobiles only when it uses additional information (signal statistics). this new policy along with the truthful signals from mobiles forms a nash equilibrium (ne) called a truth revealing equilibrium. finally, we propose new iterative algorithms to implement fair scheduling policies that robustify the otherwise non-robust (in presence of noncooperation) a-fair scheduling algorithms.
optimal activation and transmission control in delay tolerant networks. much research has been devoted to maximize the life time of mobile ad-hoc networks. life time has often been defined as the time elapsed until the first node is out of battery power. in the context of static networks, this could lead to disconnectivity. in contrast, delay tolerant networks (dtns) leverage the mobility of relay nodes to compensate for lack of permanent connectivity, and thus enable communication even after some nodes deplete their stored energy. one can thus consider the lifetimes of nodes as some additional parameters that can be controlled to optimize the performance of a dtn. in this paper, we consider two ways in which the energy state of a mobile can be controlled. both listening and transmission require energy, besides each of these has a different type of effect on the network performance. therefore we consider a joint optimization problem consisting of: i) activation, which determines when a mobile will turn on in order to receive packets, and ii) transmission control, which regulates the beaconing. the optimal solutions are shown to be of the threshold type. the findings are validated through extensive simulations.
incorporating random linear network coding for peer-to-peer network diagnosis. recent studies show that network coding improves multicast session throughput. in this paper, we demonstrate how random linear network coding can be incorporated to provide network diagnosis for peer-to-peer systems. we present a new trace collection protocol that allows operators to diagnose peer-topeer networks. it is essential to monitor large-scale peer-to-peer applications by collecting measurements referred to as snapshots from the peers. however, existing solutions are not scalable and fail to collect measurements from peers that departed before the time of collection. we use progressive random linear network coding to disseminate the snapshots in the network, from which the server pulls data in a delayed fashion. we leverage the power of progressive encoding to increase block diversity and tolerate extreme block losses by introducing redundancy in the network. peers cooperate by allocating cache capacity for other peers. snapshots of departed peers can thus be retrieved from the network. we show how our protocol controls the redundancy introduced through progressive encoding and thus scales to large number of peers and tolerates high level of peer dynamics.
walking in facebook: a case study of unbiased sampling of osns. with more than 250 million active users [1], facebook (fb) is currently one of the most important online social networks. our goal in this paper is to obtain a representative (unbiased) sample of facebook users by crawling its social graph. in this quest, we consider and implement several candidate techniques. two approaches that are found to perform well are the metropolis-hasting random walk (mhrw) and a reweighted random walk (rwrw). both have pros and cons, which we demonstrate through a comparison to each other as well as to the "ground-truth" (uni - obtained through true uniform sampling of fb userids). in contrast, the traditional breadth-first-search (bfs) and random walk (rw) perform quite poorly, producing substantially biased results. in addition to offline performance assessment, we introduce online formal convergence diagnostics to assess sample quality during the data collection process. we show how these can be used to effectively determine when a random walk sample is of adequate size and quality for subsequent use (i.e., when it is safe to cease sampling). using these methods, we collect the first, to the best of our knowledge, unbiased sample of facebook. finally, we use one of our representative datasets, collected through mhrw, to characterize several key properties of facebook.
collaborative measurements of upload speeds in p2p systems. in this paper, we study the theory of collaborative upload bandwidth measurement in peer-to-peer environments. a host can use a bandwidth estimation probe to determine the bandwidth between itself and any other host in the system. the problem is that the result of such a measurement may not necessarily be the sender's upload bandwidth, since the most bandwidth restricted link on the path could also be the receiver's download bandwidth. in this paper, we formally define the bandwidth determination problem and devise efficient distributed algorithms. we consider two models, the free-departure and no-departure model, respectively, depending on whether hosts keep participating in the algorithm even after their bandwidth has been determined. we present lower bounds on the timecomplexity of any collaborative bandwidth measurement algorithm in both models. we then show how, for realistic bandwidth distributions, the lower bounds can be overcome. specifically, we present o(1) and o(log log n)-time algorithms for the two models. we corroborate these theoretical findings with practical measurements on a implementation on planetlab.
back-pressure routing for intermittently connected networks. we study a mobile wireless network where groups or clusters of nodes are intermittently connected via mobile "carriers" (the carriers provide connectivity over time among different clusters of nodes). over such networks (an instantiation of a delay tolerant network), it is well-known that traditional routing algorithms perform very poorly. in this paper, we propose a two-level back-pressure with source-routing algorithm (bp+sr) for such networks. the proposed bp+sr algorithm separates routing and scheduling within clusters (fast time-scale) from the communications that occur across clusters (slow time-scale), without loss in network throughput (i.e., bp+sr is throughput-optimal). more importantly, for a source and destination node that lie in different clusters, the traditional back-pressure algorithm results in large queue lengths at each node along its path. this is because the queue dynamics are driven by the slowest time-scale (i.e., that of the carrier nodes) along the path between the source and destination, which results in very large end-to-end delays. on the other-hand, we show that the two-level bp+sr algorithm maintains large queues only at a very few nodes, and thus results in order-wise smaller end-to-end delays. we provide analytical as well as simulation results to confirm our claims.
layered internet video engineering (live): network-assisted bandwidth sharing and transient loss protection for scalable video streaming. this paper presents a novel scheme, layered internet video engineering (live), in which network nodes feed back virtual congestion levels to video senders to assist both media-aware bandwidth sharing and transient loss protection. the video senders respond to such feedback by adapting the rates of encoded h.264/svc streams based on their respective video rate-distortion (r-d) characteristics. the same feedback is employed to calculate the amount of forward error correction (fec) protection for combating transient losses. simulation studies show that live can minimize the total distortion of all participating video streams and hence maximize their overall quality. at steady state, video streams experience no queueing delays or packet losses. in face of transient congestion, the network-assisted adaptive fec scheme effectively protects video packets from losses while minimizing overhead. our theoretical analysis further guarantees system stability for an arbitrary number of streams with heterogenous round trip delays below a prescribed limit. finally, we show that live streams can coexist with tcp flows within the existing explicit congestion notification (ecn) framework.