- Competitive Analysis of the TCP Congestion
Control Algorithm with Professors Jeff Edmonds, Patrick
Dymond.

(pdf file of the journal version submitted) [Appeared in SPAA 03] - A New Active Queue Management Algorithm with Professors Jeff Edmonds, Patrick Dymond and Mr Kashif Ali. [submtted]
- Lower Bounds and Top-down Algorithms for
Loss-based Multicast Tree Construction

[submitted]

ABSTRACT :

While robust measurements of network dynamics are essential for the design and management of internetworks, administrative, economic and privacy issues make it impractical to monitor every link in the network. Therefore it becomes necessary to infer network and performance characteristics from end-to-end measurements. One characteristic that is frequently needed to build reliable multicast protocols is the topology of the tree used for multicast communications. Several algorithms have been proposed in the literature for making use of correlations between packets lost at each of the receivers to infer a multicast tree. In this work, we consider two aspects of the multicast tree inference problem that has not received much attention in the literature. The first problem we look at is the*sample complexity*or the number of samples required to infer multicast trees with given error bounds. Our results quantify the tradeoff between the number of samples and the probability of computing the tree correctly, and provide lower bounds on the number of samples needed to compute the tree with a given error probability. We prove that these bounds are tight by proving that some existing algorithms achieve sample complexities that are within constant factors of our lower bounds. Second, we design efficient algorithms for inferring the logical multicast tree and the loss rates on each link of the tree. Our algorithms differ from existing ones in that they construct multicast trees in a top-down manner. - The effectiveness of vaccinations on the
spread of email-based computer viruses with Mr. Hui
Wang
Accepted for publication in CCECE 2005.

ABSTRACT :

In the last decade, computer viruses have caused tremendous losses to organizations. New viruses continue to cause havoc, in spite of having better antivirus software. It is thus imperative that we understand what factors significantly influence the spread of viruses. In this paper, we model the networks of users as graphs. For simplicity, we assume that every user works only on their own computer. We assume that nodes in the graph are initially susceptible to infection. Once infected, a node may spread the virus (using perhaps, the inbox or address book) until either the virus is removed and the node is immunized. We assume that an immunized node never gets the same virus again. We study the effect of vaccinations in containing the spread of email-borne computer viruses on some traditional structured interconnection graphs, some simple small-world graphs, as well as ``Internet-like'' small-world graphs generated by the BRITE package. We test the effectiveness of vaccinations in containing the spread of viruses by looking at the total number of nodes infected for different values of the delay D which is incurred in detecting a virus, developing a vaccine and immunizing each infected node. Our simple user model assumes that a user is likely to open an email attachment (and activate the virus) with probability p and delete it with probability 1 - p. Intuitively, one would expect that the fraction of nodes infected would show a 0-1 behavior as p is varied or as D is varied. Using simulations, we demonstrate that while this is true for the traditional graphs we used, it does not hold for small-world graphs. Since user networks are known to be small-world graphs, this implies that vaccinations are far less effective on real networks than they would be if the user networks were like traditional interconnection graphs.

ABSTRACT :

While the well-known Transport Control Protocol (TCP) is a

ABSTRACT :

In this paper, we first propose a new active queue management algorithm RQM based on rates of traffic passing through a router instead of the buffer occupancy inside a router. Our algorithm does not require per-session states to be maintained at the routers. We prove that our algorithm is competitive to the optimal under some simplifying assumptions. Using simulations, we show that our algorithm is superior to the well-studied RED and REM algorithms in many scenarios.

Please send me email if you want copies of these papers.