14424091
Sustaining Availability of Web Services under Distributed Denial of Service Attacks
The recent tide of Distributed Denial of Service (DDoS) attacks against high-profile web sites demonstrate how devastating DDoS attacks are and how defenseless the Internet is under such attacks. We design a practical DDoS defense system that can protect the availability of web services during severe DDoS attacks. The basic idea behind our system is to isolate and protect legitimate traffic from a huge volume of DDoS traffic when an attack occurs. Traffic that needs to be protected can be recognized and protected using efficient cryptographic techniques. Therefore, by provisioning adequate resource (e.g., bandwidth) to legitimate traffic separated by this process, we are able to provide adequate service to a large percentage of clients during DDoS attacks. The worst-case performance (effectiveness) of the system is evaluated based on a novel game theoretical framework, which characterizes the natural adversarial relationship between a DDoS adversary and the proposed system. We also conduct a simulation study to verify a key assumption used in the game-theoretical analysis and to demonstrate the system dynamics during an attack.
10184291
Efficient and scalable query routing for unstructured peer-to-peer networks
Searching for content in peer-to-peer networks is an interesting and challenging problem. Queries in Gnutella-like unstructured systems that use flooding or random walk to search must visit O(n) nodes in a network of size n, thus consuming significant amounts of bandwidth. In this paper, we propose a query routing protocol that allows low bandwidth consumption during query forwarding using a low cost mechanism to create and maintain information about nearby objects. To achieve this, our protocol maintains a lightweight probabilistic routing table at each node that suggests the location of each object in the network. Following the corresponding routing table entries, a query can reach the destination in a small number of hops with high probability. However, maintaining routing tables in a large and highly dynamic network requires non-traditional mechanisms. We design a novel data structure called an exponentially decaying bloom filter (EDBF) that encodes such probabilistic routing tables in a highly compressed manner, and allows for efficient aggregation and propagation. The search primitives provided by our system can be used to search for single keys or multiple keywords with equal ease. Analytical modeling of our design predicts significant improvements in search efficiency, verified through extensive simulations in which we observed an order of magnitude reduction in query path length over previous proposals.
905381
On the computational complexity of maintaining GPS clock in packet scheduling
Packet scheduling is an important mechanism to provide QoS guarantees in data networks. A scheduling algorithm generally consists of two functions: one estimates how the GPS (general processor sharing) clock progresses with respect to the real time; the other decides the order of serving packets based on an estimation of their GPS start/finish times. In this work, we answer important open questions concerning the computational complexity of performing the first function. We systematically study the complexity of computing the GPS virtual start/finish times of the packets, which has long been believed to be /spl Omega/(n) per packet but has never been either proved or refuted. We also answer several other related questions such as "whether the complexity can be lower if the only thing that needs to be computed is the relative order of the GPS finish times of the packets rather than their exact values?".
195710562
On fundamental tradeoffs between delay bounds and computational complexity in packet scheduling algorithms
In this work, we clarify, extend and solve an open problem concerning the computational complexity for packet scheduling algorithms to achieve tight end-to-end delay bounds. We first focus on the difference between the time a packet finishes service in a scheduling algorithm and its virtual finish time under a GPS (General Processor Sharing) scheduler, called GPS-relative delay. We prove that, under a slightly restrictive but reasonable computational model, the lower bound computational complexity of any scheduling algorithm that guarantees O(1) GPS-relative delay bound is Ω (log 2 n) (widely believed as a "folklore theorem" but never proved). We also discover that, surprisingly, the complexity lower bound remains the same even if the delay bound is relaxed to O(na) for 0‹a⋵1. This implies that the delay-complexity tradeoff curve is "flat" in the "interval" [O(1), O(n)). We later extend both complexity results (for O(1) or O(na) delay) to a much stronger computational model. Finally, we show that the same complexity lower bounds are conditionally applicable to guaranteeing tight end-to-end delay bounds. This is done by untangling the relationship between the GPS-relative delay bound and the end-to-end delay bound.
47532017
On fundamental tradeoffs between delay bounds and computational complexity in packet scheduling algorithms
We clarify, extend, and solve a long-standing open problem concerning the computational complexity for packet scheduling algorithms to achieve tight end-to-end delay bounds. We first focus on the difference between the time a packet finishes service in a scheduling algorithm and its virtual finish time under a GPS (General Processor Sharing) scheduler, called GPS-relative delay. We prove that, under a slightly restrictive but reasonable computational model, the lower bound computational complexity of any scheduling algorithm that guarantees O(1) GPS-relative delay bound is /spl Omega/(logn). We also discover that, surprisingly, the complexity lower bound remains the same even if the delay bound is relaxed to O(n/sup a/) for 0<a<1. This implies that the delay-complexity tradeoff curve is flat in the "interval" [O(1),O(n)). We later conditionally extend both complexity results (for O(1) or O(n/sup a/) delay) to a much stronger computational model, the linear decision tree. Finally, we show that the same complexity lower bounds are conditionally applicable to guaranteeing tight end-to-end delay bounds, if the delay bounds are provided through the Latency Rate (LR) framework.
16814075
On algebraic construction of Gallager and circulant low-density parity-check codes
This correspondence presents three algebraic methods for constructing low-density parity-check (LDPC) codes. These methods are based on the structural properties of finite geometries. The first method gives a class of Gallager codes and a class of complementary Gallager codes. The second method results in two classes of circulant-LDPC codes, one in cyclic form and the other in quasi-cyclic form. The third method is a two-step hybrid method. Codes in these classes have a wide range of rates and minimum distances, and they perform well with iterative decoding.
30458595
Finding an Optimal Path without Growing the Tree
In this paper, we study a class of optimal path problems with the following phenomenon: The space complexity of the algorithms for reporting the lengths of single-source optimal paths for these problems is asymptotically smaller than the space complexity of the "standard" treegrowing algorithms for finding actual optimal paths. We present a general and efficient algorithmic paradigm for finding an actual optimal path for such problems without having to grow a single-source optimal path tree. Our paradigm is based on the "marriage-before-conquer" strategy, the prune-and-search technique, and a data structure called clipped trees. The paradigm enables us to compute an actual path for a number of optimal path problems and dynamic programming problems in computational geometry, graph theory, and combinatorial optimization. Our algorithmic solutions improve the space bounds (in certain cases, the time bounds as well) of the previously best known algorithms, and settle some open problems. Our techniques are likely to be applicable to other problems.
10511708
Automatic diagnosis and response to memory corruption vulnerabilities
Cyber attacks against networked computers have become relentless in recent years. The most common attack method is to exploit memory corruption vulnerabilities such as buffer overflow and format string bugs. This paper presents a technique to automatically identify both known and unknown memory corruption vulnerabilities. Based on the observation that a randomized program usually crashes upon a memory corruption attack, this technique uses the crash as a trigger to initiate an automatic diagnosis algorithm. The output of the diagnosis includes the instruction that is tricked to corrupt data, the call stack at the time of corruption, and the propagation history of corrupted data. These results provide useful information in fixing the vulnerabilities. Moreover, the diagnosis process also generates a signature of the attack using data/address values embedded in the malicious input message, and is used to block future attacks. Such a signature is further associated with the program execution state to reduce false positives without decreasing the detection rate. The proposed techniques enable the development of a decentralized self-diagnosing and self-protecting defense mechanism for networked computers. We report the implementation experience and experimental evaluation of a prototype system on Linux.
33593406
CrimeLink Explorer: Using Domain Knowledge to Facilitate Automated Crime Association Analysis
Link (association) analysis has been used in law enforcement and intelligence domains to extract and search associations between people from large datasets. Nonetheless, link analysis still faces many challenging problems, such as information overload, high search complexity, and heavy reliance on domain knowledge. To address these challenges and enable crime investigators to conduct automated, effective, and efficient link analysis, we proposed three techniques which include: the concept space approach, a shortest-path algorithm, and a heuristic approach that captures domain knowledge for determining importance of associations. We implemented a system called CrimeLink Explorer based on the proposed techniques. Results from our user study involving ten crime investigators from the Tucson Police Department showed that our system could help subjects conduct link analysis more efficiently. Additionally, subjects concluded that association paths found based on the heuristic approach were more accurate than those found based on the concept space approach.
5323377
Visualizing the expertise space
Expertise management systems are being widely adopted in organizations to manage tacit knowledge embedded in employees' heads. These systems have successfully applied many information technologies developed in fields such as information retrieval and document management to support expertise information collection, processing, and distribution. In this paper, we investigate the potentials of applying visualization techniques to support exploration of an expertise space. We implemented two widely applied dimensionality reduction visualization techniques, the self-organizing map and multidimensional scaling; to generate expert map and expertise field map visualizations based on an expertise data set. Our proposed approach is generic for automatic mapping of expertise space of an organization, research field, scientific domain, etc. Our initial analysis on the visualization results indicated that the expert map and expertise field map captured useful underlying structures of the expertise space and had the potential to support more efficient and effective expertise information searching and browsing.
17229097
Distance irredundance and connected domination numbers of a graph
Let k be a positive integer and G be a connected graph. This paper considers the relations among four graph theoretical parameters: the k-domination number @c"k(G), the connected k-domination number @c"k^c(G); the k-independent domination number @c"k^i(G) and the k-irredundance number ir"k(G). The authors prove that if an ir"k-set X is a k-independent set of G, then ir"k(G)[email protected]"k(G)[email protected]"k^i(G), and that for k>=2, @c"k^c(G)=1 if ir"k(G)=1, @c"k^c(G)=