The Large Vision-Language Model (LVLM) integrates computer vision and natural language processing techniques, offering substantial application potential. However, these models demand extensive resources during inference. Adaptive attention techniques can dynamically reduce computational redundancy and thus improve efficiency. Although current adaptive attention methods significantly reduce the memory requirements of Transformer-based language models, they are not tailored for LVLMs. We observe that LVLMs generate responses from both remote image tokens and local text tokens, and different modalities have different attention patterns. This observation inspires us to manage the attention for each modality separately. Specifically, for visual input, we store the cache of potentially useful information but only compute the most critical parts. For language input, we care more about local information. Based on our observation and analysis of vision-language attention patterns, we develop A-VL, a plug-and-play adaptive attention tailored for LVLM inference. Extensive evaluations on three vision-language tasks and five datasets show the effectiveness of our designs. Our approach A-VL outperforms existing adaptive attention methods in reducing memory usage and computational load without compromising performance.

Large Language Models (LLMs) have shown remarkable capabilities in text and multimodal processing, yet they fundamentally lack physical awareness--understanding of real-world physical phenomena. In this work, we present ACORN, a framework that teaches LLMs physical awareness through sound, focusing on fundamental physical phenomena like the Doppler effect, multipath effect, and spatial relationships. To overcome data scarcity, ACORN introduce a physics-based simulator combining real-world sound sources with controlled physical channels to generate diverse training data. Using this simulator, we build AQA-PHY, a comprehensive Audio Question-Answer dataset, and propose an audio encoder that processes both magnitude and phase information. By connecting our audio encoder to state-of-the-art LLMs, we demonstrate reasonable results in both simulated and real-world tasks, such as line-of-sight detection, Doppler effect estimation, and Direction-of-Arrival estimation, paving the way for enabling LLMs to understand physical world.

We present a novel approach to monitor the Body in White (BiW), the fundamental metallic structure of a vehicle. Existing monitoring methods, including both wired and wireless sensor systems, face significant challenges due to integration complexity, weight considerations, material costs, and signal blockage within the metallic environment. To overcome these limitations, we introduce Arach-Net, an acoustic backscatter network that leverages the conductive properties of the BiW to propagate vibration signals for energy transfer and data communication. This system comprises battery-free tags that harvest energy from BiW vibrations and utilize a backscatter technique for efficient communication, thereby eliminating the need for external power sources and reducing the power consumption. We address key challenges such as power sufficiency for tag activation and sustained operation, and collision reduction in network communication, by designing an ultra-low power backscatter tag and a distributed slot allocation protocol. We implement ArachNet, and deploy 12 tags onto the BiW of an electric SUV car. The evaluation results show that the power consumption of the tag is 51.0 μW for uplink packet transmission, and 24.8 μW for downlink packet reception. With our network protocol, the slot utilization can be up to 81.2%.

Middleboxes are becoming indispensable in modern networks. However, programming the network stack of middleboxes to support emerging transport protocols and flexible stack hierarchy is still a daunting task. To this end, we propose Rubik, a language that greatly facilitates the task of middlebox stack programming. Different from existing hand-written approaches, Rubik offers various high-level constructs for relieving the operators from dealing with massive native code, so that they can focus on specifying their processing intents. We show that using Rubik one can program the middlebox stack with minor effort, e.g., 250 lines of code for a complete TCP/IP stack, which is a reduction of 2 orders of magnitude compared to the hand-written versions. To maintain a high performance, we conduct extensive optimizations at the middle-and back-end of the compiler. Experiments show that the stacks generated by Rubik outperform the mature hand-written stacks by at least 30% in throughput.

In this paper, we demonstrate how Hyperledger Fabric, one of the most popular permissioned blockchains, can benefit from network-attached acceleration. The scalability and peak performance of Fabric is primarily limited by the bottlenecks present in its block validation/commit phase. We propose Blockchain Machine, a hardware accelerator coupled with a hardware-friendly communication protocol, to act as the validator peer. It can be adapted to applications and their smart contracts, and is targeted for a server with network-attached FPGA acceleration card. The Blockchain Machine retrieves blocks and transactions in hardware directly from the network interface, which are then validated through a configurable and efficient block-level and transaction-level pipeline. The validation results are then transferred to the host CPU where non-bottleneck operations are executed. From our implementation integrated with Fabric v1.4 LTS, we observed up to 12× speedup in block validation when compared to software-only validator peer, with commit throughput of up to 68,900 tps. Our work provides an acceleration platform that will foster further research on hardware acceleration of permissioned blockchains.

Network programming languages (NPLs) empower operators to program network data planes (NDPs) with unprecedented efficiency. Currently, various NPLs and NDPs coexist and no one can prevail over others in the short future. Such diversity is raising many problems including: (1) programs written with different NPLs can hardly interoperate in the same network, (2) most NPLs are bound to specific NDPs, hindering their independent evolution, and (3) compilation techniques cannot be readily reused, resulting in much wasteful work. These problems are mostly owing to the lack of modularity in the compilers, where the missing part is an intermediate representation (IR) for NPLs. To this end, we proposeNetwork Transaction Automaton (NTA), a highly-expressive and language-independent IR, and show it can express semantics of 7 mainstream NPLs. Then, we designCODER, a modular compiler based on NTA, which currently supports 2 NPLs and 3 NDPs. Experiments with real and synthetic programs show CODER can correctly compile those programs for real networks within moderate time.

TCAM is widely used for flow table lookup in Software-Defined Networking (SDN) switches for datacenter and enterprise networks. While its lookup throughput is unparalleled, TCAM updating, particularly for new rule insertions, can impair the overall system performance. A rule insertion entails two steps: 1) Computing the rule moving operations; and 2) Interrupting the TCAM lookups to apply the operations. In previous work, the performance gain on one step is always at the expense of the performance loss on the other. However, update throughput and latency depend on both. In this paper, we present a faster and more balanced TCAM update scheme, which not only achieves the shortest interrupt time so far but also significantly reduces the computation time. By using a novel sequential stack, FastUp reduces the time and space complexity of the state-of-the-art schemes from$O(m^{2})$and$O(m)$to$O(m\log h)$and$O(h)$, respectively, where$h << m$. Evaluations show that FastUp shortens the computation time and the interrupt time by$100\times$and$1.6\times$, respectively, which is equivalent to update delay${15\times}$reduction and$\mathbf{10\times}$update throughput gain against the state-of-the-art schemes. Moreover, we debunk a common mistake and show the dynamic programming based algorithm cannot be used to solve the reorder problem, and instead we use a bidirectional rule moving method to address the problem. In addition, we propose a practical method to find the theoretical lower bound of interrupt time in relatively large TCAM, which can be used to evaluate the optimality degree of TCAM update schemes. Evaluations show that FastUp achieves 90 % optimality.

A crucial requirement for Software Defined Network (SDN) is that data plane forwarding behaviors should always agree with control plane policies. Such requirement cannot be met when there areforwarding anomalies, where packets deviate from the paths specified by the controller. Most anomaly detection methods for SDN install dedicated rules to collect statistics of each flow, and check whether the statistics conform to the “flow conservation principle”. We find these methods have a limited detection scope: they look at one flow each time, thus can only check a small number of flows simultaneously. In addition, dedicated rules for statistics collection can impose a large overhead on flow tables of SDN switches. To this end, this paper presents FOCES, a network-wide forwarding anomaly detection and localization method in SDN. Different from previous methods, FOCES applies a new kind of flow conservation principle at network wide, and can check forwarding behaviors ofallflows in the network simultaneously, without installing any dedicated rules. Finally, FOCES applies a voting-based method to localize malicious switches when anomalies are detected. Experiments with four network topologies show that FOCES can achieve a detection precision higher than 90%, when the packet loss rate is no larger than 10%, and a localization accuracy of around 80% when the packet loss rate is no larger than 5%.

Network programming languages (NPLs) empower operators to program network data planes (NDPs) with unprecedented efficiency. Currently, various NPLs and NDPs coexist and no one can prevail over others in the short future. Such diversity is raising many problems including: (1) programs written with different languages can hardly interoperate in the same network, and (2) most NPLs are bound to specific NDPs, hindering their independent evolution. These problems are mostly owing to the lack of modularity in the compilers, where the missing part is an intermediate representation (IR) for NPLs. To this end, we propose Network Transaction Automaton (NTA), a highly-expressive and language-independent representation as the IR. We show that NTA can express semantics of 6 mainstream NPLs, and can be composed efficiently without any semantics loss.

Network programming languages (NPLs) empower operators to program network data planes (NDPs) with unprecedented efficiency. Currently, various NPLs and NDPs coexist and no one can prevail over others in the short future. Such diversity is raising many problems including: (1) programs written with different NPLs can hardly interoperate in the same network, (2) most NPLs are bound to specific NDPs, hindering their independent evolution, and (3) compilation techniques cannot be readily reused, resulting in much wasteful work. These problems are mostly owing to the lack of modularity in the compilers, where the missing part is an intermediate representation (IR) for NPLs. To this end, we propose Network Transaction Automaton (NTA), a highly-expressive and language-independent IR, and show it can express semantics of 7 mainstream NPLs. Then, we design CODER, a modular compiler based on NTA, which currently supports 2 NPLs and 3 NDPs. Experiments with real and synthetic network programs show CODER is efficient and scalable.

While widely used for flow tables in SDN switches, TCAM faces challenges for rule updates. Both the computation time and interrupt time need to be short. We propose FastUp, a new TCAM update algorithm, which improves the previous dynamic programming-based algorithms. Evaluations show that FastUp shortens the computation time by 40~100× and the interrupt time by 1.2~2.5×. In addition, we are the first to prove the NP-hardness of the optimal TCAM update problem, and provide a practical method to evaluate an algorithm's degree of optimality. Experiments show that FastUp's optimality reaches 90%.

Programmable data planes, PDPs, enable an unprecedented level of flexibility and have emerged as a promising alternative to existing data planes. Despite the rapid development and prototyping cycles that PDPs promote, the existing PDP ecosystem lacks appropriate abstractions and algorithms to support these rapid testing and deployment life-cycles. In this paper, we propose P4Visor, a lightweight virtualization abstraction that provides testing primitives as a first-order citizen of the PDP ecosystem. P4Visor can efficiently support multiple PDP programs through a combination of compiler optimizations and program analysis-based algorithms. P4Visor's algorithm improves over state-of-the-art techniques by significantly reducing the resource overheads associated with embedding numerous versions of a PDP program into hardware. To demonstrate the efficiency and viability of P4Visor, we implemented and evaluated P4Visor on both a software switch and an FPGA-based hardware switch using fourteen of different PDP programs. Our results demonstrate that P4Visor introduces minimal overheads and is one order of magnitude more efficient than existing PDPs primitives for concurrently supporting multiple programs.

One major research challenge for Software-Defined Networking is to properly deploy and efficiently utilize multiple controllers to improve resource utilization and maintain high network performance. While addressing this Controller Placement Problem (CPP), many existing studies overlooked the importance and influence of the Controller Scheduling Problem (CSP) with the central focus on proper distribution of requests from all switches among all controllers. In this paper, we define a new Controller Placement and Scheduling Problem (CPSP), emphasizing on the necessity and importance of tackling both CPP and CSP simultaneously in a coherent framework. To solve CPSP, we must seek a combination of solutions to both problems. Particularly, CSP is addressed based on a given solution to CPP and a Gradient-Descent-based (GD-based) scheduling algorithm is developed to optimize the probabilistic distribution of requests among all controllers. Built on the GD-based approach for controller scheduling, a Clustering-based Genetic Algorithm with Cooperative Clusters (CGA-CC) is further proposed to address CPP. In comparison to the majority of heuristic methods developed in the past, CGA-CC has two unique strengths. Specifically, it partitions a large network to substantially reduce the search space of the Genetic Algorithm (GA), resulting in fast identification of high-quality CPP solutions. Moreover, a greedy load re-distribution mechanism is developed to handle unexpected demand variations by dynamically forwarding bursting requests to neighboring sub-networks. Extensive simulations showed that our algorithms can significantly outperform several existing algorithms, including a recently proposed approach called Multi-controller Selection and Placement Algorithm (MSPA), in terms of both response time and controller utilization.

Extracting fields from layer 7 protocols such as HTTP, known as L7 parsing, is the key to many critical network applications. However, existing L7 parsing techniques center around protocol specifications, thereby incurring large human efforts in specifying data format and high computational/memory costs that poorly scale with the explosive number of L7 protocols. To this end, this paper introduces a new framework namedcontent-based L7 parsing, where the content instead of the format becomes the first class citizen. Under this framework, users only need to label what content they are interested in, and the parser learns an extraction model from the users’ labeling behaviors. Since the parser is specification-independent, both the human effort and computational/memory costs can be dramatically reduced. To realize content-based L7 parsing, we propose REPLAY which builds on recurrent neural network (RNN) and addresses a series of technical challenges like large labeling overhead and slow parsing speed. We prototype REPLAY on GPUs, and show it can achieve a precision of 98% and a recall of 97%, with a throughput as high as 12Gbps for diverse extraction tasks.

Blockchain technologies are on the rise, and Hyperledger Fabric is one of the most popular permissioned blockchain platforms. In this paper, we re-architect the validation phase of Fabric based on our analysis from fine-grained breakdown of the validation phase's latency. Our optimized validation phase uses a chaincode cache during validation of transactions, initiates state database reads in parallel with validation of transactions, and writes to the ledger and databases in parallel. Our experiments reveal performance improvements of 2x for CouchDB and 1.3x for LevelDB. Notably, our optimizations can be adopted in a future release of Hyperledger Fabric.

A key feature of software-defined networking (SDN) is the decoupling of control pane and data plane. Although delivering huge benefits, such a decoupling also brings a new risk: the data plane states (i.e., flow tables) may deviate from the control plane policies. Existing data plane testing tools such as RuleScope check the correctness of flow tables by injecting probes. However, they are limited in four aspects: 1) are slow in generating probes due to solving SAT problems; 2) may raise false negatives when there are multiple missing rules; 3) cannot test cascaded flow tables used by OpenFlow switches; and 4) either does not support incremental update or has a slow update speed. To overcome these limitations, we present RuleChecker, a fast data plane testing tool for SDN. In contrast to previous tools that generate each probe by solving an SAT problem, the RuleChecker takes the flow table as whole and generates all probes through an iteration of simple set operations. By leveraging binary decision diagram to encode sets, we make the RuleChecker extremely fast: nearly$20\times $faster than the RuleScope, and can update probes in less than 2 ms for 90% of the cases, based on the Stanford backbone rule set.

Programmable data planes, PDPs, enable an unprecedented level of flexibility and have emerged as a promising alternative to existing data planes. Despite the rapid development and prototyping cycles that PDPs promote, the existing PDP ecosystem lacks appropriate abstractions and algorithms to support these rapid testing and deployment life-cycles. In this paper, we propose P4Visor, a lightweight virtualization abstraction that provides testing primitives as a first-order citizen of the PDP ecosystem. P4Visor can efficiently support multiple PDP programs through a combination of compiler optimizations and program analysis-based algorithms. P4Visor s algorithm improves over state-of-the-art techniques by significantly reducing the resource overheads associated with embedding numerous versions of a PDP program into hardware. To demonstrate the efficiency and viability of P4Visor, we implemented and evaluated P4Visor on both a software switch and an FPGA-based hardware switch using fourteen different PDP programs. Our results demonstrate that P4Visor introduces minimal overheads (less than 1%) and is one order of magnitude more efficient than existing PDPs primitives for concurrently supporting multiple programs.

A crucial requirement for Software Defined Network (SDN) is that data plane forwarding behaviors should always agree with control plane policies. Such requirement cannot be met when there are forwarding anomalies, where packets deviate from the paths specified by the controller. Most anomaly detection methods for SDN install dedicated rules to collect statistics of each flow, and check whether the statistics conform to the flow conservation principle. Such per-flow detection methods have a limited detection scope: they look at one flow each time, thus can only check a limited number of flows simultaneously. In addition, dedicated rules for statistics collection can impose a large overhead on flow tables of SDN switches. To this end, this paper presents FOCES, a network-wide forwarding anomaly detection method in SDN. Different from previous methods, FOCES applies a new kind of flow conservation principle at network wide, and can check forwarding behaviors of all flows in the network simultaneously, without installing any dedicated rules. Experiments show FOCES can achieve a detection precision higher than 90% for four network topologies, even when packet loss rates are as high as 10%.

Software Defined Network (SDN) enables flexible update of network functions with a well-defined abstraction between the control and the data plane. However, multiple active network functions with the same priority will potentially trigger conflicts among policies with overlapped flow space, causing the flow table explosion. In contrast to the local switch conflict resolution schemes proposed by previous works, this paper tackles the same problem from a different angle and resolves the policy conflict problem by coordinating all switches under a global centralized view. Specifically, we propose COnflict RAzor (CORA), which tremendously reduces the storage cost of conflicting policies leveraging the global network information obtained in the controller. The basic idea of CORA is migrating policies causing large explosions across the network if necessary, while keeping the semantics equivalence. We prove CORA's NP hardness and propose a heuristic to efficiently search a near-optimal policy migration strategy. Our experiments demonstrate that, CORA can effectively reduce the flow table storage occupation by at least 49% within less than 40 seconds.

Nowadays, Deep Packet Inspection (DPI) becomes a critical component of the network traffic detection applications. For comprehensive analysis of traffic, regular expression matching as the core technique of DPI is widely used. However, web services tend to compress their traffic for less data transmission, which challenges the regular expression matching to achieve wire-speed processing. In this paper, we propose Twins, a fast regular expression matching method over compressed traffic that leverages the returned states encoding in the compression to skip the bytes to be scanned. In our evaluation results, Twins can skip about 90% compression data and can achieve 1.5Gbps throughput, which gains 2.7~3.4 performance boost to the state-of-the-art work.

The prohibitive cost of deploying a sophisticated DNS-based CDN makes anycast-based CDN an attractive alternative for new or small CDN operators. In anycast-based CDNs, user requests are naturally routed to the “closest” server determined by Internet routing. For the operators, however, this comes at a cost—loss of control—how the traffic is routed is entirely at the mercy of BGP routing. The “closest” server may be overloaded, or simply not the best choice. This “loss of control” undermines thescalabilityof anycast-based CDN architectures. To have control over how traffic is routed, existing work either requires adding a large amount of complexity to the system (high Capex/Opex) or is unable to achieve precise and fine-grained control. This paper proposes T-SAC, a scalable anycast-based CDN architecture that capitalizes on the programmability and flexibility of SDN/NFV, enabling fine-grained traffic redirection among CDN servers. T-SAC achieves precise control by leveraging a load-based redirection algorithm and a single 1-bit no-redirect flag. We implement T-SAC in the real system and evaluate its performance from various aspects using DASH and web applications. The results show that T-SAC is capable of redirecting the right amount of traffic at the right time to the right servers, making the system highly scalable.

A lot of recent work has focused on reducing in network queueing latency in datacenter networks. In this paper, we focus on a less explored topic --- latency increases caused by queueing in rate limiters on the end-host. First, we show that latency can be increased by an order of magnitude by rate limiters in cloud networks. To solve this problem, we extend ECN marking into rate limiters and use a datacenter congestion control algorithm --- DCTCP. Unfortunately, while this reduces latency, it also leads to throughput oscillation. Thus, this solution is not sufficient. In this paper, we also analyze the specific reasons that ECN marking in software rate limiters leads to the throughput oscillation problem. Finally, we propose two potential solutions to design software rate limiters that can achieve stable high throughput and low latency.

The reactive model of Software Defined Networking (SDN) invokes controller to dynamically determine the behaviors of a new flow without any pre-knowledge in the data plane. However, the reactive events raised by such flexible model meanwhile consume lots of the bottleneck resources of the fast memory in switch and bandwidth between controller and switches. To address this problem, we propose SoftRing with the motivation to mitigate the overhead to handle a reactive event. In fact, the reactive packets are not necessarily stored in the switch or sent to the controller; instead, they are forwarded to traverse a pre-defined loop path. The packets will finally leave the loop path after the switch rules related to the packet flow being updated to switches in the loop with fewer flow entries. We have implemented a SoftRing system that integrates the controller and software/hardware SDN switches. The results show that SoftRing can eliminate the fast memory requirement for reactive packets and reduce the control channel bandwidth consumption up to 80%, with the cost of less than 5% data plane bandwidth, an average of three extra flow entries in each switch, and minor extra latency for the flow forwarding.

A key feature of Software Defined Network is the decoupling of control pane and data plane. Although delivering huge benefits, such a decoupling also brings a new risk: the data plane states (i.e., flow tables) may deviate from the control plane policies. Existing data plane testing tools like Monocle check the correctness of flow tables by injecting probes. However, they are limited in four aspects: (1) slow in generating probes due to solving SAT problems, (2) may raise false negatives when there are multiple missing rules, (3) do not support incremental probe update to work in dynamic networks, and (4) cannot test cascaded flow tables used by OpenFlow switches. To overcome these limitations, we present RuleChecker, a fast and complete data plane testing tool. In contrast to previous tools that generate each probe by solving an SAT problem, RuleChecker takes the flow table as whole and generates all probes through an iteration of simple set operations. By lever-aging Binary Decision Diagram (BDD) to encode sets, we make RuleChecker extremely fast: around 5 χ faster than Monocle (when detecting rule missing faults), and nearly 20 χ faster than RuleScope (when detecting both rule missing and priority faults), and can update probes in less than 2 ms for 90% of cases, based on the Stanford backbone rule set.

Traffic statistics are fundamental for many network measurement tasks like heavy hitter identification, traffic matrix estimator, anomaly detection, etc. However, traditional techniques like NetFlow and sFlow only provide coarse-grained statistics due to packet or flow sampling. Even Software Defined Networking (SDN) offers fine-grained traffic statistics collection, most of existing methods focus on specific applications and thus lack generality. To this end, we propose CounterMap, a generic traffic statistics collection and query platform. CounterMap maintains a full map of flow counters by actively polling switches and passively monitoring flow timeouts. For efficient storage and query, CounterMap stores the counters in fast off-the-shelf inmemory data store, and offers a generic SQL-like query language. With the CounterMap language, applications can gain visibility into both existing and historical flows, without querying the dataplane devices themselves. We show how network applications benefit from CounterMap, with higher measurement accuracy and lower dataplane overhead.

Matching multiple patterns is the key technology in firewall, Intrusion Detection Systems, etc. However, most of the web services nowadays tend to compress their traffic for less transferring data and better user experience, which has challenged the multi-pattern matching original working only on raw content. Naive and straightforward solutions towards this challenge either decompress the compressed data first and apply legacy multi-pattern matching methods, or have to scan redundant data during the matching., which are not fast and memory efficient. In this paper, we propose COmpression INspection (COIN) method for multi-pattern matching on compressed HTTP traffic. COIN does not decompress the data before matching and only scans once each bit of the traffic under inspection. We have collected real traffic data from Alexa.com top 500 and Alexa.cn top 20000 web sites and have performed the experiments under 1430 SNORT patterns. The evaluation results show that COIN is 10–31% faster than state-of-the-art approach.

Optical data center networks (DCNs) are becoming increasingly attractive due to their technological strengths compared with the traditional electrical networks. However, existing optical DCNs are either hard to scale, vulnerable to single point of failure, or provide limited network bisection bandwidth for many practical data center workloads. To this end, we present WaveCube, a scalable, fault-tolerant, high-performance optical DCN architecture. To scale, WaveCube removes MEMS,1a potential bottleneck, from its design. WaveCube is fault-tolerant, since it does not have single point of failure and there are multiple node-disjoint parallel paths between any pair of top-of-rack switches. WaveCube delivers high performance by exploiting multi-pathing and dynamic link bandwidth along the path. For example, our evaluation results show that, in terms of network bisection bandwidth, WaveCube outperforms prior optical DCNs by up to 400% and is 70%-85% of the ideal non-blocking network (ı.e., theoretical upper bound) under both realistic and synthetic traffic patterns. WaveCube's performance degrades gracefully under failures-it drops 20% even with 20% links cut. WaveCube also holds promise in practice-its wiring complexity is orders of magnitude lower than Fattree, BCube, and c-Through at scale, and its power consumption is 35% of them.

Software defined networks provide new opportunities for automating the process of network debugging. Many tools have been developed to verify the correctness of network configurations on the control plane. However, due to software bugs and hardware faults of switches, the correctness of control plane may not readily translate into that of data plane. To bridge this gap, we present VeriDP, which can monitor "whether actual forwarding behaviors are complying with network configurations". Given that policies are well-configured, operators can leverage VeriDP to monitor the correctness of the network data plane. In a nutshell, VeriDP lets switches tag packets that they forward, and report tags together with headers to the verification server before the packets leave the network. The verification server pre-computes all header-to-tag mappings based on the configuration, and checks whether the reported tags agree with the mappings. We prototype VeriDP with both software and hardware OpenFlow switches, and use emulation to show that VeriDP can detect common data plane fault including black holes and access violations, with a minimal impact on the data plane.

How to debug large networks is always a challenging task. Software Defined Network (SDN) offers a centralized con- trol platform where operators can statically verify network policies, instead of checking configuration files device-by-device. While such a static verification is useful, it is still not enough: due to data plane faults, packets may not be forwarded according to control plane policies, resulting in network faults at runtime. To address this issue, we present VeriDP, a tool that can continuously monitor what we call control-data plane consistency, defined as the consistency between control plane policies and data plane forwarding behaviors. We prototype VeriDP with small modifications of both hardware and software SDN switches, and show that it can achieve a verification speed of 3 μs per packet, with a false negative rate as low as 0.1%, for the Stanford backbone and Internet2 topologies. In addition, when verification fails, VeriDP can localize faulty switches with a probability as high as 96% for fat tree topologies.

The OpenFlow paradigm embraces third-party development efforts, and therefore suffers from potential attacks that usurp the excessive privileges of control plane applications (apps). Such privilege abuse could lead to various attacks impacting the entire administrative domain. In this paper, we present SDNShield, a permission control system that helps network administrators to express and enforce only the minimum required privileges to individual controller apps. SDNShield achieves this goal through (i) fine-grained SDN permission abstractions that allow accurate representation of app behavior boundary, (ii) automatic security policy reconciliation that incorporates security policies specified by administrators into the requested app permissions, and (iii) a lightweight thread-based controller architecture for controller/app isolation and reliable permission enforcement. Through prototype implementation, we verify its effectiveness against proof-of-concept attacks. Performance evaluation shows that SDNShield introduces negligible runtime overhead.

Software-dehned network (SDN) is deemed to enable more dynamic management of data center networks that promptly respond to network events with changes in network policies. Although the SDN controller architecture is increasingly optimized for swift policy updates, the data plane, especially the prevailing TCAM-based flow tables on physical SDN switches, remains unoptimized for fast rule updates, and is gradually becoming the primary bottleneck along the policy update pipeline. In this paper, we present RuleTris, the hrst SDN update optimization framework that minimizes rule update latency for TCAM-based switches. RuleTris employs the dependency graph (DAG) as the key abstraction to minimize the update latency. RuleTris efhciently obtains the DAGs with novel dependency preserving algorithms that incrementally build rule dependency along with the compilation process. Then, in the guidance of the DAG, RuleTris optimizes the rule updates in TCAM to avoid unnecessary entry moves, which are the main cause of TCAM update inefhciency. We prove that RuleTris generates TCAM updates with the minimum number of TCAM entry moves. In evaluation, RuleTris achieves a median of <;12ms and 90-percentile of <;15ms the end-to-end per-rule update latency on our hardware prototype, outperforming the state-of-the-art composition compiler CoVisor by ~20 times.

Software Defined Networking (SDN) is evolving to such a phase that multiple programming languages and rule specifications coexist. However, current SDN compilers are closely bound to both languages and rules, thus disable the interoperability and compatibility of SDN programs. To solve this problem, we propose to modularize the SDN compiler by leveraging intermediate representation (IR), a common technique for computer compiler design. Specifically, we introduce Semantic Rule (SR) as the first IR for SDN compilers, which is a simple, language-independent, and semantic-preserving representation. We develop two optimizations on the semantic rule to coordinate cross-language programs in a single network and compress the number of compiled rules. We implement a modular compiler prototype with the proposed SR, and demonstrate that RYU programs can run at both OpenFlow and POF network. With synthetic network configurations, we demonstrate that the optimizations on SRs are effective, efficient and scalable.

SDN has become the wide area network technology, which the academic and industry most concerned about.The limited table sizes of today’s SDN switches has turned to the most prominent short planks in the network design implementation. TCAM based flow table can provide an excellent matching performance while it really costs much. Even the flow table overflow cannot be prevented by a fixed-capacity flow table. In this paper, we design FTS(Flow Table Sharing) mechanism that can improve the performance disaster caused by overflow. We demonstrate that FTS reduces both control messages quantity and RTT time by two orders of magnitude compared to current state-of-the-art OpenFlow table-miss handler.

Application Driven Network(ADN) is a new paradigm that provides on-demand differentiated services for applications. A physical network in ADN is sliced into various logically isolated sub-networks. Each network slice can have its own network architecture and protocol to serve one application exclusively. ADN enhances the user experience while keeping the resource efficiency by further imposing multiplexing among these logically isolated sub-networks.

OpenFlow, as the Software Defined Networking (SDN) primitive, provides a simple forwarding plane abstraction, which heavily relies on the fast memory inside the OpenFlow Switch (OFS). OFS components, e.g. flow table, meter table, counters, have to compete for the limited fast memory resource. As a result, only a few counting functions are defined as mandatory in the OFS specification, although a lot of SDN proposals depend on a detailed states collected by the optional counters in the specification. This fact motivates us to rethink the way to maintain counters in the OFS. We propose a new architecture called CACTI, which only consumes several registers in the fast path and moves the completed counters into the on chip RAM like cache in the slow path processor. Theoretical analysis and experiments on the prototype system demonstrated the efficiency of our architecture: CACTI is capable to achieve the throughput of 29.4-39.7M pps packets per second (pps). No RAM resource is needed any more in the fast path, instead, CACTI consumes only 0.24-0.54\% Look-Up Table and 0.35-0.43\% flip-flops compared with the entire FPGA-based OFS design in the fast path, and the unused CPU cache in the slow path.

Controllers play a critical role in software-defined networking (SDN). However, existing single-controller SDN architectures are vulnerable to single-point failures, where a controller’s capacity can be saturated by flooded flow requests. In addition, due to the complicated interactions between applications and controllers, the flow setup latency is relatively large. To address the above security and performance issues of current SDN controllers, we propose distributed rule store (DRS), a new multi-controller architecture for SDNs. In DRS, the controller caches the flow rules calculated by applications, and distributes these rules to multiple controller instances. Each controller instance holds only a subset of all rules, and periodically checks the consistency of flow rules with each other. Requests from switches are distributed among multiple controllers, in order to mitigate controller capacity saturation attack. At the same time, when rules at one controller are maliciously modified, they can be detected and recovered in time. We implement DRS based on Floodlight and evaluate it with extensive emulation. The results show that DRS can effectively maintain a consistently distributed rule store, and at the same time can achieve a shorter flow setup time and a higher processing throughput, compared with ONOS and Floodlight.

The de facto implementation of Software Defined Networking (SDN), i.e., OpenFlow, only parses L2-L4 headers, which limits the use of SDN to employ control intelligence in application layer. In this paper, we advocate content parsing to empower SDN with finer grained control ability over traffic. Specifically, we propose a scalable content parser, called COPY, to identify and parse application layer protocols. COPY creates a distinguishable counting context free grammar (DCCFG) to specify the protocol's semantics in application layer, and translates multiple DCCFGs into one distinguishable counting automaton (DCA). DCA is generated without semantic loss from the single DCCFG, and thus provides accurate and scalable parsing ability. Our experiments show that COPY precisely identifies every packet in a labeled trace. When comparing with other six approaches on the real traces, COPY performs 4.2Gb/s and 24.7Gb/s with single- and eight-thread models, respectively, which improves 20%-860% than others, and consumes acceptable offline overhead in time and space.

Location Based Service (LBS) is gaining popularity on smart phones. One fundamental LBS is range search, which returns all Point of Interests (POIs) within a user-specified range. However, people also leave their location privacy at risks when using LBS like range search. How can a user invoke such service without revealing his location is an interesting, yet challenging problem to solve. Most existing approaches blur a user's location into a cloaked region, so that LBS cannot figure out the exact location of the requesting user. However, this would make the returning results inaccurate, containing some out-of-range POIs. To this end, we propose PAPERS, a new method to provide location privacy for users of range search. PAPERS leverage homomorphic encryption to let the user encrypt her location, and the LBS server can compute distances on ciphertext. In this way, the returning results by LBS are exactly the POIs within the specified range, while LBS learns nothing about user's real location. We implement a prototype of PAPERS, and evaluate it with real POI set of a large-scale production LBS. Experimental results show that PAPERS can achieve the goal of privacy protection, with reasonable overhead in response time and communication cost.

Many applications of wireless sensor networks (WSNs) need to balance multiple yet often conflicting performance requirements such as high energy efficiency, high throughput, low delay and low loss. Finding appropriate WSN parameter configuration to achieve the best trade-off requires in depth understanding of the joint effect of key parameters residing at different layers on the performance. In this paper, we present an extensive experimental study on the data delivery performance of aWSN link, where 4 major performance metrics, namely energy, throughput, delay and loss, were measured over 6 months under around 50 thousand parameter configurations of 7 key stack parameters. Different from existing work, rich observations are made out of the extensive measurement data, with the focus on the joint effect of these parameters on the performance. Specifically, for each of the four performance metrics, a set of guidelines is derived for parameter optimization. In addition, we propose empirical models for each performance metric to quantify the joint effects, which enable finding optimal settings for parameters such as payload size or retransmissions, in consideration of link quality and other parameter settings, to achieve better performance trade-offs. To demonstrate the potential of this work, the obtained joint parameter optimization results are applied to an example. The outcome is compared with those achieved by following representative single-parameter tuning guidelines from the literature. The comparison reveals that by considering the joint effect of multi-layer parameters together, a WSN application can obtain a much improved performance trade-off.

Optical data center networks (DCNs) are becoming increasingly attractive due to their technological strengths compared to traditional electrical networks. However, prior optical DCNs are either hard to scale, vulnerable to single point of failure, or provide limited network bisection bandwidth for many practical DCN workloads. To this end, we present WaveCube, a scalable, fault-tolerant, high-performance optical DCN architecture. To scale, WaveCube removes MEMS1, a potential bottleneck, from its design. Wave-Cube is fault-tolerant since it does not have single point of failure and there are multiple node-disjoint parallel paths between any pair of Top-of-Rack (ToR) switches. WaveCube delivers high performance by exploiting multi-pathing and dynamic link bandwidth along the path. Our extensive evaluation results show that WaveCube outperforms previous optical DCNs by up to 400% and delivers network bisection bandwidth that is 70%–85% of an ideal non-blocking network under both realistic and synthetic traffic patterns. WaveCube's performance degrades gracefully under failures — it drops 20% even with 20% links cut. WaveCube also holds promise in practice — its wiring complexity is orders of magnitude lower than Fattree, BCube and c-Through at large scale, and its power consumption is 35% of them.

An appropriate tool to generate real network traffic plays an important role in testing network system. Traditionally, such a tool relies on software solutions that copies data back and forth between different part of memory to capture or replay network traffic. In this paper, we propose an FPGA-centric approach using parallel logic, which can ensure high accuracy of time and high throughput. We first design an FPGA add-on board dealing with the multifarious work like adding content or calculate statistical value. The system is implemented on an own designed off-the-shelf FPGA network add-on card to demonstrate the viability of our assumption. Experiments demonstrate reasonable performance improvement (higher throughput and replay time precision) when compared with software based solutions.

It has become a common practice that enterprises outsource their networks to the cloud by renting multiple virtual machines (VMs) in cloud datacenters. Due to the multi-tenant nature of cloud datacenter, how to efficiently share the network resources becomes an important issue. Recent studies, e.g., SecondNet and Oktopus, have taken network bandwidth into consideration when allocating VMs. However, these schemes are problematic in that the allocation is not that accurate, and can result in a low multiplexing rate. To this end, we present VirtualRack (VR), a new bandwidth-aware VM allocation scheme in multi-tenant datacenters. VR simultaneously considers intra-datacenter bandwidth and Internet-access-bandwidth requirements in the allocation process. In addition, we introduce a redundancy factor α that can be specified by tenants to accommodate their dynamic requirements. Simulation results show that VR can guarantee the network performance for each of the multiple tenants, and at the same time keep a high acceptance ratio without any false allocation.

No abstract available.

This paper studies the fine-grained traffic identification (FGTI) for better understanding and managing networks.Instead of only indicating which application/protocol that a packet is related to, FGTI maps the traffic packet to ameaningful user behavior or application context. In this paper, we first propose rule organized optimal matching (ROOM),which splits the identification rules into several fields and elaborately organizes the matching order of the fields. Asa result, ROOM can only activate the matching operations on a (small) part of the rules that could be possibly hit. Weformulate the optimal rule organization problem of ROOM mathematically and demonstrate it to be NP-hard, and then wepropose a heuristic algorithm to solve the problem with the time complexity of O(N2) (N is the number of fields in the rule set). Based on ROOM, wefurther propose MP-ROOM, which is extended to well support the rules cross multiple protocol data units (PDUs) fortraffic identification. In addition, we implement a prototype system including MP-ROOM and related work for evaluations.The evaluations show very promising results: 1.5 ~71.3 times throughput improvement is obtained by MP-ROOM inthe real system with less than 300-MB memory consumption. With multiple-thread parallel programming, we successfullyachieve the throughput over 40 Gb/s for real traces.

A complete flow statistics report should include both flow size (the number of packets in a flow) counting and flow volume (the number of bytes in a flow) counting. Although previous studies have contributed a lot to the flow size counting problem, it is still a great challenge to well support the flow volume statistics due to the demanding requirements on both memory size and memory bandwidth in monitoring device. In this paper, we propose a DIScount COunting (DISCO) method, which is designed for both flow size and flow bytes counting. For each incoming packet of length l, DISCO increases the corresponding counter assigned to the flow with an increment that is less than l. With an elaborate design on the counter update rule and the inverse estimation, DISCO saves memory consumption while providing an accurate unbiased estimator. The method is evaluated thoroughly under theoretical analysis and simulations with synthetic and real traces. The results demonstrate that DISCO is more accurate than related work given the same counter sizes. DISCO is also implemented on the network processor Intel IXP2850 for a performance test. Using only one microengine (ME) in IXP2850, the throughput can reach up to 11.1 Gb/s under a traditional traffic pattern. The throughput increases to 39 Gb/s when employing four MEs.

Fine-grained traffic identification (FGTI) reveals the context/purpose of each packet that flows through the network nodes/links. Instead of only indicating the application/protocol that a packet is related to, FGTI further maps the packet to a meaningful user behavior or application context. In this paper, we propose a Rule Organized Optimal Matching (ROOM) for fast and memory efficient fine-grained traffic identification. ROOM splits the identification rules into several fields and elaborately organizes the matching order of the fields. We formulate and model the optimal rule organization problem of ROOM mathematically, which is demonstrated to be NP-hard, and then we propose an approximate algorithm to solve the problem with the time complexity of O(N2) (N is the number of fields in a rule). In order to perform evaluations, we implement ROOM and related work as real prototype systems. Also, real traces collected in wired Internet and mobile Internet are used as the experiment input. The evaluations show very promising results: 1.6X to 104.7X throughput improvement is achieved by ROOM in the real system with acceptable small memory cost.

Private BitTorrent (PT) is a new trend in Peer-to-Peer file sharing system, which provides high incentives for its users to seed after download by maintaining an upload-to-download ratio in the tracker for each registered community member. From the data we collected from six active PT sites, we discover that the population of both users and contents in any single PT site is much less than the public BitTorrent, and the intersection of content sets in different PTs is quite small. Based on this observation, we propose a content sharing/distribution framework among PTs (named CrossPT), as well as its sharing mechanism. In addition, we investigate the sharing strategy of the PT participants in CrossPT using game theory and the fetch strategy by modeling the scenario to a Neighbor Selection Problem (NSP). We prove NSP to be NP-complete and propose a heuristic algorithm to solve it. The evaluations with the input of crawled data from six PT sites demonstrate the efficiency of our mechanism. The content sizes of the six PT sites can be increased by 113.95%-438.46% with CrossPT. Also, the content distribution process can be done in less than one second, excluding the delivery time of the content itself.

In this paper, we have designed a Multi-Frequency Scaling scheme for energy conservation of network devices, especially routers and switches. The frequency of components in a network device is scaled dynamically according to the real time workload. A Markov model is developed for performance analysis of this mechanism. We implement a prototype of this scheme in the data path of a general IPv4 router based on a real hardware platform - NetFPGA. Experimental results show excellent energy savings at the cost of a tolerable latency, under various ranges of traffic loads. Our work indicates the feasibility and possibility of deploying this mechanism into real network devices for energy saving.

Address auto-configuration is a key problem in data center networks, where servers and switches encode topology information into their addresses for routing. A recent work DAC [2] has been introduced to address this problem. Without malfunctions, DAC can auto-configure all the devices quickly. But in case of malfunctions, DAC requires significant human efforts to correct malfunctions and it can cause substantial operation delay of the whole data center. In this paper, we further optimize address auto-configuration process even in the presence of malfunctions. Instead of waiting for all the malfunctions to be corrected, we could first configure the devices that are not involved in malfunctions and let them work first. This idea can be translated to considerable practical benefits because in most cases malfunctions in data centers only account for a very small portion. To realize the idea, we conceptually remove the malfunctions from the physical data center topology graph and mathematically convert the address configuration problem into induced sub graph isomorphism problem, which is NP-complete. We then introduce an algorithm that can solve the induced sub graph isomorphism quickly by taking advantage of data center topology characteristics and induced sub graph properties. We extensively evaluate our design on representative data center structures with various malfunction scenarios. The evaluation results demonstrate that the proposed framework and algorithm are efficient and labor-free to deal with the mapping task in the presence of error devices.

Our measurements on production data center traffic together with recently reported results suggest that data center networks suffer from long-lived congestion caused by core network over subscription and unbalanced workload placement. In contrast to traditional traffic engineering approaches that optimize flow routing, in this paper, we explore the opportunity to address the continuous congestion via optimizing VM placement in virtualized data centers. To this end, we present Virtual Knotter, an efficient online VM placement algorithm to reduce congestion with controllable VM migration traffic as well as low time complexity. Our evaluation with both real and synthetic traffic patterns shows that Virtual Knotter performs close to the baseline algorithm in terms of link unitization, with only 5%-10% migration traffic of the baseline algorithm. Furthermore, Virtual Knotter decreases link congestion time by 53% for the production data center traffic.

Green networking in the Internet becomes increasingly important. In a high-performance router, the dominant power consumer on the Internet, half of its total power usage goes into the line-cards, where the traffic managers inside consume most of it. In this paper, we propose an energy-efficient design on the traffic manager architecture for packet buffering and storage. Unlike traditional routers where packets are always kept in off-chip memory, we propose a dynamic on-chip and off-chip scheduling mechanism, called Dynamic Packet Manager (DPM), to reduce both peak and average power consumption caused by the traffic manager. DPM buffers packets in a small on-chip memory in the light-traffic period, and activates the off-chip memory on when the on-chip memory is to overflow. In this design, when the traffic is light, the off-chip memory is put into power saving state by clock gating so that the average power consumption is reduced. With an on-chip flow based and off-chip class-based design, DPM can save one off-chip memory otherwise used for the per-flow index information storage, therefore further reduce the peak power usage. We present the theoretic analysis guiding the implementation of the DPM mechanism. Experiments on three prototypes implemented on different hardware show that the peak and average power consumptions can be reduced by 27.9% and 37.5% respectively, along with less on-chip memory cost. Besides, the traffic manger with DPM shows better performance on average packet scheduling delay than the one without DPM.

Peer-to-Peer (P2P) mode dominates the way that files are shared over the Internet today. A measurement study on the user behaviour during the P2P file sharing is important and helpful to better understand and design P2P networks. In this study, the authors developed a method to collect information about peers and connections in movie sharing at the BitTorrent client side. Movie is selected as the investigation object since its immense popularity and large size among all the file types over P2P networks. The method proposed in this study can be easily applied to study the distribution behaviour of other types of files. Based on the collected data, the authors have derived 10 observations in three categories: (i) distributions of peers and connections over globe time and local time (after adjustment of time differences); (ii) distributions of peers and connections over geographic areas (at different levels of continents, countries, cities); and (iii) the influence to the above distributions by differences of population, gross domestic product (GDP) and life style.

SYN flood attacks still dominate distributed denial of service attacks. It is a great challenge to accurately detect the SYN flood attacks which utilise skillful spoofs to evade traditional detection methods. An intelligent attacker would evade the public detection methods by suitably spoofing the attack to appear benign. Keeping per-flow or per-connection state could eliminate such a spoofing, but meanwhile, it is very difficult to be implemented in practice. A more accurate and fast SYN flood detection method, named SACK2, is proposed to deal with all kinds of SYN flood attacks with limited implementation costs. SACK2 exploits the behaviour of the SYN/ACK-CliACK pair to identify the victim server and the TCP port being attacked, where a SYN/ACK packet is sent by a server when receiving a connection request and a CliACK packet is the ACK packet sent by the client to complete the three-way handshake. It also utilises the space efficient data structure, counting Bloom filter, to recognise the CliACK packet. The memory cost of SACK2 for a 10 Gbps link is 364 KB and can be easily accommodated in modern routers. SACK2 can report the start of the attack in less than one detection period, and the end of the attack less than two detection periods. It is also demonstrated that SACK2 is the most accurate detection method through comprehensive experiments.

Sampling technology has been widely deployed in network measurement systems to control memory consumption and processing overhead. However, most of the existing methods suffer from large errors for the estimation of small-size flows. To address this problem, we propose an adaptive non-linear sampling (ANLS) method for flow size estimation. Instead of statically pre-configuring the sampling rate, ANLS dynamically adjusts the sampling rate for each flow according to the value of a corresponding counter. A smaller sampling rate is utilized when the counter value is large, while a larger sampling rate is employed for a smaller counter. In this paper, the unbiased flow size estimation, the relative error, and the required counter size are studied through theoretical analysis and experimental evaluations. The analysis and experiments demonstrate that ANLS can significantly improve the estimation accuracy (particularly for small-size flows), and save memory consumption, while maintaining processing overhead comparable to existing methods. Moreover, we validate the design of ANLS by implementing an FPGA-based prototype, which is capable of measuring traffic throughput up to 26.5 Gbps.

In response to Internet emergencies, Internet resiliency is investigated directly through an autonomous system (AS) level graph inferred from policy-compliant BGP paths or/and traceroute paths. Due to policy-driven inter-domain routing, the physical connectivity does not necessarily imply network reachability in the AS-level graph, i.e., many physical paths are not visible by the inter-domain routing protocol for connectivity recovery during Internet outages. We call the invisible connectivity at the routing layer, which can be quickly restored for recovering routing failures by simple configurations, as the potential routing diversities. In this paper, we evaluate two kinds of potential routing diversities, which are recognized as Internet eXchange Points (IXPs) participant reconnection and peering policy relaxation. Using the most complete dataset containing AS-level map and IXP participants that we can achieve, we successfully evaluate the ability of potential routing diversity for routing recovery during different kinds of Internet emergencies. Encouragingly, our experimental results show that 40% to 80% of the interrupted network pairs can be recovered on average beyond policy-compliant paths, with rich path diversities and a little traffic shifts. Thus, this paper implies that the potential routing diversities are promising venues to address Internet failures.

BGP dictates routing between autonomous systems with rich policy mechanisms in today's Internet. Operators translate high-level policy objectives into low-level router configurations without a comprehensive understanding of the actual effects on the network behavior, leaving the routing management an error-prone and time-consuming procedure. A fundamental question is: how to verify the intended routing principles against the actual routing effects of an ISP? In this paper, we develop a Routing Policy Inference Model (RPIM) as the first step towards addressing this fundamental issue. RPIM extracts various policy patterns from the BGP routing tables and translates them into high-level policy objectives of the ISP using a grouping and matching technique. Our work bridges the gap between the high-level policy objectives and the actual routing effects, which provides network operators with a novel approach to verify their policy design principles, thus facilitating the routing management. We evaluate our approach by extensive simulations using the Internet AS-level topology from CAIDA and the real routing data from the Abilene network. Simulation results show that RPIM achieves over 78.94% average inference accuracy in our suggested optimal threshold range. We also verify RPIM on several operating ISPs by the registered policies in an Internet Routing Registry (IRR). A representative case study on AS3292 demonstrates that RPIM effectively infers high-level policy objectives from routing data.

The eXplicit Control Protocol (XCP) is a promising congestion control protocol that outperforms TCP in terms of efficiency, fairness, persistent queue length, and packet loss rate. XCP quantitatively informs senders how to adjust their sending rate, and assumes that all senders will respond. However, short-lived flows are often on the order of a few segments, they may be unresponsive to XCP feedback, and have negative impact on the system control loop. In this paper, a control theoretic analysis of the XCP properties is conducted in the presence of short-lived traffic. First, the original XCP model is modified to account for these unresponsive flows. Then, with the M/G/∞ model of short-lived traffic, their impact on the XCP control loop is analyzed, and theoretical results show that short-lived bursty traffic have the effect of reducing the available bandwidth and increasing the variances of long-lived XCP flows. Finally, theoretical results are verified using packet level simulations.

Peer-to-Peer (P2P) mode dominates the way that files are shared over the Internet today. A measurement study on the user behavior during the P2P file sharing is important and helpful to better understand and design P2P networks. In this paper, we developed a method to collect information about peers and connections in movie sharing at the BitTorrent client side. Based on the collected data, we have derived 5 observations in the influence upon peers and connections distributions over geographic areas (at different levels of continents, countries, cities) by differences of population, GDP (Gross Domestic Product), time zone and life style.

Flow size statistics is a fundamental task of passive measurement. In order to bound the estimation error of passive measurement for both small and large flows, previous probabilistic counter updating algorithms used linear or nonlinear sampling function to automatically adjust the sampling rate. However, each of these methods employed a pre-set and fixed sampling function during the measurement period. As a result, the performance would vary for different flow distributions. In this paper, we propose a Smart Selection Sampling (S3) approach, which can tune the sampling function to reach a comparatively lower relative error. The key component of S3 is a heuristic algorithm leveraging the flow distribution information to determine a better sampling function so as to achieve better measurement accuracy. Experiments under real trace and synthetic traces demonstrate that S3 is more accurate than the previous work if given the same memory sizes to accommodate flow statistics counters.

The eXplicit Control Protocol (XCP) is a promising congestion control protocol that outperforms TCP in terms of efficiency, fairness, persistent queue length, and packet loss rate. However, XCP will behave in a noticeably unstable manner if the maximum round trip time of a flow is much larger than average round trip time of all flows, which is a typical nonlinear instability. In this paper, eXCP is proposed to stabilize the system and enable XCP to deal with heterogeneous feedback delays. With the aid of the exponentially weighted moving average filter, eXCP directly reduces the volatility of the control interval and effectively improves the stability of the aggregate input traffic at a bottleneck link. Simulations also have shown that the variance of per-flow throughput and round trip time decrease dramatically.

Network measurement projects such as NLANR, Routeviews and RIPE have greatly advanced people's ability to understand, manage and engineer the Internet. Meanwhile, the significant maintenance fee to support such monitoring infrastructures motivates us to think about a cost-effective way to manage these systems. In this study, the authors measure, model and evaluate the border gateway protocol (BGP) monitoring system (BGPMon) that is mainly composed of vantage point ASes (i.e. monitors or VPs) peered with Routeviews and RIPE. The results from the authors’ experiments show the feasibility to use fewer VPs while still retaining the original monitoring capability of the existing BGPMon. Only 110 VPs out of the original 438 ones are capable of monitoring most of the information for all the six metrics with the optimum VP selection method given in this paper. The authors further evaluate the selected VPs at different times and observe that the performance is encouragingly stable, for example, more than 99% of the information for five out of the six metrics can be constantly captured with less than 110 VPs in random samples.

Flow-level sampling methods have been widely studied and extensively employed in network traffic measurement systems. However, traffic anomalies are becoming more prevalent and severe in the Internet, which pose great challenges to the traffic measurement. Existing solutions targeted at such scenario have either low accuracy or high memory usage. In this paper, we propose a two-stage sampling approach-Anti Attack Counters (A2C) and an efficient parameter adapting method to solve the problem. The proposed sampling mechanism can adapt to the network condition automatically and collect more information even under severe traffic attacks. Theoretical analysis on accuracy and resource requirement is presented in our work. Furthermore, we validate our approach using both synthetic and real traces. The experimental results demonstrate that A2C is of high resilience while providing significantly improved measurement accuracy with reduced memory occupation comparing with other existing anti-attack countermeasures.

More complicated computational tasks are posed to the network equipments, such as Deep packet inspection (DPI) for network security check and network coding to achieve efficient multicast, etc. These complicated applications need processors to process the whole packet payload, potentially causing low throughput and long latency due to the large access delay to external memories. The behind hint lies that we can get the packet-processor/thread pair binding information in advance from the front-end dispatching component before the packet will be actually processed by cores. This interesting observation enables us design a new architecture of memory access for packet processors instead of the traditional model. In this paper we explore to apply push model to packet processors. The push model makes the data being pushed into the local memory/on-chip L1 cache in an on-demand and fine granularity manner ahead of being asked by running instructions, making a core always feels getting its data from the local memory/L1 cache instead of fetching them from the external memory in pull model. In order to verify the effectiveness, we design and implement the push model with the Intel IXP2850, and then conduct experiments to show the performance of push model in the IXP2850 simulator compared with the pull model. Simulation results indicate that applying push model to packet processors could improve the system throughput and reduce the packet processing latency and reducing required number of hardware threads.

Per-flow queuing is believed to be an effective approach to guarantee Quality of Service (QoS) in high performance routers. However, its brute-force implementation consumes a huge amount of memory and is not scalable as the number of flows increases. Dynamic Queue Sharing (DQS) mechanism, in which a physical queue is dynamically created on-demand when a new flow comes and released when the flow temporarily paused, is able to achieve per-flow queuing performance with much less memory. In this paper, based on DQS, an active per-flow queuing system is designed, implemented and tested. To evaluate the effectiveness of DQS, we implement two FPGA-based Traffic Manager (TM) prototypes, one with DQS and the other a traditional one. The real chip implementation shows that DQS can not only scale down the required memory for per-flow queuing but also reduce the total number of control logic elements. As a result of reduced control logic, original 3-stage scheduling in naive scheme can be improved to be a single stage while maintaining the same delay performance, thus resulting in a faster speed potential. Besides, the power consumption can also considerably be reduced. Our experiments on a 4Gbps TM prototype using Stratix EP1S80F1508C5 FPGA show a 58.6% decrease in control memory. Meanwhile, the logic cells and LC registers are reduced by 6.8% and 15.0% respectively, and the power consumption is saved by 23% compared with the brute-force per-flow queuing implementation with 8K queues.

A basic task in network passive measurement is collecting flow statistics information for network state characterization. With the continuous increase of Internet link speed and the number of flows, flow statistics has become a great challenge due to the demanding requirements on both memory size and memory bandwidth in measurement devices. In this paper, we propose a DIScount COunting (DISCO) method, which is designed for both flow size and flow volume counting. For each incoming packet of length l, DISCO increases the corresponding counter assigned to the flow with an increment that is less than l. With an elaborate design on the counter update rule and the inverse estimation, DISCO saves memory consumption while providing an accurate unbiased estimator. The method is evaluated thoroughly under theoretical analysis and simulations with synthetic and real traces. The results demonstrate that DISCO is more accurate than related work given the same counter size. DISCO is also implemented on network processor Intel IXP2850 for performance test. Using only one MicroEngine (ME) in IXP2850, the throughput can reach up to 11.1Gbps under a traditional traffic pattern, and it increases almost linearly with the number of MEs employed.

As the Internet becomes a critical infrastructure component of our global information-based society, any interruption to its availability can have significant economical and societal impacts. Although many researches tried to improve the resilience through the BGP policy-compliant paths, it has been demonstrated that the Internet is still highly vulnerable when major failures happen. In this paper, we aim to overcome the inherent constraint of the existing BGP-compliant recovery schemes and propose to seek additional potential routing diversity by relaxing BGP peering links and through Internet eXchange Points (IXPs). The focus of this paper is to evaluate the potentiality of these two schemes, rather than on their implementations. By collecting most complete AS link map up-to-date with 31K nodes and 142K links, we demonstrate that the proposed potential routing diversity can recover 40% to 80% of the disconnected paths on average beyond BGP-compliant paths. This work suggests a promising venue to address the Internet failures.

The publicly available BGP vantage points (VPs) have been heavily used by the research community to build the Internet autonomous system (AS) level topology, which is a key input to many applications, such as routing protocol design, performance evaluation and network security issues. However, a detailed study on the eyeshots of these VPs has received little attention before. In this paper, we inspect these VPs carefully. Specifically, we do a measurement work to evaluate the effect of various factors on the eyeshot of each individual VP as well as the relationship between the eyeshots of different VPs. Based on the measurements, we disclose several counterintuitive observations and explain the possible reasons behind, which will help people to better understand the eyeshots of VPs and make better use of them in practice.

SYN flood attacks still dominate distributed denial of service attacks. It is a great challenge to accurately detect the SYN flood attacks in high speed networks. An intelligent attacker would evade the public detection methods by suitably spoofing the attack to pretend to be benign. Keeping per-flow or per-connection state could eliminate such a spoofing, but meanwhile, it also consumes extremely huge resources. We propose a more accurate and fast SYN flood detection method, named SACK2, which could detect all kinds of SYN flood attacks with limited implementation costs. SACK2exploits the behavior of the SYN/ACK-CliACK pair to identify the victim server and the TCP port being attacked, where a SYN/ACK packet is sent by a server when receiving a connection request and a CliACK packet is the ACK packet sent by the client to complete the three-way handshake. We utilize the space efficient data structure, counting Bloom filter, to recognize the CliACK packet. Comprehensive experiments demonstrate that, SACK2is the fastest and most accurate detection method compared with related methods which also leverage the packet pair's behavior. The memory cost of SACK2for a 10 Gbps link is 364 KB and can be easily accommodated in modern routers.

Sampling technology has been widely deployed in measurement systems to control memory consumption and processing overhead. However, most of the existing sampling methods suffer from large estimation errors in analyzing small-size flows. To address the problem, we propose a novel adaptive non-linear sampling (ANLS) method for passive measurement. Instead of statically configuring the sampling rate, ANLS dynamically adjusts the sampling rate for a flow depending on the number of packets having been counted. We provide the generic principles guiding the selection of sampling function for sampling rate adjustment. Moreover, we derive the unbiased flow size estimation, the bound of the relative error, and the bound of required counter size for ANLS. The performance of ANLS is thoroughly studied through theoretic analysis and experiments under synthetic/real network data traces, with comparison to several related sampling methods. The results demonstrate that the proposed ANLS can significantly improve the estimation accuracy, particularly for small-size flows, while maintain a memory and processing overhead comparable to existing methods.

Sampling is increasingly utilized by passive measurement systems to save the resources consumption. However, the widely adopted static linear sampling selects packets with the same sampling rate (probability) for both large flows and small flows, which leads to intolerably high relative error for small flows. In order to bound the relative error for both small and large flows, we have proposed an adaptive nonlinear sampling method for passive measurement, which dynamically tunes the sampling rate according to the counter value. We have provided the unbiased estimation of the actual number of events n and have demonstrated that the relative error is radic[(1-1/n)a/2] for both large flows and small flows, where a is a constant parameter, and the counter size is bounded by a logarithmic function, log(1+an)/log(1+a). The theoretical and experimental results have shown that the proposed adaptive sampling method obtain a better tradeoff between relative error and memory consumption than existing sampling methods.

Per-flow queuing is believed to be able to guarantee advanced Quality of Service (QoS) for each flow. With the dramatic increase of link speed and number of traffic flows, per-flow queuing faces a great challenge since millions of queues need to be maintained for implementation in a traditional sense. In this paper, by setting only a small number of physical queues, we propose a Dynamic Queue Sharing (DQS) mechanism to achieve an equal performance to the pure per-flow queuing with a lower cost. The proposed mechanism is based on an interesting fact that the number of simultaneous active flows in the router buffer is far less than that of in-progress flows. In DQS, a physical queue is dynamically created on-demand when a new flow comes and then dynamically released when the flow temporarily pauses. Hashing and binary sorting tree (or linked list) are combined to manage the mapping between flows and queues, so as to isolate flows in different queues. Theoretical analysis and traces experiments are conducted to evaluate DQS. The results demonstrate that when the parameters are well set, the operation delay is less than two time cycles in average with an extra memory of 16k bits.

With the continuous advances in optical communications technology, the link transmission speed of Internet backbone has been increasing rapidly. This in turn demands more powerful IP address lookup engine. In this paper, we propose a power-efficient parallel TCAM-based lookup engine with a distributed logical caching scheme for dynamic load-balancing. In order to distribute the lookup requests among multiple TCAM chips, a smart partitioning approach called pre-order splitting divides the route table into multiple sub-tables for parallel processing. Meanwhile, by virtual of the cache-based load balancing scheme with slow-update mechanism, a speedup factor ofN-1 can be guaranteed for a system with N (N>2) TCAM chips, even with unbalanced bursty lookup requests.

Flow-level traffic measurement is important for network management. The widely used centralized per-flow measurement faces a great challenge due to the demanding requirement on both memory bandwidth and memory size within a single traffic monitor. This paper addresses the issue of deploying a Distributed Passive Measurement System (DPMS) in a large scale network; specifically, we study how to optimally place traffic monitors and sample stochastic traffic flows, so that the probability of a packet being sampled (a.k.a. measurement coverage) is maximized. We formulate this problem as a Stochastic Chance Constrained Optimization (SCCO) problem; and we propose a Hybrid Intelligent (HI) algorithm to solve this problem. The HI algorithm consists of two major components, namely, uncertain function approximation and genetic algorithm. Equipped with the HI algorithm, we are able to address the optimal tradeoff between measurement coverage and deployment cost for networks with random traffic, which has not been studied before. Our simulations and experiments demonstrate the effectiveness of our algorithm, i.e., a small deployment cost or a small number of monitors are sufficient to maintain a high level of measurement coverage.

Caching, multithreading and the combination of them are the major latency hiding techniques adopted in network processors (NPs). Although they achieve great success in general purpose processors (GPPs), none of them have been well studied under the new context of packet processing. In this paper, we simulate the processing procedure of a four-PE (processing element) network processor and thoroughly evaluate different configurations of these techniques with real-life packet traces. Our major findings include: (1) In general, all of these latency hiding techniques effectively increase the traffic throughput and robustness of NP; but thread allocation policy has great impact on their performance. (2) If assigning packets of the same flow to different threads is allowed, multithreading keeps the PE in a working state as long as possible and less jitter in packet sending rate is resulted than caching schemes; otherwise, a cache with a reasonable size outperforms multithreading in almost all metrics such as traffic throughput, packet loss rate, queuing and total delay. (3) When access latency is comparable to the working time of execution unit, the performance of multithreading is more sensitive to packet arrival process and memory reference pattern than caching. In short, caching and multithreading have their respective advantages under different environment. In some cases, combined caching and multithreading tend to bring more performance gain than simply adding more threads or cache entries.

Prior survey of RED algorithm deployment on multiqueue system with shared buffer was unfair and sensitive to congestion level by statically setting the parameters. In this paper, our goal is to deploy the Random Early Detection (RED) algorithm in routers on shared buffer and solve these problems. A novel buffer management scheme that dynamically adjusts the parameters of RED named RED-ODT is proposed. Simulations under uniform traffic load and nonuniform traffic load are given, the results of which ascertain and demonstrate the superiority of the proposed scheme in terms of low packet drop ratio, satisfying buffer utilization and fairness. Simulation also shows that RED-ODT is insensitive to congestion level.

Ternary content-addressable memory (TCAM) is widely used in high-speed route lookup engines. However, restricted by the memory access speed, the route lookup engines for next-generation terabit routers demand exploiting parallelism among multiple TCAMs. Traditional parallel methods always incur excessive redundancy and high power consumption. We propose An original TCAM-based IP lookup scheme that achieves an ultra high lookup throughput and a high utilization of the memory while being power efficient. In our multichip scheme, we devise a load-balanced TCAM table construction algorithm together with an adaptive load balancing mechanism. The power efficiency is well controlled by decreasing the number of TCAM entries triggered in each lookup operation. Using 133 MHz TCAM chips and given 25% more TCAM entries than the original route table, the proposed scheme achieves a lookup throughput of up to 533 Mpps and is simple for ASIC implementation.