When: Tuesday, May 06, 12:00 p.m.

Where: Distributed Education Center
Lobby LevelCollaborative Innovation Center

Eng Keong Lua, Special Researcher
Nippon Telegraph and Telephone Corporation
NTT Service Integration Laboratories, Tokyo

CyLab Seminar

Abstract:
Internet coordinate systems embed network metrics such as latencies between Internet nodes into some geometric space so that unmeasured latencies can be estimated using distance computation in that space. The goals of constructing such an embedding into node coordinates are twofold. Firstly, the embedding should be scalable in the sense that it must be done with many fewer measurements than the N² required on a full mesh of N nodes. That is, if an Internet coordinate system required O(N²) measurements, then we might as well not use it to estimate the Internet latencies between nodes. Secondly, this must be done so that the resulting system is accurate for all pairs of nodes in such a way that the embedded geometric distances between nodes should, in some sense, closely approximate their network distances. The methods should remain accurate even when the input is a small subset of all possible network distance measurements. The published techniques appear to work very well when accuracy is tested using accuracy metrics such as absolute relative error. Our main observation is that absolute relative error tells us very little about the quality of an embedding as experienced by a user. We define several new accuracy metrics that attempt to quantify various aspects of user-oriented quality. Evaluation of current Internet coordinate systems using our new accuracy metrics indicates that their quality is not as high as that suggested by the use of absolute relative error.

The Triangle Inequality Violations (TIVs) in the Internet latency routes caused by the Internet's routing structure will necessarily degrade the accuracy of any embedding technique. This is because the mathematical underpinnings the network embedding methods assume that the initial Internet latency measurements form a metric space and triangle inequality satisfies. The effect of such violations on the embeddings can be rather counter-intuitive – even when a private peering shortcut is the shortest path between nodes on either side of it, the embedding tends to stretch the shortcut considerably, making many close nodes appear to be very distant from each other. We further study and show that the violations of triangle inequality of latencies produced by the underlying Internet routes are persistent, widespread and a direct consequence of Internet routing policies. In particular, we investigate by illustrating with real examples from the current Internet, how routing policies for both intra- and inter-domain routing can naturally give rise to violations of the triangle inequality with respect to measured latencies. We argue that TIVs should not be treated as measurement artifacts, but rather as natural features of the Internet's routing structure. It is also interesting to note that two popular research areas are in conflict here – violations of triangle inequality in the Internet latency structure may cause problems for Internet coordinate systems, but they are the "raison d'etre" of overlay routing techniques such as Resilient Overlay Networks (RON) (going from node A to node B, it may be better to go through node C, which this may not be allowed under current routing policies at layer 3).

Eng Keong Lua is currently the Special Researcher in the Nippon Telegraph and Telephone Corporation (NTT), NTT Service Integration Laboratories, at Tokyo, Japan. In 2006, he obtained his Ph.D. degree in Computer Science from the University of Cambridge, United Kingdom (UK). He was supported by Microsoft Research Fellowship, Cambridge-MIT Institute, and UK EPSRC e-Science FutureGrid program. In 2004, he had completed a 6-month research internship at the Intel Research, Cambridge, UK. He was the inaugural recipient of the prestigious Australia-Asia Award in 2003, presented by the Australian Government to promising scholars in Asia for sponsorship of research activities in Australia. He received his M.Sc. degree in Telecommunications with Distinction from the Department of Electronic and Electrical Engineering, University College London (UCL), UK, in 1997, and both Postgraduate Diploma of Teaching in Higher Education and B.A.Sc degree in Computer Engineering with Merit from the Nanyang Technological University, Singapore, in 1995 and 1993 respectively. Prior to his Ph.D. research studies, he was the Assistant Director in the Information Infrastructure Development Division, of the Infocomm Development Authority of Singapore, where he was involved in the governmental policy and regulatory aspects of cutting edge technologies for national information infrastructure development. He was formerly the key Solution Architect and Consulting Project Manager in the Hewlett-Packard Consulting and R&D. In his consulting engagements, he served as industry advisor and delivered large turn-key projects to major telecommunication service providers at worldwide level. He had also spent several years as a faculty member in academia, and had served in various strategic and technical advisory committees.

His research areas are networking and distributed systems. His main research interests include clean-slate design of security, protocol and service management for future ubiquitous communication network architecture and distributed systems through the principles of self-organization, self-defense, data-centric networking, meta-routing and network virtualization, with emphasis on service overlay networks, wireless (mobile) networks, and the Internet. He is co-writing a book on Peer-to-Peer Networking and Applications, to be published by Morgan Kaufmann, Elsevier Inc. on June 2008. He has 28 refereed research publications and a total of 10 filed patents with 5 patents granted by the Japan Patent Office. He is a member of the IEEE Computer and Communications Societies (USA), ACM (USA), IET (UK) and IES (Singapore). He holds professional certifications from Cisco Systems in Network Professional (CCNP), Network Associate (CCNA) and Academic Instructor (CCAI).

Lunch provided

<< Back