24th IEEE International Conference on Network Protocols, ICNP 2016, Singapore, November 8-11, 2016. IEEE Computer Society 【DBLP Link】
【Paper Link】 【Pages】:1-10
【Authors】: Xuan Feng ; Qiang Li ; Haining Wang ; Limin Sun
【Abstract】: Industrial control system (ICS) devices with IP addresses are accessible on the Internet and play a crucial role for critical infrastructures like power grid. However, there is a lack of deep understanding of these devices' characteristics in the cyberspace. In this paper, we take a first step in this direction by investigating these accessible industrial devices on the Internet. Because of critical nature of industrial control systems, the detection of online ICS devices should be done in a real-time and non-intrusive manner. Thus, we first analyze 17 industrial protocols widely used in industrial control systems, and train a probability model through the learning algorithm to improve detection accuracy. Then, we discover online ICS devices in the IPv4 space while reducing the noise of industrial honeypots. To observe the dynamics of ICS devices in a relatively long run, we have deployed our discovery system on Amazon EC2 and detected online ICS devices in the whole IPv4 space for eight times from August 2015 to March 2016. Based on the ICS device data collection, we conduct a comprehensive data analysis to characterize the usage of ICS devices, especially in the answer to the following three questions: (1) what are the distribution features of ICS devices, (2) who use these ICS devices, and (3) what are the functions of these ICS devices.
【Keywords】: Integrated circuits; Protocols; Industrial control; Payloads; Object recognition; Internet; IP networks
【Paper Link】 【Pages】:1-10
【Authors】: Mingjun Xiao ; Jie Wu ; He Huang ; Liusheng Huang ; Chang Hu
【Abstract】: Mobile crowdsensing is a new paradigm in which a group of mobile users exploit their smart devices to cooperatively perform a large-scale sensing job over urban environments. In this paper, we focus on the Deadline-sensitive User Recruitment (DUR) problem for probabilistically collaborative mobile crowdsensing. Unlike previous works, mobile users in this problem perform sensing tasks with probabilities, and multiple users might be recruited to cooperatively perform a common task, ensuring that the expected completion time is no larger than a deadline. Owing to such a probabilistic collaboration, DUR can be formalized as a non-trivial set cover problem with non-linear programming constraints and an optimization objective of real function. We first prove that the DUR problem is NP-hard. Then, we propose a greedy DUR algorithm, called gDUR, to solve this problem. Next, we prove that the gDUR algorithm can achieve a logarithmic approximation ratio. Furthermore, we extend the problem to a more complex case where sensing duration is taken into consideration, and we propose a sensing-duration-aware user recruitment algorithm, called dDUR. Finally, we validate the performance of the proposed algorithms through extensive simulations, based on a real mobile social network trace and a synthetic trace.
【Keywords】: Sensors; Mobile communication; Probabilistic logic; Recruitment; Collaboration; Mobile computing; Approximation algorithms
【Paper Link】 【Pages】:1-10
【Authors】: Binbin Li ; Yuan He ; Wenyuan Liu ; Lin Wang ; Hongyan Wang
【Abstract】: RFID systems nowadays are operated at large-scale in terms of both occupied space and tag quantity. One may have prior knowledge of the complete set of tags (denoted by N) and any set of wanted tags (denoted by M) within the complete set, i.e., M ⊆ N. Then here comes an open problem: when one is particularly interested in a subarea of the system, how to collect information (not simply tagIDs) from a wanted subset (denoted by dM) of the interrogated tags (denoted by dN) in that subarea? This issue has great significance in many practical applications but appears to be challenging when there is a stringent time constraint. In this work, we first establish the lower-bound of this problem, and show a straightforward polling solution. Then, we propose a novel polling protocol called LocP, which consists of two phases: the Tags-Filtering phase and the Ordering-and-Reporting phase. LocP employs Bloom Filter twice to significantly reduce the scale of candidate tags in the Tags-Filtering phase. In the Ordering-and-Reporting phase, tags determine their own transmission time-slots according to the allocation vectors iteratively broadcasted by the reader. LocP thus achieves a delicate tradeoff between time and polling accuracy. We conduct extensive simulations to evaluate the performance of LocP. The results demonstrate that LocP is highly efficient in terms of information collection time, leading to convincing applicability and scalability of large-scale RFID systems.
【Keywords】: Protocols; Radiofrequency identification; Microwave integrated circuits; Market research; Conferences; Scalability; Airports
【Paper Link】 【Pages】:1-10
【Authors】: Zhichao Cao ; Jiliang Wang ; Daibo Liu ; Xiaolong Zheng
【Abstract】: Asynchronous duty cycle is widely used for energy constraint wireless nodes to save energy. The basic flooding service in asynchronous duty cycle networks, however, is still far from efficient due to severe packet collisions and contentions. We present Chase, an efficient and fully distributed concurrent broadcast layer for flooding in asynchronous duty cycle networks. The main idea of Chase is to meet the strict signal timing and strength requirements (e.g., Capture Effect) for concurrent transmission while reducing contentions and collisions. We propose a distributed random inter-preamble packet interval adjustment approach to constructively satisfy the requirements. Even when requirements cannot be satisfied due to physical constraints (e.g., the difference of signal strength is less than a 3 dB), we propose a light-weight signal pattern recognition based approach to identify such a circumstance and extend radio-on time for packet delivery. We implement Chase in TinyOS and TelosB platform and extensively evaluate its performance. The implementation does not have any specific requirement on the hardware and can be easily extended to other platforms. The evaluation results also show that Chase can significantly improve flooding efficiency in asynchronous duty cycle networks.
【Keywords】: Delays; Protocols; Conferences; Schedules; Reliability; Pattern recognition
【Paper Link】 【Pages】:1-10
【Authors】: Yossi Kanizo ; Ori Rottenstreich ; Itai Segall ; Jose Yallouz
【Abstract】: In enterprise networks, network functions such as address translation, firewall and deep packet inspection are often implemented in middleboxes. Those can suffer from temporary unavailability due to misconfiguration or software and hardware malfunction. Traditionally, middlebox survivability is achieved by an expensive active-standby deployment where each middlebox has a backup instance, which is activated in case of a failure. Network Function Virtualization (NFV) is a novel networking paradigm allowing flexible, scalable and inexpensive implementation of network services. In this work we suggest a novel approach for planning and deploying backup schemes for network functions that guarantee high levels of survivability with significant reduction in resource consumption. In the suggested backup scheme we take advantage of the flexibility and resource-sharing abilities of the NFV paradigm in order to maintain only a few backup servers, where each can serve one of multiple functions when corresponding middleboxes are unavailable. We describe different goals that network designers can take into account when determining which functions to implement in each of the backup servers. We rely on a graph theoretical model to find properties of efficient assignments and to develop algorithms that can find them. Extensive experiments show, for example, that under realistic function failure probabilities, and reasonable capacity limitations, one can obtain 99.9% survival probability with half the number of servers, compared to standard techniques.
【Keywords】: Servers; Middleboxes; Bipartite graph; Conferences; Protocols; Resource management
【Paper Link】 【Pages】:1-10
【Authors】: Takeru Inoue ; Richard Chen ; Toru Mano ; Kimihiro Mizutani ; Hisashi Nagata ; Osamu Akashi
【Abstract】: Modern networks have complex configurations to provide advanced functions, but the complexity also makes them error-prone. Network verification is attracting attention as a key technology to detect inconsistencies between a configuration and a policy before deployment. Existing verifiers, however, either generally verify various properties over the policy at the cost of efficiency, or efficiently perform configuration analysis without paying much attention to the policy. This paper presents a novel framework of data-plane verification, which flexibly checks the inconsistency with great efficiency. For the purpose of generality, our framework formalizes a verification process with three abstract steps: each step is related to 1) packet behaviors defined by a configuration, 2) operator intentions described in a policy, and 3) the inspection of their relation. These steps work efficiently with each other on the simple quotient set of packet headers. This paper also reveals how the second step can be regarded as the windowing query problem in computational geometry. Two novel windowing algorithms are proposed with solid theoretical analyses. Experiments on real network datasets show that our framework with the windowing algorithms is surprisingly fast even when verifying the policy compliance; e.g., in a medium-scale network with thousands of switches, our framework reduces the verification time of all-pairs reachability from ten hours to ten minutes.
【Keywords】: Ports (Computers); Protocols; Complexity theory; Algorithm design and analysis; Conferences; Computational geometry; Solids
【Paper Link】 【Pages】:1-10
【Authors】: Huanyang Zheng ; Jie Wu
【Abstract】: This paper proposes a scalable publish/subscribe system based on unstructured P2P networks, which are shown to have Nested Scale-Free Architectures (NSFAs). The scale-free architecture is a classic concept, which means that the peer degree distribution follows power-law. `Nested' indicates that the scale-free architecture is preserved when low-degree peers and their associated connections are removed. We find that NSFA's hierarchy can be distributedly constructed, and has a better bound than classic hierarchies. By leveraging the NSFA's hierarchy, our publish/subscribe system achieves a competitive tradeoff among the event routing efficiency, system robustness, and overhead. For an unstructured P2P network with |V| peers, the number of routing hops for the event deliveries in our system is expected to be O(ln ln |V|). For the topological information, each peer only needs to maintain an overhead with a constant size, O(1). Peer arrival, departure, and failure can be handled within a message complexity of O(ln ln |V|). Finally, real data-driven experiments demonstrate the efficiency and effectiveness of the NSFA-based publish/subscribe system.
【Keywords】: Peer-to-peer computing; Routing; Robustness; Computer architecture; Servers; Labeling; Conferences
【Paper Link】 【Pages】:1-10
【Authors】: Zicheng Chi ; Yao Yao ; Tiantian Xie ; Zhichuan Huang ; Michael Hammond ; Ting Zhu
【Abstract】: The emerging smart health and smart home applications require pervasive and non-intrusive human activity recognition and monitoring. Traditional technologies (e.g., using cameras or accelerometers and gyroscopes) may introduce privacy issues or require people to wear sensors. To address these issues, recent approaches exploit fine-grained wireless signals for activity recognition. However, these approaches require devices that are costly or need to provide unique wireless features (e.g., Doppler shifts or phase information). With the increasingly available Internet of Things (IoT) devices, in this paper, we propose Harmony, a human activity recognition and monitoring middleware which can utilize the coarse-grained (but pervasively available) received signal strength (RSS) measurements from the radios of IoT devices. We implement a complete evaluation platform (from data collection to data analysis) of the middleware on top of low cost ZigBee compliant MICAz nodes and a laptop. We also conducted extensive experiments. Our results show that our design can achieve similar accuracy as fine-grained WiFi channel state information (CSI) measurement-based approaches. Specifically, our overall human activities recognition accuracy is up to 74% and 90% for RSS readings from a single pair and 3 pairs of IoT devices, respectively.
【Keywords】: Receivers; Monitoring; Middleware; ZigBee; IEEE 802.11 Standard; Wireless sensor networks
【Paper Link】 【Pages】:1-10
【Authors】: Andrey Gushchin ; Shih-Hao Tseng ; Ao Tang
【Abstract】: Many network flows nowadays, especially in a data center environment, have associated deadlines by which they must be fully transmitted. Nevertheless, traditional transport protocols such as TCP, focus on concepts like throughput and fairness, and do not aim to satisfy flow deadlines. Motivated by this limitation, several alternative transport designs and solutions have been recently proposed. These approaches generally achieve a better performance in terms of the number of satisfied deadlines and are usually built upon various heuristics. In contrast to these previous works, this article approaches the problem directly from an optimization perspective. We first prove that the problem belongs to the class of NP-hard problems that do not even admit a constant ratio approximation solution (unless P=NP), and formulate it as a mixed integer-linear optimization program. Then, using linear programming approximations, we further develop offline and online optimization-based rate control algorithms to approach the problem. Flow-level simulation results indicate that the proposed algorithms can be near-optimal, and hence they can be served as benchmarks against which other solutions to this problem can be evaluated. We additionally performed simulations incorporating such real network features as deployment delays and packet-level granularity to evaluate the performance of the proposed algorithms in a more realistic environment.
【Keywords】: Protocols; Routing; Optimization; Processor scheduling; Optimal control; Linear programming; Scheduling
【Paper Link】 【Pages】:1-10
【Authors】: Liang Ma ; Mudhakar Srivatsa ; Derya Cansever ; Xifeng Yan ; Sue Kase ; Michelle Vanni
【Abstract】: We investigate the problem of query answering in expert networks, which are composed of inter-connected experts with various specialties. Upon receiving a query, the expert network is tasked to route this query to experts with sufficient expertise in a timely and reliable manner. However, the efficiency of query answering depends on the underlying query routing protocol being used. Among all possible query routing protocols, decentralized search, operating purely on each expert's local information without any network global knowledge, represents the most basic and scalable routing protocol. However, there is still a lack of fundamental understanding on the efficiency of decentralized search in different expert networks. In this regard, we establish a generic model that can abstract diversified social and structural attributes in various expert networks into a common framework, thus applicable to a wide range of network scenarios. On top of such generic network model, we then study decentralized search by quantifying its performance under a variety of network parameters. Our key findings reveal the existence of network conditions, under which decentralized search can achieve significantly short query routing paths (i.e., between O(log n) and O(log2 n) hops, n: total number of experts in the network). To the best of our knowledge, this is the first work studying fundamental behaviors of decentralized search without relying on strict underlying network structures in expert networks. Experiments in both synthetic and real expert networks confirm the efficacy of the developed performance bounds in understanding and reasoning the network performance.
【Keywords】: Routing; Query processing; Routing protocols; Knowledge engineering; Search problems; Electronic mail
【Paper Link】 【Pages】:1-10
【Authors】: Fan Zhang ; Hanhua Chen ; Hai Jin
【Abstract】: Event stream dissemination dominates the workloads in large-scale Online Social Network (OSN) systems. Based on the de facto per-user view data storage, event stream dissemination raises a large amount of inter-server traffics due to the complex interconnection among OSN users. The state-of-the-art schemes mainly explore the structure features of social graphs to reduce the inter-server messages for event stream dissemination. Different sub-graph structures are exploited for achieving the approximated optimal assignment. However, such schemes incur high costs of computation or communication. In this work, we follow a different design philosophy by using a game theoretic approach, which decomposes the high complex graph computation problem into individuals' rational strategy selection of each node. Specifically, we propose a novel social piggyback game to achieve a more efficient solution. We mathematically prove the existing of the Nash Equilibrium of the social piggyback game. Moreover, we propose an efficient best response dynamic algorithm to achieve the Nash Equilibrium, which quickly converges in a small number of iterations for large-scale OSNs. We further show that the communication cost of this design achieves a 1.5-approximation of the theoretical social optimal. We conduct comprehensive experiments to evaluate the performance of this design using large-scale real-world traces from popular OSN systems. Results show that the social piggyback game achieves a significant 302× improvement in system efficiency compared to existing schemes.
【Keywords】: Games; Schedules; Heuristic algorithms; Algorithm design and analysis; Nash equilibrium; Social network services; Servers
【Paper Link】 【Pages】:1-10
【Authors】: Qiang Liu ; Nageswara S. V. Rao ; Chase Q. Wu ; Daqing Yun ; Rajkumar Kettimuthu ; Ian T. Foster
【Abstract】: Wide-area data transfers in high-performance computing and big data scenarios are increasingly being carried over dedicated network connections that provide high capacities at low loss rates. UDP-based transport protocols are expected to be particularly well-suited for such transfers but their performance is relatively unexplored over a wide range of connection lengths, compared to TCP over shared connections. We present extensive throughput measurements of UDP-based Data Transfer (UDT) over a suite of physical and emulated 10 Gbps connections. In sharp contrast to current UDT analytical models, these measurements indicate much more complex throughput dynamics that are sensitive to the connection modality, protocol parameters, and round-trip times. Lyapunov exponents estimated from the Poincaré maps of UDT traces clearly indicate regions of instability and complex dynamics. We propose a simple model based on the ramp-up and sustainment regimes of a generic transport protocol, which qualitatively illustrates the dominant monotonicity and concavity properties of throughput profiles and relates them to Lyapunov exponents. These measurements and analytical results together enable us to comprehensively evaluate UDT performance and select parameters to achieve high throughput, and they also provide guidelines for designing effective transport protocols for dedicated connections.
【Keywords】: Throughput; Transport protocols; Data transfer; Analytical models; Conferences; Time measurement
【Paper Link】 【Pages】:1-10
【Authors】: Qiongwen Xu ; Xu Zhang ; Jin Zhao ; Xin Wang ; Tilman Wolf
【Abstract】: Shortest-path queries on weighted graphs are an essential operation in computer networks. The performance of such algorithms has become a critical challenge in emerging software-defined networks (SDN), since SDN controllers need to perform a shortest-path query for every flow. Unlike classic solutions (e.g., Dijkstra's algorithm), high-performance shortest-path query algorithms include two stages: preprocessing and query answering. Despite the improved query answering time, existing two-stage algorithms are still extremely time-consuming in preprocessing large-scale graphs. In this paper, we propose an efficient shortest-path query algorithm, called BBQ, which reduces the running time of both stages via tree decomposition. BBQ constructs a distance oracle in a bottom-top-bottom manner, which significantly reduces preprocessing time over existing algorithms. In addition, BBQ can answer batch queries in bulk by traversing the decomposed tree instead of executing separate queries. Our experimental results show that BBQ outperforms state-of-the-art approaches by orders of magnitude for the running time of the preprocessing stage. Meanwhile, BBQ also offers remarkable acceleration for answering batches of queries. As a result, SDN controllers that use BBQ can sustain 1.1-27.9 times higher connection request rates.
【Keywords】: Phase locked loops; Conferences; Protocols; Acceleration; Runtime; Time complexity
【Paper Link】 【Pages】:1-10
【Authors】: Meng Jin ; Yuan He ; Xiaolong Zheng ; Dingyi Fang ; Dan Xu ; Tianzhang Xing ; Xiaojiang Chen
【Abstract】: Operating in unlicensed ISM bands, ZigBee devices often yield poor throughput and packet reception ratio due to the interference from ever increasing wireless devices in 2.4 GHz band. Although there have been many efforts made for interference avoidance, they come at the cost of miscellaneous overhead, which oppositely hurts channel utilization. Our empirical results show that, a specific interference is likely to have different influence on different outbound links of a ZigBee sender, which indicates the chance of concurrent transmissions. Based on this insight, we propose Smoggy-Link, a practical protocol to exploit the potential concurrency for adaptive ZigBee transmissions under harsh interference. Smoggy-Link maintains an accurate link model to describe and trace the relationship between interference and link quality of the sender's outbound links. With such a link model, Smoggy-Link can obtain fine-grained spatiotemporal link information through a low-cost interference identification method. The link information is further utilized for adaptive link selection and intelligent transmission schedule. We implement and evaluate a prototype of our approach with TinyOS and TelosB motes. The evaluation results show that Smoggy-Link has consistent improvements in both throughput and packet reception ratio under interference from various interferer.
【Keywords】: Interference; IEEE 802.11 Standard; ZigBee; Bluetooth; Protocols; Wireless communication; Concurrent computing
【Paper Link】 【Pages】:1-10
【Authors】: Haoyang Lu ; Wei Gao
【Abstract】: Scheduling in wireless networks is critical to maximize the network throughput by avoiding interference among wireless links, and is usually formulated as solving the NP-hard Maximum Weighted Independent Set (MWIS) problem over a network confiict graph. Existing scheduling algorithms are designed to provide approximations to global optimality via distributed operations in wireless networks, but will frequently reschedule the entire network in cases of network dynamics regardless of the actual network area being affected by these dynamics. Such repetitive rescheduling results in a large amount of computation and communication overhead, most of which may be, however, unnecessarily incurred over the wireless links that remain unchanged. To reduce such overhead and improve the scheduling cost-effectiveness, in this paper we develop distributed algorithms that adaptively constrain network scheduling within the limited scope where network dynamics occur. The scheduling results from such limited operations are then combined with the previous scheduling results over the remaining portions of the network, hence still providing guaranteed network throughput. The performance of our proposed algorithms has been validated by formal analysis, and been verified by both numerical studies and real-world experiments.
【Keywords】: Wireless networks; Throughput; Interference; Scheduling algorithms; Dynamic scheduling
【Paper Link】 【Pages】:1-10
【Authors】: Chin-Jung Liu ; Li Xiao
【Abstract】: Network densification by installing more cellular stations (cells) with smaller coverage is a promising technique to improve wireless capacity to meet the overwhelming demands for mobile data usage. These smaller cells with different coverage and the macrocellular base station form heterogeneous cellular networks (HetNet). However, the dense deployment of HetNet cells might result in unexpected inter-cell interference. In cellular networks, the data to all cells and to the mobile stations (MSs) are originated from the core cellular network. We take advantage of this characteristic and propose a technique called interference precancellation. If the interferer to an MS is identified, the victim cell that serves the victim MS transmits the interference precanceled signal, which is the signal intended for the victim MS subtracts the interference signal. The interference precanceled signal and the interference signal scramble at the victim MS and become the intended signal. With interference precancellation, the interferer and the victim cell can utilize the same wireless resources and thus the capacity is further improved. However, some MSs are interference-free and for MSs whose exact interferers cannot be determined, the MSs still require isolated resources. We propose an algorithm for resource management with interference precancellation (RMIP) that jointly considers MSs experiencing different level of interference. Through experiments on GNURadio/USRP, we show that the known interference signal can be precanceled and the combination of the interference signal and the precanceled signal becomes the intended signal. Through simulation, we evaluate the performance in larger HetNets.
【Keywords】: Interference; Cellular networks; Femtocells; Resource management; Wireless communication; OFDM
【Paper Link】 【Pages】:1-10
【Authors】: Hengky Susanto ; Hao Jin ; Kai Chen
【Abstract】: Coflow scheduling can improve application-level communication performance for data-parallel clusters. However, most prior coflow scheduling schemes are based on the centralized approach, which achieve good performance but suffers from high control overhead and scalability issue. On the other hand, state of the art decentralized solution requires switch modification, which makes it hard to implement. In this paper, we present Stream, the decentralized and readilyimplementable solution for coflow scheduling. The key idea of Stream is to opportunistically take advantage of many-to-one and many-to-many coflow patterns to coordinate coflows without resorting to the centralized controller, and then emulate shortest coflow first scheduling to minimize the average coflow completion time (CCT). We implement Stream with existing commodity switches and show its performance using both testbed experiments and large-scale simulations. Our evaluation results show that Stream's performance is comparable to the centralized solution, and outperforms the state of the art decentralized scheme by 1.77x on average.
【Keywords】: Receivers; Switches; Network topology; Topology; Production; Facebook; Conferences
【Paper Link】 【Pages】:1-10
【Authors】: Xingliang Yuan ; Huayi Duan ; Cong Wang
【Abstract】: Migrating middleboxes to third-party service providers (e.g., clouds and ISPs) has drawn widespread attentions recently from both industry and academia. While its benefits on reduced local cost and increased service scalability are well understood, such deployment also introduces new security concerns, due to the fact that these boxes are no longer under the direct control of enterprises. Among others, one fundamental desideratum here is to ensure that those middleboxes consistently perform network functions as intended. In this work, we propose practical solutions towards enabling runtime execution assurances of outsourced middleboxes with high confidence. As an initial effort, we target on pattern matching based network functions, which cover a broad class of middlebox applications such as instruction detection, web firewall, and traffic classification. For efficiency, our design follows the same roadmap of probabilistic checking that provides tunable levels of assurance, as in outsourced computation and distributed computing literature. We show how to synthesize the design intuitions in the context of outsourced middleboxes and the dynamic network effect. We present diligent technical instantiations, in the case of single middlebox and the composition of multiple middlebox service chaining, respectively. For a large batch of packets, sufficiently high assurance levels can be achieved by pre-processing only a few randomly selected packets, with marginal overhead. Evaluations of our system prototype on Amazon EC2 show that, the processing of 1000 packets, which includes pattern matching and execution proof generation, results in 200-500ms latency and throughput up to 360Mbps.
【Keywords】: Middleboxes; Pattern matching; Protocols; Cryptography; Runtime; Context
【Paper Link】 【Pages】:1-10
【Authors】: Wei Wang ; A.-Long Jin
【Abstract】: Cloud networks consist of a large number of links, on which tenants have correlated and elastic bandwidth demands in the form of coflows. Ideally, a cloud network sharing policy should provide tenants with isolation guarantees on the minimum coflow progress, while at the same time attaining as high utilization as possible. Prior work shows that to achieve the optimal isolation guarantee, strategy-proofness is needed, in that tenants cannot lie about demands to obtain higher progresses. However, this requirement is derived under a simplified assumption that tenants are only interested in maximizing coflow progresses. We show in this work that a rational tenant should pursue more bandwidth allocation as a secondary objective after progress maximization. In this new model, enforcing strategy-proofness inevitably hurts the isolation guarantee. We propose a new network sharing policy to achieve the optimal isolation guarantee while attaining the highest possible utilization in spite of strategic, untruthful tenants. Trace-driven evaluations show that our policy outperforms existing alternatives with better isolation guarantee, higher utilization, and shorter coflow completion time (CCT).
【Keywords】: Bandwidth; Resource management; Channel allocation; Correlation; Conferences; Protocols; Fabrics
【Paper Link】 【Pages】:1-10
【Authors】: H. B. Acharya ; Satyam Kumar ; Mohit Wadhwa ; Ayush Shah
【Abstract】: Networking infrastructure, such as routers and firewalls, consist of a policy (i.e., where to forward which packets) and a mechanism that implements it. As the correctness of the policy is critical, it is a natural candidate for formal verification. Indeed, several verification algorithms have been developed, that detect anomalies, conflicts, and redundancies in practical firewalls and flow tables. However, theory suggests that the problem is intractable in general: the decision tree for a policy is of size O((2n)d), where n is the number of rules and d is the number of observed features used in making the decision. (In a typical firewall, n = 1000 and d = 10.) In this paper, we show why the verification of practical firewalls is not as hard as previously thought. Using a new concept, “rules in play,” we find a new, tight bound on the size of the decision tree, and suggest three other factors - narrow fields, singletons, and all-matches - that make the problem tractable in practice. We also present an algorithm to solve an open problem: pruning a policy to the minimum possible number of rules, without changing its meaning.
【Keywords】: Complexity theory; Decision trees; Protocols; Routing; Size measurement; IP networks
【Paper Link】 【Pages】:1-10
【Authors】: Xuan Liu ; Bin Xiao ; Feng Zhu ; Shigeng Zhang
【Abstract】: Fast tag identification is a fundamental challenging problem in multi-reader RFID systems. The challenge is how to effectively handle Reader-Tag (RT) collisions and Reader-Reader (RR) collisions among adjacent readers. These collisions are caused by interfering signals simultaneously transmitted by the readers, and may disallow adjacent readers to work together. Prior works tackle this problem by scheduling adjacent readers to work in different time slots. The readers that are selected to simultaneously work, however, are usually only a small proportion of the total readers. This greatly restricts the identification throughput. Our insightful investigation on the current tag identification protocol reveals that RT collisions are caused by asynchronous actions of readers. i.e., a reader transmits signal while its adjacent readers receive. We thus develop Slot Splitting, a technique that can completely eliminate RT collisions by synchronizing actions of readers. We also propose a reader selection algorithm that minimizes RR collisions by selecting a reader set with maximum reading efficiency. The combination of these new techniques inspires Federal, a Fast and efficient tag identification protocol with interference-elimination-based reader scheduling. To our knowledge, Federal is the first identification protocol that completely eliminates RT collisions and minimizes RR collisions in both regularly and randomly deployed multi-reader systems. We validate the feasibility of Slot Splitting with experiments on the USRP platform and evaluate the performance of Federal through extensive simulations. The results show that Federal can increase tag identification throughput by up to 218% compared with the state-of-the-art work.
【Keywords】: Protocols; Throughput; Radiofrequency identification; Interference; Radiation detectors; Conferences; Monitoring
【Paper Link】 【Pages】:1-10
【Authors】: Vinay Kolar ; Israat Tanzeena Haque ; Vikram P. Munishwar ; Nael B. Abu-Ghazaleh
【Abstract】: Smart camera networks (SCNs) are increasingly used in applications such as homeland security, border control and traffic monitoring. The cameras are often wireless with an organically growing structure, to reduce the overhead of deployment. We frame a new and important problem in SCNs: how to transmit videos from multiple cameras with overlapping coverage given the limited available wireless bandwidth to maximize the quality of the received videos. We call this problem Coordinated Transport of Correlated Videos (CTCV). CTCV is a more general version of 3D video transport: in that problem, highly correlated videos from two cameras (that provide the 3D perspective) are jointly encoded exploiting their pre-defined and known overlap. In contrast, in CTCV there is an arbitrary number of cameras whose overlap is not known apriori and that require transmission as multiple video streams. To effectively support CTCV, we propose a video delivery protocol that consists of two primary components: (1) Consolidation of correlated videos from multiple cameras which removes spatially redundant fields-of-view; and (2) Network and coverage aware bandwidth allocation to optimize coverage quality cooperatively among the different video streams to match the available bandwidth. We formulate the problem of optimal bandwidth allocation for maximizing coverage. We propose and investigate different heuristic policies for bandwidth allocation. We evaluate CTCV using data from a small camera testbed as well as topologies from realistic deployments. Experiments show that CTCV achieves around 10 dB gains in video quality in the scenarios we consider.
【Keywords】: Cameras; Streaming media; Redundancy; Protocols; Bandwidth; Wireless communication; Monitoring
【Paper Link】 【Pages】:1-10
【Authors】: Sorrachai Yingchareonthawornchai ; James Daly ; Alex X. Liu ; Eric Torng
【Abstract】: OpenFlow packet classification needs to satisfy two requirements: high speed and fast updates. Although packet classification is a well-studied problem, no existing solution satisfies both requirements. Decision tree methods, such as HyperCuts, EffiCuts, and SmartSplit can achieve high-speed packet classification but not fast updates. The Tuple Space Search (TSS) algorithm used in Open vSwitch achieves fast updates but not high-speed packet classification. In this paper, we propose a hybrid approach, PartitionSort, that combines the benefits of both TSS and decision trees achieving both high-speed packet classification and fast updates. A key to PartitionSort is a novel notion of ruleset sortability that provides two key benefits. First, it results in far fewer partitions than TSS. Second, it allows the use of Multi-dimensional Interval Trees to achieve logarithmic classification and update time for each sortable ruleset partition. Our extensive experimental results show that PartitionSort is an order of magnitude faster than TSS in classifying packets while achieving comparable update time. PartitionSort is a few orders of magnitude faster in construction time than SmartSplit, a state-of-the-art decision tree classifier, while maintaining competitive classification time. Finally, PartitionSort is scalable to an arbitrary number of fields.
【Keywords】: Decision trees; Partitioning algorithms; Protocols; Algorithm design and analysis; Conferences; Switches; IP networks
【Paper Link】 【Pages】:1-10
【Authors】: Gayane Vardoyan ; Nageswara S. V. Rao ; Don Towsley
【Abstract】: In recent years, there has been a steady growth in network bandwidths. This is especially true in scientific and big data environments, where high bandwidth-delay products (BDPs) are common. It is well-understood that legacy TCP (e.g. TCP Reno) is not appropriate for such environments, and several TCP variants were developed to address this shortcoming. These variants, including CUBIC, STCP, and H-TCP, have been studied in some empirical contexts, and some analytical models exist for CUBIC and STCP. However, since these studies were conducted, BDPs further increased, and new bulk data transfer methods have emerged that utilize parallel TCP streams. In view of these new developments, it is imperative to revisit the question: `Which congestion control algorithms are best adapted to current networking environments?' In order to answer this question, (i) we create a general theoretical framework within which to develop mathematical models of TCP variants that account for finite buffer sizes, maximum window constraints, and parallel TCP streams; (ii) we validate the models using measurements collected over a high-bandwidth testbed and achieve low prediction errors; (iii) we find that CUBIC and H-TCP outperform STCP, especially when multiple streams are used.
【Keywords】: Protocols; Data transfer; Linux; Kernel; Throughput; SONET; Bandwidth
【Paper Link】 【Pages】:1-10
【Authors】: Linqi Guo ; John Pang ; Anwar Walid
【Abstract】: Network functions typically need to be visited in a specific order to meet certain objectives, giving rise to the notion of Service Function Chaining. Software-Defined-Networking enables fine-grained traffic routing optimization while satisfying correct traversal of network functions. In this work, we investigate the problem of maximizing throughput in SDN-enabled networks with respect to service chaining specifications under both traditional and new constraints. Besides the algorithm design, we also derive rigorous performance bounds. In the offline traffic routing case, we propose Traffic-Merging-Algorithm and prove that, although the underlying optimization problem is generally NP-hard, our algorithm can efficiently compute the optimal solution in practical settings. In the online traffic routing case, we propose the Primal-Dual-Update-Algorithm, which comes with a system parameter that trades off the algorithm's throughput competitiveness and its meeting of QoS requirements, and prove that our online algorithm achieves optimal tradeoff. We demonstrate that our solutions can be used to address practical problems by conducting simulation-based evaluation over backbone and data center topologies.
【Keywords】: Routing; Middleboxes; Optimization; Handheld computers; Delays; Throughput; Algorithm design and analysis
【Paper Link】 【Pages】:1-10
【Authors】: Faraz Ahmed ; M. Zubair Shafiq ; Amir R. Khakpour ; Alex X. Liu
【Abstract】: Content Distribution Networks (CDNs) maintain multiple transit routes from content distribution servers to eyeball ISP networks which provide Internet connectivity to end users. Due to the dynamics of varying performance and pricing on transit routes, CDNs need to implement a transit route selection strategy to optimize performance and cost tradeoffs. In this paper, we formalize the transit routing problem using a multi-attribute objective function to simultaneously optimize end-to-end performance and cost. Our approach allows CDNs to navigate the cost and performance tradeoff in transit routing through a single control knob. We evaluate our approach using real-world measurements from CDN servers located at 19 geographically distributed IXPs. Using our approach, CDNs can reduce transit costs on average by 57% without sacrificing performance.
【Keywords】: Servers; Internet; Routing; Pricing; Linear programming; Delays; Conferences
【Paper Link】 【Pages】:1-10
【Authors】: Wen Wang ; Wenbo He ; Jinshu Su
【Abstract】: With SDN control programs from multi-domains configuring the network, it is inevitable that control programs make conflicting control decisions, which probably lead to misconfiguration or performance degradation. Existing control coordination approaches either compose control programs to derive consistent solutions jointly or examine the generated rules of each control program to ensure they are consistent. However, the former is usually of great complexity and hard to be conducted automatically, and the latter probably results in suboptimal solutions due to the independent execution of control programs. Moreover, these approaches all fail to consider the control utility of control programs. In this paper, we propose Redactor to optimize the consistency and utility of network control in an automatic and dynamic manner. To make network control consistent, we implement SDN control programs with declarative language Prolog, and compose control programs automatically to execute together to make consistent decisions. When conflicts occur, we use a heuristic approach to compromise a subset of control programs to maximize the control utility. We compare Redactor with the static priority mechanism and Athens [1], and the results show that Redactor always satisfies more control objectives to achieve better control consistency and utility.
【Keywords】: Process control; Bandwidth; Switches; Routing; Proposals; Conferences
【Paper Link】 【Pages】:1-10
【Authors】: Shiyao Ma ; Jingjie Jiang ; Bo Li ; Baochun Li
【Abstract】: Data-parallel applications, especially those associated with user-facing web services, have struggled to enhance their worst case performance. It is therefore important to improve the minimum amount of resources guaranteed for applications in a cluster. Existing cluster management frameworks, however, provide isolation for computation resources (such as CPU) only, and are oblivious to network isolation guarantees. In this paper, we design, implement and evaluate Libra, a new cluster management framework that helps to maximize the isolation guarantee for the bandwidth requirements from applications. We start with a theoretical analysis of the network sharing problem, which contains two key steps: container placement and bandwidth allocation. By collecting the status of access links and the bandwidth demand of applications, we coordinate the placement of containers to minimize the system bottleneck such that the bandwidth guarantee for applications can be optimized. We further embrace host-based rate limiting to ensure such maximized bandwidth guarantee can be reached without hurting network utilization. Both our testbed-based experiments and large-scale simulations demonstrate that Libra significantly improves the network isolation guarantee: in comparison with existing cluster managers and network schedulers, the performance gain is more than 105.59%. Meanwhile, it improves application performance by 57.71% and maintains high network utilization.
【Keywords】: Containers; Bandwidth; Downlink; Channel allocation; Uplink; Resource management; Conferences
【Paper Link】 【Pages】:1-10
【Authors】: Haipeng Dai ; Xiaoyu Wang ; Alex X. Liu ; Fengmin Zhang ; Yang Zhao ; Guihai Chen
【Abstract】: Wireless Power Transfer (WPT) has received more and more attentions because of its convenience and reliability. In this paper, we first propose the notion of omnidirectional charging by which an area is omnidirectionally charged if a device with directional antennas at any position in the area with any orientation can be charged by directional chargers with power being no smaller than a given threshold. We present our empirical charging model based on field experimental results using off-the-shelf WPT products. Next, we consider the problem of detecting whether the target area achieves omnidirectional charging given a deterministic deployment of chargers. We develop piecewise constant approximation and area discretization techniques to partition the target area into subareas and approximate powers from chargers as constants. Then we propose the Minimum Coverage Set extraction technique which reduces the continuous search space to a discrete one and thereby allows a fast detection algorithm. Moreover, we consider the problem of determining the probability that the target area achieves omnidirectional charging given a random deployment of chargers. We first replace the target area by grid points on triangular lattices to reduce the search space from infinite to finite, then approximate chargers' power with reasonable relaxation, and derive an upper bound of the omnidirectional charging probability. Finally, we conduct both simulation and field experiments, and the results show that our algorithm outperforms comparison algorithms by at least 120%, and the consistency degree of our theoretical results and field experimental results is larger than 93.6%.
【Keywords】: Wireless sensor networks; Wireless communication; Directional antennas; Adaptation models; Joining processes; Conferences; Protocols
【Paper Link】 【Pages】:1-10
【Authors】: Hongli Xu ; Zhuolong Yu ; Xiang-Yang Li ; Chen Qian ; Liusheng Huang ; Taeho Jung
【Abstract】: Due to flow dynamics, a software defined network (SDN) may need to frequently update its data plane so as to optimize various performance objectives, such as load balancing. Most previous solutions first determine a new route configuration based on the current flow status, and then update the forwarding paths of existing flows. However, due to slow update operations of Ternary Content Addressable Memory (TCAM) based flow tables, unacceptable update delays may occur, especially in a large or frequently changed network. According to recent studies, most flows have short duration and the workload of the entire network may vary after a long duration. As a result, the new route configuration may be no longer efficient for the workload after the update, if the update duration takes too long. In this paper, we address the real-time route update, which jointly considers the optimization of flow route selection in the control plane and update scheduling in the data plane. We formulate the delay-satisfied route update (DSRU) problem, and prove its NP-Hardness. Two algorithms with bounded approximation factors are designed to solve this problem. We implement the proposed methods on our SDN testbed. The experimental results and extensive simulation results show that our method can reduce the route update delay by about 60% compared with previous route update methods while preserving a similar routing performance (with link load ratio increased less than 3%).
【Keywords】: Delays; Control systems; Real-time systems; Optimization; Routing protocols; Approximation algorithms; Load management
【Paper Link】 【Pages】:1-10
【Authors】: Mahanth Gowda ; Nirupam Roy ; Romit Roy Choudhury ; Srihari Nelakuditi
【Abstract】: Randomized backoff is a well-established approach for avoiding collisions in CSMA networks. Today's backoff operation, such as in WiFi, attempts to create a total ordering among all the nodes contending for the channel. Total ordering requires assigning a unique backoff to each node, which is achieved by having nodes choose their back-offs from a large range, ultimately leading to channel wastage. This paper observes that total ordering can be achieved more efficiently. We propose “hierarchical backoff” in which nodes pick random numbers from a smaller range, resulting in groups of nodes picking the same number (i.e., partial order). Now, the group of nodes that picks the smallest number is advanced to a second round, where they again perform the same operation. This results in more efficient backoff because the time for partially ordering all nodes plus totally ordering each small groups is actually less than the time needed to totally order all nodes. Realizing the above intuition requires addressing new protocol challenges in group signaling, the feasibility of which is demonstrated on a USRP/GNUradio prototype. Large scale simulations also show consistent throughput gains by incorporating the proposed backoff approach into two CSMA protocols - WiFi and oCSMA. We also show that the proposed approach can be complementary to and even outperform existing backoff optimization schemes.
【Keywords】: IEEE 802.11 Standard; Protocols; Radiation detectors; Multiaccess communication; Conferences; Signal resolution; Throughput
【Paper Link】 【Pages】:1-10
【Authors】: Zongqing Lu ; Kevin S. Chan ; Rahul Urgaonkar ; Thomas F. La Porta
【Abstract】: The vast adoption of mobile devices with cameras has greatly assisted in the proliferation of the creation and distribution of videos. For a variety of purposes, valuable information may be extracted from these videos. While the computational capability of mobile devices has greatly improved recently, video processing is still a demanding task for mobile devices. Given a network consisting of mobile devices and video-clouds, mobile devices may be able to upload videos to video-clouds, which are more computationally capable for these processing tasks. However, due to networking constraints, when a video processing task is initiated through a query, most videos will not likely have been uploaded to the video-clouds, especially when the query is about a recent event. We investigate the problem of minimal query response time for processing videos stored across a network; however, this problem is a strongly NP-hard problem. To deal with this, we first propose a greedy algorithm with bounded performance. To further deal with the dynamics of the transmission rate between mobile devices and video-clouds, we propose an adaptive algorithm. To evaluate these algorithms, we built an on-demand video processing system. Based on the measurements of the system, we perform simulations to extensively evaluate the proposed algorithms. We also perform experiments on a small testbed to examine the realized system performance. Results show the performance of the greedy algorithm is close to the optimal and much better than other approaches, and the adaptive algorithm performs better with more dynamic transmission rates.
【Keywords】: Mobile handsets; Performance evaluation; Delays; Time factors; Heuristic algorithms; Streaming media; Wireless networks
【Paper Link】 【Pages】:1-10
【Authors】: Min Chen ; Jia Liu ; Shigang Chen ; Qingjun Xiao
【Abstract】: Radio-frequency identification (RFID) technologies have been widely used in many applications, including inventory management, supply chain, product tracking, transportation, logistics, etc. Tag estimation, which is to estimate the cardinality of a single tag set, is an important research topic. This paper expands the estimation research as follows: It performs joint estimation between two tag sets (which exist at different locations or at the same location but different times). More importantly the estimation is fine-grained in an effort to accommodate common practical scenarios, where each tag set consists of tags belonging to different categories. For any two given tag sets, we want to know the detailed information about the joint property of each category, instead of just the aggregate information of the whole sets. Furthermore, due to the open nature of RFID communications, it is often desirable that tag estimation can be performed in an anonymous way without revealing the tags' ID information. To support these requirements, we develop a new technique called mask bitmap that can encode a tag set without requiring the tags to report their IDs or category IDs. Any two mask bitmaps of different tag sets can be combined to perform category-level joint estimation. Through formal analysis, we determine how to set system parameters to meet a given accuracy requirement that can be arbitrarily set. Extensive simulation results confirm that the proposed solution can yield accurate category-level estimates in an efficient way, and preserve tags' anonymity as well.
【Keywords】: Estimation; Radiofrequency identification; Protocols; Conferences; Aggregates; Simulation; Servers
【Paper Link】 【Pages】:1-10
【Authors】: Liang Wang ; Gareth Tyson ; Jussi Kangasharju ; Jon Crowcroft
【Abstract】: Caching is a core principle of information-centric networking (ICN). Many novel algorithms have been proposed for enabling ICN caching, many of which rely on collaborative principles, i.e. multiple caches interacting to decide what to store. Past work has assumed entirely altruistic nodes that will sacrifice their own performance for the global optimum. In this paper, we argue that this assumption is flawed. We address this problem by modelling the in-network caching problem as a Nash bargaining game. We develop optimal and heuristic caching solutions that explicitly consider both performance and fairness. We argue that only algorithms that are fair to all parties will encourage engagement and cooperation. Through extensive simulations, we show our heuristic solution, FairCache, ensures that all collaborative caches achieve performance gains without undermining the performance of others.
【Keywords】: Collaboration; Games; NIST; Protocols; Algorithm design and analysis; Conferences; Prediction algorithms
【Paper Link】 【Pages】:1-10
【Authors】: Shihan Xiao ; Yong Cui ; Xin Wang ; Zhenjie Yang ; Shenghui Yan ; Liu Yang
【Abstract】: Virtual machine (VM) migration is a key technique for network resource optimization in modern data center networks (DCNs). Previous work generally focuses on how to place the VMs efficiently in a static network topology by migrating the VMs with large traffic demands to close servers. When the VM demands change, however, a great cost will be paid on the VM migration. With the advance of software-defined network (SDN), recent studies have shown great potential to implement an adaptive network topology at a low cost. Taking advantage of the topology adaptability, in this paper, we propose a new paradigm for VM migration by dynamically constructing a topology based on the VM demands to lower the cost of both VM migration and communication. We formulate the traffic-aware VM migration problem in an adaptive topology and show its NP-hardness. Then we develop a novel progressive-decompose-rounding (PDR) algorithm to solve this problem in polynomial time with a proved approximation ratio. Extensive trace-based simulations show that PDR can achieve higher flow throughput among VMs with only a quarter of the migration cost compared to other state-of-art VM migration solutions. We finally implement an OpenvSwitch-based testbed and demonstrate the efficiency of our solution.
【Keywords】: Topology; Servers; Network topology; Wireless communication; Routing; Interference; Optimization
【Paper Link】 【Pages】:1-10
【Authors】: Marcel Flores ; Alexander Wenzel ; Aleksandar Kuzmanovic
【Abstract】: Enabling communication between routers and endpoints has long been sought after as an approach to congestion control in the Internet. However, the narrow-waist of TCP/IP has complicated the deployment of such communication. In this paper, we present Kick-Ass1, a congestion control mechanism that enables explicit rate congestion control protocols to be deployed within the TCP/IP stack. The key idea is to utilize packet lengths as a vehicle to communicate fine-grained explicit rate and other information from routers to endpoints and vice versa. Given that our approach (i) requires no explicit coordination among Kick-Ass routers, (ii) no explicit coordination among Kick-Ass routers and endpoints, and (iii) is effective on paths that include legacy routers, it provides a practical road towards a faster Internet, today. Using large-scale simulations, testbed experiments, and wide-area Internet evaluations, we demonstrate that (i) a basic explicit-rate protocol using the Kick-Ass mechanism improves flow completion times by up to an order of magnitude and outperforms endpoint-based approaches, including CUBIC and PCC. (ii) Kick-Ass is incrementally deployable on the Internet. (iii) Deploying Kick-Ass at end-hosts and edge routers can enable the above performance benefits, without waiting for universal adoption. (iv) Our packet-fragmentation mechanism is well behaved on the Internet.
【Keywords】: Internet; Routing protocols; TCPIP; Delays; Encoding
【Paper Link】 【Pages】:1-10
【Authors】: Aditya Yadav ; Arun Venkataramani
【Abstract】: Despite the explosive growth of mobile devices and applications in recent years, today's Internet provides little intrinsic support for seamless mobility. Prior solutions to addressing this problem either handle only a subset of endpoint mobility scenarios or require nontrivial changes to legacy infrastructure. In this paper, we present the design and implementation of msocket, a system that allows communicating endpoints to move across network locations arbitrarily while maintaining disruption-tolerant connectivity without any change to legacy operating systems or network infrastructure. msocket supports pre-lookup, connect-time, individual, and simultaneous mobility of one or both endpoints across multihomed network addresses, and enables seamless mobile-to-mobile communication despite the presence of address-translating middleboxes. We have implemented msocket as a user-level socket library and our evaluation shows that: (1) msocket recovers from mobility of one or both endpoint(s) in roughly two round-trips; (2) msocket's multipath scheduler greatly enhances user-perceived performance or power consumption in multihomed settings; and (3) msocket imposes little additional overhead over traditional TCP/IP sockets.
【Keywords】: Mobile communication; Middleboxes; Sockets; Mobile computing; Servers; Kernel
【Paper Link】 【Pages】:1-10
【Authors】: Chenfei Gao ; Gozde Ozcan ; Jian Tang ; Mustafa Cenk Gursoy ; Weiyi Zhang
【Abstract】: Inspired by the success of use of Virtual Machines (VMs) in cloud computing, virtualization has been introduced to wireless networking recently, enabling support for multiple Mobile Virtual Network Operators (MVNOs) via isolated slices over a shared wireless substrate. In this paper, we present design, implementation and evaluation of a novel cloud framework, R-Cloud, to enable radio resources at Base Stations (BSs) to be effectively allocated to multiple MVNOs as a service, which is referred to as Radio-as-a-Service (RaaS). R-Cloud employs a hybrid two-level control framework to enable coarse-grained and fine-grained resource allocation at the cloud and BS levels respectively. Specifically, R-Cloud not only coordinates resource allocation among BSs, MVNOs and mobile users across a Radio Access Network (RAN) and enables performance isolation by optimizing resource sharing and user association using an LP-rounding based algorithm at the cloud level; but also effectively schedule transmissions among multiple users at a BS using an optimal scheduling policy. We implemented R-Cloud over a wireless network testbed with software defined radios. It has been shown by extensive experimental and simulation results that R-Cloud can achieve effective RaaS over wireless networks and the proposed resource allocation algorithms outperform widely-used baseline solutions.
【Keywords】: Decision support systems; Conferences; Protocols
【Paper Link】 【Pages】:1-10
【Authors】: Jing Tang ; Xueyan Tang ; Junsong Yuan
【Abstract】: Information can be disseminated widely and rapidly through Online Social Networks (OSNs) with “word-of-mouth” effects. Viral marketing is such a typical application in which new products or commercial activities are advertised by some seed users in OSNs to other users in a cascading manner. The budget allocation for seed selection reflects a tradeoff between the expense and reward of viral marketing. In this paper, we define a general profit metric that naturally combines the benefit of influence spread with the cost of seed selection in viral marketing to eliminate the need for presetting the budget for seed selection. We carry out a comprehensive study on finding a set of seed nodes to maximize the profit of viral marketing. We show that the profit metric is significantly different from the influence metric in that it is no longer monotone. As a result, from the computability perspective, the problem of profit maximization is much more challenging than that of influence maximization. We develop new seed selection algorithms for profit maximization with strong approximation guarantees. Experimental evaluations with real OSN datasets demonstrate the effectiveness of our algorithms.
【Keywords】: Approximation algorithms; Greedy algorithms; Integrated circuit modeling; Measurement; Social network services; Computational modeling
【Paper Link】 【Pages】:1-10
【Authors】: Yang Wang ; Gaogang Xie ; Zhenyu Li ; Peng He ; Kavé Salamatian
【Abstract】: NFV together with SDN provides the flexibility for NFs in the way that they are deployed and managed. The flexibility enables dynamical scale in and scale out through migrating in-process flows among NFs. Due to stateful packet processing in NFs, flow migration has to guarantee loss-free and order-preserving for both flow states and packets. Existing frameworks closely coupled state transfer and packets migration, and thus fail to achieve safe and efficient migration with low overhead. This paper presents our design and implementation of a distributed flow migration framework, Transparent Flow Migration (TFM). TFM completely decouples the state transfer and packets migrations. The decoupling allows us to optimize the two processes separately and run them in parallel. TFM implements various optimizations through the TFM box, a shim layer providing transparent packet migration to NFs. Our evaluation shows that TFM guarantees loss-free and order-preserving for both scale-in and scale-out flow migration, and outperforms existing approaches with 3× smaller migration time. Besides, TFM uses small overhead and has very limited impacts on throughput of live TCP flows.
【Keywords】: Noise measurement; Process control; Protocols; Switches; Conferences; Hardware
【Paper Link】 【Pages】:1-10
【Authors】: Liuhua Chen ; Haiying Shen ; Stephen Platt
【Abstract】: In cloud datacenters, multiple Virtual Machines (VMs) are co-located in a Physical Machine (PM) to serve different applications. Prior VM consolidation methods for cloud datacenters schedule VMs mainly based on resource (CPU and memory) constraints in PMs but neglect serious shared Last Level cache contention between VMs. This may cause severe VM performance degradation due to cache thrashing and starvation for VMs. Current cache contention aware VM consolidation strategies either estimate cache contention by coarse VM classification for each individual VM without considering co-location and (or) require the aid of hardware to monitor the online miss rate of each VM. Therefore, these strategies are insufficiently accurate and (or) difficult to adopt for VM consolidation in clouds. In this paper, we formalize the problem of cache contention aware VM placement and migration in cloud datacenters using integer linear programming. We then propose a cache contention aware VM placement and migration algorithm (CacheVM). It estimates the total cache contention degree of co-locating a given VM with a group of VMs in a PM based on the cache stack distance profiles of the VMs. Then, it places the VM to the PM with the minimum cache contention degree and chooses the VM from a PM that generates the maximum cache contention degree to migrate out. We implemented CacheVM and its comparison methods on a supercomputing cluster. Trace-driven simulation and real-testbed experiments show that CacheVM outperforms other methods in terms of the number of cache misses, execution time and throughput.
【Keywords】: Cloud computing; Resource management; Degradation; Memory management; Monitoring; Radiation detectors; Virtual machining
【Paper Link】 【Pages】:1-10
【Authors】: Xiaoyu Zhang ; Wei Dong ; Wei Ren
【Abstract】: Most sensor networks employ distributed and dynamic routing protocols. The flexibility that each node can choose the best forwarder from a diverse candidate set could offer excellent routing performance when the network is highly dynamic. However, it sacrifices routing predictability since it is possible that routing loops are frequently formed. Can we increase the network predictability by controlling the network? As a step towards solving this problem, we introduce FlexCut, a flexible approach for cutting off wireless links, which essentially limits the candidate forwarder set of each node. Unlike existing SDN solutions, FlexCut introduces flexible control over existing distributed and dynamic routing protocols. FlexCut can trade arbitrary amounts of routing diversity for better network performance by exposing to network operators a parameter which quantifies the aggressiveness. We propose novel algorithms, both centralized and distributed, to cut off user-defined number of links so that loops can be alleviated while routing flexibility can be preserved to the largest extent. We evaluate FlexCut extensively by both testbed experiments and simulations. Results show that FlexCut improves the performance by 40% ~ 90% compared with a baseline algorithm in terms of our optimization goal. Results also show that FlexCut can improve the network performance of a sensor network by 20% ~ 35%, 30% ~ 50%, 25% respectively, in terms of packet delivery ratio, transmission delay and radio duty cycle.
【Keywords】: Routing; Routing protocols; Wireless sensor networks; Network topology; Conferences; Wireless communication
【Paper Link】 【Pages】:1-10
【Authors】: Jiaqi Zheng ; Hong Xu ; Xiaojun Zhu ; Guihai Chen ; Yanhui Geng
【Abstract】: We present Sentinel, a novel failure recovery system for traffic engineering that pre-computes and installs backup tunnels to improve the robustness of software defined wide area networks (WANs). When a link fails, switches locally redirect traffic to backup tunnels and recover immediately in the data plane, thus substantially reducing the transient congestion compared to reactive rescaling. On the other hand Sentinel completely avoids the bandwidth headroom required by existing proactive approaches like FFC, and improves efficiency of operating the expensive WAN. We make several technical contributions in designing Sentinel. We formulate traffic engineering with backup tunnels (TE-BT) as optimization programs. We propose an approximation algorithm to efficiently solve the problem. We further present a concrete design and implementation of the system based on Openflow group tables for backup tunnels. Extensive experiments on Mininet and numerical simulations show that similar to FFC, Sentinel reduces congestion by 45% compared with rescaling, and its algorithm runs much faster than FFC. Sentinel only introduces a small number of additional forwarding rules and can be readily implemented on today's Openflow switches.
【Keywords】: Wide area networks; Bandwidth; Approximation algorithms; Topology; Control systems; Packet loss
【Paper Link】 【Pages】:1-10
【Authors】: Taeho Lee ; Christos Pappas ; Pawel Szalachowski ; Adrian Perrig
【Abstract】: The act of communication on the Internet inevitably leaks information. In particular, network headers reveal information (e.g., source address, flow information); yet, protecting the header has proven challenging. Past research successfully protected certain fields of the headers (e.g., source address), but no proposal has attempted to eliminate flow information from the header so that packets cannot be linked to flows; flow information is systematically used to subvert privacy. Hence, we investigate the following questions: Can we design an architecture that eliminates flow-packet linkability? Can we do so without imposing impractical requirements on the network infrastructure? Our proposed architecture is based on per-packet One Time Address (OTA)-an address that a host uses to send or receive exactly one packet. Furthermore, the architecture eliminates any implicit (e.g., the standard five-tuple in TCP/UDP packets) or explicit (e.g., flow identifier) flow information from packet headers. Yet, the architecture allows the communicating hosts to demultiplex seemingly unrelated packets to flows. We have implemented the proposed architecture, and our evaluation shows that it can satisfy today's packet forwarding requirements.
【Keywords】: Encryption; Privacy; Data privacy; Conferences; Protocols; Proposals
【Paper Link】 【Pages】:1-10
【Authors】: Jose Yallouz ; Ori Rottenstreich ; Péter Babarczi ; Avi Mendelson ; Ariel Orda
【Abstract】: Network survivability has been recognized as an issue of major importance in terms of security, stability and prosperity. A crucial research problem in this context is the identification of suitable pairs of disjoint paths. Here, “disjointness” can be considered in terms of either nodes or links. Accordingly, several studies have focused on finding pairs of either link or node disjoint paths with a minimum sum of link weights. In this study, we investigate the gap between the optimal node-disjoint and link-disjoint solutions. Specifically, we formalize several optimization problems that aim at finding minimum-weight link-disjoint paths while restricting the number of its common nodes. We establish that some of these variants are computationally intractable, while for other variants we establish polynomial-time algorithmic solutions. Finally, through extensive simulations, we show that, by allowing link-disjoint paths share a few common nodes, a major improvement is obtained in terms of the quality (i.e., total weight) of the solution.
【Keywords】: Quality of service; Optimization; Conferences; Protocols; Context; Delays
【Paper Link】 【Pages】:1-10
【Authors】: Kirill Kogan ; Sergey I. Nikolenko ; Patrick Th. Eugster ; Alexander Shalimov ; Ori Rottenstreich
【Abstract】: The Internet routing ecosystem is facing substantial scalability challenges due to continuous, significant growth of the state represented in the data plane. Distributed switch architectures introduce additional constraints on efficient implementations from both lookup time and memory footprint perspectives. In this work we explore efficient FIB representations in common distributed switch architectures. Our approach introduces substantial savings in memory footprint transparently for existing hardware. Our results are supported by an extensive simulation study on real IPv4 and IPv6 FIBs.
【Keywords】: Switches; Ports (Computers); Memory management; Conferences; Protocols; Routing; Internet
【Paper Link】 【Pages】:1-2
【Authors】: Kamran Ali ; Ioannis Pefkianakis ; Alex X. Liu ; Kyu-Han Kim
【Abstract】: Powerline communication (PLC) provides inexpensive, secure and high speed network connectivity, by leveraging the existing power distribution networks inside the buildings. While PLC technology has the potential to improve connectivity and is considered a key enabler for sensing, control, and automation applications in enterprises, it has been mainly deployed for improving connectivity in homes. Deploying PLCs in enterprises is more challenging since the power distribution network is more complex as compared to homes. Moreover, existing PLC technologies such as HomePlug AV have not been designed for and evaluated in enterprise deployments. To this end, we give guidlines for designing PLC networks for providing ubiquitous connectivity in enterprises, based on measurement study of PLC performance in enterprise settings using commodity HomePlug AV PLC devices. Based on our findings, we propose that careful planning of PLC network topology, routing and spectrum sharing can significantly boost performance of enterprise PLC networks.
【Keywords】: Throughput; Performance evaluation; Modulation; Buildings; Routing; Power systems; Interference
【Paper Link】 【Pages】:1-2
【Authors】: Kai Gao ; Chen Gu ; Qiao Xiang ; Xin Wang ; Yang Richard Yang ; Jun Bi
【Abstract】: Providing an interface for network applications to access network state, Software-Defined Networking (SDN) northbound API protocol is the foundation for the development of programmable networks with adaptive applications. However, with the growing network scale and applications' need for routing state at multi-domain level, feeding complete routing states to applications would jeopardize their scalability and network providers' privacy. Thus a good routing state abstraction is needed, which must be on-demand so that different applications can receive customized abstract state suiting their needs. Moreover, it must be minimal and equivalent, i.e., containing all the necessary information for applications to make decisions as the complete state does with no redundancy. Current routing state abstractions are not on-demand, and adopt extreme aggregation approaches (e.g., the big switch) to provide a minimal abstraction with the price of severe information loss. For instance, bottleneck links shared between flows are concealed, leading applications to make sub-optimal decisions. In this paper, we design ORSAP, the first on-demand routing state abstraction protocol, through which network applications can describe their demands while Internet service providers can provide the on-demand minimal equivalent routing state accordingly. ORSAP ensures applications' scalability, protects network providers' privacy, and significantly reduces the traffic to disseminate the information. Experiments show that with ORSAP and the abstraction engine we introduced in this paper, one can achieve a state abstraction ratio of up to 60% with an extremely low computation time even with large networks and complex application queries.
【Keywords】: Routing; Protocols; Engines; Privacy; Scalability; Topology; Conferences
【Paper Link】 【Pages】:1-2
【Authors】: Peng Wang ; George Trimponias ; Hong Xu ; Hongyuan Liu ; Yanhui Geng
【Abstract】: Data center networks demand high-performance, robust, and practical data plane load balancing protocols. Despite progress, existing work falls short of satisfying these requirements. We design and evaluate Luopan, a novel sampling based load balancing protocol that overcomes these challenges. Luopan operates at flowcell granularity similar to Presto. It periodically samples a few paths to each destination switch and directs flowcells to the least congested one. By being congestion-aware, Luopan improves flow completion time (FCT), and is more robust to topological asymmetries compared to Presto. The sampling approach simplifies the protocol and makes it much more scalable for implementation in large-scale networks compared to existing congestion-aware schemes. We conduct comprehensive packet-level simulations with a production workload. The results show that Luopan consistently outperforms state-of-the-art schemes in large-scale symmetric and asymmetric topologies. Compared to Presto, Luopan with 2 samples improves the 99%ile FCT of mice flows by up to 45%, and average FCT of medium flows by ~20%.
【Keywords】: Switches; Load management; Topology; Computer networks; Communication system traffic; Probes; Protocols
【Paper Link】 【Pages】:1-2
【Authors】: Lijing Wang ; Wentao Shang ; Wenbo He ; Dongsheng Wang
【Abstract】: This poster presents a consistent replication protocol natively designed for NDN. This protocol can serve as a basic building block for designing consistent data replication, distributed lock service and other fault tolerant system over NDN networks. It also removes the burdens of implementing complex and error-prone logic of maintaining consistency from applications and greatly simplifies the design and implementation of distributed applications over NDN.
【Keywords】: Protocols; Synchronization; Peer-to-peer computing; Jacobian matrices; Conferences; Computer science; Ports (Computers)
【Paper Link】 【Pages】:1-2
【Authors】: Jia Liu ; Youlin Zhang ; Min Chen ; Shigang Chen ; Lijun Chen
【Abstract】: Traditional radio frequency identification (RFID) technologies allow tags to communicate with a reader but not among themselves. By enabling peer-to-peer communications among nearby tags, the emerging networked tags make a fundamental enhancement to today's RFID systems. This new capability supports a series of system-level functions in previously infeasible scenarios where the readers cannot cover all tags due to cost or physical limitations. This paper makes the first attempt to design a new communication model that is specifically tailored to efficient implementation of system-level functions in networked tag systems. Instead of exploiting complex mechanisms for collision detection and resolution, we propose a collision-resistent communication model (CCM) that embraces the collision in tag communications and utilizes it to merge the data from different sources in a benign way. Two fundamental applications: RFID estimation and missing-tag detection, are presented to illustrate how CCM assists efficient system-level operations in networked tag systems. Simulation results show that system-level applications through CCM outperform those through ID collection.
【Keywords】: Radiofrequency identification; Estimation; Peer-to-peer computing; Collision avoidance; Routing; Fans; Conferences
【Paper Link】 【Pages】:1-2
【Authors】: Yanan Bao ; Huasen Wu ; Albara Ah Ramli ; Bradley Wang ; Xin Liu
【Abstract】: 360-degree video transmission consumes 4~6× the bandwidth of a regular video, and thus imposes significant challenges to networks. To address this challenge, in this paper, we propose a motion-prediction-based transmission mechanism that matches network video transmission to viewer needs. Ideally, if viewer motion is perfectly known in advance, we could reduce bandwidth consumption by 80%. Practically, however, we have to address the random nature of viewer motion, in order to guarantee the quality of the viewing experience. Based on our experimental study of viewer motion (comprising 16 video clips and over 150 subjects), we propose a machine learning mechanism that predicts viewer motion. Based on such predictions, we propose a partial-content-transmission mechanism that reduces the overall bandwidth consumption while providing probabilistic performance guarantees. Real-trace-based evaluations show that the proposed scheme significantly reduces bandwidth consumption with negligible performance degradation. For example, given a failure ratio of 0.1%, we can reduce bandwidth consumption by more than 40%.
【Keywords】: Bandwidth; Videos; Artificial neural networks; Resists; Hardware; Software; Predictive models
【Paper Link】 【Pages】:1-2
【Authors】: Leonhard Nobach ; Ivica Rimac ; Volker Hilt ; David Hausheer
【Abstract】: Instance migration and scale-in/out operations in network functions virtualization (NFV) require state transfer mechanisms, which are known to cause service degradation through increased jitter and packet loss. Techniques such as packet duplication for state synchronization mitigate this problem, however, they incur significant additional costs. In this paper, we provide a novel interface to the VNF to announce “statelets” for incoming packets, which comprise only the information in the packet which is required for a VNF's internal state change. Based on this interface, we design and implement SliM, a statelet-based framework for seamless VNF migration. First evaluation results show that SliM operates seamlessly at very high dataplane utilization of physical links, up to 3 times the utilization level at which existing approaches are failing due to insufficient bandwidth for state synchronization.
【Keywords】: Payloads; Packet loss; Bandwidth; Cloud computing; Protocols; Synchronization
【Paper Link】 【Pages】:1-2
【Authors】: Radhika Sukapuram ; Gautam Barua
【Abstract】: Per-packet consistency (PPC) is preserved, if during an update to a Software Defined Network (SDN), every packet either matches the new rules added or the old rules to be deleted, but not a combination of both. We propose a general update algorithm called PPCU that preserves PPC, is concurrent and provides an all-or-nothing semantics for an update, irrespective of the execution speeds of switches and links, while confining changes to only the affected switches and affected rules.
【Keywords】: Software; Switches; Conferences; Software algorithms; Semantics; Protocols; Clocks
【Paper Link】 【Pages】:1-2
【Authors】: Kang Chen ; Haiying Shen
【Abstract】: Nodes in Delay Tolerant Networks (DTN) rely on routing utilities (e.g., probabilities of meeting nodes) to decide the packet forwarder. As the utilities reflect user privacy, nodes may be reluctant to disclose such information directly. Therefore, we propose a distributed strategy to protect the aforementioned private information in utility-based DTN routing algorithms while still guarantying the correctness of packet forwarding, namely meeting Relationship Anonymity (ReHider). We also present an enhanced version that can better prevent certain malicious behaviors (probing attack and brute-force attack). Initial analysis show the effectiveness of the proposed strategy.
【Keywords】: Routing; Encryption; Delays; Algorithm design and analysis; Mobile computing; Conferences
【Paper Link】 【Pages】:1-2
【Authors】: Tong Yang ; Alex X. Liu ; Qiaobin Fu ; Dongsheng Yang ; Steve Uhlig ; Xiaoming Li
【Abstract】: Fitting large and ever increasing routing tables in small on-chip memory is just like fitting an elephant in a box, which has been considered as impossible. In this paper, we propose the data structure of two-Dimensional Division Bloom Filter (D2BF) that can compactly encode almost all the needed information for performing IP lookup from a FIB in small on-chip memory. With pipelining, we further achieve the throughput of one packet per on-chip memory access.
【Keywords】: System-on-chip; IP networks; Ports (Computers); Random access memory; Routing; Matched filters; Conferences
【Paper Link】 【Pages】:1-2
【Authors】: Chen Tian ; Alex X. Liu ; Ali Munir ; Jie Yang
【Abstract】: We propose OpenFunction, an extensible data plane abstraction protocol for platform-independent software-defined middleboxes. The main challenge is how to abstract packet operations, flow states and event generations with elements. The key decision of OpenFunction is: actions/states/events operations should be defined in a uniform pattern and independent from each other. We implemented a working SDM system including one OpenFunction controller and OpenFunction boxes based on Netmap, DPDK and FPGA to verify OpenFunction abstraction.
【Keywords】: Middleboxes; Protocols; Hardware; Process control; Logic gates; Semantics; Technological innovation
【Paper Link】 【Pages】:1-2
【Authors】: Li Yan ; Juanjuan Zhao ; Haiying Shen ; Cheng-Zhong Xu ; Feng Luo
【Abstract】: The future generation transportation system will be featured by electrified public transportation. To fulfill metropolitan transit demands, electric vehicles (EVs) must be continuously operable without recharging downtime. Wireless Power Transfer (WPT) techniques for in-motion EV charging is a solution [1], [2]. It however brings up a challenge: how to deploy charging lanes in a metropolitan road network to minimize the deployment cost while enabling EVs' continuous operability.
【Keywords】: Trajectory; Roads; Electric vehicles; Frequency diversity; Global Positioning System; Quantization (signal)
【Paper Link】 【Pages】:1-2
【Authors】: Chengxi Gao ; Victor C. S. Lee
【Abstract】: Most of current Data Center Network (DCN) protocols leverage Explicit Congestion Notification (ECN) for congestion control. However, the majority of them assume single-queue scenario in each switch port, making their performance inferior in multiple-queue scenario. MQECN [1] solves this problem by periodically measuring the round time of queue scheduling, calculating a threshold for individual queue based on its weight and the measured round time, and adopting standard ECN in each queue. However, MQECN incurs non-negligible overhead for frequent round time measurement, and inaccurate round time measurement is unavoidable. To this end, we propose DEME, a light-weight DCN scheme for multiple-queue scenario with no need for round time measurement or per queue threshold setting. The core idea of DEME is to decouple packet marking from enqueuing, which means, when a packet is enqueued and the total queue length exceeds the standard threshold, instead of marking this newly arrived packet, we mark the head packet of the queue whose length exceeds its fair share the most. Experiments show that our light-weight DEME has similar performance with MQECN in terms of average Flow Completion Time and guarantees the fairness.
【Keywords】: Standards; Switches; Ports (Computers); Time measurement; Protocols; Throughput; Conferences
【Paper Link】 【Pages】:1-2
【Authors】: Xingliang Yuan ; Huayi Duan ; Cong Wang
【Abstract】: Outsourced middlebox services have drawn broad attentions recently from both industry and academia [1]. Despite benefiting enterprises from reduced cost and increased service scalability, such services also introduce acute security concerns, because these boxes are no longer under direct control of enterprises. Among others, one fundamental and immediate requirement is to ensure that those middleboxes always perform network functions truthfully and correctly [2]. Fulfilling this requirement will extend enterprises' visibility into remote middleboxes and promote further adoption of middlebox outsourcing services. Unfortunately, to our best knowledge, little work investigates the above problem, i.e., making network functions executed by middleboxes verifiable.
【Keywords】: Middleboxes; Pattern matching; Cryptography; Protocols; Bandwidth; Throughput
【Paper Link】 【Pages】:1-2
【Authors】: Xuan Feng ; Qiang Li ; Haining Wang ; Limin Sun
【Abstract】: Industrial control system (ICS) devices with IP addresses are accessible on the Internet and play a crucial role for critical infrastructures like power grid. However, there is a lack of deep understanding on these devices' characteristics in the cyber space. In this paper, we propose ASCEND, a search engine for online industrial control devices. ASCEND analyse 17 industrial protocols and use it to discover almost all online ICS devices in the IPv4 while reducing the noise of industrial honeypots. It provides a big picture of online ICS devices: who are using ICS devices; where they are located and what functions these ICS device have. In order to demonstrate how ASCEND works, we have implemented the prototype system and verified it in the real-world experiments.
【Keywords】: Integrated circuits; Protocols; Industrial control; Search engines; Internet; Prototypes; Indexes
【Paper Link】 【Pages】:1-2
【Authors】: Qiang Li ; Xuan Feng ; Zhi Li ; Haining Wang ; Limin Sun
【Abstract】: Nowadays, the number of visible physical devices exposed on the Internet is dynamically increasing and they play a crucial role for bridging between the cyber space and the physical world, such as network printer, Webcam, and industrial control devices. Discovering these devices brings about the deep understanding on these devices' characteristics and help secure device security in the cyber space. A device fingerprint is a prerequisite of device discovery in the Internet. However, today's online device search depends on keywords of packet head fields and the keyword collection is done manually. This impedes an accurate and large-scale device discovery, due to high human efforts and inevitable human errors, as well as the difficulty of keeping keywords complete and updated. To address this problem, we propose GUIDE, a framework to automatically generate device fingerprints based on webpages embedded in these devices. In order to demonstrate how GUIDE works, we also develop its prototype system and provide a case study which discover surveillance devices in the cyber space.
【Keywords】: Surveillance; Feature extraction; Natural language processing; Support vector machines; Conferences; Protocols; Internet
【Paper Link】 【Pages】:1-2
【Authors】: Osamah L. Barakat ; David Koll ; Xiaoming Fu
【Abstract】: SDN (Software-Defined Networking) promises easier management of complex networks. In abiding by this promise northbound APIs play a major role, as they provide abstractions to ease the process of writing network applications. As more and more of such abstractions emerge, one challenging task is to orchestrate different policies that originate from different abstractions. In an effort to provide automation for this process, recent research has suggested to replace the application-specific abstractions by a primitive, SQL-based data representation of the entire network control infrastructure. This representation can then be transformed into higher-level abstractions. However, the use of relational databases results in performance inferior to existing controllers and still requires complex application writing. To address these issues, in this work we introduce Gavel, a graph database based controller which exploits the natural graph structure of computer networks. Based on results obtained from a prototype implementation, we show that Gavel not only simplifies application writing, but at the same time offers a significantly better performance than existing schemes.
【Keywords】: Writing; Prototypes; Ports (Computers); Relational databases; Switches; Conferences
【Paper Link】 【Pages】:1-2
【Authors】: Bruhadeshwar Bezawada ; Xiaojiang Liang ; Alex X. Liu ; Rui Li
【Abstract】: Fast growing communication networks like wireless ad-hoc networks and Internet-of-things (IoT) put forth new challenges in secure communication like eavesdropping and tampering attacks. For such networks, we consider the following important problem: How to establish a shared secret group key among the nodes of a dynamically formed ad-hoc group? There are two major challenges: (a) The nodes are constrained and cannot support expensive public-key operations, especially for large groups and (b) the neighborhood of an ad-hoc node is not determined a-priori and therefore, the node needs to be able to establish a group key with any dynamic sub-set of the nodes. In this work, we describe a novel template based approach to group key establishment wherein our template is a logical shared secret distribution hierarchy built on the ad-hoc nodes prior to deployment. Our template approach ensures that any given ad-hoc node shares a distinct set of secrets with any dynamic group of nodes, regardless of the physical neighborhood, after deployment. We illustrate our approach using two instantiations of symmetric secret distribution protocols namely: sub-set and dual one-way hash chain distributions.
【Keywords】: Ad hoc networks; Protocols; Cryptography; Electronic mail; Wireless sensor networks; Conferences; Communication system security
【Paper Link】 【Pages】:1-2
【Authors】: Rui Li ; Wenjie Li ; Bruhadeshwar Bezawada ; Zheng Qin
【Abstract】: For fast packet classification, the de-facto industry standard is to use Ternary Content Addressable Memory (TCAM) chips where each chip stores one classifier rule and a given packet is checked against all such rules in parallel. In spite of the TCAM advantages, for a large number of rules, the TCAM deployment becomes expensive and the power consumption increases significantly. Therefore, it is desirable to reduce the number of TCAM rules while retaining the original classification semantics. In this work, we present efficient graph-based algorithms and data structures that allow us to capture the rule ordering relationships and iteratively compress the TCAM rules. Through extensive experiments, we show that our algorithm achieves 75% reduction of firewall rule sets on an average and even achieves an additional 24% compression on the output rule set of the state-of-the-art solutions.
【Keywords】: Sorting; Semantics; Redundancy; Compression algorithms; Publishing; Algorithm design and analysis; Conferences
【Paper Link】 【Pages】:1-2
【Authors】: Xiang-Fa Guo ; Hande Hong ; Mun Choon Chan ; Li-Shiuan Peh
【Abstract】: Mobile devices, in particular, smartphones are ubiquitous. Many of these devices are able to communicate using the Wi-Fi network. In order to support fast service discovery, Wi-Fi devices broadcast probe request frames to actively look for Wi-Fi Access Points (APs) nearby. These probe requests provide information that allows one to extract useful observation about user behavior. In this paper, we present our results obtained from a long-term passive scanning of Wi-Fi probe request packets collected in a popular outdoor food court in Singapore. The collection was done over a 32-month duration. We present measurements on the breakdown in device vendors, probe intervals, Service Set Identifier (SSID) leakage and a simple counting application.
【Keywords】: IEEE 802.11 Standard; Probes; Smart phones; Data collection; Monitoring; Manuals
【Paper Link】 【Pages】:1-2
【Authors】: Chen Tian ; Junhua Yan ; Alex X. Liu ; Yizhou Tang ; Yuankun Zhong ; Zi Li
【Abstract】: For a datacenter running a data-parallel analytic framework, minimizing job completion time (JCT) is crucial for application performance. The key observation is that JCT could be improved, if network scheduling can exploit the opportunity of decreasing the amount of occupied machine slot-time spend on communication. We propose Macroflow, a networking abstraction that captures the primitive resource granularity of data-parallel frameworks. We study the inter-macroflow scheduling problem for decreasing application JCT. We propose the Smallest-Macroflow-First (SMF) and Smallest-Average-Macroflow-First (SAMF) heuristics that greedily schedule macroflows based on their network footprint. Trace-driven simulations demonstrate that our algorithms can reduce the average and tail JCT of network-intensive jobs by up to 20% and 25%, respectively; at the same time, the throughput of computation-intensive jobs is increased by up to 2.2×.
【Keywords】: Throughput; Measurement; Ports (Computers); Processor scheduling; Conferences; Protocols; Fabrics
【Paper Link】 【Pages】:1-6
【Authors】: Ali Mohammadkhan ; K. K. Ramakrishnan ; Ashok Sunder Rajan ; Christian Maciocco
【Abstract】: As demand for wireless mobile connectivity continues to explode, cellular network infrastructure capacity requirements continue to grow. While 5G tries to address capacity requirements at the radio layer, the load on the cellular core network infrastructure (called Enhanced Packet Core (EPC)) stresses the network infrastructure. Our work examines the architecture, protocols of current cellular infrastructures and the workload on the EPC. We study the challenges in dimensioning capacity and review the design alternatives to support the significant scale up desired, even for the near future. We breakdown the workload on the network infrastructure into its components-signaling event transactions; database or lookup transactions and packet processing. We quantitatively show the control plane and data plane load on the various components of the EPC and estimate how future 5G cellular network workloads will scale. This analysis helps us to understand the scalability challenges for future 5G EPC network components. Other efforts to scale the 5G cellular network take a system view where the control plane is separated from the data path and is terminated on a centralized SDN controller. The SDN controller configures the data path on a widely distributed switching infrastructure. Our analysis of the workload informs us on the feasibility of various design alternatives and motivates our efforts to develop our clean-slate approach, called CleanG.
【Keywords】: IP networks; Protocols; Cellular networks; Ports (Computers); Conferences; Servers; Quality of service
【Paper Link】 【Pages】:1-6
【Authors】: Mari Otokura ; Kenji Leibnitz ; Yuki Koizumi ; Daichi Kominami ; Tetsuya Shimokawa ; Masayuki Murata
【Abstract】: Recently, communication network services have become increasingly diverse and dynamic. Network Function Virtualization (NFV) is an effective technique to deal with these dynamic situations. Most related work on the VNF placement problem does not consider the dynamics of requests, but only static scenarios. The important goals of the dynamic VNF placement problem include accommodating new requests following the traffic dynamics and reducing the time to calculate solutions. To tackle this problem, we utilize the concept of Modularly Varying Goals (MVG), which is based on a genetic algorithm (GA) and generates solutions that can easily adapt to time-varying goals in short time. In this paper, we propose Evolvable VNF Placement (EvoVNFP) that applies the concept of MVG to the dynamic VNF placement problem to reduce the time to obtain solutions. Results from numerical evaluations show that our method is able to better follow the dynamics of VNF requests and also reduce time until adapting to successive objectives.
【Keywords】: Delays; Genetic algorithms; Conferences; Protocols; Propagation delay; Electronic mail; Evolution (biology)
【Paper Link】 【Pages】:1-7
【Authors】: Chen Sun ; Jun Bi ; Hongxin Hu ; Zhilong Zheng
【Abstract】: As the de facto data plane technique of Software-Defined Networking (SDN), OpenFlow introduces significant programmability to enable innovative network applications. However, the simple OpenFlow data plane only maintains flow-level counters and lacks an efficient mechanism to manage network-level states, which limits its support for advanced state-aware applications. Regularly pulling whole state information from the data plane to the controller might incur untimely response to important network-level states such as CPU exhaustion, switch overload, etc and cause unnecessary traffic. To address above challenges, we introduce a novel Network-level State Management Architecture (NeSMA) to efficiently support advanced network-level state-aware applications by exploiting the opportunity of SDN central control. The data plane could be configured to check state regularly and report to the controller when triggered by state transitions. We design both sequential and parallel composition methods to deal with complex network-level states in NeSMA. To demonstrate the feasibility of our approach, we implement a software prototype of NeSMA, based on which we develop a data-center flow scheduling application. Experimental results show that NeSMA can process network-level states with low network resource consumption and high scalability without compromising packet forwarding efficiency.
【Keywords】: Switches; Monitoring; Process control; Protocols; Conferences; Software
【Paper Link】 【Pages】:1-6
【Authors】: Chien-Hsin Chen ; Chien Chen ; Ssu-Hsuan Lu ; Chien-Chao Tseng
【Abstract】: The Internet has evolved greatly in this decade. For economic benefits, the management of Internet networks needs to adapt to mass changes without huge modifications in hardware and software. Especially in campus networks, there are a variety of users and devices with different Quality of Service (QoS) requirements and management policies. Software-defined networking (SDN) decouples the data and control planes. The separated control plan resides on a centralized controller to make networks easier to manage. In this paper, a role-based SDN campus network slicing is proposed by utilizing an authentication controller and the virtualization technology of FlowVisor to divide the campus network into several virtual networks according to the types of users. However, the mapping between the devices' MAC addresses and the users' roles results in a heavy loading problem on FlowVisor. Therefore, a VLAN-based slicing is introduced in this framework to offload the workload of FlowVisor for classifying packets into corresponding slices. Packets are appended with VLAN tags for recognizing types of users to lower the overhead of FlowVisor. Analyses of experimental results show that compared with MAC-based slicing, VLAN-based slicing can reduce the flow setup latency by 14% to 60% depending on the number of devices.
【Keywords】: Authentication; Control systems; Virtualization; Protocols; Quality of service; Conferences; Internet
【Paper Link】 【Pages】:1-8
【Authors】: Wei Li ; Fengxu Lin ; Guanchao Sun
【Abstract】: The current IPsec gateway integrates many functions of IPsec operation, tunnel management and forwarding decision, which makes the IPsec gateway complicated in maintenance and deployment. The problem of maintaining such devices prevents IPsec VPN from applying widely. The emergence of SDN provides an innovative way to decouple the control plane and data plane. In this paper, a Software-Defined IPsec Gateway (SDIG) is proposed to achieve net2net IPsec VPN. Different from the traditional IPsec gateway, the SDIG device serves as a data plane equipment that just concentrates on exchanging IKE packets and encrypting/decrypting IP packets. A global view of SDIG devices can be constructed in the SDN controller by collecting the status of all devices. Therefore the controller can manage and configure SDIG devices centrally, and simplify deployment complexity. Outbound IP packets for the SDIG device can be viewed as a trigger to control the establishment of IPsec tunnels. The SDIG device and the controller exchange information through a customized southbound protocol. The prototype system of SDIG is implemented, and the preliminary experimental results show that the method is feasible and effective.
【Keywords】: Logic gates; Protocols; Security; Performance evaluation; IP networks; Conferences; Virtual private networks
【Paper Link】 【Pages】:1-6
【Authors】: Lin Wang ; Lei Jiao ; Dzmitry Kliazovich ; Pascal Bouvry
【Abstract】: The prosperous growth of the Internet-of-Things industry attracts numerous interests in employing edge clouds (a.k.a. cloudlets) to enhance the performance of mobile services and applications. Most existing research has been focused on offloading computational tasks from mobile devices to a single cloudlet or a central location, yet overlooked the issue of jointly coordinating the offloaded tasks in a system of multiple cloudlets. In this paper, we fill this gap by investigating the assignment and the scheduling of mobile computational tasks over multiple cloudlets, while optimizing the overall cost efficiency by leveraging the heterogeneity of cloudlets. We model both data transfer and computation in terms of monetary and time costs, with task deadlines guaranteed. We formulate the problem as a mixed integer program and prove its NP-hardness. By introducing admission control for the cloudlet provider to shape the system workload, we transform our problem into maximizing the task admission rate over the two coupled phases: data transfer and computation. We propose an efficient two-phase scheduling algorithm, and demonstrate that, compared with the conventional approach of always selecting the closest cloudlet, our approach achieves significantly higher admission rate with up to 20% reduction in the average cost of all offloaded tasks.
【Keywords】: Cloud computing; Silicon; Mobile handsets; Mobile communication; Conferences; Data transfer; Computational modeling
【Paper Link】 【Pages】:1-6
【Authors】: Carlos Bermejo ; Dimitris Chatzopoulos ; Pan Hui
【Abstract】: The wide spread of smart mobile devices such as tablets and phones makes mobile crowdsensing a viable approach for collecting data and monitoring phenomena of common interest. Smart devices can sense and compute their surroundings and contribute to mechanisms that examine social and collective behaviours. Crowdsensing offers a feasible alternative to exchange and compute sensing tasks and data between devices. Due to the limited resources (i.e., battery, processing power, memory) of smart mobile devices, the cooperation and hence, the performance of the mobile crowdsensing applications may be affected. We empirically show that collective incentives, such as trust (social ties) among participants, and resources availability can boost the performance of mobile crowdsensing applications. This collective incentive together with the existing cooperation enforcing mechanisms, can enhance the cooperation of the participants and incentify them to cooperate in social based mobile crowdsensing applications.
【Keywords】: Mobile communication; Sensors; Batteries; Mobile handsets; Conferences; Performance evaluation; Servers
【Paper Link】 【Pages】:1-6
【Authors】: Konglin Zhu ; Wenting Zhi ; Lin Zhang
【Abstract】: Nowadays social networking services (SNS) have become an important part of our daily-life. Thanks to the rapid development of mobile computing technologies, more and more people start to use mobile devices, e.g., smartphones and tablets, to access the SNS. Different from the traditional way, i.e., using the desktop PCs to access the web interface of the SNS, using mobile devices will introduce more flexibility. However, there is a lack of a comprehensive study to evaluate the effects of using mobile devices to access SNS. In this paper, we study the Twitter social network by comparing between the emerging mobile users and traditional web users. We have three major findings. First, by examining the tweet posting behavior, we find that mobile users are more active for posting shorter tweets, while less active for retweeting. Second, by referring to the social structure, we can see that the social network composed by mobile users are less clustered, while the radius and diameters of mobile social graph are shorter. Finally, we introduce one classic simulation scenarios, which is information diffusion in SNS. The simulation results indicate that the mobile effects actually decrease the scope of information diffusion as they are less active for message forwarding.
【Keywords】: Mobile communication; Twitter; Mobile computing; Wireless sensor networks; Mobile handsets; Conferences
【Paper Link】 【Pages】:1-5
【Authors】: Gaoyang Guan ; Wei Dong ; Yi Gao ; Jiajun Bu
【Abstract】: Rapid prototyping of IoT platforms is essential for developers to obtain first-mover advantage, validate feasibility of innovative ideas and the key technologies. In this paper, we present TinyLink, an approach for rapid and cost-effective prototyping of IoT platforms. With TinyLink, developers can specify the key platform functionalities and let TinyLink deal with the details of hardware components. Then TinyLink creates user constraints from the functionalities, as well as the inherent hardware constraints. The high level goal is to automatically select the hardware components so that they can satisfy the user requirements with the lowest cost. TinyLink solves the optimization problem and outputs a list of hardware components. We implement TinyLink and evaluate it using real-world IoT platform requirements. Results show that TinyLink achieves a lower cost compared with an existing IoT application, without affecting the functionalities of the platform.
【Keywords】: Optimization; Internet of Things; Rapid Prototyping
【Paper Link】 【Pages】:1-6
【Authors】: Kai Ryu ; Yuki Koizumi ; Toru Hasegawa
【Abstract】: Internet of Things (IoT) devices deployed everywhere are expected as potential data sources for various location-based services. This paper designs an anonymous geographical routing/forwarding mechanism to support location-based IoT services, where users collect data pieces from IoT devices by specifying their locations rather than their names/addresses. A key idea of the routing/forwarding mechanism is enabling users to collect location-dependent data without locations of users' interest being leaked.
【Keywords】: IoT (Internet of Things); NDN (Named Data Networking); Geographical Routing/Forwarding
【Paper Link】 【Pages】:1-6
【Authors】: James G. Wright ; Stephen D. Wolthusen
【Abstract】: The ISO/IEC 62351 standard provides a set of security controls and protocols for communications in smart grids based on the ISO/IEC 60870, 61850, and DNP3 standards. It offers the protection goals of confidentiality, integrity, and authentication. In this paper we perform a systematic study of the ISO/IEC 62351-3 standard regarding the use of public key infrastructure in smart grid communication. We show that the standard at present does not align with the quality of service requirements for performance and interoperability in the ISO/IEC 61850 standard and thereby may jeopardise effective operations. We demonstrate that it is possible to claim conformance with the ISO/IEC 62351-3 standard but be vulnerable to denial of service attacks arising from insufficiently specified behaviour for public key certificate validation and revocation. Further issues can give rise to downgrade attacks against cipher suites and protocols used, allowing a man-in-the-middle attacks contrary to the standard's claims.
【Keywords】: Public key; Protocols; IEC Standards; Authentication; Conferences
【Paper Link】 【Pages】:1-5
【Authors】: Pratik Narang ; Biplab Sikdar
【Abstract】: Devices that monitor and measure various system parameters or physical phenomena form an integral part of cyber-physical systems. Such devices usually operate continuously and gather important data that is often critical for the operation of the underlying system. Thus, it becomes important to understand and detect abnormal or malicious device behavior, false injection of data by an adversary, or other security threats that may lead to incorrect measurement data. This paper addresses the problem of detection of anomalies in diurnal traffic volume data in an intelligent transportation system. The proposed approach leverages the statistical properties of the data to perform anomaly detection by calculating the `local density' of the data points. Anomalous behavior in the traffic volumes reported by road segments is calculated based on sparse local density of the data points. Our approach for detecting anomalies does not require any information about the outside factors which might have influenced the data. The proposed approach has been evaluated on attacks simulated on transportation data collected by the New York State Department of Transportation. The proposed approach also extends to other cyber-physical systems where the monitored data exhibits diurnal patterns.
【Keywords】: Roads; Measurement; Monitoring; Market research; Conferences; Security; Cyber-physical systems
【Paper Link】 【Pages】:1-6
【Authors】: Pascal Poupart ; Zhitang Chen ; Priyank Jaini ; Fred Fung ; Hengky Susanto ; Yanhui Geng ; Li Chen ; Kai Chen ; Hao Jin
【Abstract】: We describe an emerging application of data mining in the context of computer networks. This application concerns the problem of predicting the size of a flow and detecting elephant flows (very large flows). Flow size is a very important statistic that can be used to improve routing, load balancing and scheduling in computer networks. Flow size prediction is particularly challenging since flow patterns continuously change and predictions must be done in real time (milliseconds) to avoid delays. We describe how to formulate the problem as an online machine learning task to continuously adjust to changes in flow traffic. We evaluate the predictive nature of a set of features and the accuracy of three online predictors based on neural networks, Gaussian process regression and online Bayesian Moment Matching on three datasets of real traffic. We also demonstrate how to use such online predictors to improve routing (i.e., reduced flow completion time) in a network simulation.
【Keywords】: Bandwidth; Neural networks; Mice; Bayes methods; Training; Conferences; Computer networks
【Paper Link】 【Pages】:1-6
【Authors】: David A. McGrew ; Blake Anderson
【Abstract】: Traditional flow monitoring provides a high-level view of network communications by reporting the addresses, ports, and byte and packet counts of a flow. This data is valuable, but it gives little insight into the actual content or context of a flow. To obtain this missing insight, we investigated intra-flow data, that is, information about events that occur inside of a flow that can be conveniently collected, stored, and analyzed within a flow monitoring framework. The focus of our work is on new types of data that are independent of protocol details, such as the lengths and arrival times of messages within a flow. These data elements have the attractive property that they apply equally well to both encrypted and unencrypted flows. Protocol-aware telemetry, specifically TLS-aware telemetry, is also analyzed. In this paper, we explore the benefits of enhanced telemetry, desirable properties of new intra-flow data features with respect to a flow monitoring system, and how best to use machine learning classifiers that operate on this data. We provide results on millions of flows processed by our open source program. Finally, we show that leveraging appropriate data features and simple machine learning models can successfully identify threats in encrypted network traffic.
【Keywords】: Cryptography; Monitoring; Malware; Radiation detectors; Conferences; Protocols; Telemetry
【Paper Link】 【Pages】:1-6
【Authors】: Min Cheng ; Qian Xu ; Jianming Lv ; Wenyin Liu ; Qing Li ; Jianping Wang
【Abstract】: Detecting anomalous Border Gateway Protocol (BGP) traffic is significantly important in improving both security and robustness of the Internet. Existing solutions apply classic classifiers to make real-time decision based on the traffic features of present moment. However, due to the frequently happening burst and noise in dynamic Internet traffic, the decision based on short-term features is not reliable. To address this problem, we propose MS-LSTM, a multi-scale Long Short-Term Memory (LSTM) model to consider the Internet flow as a multi-dimensional time sequence and learn the traffic pattern from historical features in a sliding time window. In addition, we find that adopting different time scale to preprocess the traffic flow has great impact on the performance of all classifiers. In this paper, comprehensive experiments are conducted and the results show that a proper time scale can improve about 10% accuracy of LSTM as well as all conventional machine learning methods. Particularly, MS-LSTM with optimal time scale 8 can achieve 99.5% accuracy in the best case.
【Keywords】: Hidden Markov models; Time series analysis; Internet; Conferences; Computational modeling; Logic gates; Protocols
【Paper Link】 【Pages】:1-5
【Authors】: Pedro Amaral ; João Dinis ; Paulo Pinto ; Luis Bernardo ; Joao Tavares ; Henrique S. Mamede
【Abstract】: Software Defined Networks (SDNs) provides a separation between the control plane and the forwarding plane of networks. The software implementation of the control plane and the built in data collection mechanisms of the OpenFlow protocol promise to be excellent tools to implement Machine Learning (ML) network control applications. A first step in that direction is to understand the type of data that can be collected in SDNs and how information can be learned from that data. In this work we describe a simple architecture deployed in an enterprise network that gathers traffic data using the OpenFlow protocol. We present the data-sets that can be obtained and show how several ML techniques can be applied to it for traffic classification. The results indicate that high accuracy classification can be obtained with the data-sets using supervised learning.
【Keywords】: Traffic Classification; Software defined Networks; Machine Learning; Data Analysis
【Paper Link】 【Pages】:1-6
【Authors】: Zhitang Chen ; Jiayao Wen ; Yanhui Geng
【Abstract】: Network traffic volume estimation and prediction is an important research topic that attracts persistent attention from the networking community and the machine learning community. Although there has been extensive work on estimating or predicting the traffic matrix using time series models, low rank matrix decomposition et. al, to the best of our knowledge, there is few work investigating the problem whether we are able to estimate and predict the traffic volume based on some statistics of the traffic which are much less costly to collect, for example, the flow counts. In this paper, we propose to model the relationship between the traffic volume and simple statistics about flows using a Hidden Markov Model based on which we can avoid direct measurement of the traffic volume but instead we estimate and predict the hidden traffic volume based on those simple flow statistics which are collected by some sketch techniques. We demonstrate the feasibility and effectiveness of our proposed method using some semi-simulation and real data experimental results.
【Keywords】: Hidden Markov models; Volume measurement; Predictive models; Conferences; Tomography; Kernel; Biological neural networks
【Paper Link】 【Pages】:1-6
【Authors】: Jaeyoung Choi ; Sangwoo Moon ; Jinwoo Shin ; Yung Yi
【Abstract】: Recently, the problem of detecting the rumor source in a social network has been much studied, where it has been shown that the detection probability cannot be beyond 31% even for regular trees. In this paper, we study the impact of an anti-rumor on the rumor source detection. We first show a negative result: the anti-rumor's diffusion does not increase the detection probability under Maximum-Likelihood-Estimator (MLE) when the number of infected nodes are sufficiently large by passive diffusion that the anti-rumor starts to be spread by a special node, called the protector, after is reached by the rumor. We next consider the case when the distance between the rumor source and the protector follows a certain type of distribution, but its parameter is hidden. Then, we propose the following learning algorithm: a) learn the distance distribution parameters under MLE, and b) detect the rumor source under Maximum-A-Posterior-Estimator (MAPE) based on the learnt parameters. We provide an analytic characterization of the rumor source detection probability for regular trees under the proposed algorithm, where MAPE outperforms MLE by up to 50% for 3-regular trees and by up to 63% when the degree of the regular tree becomes large. We demonstrate our theoretical findings through numerical results, and further present the simulation results for general topologies (e.g., Facebook and US power grid networks) even without knowledge of the distance distribution, showing that under a simple protector placement algorithm, MAPE produces the detection probability much larger than that by MLE.
【Keywords】: Maximum likelihood estimation; Conferences; Social network services; Network topology; Topology; Internet; Protocols