(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.

- 5. Anders Hansson, Gabriel Istrate.
**Counting preimages of TCP reordering patterns.***Discrete Applied Mathematics*, (to appear), 2008.