Network configurations are constantly changing, and each change poses a risk of catastrophic network outages. Consequently, the networking community has put significant effort into developing and optimizing configuration verifiers. However, we observe existing configuration verifiers still have a significant drawback: they are not optimized for configuration changes. That is, they always check a snapshot of network configuration from scratch, even though the configuration often changes slightly since the last verification. In this paper, we demonstrate the benefits, opportunities, and challenges of incremental network configuration verification (INCV). We also demonstrate the feasibility of INCV by introducing RealConfig, an incremental configuration verifier that can check configuration changes within one second.

There is an increasing trend that enterprises outsource their middlebox processing to a cloud for lower cost and easier management. However, outsourcing middleboxes brings threats to the enterprise's private information, including the traffic and rules of middleboxes, all of which are visible within the cloud. Existing solutions for secure middlebox outsourcing either incur significant performance overhead or do not support incremental updates. In this article, we present a secure and dynamic middlebox outsourcing framework, SICS, short for Secure In-Cloud Service. SICS encrypts each packet header and uses a label for in-cloud rule matching, which enables the cloud to perform its functionalities correctly with minimum header information leakage. Evaluation results show that SICS achieves higher throughput, faster construction and update speed, and lower resource overhead at the enterprise and in the cloud when compared with existing solutions.

Identifying the network-wide forwarding behaviors of a packet is essential for many network management applications, including rule verification, policy enforcement, attack detection, traffic engineering, and fault localization. Current tools that can perform packet behavior identification either incur large time and memory costs or do not support real-time updates. In this paper, we present AP Classifier, a control plane tool for packet behavior identification. AP Classifier is developed based on the concept of atomic predicates, which can be used to characterize the forwarding behaviors of packets. Experiments using the data plane network state of two real networks show that the processing speed of AP Classifier is faster than existing tools by at least an order of magnitude. Furthermore, AP Classifier uses very small memory and is able to support real-time updates.

Packet transformers are widely used in ISPs, datacenter infrastructures, and layer-2 networks. Existing network verification tools do not scale to large networks with transformers (e.g., MPLS, IP-in-IP, and NAT). Toward scalable verification, we conceived a novel packet equivalence relation. For networks with packet transformers, we first present a formal definition of the packet equivalence relation. Our transformer model is general, including most transformers used in real networks. We also present a new definition of atomic predicates that specify the coarsest equivalence classes of packets in the packet space. We designed an algorithm for computing these atomic predicates. We built a verifier, named Atomic Predicates for Transformers, and evaluated its performance using four network data sets with MPLS tunnels, IP-in-IP tunnels, and NATs. For a provider cone data set with 11.6 million forwarding rules, 92 routers, 1920 duplex ports, and 40 MPLS tunnels which use 170 transformers, APT used only 0.065 s, on average, to compute the reachability tree from a source port to all other ports for all packets and perform loop detection as well. For the Stanford and Internet2 data sets with NATs, APT is faster than HSA (Hassel in C implementation) by two to three orders of magnitude. By working with atomic predicates instead of individual packets, APT achieves verification performance gains by orders of magnitude.

Network management will benefit from automated tools based upon formal methods. Several such tools have been published in the literature. We present a new formal method for a new tool, Atomic Predicates (AP) Verifier, which is much more time and space efficient than existing tools. Given a set of predicates representing packet filters, AP Verifier computes a set of atomic predicates, which is minimum and unique. The use of atomic predicates dramatically speeds up computation of network reachability. We evaluated the performance of AP Verifier using forwarding tables and ACLs from three large real networks. The atomic predicate sets of these networks were computed very quickly and their sizes are surprisingly small. Real networks are subject to dynamic state changes over time as a result of rule insertion and deletion by protocols and operators, failure and recovery of links and boxes, etc. In a software-defined network, the network state can be observed in real time and thus may be controlled in real time. AP Verifier includes algorithms to process such events and check compliance with network policies and properties in real time. We compare time and space costs of AP Verifier with Header Space and NetPlumber using datasets from the real networks.

Identifying the network-wide forwarding behaviors of a packet is essential for many network management applications, including rule verification, policy enforcement, attack detection, traffic engineering, and fault localization. Current tools that can perform packet behavior identification either incur large time and memory costs or do not support real-time updates. In this paper we present AP Classifier, a control plane tool for packet behavior identification. AP Classifier is developed based on the concept of atomic predicates which can be used to characterize the forwarding behaviors of packets. Experiments using the data plane network state of two real networks show that the processing speed of AP Classifier is faster than existing tools by at least an order of magnitude. Furthermore, AP Classifier uses very small memory and is able to support real-time updates.

Applications running on the same Wireless Sensor Network (WSN) platform usually have different Quality of Service (QoS) requirements. Two basic requirements are low delay and high data integrity. However, in most situations, these two requirements cannot be satisfied simultaneously. In this paper, based on the concept ofpotentialin physics, we propose IDDR, a multi-path dynamic routing algorithm, to resolve this conflict. By constructing a virtual hybrid potential field, IDDR separates packets of applications with different QoS requirements according to the weight assigned to each packet, and routes them towards the sink through different paths to improve the data fidelity for integrity-sensitive applications as well as reduce the end-to-end delay for delay-sensitive ones. Using the Lyapunov drift technique, we prove that IDDR is stable. Simulation results demonstrate that IDDR provides data integrity and delay differentiated services.

To debug reach ability problems, a network operator often asks operators of other networks for help by telephone or email. We present a new protocol, COVE, for automating the exchange of data plane reach ability information between networks in a business relationship. A network deploys COVE in a host (its local verifier) which can construct both forward and reverse reach ability trees in the Internet data plane for the network's provider/customer cone. Each edge in a tree is annotated by a set of packets that can traverse the edge. COVE was designed with partial deployment in mind. Reachable networks that do not deploy COVE are leaf nodes in reach ability trees. Partial trees are useful. We constructed an Internet dataset of 2, 649 ASes and performed experiments in which up to 170 workstations ran COVE as local verifiers to construct forward and reverse provider (also customer) trees for ASes. The results of these experiments demonstrate scalability of COVE to very large ASes in the Internet. We illustrate applications of COVE to solve the following network management problems: evaluating inbound load balancing policies, what-if analysis before adding a new provider, finding additional paths, configuring default routes as backup, black hole detection, and persistent forwarding loop detection.

Network management will benefit from automated tools based upon formal methods. Several such tools have been published in the literature. We present a new formal method for a new tool, Atomic Predicates (AP) Verifier, which is much more time and space efficient than existing tools. Given a set of predicates representing packet filters, AP Verifier computes a set of atomic predicates, which is minimum and unique. We evaluated the performance of AP Verifier using forwarding tables and ACLs from three large real networks. The atomic predicate sets of these networks were computed very quickly and their sizes are surprisingly small. The use of atomic predicates dramatically speeds up computation of network reachability. On the average, AP Verifier is 3 orders of magnitude faster than an existing tool, Hassel in C. It also uses 2 to 3 orders of magnitude less memory than Hassel in C.

Network management will benefit from automated tools based upon formal methods. Several such tools have been published in the literature. We present a new formal method for a new tool, Atomic Predicates (AP) Verifier, which is much more time and space efficient than existing tools. Given a set of predicates representing packet filters, AP Verifier computes a set of atomic predicates, which is minimum and unique. The use of atomic predicates dramatically speeds up computation of network reachability. We evaluated the performance of AP Verifier using forwarding tables and ACLs from three large real networks. The atomic predicate sets of these networks were computed very quickly and their sizes are surprisingly small. Real networks are subject to dynamic state changes over time as a result of rule insertion and deletion by protocols and operators, failure and recovery of links and boxes, etc. In a software-defined network, the network state can be observed in real time and thus may be controlled in real time. AP Verifier includes algorithms to process such events and check compliance with network policies and properties in real time. We compare time and space costs of AP Verifier with NetPlumber using datasets from the real networks.

In this paper, we investigate the Frequency Domain Packet Scheduling (FDPS) problem for 3GPP Long Term Evolution (LTE) Uplink (UL). Instead of studying a specific scheduling policy, we provide a unified approach to tackle this issue. First, we formalize a general LTE UL FDPS problem, which is suitable for various scheduling policies. Then, we prove that the problem is MAX SNP-hard, which implies that approximation algorithms with constant approximation ratios are the best that we can hope for. Therefore, we design two approximation algorithms, both of which have polynomial runtime. The first algorithm is based on a simple greedy method. The second one is based on the Local Ratio (L-R) technique and it can approximately solve the LTE UL FDPS problem with an approximation ratio of 2. To further analyze the stability of the 2-approximation L-R algorithm, we derive a specific FDPS problem, which incorporates the queue length and channel quality information. We utilize the Lyapunov Drift to prove the L-R algorithm is stable for any $((\omega_0, \epsilon_0))$-admissible LTE UL systems. The simulation results indicate good performance of the L-R scheduler.

In this paper, we formalize a general Frequency Domain Packet Scheduling (FDPS) problem for 3GPP LTE Downlink (DL). The DL FDPS problem incorporates the SingleUser Multiple Input Multiple Output (SU-MIMO) technique, and can express various scheduling policies, including the Proportional-Fair metric, the MaxWeight scheduling, etc. For LTE DL SU-MIMO, the constraint of selecting only one MIMO mode (transmit diversity or spatial multiplexing) per user in each transmission time interval (TTI) increases the hardness of the FDPS problem. We prove the problem is MAX SNP-hard, which implies approximation algorithms with constant approximation ratios are the best we can expect. Subsequently, we propose an approximation algorithm of polynomial runtime. The solution is based on a greedy method for maximizing a non-decreasing submodular function over a matroid. The algorithm can solve the general DL FDPS problem with an approximation ratio of 4. We implement the proposed algorithm and compare its performance with other well-known schedulers.

In this paper, we investigate the frequency-domain packet scheduling (FDPS) problem for 3GPP LTE Uplink (UL). Instead of studying a specific scheduling policy, we provide a unified approach to tackle this issue. First we formalize a general LTE UL FDPS problem which is suitable for various scheduling policies. Then we prove that the problem is MAX SNP-hard, which implies that approximation algorithms with constant approximation ratios are the best that we can hope for. Therefore we design two approximation algorithms, both of which have polynomial runtime. Subsequently, we analyze the two algorithms and find their approximation ratios. The first algorithm is easy to follow, since it is based on a simple greedy method. The second one is based on the local ratio technique and it can approximately solve the LTE UL FDPS problem with a approximation ratio of 2.

Energy efficient communication is a key requirement of energy-constrained underwater sensor networks (UWSNs). In this paper, we show that the cooperative diversity, which is conventionally utilized to improve reliability in UWSNs, can be employed to reduce energy consumption and preserve a reasonable level of data reliability and communication delay. We first elucidate in what circumstances the cooperative diversity saves energy compared to the non-cooperative diversity. We show that this largely depends on parameters such as distance between the source and the destination node, the location of potential partner node, and the requirements of reliability and communication delay. Second, we propose a simple but effective cooperation scheme to take advantage of the cooperative diversity. The cooperation diversity can achieve a near-optimal energy saving in some circumstances, and it is no worse than the non-cooperative diversity in all cases. Our work provides instructive theoretical guidelines for designing practical UWSNs.

Seamless handover is one of the most attractive research fields in B3G systems. Many mechanisms are proposed to provide certain QoS guarantees in handovers of mobile systems, which would also introduce new threats, such as DoS and DDOS attacks. In this paper, we extend a cookie-based scheme to protect systems from DoS and DDoS attacks. We also adopt a novel queuing network model to analyze our scheme by estimating two essential metrics, i.e. the mean total response time and the mean queue length of MAP. Numerical results indicate that our mechanism works better than the traditional cookie-based scheme and it could effectively help networks defend against abnormal attacks in the handover process.

BitTorrent is one of the most popular P2P file sharing systems. However, chunk-based file sharing mode makes it difficult to detect content pollution and prevent pollution dissemination during downloading process. In this paper, we propose an early warning scheme against pollution dissemination for BitTorrent. Our idea is to build an early cooperative warning mechanism and rapidly spread alert message among peers in the swarm when pollution is detected at the early stage, which is called "early warning, quickly reacting". The performance evaluation based on fluid model shows the necessity and effectiveness of our scheme, which effectively reduces the traffic abusement and restricts pollution dissemination in BitTorrent-like P2P networks. Another advantage of our solution is that it can handle cheating behaviors made by malicious or unconscious peers, which shows the robustness of our solution.

In this paper, we propose hierarchical Stochastic Game Nets, and use it to model and analyze the security issues in online banking system. Firstly, the definition and modeling algorithm of hierarchical Stochastic Game Nets are given. In which, some theorems are proved. Then we apply hierarchical Stochastic Game Nets to describe the attack and defense course in the online banking. Finally we analyze the attack time and attack probability in the online banking quantitatively based on the model successfully.

Underwater communication is a challenging topic due to its singular channel characteristics. Most protocols used in terrestrial wireless communication can not be directly applied in the underwater world. In this paper, we focus on the issue of energy efficient transmission in underwater sensor networks (UWSNs) and analyze this problem in a rigorous and theoretical way. We formalize an optimization problem which aims to minimize energy consumption and simultaneously accounts for other performance metrics such as the data reliability and the communication delay. With the help of Karush-Kuhn-Tucker conditions (KKT conditions), we derive a simple and explicit, but nevertheless accurate, approximate solution under reasonable assumptions. This approximate solution provides theoretical guidelines for designing durable and reliable UWSNs. Our result also shows that reliability and communication delay are crucial factors to the energy consumption for transmission.

Multiple transmission rates are supported in the current 802.11 WLANs, which allows stations to exploit different rates in an adaptive manner to cope with the variability of wireless channels and achieve the higher system throughput. Many efforts have been made at rate adaptation in the literature. The design of rate adaptation algorithms needs to take four basic issues into account. In this paper, by properly addressing the four issues, we present a novel rate adaptation algorithm, idle detection based optimal throughput rate adaptation (ITRA). We apply a comprehensive approach to designing the rate adaptation mechanism and attempt to maximize the overall system throughput. ITRA is furnished with two instructive features. First, ITRA modifies the conventional exponential backoff rule to a constant one. With the help of constant contention window (CW), ITRA can discriminate collisions from channel errors, and does not need RTS/CTS handshakes which are adopted by many existing works. We derive an explicit relation between the throughput and the CW size, and choose the CW size to optimize the throughput as well as improve the fairness. Secondly, ITRA directly estimates the current network throughput and changes transmission rate according to the estimation. Since the fundamental purpose of rate adaptation is to improve the network throughput, using the throughput as the metric is more straightforward than applying indirect criteria like frame transmission statistics or PHY metrics. We evaluate our proposed scheme by simulation, and the result shows that ITRA achieves satisfactory performance.

Most previous models about wireless channels are mainly adopted to obtain average packet error rates or to generate artificial network traces. However, when we combine packet group transmission with error correcting mechanisms, the steady packet error rate (PER) is not accurate enough to depict the short-term error event. In this paper, we propose a Markov chain model for group transmission to indicate influences of group length N and initial channel state on transmission reliability. Based on the model, we prove that the difference between steady PER and packet error rate within a group (PERG) is O(1/N), which can be used to estimate group length under a certain error rate constraint. Finally, we apply the model to compare the multipath transmission with the single-path transmission, and investigate an extreme case where the multipath way is less reliable than the single-path way.

As a potentially competitive technique, erasure coding has been employed in wireless sensor networks (WSNs) to enhance transmission reliability. In this paper, to design a practical and efficient redundancy mechanism in WSNs, we firstly provide a theoretical study of packet delivery probability and average energy consumption for retransmission and redundancy mechanisms. The theoretical results indicate that in WSNs, the adaptive redundancy coding mechanism is more energy efficient than retransmission while keeping the same level of reliability in most scenarios. Then based on the mapping table and two basic design principles obtained from the theoretical analysis, we propose a reliable transport protocol ARRTP which combines the adaptive redundancy mechanism and partial retransmission. The simulation and trace-driven results both verify that when the loss probability varies from low to high, our protocol provides reliability with comparably lower energy consumption. Furthermore, compared with fixed redundancy degrees, the robustness of the adaptive mechanism are also evaluated.

More attention has been paid to congestion control in the emerging area of wireless sensor network (WSN). However, most research works in the past stayed at the level of the current algorithms design or modification, and seldom sought solutions on the viewpoint of architecture. In this paper, Backpressure(BP) under Active Network(AN) architecture is used to make congestion control more responsive to detect/recover congestion in WSN. We design a simple Active Backpressure mechanism to allocate bandwidth Proportional to the Size of tree (ABPS), and we present a fluid-based analytical model of ABPS using stochastic differential equations. ABPS introduces programs in each data packet that tell nodes how to react to congestion, and quickly converge to a fair and efficient rate. We demonstrate a deterministic approach to analyse the stochastic model, in which we obtain a set of ordinary differential equations from our model, and we derive the average behavior of queue length and flow throughput from the ordinary differential equations. Finally, we evaluate ABPS extensively on a 50-node wireless sensor network. Simulation results validate the effectiveness of our ABPS and match well with the theoretic analysis.