Recently, deep learning-based methods for blind reverberation time estimation have been proposed, and outperform those based on conventional signal processing. The signal processing approaches extract the reverberant environmental features of sound by statistical analysis, while deep learning approaches train a network to capture the relationship between acoustic features and the reverberation time. In this letter, we propose a method for blind reverberation time estimation that explicitly reflects physical properties of reverberation by combining the deep learning approach, attentive pooling, and statistical characteristics of reverberant speech obtained using a signal processing method, i.e., spectral decay rates (SDRs). The results obtained with the proposed blind reverberation time estimation method are superior to the previously published state-of-the-art results for the EVAL dataset of the ACE Challenge. This work can be considered a good example of the collaboration between signal processing expertise and deep learning approach.

Advanced computer security systems rely on a host of detectors that examine anomalies, or known signatures, to qualify network traffic. Anomaly detectors usually come at greater cost in resources over signature detectors spurring the desire to translate anomalies into identifiable signatures. Automatic Signature Generation (ASG) attempts to automate the process of creating signatures to describe newly identified malicious network traffic. However, the quality of the signatures created in ASG depends on the ability to identify malicious traffic which remains a difficult problem plagued by massive amounts of data, high-speed links, and an adversarial environment. As a result, the detection process itself can greatly hamper the process of Automatic Signature Generation.This research attempts to leverage the Metasploit framework to provide a simulation environment that can execute exploits and record those attacks without interference from rogue users or any reliance on detection methods. This simulation environment side-steps the problem of identifying the malicious traffic because the executed exploits are known malicious and isolated. The Metasploit framework provides many tools for mutating and varying attack signatures such that each execution of an exploit may have a wildly different signature. We employ this mutational feature of Metasploit, and use prior ASG techniques, to create a smaller set of signatures that address the core of an attack rather than quantifying each variant. We demonstrate that creating signatures in such an environment is not only viable, but may even be desirablein order for a user to have the most effective signature set for their purpose.

The performance of Network Intrusion Detection Systems (NIDS) depends heavily on the inputs to the system (rules and network traffic). A common trend in the evaluation of NIDS is to use a narrow selection of publicly or privately available rule-sets and traffic. Private rule-sets and traffic make the repeatability of experiments difficult while publicly available rule-sets and traffic often lack the diversity to explore the NIDS's true operating range. This can cause misleading results in the face of inputs that do not adequately test the NIDS. To improve diversity and provide better context for evaluations it is necessary to employ synthesized traffic and rules in addition to the use of public or private traffic and rule-sets. This research expands on previous models and tools to provide systematic means for increasing the diversity and context of any evaluation providing for a broader perspective from which to view NIDS performance and compare results.

To support scalable, flexible software-defined networking, OpenFlow is designed to provide granular traffic control across multiple vendor's network devices for efficient flow processing. Decision-tree packet classification algorithms do not scale to the number of flow table fields while decomposition algorithms such as RFC fail to provide necessary incremental update and determinism. Since searching in a single field is well studied, e.g. Longest Prefix Match (LPM) for prefix fields, we propose a decomposition approach which performs individual search on each flow table field, aggregates these results and conducts a query in a single hash table. Our approach scales well to the number of fields and allows incremental update. Meanwhile deterministic query is enabled for high-speed search. As far as we know our proposal is the first efficient decomposition approach to address multidimensional match in an OpenFlow flow table with an arbitrary number of fields as well as any match type. Theoretical analysis and experiments using synthetic classifiers justify the performance improvement.

Regular expressions have become a fixture in network security systems such as Network Intrusion Detection, Spam email filtering, and Antivirus. Unfortunately, regular expressions require considerably more resources in matching over fixed binary or character strings. Much research has focused on improving matching architectures or hardware support to create more efficient regular expression matching. This research, however, investigated whether or not the regular expression set itself contained any lever that might make for creating more efficient automata prior to moving such automata to any specific matching architecture or hardware. We found that typical Non-deterministic Finite Automata (NFA) construction methodologies create redundant paths in the NFA when used with the complex rule-sets employed in network security. This stems directly from the fact that creating optimized NFA is a hard problem. As such, we created REduce, a tool that uses shared prefixes among regular expressions as a heuristic to eliminate redundant paths among shared prefixes within constructed NFA. The end result is smaller matching automata (between 4-50% depending on the rule-set) and a 4-900% improvement in throughput due to reductions in active state. More importantly, REduce only targets NFA construction, thus the generated NFA can be converted to any specific matching architecture or hardware for cumulative improvement.

Network Intrusion Detection Systems (NIDS) examine millions of network packets searching for malicious traffic. Multi-gigabit line-speeds combined with growing databases of rules lead to dropped packets as the load exceeds the capacity of the device. Several areas of research have attempted to mitigate this problem through improving packet inspection efficiency, increasing resources, or reducing the examined population. A popular method for reducing the population examined is to employ run-time filters that can provide a quick check to determine that a given network packet cannot match a particular rule set. While this technique is an excellent method for reducing the population under examination, rogue elements can trivially bypass such filters with specially crafted packets and render the run-time filters effectively useless. Since the filtering comes at the cost of extra processing a filtering solution could actually perform worse than a non-filtered solution under such pandemic circumstances. To defend against such attacks, it is necessary to consider run-time filters as an independent anomaly detector capable of detecting attacks against itself. Such anomaly detection, together with judicious rate-limiting of traffic forwarded to full packet inspection, allows the detection, logging, and mitigation of attacks targeted at the filters while maintaining the overall improvements in NIDS performance garnered from using run-time filters.

Longest Prefix Matching in IP Address lookup remains a bottleneck for high-speed routers where large volumes of traffic at multi-gigabyte link speeds require extremely fast lookup time. By taking advantage of bitmap and hashing techniques effectively used in Tree Bitmap algorithm and Binary hash searching on prefix length algorithm we propose a hierarchical hashing scheme based on observations about prefix length distribution in real routing tables. Theoretical analysis and experiments using real routing tables show that our scheme significantly improve IP lookup efficiency by remarkably reducing the number of memory access, consuming less memory and enabling fast update.

Ternary Content-Addressable Memory (TCAM) is the de facto industrial standard to perform packet classification. However inefficient representation of port ranges results in the range expansion problem which sharply degrades TCAM storage performance. A range has to be converted into a set of prefixes with each stored in a separate TCAM entry. The range expansion problem occurs when a rule with multiple range fields causes a multiplicative expansion in the number of TCAM entries. Unfortunately, the problem is growing worse as an increasing number of such rules in “real-world” classifiers are in use. To address range expansion our Divide-and-Conquer Scheme (DCS) fulfills the Divide-and-Conquer principle in two levels. First, we divide an individual range through range partitioning. A class of ranges can be optimally represented through a novel range encoding we developed. We observe the extensive presence of DCS-compatible ranges in real classifiers and more can be retrieved through our partitioning scheme. Second we divide the ranges in a classifier in terms of a hybrid utilization of various schemes. Technology advancement provides the necessary support for an open and flexible logical TCAM block division in order to avoid expensive hardware modifications and allow the use of DCS directly upon TCAM blocks. Our scheme allows fast preprocessing, constant time searching, and dynamic incremental update. Theoretical analysis and simulation using synthetic classifiers show a substantial storage improvement using our scheme.

Intrusion Detection Systems (IDS) play an important role in network security. The main challenge is how to find occurrences of patterns defined in the rule set which describe the signature of malicious activities. In this paper, we propose an efficient exact pattern matching algorithm based on the bit-parallel approach. Experimental results show that our algorithm outperforms the traditional Aho-Corasick automaton at the cost of a small number of false positives.

Packet classification is primarily used by network devices, such as routers and firewalls, to do additional processing such as packet filtering, and Quality-of-Service (QoS) for a specific subset of network packets. In decision tree based packet classification system, packets are classified by searching in the tree data structure. Tree search presents significant challenges because it requires a number of unpredictable and irregular memory accesses. Since packet classification is per-packet operation and memory latency (caused by cache and TLB misses) is considerably high, any technique that can reduce cache and TLB misses can be useful in practice for improving lookup time in packet classification. In this paper, we present an efficient memory layout for the tree data structure which ensures the movement of data optimally among the different levels of the memory hierarchy on general purpose processors. In particular, for a given node size, the number of accessed cache lines (and memory pages) is minimized by our proposed memory layout resulting in less number of cache and TLB misses. This reduction directly contributes in improving the look up performance. The decision tree laid out in the proposed layout can also exploit the strong computing power of multi-core architecture by leveraging data- and thread-level parallelism. Experimental results on two different state-of-the-art processors show that significant performance improvements (40–55% faster) and near-linear speedup (3.8× on quad cores) on multi-core architecture is achievable by applying our proposed memory layout for the packet classification tree data structure.

Ternary Content Addressable Memories (CAMs) are widely used by high-speed routers to find matching routes in a routing table, because they enable the longest prefix matching operation to complete in a single clock cycle. However, they are costly and their power consumption is very high and some solutions have been proposed. But some issues have not been well studied: first, the memory accesses often take down the high speed of TCAMs; second, the prefixes must be sorted in prefix length decreasing order, which makes the update of routing table very slow. Third, even though the TCAMs are pretty fast, they can only process one match at one time, which make them unscalable. In this paper, we first discuss these problems and propose an efficient algorithm to solve these problems.

In a P2P-based media distribution network (PMDN), content migration is one of the key problems that affect the overall performance of a system. In the system hierarchy, the content migration problem consists of two levels of migration: provider-level migration and user-level migration. In this paper, we focus on the former, provider-level migration, where the goal is to reduce data migration cost while enhancing the local cache hit ratio of media contents. Since this is an NP-complete problem, we propose two types of heuristic migration strategies: object-benefit-based migration (OBM) and peer-benefit-based migration (PBM). The former maximizes the local benefits in allocating a data object to a certain node, while the latter maximizes the benefit of each peer. Experimental results show the effectiveness of both algorithms, which significantly outperform random and round-robin migration schemes.

Distributed Denial of Service (DDoS) attacks pose one of the most serious security threats to the Internet. We examine the drawbacks of existing defense schemes. To combat these deficiencies, we propose a credit-based defense system: TrustGuard. Essentially, flows accumulate credit based on the diversity of their packet-size distribution. The more diverse the flow, the more credit it has. Since DDoS attacks demonstrate low diversity they accumulate less credit and are likely to be dropped by the system. Naturally, the performance of TrustGuard greatly depends on the choice of credit accumulation and flow selection methods. We derive our solution by identifying the essential characteristics of DDoS attacks. Our analysis accounts for both micro and macro behaviors of DDoS attacks. The primary goal of this work is to not only detect the occurrence of a DDoS attack, but to also identify the attackers and victims involved. Experimental results demonstrate that TrustGuard performs admirably in both cases.

This paper presents an approach for implementing a 8-tap high-performance digital FIR (Finite Impulse Response) filter using Logarithmic Number System(LNS). In the past, FIR filters were implemented by conventional number system; therefore, the speed was limited due to the multiply accumulate operations. We realize a fast FIR filter by utilizing the Logarithmic Number System, which allows simple implementation of multiplication using a fixed-point adder. And the serious demerit of Logarithmic Number System's algorithm, conversions to and from the conventional number representations is effectively overcome by utilizing our pipeline architecture, so the delay and complexity of the filter is reduced. The critical path was reduced from a multiply-accumulate operation to an adder operation, and our FIR filter can operate at 1.3G Hz under the condition of 1.2 V power supply using SMIC 0.13um CMOS technology, and requires approximate 27 percent lesser area than the original FIR filter.

Many network security applications in today's networks are based on deep packet inspection, checking not only the header portion but also the payload portion of a packet. For example, traffic monitoring, layer-7 filtering, and network intrusion detection all require an accurate analysis of packet content in search for predefined patterns to identify specific classes of applications, viruses, attack signatures, etc. Regular expressions are often used to represent such patterns. They are implemented using finite automata, which take the payload of a packet as an input string. However, existing approaches, both non-deterministic finite automata (NFA) and deterministic finite automata (DFA), do not deal with compressed traffic, which becomes more and more popular in HTTP applications. In this paper, we propose an efficient algorithm for regular expression matching to implement deep packet inspection on compressed traffic. Based on the observations of DFA, we design a scheme to skip most of the matching process in the compressed parts of traffic. To the best of our knowledge, this is the first effort to design an efficient regular expression matching on compressed traffic. We evaluate our algorithm using rule sets provided by Snort, a popular open-source intrusion detection system. The evaluation results show that our approach can reduce the number of state access in the DFA significantly.

Traffic traces provide valuable data to researchers and organizations alike. However, organizations that provide this information do not wish to expose the internal workings of their networks to potential attack. Traffic trace anonymization attempts to mitigate this concern by hiding sensitive information while preserving most of the empirical value of the trace. Unfortunately, many attacks such as statistical fingerprinting, known-plaintext, and port evaluation can serve to identify communications within a trace which can lead an attacker to the real-world identities of anonymized devices. The inherent graph structure embedded in network traffic stands as a primary lever in achieving such de-anonymization. We propose Netshuffle, a method that distorts the graph structure in the anonymized trace such that an attacker cannot rely on the edges (communications) to identify a particular end-node (device). In essence, we shuffle the edges of the graph like a deck of cards so that even if an attacker can identify an edge, that edge does not necessarily connect to the intended target. Thus, inferences based on features of communications will either lead an attacker astray, or force the attacker to guess as to the identity of the targeted node from several indistinguishable candidates. Netshuffle provides a complimentary vector of protection to current anonymization techniques at limited cost in data utility.

Over the past decade, various intrusion detection and prevention systems have been proposed to detect DDoS attacks and mitigate the caused damage. However, many existing IDS systems still keep per-flow state to detect anomaly, and thus do not scale with link speeds in multi-gigabit networks. In this paper, we present a two-level approach for scalable and accurate DDoS attack detection by exploiting the asymmetry in the attack traffic. In the coarse level, we use a modified count-min sketch (MCS) for fast detection, and in the fine level, we propose a bidirectional count sketch (BCS) to achieve better accuracy. At both detection levels, sketch structures are utilized to ensure the scalability of our scheme. The main advantage of our approach is that it can track the victims of attacks without recording every IPaddress found in the traffic. Our scheme can save over 90% key storage. Such feature is significant for the detection in the highspeed environment. Experimental results using the real Internet traffic show that our approach is able to quickly detect anomaly events and track those victims with a high level of accuracy.

Many network security applications in today's networks are based on deep packet inspection, checking not only the header portion but also the payload portion of a packet. For example, traffic monitoring, layer-7 filtering, and network intrusion detection all require an accurate analysis of packet content in search for predefined patterns to identify specific classes of applications, viruses, attack signatures, etc. Pattern matching is a major task in deep packet inspection. The two most common implementations of Pattern matching are based on Non-deterministic Finite Automata (NFAs) and Deterministic Finite Automata (DFAs), which take the payload of a packet as an input string. In this paper, we propose an efficient NFA-based pattern matching in Binary Content Addressable Memory(BCAM), which uses data search words consisting of 1s and 0s. Our approach can process multiple characters at a time using limited BCAM entries, which makes our approach scalable well. We evaluate our algorithm using patterns provided by Snort, a popular open-source intrusion detection system. The simulation results show that our approach outperforms existing CAM-based and software-based approaches.

Due the significant need for real-time anonymization we propose Real-time Netshuffle [1]; a complete graph distortion technique designed to mitigate risk to inference attacks in traffic anonymization. Real-time Netshuffle provides an additional layer of security, in concert with other on-line traffic anonymization techniques, while imposing only minimal damage to the empirical value of the data.

We present a fast cyclic redundancy check (CRC) algorithm that performs CRC computation for any length of message in parallel. Traditional CRC implementations have feedbacks, which make pipelining problematic. In the proposed approach, we eliminate feedbacks and implement a pipelined calculation of 32-bit CRC in the SMIC 0.13 ¿m CMOS technology. For a given message, the algorithm first chunks the message into blocks, each of which has a fixed size equal to the degree of the generator polynomial. Then it computes CRC for the chunked blocks in parallel using lookup tables, and the results are combined together by performing XOR operations. The simulation results show that our proposed pipelined CRC is more efficient than existing CRC implementations.

Ternary Content Addressable Memories (CAMs) are widely used in high-speed routers. They allow a longest-prefix matching operation to complete within a single clock cycle. However, TCAMs are costly and their power consumption is very high. In this paper, we identify two kinds of redundancy in the usage of TCAMs in IP route lookup, and propose a hybrid scheme which combines Binary CAMs and Ternary CAMs to reduce the total area and power consumption. We also introduce shared memory blocks for further simplification of the lookup circuit. The simulation result shows that our approach can save more than 50% of transistors in CAMs, compared with the traditional way, and that it reduces the critical path in IP route lookup significantly.

Packet classification is a fundamental task for network devices such as edge routers, firewalls, and intrusion detection systems. Currently, most vendors use Ternary Content Addressable Memories (TCAMs) to achieve high-performance packet classification. TCAMs use parallel hardware to check all rules simultaneously. Despite their high speed, TCAMs have a fundamental in dealing with ranges efficiently. Many packet classification rules contain range specifications, each of which needs to be translated into multiple prefixes to store in TCAMs. Such translation may result in an explosive increase in the number of required TCAM entries. In this paper, we propose a redundancy removal algorithm using a tree representation of rules. The proposed algorithm removes redundant rules and combines overlaying rules to build an equivalent, smaller rule set for a given packet classifier. This equivalent transformation can significantly reduce the number of required TCAM entries. Our experiments show a reduction of 70.9% in the number of TCAM entries. Besides, our algorithm eliminates requirement of priority encoder circuits. It can also be used as a preprocessor, in tandem with other methods, to achieve further performance improvement.

Ternary Content Addressable Memories (CAMs) are widely used by high-speed routers to find matching routes in a routing table, because they enable the longest prefix matching operation to complete in a single clock cycle. However, they are costly and their power consumption is very high. In this paper, we identify two kinds of redundancy in the usage of TCAMs in IP route lookup, and then propose a hybrid scheme which combines Binary CAMs and Ternary CAMs to reduce the total area and power consumption, exploiting the uneven distribution of IP prefix lengths in real-world IP routing tables. We also introduce shared memory blocks for further simplification of the lookup circuit. The simulation results show that our approach can save more than 50% of transistors in CAMs, compared with the traditional way in storing a set of real-world routing tables, and that it reduces the critical path in IP route lookup significantly.

Recently, many new types of distributed denial of service (DDoS) attacks have emerged, posing a great challenge to intrusion detection systems. In this paper, we introduce a new type of DDoS attacks called stealthy DDoS attacks, which can be launched by sophisticated attackers. Such attacks are different from traditional DDoS attacks in that they cannot be detected by previous detection methods effectively. In response to this type of DDoS attacks, we propose a detection approach based on time-series decomposition, which divides the original time series into trend and random components. It then applies a double autocorrelation technique and an improved cumulative sum technique to the trend and random components, respectively, to detect anomalies in both components. By separately examining each component and synthetically evaluating the overall results, the proposed approach can greatly reduce not only false positives and negatives but also detection latency. In addition, to make our method more generally applicable, we apply an adaptive sliding-window to our real-time algorithm. We evaluate the performance of the proposed approach using real Internet traces, demonstrating its effectiveness.

Many network security applications in today's networks are based on deep packet inspection, checking not only the header portion but also the payload portion of a packet. For example, traffic monitoring, layer-7 filtering, and network intrusion detection all require an accurate analysis of packet content in search for predefined patterns to identify specific classes of applications, viruses, attack signatures, etc. Regular expressions are often used to represent such patterns. They are implemented using finite automata, which take the payload of a packet as an input string. However, existing approaches, both non-deterministic finite automata (NFA) and deterministic finite automata (DFA), have limitations; NFAs have excessive time complexity while DFAs have excessive space complexity. In this paper, we propose an efficient algorithm for regular expression matching to implement deep packet inspection on multi-core architecture. A regular expression is split into NFA-friendly components and DFA-friendly components, which are then assigned to different cores. This hybrid method combines the merits of NFA and DFA implementations, and efficiently takes advantage of multi-core architecture. We evaluate our algorithm using rule sets provided by Snort, a popular open-source intrusion detection system. The simulation results show that our approach outperforms existing NFA/DFA and hybrid approaches. Furthermore, our algorithm performs well on the important issues on multi-core architecture design, such as load balancing, data locality and communication between cores.

Packet classification is one of the crucial components of application such as firewalls, intrusion detection, and differentiated services. For example, an intrusion detection system (IDS) classifies packets either as benign or malicious and alerts the network administrator when hostile traffic is detected. Since existing IDS spend the majority of CPU time in packet classification, an IDS fails to detect malicious packets under high load. Many ideas have been proposed to make the packet inspection faster so that an IDS spends less time in packet classification. However, because of the increasing number of security threats and vulnerabilities, the number of rules often exceeds thousands, requiring more than hundreds of megabytes of memory. As a result, an IDS spends longer time to classify packets since each packet incurs many memory accesses, and thus the throughput of an IDS is limited by memory bandwidth. The problem can be mitigated by exploiting locality in traffic patterns. In this paper, we propose npf, a fast and traffic-adaptive packet classifier which dynamically reorganizes the internal data structure based on the traffic pattern. Unlike existing approaches requiring a separate, off-line reorganization phase, npf performs reorganization on-line with little overhead, resulting in higher throughput without compromising accuracy. Experimental results on our test bed show that npf outperforms a traditional packet classifier by spending an order of magnitude less time per packet in order to classify the packet.

A rule-based intrusion detection system compares the incoming packets against rule set in order to detect intrusion. Unfortunately, it spends the majority of CPU time in packet classification to search for rules that match each packet. A common approach is to build a graph such as rule trees or finite automata for a given rule set, and traverse it using a packet as an input string. Because of the increasing number of security threats and vulnerabilities, the number of rules often exceeds thousands requiring more than hundreds of megabytes of memory. Exploring such a huge graph becomes a major bottleneck in high-speed networks since each packet incurs many memory accesses with little locality. In this paper, we propose rule hashing for fast packet classification in intrusion detection systems. The rule hashing, combined with hierarchical rule trees, saves memory and reduce the number of memory accesses by allowing the whole working set to be accommodated in a cache in most of the time, and thus improves response times in finding matching rules. We implement our algorithm in Snort, a popular open-source intrusion detection system. Experimental results show that our implementation is faster than original Snort to deal with the same real packet traces while consuming an order of magnitude less memory.

Intrusion detection systems spend the majority of CPU time on matching packets against rules. Hence, fast identification of matches is crucial. Previous approaches may result in poor performance under certain traffic conditions because they either do not respond to traffic pattern or require setup time to organize rules whenever traffic pattern changes. We propose a two-stage packet matching to reduce matching time with little overhead. The first stage applies a small number of most-frequently matched rules. Only a fraction of packets are passed to the second stage, experiencing longer processing time. Rules in the first stage are constantly updated as their frequencies change.

In this paper, we propose a new clustering approach, bandwidth-adaptive clustering (BAC), for MANETs. BAC forms and maintains clusters using only local topology information. To adapt to network conditions and reduce the message overhead, BAC makes members forward the maintenance messages probabilistically based on available bandwidth. The multi-hop nature and Merge operation of BAC reduce the changes in case of mobility and achieve fewer consistent clusters. By bounding cluster size and the number of hops between members and clusterheads, BAC achieves more control on the number of formed clusters and the compactness of clusters. Simulation results demonstrate BAC's better performance on construction and maintenance of clusters in case of mobility, adaptiveness to network conditions, and effectiveness in reducing message overhead with nearly no performance degradation.

Abstract — Internet paths sharing the same bottleneck can be identified using several shared congestion detection techniques. However, all of these techniques have been designed to detect shared congestion between a pair of paths. To cluster N paths by shared congestion, a straightforward approach of using pairwise tests would require O(N 2) time complexity. In this paper, we present a scalable approach to cluster Internet paths based on DCW (Delay Correlation with Wavelet denoising) which does not require a common end point between paths. We present a function to map each path’s measurement data into a point in a multidimensional space such that points are close to each other if and only if the corresponding paths share congestion. Because points in the space are indexed using a tree-like structure, the computational complexity of clustering N paths can be reduced to O(N log N). The indexing overhead can be further improved by reducing dimensionality of the space through wavelet transform. Computation cost is kept low by reusing for dimensionality reduction the same wavelet coefficients obtained in DCW. Our approach is evaluated by simulations and found to be effective for a large N. The tradeoff between dimensionality and clustering accuracy is shown empirically. I.

The overlay network approach is an emerging technique to satisfy the strict requirements for various real-time multimedia services. However, overlay networks suffer from a shared congestion problem since each unicast flow may interfere with each other in the common underlying links. Most previous techniques to detect shared congestion have limitations when applied as a general solution, since they assume perfect synchronization between probing packets. However, our recent work shows that a technique based on wavelet denoising can overcome the limitations by mitigating the interfering effects such as synchronization offset and the random fluctuations of queueing delay; the proposed technique provides a more robust and accurate detection in the presence of a large amount of synchronization offset In this paper, wavelet denoising is tailored to the characteristics of queueing delay on packet networks. The wavelet denoising based technique is verified through extensive simulations. The efficacy of the proposed approach is demonstrated by the detection accuracy and convergence speed.

Per-flow congestion control helps endpoints fairly and efficiently share network resources. Better utilization of network resources can be achieved, however, if congestion management algorithms can determine when two different flows share a congested link. Such knowledge can be used to implement cooperative congestion control or improve the overlay topology of a P2P system. Previous techniques to detect shared congestion either assume a common source or destination node, drop-tail queueing, or a single point of congestion. We propose in this paper a novel technique, applicable to any pair of paths on the Internet, without such limitations. Our technique employs a signal processing method, wavelet denoising, to separate queueing delay caused by network congestion from various other delay variations. Our wavelet-based technique is evaluated through both simulations and Internet experiments. We show that, when detecting shared congestion of paths with a common endpoint, our technique provides faster convergence and higher accuracy while using fewer packets than previous techniques, and that it also accurately determines when there is no shared congestion. Furthermore, we show that our technique is robust and accurate for paths without a common endpoint or synchronized clocks; more specifically, it can tolerate a synchronization offset of up to one second between two packet flows.

Internet radio and television stations require significant bandwidth to support delivery of high quality audio and video streams to a large number of receivers. IP multicast is an appropriate delivery model for these applications. However, widespread deployment of IP multicast on the Internet is unlikely in the near future. An alternative is to build a multicast tree in the application layer Previous studies have addressed tree construction in the application layer However most of them focus on reducing delay. Few systems have been designed to achieve a high throughput for bandwidth-intensive applications. In this paper we present a distributed algorithm to build an application-layer tree. We prove that our algorithm finds a tree such that the average incoming rate of receivers in the tree is maximized (under certain network model assumptions). We also describe protocols that implement the algorithm. For implementation on the Internet, there is a tradeoff between the overhead of available bandwidth measurements and fast convergence to the optimal tree. This tradeoff can be controlled by tuning some parameters in our protocols. Our protocols are also designed to maintain a small number, O(log n), of soft states per node to adapt to network changes and node failures.

We investigate the fairness, smoothness, responsiveness, and aggressiveness of TCP and three representative TCP-friendly congestion control protocols: GAIMD, TFRC, and TEAR. The properties are evaluated both analytically and via simulation by studying protocol responses to three network environment changes. The first environment change is the inherent fluctuations in a stationary network environment. Under this scenario, we consider three types of sending rate variations: smoothness, short-term fairness, and long-term fairness. For a stationary environment, we observe that smoothness and fairness are positively correlated. We derive an analytical expression for the sending rate coefficient of variation for each of the four protocols. These analytical results match well with experimental results. The other two environment changes we study are a step increase of network congestion and a step increase of available bandwidth. Protocol responses to these changes reflect their responsiveness and aggressiveness, respectively.

Multicast sessions may have a large number of receivers with heterogeneous reception capacities. To accommodate this heterogeneity various multi-rate schemes, based upon the use of layering or replication, have been proposed. We consider the optimal partitioning of receivers into groups for multi-rate schemes. For a general class of utility functions, we formulate the partitioning problem as an optimization problem to maximize the sum of receiver utilities. We present an efficient dynamic programming algorithm to solve the partitioning problem, and prove that the solution it finds is optimal. We also show that the majority of the benefit of a multi-rate scheme can be gained by using a small number of groups (or layers), say 4 to 5. To illustrate our solution approach, we apply it to the case where receiver capacities are determined by multi-rate max-min fair rates. A complete protocol for receiver rates computation, rates collection, optimal receiver partitioning, and receiver adaptation is presented. We then compare our approach with other multi-rate approaches as well as a single-rate approach. Experimental results show that our approach provides substantial performance improvements.