1161111
Localization in sparse networks using sweeps
Determining node positions is essential for many next-generation network functionalities. Previous localization algorithms lack correctness guarantees or require network density higher than required for unique localizability. In this paper, we describe a class of algorithms for fine-grained localization called Sweeps. Sweeps correctly finitely localizes all nodes in bilateration networks. Sweeps also handles angle measurements and noisy measurements. We demonstrate the practicality of our algorithm through extensive simulations on a large number of networks, upon which it consistently localizes one-thousand-node networks of average degree less than five in less than two minutes on a consumer PC.
4407504
Optimal ISP subscription for Internet multihoming: algorithm design and implication analysis
Multihoming is a popular method used by large enterprises and stub ISPs to connect to the Internet to reduce cost and improve performance. Recently researchers have studied the potential benefits of multihoming and proposed protocols and algorithms to realize these benefits. They focus on how to dynamically select which ISPs to use for forwarding and receiving packets, and assume that the set of subscribed ISPs is given a priori. In practice, a user often has the freedom to choose which subset of ISPs among all available ISPs to subscribe to. We call the problem of how to choose the optimal set of ISPs the ISP subscription problem. In this paper, We design a dynamic programming algorithm to solve the ISP subscription problem optimally. We also design a more efficient algorithm for a large class of common pricing functions. Using real traffic traces and realistic pricing data, we show that our algorithm reduces users' cost. Next we study how ISPs respond to users' optimal ISP subscription by adjusting their pricing strategies. We call this problem the ISP pricing problem. Using a realistic charging model, we formulate the problem as a non-cooperative game. We first prove that if cost is the only criterion used by a user to determine which subset of ISPs to subscribe to, at any equilibrium all ISPs receive zero revenue. We then study a more practical formulation in which different ISPs provide different levels of reliability and users choose ISPs to both improve reliability and reduce cost. We analyze this problem and show that at any equilibrium an ISP's revenue is positive and determined by its reliability.
5645902
On designing incentive-compatible routing and forwarding protocols in wireless ad-hoc networks: an integrated approach using game theoretical and cryptographic techniques
In many applications, wireless ad-hoc networks are formed by devices belonging to independent users. Therefore, a challenging problem is how to provide incentives to stimulate cooperation. In this paper, we study ad-hoc games---the routing and packet forwarding games in wireless ad-hoc networks. Unlike previous work which focuses either on routing or on forwarding, this paper investigates both routing and forwarding. We first uncover an impossibility result---there does not exist a protocol such that following the protocol to always forward others' traffic is a dominant action. Then we define a novel solution concept called cooperation-optimal protocols. We present Corsac, a cooperation-optimal protocol consisting of a routing protocol and a forwarding protocol. The routing protocol of Corsac integrates VCG with a novel cryptographic technique to address the challenge in wireless ad-hoc networks that a link's cost (ie, its type) is determined by two nodes together. Corsac also applies efficient cryptographic techniques to design a forwarding protocol to enforce the routing decision, such that fulfilling the routing decision is the optimal action of each node in the sense that it brings the maximum utility to the node. Additionally, we extend our framework to a practical radio propagation model where a transmission is successful with a probability. We evaluate our protocols using simulations. Our evaluations demonstrate that our protocols provide incentives for nodes to forward packets.
38612898
Transient behaviors of TCP-friendly congestion control protocols
We investigate the fairness, smoothness, responsiveness, and aggressiveness of TCP and three representative TCP-friendly congestion control protocols: GAIMD, TFRC, and TEAR. The properties are evaluated both analytically and via simulation by studying protocol responses to three network environment changes. The first environment change is the inherent fluctuations in a stationary network environment. Under this scenario, we consider three types of sending rate variations: smoothness, short-term fairness, and long-term fairness. For a stationary environment, we observe that smoothness and fairness are positively correlated. We derive an analytical expression for the sending rate coefficient of variation for each of the four protocols. These analytical results match well with experimental results. The other two environment changes we study are a step increase of network congestion and a step increase of available bandwidth. Protocol responses to these changes reflect their responsiveness and aggressiveness, respectively.
15017783
On the Computational Complexity of Sensor Network Localization
Determining the positions of the sensor nodes in a network is essential to many network functionalities such as routing, coverage and tracking, and event detection. The localization problem for sensor networks is to reconstruct the positions of all of the sensors in a network, given the distances between all pairs of sensors that are within some radius r of each other. In the past few years, many algorithms for solving the localization problem were proposed, without knowing the computational complexity of the problem. In this paper, we show that no polynomial-time algorithm can solve this problem in the worst case, even for sets of distance pairs for which a unique solution exists, unless RP = NP. We also discuss the consequences of our result and present open problems.
3103973
Sprite: a simple, cheat-proof, credit-based system for mobile ad-hoc networks
Mobile ad hoc networking has been an active research area for several years. How to stimulate cooperation among selfish mobile nodes, however, is not well addressed yet. In this paper, we propose Sprite, a simple, cheat-proof, credit-based system for stimulating cooperation among selfish nodes in mobile ad hoc networks. Our system provides incentive for mobile nodes to cooperate and report actions honestly. Compared with previous approaches, our system does not require any tamper-proof hardware at any node. Furthermore, we present a formal model of our system and prove its properties. Evaluations of a prototype implementation show that the overhead of our system is small. Simulations and analysis show that mobile nodes can cooperate and forward each other's messages, unless the resource of each node is extremely low.
2702750
A new look at multimedia synchronization in distributed environments
A multimedia system requires to handle automatically and uniformly the generation, manipulation, presentation, storage, and communication of independent discrete and continuous media data. The synchronization between various kinds of media data is a key issue in an integrated multimedia system, and has drawn a considerable attention. In this paper we investigate the synchronization problem in distributed multimedia environments and propose a new approach. Based on a globally synchronized clock, we present an isochronous clock-driven protocol for multimedia synchronization in a distributed environment. We show that the isochronous approach is simple, easy to understand, and more importantly, can guarantee the temporal ordering (including causal order and /spl Delta/-causal order). We believe that with the new developments in the improved NTP over Internet and very high accuracy of synchronized clocks over ATM and LANs, the clock-based distributed synchronization would provide a promising, yet simple and intuitive, alternative to the existing approaches.
17384103
RDT Properties and Evaluations
Proposed for MPCs, RDT has already been proved to support better performances than most of the direct network, such as smaller diameter based on its vector routing algorithm, smaller degree, embedded mesh/torus topology, etc. It gives a network form method to form groups of networks with recursively structured torus/torus-like networks. A RDT structure can be formed with the method and its related parameters. After analyzing its performance by the average distance, the descending vector routing reducing redundant computations and the fault-tolerant routing algorithm are proposed. A simpler structure named RDT(2,2,1)/a are proposed for the parallel systems with no more than 5000 nodes and given its performance evaluation. Considering the structure features of the practical RDTs, they are suitable for the interconnection network of an NoC design. The design of laying out RDT(2,2, 1)/a is proposed and proved to be available
19972899
Exploring Multilingual Negotiation Support for English-Chinese Dyads: An Experimental Study
The increasing number of international negotiations involving multiple languages necessitates a growing reliance on multilingual support. Whereas empirical studies on negotiation support systems (NSS) have shown that NSS generally improve negotiation performance, no existing NSS caters for multilingual negotiations. With multilingual support, communication problems brought by the different negotiators' cultures and languages are expected to be addressed. In this study, a negotiation support system with multilingual support was developed and a laboratory experiment was conducted to examine the impact of such support on six important dependent variables. Findings suggested significant effects of NSS support on individual outcome and joint outcome. Multilingual support helped to improve equality of outcome (under qualified conditions) but the time taken was significantly longer.
13986906
Decentralised Coordination for Software Process Enactment
Software process enactment mainly involves coordination of relevant team members to enact various tasks, which is supported by a centralised client/server architecture traditionally. This paper adopts concepts from peer-to-peer computing and presents an innovative approach to support decentralised process enactment. With this approach, team members are supported with coordination by direct communication among peers, which reflects applications’ increasingly distributed nature better. In addition, as a software process may be modelled incompletely at modelling time, a mechanism supporting run-time refinement of incomplete processes is also described in this paper.
39340312
Optimizing Peer Virtualization and Load Balancing
Structured peer-to-peer systems are popular solutions for large scale distributed computing and query processing. Heterogeneity among peers calls for peer virtualization to maintain a simple, yet powerful peer-to-peer overlay network. Nevertheless, peer virtualization generates a huge number of virtual peers and causes the unnecessary communication overhead in the routing process. In this paper, we propose a new peer-to-peer routing algorithm that reduces the number of hops of message forwarding and improves the performance of routing. We study the new and previous algorithms from the analytical perspective and through simulations. It shows that the average number of hops per query is improved by 15% to 25% in our algorithm. In addition, we propose a Top-k peer selection algorithm for load balancing to find out the top k best available nodes in the P2P network with 2(N-1) messages within 2O(logN) hops. (N is the number of physical nodes.) The load balancing scheme is based on multiple factors which could be optimized on cost, proximity, reputation and other factors.