Decentralized unstructured peer-to-peer networks rely on inefficient flooding based mechanisms to locate objects. In order to limit the effects of flooding, all requests are only allowed to remain in the network for a limited number of hops. Due to this queries originating at any node in the network can only cover a small portion of the peer-to-peer overlay network. This creates situations in which objects are "not visible" to all the nodes inside of the network. This paper introduces mechanisms that have a two-folded effect, {\bf 1)} reduces the effect of flooding by identifying the common interests between the peers and organizing the peer-to-peer overlay based on these common interests ensuring that the set of peers a query is propagated through are likely to share objects in the same category of interest as the request, and {\bf 2)} guarantees finding the location of any object that has been shared in the system, by building and utilizing distributed catalogues of interests. We applied our ideas on the gnutella network and developed and deployed a modified gnutella client using our new mechanisms.

Pre-2018 CSE ID: CS2003-0740

A classifier consists of a set of rules for classifying packets based on header fields. Because core routers can have fairly large (e.g., 2000 rule) database and must use limited SRAM to meet OC-768 speeds, the best existing classification algorithms (RFC, HiCuts, ABV) are precluded because of the large amount of memory they need. Thus the general belief is that hardware solutions like CAMs are needed, despite the amount of board area and power they consume. In this paper we provide an algorithm based on a fast search structure capable of providing search results with a throughput closer to the speed of the line where speed of the line may be OC 192, i.e. a packet every 32 ns. It is based on a decision tree in which each node can be seen as a k-dimensional hypercube, in which each dimension of the hypercube is associated with a dimension in the rules of the classifier. In each node a decision is taken based on information from one or multiple fields. The fields chosen to be used in a decision process of a node are based on a set of heuristics that we develop. These heuristics take into account the overall memory that may be occupied by the whole search data structure as well as providing a maximal acceptable depth to the decision tree. The search structure also allows fast incremental updates, with an update time comparable with the time of the search. It can also be pipelined in which case the throughput may be increased to about one packet per 8 ns (limited by the speed of SRAM) in which case the packet classification operation may be applicable to OC 768 links.

Pre-2018 CSE ID: CS2002-0730

A classifier consists of a set of rules for classifying packets based on header fields. Because core routers can have fairly large (e.g., 2000 rule) database and must use limited SRAM to meet OC-768 speeds, the best existing classification algorithms (RFC, HiCuts, ABV) are precluded because of the large amount of memory they need. Thus the general belief is that hardware solutions like CAMs are needed, despite the amount of board area and power they consume. In this paper, we provide an alternative to CAMs via an Extended Grid-of-Tries (EGT) algorithm whose worst-case speed scales well with database size while using a minimal amount of memory. Our evaluation is based on real databases used by Tier 1 ISPs, and synthetic databases. EGT is based on a observation that we found holds for all the Tier 1 databases we studied: regardless of database size, any packet matches only a small number of distinct source-destination prefix pairs. The code we wrote for EGT, RFC, HiCuts, and ABV is publicly available, providing the first publicly available code to encourage experimentation with classification algorithms.

Pre-2018 CSE ID: CS2002-0719

This paper introduces a classification algorithm called HyperCuts. Like the previously best known algorithm, HiCuts, HyperCuts is based on a decision tree structure. Unlike HiCuts, however, in which each node in the decision tree represents a hyperplane, each node in the HyperCuts decision tree represents a k-dimensional hypercube, where k > 1. Using this extra degree of freedom and a new set of heuristics to find optimal hypercubes for a given amount of storage, HyperCuts can provide an order of magnitude improvement over existing classification algorithms. It uses 2 to 10 times less memory than HiCuts optimized for memory, while the worst case search time of HyperCuts is 50-500% better than that of HiCuts optimized for speed. Compared with another scheme recently introduced in Infocom 2003 called EGT-PC, HyperCuts uses 1.8-7 times less memory space while the worst case search time is up to $5$ times smaller. More importantly, unlike EGT-PC, HyperCuts can be fully pipelined to provide one classification result every memory access time, and has fast updates.

Pre-2018 CSE ID: CS2003-0736

This report describes the scaled bitmap data structure, that can accurately estimate the number of unique elements in a set (assuming the set has a continuously increasing number of elements). This data structure is particular motivated by the need toefficiently count the number of IP addresses, infected by a network worm during an epidemic.

Pre-2018 CSE ID: CS2005-0819

Network worms are a major threat to the security of today's Internet-connected hosts and networks. The combination of unmitigated connectivity and widespread software homogeneity allows worms to exploit tremendous parallelism in propagation. Modern worms spread so quickly that no human-mediated reaction to the outbreak of a new worm can hope to prevent a widespread epidemic. In this paper we propose an automated method for detecting new worms based on traffic characteristics common to most of them: highly repetitive packet content, an increasing population of sources generating infections and an increasing number of destinations being targeted. Our method generates content signatures for the worm without any human intervention. Preliminary results on a small network show promising results: we have identified three confirmed worms with a low percentage of false positives. This gives us reason to believe that our method could form the core of an effective network-level worm detection and countermeasure system capable of substantially slowing down the spread of new worms.

Pre-2018 CSE ID: CS2003-0761

Worms are a major threat to the security and reliability of today's networks. Because they can spread rapidly from computer to computer, to effectively contain them we need automated methods to very quickly identify and filter new worms before they grow into a massive epidemic. In this paper we propose such an automated approach based on identifying in real time the traffic characteristics common to all worms: highly repetitive packet content, going from an increasing number of infected hosts to very many random IP addresses of potential new victims. Our preliminary results on a small network show that our automated approach of identifying new worms is promising: it identified three confirmed worms with an encouragingly low percentage of false positives when configured with good parameters.

Pre-2018 CSE ID: CS2003-0745

Peer-to-peer systems like KaZaa use the notion of super-peers to improve search performance. In this paper, we analyze the impact of Internet Service Providers deploying these super-peers in the ir networks. The principle benefits for ISPs are the ability to perform P2P traffic engineering and to push content directly to the users, both of which translate into economic value for the ISPs. The benefit for end users is improved search performance. We propose and evaluate a technique called Topic-based Search Optimization that can be used by super-peers to improve search performance.

Pre-2018 CSE ID: CS2003-0742