20th IEEE International Conference on Network Protocols, ICNP 2012, Austin, TX, USA, October 30 - Nov. 2, 2012. IEEE Computer Society 【DBLP Link】
【Paper Link】 【Pages】:1-2
【Authors】: Tao Feng ; Jun Bi ; Hongyu Hu
【Abstract】: Software defined networking (SDN) has been a promising network architecture to improve the openness of network and the diversity of protocols. Network operating system (NOS) in SDN is a key component for the abstraction of infrastructure and feature-rich protocols, which provide a general control plane and a unified protocol operating view. SDN-oriented NOS design requires not only the control shift from the specific network functions and vendor-dependent implementation in a traditional control plane to a general control functions, but also the extension of abstraction from computing process in a computer operating system to forwarding operation. To address this, we present a novel network operating system-TUNOS from the view of device control capacities and network control capacities. For the purpose of scalability, robustness, flexibility and high-performance, TUNOS provides open device management, cognitive network status, global network view, virtual forwarding space, and APP context management. General network control APIs are designed for user-friendly network programming.
【Keywords】: Protocols; Process control; Scalability; Context; Operating systems; Computer architecture; Servers
【Paper Link】 【Pages】:1-2
【Authors】: Xiaoke Jiang ; Jun Bi ; You Wang ; Pingping Lin ; Zhaogeng Li
【Abstract】: In this paper, we proposal an content provider mobility solution of Named Data Networking (NDN) [1]. Here content provider means the host of NDN network which provide content originally. We add a Locator are to the Interest packet [2]. Mapping System also introduced into the network, which maps identifier to locator. The original name is used as identifier. Thus, matching lookup in Content Store (CS) and Pending Interest Table (PIT) employs identifier, while forwarding lookup in Forwarding Information Base (FIB) employs locator. In reality, Mapping System should be a DNS-like distributed system, so the record updating has time latency. It's hard to solve provider mobility when there is no explicit "where" information, that's why locator is imported in NDN, however, "where" still serves as the secondary information of the network.
【Keywords】: Locator; NDN; CCN; Mobility; Mapping System
【Paper Link】 【Pages】:1-2
【Authors】: Hyojoon Kim ; Mike Schlansker ; Jose Renato Santos ; Jean Tourrilhes ; Yoshio Turner ; Nick Feamster
【Abstract】: Software Defined Networking, or SDN, based networks are being deployed not only in testbed networks, but also in production networks. Although fault-tolerance is one of the most desirable properties in production networks, there are not much study in providing fault-tolerance to SDN-based networks. The goal of this work is to develop a fault tolerant SDN architecture that can rapidly recover from faults and scale to large network sizes. This paper presents CORONET, a SDN fault-tolerant system that recovers from multiple link failures in the data plane. We describe a prototype implementation based on NOX that demonstrates fault recovery for emulated topologies using Mininet. We also discuss possible extensions to handle control plane and controller faults.
【Keywords】: Fault tolerant systems; Fault tolerance; Network topology; Routing; Topology; Computer architecture; Production
【Paper Link】 【Pages】:1-2
【Authors】: Jie Li ; Jun Bi ; Jianping Wu
【Abstract】: The authentication of the IP source address remains one of the most important steps in making the Internet as trustworthy as possible. With existing anti-spoofing solutions, deployed ASes lack cooperation when exchanging routing decisions and disseminations. In general, this makes anti-spoofing mechanisms inefficient and does not adapt to incremental deployment. By introducing routing choice feedback, we propose a distributed inter-domain anti-spoofing solution (Umbrella). In Umbrella, the deployed ASes can acquire approximate global routing choice information. Our approach offers gains in efficiency through the verification of the packets forwarding path and the construction of dynamically spoofing packets filter. Our experimental analysis of Umbrella shows it to be both effective and incrementally deployable.
【Keywords】: Routing; Filtering; IP networks; Educational institutions; Internet; Security; Topology
【Paper Link】 【Pages】:1-6
【Authors】: Raimondas Sasnauskas ; Philipp Kaiser ; Russ Lucas Jukic ; Klaus Wehrle
【Abstract】: Automatism and high-coverage are the core challenges in testing communication protocols in their early development phase. Ideally, the testing process should cope with a large input space, several sources of non-determinism, and heterogeneous operating environments to effectively explore the emerging execution paths. In practice, however, the missing tool support imposes a huge amount of manual effort to perform integrated conformance and interoperability testing of protocol implementations. In this paper, we first detail on the protocol testing issues, such as low coverage, missing code and automation, we experienced during the lifetime of an university-industry project. Second, we present SymNet, an integrated testing environment which targets the latter limitations using state-of-the-art symbolic execution techniques. Our approach is to interconnect several virtual machines, execute each of them using selective symbolic execution, and centrally coordinate the emerging distributed execution paths. The key challenges are the synchronization of distributed constraints, detection of false positives, and pruning of redundant execution states. We detail on SymNet architecture, show its applicability to real-world protocol software, and discuss future research directions.
【Keywords】: Testing; Protocols; Concrete; Hip; Synchronization; Software; Switches
【Paper Link】 【Pages】:1-6
【Authors】: Chen Chen ; Limin Jia ; Boon Thau Loo ; Wenchao Zhou
【Abstract】: In recent years, there have been strong interests in the networking community in designing new Internet architectures that provide strong security guarantees. However, none of these proposals back their security claims by formal analysis. In this paper, we use a reduction-based approach to prove the route authenticity property in secure routing protocols. These properties require routes announced by honest nodes in the network not to be tampered with by the adversary. We focus on protocols that rely on layered signatures to provide security: each route announcement is associated with a list of signatures attesting the authenticity of its subpaths. Our approach combines manual proofs with automated analysis. We define several reduction steps to reduce proving route authenticity properties to simple conditions that can be automatically checked by the Proverif tool. We show that our analysis is correct with respect to the trace semantics of the routing protocols.
【Keywords】: Routing protocols; Security; Routing; Topology; Internet; Semantics
【Paper Link】 【Pages】:1-6
【Authors】: Sarah Edenhofer ; Peter Höfner
【Abstract】: Dynamic MANET On-demand (AODVv2) routing, formerly known as DYMO, is a routing protocol especially designed for wireless, multi hop networks. AODVv2 determines routes in a network in an on-demand fashion. In this paper we present a formal model of AODVv2, using the process algebra AWN. The benefit of this is two-fold: (a) the given specification is definitely free of ambiguities; (b) a formal and rigorous analysis of the routing protocol is now feasible. To underpin the latter point we also present a first analysis of the AODVv2 routing protocol. On the one hand we show that some of the problems discovered in the AODV routing protocol, the predecessor of AODVv2, have been addressed and solved. On the other hand we show that other limitations still exist; an example is the establishment of non-optimal routes. Even worse, we locate shortcomings in the AODVv2 routing protocol that do not occur in AODV. This yields the conclusion that AODVv2 is not necessarily better than AODV.
【Keywords】: Routing protocols; Routing; Analytical models; Ad hoc networks; Algebra; Standards
【Paper Link】 【Pages】:1-6
【Authors】: Vincent Rahli ; Nicolas Schiper ; Robbert van Renesse ; Mark Bickford ; Robert L. Constable
【Abstract】: We present a fault-tolerant ordered broadcast service that is correct-by-construction. Our broadcast service allows for diversity in space, whereby the participants in the broadcast protocol run different code, as well as in time, whereby the protocol itself is changed periodically. We use the Nuprl proof assistant to specify the service, prove correctness, and synthesize the code. The paper includes initial performance results.
【Keywords】: Protocols; Proposals; Computer crashes; Switches; Reactive power; Fault tolerance; Fault tolerant systems
【Paper Link】 【Pages】:1-6
【Authors】: Shuyuan Zhang ; Abdulrahman Mahmoud ; Sharad Malik ; Sanjai Narain
【Abstract】: Firewalls are widely deployed to safeguard the security of networks and it is critical for enterprise networks to have firewalls to prevent malicious attacks and to guarantee the normal functioning of the network. Firewalls prevent dangerous packets from entering the inner network by looking up the Access Control List (ACL) to permit or drop certain packets. However, ACLs often suffer from redundancy problems, which can degrade the performance of firewalls and the network. The contribution of this paper is threefold: 1) we present a Boolean Satisfiability (SAT) based technique that can compare the equivalence and inclusion relationship between two firewalls, which is very valuable for the testing between a given firewall and an optimized one, 2) we present a technique to discover redundancies within a firewall, and 3) we formulate the ACL optimization problem as a Quantified Boolean Formula problem (QBF) and explore its practical application using a QBF solver.
【Keywords】: Redundancy; Encoding; Reactive power; Benchmark testing; Security; Protocols; Optimization
【Paper Link】 【Pages】:1-6
【Authors】: Debbie Perouli ; Stefano Vissicchio ; Alexander J. T. Gurney ; Olaf Maennel ; Timothy G. Griffin ; Iain Phillips ; Sonia Fahmy ; Cristel Pelsser
【Abstract】: Routing stability and correctness in the Internet have long been a concern. Despite this, few theoretical frameworks have been proposed to check BGP configurations for convergence and safety. The most popular approach is based on the Stable Paths Problem (SPP) model. Unfortunately, SPP requires enumeration of all possible control-plane paths, which is infeasible in large networks. In this work, we study how to apply algebraic frameworks to the BGP configuration checking problem. We propose an extension of the Stratified Shortest Path Problem (SSPP) model that has a similar expressive power to SPP, but enables more efficient checking of configuration correctness. Our approach remains valid when BGP policies are applied to iBGP sessions - a case which is often overlooked by previous work, although common in today's Internet. While this paper focuses mainly on iBGP problems, our methodology can be extended to eBGP if operators are willing to share their local-preference configurations.
【Keywords】: Silicon
【Paper Link】 【Pages】:1-6
【Authors】: Seungwon Shin ; Guofei Gu
【Abstract】: Cloud computing is becoming a popular paradigm. Many recent new services are based on cloud environments, and a lot of people are using cloud networks. Since many diverse hosts and network configurations coexist in a cloud network, it is essential to protect each of them in the cloud network from threats. To do this, basically, we can employ existing network security devices, but applying them to a cloud network requires more considerations for its complexity, dynamism, and diversity. In this paper, we propose a new framework, CloudWatcher, which provides monitoring services for large and dynamic cloud networks. This framework automatically detours network packets to be inspected by pre-installed network security devices. In addition, all these operations can be implemented by writing a simple policy script, thus, a cloud network administrator is able to protect his cloud network easily. We have implemented the proposed framework, and evaluated it on different test network environments.
【Keywords】: Security; Monitoring; Algorithm design and analysis; Routing; Virtual machining; Cloud computing; Network topology
【Paper Link】 【Pages】:1-6
【Authors】: Gowtham Boddapati ; John Day ; Ibrahim Matta ; Lubomir T. Chitkushev
【Abstract】: The TCP/IP architecture was originally designed without taking security measures into consideration. Over the years, it has been subjected to many attacks, which has led to many patches to counter them. Our investigations into the fundamental principles of networking have shown that carefully following an abstract model of Inter-Process Communication (IPC) addresses many problems [1]. Guided by this IPC principle, we designed a clean-slate Recursive InterNetwork Architecture (RINA) [2]. In this paper, we show how, without the aid of cryptographic techniques, the bare-bones architecture of RINA can resist most of the security attacks faced by TCP/IP, and of course, is only more secure if cryptographic techniques are employed. Specifically, the RINA model decouples different concerns that makes it more resistant to transport-level attacks: (1) RINA decouples authentication from connection management, thus transport-level attacks are limited to “insider” attacks, and (2) RINA decouples transport port allocation and access control from data synchronization and transfer, thus making transport-level attacks much harder to mount. Using typical field lengths in packet headers, we analyze how hard it is for an intruder to compromise RINA.
【Keywords】: Receivers; Cryptography; Resource management
【Paper Link】 【Pages】:1-6
【Authors】: Kevin Weekly ; Kristofer S. J. Pister
【Abstract】: In this work, we present the results of a study on the detrimental effects of sinkhole attacks on Wireless Sensor Networks (WSNs) which employ the Routing Protocol for LLNs (Low-power and Lossy Networks). A sinkhole is a compromised node which attempts to capture traffic with the intent to drop messages, thus degrading the end-to-end delivery performance, that is, reducing the number of messages successfully delivered to their destination. The mechanism by which the sinkhole captures traffic is by advertising an attractive route to its neighbors. We evaluate two countermeasures addressing the sinkhole problem: a parent fail-over and a rank authentication technique. We show via simulation that while each technique, applied alone, does not work all that well, the combination of the two techniques significantly improves the performance of a network under attack. We also demonstrate that, with the defenses described, increasing the density of the network can combat a penetration of sinkholes nodes, without needing to identify the sinkholes.
【Keywords】: Routing protocols; Communication system security; Ad hoc networks
【Paper Link】 【Pages】:1-6
【Authors】: Fahad A. Arshad ; Gaspar Modelo-Howard ; Saurabh Bagchi
【Abstract】: The question of whether to migrate IT services to a cloud computing infrastructure arises before most IT decision makers today. To enable secure access to sensitive resources a virtual private network (VPN) is almost a required piece of technology. Setting up and managing a VPN server is a non-trivial task-there are a variety of modes in which VPN can be used (IPSec, SSL/TLS, PPTP), there are a variety of software-only and software-hardware solutions, and each comes with a rich set of configuration options. Therefore, it is a perplexing question to practitioners what option to choose, with an understanding of the performance and the security implications of each choice. In this paper, we consider the various factors that should go into such decision making and exemplify this by choosing among two competitive options for protecting access to IT resources of our NSF center which has a significant number of external (i.e., non-Purdue) users. The two options are an open-source software-only VPN (pfSense) and a commercial appliance, i.e., an integrated hardware-software solution. Further, the first is managed by us while the latter is outsourced to an entity that provides VPN services to multiple consumer organizations, and hence, referred by us as the cloud-based service. We follow up with conducting a post-deployment study of the VPN users which reveals that despite a two-fold reduction in throughput, the cloud-based service is considered satisfactory due to its non-intrusiveness with respect to other network activities and ease of configuration.
【Keywords】: Cloud Computing; Virtual Private Network; Security; Configurability
【Paper Link】 【Pages】:1-6
【Authors】: Ruidong Li ; Ved P. Kafle ; Hiroaki Harai
【Abstract】: The ID/locator split-based approach has been widely recognized as a promising approach for the design of future networks. However, the existing ID/locator split architectures are still vulnerable to various attacks, such as impersonation attacks and man-in-the-middle attacks. They cannot be simply protected by the existing security mechanisms, which have the limitations especially on scalability. To solve these problems, we propose a proactive scheme for securing ID/locator split architecture, which embeds built-in security features to enable proactive protections of the architecture. Through this scheme, hosts register their information to the network securely, obtain trustworthy information of destination hosts, authenticate each other, and securely update their locators without requiring an involvement of a trusted third party (TTP). Compared to other existing security mechanisms, the proposed scheme does not require additional authentication mechanism and it can provide the thorough protections of the whole architecture.
【Keywords】: authentication; Future Network; ID/Locator split architecture; security
【Paper Link】 【Pages】:1-6
【Authors】: Mohammad Ehdaie ; Nikolaos Alexiou ; Mahmoud Ahmadian-Attari ; Mohammad Reza Aref ; Panos Papadimitratos
【Abstract】: A large number of Wireless Sensor Network (WSN) security schemes have been proposed in the literature, relying primarily on symmetric key cryptography. To enable those, Random Key pre-Distribution (RKD) systems have been widely accepted. However, WSN nodes are vulnerable to physical compromise. Capturing one or more nodes operating with RKD would give the adversary keys to compromise communication of other benign nodes. Thus the challenge is to enhance resilience of WSN to node capture, while maintaining the flexibility and low-cost features of RKD. We address this problem, without any special-purpose hardware, proposing a new and simple idea: key splitting. Our scheme does not increase per-node storage, and computation and communication overheads, and it can increase connectivity. More important, it achieves a significant increase in resilience to compromise compared to the state of the art, notably when the adversary does not have overwhelming computational power.
【Keywords】: Peer to peer computing; Wireless sensor networks; Sensors; Resilience; Security; Protocols; Probability
【Paper Link】 【Pages】:1-2
【Authors】: Pingping Lin ; Jun Bi ; Hongyu Hu
【Abstract】: Software Defined Networking (SDN) is considered as a promising method to re-construct the architecture of Internet. At present, the programs of network protocols are mixed together in SDN controller. However, in the production network, an isolated network environment with private resources is needed for each network protocol running on the same SDN controller. It is therefore necessary to design a practical virtualization cloud platform on the SDN network operating system (NOS). In this paper, we introduce a virtualization cloud platform for SDN production network. A prototype is implemented and two cases are performed to show the feasibility and the effectiveness of our proposed framework.
【Keywords】: Virtualization Cloud Platform; Software Defined Networking
【Paper Link】 【Pages】:1-2
【Authors】: Shou-pon Lin ; Nicholas F. Maxemchuk
【Abstract】: Vehicle automation has progressed from systems that monitor the operation of a vehicle and assist a driver, with functions such as antilock braking and cruise control, to systems that detect the operation of adjacent vehicles, to implement emergency braking and intelligent cruise control. The next generation of systems will share sensor readings and collaborate to control braking operations by looking several cars ahead or by creating safe gaps for merging vehicles. The rules that control the interaction between automobiles are protocols.
【Keywords】: Protocols; Collaboration; Automobiles; Merging; Computer architecture; Hardware
【Paper Link】 【Pages】:1-2
【Authors】: Debbie Perouli ; Timothy G. Griffin ; Olaf Maennel ; Sonia Fahmy ; Iain Phillips ; Cristel Pelsser
【Abstract】: Internet Service Providers (ISPs) use routing policies to implement the requirements of business contracts, manage traffic, address security concerns and increase scalability of their network. These routing policies are often a high-level expression of strategies or intentions of the ISP. They have meaning when viewed from a network-wide perspective (e.g., mark on ingress, filter on egress). However, configuring these policies for the Border Gateway Protocol (BGP) is undertaken at a low-level, on a per router basis. Unintended routing outcomes have been observed. In this work, we define a language that allows analysis of network-wide configurations at the high-level. This language aims at bridging the gap between router configurations and abstract mathematical models capable of capturing complex policies. The language can be used to verify desired properties of routing protocols and hence detect potential unintended states of BGP. The language is accompanied by a tool suite that parses router configuration languages (which by their nature are vendor-dependent) and translates them into vendor-independent representations of policies.
【Keywords】: Routing protocols; Internet; Educational institutions; Routing; Communities; Vegetation; Computer science
【Paper Link】 【Pages】:1-2
【Authors】: Wenyu Ren ; Yong Li ; Depeng Jin ; Li Su ; Lieguang Zeng
【Abstract】: Vehicular Delay Tolerant Networks (VDTN) are used to distribute a large amount of mobile data by high-capacity device-to-device communication. Given a number of available vehicles in VDTN, the current vehicular data sharing models always utilize all of them to achieve the best effect, failing to balance the performance gained and cost of employing them. Taking the cost into account, we study the problem of the optimal number of vehicles to be deployed in the data sharing system, which considers using erasure codes to further increase the system efficiency if possible. By establishing the system goal which consists both the effectiveness and the cost of the vehicular network mathematically, we formulate the above problem as a utility function minimization problem. Finally, we solve the problem by theoretical derivation, and demonstrate the efficiency of the obtained solution through simulations using real vehicular traces of Beijing and Shanghai.
【Keywords】: Vehicles; Encoding; Mobile communication; Mobile computing; Delay; Minimization; Exponential distribution
【Paper Link】 【Pages】:1-2
【Authors】: You Wang ; Jun Bi ; Chenghui Peng
【Abstract】: Resolution from identifiers to locators serves as a key component of mapping-based mobility solutions. In this paper we address the weakness of current resolution methods in supporting diverse mobility scenarios and propose a Global Resolution Service offered by Resolution Service Providers. We present a preliminary design and simulation, and results show that our approach is able to provide better resolution service compared to existing solutions in terms of performance.
【Keywords】: overlay; Mobility; identifier; resolution
【Paper Link】 【Pages】:1-2
【Authors】: Tong Yang ; Shenjiang Zhang ; Xianda Sun ; Huichen Dai ; Ruian Duan ; Jianyuan Lu ; Zhian Mi ; Bin Liu
【Abstract】: Virtual router research has drawn increasing attention in recent years, and the most challenging issues of virtual routers are compression, lookup, and incremental update of 10~200 routing tables. In this paper, we propose a set of solutions to achieve that storage, lookup time, and update time don't expand to 10~200 times, but reduce to 1~2 times.
【Keywords】: Routing; Arrays; Random access memory; Field programmable gate arrays; Polymers; Routing protocols; Hardware
【Paper Link】 【Pages】:1-2
【Authors】: Baobao Zhang ; Jun Bi ; Jianping Wu
【Abstract】: In this work, we devise an aggregation method based on overlapped path tunnel. This aggregation method can be used to adjust the maximum number of forwarding entries to an acceptable value. In this work, we show the effectiveness of the aggregation method using a manual way. In the future, we will study the automatic way of establishing tunnels to limit the maximum number of entries to an acceptable value.
【Keywords】: MPLS; Aggregation; Forwarding Table
【Paper Link】 【Pages】:1-10
【Authors】: Tao Xiong ; Jin Zhang ; Junmei Yao ; Wei Lou
【Abstract】: Hidden terminals are typical interference sources that can significantly reduce the throughput of a wireless network if it adopts the CSMA/CA MAC protocol. The RTS/CTS mechanism is a well-known solution to this hidden terminal problem. However, it only works well under the assumption that all hidden terminals can decode the CTS packets correctly. In the real world, the CTS packets might not be correctly received all the time due to either the CTS packets are unable to be decoded at remote hidden terminals or the CTS packets are collided with other packets at the hidden terminals. Both of these drawbacks can make the standard RTS/CTS mechanism fail to silence all hidden terminals, and deteriorate the throughput of the wireless network. In this paper, we present the RTS/S-CTS mechanism, a novel symbol-level detection mechanism that combats these two drawbacks. The RTS/S-CTS frames make slight changes to the standard RTS/CTS frames, and can be compatible with the standard 802.11 MAC layer. We design the symbol-level detection decoder (SLDD) and NAV decision algorithm that enable the S-CTS frame to be correctly detected from collisions and by remote hidden terminals. We build a testbed of RTS/S-CTS with GNURadio/USRP2 software radio to demonstrate its feasibility and run ns-2 simulations to evaluate its performance. The results show that the RTS/S-CTS can achieve up to 63% throughput improvement in the random topology network scenario compared with the standard RTS/CTS.
【Keywords】: wireless networks; Cross-layer design; hidden terminal problem; RTS/CTS; signal correlation and detection
【Paper Link】 【Pages】:1-12
【Authors】: Matvey Arye ; Erik Nordström ; Robert Kiefer ; Jennifer Rexford ; Michael J. Freedman
【Abstract】: Modern consumer devices, like smartphones and tablets, have multiple interfaces (e.g., WiFi and 4G) that attach to new access points as users move. These mobile, multi-homed computers are a poor match with an Internet architecture that binds connections to fixed endpoints with topology-dependent addresses. As a result, hosts typically cannot spread a connection over multiple interfaces or paths, or change locations without breaking existing connections. In this paper, we create an end-to-end connection control protocol (ECCP) that allows hosts to communicate over multiple interfaces with dynamically-changing IP addresses and works with multiple data-delivery protocols (i.e., reliable or unreliable transport). Each ECCP connection consists of one or more flows, each associated with an interface or path. Through end-to-end signaling, a host can move an existing flow from one interface to another, or change its IP address, without any support from the underlying network. We develop formal models to verify that ECCP works correctly in the presence of packet loss, out-of-order delivery, and frequent mobility, and to identify bugs and design limitations in earlier mobility protocols.
【Keywords】: formal methods; migration; mobile devices; network architecture; end-to-end signaling
【Paper Link】 【Pages】:1-10
【Authors】: Jun Li ; Toby Ehrenkranz ; Paul Elliott
【Abstract】: Due to operational malpractice or security attacks, an IP prefix (i.e., a block of IP addresses) can undergo many types of routing anomalies. Perhaps the most well-known of such anomalies is prefix hijacking, where an attacker hijacks traffic meant to reach the legitimate user of a prefix. Anomalies can also easily occur through route leaks, which can disrupt traffic for numerous prefixes at once. While various solutions have been proposed to detect such anomalies, these solutions are limited and susceptible to attacker countermeasures. In this paper we present Buddyguard, a new approach to detecting prefix anomalies including prefix hijacking and route leaks. Buddyguard compares the behavior of a monitored prefix with the behavior of a set of numerous buddy prefixes. The system detects anomalies when the behavior of the monitored prefix significantly diverges from that of its buddies. Our evaluation results show that Buddyguard provides fast, accurate and lightweight monitoring of IP prefix anomalies, and its introduction and use of buddy prefixes enables it to be resilient against resourceful attackers.
【Keywords】: IP networks; Monitoring
【Paper Link】 【Pages】:1-10
【Authors】: Yipeng Wang ; Xiao-chun Yun ; Muhammad Zubair Shafiq ; Liyan Wang ; Alex X. Liu ; Zhibin Zhang ; Danfeng Yao ; Yongzheng Zhang ; Li Guo
【Abstract】: Extracting the protocol message format specifications of unknown applications from network traces is important for a variety of applications such as application protocol parsing, vulnerability discovery, and system integration. In this paper, we propose ProDecoder, a network trace based protocol message format inference system that exploits the semantics of protocol messages without the executable code of application protocols. ProDecoder is based on the key insight that the n-grams of protocol traces exhibit highly skewed frequency distribution that can be leveraged for accurate protocol message format inference. In ProDecoder, we first discover the latent relationship among n-grams by first grouping protocol messages with the same semantics and then inferring message formats by keyword based clustering and cluster sequence alignment. We implemented and evaluated ProDecoder to infer message format specifications of SMB (a binary protocol) and SMTP (a textual protocol). Our experimental results show that ProDecoder accurately parses and infers SMB protocol with 100% precision and recall. For SMTP, ProDecoder achieves approximately 95% precision and recall.
【Keywords】: Protocols; Postal services; Semantics; Reverse engineering; Electronic mail; Natural language processing; Vectors
【Paper Link】 【Pages】:1-10
【Authors】: Suchul Lee ; Chong-kwon Kim
【Abstract】: To exploit frequency diversity in Wi-Fi channels, instantaneous channel quality must be estimated. However, there is a trade-off between acquiring channel quality information and improving protocol efficiency because channel estimation consumes time and frequency resource that ideally should be used for data transfer. In this paper, we present D-Fi (Diversity-aware Wi-Fi), a novel Wi-Fi PHY/MAC protocol, that capitalizes on frequency diversity gains while sustaining protocol efficiency. The D-Fi design allows to estimate channel quality while D-Fi is performing channel contention using an OFDM-based Bloom filter. To resolve the ambiguity caused by the Bloom filter, we adopt two methods: (i) An analysis-based multi channel backoff method enables to explore/exploit frequency diversity while reducing the occurrence of the ambiguity. (ii) Applying machine learning (ML) methods to the D-Fi PHY/MAC protocol corrects the ambiguity taken place already and makes our protocol reliable. We have shown the feasibility of D-Fi by implementing it on the USRP/GNURadio platform. Experiments and trace-driven simulations show that D-Fi successfully achieves frequency diversity gains without losing improved protocol efficiency.
【Keywords】: Media Access Protocol; Channel estimation; Estimation; OFDM; Frequency estimation; Time frequency analysis
【Paper Link】 【Pages】:1-11
【Authors】: Somaya Arianfar ; Pasi Sarolahti ; Jörg Ott
【Abstract】: TCP and other Internet transport protocols rely on series of hard-coded initial values for their connection state, particularly for the congestion control parameters. For example, recently the initial value of congestion window has been under much debate, as there is a desire to make TCP more efficient for common use cases, while not endangering its performance on scenarios with limited network bandwidth. Our take on this discussion is that there is no clear single set of initial values that would work for all cases. Earlier research has proposed sharing connection and congestion control state among multiple connections over time, but that approach is limited to sharing connections to a particular host, which is not sufficient, because services are often distributed across multiple hosts, and opening multiple connections to the same host is a rather rare use case. We aim to solve this problem by proposing the Pathlet Transport Architecture that models the network paths as a series of pathlets, and uses those as the basis of initializing and maintaining the various transport parameters, particularly those related to congestion control. We analyze our initial instantiation of the PTA architecture using ns-3 simulations for TCP congestion control parameters, and show how it improves the communication performance in various different network scenarios, where single common set of magic values would fail.
【Keywords】: Receivers; IP networks; Wireless communication; Standards; Routing protocols; Sockets
【Paper Link】 【Pages】:1-11
【Authors】: Yuan Feng ; Baochun Li ; Bo Li
【Abstract】: It is typical for enterprises to rely on services from cloud providers in order to build a scalable platform with abundant available resources to satisfy user demand, and for cloud providers to deploy a number of datacenters inter-connected with high-capacity links, across different geographical regions. In this paper, we propose that video conferencing, even with its stringent delay constraints, should also be provided as a cloud service, taking full advantage of the inter-datacenter network in the cloud. We design Airlift, a new protocol designed for the inter-datacenter network, tailored to the needs of a cloud-based video conferencing service. Airlift delivers packets in live video conferences to their respective destination datacenters, with the objective of maximizing the total throughput across all conferences, yet without violating end-to-end delay constraints. In order to simplify our protocol design in Airlift, we use intra-session network coding and the concept of conceptual flows, such that the optimization problem that can be conveniently formulated as a linear program. Our real-world implementation of Airlift has been deployed over the Amazon EC2 cloud. We show that Airlift delivers a substantial performance advantage over state-of-the-art peer-to-peer solutions.
【Keywords】: Delay; Throughput; Network coding; Protocols; Silicon; Steiner trees; Peer to peer computing
【Paper Link】 【Pages】:1-9
【Authors】: Michael Schier ; Michael Welzl
【Abstract】: The Datagram Congestion Control Protocol (DCCP) is no longer too young to be usable: the first RFCs were published in 2006, and a stable and quite complete Linux implementation exists. DCCP over UDP has also recently been specified to address network traversal problems. But how good is the service provided to applications by this protocol? This paper identifies some deficiencies of the current implementation - the lack of transparency in the API with regard to packet loss, the coarse granularity of the lookup table used to calculate the TFRC equation, and the lack of history discounting in CCID-3 - and demonstrates that they can significantly impair the performance of typical DCCP use cases such as live video streaming. Solutions are proposed to tackle all these problems, and it is shown that they considerably improve the performance and the flexibility of applications.
【Keywords】: Bit rate; Linux; History; Loss measurement; Equations; Kernel; Vectors
【Paper Link】 【Pages】:1-10
【Authors】: Behnaz Arzani ; Roch Guérin ; Alejandro Ribeiro
【Abstract】: Wireless mesh networks hold the promise of rapid and flexible deployments of communication facilities. This potential notwithstanding, the often erratic behavior of multihop wireless transmissions is limiting the range of applications that such networks can target. In this paper we investigate the feasibility and benefits of a routing protocol explicitly aimed at making wireless mesh networks more predictable while preserving their efficiency and flexibility. The protocol's basic premise is the classical idea that a multipath solution can offer resiliency to unexpected link variations. The paper's contributions are in demonstrating how this can be effectively realized in a wireless context, and in offering initial evidences of its efficacy. In particular, the paper illustrates how routing decisions that account for link variability can be computed in a distributed fashion, and the benefits they afford in improving the stability of end-to-end transmission rates even in the presence of random network fluctuations.
【Keywords】: Protocols; Reliability
【Paper Link】 【Pages】:1-9
【Authors】: Shaojie Tang ; Jie Wu ; Guihai Chen ; Cheng Wang ; Xuefeng Liu ; Tao Li ; Xiang-Yang Li
【Abstract】: To ensure sustainable operations of wireless sensor networks, environmental energy harvesting has been well recognized as one promising solution for long-term applications. Unlike in battery-powered sensor networks, we are targeting a duty-cycle adjustment to optimize the network performance, e.g., delay minimization, with full harvested energy utilization. In this paper, we introduce a set of duty-cycle adjustment schemes that will minimize cross traffic delay (CTD) in energy-harvesting sensor networks. We first present an offline solution by assuming that the link reliability and traffic distribution are known a priori. Based on the submodular property of the CTD function, we theoretically prove that a simple greedy algorithm can achieve constant approximation. We next propose a class of online algorithms that do not require the knowledge of link reliability and traffic distribution. For each of these algorithms, we give a theoretical bound on the performance. We have evaluated our design with a TelosB-based implementation and experimental results corroborate our theoretical analysis.
【Keywords】: submodular; Wireless sensor networks; solar powered; duty-cycle
【Paper Link】 【Pages】:1-10
【Authors】: Sohraab Soltani ; Hassan Aqeel Khan ; Hayder Radha
【Abstract】: This paper presents the design of a new paradigm for a content-aware wireless MAC layer that is optimized for wireless video (first and foremost) while targeting fairness and stability among competing video traffic, and among video and non-video traffic. Hence, we refer to the proposed MAC framework as the FAST (Fair And STable) protocol. FAST employs two parameters for each packet, a quality value and a time-to-live value. Based on these parameters, FAST is designed on a multiclass priority queuing system that classifies the incoming traffic according to the content of each traffic flow and further identifies different priorities within each video content. We develop analytical frameworks to formulate channel allocation based on video/non-video fairness and video stability requirements as a joint bandwidth maximization and scheduling optimization problem. We incorporate these frameworks to design and simulate a content-aware channel access mechanism, which utilizes video traffic content classifications and users demand in conjunction with stability and fairness requirements at the MAC layer to allocate wireless channels to individual wireless users. Our simulation results show that FAST provides significant improvements in packet-loss-ratio, delay, overall fairness, and stability parameters when compared with leading access control mechanisms over 4G/LTE environment.
【Keywords】: Servers
【Paper Link】 【Pages】:1-10
【Authors】: George Papageorgiou ; Shailendra Singh ; Srikanth V. Krishnamurthy ; Ramesh Govindan ; Tom La Porta
【Abstract】: Traditional routing metrics designed for wireless networks are application agnostic. In this paper, we consider a wireless network where the application flows consist of video traffic. From a user-perspective, reducing the level of video distortion is critical. We ask the question “Should the routing policies change if the end-to-end video distortion is to be minimized?” Popular link-quality based routing metrics (such as ETX) do not account for dependence (in terms of congestion) across the links of a path; as a result, they can cause video flows to converge onto a few paths and thus, cause high video distortion. To account for the evolution of the video frame loss process we construct an analytical framework to first, understand and second, assess the impact of the wireless network on video distortion. The framework allows us to formulate a routing policy for minimizing distortion, based on which we design a protocol for routing video traffic. We find via simulations and testbed experiments that our protocol is efficient in reducing video distortion and minimizing the user experience degradation. Specifically, our protocol reduces the distortion by 20% over traditional methods, which significantly improves the video quality perceived by a user.
【Keywords】: Packet loss; Routing; Computational modeling; Mathematical model; Streaming media
【Paper Link】 【Pages】:1-10
【Authors】: Jianxia Ning ; Shailendra Singh ; Konstantinos Pelechrinis ; Bin Liu ; Srikanth V. Krishnamurthy ; Ramesh Govindan
【Abstract】: Due to the lossy nature of wireless links, it is difficult to determine if packet losses are due to wireless-induced effects or from malicious discarding. Many prior efforts on detecting malicious packet drops rely on evidence collected via passive monitoring by neighbor nodes; however, they do not analyze the cause of packet losses. In this paper, we ask: (a) Given certain macroscopic parameters of the network (like traffic intensity and node density) what is the likelihood that evidence exists with respect to a transmission? and, (b) How can these parameters be used to perform a forensic analysis of the reason for the losses? Towards answering the above questions, we first build an analytical framework that computes the likelihood that evidence (we call this transmission evidence or TE for short) exists with respect to transmissions, in terms of a set of network parameters. We validate our analytical framework via both simulations as well as real-world experiments on two different wireless testbeds. The analytical framework is then used as a basis for a protocol within a forensic analyzer to assess the cause of packet losses and determine the likelihood of forwarding misbehaviors. Through simulations, we find that our assessments are close to the ground truth in all examined cases, with an average deviation of 2.3% from the ground truth and a worst case deviation of 15.0%.
【Keywords】: Availability; Forensics; Interference; Receivers; Packet loss; Transmitters
【Paper Link】 【Pages】:1-10
【Authors】: Lei Yu ; Karan Sapra ; Haiying Shen ; Lin Ye
【Abstract】: The pay-as-you-go service model impels cloud customers to reduce the usage cost of bandwidth. Traffic Redundancy Elimination (TRE) has been shown to be an effective solution for reducing bandwidth costs, and has recently captured significant attention in the cloud environment. By studying the TRE techniques with a trace driven approach, we found that solely using either sender-based TRE or receiver-based TRE cannot simultaneously capture traffic redundancy in both short-term (time span of seconds) and long-term (time span of hours or days) data redundancy, which concurrently appear in the traffic. Additionally, the TRE efficiency of existing receiver-based TRE solution is susceptible to data changes compared to historical data in the cache. In this paper, we propose a sender and receiver Cooperative end-to-end TRE solution (CoRE) for efficiently identifying and removing both short-term and long-term redundancy. Through a two-layer redundancy detection design and one single pass algorithm for chunking and fingerprinting, CoRE efficiently carries out cooperative operations between the sender and the receiver. By extensive evaluation with several real traces, we show that CoRE is able to identify both short-term and longterm redundancy with low additional cost, while ensuring TRE efficiency from data changes.
【Keywords】: Receivers; Switches
【Paper Link】 【Pages】:1-10
【Authors】: Debbie Perouli ; Timothy G. Griffin ; Olaf Maennel ; Sonia Fahmy ; Cristel Pelsser ; Alexander J. T. Gurney ; Iain Phillips
【Abstract】: Internet Service Providers (ISPs) need to balance multiple opposing objectives. On one hand, they strive to offer innovative services to obtain competitive advantages; on the other, they have to interconnect with potentially competing ISPs to achieve reachability, and coordinate with them for certain services. The complexity of balancing these objectives is reflected in the diversity of policies of the Border Gateway Protocol (BGP), the standard inter-domain routing protocol. Unforeseen interactions among the BGP policies of different ISPs can cause routing anomalies. In this work, we propose a methodology to allow ISPs to check their BGP policy configurations for guaranteed convergence to a single stable state. This requires that a set of ISPs share their configurations with each other, or with a trusted third party. Compared to previous approaches to BGP safety, we (1) allow ISPs to use a richer set of policies, (2) do not modify the BGP protocol itself, and (3) detect not only instability, but also multiple stable states. Our methodology is based on the extension of current theoretical frameworks to relax their constraints and use incomplete data. We believe that this provides a rigorous foundation for the design and implementation of safety checking tools.
【Keywords】: Routing; Safety; Peer to peer computing; Guidelines; Electronic mail; Internet; Protocols
【Paper Link】 【Pages】:1-10
【Authors】: Le Chang ; Jianping Pan
【Abstract】: In this paper, we propose a modeling framework to capture the major characteristics of peer-assisted video ondemand systems offering standard and high-definition channels. Our framework can be extended to model a variety of caching strategies, including FIFO, passive caching, and active caching. We use the framework to prove that passive caching is sufficiently effective for stationary user behaviors, and generate the optimal caching solutions when the channels in the system demonstrate different popularity evolutions, i.e., with non-stationary behaviors. Simulation results verify the efficacy of our active-caching strategy and provide further insights into such systems that are gaining more popularity over the Internet.
【Keywords】: caching strategy; Peer-to-peer; video on-demand (VoD); view-upload decoupling (VUD); bandwidth allocation
【Paper Link】 【Pages】:1-10
【Authors】: Yin Xu ; Wai Kay Leong ; Ben Leong ; Ali Razeen
【Abstract】: We show that the performance of downloads in a 3G/HSPA mobile network can be significantly degraded by a concurrent upload that saturates the uplink buffer on the mobile device. In particular, we found in some instances that download speeds can be reduced by over an order of magnitude from 2,000 kbps to 100 kbps. To mitigate this problem, we propose a new algorithm called Receiver-side Flow Control (RSFC) that regulates the uplink buffer on 3G/HSPA data senders. It uses a feedback loop to monitor the available upload capacity and dynamically adjusts the TCP receiver window (rwnd) accordingly. We evaluated RSFC on the 3G/HSPA networks of three different mobile ISPs and show that for one of them, RSFC can improve the download throughput from less than 400 kbps to up to 1,400 kbps. In the presence of a concurrent upload, RSFC can also reduce website load times from more than 2 minutes to less than 1 minute 90% of the time. Our technique is compatible with existing TCP implementations and can easily be deployed at 3G web proxies without requiring any modification to existing mobile devices.
【Keywords】: Uplink; Delay; Mobile communication; Receivers; Throughput; Downlink; Servers
【Paper Link】 【Pages】:1-10
【Authors】: Hanhua Chen ; Hai Jin ; Ning Jin ; Tao Gu
【Abstract】: Efficiently operating on relevant data for users in large-scale online social network (OSN) systems is a challenging problem. Storage systems used by popular OSN systems often rely on key-value stores, where randomly partitioning the data of users among servers across the data centers is the defacto standard. Although by using DHTs, the random partition scheme is highly scalable for hosting a large number of users, it leads to costly inter-server communications across data centers due to the complexity of interconnection and interaction between OSN users. In this paper, we explore how to reduce the inter-server communications by retaining the simple and robust nature of OSNs. We propose a data placement solution atop OSN systems to divide users among servers according to the interaction-locality-based structure. Our approach exploits a simple, yet powerful principle of OSN interactions, self-similarity, which reveals that the inter-server communication cost is minimized under such intrinsic structure. Our algorithm avoids a significant amount of inter-server traffic as well as achieves load balance among servers across the data centers. We demonstrate the existence of self-similarity in large-scale Facebook traces including 10 million Facebook users and 24 million interaction events. We conduct comprehensive trace-driven simulations to evaluate this design exploiting the unique feature of self-similarity. Results show that our scheme significantly reduces the traffic and latency of the existing schemes.
【Keywords】: online social networks; Self-similarity; interaction graph; inter-server communications; data center
【Paper Link】 【Pages】:1-10
【Authors】: Yu Cao ; Mingwei Xu ; Xiaoming Fu
【Abstract】: With the aid of multipath transport protocols, a multihomed host can shift some of its traffic from more congested paths to less congested ones, thus compensating for lost bandwidth on some paths by moderately increasing transmission rates on other ones. However, existing multipath proposals achieve only coarse-grained load balancing due to a rough estimate of network congestion using packet losses. This paper formulates the problem of multipath congestion control and proposes an approximate iterative algorithm to solve it. We prove that a fair and efficient traffic shifting implies that every flow strives to equalize the extent of congestion that it perceives on all its available paths.We call this result “Congestion Equality Principle”. By instantiating the approximate iterative algorithm, we develop weighted Vegas (wVegas), a delay-based algorithm for multipath congestion control, which uses packet queuing delay as congestion signals, thus achieving fine-grained load balancing. Our simulations show that, compared with loss-based algorithms, wVegas is more sensitive to changes of network congestion and thus achieves more timely traffic shifting and quicker convergence. Additionally, as it occupies fewer link buffers, wVegas rarely causes packet losses and shows better intra-protocol fairness.
【Keywords】: Robustness
【Paper Link】 【Pages】:1-10
【Authors】: Chen Qian ; Simon S. Lam
【Abstract】: We present the architecture and protocols of ROME, a layer-2 network designed to be backwards compatible with Ethernet and scalable to tens of thousands of switches and millions of end hosts. ROME is based upon a recently developed geographic routing protocol, greedy distance vector (GDV). Switches in ROME do not need any location information. Protocol design innovations in ROME include a stateless multicast protocol, a Delaunay DHT, as well as routing and host discovery protocols for a hierarchical network. ROME protocols do not use broadcast. Extensive experimental results from a packet-level event-driven simulator, in which ROME protocols are implemented in detail, show that ROME protocols are efficient and scalable to metropolitan size. Furthermore, ROME protocols are highly resilient to network dynamics. The routing latency of ROME is only slightly higher than shortest-path latency. To demonstrate scalability, we provide simulation performance results for ROME networks with up to 25,000 switches and 1.25 million hosts.
【Keywords】: Routing; Receivers; IP networks; Routing protocols; Servers; Unicast
【Paper Link】 【Pages】:1-10
【Authors】: Bo Han ; Aravind Srinivasan
【Abstract】: In this paper, we propose an energy efficient device discovery protocol, eDiscovery, as the first step to bootstrapping opportunistic communications for smartphones, the most popular mobile devices. We chose Bluetooth over WiFi as the underlying wireless technology of device discovery, based on our measurement study of their energy consumption on smartphones. eDiscovery adaptively changes the duration and interval of Bluetooth inquiry in dynamic environments, by leveraging history information of discovered peers. We implement a prototype of eDiscovery on Nokia N900 smartphones and evaluate its performance in three different environments. To the best of our knowledge, we are the first to conduct extensive performance evaluation of Bluetooth device discovery in the wild. Our experimental results demonstrate that compared with a scheme with constant inquiry duration and interval, eDiscovery can save around 44% energy at the expense of discovering only about 21% less peers. The results also show that eDiscovery performs better than other existing schemes, by discovering more peers and consuming less energy.
【Keywords】: Bluetooth; Device discovery; opportunistic communications; energy efficiency; smartphones
【Paper Link】 【Pages】:1-10
【Authors】: Yong Fu ; Mo Sha ; Gregory Hackmann ; Chenyang Lu
【Abstract】: Transmission power control (TPC) has the potential to reduce power consumption in Wireless Sensor Networks (WSNs). However, despite a multitude of existing protocols, they still face significant challenges in real-world deployments. A practical TPC protocol must be robust against complex and dynamic wireless properties, and efficient for resource-constrained sensors. This paper presents P-TPC, a practical TPC protocol designed on control-theoretic techniques. P-TPC features a highly efficient controller designed on a dynamic model that combines a theoretical link model with online parameter estimation. P-TPC's robustness and energy savings are demonstrated through trace-driven simulations and real-world experiments in a campus building and residential environments.
【Keywords】: Wireless sensor networks; Protocols; Receivers
【Paper Link】 【Pages】:1-10
【Authors】: Kang Chen ; Haiying Shen
【Abstract】: Previous Delay Tolerant Network (DTN) routing algorithms exploit either past encounter records (probabilistic routing) or social network properties (social network based routing) to derive a node's probability of delivering packets to their destinations. However, they only have a local view of the network, which limits the routing efficiency. Also, when two nodes meet, they have to exchange the delivery probabilities to the destinations of all packets in the two nodes, which incurs high resource consumption. In a social network, the people a person frequently meets are usually stable, which makes them play a more important role in forwarding message for the person. Based on this, we propose a lightweight distributed Social MAp based Routing algorithm in delay Tolerant networks (SMART). In SMART, each node builds its own social map consisting of nodes it has met and their frequently encountered nodes in a distributed manner. Based on both encountering frequency and social closeness of the two linked nodes in the social map, we decide the weight of each link to reflect the packet delivery probability between the two nodes. The social map enables more accurate forwarder selection through a broader view. Moreover, nodes exchange much less information for social map update and need fewer updates due to social map stability, which reduces resource consumption. Trace-driven experiments and tests on the GENI ORBIT testbed demonstrate the high efficiency of SMART in comparison with previous algorithms.
【Keywords】: Routing; Relays; Social network services; Probability; Probabilistic logic; Joining processes; Delay
【Paper Link】 【Pages】:1-10
【Authors】: Ze Li ; Haiying Shen
【Abstract】: A peer-to-peer (P2P) file sharing system provides a platform that enables users to share their files. Retrieving files efficiently and trustworthily in such a large and jumbled system is critically important. However, the issues of efficient searching and trustworthy searching have only been studied separately. Simply combining two separate strategies dealing with each issue doubles system overhead. In this paper, we first study trace data from Facebook and BitTorrent. Guided by the study observations, we propose a P2P system based on social networks for simultaneous efficient and trustworthy file sharing, namely Social-P2P. Social-P2P groups common-multi-interest nodes into a cluster and further connects socially close nodes within a cluster. The comparably stable nodes in each cluster form a DHT for inter-cluster file searching. A file query is forwarded to the cluster of the file by the DHT routing and then is forwarded along constructed connections within a cluster, which achieves high hit rate and reliable routing. Sharing files among socially close friends discourages nodes from providing faulty files since people are unlikely to risk their reputation in the real world. Experimental results show that by leveraging a social network, Social-P2P achieves highly efficient and trustworthy file sharing.
【Keywords】: Peer to peer computing; Vectors; Facebook; Servers; Routing; Maintenance engineering
【Paper Link】 【Pages】:1-10
【Authors】: Tong Yang ; Zhian Mi ; Ruian Duan ; Xiaoyu Guo ; Jianyuan Lu ; Shenjiang Zhang ; Xianda Sun ; Bin Liu
【Abstract】: With the rapid growth of the Internet, the update messages in backbone routers become more and more frequent due to the ever-increasing dynamic changes on network topologies and new emerging functionalities of the Internet. In addition, update messages often come as a burst. Update action interrupts the packet lookup operation in the router's data plane, thus inefficient incremental update algorithm slows down IP lookup speed, and potentially badly degrades the system performance during bursty updates. Among trie-based routing lookup algorithms, binary trie has the best update complexity O(W) (W is the maximum depth of the trie), but exhibits slow lookup speed, failing to be competent for forwarding tens of gigabit-per-second traffic in backbone routers. Therefore, various improved routing lookup algorithms are proposed to pursue high speed based on binary trie, but sacrificing the performance of incremental update. To minimize the interruption time that update operation incurs, we propose Blind Spot (BS) algorithm by picking out those updating nodes which would have produced domino effect, achieving an update complexity of O(lookup+h), meanwhile keeping the lookup speed almost unchanged. Blind Spot algorithm is a universal methodology, which is applicable to all the trie-based lookup algorithms. To evaluate the performance of BS algorithm, we applied it to Lulea [1] and LC-trie [2] algorithms as two representatives. Extensive experimental results show that both Lulea+BS and LC+BS algorithms achieve a much faster update speed than binary trie, while keeping the same lookup speed as the original Lulea and LC-trie algorithms.
【Keywords】: Routing; Algorithm design and analysis; Complexity theory; Filtering algorithms; Visualization; Hardware; Random access memory
【Paper Link】 【Pages】:1-10
【Authors】: Qinghua Li ; Guohong Cao
【Abstract】: The proliferation and ever-increasing capabilities of mobile devices such as smart phones give rise to a variety of mobile sensing applications. This paper studies how an untrusted aggregator in mobile sensing can periodically obtain desired statistics over the data contributed by multiple mobile users, without compromising the privacy of each user. Although there are some existing works in this area, they either require bidirectional communications between the aggregator and mobile users in every aggregation period, or has high computation overhead and cannot support large plaintext spaces. Also, they do not consider the Min aggregate which is quite useful in mobile sensing. To address these problems, we propose an efficient protocol to obtain the Sum aggregate, which employs an additive homomorphic encryption and a novel key management technique to support large plaintext space. We also extend the sum aggregation protocol to obtain the Min aggregate of time-series data. Evaluations show that our protocols are orders of magnitude faster than existing solutions.
【Keywords】: Encryption; Aggregates; Mobile communication; Sensors; Protocols; Equations
【Paper Link】 【Pages】:1-10
【Authors】: Jing Zhu ; Dan Li ; Jianping Wu ; Hongnan Liu ; Ying Zhang ; Jingcheng Zhang
【Abstract】: To efficiently utilize their infrastructure and thus increase their revenue, cloud providers need mechanisms to provide resource allocation and performance isolation for different tenants in the shared platform. In particular, network bandwidth sharing is a critical yet still an open problem to most cloud providers. In this paper, we study the problem of virtual machine (VM) allocation under the consideration of providing bandwidth guarantees. We first propose an online allocation algorithm for tenants with homogeneous bandwidth demand, which improves on the accuracy of existing algorithms. Subsequently, we extend it to handle heterogeneous bandwidth demand. Extensive simulations show that our algorithm makes much more efficient utilization of the network resource than existing algorithms, and performs close to the optimal offline allocation.
【Keywords】: Artificial neural networks; Resource management; Nonhomogeneous media; Bismuth
【Paper Link】 【Pages】:1-10
【Authors】: Ning Jin ; Kaiji Chen ; Tao Gu
【Abstract】: In this paper, we investigate the energy balanced data collection problem in WSNs, aiming to balance the energy consumption among all the sensor nodes in the data propagation process. Energy balanced data collection can potentially save energy consumption and prolong the network lifetime, and hence it has many practical implications for WSN design and deployment. The traditional hop-by-hop transmission model allows a sensor node to propagate its packets in a hop-by-hop manner towards the sink, resulting in poor energy balance for the entire network. To address the problem, we apply a slice based energy model, and divide the energy balanced data collection problem into inter- and intra-slice energy balance problems. We then propose a novel Inter-slice Mixed Transmission strategy and an Intra-slice Forwarding technique to address each of the problems. Finally, we design an Energy-balanced Transmission Protocol (ETP) to combine both techniques to achieve total energy balance in data collection. Through extensive simulation studies, we demonstrate that, while ETP achieves energy balanced data collection, the network lifespan is increased by 10 times and the network delay is decreased by more than 70% compared to the hop-by-hop transmission in a general square area WSN.
【Keywords】: Wireless sensor networks; Data collection; Energy consumption; Silicon; Mathematical model; Data models; Batteries
【Paper Link】 【Pages】:1-11
【Authors】: Takeshi Kubo ; Atsushi Tagami ; Teruyuki Hasegawa ; Toru Hasegawa ; Jean C. Walrand
【Abstract】: This paper proposes a new type of range-free localization method based on affine transformation. Nodes extract subgraphs with a grid topology from a sensor network and assign x-y coordinates to themselves in a decentralized manner. The nodes estimate their positions using an affine transformation based on the mapping of the physical positions and the x-y coordinates of three anchors in an extracted graph. In contrast with multilateration-based localization methods, the proposed method works well even in a non-convex hull deployment, such as a terrain with big regions without sensors. We provide a theoretical analysis and simulation results. We also present a strategy for minimizing the position estimation error and maximizing the coverage of the proposed method. In the simulation results, the position estimation error is 0.18 (normalized by the radio communication range) and the coverage is almost 100% in a non-convex hull deployment.
【Keywords】: affine transformation; Range-free localization; grid graph; decentralized algorithm
【Paper Link】 【Pages】:1-10
【Authors】: Lei Jiao ; Jun Li ; Tianyin Xu ; Xiaoming Fu
【Abstract】: Geo-distributed IaaS (Infrastructure-as-a-Service) clouds provide an intriguing platform to deploy Online Social Network (OSN) services. To leverage the potential of clouds, a major task of OSN providers is optimizing the monetary cost spent on cloud resource utilization while providing satisfactory Quality of Service (QoS) to OSN users. We thus study the problem of cost optimization for the dynamic OSN on multiple geo-distributed clouds over consecutive time periods, with its QoS meeting the pre-defined requirement. We model the QoS as well as the cost of an OSN, formulate the problem, and design a solution named cosplay. Our experiments with a large-scale Twitter trace show that, while always ensuring the QoS as required, cosplay can achieve superior one-time cost reduction compared with the state of the art, and can also reduce the accumulative cost significantly when continuously evaluated over 48 months with dynamics comparable to real-world OSNs.
【Keywords】: Quality of service; Optimization; Data models; Maintenance engineering; Partitioning algorithms; Resource management; Twitter