1. Vijay Vazirani, Georgia Tech "The Steiner Tree Problem and its Generalizations" The Steiner tree problem was defined by Gauss in a letter to Schumacher, and occupies today a central place in the emerging theory of approximation algorithms. In this talk, we will outline ideas behind three results obtained in the last year: Promel and Steger's algorithm for Steiner trees via matriod parity, Jain's factor 2 algorithm for the generalized Steiner network problem, and joint work with Rajagopalan on using the bidirected cut relaxation for this problem. 2. Mehdi Hoseyni-Nasab, Rutgers University "Parallel Simulation of Communication Networks by Time Segmentation" Discrete event simulation has proven to be an effective method in analysis of modern communication networks. However, producing reliable estimators for the performance measures of such systems often requires highly extensive computations. Therefore, developing algorithms and techniques for simulating such systems on parallel processors is a crucial part of numerical evaluation of these systems. We present a time parallel simulation approach, namely the time segmentation method, that can be used to efficiently generate long sample paths of discrete event systems. We demonstrate the applicability of this method to parallel simulation of a variety of queueing models of communication networks. Furthermore, we study the extent of accuracy and efficiency of the method through various analytical and numerical results. 3. Michael Krivelevich, Rutgers University "The choice number of random bipartite graphs" The choice number ch(G) of a graph G is the minimum integer k such that for every assignment of a list S(v) of k colors to every vertex v of G (lists for different vertices may be different), there is a proper coloring of G that assigns to each vertex v a color from S(v). Although it is a straightforward generalization of the chromatic number of a graph, the choice number appears to be a much more complicated parameter and much less is known about it. I will discuss the problem of determining the asymptotic behavior of the choice number of random bipartite graphs. A random bipartite graph G(n,n,p) is obtained by taking two disjoint subsets of vertices A and B of cardinality n each and by connecting a vertex from A and that from B by an edge randomly and independently with probability p=p(n). Our main result states that for all values of the edge probability p(n), the choice number of the random bipartite graph G(n,n,p) is almost surely (1+o(1))log_2(np). This is a joint work with Noga Alon, Tel Aviv University, Israel. 4. Mark Smith, AT&T Labs Formal Verification of Safety and Performance Properties of TCP Selective Acknowledgment We present a formal proof that the selective acknowledgment (SACK) mechanism that is being proposed as a new standard option for TCP does not violate the safety properties of the acknowledgment (ACK) mechanism that is currently used with TCP. The new mechanism is being proposed to improve the performance of TCP when multiple packets are lost from one window of data. With selective acknowledgment, non-contiguous blocks of data can be acknowledged, and the sender only has to retransmit data that is actually lost. The proposed mechanism for implementing the SACK option for TCP is sufficiently complicated that it is not obvious that it is indeed safe. Because this mechanism is being proposed as a new standard for TCP, we think it is important to formally verify its safety properties. We first present a formal automaton model of the SACK protocol. We then verify that SACK is indeed safe. The verification is done by first defining a simple specification of the required safety properties. the protocol is supposed to satisfy. We then use invariant assertion and simulation techniques to show the protocol indeed satisfies these properties. Using the model we also show that SACK can improve the time it takes for the sender to recover from multiple packet losses, compared to the cumulative ACK protocol. Since there is additional information at the sender, SACK can save a round-trip time which the cumulative ACK mechanism has to wait before retransmitting subsequent packets lost after the very first loss.Other Workshops

DIMACS Homepage

Contacting the Center

Document last modified on September 25, 1998.