DIMACS Mixer Series - October 2, 1998

NEC Research Institute, Princeton, NJ

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