Combinatorial and Applied Aspects of Networking

(in chronological order) 

  • 1. Gabriel Istrate, Anders Hansson, Madhav V. Marathe, Sunil Thulasidasan and Christopher L. Barrett. Semantic compression of TCP traces. In Proceedings of the IFIP NETWORKING Conference, F. Boavida et al. (editors), pp. 123-135. Lecture Notes in Computer Science, vol. 3976, Springer Verlag, 2006. 

   Despite the fact that I'm a theoretician, this is a primarily "experimental" paper. We wanted to model large TCP traces, as seen using receiver information only. One requirement was to model packet dynamics, in a way that captures packet reordering. The goal is to substantially "compress" traces, in a way that preserves the semantics of TCP.

In all fairness we did not come with a full model (though it can be completed to a full model using more recent work by Jayasumana et al.). On the other hand, the paper (that took a good deal of soul and a few years to complete) introduced a number of nice modeling ideas, in a field that is about as far from my competence as I could think of.


  • 2. Christopher L. Barrett, Gabriel Istrate, V. S. Anil Kumar, Madhav V. Marathe, Shripad Thite and Sunil Thulasidasan. Strong Edge Coloring for Channel Assignment in Wireless Radio Networks. In Proceedings of the Fourth IEEE International Conference on Pervasive Computing (PERCOMW'06), Workshop on Foundations and Algorithms for Wireless Networking, pp. 106-110. IEEE Computer Society Press, ISBN 0-7695-2520-2, 2006.

 If you model a radio network by unit disk graphs you can use distance-two matchings  as a proxy for network capacity (this was invented in a JSAC paper by Marathe, Balakrishnan et al.). This paper gives approximation algorithms for distance-two matchings for various classes of graphs relevant in the networking problem.  This is a nice area, though results of Moscibroda show that the unit-disk graph model is not realistic as a mathematical abstraction of interference. 


  • 3. Anders Hansson, Gabriel Istrate and Shiva Prasad Kasiviswanathan. Combinatorics of TCP Reordering. Journal of Combinatorial Optimization, 12 (1-2), pp. 57-70, 2006.

 Work done as a summer research project with a student. It deals with the following problem: suppose a sequence of packet ID's comes at the receiver. A buffer is used to store out-of-order packets. Can one decide whether a sequence of buffer sizes corresponds to a sequence of ID's and, moreover count the number of such sequences ? 

The paper used a model of buffer information with a practical motivation. It gave a polynomial decision algorithm and FPRAS'es in some special cases. It turns out (paper 5 below) that results are much nicer for real buffer sizes (though less practically relevant).

  • 4.  Gabriel Istrate, Anders Hansson and Guanhua Yan. Packet Reordering Metrics: Some Methodological Considerations. In Proceedings of the Second International Conference on Networking and Services (ICNS'06), Workshop on Internet Packet Dynamics, San Jose CA. IEEE Computer Society Press, ISBN 0-7695-2622-5, 2006.

 When is a metric for packet reordering useful ? Of course, it all depends on your purpose (if you can tolerate some amount of reorder then the number of inversions is not a very good metric). On the other hand a measure that takes different values on two sequences that you regard as "equivalent for practical purposes" is obviously not a good one. The paper puts forth this idea and illustrates it in the context of the following equivalence notion: two sequences of packet IDs are equivalent if they lead to the same ACKs.  The paper proves several results regarding the consistency of metrics from the literature with respect to this equivalence notion. 

 Same problem as in paper 3, this time for the "real" buffer size measure. Results are much nicer, in particular you can count preimages in polynomial time. This is one the cutest little papers I have written.