Packet filters provide rules for classifying packets based on header fields. High speed packet classification has received much study. However, the twin problems of fast updates and fast conflict detection have not received much attention. A conflict occurs when two classifiers overlap, potentially creating ambiguity for packets that match both filters. For example, if Rule 1 specifies that all packets going to CNN be rate controlled and Rule 2 specifies that all packets coming from Walmart be given high priority, the rules conflict for traffic from Walmart to CNN. There has been prior work on efficient conflict detection for two dimensional classifiers. However, the best known algorithm for conflict detection for general classifiers is the naive O(N^2) algorithm of comparing each pair of rules for a conflict. In this paper, we describe an efficient and scalable conflict detection algorithm for the general case that is significantly faster. For example, for a database of 20,000 rules, our algorithm is 40 times faster than the naive implementation. Even without considering conflicts, our algorithm also provides a packet classifier with fast updates and fast lookups that can be used for stateful packet filtering.

Pre-2018 CSE ID: CS2002-0718

Accurate network traffic measurement is required for accounting, bandwidth provisioning and detecting DoS attacks. These applications see the traffic as a collection of flows they need to measure. As link speeds and the number of flows increase, keeping a counter for each flow is too expensive (using SRAM) or slow (using DRAM). The current state-of-the-art methods (Cisco's sampled NetFlow) which log periodically sampled packets are slow, inaccurate and resource-intensive. Previous work showed that at different granularities a small number of ``heavy hitters'' accounts for a large share of traffic. Our paper introduces a paradigm shift by concentrating on measuring only large flows --- those above some threshold such as 0.1\% of the link capacity. We propose two novel and scalable algorithms for identifying the large flows: sample and hold and multistage filters, which take a constant number of memory references per packet and use a small amount of memory. If M is the available memory, we show analytically that the errors of our new algorithms are proportional to 1/M; by contrast, the error of an algorithm based on classical sampling is proportional to 1/sqrt(M), thus providing much less accuracy for the same amount of memory. We also describe further optimizations such as early removal and conservative update that further improve the accuracy of our algorithms, as measured on real traffic traces, by an order of magnitude. Our schemes allow a new form of accounting called threshold accounting in which only flows above a threshold are charged by usage while the rest are charged a fixed fee. Threshold accounting generalizes usage-based and duration based pricing.

Pre-2018 CSE ID: CS2002-0699

We describe a new mechanism to deal with asymmetries that arise in routing protocols. We show how to avoid route asymmetries (due to non-unique shortest paths) for any shortest path protocol by adding random integer link costs. We show in detail how RIP can be modified to avoid route asymmetry with high probability, without affecting either its efficiency or performance metrics such as convergence time.

Pre-2018 CSE ID: CS2001-0685

Research in Reliable Multicast has focused on providing scalable, semi-reliable delivery of data. Such solutions based on schemes like SRM have proved adequate for multicast delivery of multimedia data or whiteboard applications, but are inadequate for the strict delivery semantics of file transfer. This paper describes a simple application called FTP-M that provides an efficient one-to-many multicast data transfer by simply extending the FTP protocol and user interface. FTP-M relies on a {\em strictly-reliable} Reliable Multicast protocol layer beneath to send data reliably to multiple receivers. In this paper, we describe the design and implementation of FTP-M. We suggest that FTP-M has the potential to be adopted as a standard way to achieve multicast file transfer.

Pre-2018 CSE ID: CS2001-0684

Useful measurement data is badly needed to help onitor and control large networks. Current approaches to solving measurement problems often assume minimal support from routers and protocols (e.g., tomography) or place the entire burden on the router to support heavyweight mechanisms (e.g. NetFlow, per-prefix counters). The thesis of this paper is that systems approaches to such problems can yield more efficient intermediate solutions by considering the ultimate use of the data, understanding implementation costs, and by distributing aspects of the solution among routers, protocols, and tools. We briefly show how these principles are indirectly applied in existing proposals for new measurement primitives. We then show how these principles can be used to derive new systems solutions to two separate problems: measuring route stability (by modifying route computation) and measuring traffic matrices (by implementing per-class counters that can yield traffic matrices with much smaller memory requirements than per-prefix counters). Beyond specifictechniques, we hope the principles in this position paper can provide a focus for discussion among researchers, router vendors, protocol designers, and network operators (the stakeholders in the measurement enterprise) to yield effective solutions to measurement problems.

Pre-2018 CSE ID: CS2003-0747

Packet classification is important for applications such as firewalls, intrusion detection, and differentiated services. Existing algorithms for packet classification reported in the literature scale poorly in either time or space as filter databases grow in size. Hardware solutions such as TCAMs do not scale to large classifiers. However, even for large classifiers (say 100,000 rules), any packet is likely to match a few (say 10) rules. Our paper seeks to exploit this observation to produce a scalable packet classification scheme called Aggregated Bit Vector (ABV). Our paper takes the bit vector search algorithm (BV) described in \cite{lucent} (which takes linear time) and adds two new ideas, recursive aggregation of bit maps and filter rearrangement, to create ABV (which can take logarithmic time for many databases). We show that ABV outperforms BV by an order of magnitude using simulations on both industrial firewall databases and synthetically generated databases.

Pre-2018 CSE ID: CS2001-0673

Advances in technology have led to the introduction of Gigabit and even Terabit links. However, latencies are limited by the speed of light, In this paper we propose a technique called Auto Inline Download which enables servers and clients to transfer a web page and its embedded data (such as images, applets, etc.,) with just one GET request. This saves overall retrieval time by eliminating the delays associated with buffered request processing and saves a round trip if the the inline data reference is in the last segment of the data transfer for the web page itself. During our experiments, we found that with the current segment size of 512 bytes, TCP will take at least 7 round trip times to transfer an average web page. This implies that even if we have infinite speed links, TCP slow start will limit the transfer of a web page to at least 490msec assumung a coast-coast latenct of 70 msec.

Pre-2018 CSE ID: CS2001-0683

It is becoming increasingly common for network devices to handle packets based on the contents of packet payloads. Example applications include intrusion detection, firewalls, web proxies, and layer seven switches. This paper analyzes the problem of intrusion detection and its reliance on fast string matching in packets. We show that the problem can be restructured to allow the use of more efficient string matching algorithms that operate on sets of patterns in parallel. We then introduce and analyze a new string matching algorithm that has average-case performance that is better than the best theoretical algorithm (Aho-Corasick) and much better than the currently deployed algorithm (multiple iterations of Boyer-Moore). Finally, we implement these algorithms in the popular intrusion detection platform Snort and analyze their relative performance on actual packet traces. Our results provide lessons on the structuring of content-based handlers, string matching algorithms in general, and the importance of performance to security.

Pre-2018 CSE ID: CS2001-0670

While the number of concurrent flows passing through backbone routers is large (more than 250,000), measurements show a small number of flows (say 10%) represent a large fraction of the traffic. Thus a desirable goal for a measurement algorithm at a backbone router is to identify (say) the top 10% of the flows using not much more than 10% of the memory needed to keep track of all flows. A similar goal would be to determine any flows that use more than (say) 1% of the link bandwidth (to catch hot spots) using only a small amount of high speed memory. Keeping state for each flow (to tell whether a flow is ``large'') is ruled out. Our paper describes an algorithm for identifying large flows using small memory and small per packet processing bounds. Our algorithm scales well even with increases in bandwidth and number of flows.

Pre-2018 CSE ID: CS2001-0666