Kihong Park

  Associate Professor    |    Department of Computer Science    |    Purdue University

Research Collaborators

Over the years, I have had the opportunity to collaborate with colleagues in academia and industry including students, postdocs, faculty, research scientists and engineers. Following is a non-exhaustive list with a brief description of the collaborative work.

Fred Baker [1999-2002] Fred Baker (Fellow at Cisco Systems) and I collaborated to implement optimal aggregate-flow scheduling (the L2-norm based theoretical underpinning of optimal per-hop behavior in differentiated services networks) in Cisco's router operating system IOS. We started out with a non-optimal but game theoretically motivated scheduler devised with my Ph.D. student Shaogang Chen [INFOCOM '99], but quickly switched over to an L2-norm optimum scheduler advanced with my Ph.D. student Huan Ren [IWQoS '00].

Based on IOS's architecture, we provided IOS-compatible source code with compiling and run-time testing carried out by Seok Kweon in Glenn Reitsma's group at Cisco. Benchmarking and stress testing were carried out at Purdue. The final, stable version purdue-ios runs on Cisco 7206 VXR routers on Q-Bahn, a dedicated QoS testbed comprised of nine Cisco 7206 routers following the physical connectivity of Internet2/Abilene.
[Q-Bahn Hardware (jpg) | Q-Bahn Connectivity Map (gif) | Q-Bahn Overview (pdf)]

Bob Carter [1993-1995] Bob Carter, a fellow grad student at BU, and I were interested in understanding how effective genetic algorithms were when treated as a combinatorial optimization technique. The main distinguishing trait of GAs was the cross-over operator which captured the intuition (aka "building block hypothesis") that combining good genes from parents should lead to improved fitness in offsprings. Our studies showed that this is, in general, not the case.

The gist of the underlying reason is that for genetic recombination to be effective, the objective function f must obey a "superposition principle" such that combining alleles A and B is conducive to f(A+B) > max(f(A),f(B)). The function class that satisfies this property tends to be comprised of "simple" functions (e.g., linear/monotone, unimodal) that are readily amenable to other (and more efficient) optimization methods such as gradient descent and simulated annealing. Our work helped dispel some of the romanticism associated with GAs as powerful optimizers, an inaccurate perception fostered by papers benchmarking on small problem instances.

Shaogang Chen [1997-2000] Shaogang Chen, my first Ph.D. student, and I worked on network mechanisms for multi-class QoS provisioning where users are assumed to be selfish and possess diverse service requirements. Our first problem concerned a single shared resource (e.g., switch or router link) that is partitioned into multiple service classes which are mediated by a scheduler such as weighted fair queuing (WFQ). Our work showed that such noncooperative networks can self-organize into stable (but not necessarily asymptotically so) and efficient system states [ICE '98, ICNP '98, INFOCOM '99].

An important innovation was the introduction of a user-optimal scheduler — based on user preferences inscribed in a packet (or flow), the scheduler can determine a per-user optimal service class — obviating the need for a user to exercise direct control over a switch which is practically infeasible (due to overhead issues) and untenable (due to protection issues). The second problem concerned noncooperative QoS provisioning over a network of switches where service classes chosen at each hop collectively determine a flow's end-to-end QoS. We showed that the problem is NP-hard but admits to efficient approximation via Lagrangian optimization.

Mark Crovella and Gitae Kim [1995-1997] Prof. Crovella (who had joined BU as a new faculty), Gitae Kim (a fellow grad student), and I embarked on a project to understand the causes underlying self-similar Internet traffic. Mark's dissertation was in parallel computing (but quickly switched to studying the then burgeoning WWW), Gitae was working on FEC for TCP-over-ATM with his advisor Prof. Bestavros, and I was exposed to Leland et al.'s seminal paper at SIGCOMM '93.

The ICNP paper showed that traffic self-similarity is mainly caused by heavy-tailed file size distributions, a structural property of distributed systems, with the modulating influence of TCP playing a secondary role. The SPIE paper studied the practical implications of traffic self-similarity on network performance considering the resource-bounded nature of network systems, impact of transport layer protocols (TCP and UDP), and convergence issues associated with heavy-tailed distributions when carrying out performance evaluation.
[more information]

John Cruz [1997-2001] John Cruz, my second Ph.D. student, and I tackled the problem of supporting distributed applications, including parallel distributed computing, over PC clusters through legacy compatible resource management. The two key features of our approach were: legacy application and legacy OS compatibility over commodity systems, and communication-sensitive dynamic load balancing. The first feature was achieved by inserting transparent resource management functionality inside system call wrappers — the same technique used in Condor — which allows legacy applications to be run without recompiling (just relinking).

The key innovation beyond Condor were two-fold: transparent dependency support including local file I/O, IPC, and socket communication that allowed process migration of non-isolated processes (Condor only provides NFS file I/O support), and push-pull cashing that mitigated the cost of remote dependence maintenance. The second feature, communication-sensitive load balancing, enabled migration and co-location of strongly coupled processes, thereby not only balancing CPU load but also communication costs resulting from separated processes. John did not complete his Ph.D. Thesis, a casualty of the bubble period.

Karel Culik II [1988-1990] Prof. Culik was my M.S. Thesis advisor at the Univ. of South Carolina (I joined the CS Dept. after spending a semester as a grad student at SNU in 1988). My M.S. thesis

  • K. Park. Analysis of one-way infinite sequences: an algorithmic information theoretic approach. M.S. Thesis, Univ. of South Carolina, 1990

concerned the Kolmogorov complexity of one-way infinite sequences from the viewpoint of capturing Wolfram's notion of "computational irreducibility." During my Ph.D. studies at BU, I realized that Bennett's "logical depth" provided a framework for linking descriptive complexity with computational complexity, not unrelated to computational irreducibility. I also worked with Prof. Culik as an RA on an NSF grant that looked at fractal image compression using weighted finite automata whose limit sets can be interpreted as grey scale images. My specific problem concerned Barnsley's Collage Theorem when transferred to the context of inferring weighted finite automata (i.e., image compression) from grey scale images. I implemented a prototype system on an Apollo graphics workstation.

Peter Gacs [1991-1996] After doing my military service in the Korean Army in 1990, I joined BU's Ph.D. program in the CS Dept. in 1991. Prof. Gacs was my Ph.D. Thesis advisor. I worked with him as an RA on a NSF grant studying fault-tolerance properties of probabilistic cellular automata. My passion for CAs was kindled during my M.S. study with Prof. Culik (an expert on language theoretic aspects of CA dynamics), which was also a continuation of my earlier interest in neural networks and AI. My Ph.D. thesis

showed that certain simple 1-D cellular automata proposed as potential candidates of fault-tolerant (i.e., non-ergodic) systems are forgetful when subject to biased noise. The main technical innovation was to show that certain renormalization techniques pioneered by Prof. Gacs in the opposite context of showing non-ergodicity of very complex 1-D CAs (which disproved the positive rates conjecture) could be used to prove ergodicity of simple CAs. An interesting problem remains of removing the bias condition.
[more information]

Abdelsalam Heddaya [1992-1995] Prof. Heddaya was my de facto "systems research advisor" at BU with whom I looked at communication control issues in distributed systems, including congestion control and communication management for parallel/distributed applications in cluster environments. Publications from this effort include

The SIGCOMM paper looks at the congestion control problem from the perspectives of information-limited control, impact of feedback delay, and local stability under noise. The HPDC paper applies congestion control for regulating network access by asynchronous parallel applications running over workstation clusters which can significantly improve parallel speed-up.

Jennifer Hou [2000-2004] Prof. Jennifer Hou (UIUC) and I collaborated on a joint NSF grant, "ITR: Multiple Time Scale Traffic Control for Next Generation Internets," whose aim was to study traffic control issues across multiple time scales induced by workload sensitivity and protocol stack interdependence (such as those stemming from coupling of multiple feedback loops).

One of Jennifer's students, Guanghui He, did his Ph.D. thesis on this topic with controls spanning AQM, TCP, and optimal prediction. I served as an external thesis committee member. Guanghui's thesis complements Sven Ostring's Ph.D. thesis, "Reactive traffic control mechanisms for communication networks with self-similar bandwidth demands" (Univ. of Canterbury, 2001) on which I served as an external reader.

Terrence Huntsberger [1989-1990] I worked as an RA for Prof. Huntsberger on a NIH grant at the Univ. of South Carolina studying the structure of DNA sequences which were starting to become popular with the advent of genome banks and other national/multi-disciplinary efforts. Given my interest in Kolmogorov complexity, I investigated the feasibility of using context-free grammars to capture the 1-D structure of DNA sequences. We wrote a paper

  • K. Park and T. Huntsberger. Inference of context free grammars for syntactic analysis of DNA sequences. 1990 AAAI Spring Symposium, Artificial Intelligence and Molecular Biology, pp. 110-114, 1990

which showed some potential for using restrictive grammars to represent DNA sequences. I abandoned further effort (i.e., put it on the long-term backburner) as it was clear from talking to biologists that they needed to gather more data before productive science could be undertaken (above and beyond advancing tools for fast subsequence matching and such, which, although relevant, was a "service science," not science proper).

Ikkyun Kim [2004-2006] Ikkyun Kim (ETRI) joined Purdue as a visiting researcher on a collaborative grant from ETRI studying network solutions to DDoS and worm attacks. Ikkyun was instrumental in advancing a scalable worm filter architecture that achieves gigabit wire speed worm filtering. Ikkyun implemented the worm filter architecture on Intel IXP1200 and IXP2800 network processors, benchmarking the systems under controlled workloads containing both artificial and trace-based worm traffic.

The IXP1200 worm filter delivers 1 Gbps wire speed performance whereas the IXP2800 version achieves 4 Gbps filtering performance. The key features of the worm filter architecture are speed, programmability, and targeted polymorphism support. The transit worm filter may be used as a stand-alone system deployed at an enterprise network's Internet gateway. It can also be used as a building block of a cooperative filter network for protecting the global Internet. Our research shows that 2-3% deployment suffices to attain proactive protection through local containment.

Heejo Lee [2000-2001] Gene Spafford and I had collaborated on a Sprint grant in 1997-1999 to study ATM security. I was concerned about the limited utility of cryptographic and infosec approaches to addressing network security problems where performance is key. In 2000, my postdoc Dr. Lee and I looked for fresh solutions based on network-centric methods which led us to probabilistic packet marking (PPM) and route-based packet filtering. Over dinner, one spring evening in 2000, I learned from Somesh Jha that Univ. of Washington researchers had written a technical report about similar ideas. Subsequently we focused on analyzing the problem of marking field spoofing in PPM which led to our INFOCOM '01 paper.

Given the limitations of PPM, our main work concentrated on advancing proactive solutions for spoofed DDoS attack prevention which resulted in route-based packet filtering (may be viewed as a generalization of ingress filtering). The main technical innovation of our SIGCOMM '01 paper was the introduction of power-law (inter-domain) network connectivity in performance evaluation, essential to demonstrating strong protective performance under small partial deployment. We were also one of the first to study optimization aspects of power-law graphs, showing the large gap in vertex cover sizes produced by several topology generators from those of Internet measurement graphs (incorporated in Inet3.0).

Huan Ren [1998-2002] Huan Ren, my fourth Ph.D. student, and I built on the work carried out with Shaogang Chen and Meera Sitharam. The first fundamental innovation was to link noncooperative resource provisioning with optimal scheduling. We knew from earlier results [ICE '98, INFOCOM '99] that noncooperative multi-class QoS provisioning games need not have Nash equilibria, with or without pricing (in fact, we showed a counter-intuitive situation where pricing destroys stability). We established three general conditions, called (A1), (A2), and (B), under which noncooperative multi-class QoS provisioning is asymptotically stable (and as a consequence a Nash equilibrium). We then developed a MMSE (i.e., L2-norm) theory of optimal aggregate-flow scheduling, deriving an optimum scheduler that may be viewed as an adaptive form of WFQ. We showed that the optimum MMSE scheduler satisfies properties (A1), (A2), and (B).

The second innocation was a generalization of the optimum aggregate-flow scheduling framework to general stochastic input which entailed connecting queuing theory with combinatorial optimization. The mathematical framework shares similarities with polymatroid optimization under general conservation laws, a topic studied by Mitrani, Yao, and others. The third innovation was to implement the optimum MMSE aggregate-flow scheduler in Cisco's router operating system IOS (joint collaboration with Fred Baker of Cisco Systems). The small time complexity of the optimum aggregate-flow scheduler (linear in the input) lends itself to low overhead wire speed implementation. The custom version of IOS, purdue-ios, runs on Q-Bahn, a 9 Cisco 7206 VXR router testbed following Internet2/Abilene's physical connectivity.
[Q-Bahn Hardware (jpg) | Q-Bahn Connectivity Map (gif) | Q-Bahn Overview (pdf)]

Ali Selcuk [2001-2002] Prof. Selcuk (Bilkent Univ.), then a postdoc in my lab, and I worked on the DARPA FTN project "Toward scalable solutions for distributed denial of service attack prevention" which studied proactive and reactive protection against spoofed DDoS attacks on the Internet using route-based packet filtering. The research builds on earlier work with Dr. Heejo Lee but goes further by advancing protocol optimizations, evaluating deployment issues, and incorporating structural constraints of the inter-domain Internet.

As part of the DARPA project, we devised a static DPF (distributed packet filtering) simulator that works with large-scale Internet measurement graphs. The software suite (DPFv2) was released to the DARPA community and has been used by other research groups (e.g., Duan et al., INFOCOM '05) in follow-up works. Our tools have undergone Red Team testing by SRI.
[more information]

Meera Sitharam [1998-2004] Prof. Sitharam (Univ. of Florida), a complexity theorist, visited Purdue in 1997-1998 during which we commenced our collaboration in understanding the structural properties of noncooperative multi-class network resource allocation games. Our ICE '98 paper gave a comprehensive characterization of noncooperative multiservice games with respect to stability and efficiency, showing nontrivial separation between Nash, Pareto and system equilibria.

Whereas previous works focused on showing niceties under restrictive (and unrealistic) assumptions on user utilities and network performance, our results gave a comprehensive characterization of noncooperative multiservice games including structural instability (nonexistence of Nash equilibria), conditions under which Nash equilibria are Pareto or system optimal (e.g., resource-plentiful games), the influence of pricing (which includes a "dark side"), and computational complexity considerations. Andrew Lomonosov, Meera's Ph.D. student, joined our effort.

Cole Smith [2002-2005] Prof. Smith (Univ. of Arizona), an expert in integer programming, and I collaborated on an optimization problem arising in route-based packet filter placement in network graphs. We show that optimal filter placement in general graphs is NP-hard — reduction from vertex cover — establishing the importance of vertex cover for route-based filter placement. We also discuss network topologies for which optimal filter placement has a poly-time solution, and identify when greedy filter placement finds an optimum solution. Benjamin Armbruster, Cole's student, joined our effort.

Tsunyi Tuan [1997-1999] Tsunyi Tuan, my third Ph.D. student, and I advanced predictive traffic control under self-similar traffic conditions. The bad news with long-range dependence in self-similar Internet traffic is that exponentially rare crowding events under short-range dependent input become only polynomially rare. The good news within the bad news is that long-range dependence admits long-term predictability which may be harnessed to improve traffic control.

Our first focus was on multiple time scale congestion control where the main idea was to selectively modulate the aggressiveness level of bandwidth consumption during linear increase (i.e., its slope) commensurate with predicted long-term traffic. Long-term predictability bridges the information gap of feedback congestion control in large delay-bandwidth product networks which incur a high reactive performance penalty. Our TOMACS paper extends the methodology to TCP congestion control. The second focus was on multiple time scale adaptive FEC which imparts AFEC with long-term predictability that helps calibrate the redundancy level applied over larger time scales. Tsunyi was the first casualty of the bubble period.

Walter Willinger [1998-2005] Walter Willinger (AT&T Labs-Research) and I collaborated on a couple of book projects, the first on self-similar network traffic that brought together chapter contributions providing a snapshot of the state-of-the-art circa 1999, and the second on complex systems aspects of the Internet which emanated from a workshop titled "The Internet as a Large-Scale Complex System" that we organized at the Santa Fe Institute in March, 2001, with support from NSF and SFI.

  • K. Park and W. Willinger (eds.). Self-Similar Network Traffic and Performance Evaluation, Wiley-Interscience, 2000
  • K. Park and W. Willinger (eds.). The Internet as a Large-Scale Complex System. SFI Studies in the Sciences of Complexity, Oxford University Press, 2005

The latter was a first step toward commencing a discussion that related the diverse scientific foundations underlying the Internet, first, from a phenomenological perspective as a multifaceted complex system, and second, as a large-scale man-made system with engineering implications for the future. The chapter "The Internet as a complex system" touches upon complex systems features of the Internet including self-similar traffic, power-law network topology, and noncooperative network games. An introduction to self-similar traffic is provided in the chapter "Self-similar network traffic: an overview."

Other research collaborators [joint research descriptions will follow] Prof. Saewoong Bahk (Seoul National Univ., Professor), Bhagya Bethala (Purdue Univ., Ph.D. student), Dr. Sunwoong Choi (Samsung/Seoul National Univ., Researcher), Jaehyuk Choi (Seoul National Univ., Ph.D. student), Hwanjo Heo (Purdue Univ., Ph.D. student), Prof. James W. Hong (POSTECH, Professor), Humayun Khan (Purdue Univ./Microsoft, Ph.D. student), Prof. Chong-kwon Kim (Seoul National Univ., Professor), Hyojeong Kim (Purdue Univ., Ph.D. student), Dr. Jaeyoung Kim (Samsung/POSTECH, Postdoc), Dr. Jisoo Kim (Samsung/POSTECH, Postdoc), Dr. Jason Li (IAI, Researcher), Dr. Daniel Manchala (Xerox, Researcher), Prof. Gopal Pandurangan (Purdue Univ., Professor), Wei Wang (Oracle, Researcher)

This page is under construction.