Author Archives: gene lee

On the Interactions of Overlay Routing (Master’s Thesis 2006)

Gene Moo Lee (2006). On the Interactions of Overlay Routing. Master’s Thesis, University of Texas at Austin, May 2006. [UT Library]

Overlay routing has been successful as an incremental method to improve the current Internet routing by allowing users to select the Internet paths by themselves. By its nature, overlay routing has selfish behavior, which makes an impact on the related components of Internet routing. In this thesis, we study three interactions related to overlay routing. First, overlay routing changes the traffic patterns observed by the network operating side, which uses traffic engineering techniques to cope with the dynamic traffic demands. We improve this vertical interaction between overlay routing and traffic engineering. Secondly, the performance of overlay routing may be affected by the action of other coexisting overlays. An initial result on the horizontal interaction among multiple overlays is given. Lastly, within a single overlay network, overlay nodes can be regarded as independent decision-makers, who act strategically to maximize individual gain. We design an incentive-based framework to achieve Pareto-optimality in the internal interaction of overlay routing.

Improving Sketch Reconstruction Accuracy Using Linear Least Square Method (IMC 2005)

Lee, G. M., Liu, H., Yoon, Y., and Zhang, Y. (2005). Improving Sketch Reconstruction Accuracy Using Linear Least Square Method, In Proceedings of Internet Measurement Conference (IMC 2005), Berkeley, California.

  • IMC is a premier conference in the network measurement area (h5-index: 37)

Sketch is a sublinear space data structure that allows one to approximately reconstruct the value associated with any given key in an input data stream. It is the basis for answering a number of fundamental queries on data streams, such as range queries, finding quantiles, frequent items, etc. In the networking context, sketch has been applied to identifying heavy hitters and changes, which is critical for traffic monitoring, accounting, and network anomaly detection.

In this paper, we propose a novel approach called lsquare to significantly improve the reconstruction accuracy of the sketch data structure. Given a sketch and a set of keys, we estimate the values associated with these keys by constructing a linear system and finding the optimal solution for the system using linear least squares method. We use a large amount of real Internet traffic data to evaluate lsquare against countmin, the state-of-the-art sketch scheme. Our results suggest that given the same memory requirement, lsquare achieves much better reconstruction accuracy than countmin. Alternatively, given the same reconstruction accuracy, lsquare requires significantly less memory. This clearly demonstrates the effectiveness of our approach.

Lecture Notes: NP-Completeness: An Overview

Kim, Y. E. and Lee, G. M. (2003). NP-Completeness: An Overview. Lecture Notes, November 2003.

This paper presents an overview of NP-complete problems. The theory of NP-completeness is important not only in the theoretical aspect but also in reality. First, we will take a look at the formal definition and some examples of NP-complete problems. Then, we will see how to prove a problem is NP-complete and how to cope with NP-complete problems.