Proceedings of the 18th annual IEEE International Conference on Network Protocols, ICNP 2010, Kyoto, Japan, 5-8 October, 2010. IEEE Computer Society 【DBLP Link】
【Paper Link】 【Pages】:1-10
【Authors】: Dejun Yang ; Guoliang Xue ; Xi Fang ; Satyajayant Misra ; Jin Zhang
【Abstract】: In this paper, we study the problem of routing in networks with max-min fair congestion control at the link level. The goal of each user is to maximize its own bandwidth by selecting its path. The problem is formulated as a non-cooperative game. We first prove the existence of Nash Equilibria. This is important, because at a Nash Equilibrium (NE), no user has the incentive to change its routing strategy. In addition, we investigate how the selfish behavior of the users may affect the performance of the network as a whole. We next introduce a novel concept of observed available bandwidth on each link. It allows a user to find a path with maximum bandwidth under max-min fair congestion control in polynomial time. We then present a game based algorithm to compute an NE and prove that by following the natural game course the network converges to an NE. Extensive experiments show that the network can converge to an NE in less than 10 iterations and also significantly improves the fairness compared with other algorithms. Our results have the implication for the future routing protocol design.
【Keywords】: Nash Equilibrium; Max-min fair bandwidth allocation; non-cooperative game
【Paper Link】 【Pages】:11-20
【Authors】: Fernando A. Kuipers ; Anteneh Beshir ; Ariel Orda ; Piet Van Mieghem
【Abstract】: Physical impairments, such as noise and signal distortions, negatively affect the quality of information transfer in optical networks. The effect of physical impairments predominantly augments with distance and bit rate of the signal to the point that it becomes detrimental to the information transfer. To reverse the effect of physical impairments, the signal needs to be regenerated at nodes that have regeneration capabilities. Regenerators are costly and are, therefore, usually only sparsely placed in the network, in which case it is referred to as a translucent network. This paper deals with two problems in translucent networks, namely: (1) how to incorporate impairment awareness in the routing algorithms, and (2) how many regenerators to place inside the network and where. We propose exact and heuristic algorithms for impairment-aware path selection and, through simulations, show that our heuristic TIARA is computationally efficient and performs very close to our exact algorithm EIARA. Subsequently, we propose a greedy algorithm for placing regenerators that, contrary to previous proposals, is suitable for multiple impairment metrics, has polynomial complexity for a single impairment metric, and is cheaper in terms of the number of regenerators needed.
【Keywords】: Translucent Networks; Optical Signal Impairments; Regenerator Placement; Impairment-aware Routing
【Paper Link】 【Pages】:21-30
【Authors】: Mingui Zhang ; Cheng Yi ; Bin Liu ; Beichuan Zhang
【Abstract】: Current network infrastructures exhibit poor power efficiency, running network devices at full capacity all the time regardless of the traffic demand and distribution over the network. Most research on router power management are at component level or link level, treating routers as isolated devices. A complementary approach is to facilitate power management at network level by routing traffic through different paths to adjust the workload on individual routers or links. Given the high path redundancy and low link utilization in today's large networks, this approach can potentially allow more network devices or components to go into power saving mode. This paper proposes an intra-domain traffic engineering mechanism, GreenTE, which maximizes the number of links that can be put into sleep under given performance constraints such as link utilization and packet delay. Using network topologies and traffic data from several wide-area networks, our evaluation shows that GreenTE can reduce line-cards' power consumption by 27% to 42% under constraints that the maximum link utilization is below 50% and the network diameter remains the same as in shortest path routing.
【Keywords】: Routing; Power demand; Network topology; Mathematical model; Multiprotocol label switching; Turning; Delay
【Paper Link】 【Pages】:31-40
【Authors】: Zhuo Huang ; David Lin ; Jih-Kwon Peir ; Shigang Chen ; S. M. Iftekharul Alam
【Abstract】: New generations of video, voice, high-performance computing and social networking applications have continuously driven the development of novel routing technologies for higher packet forwarding speeds to meet the future Internet demand. One of the fundamental design issues for core routers is fast routing table lookup, which is a key problem at the network layer of the Internet protocol suite. It is difficult to scale the current TCAM-based or trie-based solutions for future routing tables due to increasing table size, longer prefix length, and demands for higher throughput. This paper focuses on hash-based lookup solutions that have the potential of offering high throughput at one memory access per packet. We design the first deterministic multi-hashing scheme with small indexing overhead, which evenly distributes address prefixes to hash buckets for routing-information storage. We minimize both the size of each bucket and the number of buckets that need to be fetched to the network processor for packet forwarding. Consequently, near-optimal routing throughput is achieved. Performance evaluations demonstrate that the proposed deterministic multi-hashing scheme can maintain a constant lookup rate of over 250 million packets per second with today's commodity SRAM, which is much faster than the existing hashing schemes.
【Keywords】: Routing; Throughput; Random access memory; Internet; Table lookup; Indexing
【Paper Link】 【Pages】:41-51
【Authors】: Jiangwei Zhou ; Yu Chen ; Ben Leong ; Boqin Feng
【Abstract】: Geographic routing is a promising approach for point-to-point routing in wireless sensor networks, but it requires the availability of geographic coordinates. Location devices like GPS do not work indoors and they are often not cost-effective for ubiquitous deployment on a large scale. While it is possible to manually configure coordinates for small sensor networks, it is infeasible to do the same for large-scale networks with thousands of nodes. We present Particle Swarm Virtual Coordinates (PSVC), a distributed virtual coordinate assignment algorithm that employs Particle Swarm Optimization to compute virtual coordinates for geographic routing. PSVC converges faster, achieves a lower hop stretch, and scales well up to large networks of 3,200 nodes compared to NoGeo. Also, PSVC makes no assumptions on the network topology and can naturally be extended to three-dimensional (3D) wireless sensor networks.
【Keywords】: Routing; Springs; Network topology; Mathematical model; Three dimensional displays; Particle swarm optimization; Topology
【Paper Link】 【Pages】:52-61
【Authors】: Shucheng Liu ; Guoliang Xing ; Hongwei Zhang ; Jianping Wang ; Jun Huang ; Mo Sha ; Liusheng Huang
【Abstract】: Interference modeling is crucial for the performance of numerous WSN protocols such as congestion control, link/channel scheduling, and reliable routing. In particular, understanding and mitigating interference becomes increasingly important for Wireless Sensor Networks (WSNs) as they are being deployed for many data-intensive applications such as structural health monitoring. However, previous works have widely adopted simplistic interference models that fail to capture the wireless realities such as probabilistic packet reception performance. Recent studies suggested that the physical interference model (i.e., PRR-SINR model) is significantly more accurate than existing interference models. However, existing approaches to physical interference modeling exclusively rely on the use of active measurement packets, which imposes prohibitively high overhead to bandwidth-limited WSNs. In this paper, we propose the passive interference measurement (PIM) approach to tackle the complexity of accurate physical interference characterization. PIM exploits the spatiotemporal diversity of data traffic for radio performance profiling and only needs to gather a small amount of statistics about the network. We evaluate the efficiency of PIM through extensive experiments on both a 13-node and a 40-node testbeds of TelosB motes. Our results show that PIM can achieve high accuracy of PRR-SINR modeling with significantly lower overhead compared with the active measurement approach.
【Keywords】: Interference; Signal to noise ratio; Wireless sensor networks; Computational modeling; Particle measurements; Atmospheric measurements; Wireless communication
【Paper Link】 【Pages】:62-71
【Authors】: Xiaoping Wang ; Yunhao Liu ; Zheng Yang ; Junliang Liu ; Jun Luo
【Abstract】: Accurate localization is crucial for wireless ad-hoc and sensor networks. Among the localization schemes, component-based approaches specialize in localization performance, which can properly conquer network sparseness and anchor sparseness. However, such design is sensitive to measurement errors. Existing robust localization methods focus on eliminating the positioning error of a single node. Indeed, a single node has two dimensions of freedom in 2D space and only suffers from one type of transformation: translation. As a rigid 2D structure, a component suffers from three possible transformations: translation, rotation, and reflection. A high degree of freedom brings about complicated cases of error productions and difficulties on error controlling. This study is the first work addressing how to deal with ranging noises for component- based methods. By exploiting a set of robust patterns, we present an Error-TOlerant Component-based algorithm (ETOC) that not only inherits the high-performance characteristic of component-based methods, but also achieves robustness of the result. We evaluate ETOC through a real-world sensor network consisting of 120 TelosB motes as well as extensive large-scale simulations. Experiment results show that, comparing with the-state-of-the-art designs, ETOC can work properly in sparse networks and provide more accurate localization results.
【Keywords】: structural error tolerance; component-based; localization; location ambiguity; robust localization
【Paper Link】 【Pages】:72-81
【Authors】: Yiyang Li ; Jianxia Ning ; Zhengyuan Xu ; Srikanth V. Krishnamurthy ; Gang Chen
【Abstract】: As an alternative to radio-frequency (RF) communications, optical wireless communications (OWC) can support high data rates and low power operations while providing good jamming resistance. Our focus in this paper is on deep ultraviolet (UV) outdoor communications (UVOC) where solar blind and non-line-of-sight operations are attractive. Light beams from UV LED arrays serve as information carriers. In an abstract sense, this is similar to directional transmissions in RF; however, the PHY layer characteristics significantly differ due to atmospheric scattering. First, we perform extensive experiments on a UV testbed towards understanding signal propagation and the impact of the PHY on medium access. We find that UV propagation supports (a) fully duplex communications and (b) multiple data rate transmissions. Next, we propose a novel contention-based media access control (UVOC-MAC) protocol that inherently accounts for the UV PHY layer and fully exploits multi-fold spatial reuse opportunities. Evaluations via both simulations and analysis show that UVOC-MAC effectively mitigates collisions and achieves high throughput. In particular, up to a 4-fold increase in throughput and 50% reduction in collision are possible compared to a MAC protocol agnostic to the UV PHY properties.
【Keywords】: MAC; Optical wireless communications; UV
【Paper Link】 【Pages】:82-91
【Authors】: Jung Il Choi ; Mayank Jain ; Maria A. Kazandjieva ; Philip Levis
【Abstract】: We describe grant-to-send, a novel collision avoidance algorithm for wireless mesh networks. Rather than announce packets it intends to send, a node using grant-to-send announces packets it expects to hear others send.
【Keywords】: Multiaccess communication; Wireless communication; Bit rate; Clocks; Wireless sensor networks
【Paper Link】 【Pages】:92-102
【Authors】: Raju Kumar ; Srikar Tati ; Felipe de Mello ; Srikanth V. Krishnamurthy ; Thomas F. La Porta
【Abstract】: Network coding has been proposed as an alternative to the conventional store-and-forward routing paradigm for data delivery in networks. When deployed in a multi-rate wireless network, network coding has to interact with rate adaptation. When multicasting packets (a requirement of network coding) in a multi-rate IEEE 802.11 wireless network, one must use care when selecting the transmission rate to use. We refer to this problem as rate selection. We analyze the performance of network coding for a small set of scenarios representative of common topologies in a network that lead to coding opportunities. Based on this analysis, we present our Network Coding aware Rate Selection (NCRS) algorithm which takes into account transmission rates used for unicast links to all multicast targets. Simulation results show that in a multi-hop wireless network, network coding with NCRS achieves up to 24% more gain over routing than network coding with other rate selection algorithms.
【Keywords】: Network coding; Signal to noise ratio; Throughput; Encoding; Routing; Wireless networks; IEEE 802.11g Standard
【Paper Link】 【Pages】:103-112
【Authors】: Alexander J. T. Gurney ; Timothy G. Griffin
【Abstract】: There are several situations in which it would be advantageous to allow route preferences to be dependent on which neighbor is to receive the route. This idea could be realised in many possible ways and could interact differently with other elements of route choice, such as filtering: not all of these will have the property that a unique routing solution can always be found. We develop an algebraic model of route selection to aid in the analysis of neighbor-specific preferences in multipath routing. Using this model, we are able to identify a set of such routing schemes in which convergence is guaranteed.
【Keywords】: Routing; Servers; Routing protocols; Convergence; Algebra; Communities
【Paper Link】 【Pages】:113-123
【Authors】: Luca Cittadini ; Giuseppe Di Battista ; Thomas Erlebach ; Maurizio Patrignani ; Massimo Rimondini
【Abstract】: Compliance with the Gao-Rexford conditions [1] is perhaps the most realistic explanation of Internet routing stability, although BGP is renowned to be prone to oscillations. Informally, the Gao-Rexford conditions assume that (i) the business relationships between Internet Service Providers (ISPs) yield a hierarchy, (ii) each ISP behaves in a rational way, i.e., it does not offer transit to other ISPs for free, and (iii) each ISP ranks routes through customers better than routes through providers and peers.
【Keywords】: Routing; Business; Internet; Stability analysis; Safety; Biological system modeling; Polynomials
【Paper Link】 【Pages】:124-133
【Authors】: Zied Ben-Houidi ; Mickael Meulle
【Abstract】: One of the most common provider provisioned VPN technologies uses MPLS as a data plane for customer flow isolation and BGP as a control plane for routing between VPN sites. From a data plane perspective, such networks can provision hundreds of thousands of VPN sites. However, the BGP control plane is prone to scalability concerns. Some BGP routers in VPN backbones must handle routes for all the VPN sites that the provider connects. The number of sites can generate two million BGP routes in large VPN backbones, almost ten times the number of routes in a core Internet router. Prior work proposed solutions to evolve such networks. Yet, we argue that they fail to address the root cause of VPN routing performance issues. In this paper, we show that VPN routing scheme's poor scalability stems from the application to VPNs of a protocol originally designed for full routing, specifically the Internet. Rather than evolving the current standard based on BGP, we take a principled approach to rethink routing in large VPNs. We propose Two-Step VPN Routing, a new approach for scalable VPN routing. We validate our design choices and compare our approach to existing ones, using both BGP updates and router configurations collected from a large VPN provider.
【Keywords】: Virtual private networks; Routing; Multiprotocol label switching; Routing protocols; IP networks; Scalability; Internet
【Paper Link】 【Pages】:134-143
【Authors】: Tongqing Qiu ; Lusheng Ji ; Dan Pei ; Jia Wang ; Jun (Jim) Xu
【Abstract】: IP prefix hijacking is one of the top security threats targeting today's Internet routing protocol. Several schemes have been proposed to either detect or mitigate prefix hijacking events. However, none of these approaches is adopted and deployed on a large-scale on the Internet for reasons such as scalability, economical practicality, or unrealistic assumptions about the collaborations among ISPs. Thus there are no actionable and deployable solutions for dealing with prefix hijacking. In this paper, we study key issues related to deploying and operating an IP prefix hijacking detection and mitigation system. Our contributions include (i) deployment strategies for hijacking detection and mitigation system (named as TowerDefense): a practical service model for prefix hijacking protection and effective algorithms for selecting agent locations for detecting and mitigating prefix hijacking attacks; and (ii) large scale experiments on PlanetLab and extensive analysis on the performance of TowerDefense.
【Keywords】: Poles and towers; Internet; Topology; IP networks; Mirrors; Greedy algorithms; Routing protocols
【Paper Link】 【Pages】:144-153
【Authors】: Nan Jiang ; Jin Cao ; Yu Jin ; Erran L. Li ; Zhi-Li Zhang
【Abstract】: As a key approach to securing large networks, existing anomaly detection techniques focus primarily on network traffic data. However, the sheer volume of such data often renders detailed analysis very expensive and reduces the effectiveness of these tools. In this paper, we propose a light-weight anomaly detection approach based on unproductive DNS traffic, namely, the failed DNS queries, with a novel tool - DNS failure graphs. A DNS failure graph captures the interactions between hosts and failed domain names. We apply a graph decomposition algorithm based on the tri-nonnegative matrix factorization technique to iteratively extract coherent co-clusters (dense subgraphs) from DNS failure graphs. By analyzing the co-clusters in the daily DNS failure graphs from a 3-month DNS trace captured at a large campus network, we find these co-clusters represent a variety of anomalous activities, e.g., spamming, trojans, bots, etc.. In addition, these activities often exhibit distinguishable subgraph structures. By exploring the temporal properties of the co-clusters, we show our method can identify new anomalies that likely correspond to unreported domain-flux bots.
【Keywords】: Servers; Malware; Electronic mail; Communities; Internet; Correlation; IP networks
【Paper Link】 【Pages】:154-163
【Authors】: Lei Yang ; Jinsong Han ; Yong Qi ; Yunhao Liu
【Abstract】: Cardinality estimation and tag authentication are two major issues in large-scale Radio Frequency Identification (RFID) systems. While there exist both per-tag and probabilistic approaches for the cardinality estimation, the RFID-oriented authentication protocols are mainly per-tag based: the reader authenticates one tag at each time. For a batch of tags, current RFID systems have to identify them and then authenticate each tag sequentially, incurring large volume of authentication data and huge communication cost. We study the RFID batch authentication issue and propose the first probabilistic approach, termed as Single Echo based Batch Authentication (SEBA), to meet the requirement of prompt and reliable batch authentications in large scale RFID applications, e.g., the anti-counterfeiting solution. Without the need of identifying tags, SEBA provides a provable probabilistic guarantee that the percentage of potential counterfeit products is under the user-defined threshold. The experimental result demonstrates the effectiveness of SEBA in fast batch authentications and significant improvement compared to existing approaches.
【Keywords】: SEBA; RFID; Batch Authentication; Identification-free; Anti-Counterfeiting
【Paper Link】 【Pages】:164-173
【Authors】: Yating Hsu ; David Lee
【Abstract】: A major hurdle of formal analysis of protocol security properties is the well-known state explosion - a protocol system usually contains infinitely many or a formidable number of states. As a result, most of the analysis resorts to heuristics, such as state space pruning. Given the temporal property of authentication and authorization protocols, we introduce trace inclusion transformation of protocol specification to reduce significantly the state space. We further cut down the number of states by online minimization for obtaining a model of a manageable size for a formal and rigorous analysis. However, the two state space reduction procedures may result in false negative and false positives. We show that our trace inclusion transformation and online minimization do not introduce any false negative. On the other hand, we design an efficient algorithm for ruling out all the possible false positives. Therefore, our analysis is sound and complete. For a case study, we analyze OAuth, a standardization of API authentication protocols. Our automated analysis identifies a number of attacks in the original specification, including the one that has been detected. We also analyze the second version of OAuth and prove it is secure if the API interface is secure.
【Keywords】: OAuth; authentication and authorization; communicating extended finite state machine; trace inclusion transformation; online minimization
【Paper Link】 【Pages】:174-182
【Authors】: Hrishikesh B. Acharya ; Aditya Joshi ; Mohamed G. Gouda
【Abstract】: A firewall is a packet filter placed at an entry point of a network in the Internet. Each packet that goes through this entry point is checked by the firewall to determine whether to accept or discard the packet. The firewall makes this determination based on a specified sequence of overlapping rules. The firewall uses the first-match criterion to determine which rule in the sequence should be applied to which packet. Thus, to compute the set of packets to which a rule is applied, the firewall designer needs to consider all the rules that precede this rule in the sequence. This “rule dependency” complicates the task of designing firewalls (especially those with thousands of rules), and makes firewalls hard to understand. In this paper, we present a metric, called the dependency metric, for measuring the complexity of firewalls. This metric, though accurate, does not seem to suggest ways to design firewalls whose dependency metrics are small. Thus, we present another metric, called the inversion metric, and develop methods for designing firewalls with small inversion metrics. We show that the dependency metric and the inversion metric are correlated for some classes of firewalls. So by aiming to design firewalls with small inversion metrics, the designer may end up with firewalls whose dependency metrics are small as well. We present a method for designing modular firewalls whose inversion metrics are very small. Each modular firewall consists of several components, called firewall modules. The inversion metric of each firewall module is very small - in fact, 1 or 2. Thus, we conclude that modular firewalls are easy to design and easy to understand.
【Keywords】: Measurement; Complexity theory; Multicore processing; Fires; Algorithm design and analysis; Approximation methods; IP networks
【Paper Link】 【Pages】:183-192
【Authors】: Youngtae Noh ; Paul Wang ; Uichin Lee ; Dustin Torres ; Mario Gerla
【Abstract】: Underwater Acoustic Sensor Networks (UW-ASNs) use acoustic links as a means of communications and are accordingly confronted with long propagation delays, low bandwidth, and high transmission power consumption. This unique situation, however, permits multiple packets to concurrently propagate in the underwater channel, which must be exploited in order to improve the overall throughput. To this end, we propose the Delay-aware Opportunistic Transmission Scheduling (DOTS) algorithm that uses passively obtained local information (i.e., neighboring nodes' propagation delay map and their expected transmission schedules) to increase the chances of concurrent transmissions while reducing the likelihood of collisions. Our extensive simulation results document that DOTS outperforms existing solutions and provides fair medium access.
【Keywords】: CSMA; Underwater; Medium Access Control; Opportunistic Transmission
【Paper Link】 【Pages】:193-202
【Authors】: Wei Gao ; Guohong Cao
【Abstract】: Effective data forwarding in Delay Tolerant Networks (DTNs) is challenging, due to the low node density, unpredictable node mobility and lack of global information in such networks. Most of the current data forwarding schemes choose the nodes with the best cumulative capability of contacting others as relays to carry and forward data, but these nodes may not be the best relay choices within a short time period, due to the heterogeneity of the transient node contact patterns. In this paper, we propose a novel approach to improve the performance of data forwarding in DTNs by exploiting the transient node contact patterns. We formulate the transient node contact patterns based on experimental studies of realistic DTN traces, and propose appropriate forwarding metrics based on these patterns to improve the effectiveness of data forwarding decision. When applied to various data forwarding strategies, our proposed forwarding metrics achieve much better performance compared to existing schemes with similar forwarding cost.
【Keywords】: Transient analysis; Measurement; Peer to peer computing; Relays; Mobile communication; Time factors; IEEE 802.11 Standards
【Paper Link】 【Pages】:203-212
【Authors】: Md. Yusuf Sarwar Uddin ; Brighten Godfrey ; Tarek F. Abdelzaher
【Abstract】: In this paper, we develop a cooperative mechanism, RELICS, to combat selfishness in DTNs. In DTNs, nodes belong to self-interested individuals. A node may be selfish in expending resources, such as energy, on forwarding messages from others, unless offered incentives. We devise a rewarding scheme that provides incentives to nodes in a physically realizable way in that the rewards are reflected into network operation. We call it in-network realization of incentives. We introduce explicit ranking of nodes depending on their transit behavior, and translate those ranks into message priority. Selfishness drives each node to set its energy depletion rate as low as possible while maintaining its own delivery ratio above some threshold. We show that our cooperative mechanism compels nodes to cooperate and also achieves higher energy-economy compared to other previous results.
【Keywords】: Peer to peer computing; Routing protocols; Relays; Thin film transistors; Games; Manipulators
【Paper Link】 【Pages】:213-222
【Authors】: Chuan Han ; Yaling Yang ; Yongxiang Peng
【Abstract】: Real-time applications in ad hoc networks require fast route repair mechanisms to minimize the interruptions to their communications. Cache-based route repair schemes are popular choices since they can quickly resume communications using cached backup paths after a route break. In this paper, through thorough theoretical modeling of the cache-based route repair process, we derive the optimal cache-based route repair policy. This optimal policy considers both the overhead of the route repair schemes and the promptness of the repair action. The correctness and advantages of our optimal policy are validated by extensive simulations.
【Keywords】: Maintenance engineering; Routing protocols; Real time systems; Routing; Ad hoc networks; Adaptation model; Mobile computing
【Paper Link】 【Pages】:223-232
【Authors】: Zhenyu Yang ; Ming Li ; Wenjing Lou
【Abstract】: Live multimedia streaming (LMS) services are important in vehicular ad hoc networks (VANETs) for their capability of providing comprehensive and user-friendly information. The fundamental challenges come from achieving stable and high streaming rate (smooth playback) for all the interested vehicles while using minimal bandwidth resources, especially under the highly dynamic topology of VANETs and the lossy nature of vehicular wireless communications. A recent technique, symbol-level network coding (SLNC), has been shown to be an effective approach to improve the efficiency of bandwidth utilization, by exploiting both wireless symbol-level diversity and the benefits of network coding. In this paper, we introduce CodePlay, a new LMS scheme in VANETs that fully takes advantage of SLNC through a coordinated local push mechanism. Streaming contents are actively disseminated from dedicated sources to interested vehicles via local coordination of distributively selected relays, each of which will ensure smooth playback for vehicles nearby. CodePlay is designed to simultaneously improve the performance of LMS service in terms of streaming rate, service delivery delay and bandwidth efficiency. We use extensive simulations to show that CodePlay is potentially suitable for future LMS applications in VANET.
【Keywords】: Relays; Delay; Roads; Least squares approximation; Vehicles; Peer to peer computing; Receivers
【Paper Link】 【Pages】:233-242
【Authors】: Joon Yoo ; Brian Sung Chul Choi ; Mario Gerla
【Abstract】: In the drive-thru Internet access systems, vehicles connect to road-side access points (APs) to use IP-based services, such as web-browsing, e-mail, and file download, in addition to the customized vehicular applications. However, the mobility of vehicles and the limited coverage of APs result in the short connectivity duration and low throughput, thus leading to low availability of Internet to vehicle services. Vehicle-to-vehicle (V2V) relay support is an attractive backup solution that can address these limitations by extending the coverage. To fully realize the benefit of V2V relay support, however, the vehicle that gives the best performance must be selected as relay, yet the dynamic wireless channel conditions and the high speed of vehicles render relay selection a challenging problem. In this paper, we evaluate several relay strategies in an analytic framework to compute the resulting overall network capacity with fading channels. We then propose and devise an efficient opportunistic relay protocol that exploits multiuser diversity and effectively copes with the dynamic channel. Through both capacity analysis and Qualnet simulations, we show that the opportunistic relay scheme significantly outperforms others.
【Keywords】: Relays; Vehicles; Throughput; Fading; Protocols; Internet; Downlink
【Paper Link】 【Pages】:243-252
【Authors】: Kebin Liu ; Mo Li ; Yunhao Liu ; Xiang-Yang Li ; Minglu Li ; Huadong Ma
【Abstract】: The high mobility of VANET makes information exchange across the network excessively difficult. Traditional approaches designed for stationary networks are not applicable due to the high dynamics among the nodes. Applying the routing techniques tailored for general mobile networks inevitably brings huge traffic burden to the crowded urban VANET and leads to low efficiency. To make the information exchange fluent and efficient, we explore the unique features of the urban VANET. By exploring the invariants in the mobile network topology, we are able to efficiently manage the information on top of the “intersection graph” transformed from the underlying network of road segments in the urban area. Our approach can thus achieve efficient query dissemination and data retrieval on this information organization. We intensively investigate and analyze a trace that records the movement of more than 4000 taxies in the urban area of Shanghai City over several months. We grasp the key impact of the fundamental factors that affect the VANET behaviors and accordingly develop tailored techniques to maximize the performance of this design. Experimental results validate the effectiveness and efficiency of our design.
【Keywords】: Roads; Vehicles; Routing; Urban areas; Mobile communication; Mobile computing; Vehicle dynamics
【Paper Link】 【Pages】:253-262
【Authors】: Shaoquan Zhang ; Ziyu Shao ; Minghua Chen
【Abstract】: We study the problem of maximizing the broadcast rate in peer-to-peer (P2P) systems under node degree bounds, i.e., the number of neighbors a node can simultaneously connect to is upper-bounded. The problem is critical for supporting high-quality video streaming in P2P systems, and is challenging due to its combinatorial nature. In this paper, we address this problem by providing the first distributed solution that achieves near-optimal broadcast rate under arbitrary node degree bounds, and over arbitrary overlay graph. It runs on individual nodes and utilizes only the measurement from their one-hop neighbors, making the solution easy to implement and adaptable to peer churn and network dynamics. Our solution consists of two distributed algorithms proposed in this paper that can be of independent interests: a network-coding based broadcasting algorithm that optimizes the broadcast rate given a topology, and a Markov-chain guided topology hopping algorithm that optimizes the topology. Our distributed broadcasting algorithm achieves the optimal broadcast rate over arbitrary P2P topology, while previously proposed distributed algorithms obtain optimality only for P2P complete graphs. We prove the optimality of our solution and its convergence to a neighborhood around the optimal equilibrium under noisy measurements or without timescale separation assumptions. We demonstrate the effectiveness of our solution in simulations using uplink bandwidth statistics of Internet hosts.
【Keywords】: Peer to peer computing; Markov processes; Algorithm design and analysis; Heuristic algorithms; Network coding; Approximation methods; Broadcasting
【Paper Link】 【Pages】:263-274
【Authors】: Matthew J. Probst ; Jun Cheol Park ; Ravin Abraham ; Sneha Kumar Kasera
【Abstract】: Social networks can serve as an effective mechanism for distribution of vulnerability patches and other malware immunization code. We propose a novel approach—SocialSwarm—by which peers exploit distances to their social peers to approximate levels of altruism and to collaborate on flash distribution of large files. SocialSwarm supports heterogeneous BitTorrent swarms of mixed social and non-social peers. We implement SocialSwarm as an extension to the Rasterbar libtorrent library—widely used by BitTorrent clients—and evaluate it on a testbed of 500 independent clients with social distances extracted from Facebook. We show that SocialSwarm can significantly reduce the average file distribution time, not only among socially connected peers, but also among other swarm participants.
【Keywords】: Peer to peer computing; Bandwidth; Social network services; Protocols; Measurement; Malware; Mathematical model
【Paper Link】 【Pages】:275-284
【Authors】: Yuan Feng ; Baochun Li ; Bo Li
【Abstract】: In peer-assisted video-on-demand (VoD) streaming systems, server bandwidth costs can be astronomical when the number of videos and peers scales up. Since peers are able to seek to an arbitrary point of playback in any video at any time, prefetching is often considered a desirable way to redistribute media content in the entire system so that less server bandwidth may be consumed. In this paper, we point out that the benefits of prefetching in peer-assisted VoD do not come without considerable upfront costs of bandwidth, and as such prefetching strategies should be carefully designed to remain beneficial, but practically carried out in a decentralized manner. We show how the challenge of minimizing server bandwidth is equivalent to maximizing the system-wide utility in the context of double auction markets, where each peer participates in a number of double auctions by bidding for and selling video segments. With simulations, we show that prefetching strategies based on such double auction markets are decentralized, and are effective in reducing the consumption of server bandwidth as well, as compared to existing alternative heuristics in the literature.
【Keywords】: Bandwidth; Prefetching; Servers; Videos; Minimization; Optimization; Context
【Paper Link】 【Pages】:285-294
【Authors】: Feng Qian ; Zhaoguang Wang ; Alexandre Gerber ; Zhuoqing Morley Mao ; Subhabrata Sen ; Oliver Spatscheck
【Abstract】: In 3G cellular networks, the release of radio resources is controlled by inactivity timers. However, the timeout value itself, also known as the tail time, can last up to 15 seconds due to the necessity of trading off resource utilization efficiency for low management overhead and good stability, thus wasting considerable amount of radio resources and battery energy at user handsets. In this paper, we propose Tail Optimization Protocol (TOP), which enables cooperation between the phone and the radio access network to eliminate the tail whenever possible. Intuitively, applications can often accurately predict a long idle time. Therefore the phone can notify the cellular network on such an imminent tail, allowing the latter to immediately release radio resources. To realize TOP, we utilize a recent proposal of 3GPP specification called fast dormancy, a mechanism for a handset to notify the cellular network for immediate radio resource release. TOP thus requires no change to the cellular infrastructure and only minimal changes to smartphone applications. Our experimental results based on real traces show that with a reasonable prediction accuracy, TOP saves the overall radio energy (up to 17%) and radio resources (up to 14%) by reducing tail times by up to 60%. For applications such as multimedia streaming, TOP can achieve even more significant savings of radio energy (up to 60%) and radio resources (up to 50%).
【Keywords】: 3G mobile communication; Delay; Protocols; Optimization; Multiaccess communication; Streaming media; Bandwidth
【Paper Link】 【Pages】:295-304
【Authors】: Peilong Li ; Honghai Zhang ; Baohua Zhao ; Sampath Rangarajan
【Abstract】: Scalable video coding (SVC), together with adaptive modulation and coding (AMC), can improve wireless multicast streaming video by jointly performing radio resource allocation and modulation and coding scheme (MCS) selection. However, the existing schemes in the literature allocate radio resources for different video layers separately, which leads to a waste of radio resources. In this work, we introduce the notion of joint layer resource allocation which allows to jointly allocate resources to multiple video layers that are assigned the same MCS. We formulate this problem and prove it to be NP-hard. Then we develop a pseudo-polynomial algorithm that finds the optimal total system utility. Our algorithm assumes a very generic utility function and flexible video layer rates. To reduce the complexity of the algorithm, we also propose Fully Polynomial Time Approximation Schemes (FPTAS) for the same problem. Simulation results show that our optimal algorithm offers significant improvement on system utility over a previous optimal algorithm and a greedy algorithm both of which do not support joint layer resource allocation. The proposed approximation algorithm provides controllable tradeoff between performance and computational complexity and, with appropriately chosen parameters, it outperforms the greedy algorithm with 40% less running time.
【Keywords】: Streaming media; Resource management; Heuristic algorithms; Joints; Approximation algorithms; Encoding; Modulation
【Paper Link】 【Pages】:305-314
【Authors】: Jun Huang ; Guoliang Xing ; Gang Zhou ; Ruogu Zhou
【Abstract】: Recent years have witnessed the increasing adoption of ZigBee technology for performance-sensitive applications such as wireless patient monitoring in hospitals. However, operating in unlicensed ISM bands, ZigBee devices often yield unpredictable throughput and packet delivery ratio due to the interference from ever increasing WiFi hotspots in 2.4 GHz band. Our empirical results show that, although WiFi traffic contains abundant white space, the existing coexistence mechanisms such as CSMA are surprisingly inadequate for exploiting it. In this paper, we propose a novel approach that enables ZigBee links to achieve assured performance in the presence of heavy WiFi interference. First, based on statistical analysis of real-life network traces, we present a Pareto model to accurately characterize the white space in WiFi traffic. Second, we analytically model the performance of a ZigBee link in the presence of WiFi interference. Third, based on the white space model and our analysis, we develop a new ZigBee frame control protocol called WISE, which can achieve desired trade-offs between link throughput and delivery ratio. Our extensive experiments on a testbed of 802.11 netbooks and 802.15.4 TelosB motes show that, in the presence of heavy WiFi interference, WISE achieves 4× and 2× performance gains over B-MAC and a recent reliable transmission protocol, respectively, while only incurring 10.9% and 39.5% of their overhead.
【Keywords】: IEEE 802.11 Standards; Zigbee; White spaces; Interference; Protocols; Throughput; Receivers
【Paper Link】 【Pages】:1-2
【Authors】: Teruo Higashino ; Kenji Suzuki
【Abstract】: Welcome to ICNP 2010, the eighteenth IEEE International Conference on Network Protocols, and welcome to Kyoto, Japan! ICNP is the premier conference covering all aspects of network protocols, including design, analysis, specification, verification, implementation and performance. This is our third organization of ICNP in Japan. In 1995, 15 years ago, we first organized ICNP at Tokyo. Tokyo is the capital of Japan, and the center of politics and economics. In 2000, we organized ICNP at Osaka, which is a commercial city. This time, we organize ICNP at Kyoto. Kyoto is the old capital of Japan, and so many historical sightseeing places are located, and is a center of Japanese culture. We hope that you will enjoy Japanese beautiful culture and autumn scenery.
【Keywords】:
【Paper Link】 【Pages】:1-2
【Authors】: Sonia Fahmy ; Toru Hasegawa
【Abstract】: Welcome to IEEE ICNP 2010, the Eighteenth International Conference on Network Protocols in Kyoto, Japan! Continuing the tradition of being the premier conferences on network protocols, we have an exciting program with papers, posters and a panel, representing the best of today's research. We are delighted to have two keynote speakers this year: Professor P. R. Kumar (University of Illinois at Urbana-Champaign, USA) and Dr. Shigeyuki Akiba (President and Chief Executive Officer, KDDI R&D Laboratories Inc., Japan).
【Keywords】: