Chen-Nee Chuah, Ph.D. - US grants

The long-term career goal of the PI is to help transform the Internet into a robust, stable, and secure routing infrastructure that delivers highly reliable and predictable performance. Considering the critical role that the Internet plays in our day-to-day lives, the current routing architecture is surprisingly fragile. Fiber cuts, faulty or mis-configured equipment, and malicious attacks (e.g., the Nimda worm) have led to a widespread loss of global connectivity. To achieve our vision, we have developed the following four research agendas:

1. PI argue that an essential starting point is a thorough characterization of wide-area failure scenarios and how much they impact the traffic-forwarding plane. Through the PI's collaboration with Sprint, will monitor an operational Tier-1 Internet Service Provider's backbone to collect routing and traffic data. Based on successive conditioning of the data, will derive a wide-area failure (WARF) model that can be used by the research community to generate realistic failures in simulation or testbed environments.

2. PI will undertake a complementary effort to design a statistical BGP anomaly detector that automates the process of differentiating abnormal and expected routing behavior. The design follows basic intrusion detection principles in creating a historical profile and performing short-term testing.

3. PI will investigate an alternative approach to policy routing by designing and developing an Overlay Policy Control Architecture (OPCA) that facilitates fast route convergence and traffic engineering. OPCA will allow the concurrent use of multiple types of metrics in intra- and inter-domain routing, and illustrate that such functionality is warranted in the IP core.

4. PI will design a Routing Introspection and Feedback System (RIFS) that provides timely feedback to higher-layer entities such as overlay networks and transport or application layer proxies. will extend our study to explore a hybrid channel coding and retransmission scheme to optimize video streaming based on detection of failures and routing loops.

The outcome of this work strives to enable Internet-based distributed computing by making the core Internet more reliable and stable. Effective routing across heterogeneous networks (including wireless and satellite) is the key to truly ubiquitous connectivity, which will have a broad impact on societal applications. The hypothesis and methodologies tested in this project will help advance the knowledge in the field of wide-area routing and form a foundation for analyzing the reliability issues of other large-scale distributed systems. Will make the failure models, tools, and prototypes developed in this project available to other researchers online and via publications and training workshops.

The PI's educational mission is to train undergraduate and graduate students to become capable network engineers by incorporating real-life operational experience and anecdotes of wide-area Internet behavior into classroom teaching. This includes developing a capstone design course that gives students hands-on experience in network management and routing modules. The PI will actively recruit underrepresented women and minority students into the engineering curriculum and her research projects by collaborating with the Women in Engineering (WIE) and the Mathematics, Engineering, and Science Achievement (MESA) programs at U. C. Davis.

The proposed project explores a two-tier signaling approach with optical label switching (OLS) technique that offers the following desired properties: (a) accommodates signals of any protocol/format, (b) achieves ultra-low latency for transporting high burst-rate packets, (c) requires no network or packet synchronization, (d) interoperates with both circuit-switched and packet-switched traffic, and (e) automatically detects and restores network failures.

The project focuses not on prototyping and testbed creation but on the design, simulations, analysis of new optical networking technologies. In particular, the project investigates novel ways to incorporate intelligence in the optical nodes and in the management system to make the network more resilient, robust, and efficient. The tasks and sub-tasks of the project are listed below:

Task 1. Next Generation Networks (NGN) architecture and protocol studies
Simulate and design MPLS restoration and optical protection algorithms
Emulate New Unified Optical Networking with optical packet, burst, frame, cell switching
Design protocols for providing differentiated Class of Service and on-demand QoS.

Task 2. NGN network control, management, and signaling
Design a signaling architecture which allows rapid but optimized routing of packets
Implement NC&M which makes intelligent judgements based on the network condition.
Investigate a method for auto-detection and auto-recovery of a fault in the network

Task 3. NGN network element design and optical technologies
Design a scalable switch architecture for the IP/WDM network elements.
Implement the most effective contention resolution and congestion control method.

This project investigates the Next Generation Network Technology and Systems capable of understanding and learning the high-level perspective of the network. The proposed approach pursues a new cognitive intelligent networking paradigm that maintains the success of today's Internet but which also incorporates cognitive intelligence in the network--a new networking technique that provides the ability for the network to know what it is being asked to do, so that it can step-by-step take care of itself as it learns more. In particular, we explore new networking architecture and network elements that will lead to a future network with (a) improved robustness and adaptability, (b) improved usability and comprehensibility, (c) improved security and stability, and (d) reduced human intervention for operation and configuration. This project pursues a set of comprehensive studies that seek innovations through the design and modeling of a new brain-reflex cognitive intelligence architecture, an intelligent programmable network elements architecture, and an intelligent network control and management design.

Broader Impact: The team approach covering neuroscience, datamining, computer science, systems engineering, artificial intelligence, and networking will provide rich opportunities for students to learn beyond their primary fields of study. New courses developed by the faculty members will disseminate the new material covering neuroscience and information technology.

As the Internet becomes an essential part of our everyday computing and communication infrastructure, it has also grown to be a complex distributed system that is hard to characterize. There have been numerous studies on network topology, IP-reachability, and routing dynamics to analyze end-to-end packet forwarding performance. However, there is very little systematic investigation into the influence of other packet transformations that happen along the path, e.g., firewalls, packet filtering, and quality-of-service mapping. Among these, firewalls are ubiquitous as they become indispensable security defense mechanisms used in business and enterprise networks. Just as router mis-configurations can lead to unpredictable routing problems, misconfigured firewalls may fail to enforce the intended security policies, or may incur high packet processing delay. Unfortunately, firewall configuration for a large, complex enterprise network is a demanding and error-prone task, even for experienced administrators. Firewalls can be distributed in many parts of the network or across layers (IP-layer filtering versus application-layer solutions) to cooperatively achieve a global, network-wide policy. As distributed firewall rules are concatenated, it becomes extremely difficult to predict the resulting end-to-end behavior and whether it meets the higher-level security policy.

Intellectual merit: In this project, the principal investigators (PIs) propose to develop a unified framework for policy-checking, optimization, and auto-reconfiguration of distributed firewalls. This research will provide novel analysis, design techniques, and tools to better protect our critical information infrastructures from attacks. The PIs will explore providing consistent and efficient security protection for an enterprise that may have geographically distributed business networks served by different local Internet Service Providers. They adopt an inter-disciplinary technical approach that leverages multi-way communications among the three PIs with expertise in networking, security, and programming languages and compilers areas to design an integrated solution. In particular, the PIs propose a systematic treatment of the problem by casting it as a static program analysis question, exploiting well-established and rigorous techniques from the area of programming languages and compilers. The PIs will pursue the following closely related tasks:

Policy Validation for Security: The PIs first classify all possible policy anomalies (including both inconsistency and inefficiency) in firewall configurations. They will model firewalls as finite-state transition systems and apply symbolic model checking techniques on these finite-state representations to detect both intra-firewall and inter-firewall policy anomalies. The policy validation method consists of two phases. First, they perform control-flow analysis and identify all possible flow paths. Second, they perform data-flow analysis and check for anomalies on every path. Identifying most intra-firewall and inter-firewall anomalies can be accomplished in one traversal. The processing results of each path are further used to identify inter-path misconfigurations.

Policy Optimization for Performance: In a typical firewall setting, a packet is compared against a list of rules sequentially until the packet matches a rule. Firewalls with complex rule sets can cause significant delays on network traffic and therefore becomes a bottleneck (especially in high-speed networks) and an attractive target for DoS attacks. Therefore, it is important to optimize packet filtering to provide network Quality of Service (QoS) requirement. In addition, the total number of rules configured and the order of rules also play major roles in the load and efficiency of a firewall. The PIs approach this problem by representing filtering rules as binary decision diagrams (BDDs) and generating "optimal filter rule sets" from the internal BDD representation. They also apply dataflow analysis to hoist same or similar rules from different paths to a common location to reduce traffic. They will leverage the underlying network topology, routing, and traffic distribution information in the optimization step to improve the efficiency of firewall checking, which enhances packet-forwarding performance. The key advantage of this approach is the ability to pro-actively prevent vulnerabilities in firewalls since static analysis can be applied before the actual deployment of firewalls.

Broader Impacts: The proposed research efforts will help system and network administrators to configure networked systems more securely and efficiently. The educational component, which is directed at both undergraduate and graduate students, complements the research activities. Research results will be incorporated into new and existing courses. The PIs will actively participate in UC Davis' minority outreach programs to recruit students from underrepresented groups into science and engineering. In addition, firewall configuration tools developed in the project will be distributed for teaching

Title: Collaborative Research: CT-ISG: Accurate Sampling of the Internet

for Effective Anomaly Detection



Abstract:



Sampled traffic data has been increasingly used as input for anomaly

detection systems, as the high link speeds make it impossible to

examine each and every packet. This raises an important question of

whether sampling has a (negative) impact on the accuracy/effectiveness

of anomaly detection, and if so how to mitigate this effect.



Intellectual Merit: This project systematically studies the question

mentioned above from the following three angles. First, we will

identify traffic features that are critical for a wide range of

anomaly detection schemes and quantify how much they are distorted by

various sampling schemes. Second, we will design new sampling or

measurement techniques that preserve enough accuracy to support

effective anomaly detection, while being cost-effective and

light-weight. Third, we will study how to correlate the NetFlow

samples obtained at the edge routers with the information-rich data

generated using existing data streaming algorithms, for much better

anomaly detection than pure sampling. The new scientific knowledge

learned through this research will provide us with much better

technologies to monitor large high-speed networks for anomalous

behaviors.



Broader impact: The results will be broadly disseminated through

publications, invited talks and tutorials, and open-sourcing of

software developed for this project. The PIs' collaboration with

tier-1 ISP's will facilitate the transfer of technology from research

environment to actual managing of production networks. Research

results will be incorporated into information security curriculum.

Both PIs have been actively engaging under-represented groups in

research and higher education and will continue and expand these

efforts.

In this research, we exploit the ad hoc networks formed by vehicles equipped with robust wireless communication devices, storage, processing, and sensing capability to perform robust traffic state estimation and distributed traffic management. First, we will utilize the sensing and computation capabilities of vehicles and the self-organized grid computing engine to develop robust estimation and control algorithms to smooth vehicular traffic flow on freeways. Through simulation and analysis we will investigate the effectiveness of these schemes with the goal to reduce accidents, minimize congestion delays and maximize throughput. We will also investigate the required degree of penetration to make such a system effective. Second, as part of this research, we will develop the software architecture, the networking protocols, and the resource management algorithms to create the grid computing engine, VGrid, and integrate it with the roadside sensor infrastructure. New challenges arise due to the dynamic nature of the ad hoc grid computer as both the topology and the node membership change with time. Third, we will develop an integrated simulation tool that has both a realistic vehicular mobility model and communication/networking layers that capture the dynamics of wireless channels. Using this simulation tool, we will investigate the performance characteristics of a hybrid sensing-computing-control system, and identify design and modeling issues to improve the performance of such a system.

Our proposed research provides both an alternative infrastructure and new ways to manage traffic flow and enhance traffic safety. The distributed dynamic sensing and control architecture developed here would make ubiquitous deployment of traffic safety, security and management measures a reality wherever there are VGrid types of vehicles, which alleviates the reliance on expensive fixed infrastructure and has the potential to speed up the response time compared to traditional centralized intelligent transportation systems. Moreover, understanding the characteristics of vehicular ad hoc networks and the overlay grid computing platform will aid the development of a general framework for other applications such as vehicular collision avoidance, emergency evacuation, and disaster recovery. There are significant broader impacts of this proposed research. First, by providing both an alternative infrastructure and new ways to manage traffic flow and enhance traffic safety, significant societal benefits can be expected in the form of increased mobility and saved human lives. Second, since this project examines problems at the intersection of vehicular and information traffic, it provides interdisciplinary training to the students involved. Lastly, it enhances the educational experience of local high school students through a science project studying vehicular ad hoc networks.

This award is funded under the American Recovery and Reinvestment Act of 2009 (Public Law 111-5).

Traffic measurement is central to network operation, management, and security. Yet, support for measurement was not an integral part of the original Internet architecture. This project aims to develop a programmable measurement architecture that is versatile enough to support current and future measurement needs, adaptable to dynamic network conditions, modular/lightweight, and scalable to high link speeds.

This project proposes a new flow abstraction module and query language that can specify arbitrary traffic sub-populations for statistics collection. Efficient data structures to encode these queries will be developed. The team also strives to identify a core set of data streaming and sampling primitives that can be composed together to satisfy most of the queries. Efficient hardware implementation for these core set of primitives will constitute the basic measurement modules that can be easily reconfigured to measure traffic at different desired granularity. Measurement application case studies will be carried out to evaluate and showcase the capabilities of the proposed approach.

This project has great potential in guiding the design of a clean-slate measurement instrumentation for future Internet. It will provide both graduate and undergraduate students with training that span multiple disciplines, from fundamental statistical theory, algorithm design, to hardware implementation. The results (including the query language and underlying data structures, sampling/streaming algorithms, and hardware building blocks) will be broadly disseminated through publications, invited talks/tutorials, and open-sourcing software distribution.

This travel award supports participation in the Ninth ACM SIGCOMM Internet Measurement Conference (IMC), sponsored by ACM SIGCOMM and co-sponsored by USENIX, to be held in Chicago, IL, USA, November 4-6, 2009.

This technical conference is the primary venue for presenting new research results in an important area in networking, namely that of network measurements. The conference focuses on many research issues associated with observing the Internet, including: traffic analysis, structure and topology characteristics, performance measurements, measurement-based network management, characteristics of network applications, design of monitoring systems, anomaly detection, measurement of security threats, tools and environments in support of measurement, measurement-based assessment of simulation/testbeds, workload generation and modeling. Thus attendance at IMC provides a valuable research and career development experience for graduate students from United States academic institutions. Participants have the opportunity to present their work, attend panel and keynote speeches and technical sessions, as well as interact with peers engaged in state-of-the-art research in the field.

Approximately 10 US-based graduate students are provided the opportunity to attend IMC. The travel awards will target graduate students, in particular female and under-represented minority students, since they often have limited travel funds to attend workshops; attendance at such events is an important part of their educational experience.

This travel award supports student participation in the Tenth ACM SIGCOMM Internet Measurement Conference (IMC), sponsored by ACM SIGCOMM and ACM SIGMETRICS, in cooperation with USENIX, held in Melbourne, Australia, November 1-3, 2010.

IMC 2010 will expose students to new ideas, and allow them to interact with other researchers in the field of network measurements; specific topics include, internet traffic analysis, internet structure and topology characteristics, internet performance measurements, measurement-based network management such as traffic engineering, inter-domain and intra-domain routing, network applications such as multimedia streaming, gaming and on-line social networks, measurements of content distribution, peer-to-peer, overlay, and social networks, data-centric issues, including anonymization, querying, and storage, measurement-based inference of network properties, design of monitoring systems, sampling methods, signal processing methods, network anomaly detection and troubleshooting, network security threats and countermeasures, software tools and environments in support of measurement, measurement-based assessment of simulation/testbeds, measurement-based workload generation, measurement-based modeling, and reappraisal of previous measurement findings.

Approximately 10 US-based graduate students are provided the opportunity to attend IMC 2010. The travel awards will target graduate students, in particular female and under-represented minority students, since they often have limited travel funds to attend workshops; attendance at such events is an important part of their educational experience.

The capability to preserve, model, and predict information cascades over online social networks has many theoretical and practical implications, e.g., for marketing, recommendation filtering, and studying of societal behavior. Massive empirical data sets on users' online social activities are being collected, but they are often too big to analyze. The goal of this project is to design graph generative models and summarization techniques that can preserve pertinent information about online social interactions that lead to interesting events, e.g., viral diffusion of information or drastic change of user behavior. Towards this end, the project will develop generative models that can capture the dynamic evolution of user activity graphs (UAGs), which represent a sequence of inter-user communications/actions. At the microscopic level, the project will investigate user influence in the recruitment process. In addition, the project will design graph summarization techniques that can achieve good tradeoffs between data compression ratio, computational complexities, and accuracy in answering fundamental queries, such as identifying 'influential' sources of information cascades.

Broader Impact: If successful, this project will provide efficient methods for storing/archiving massive graph data to support longitudinal study on the dynamics of online social interactions, which has potential impact on multiple disciplines (e.g., economics, history, political sciences, and social science). This project will help train future researchers and practitioners in online social networking and network science through classroom curriculum development and online teaching. The PIs will continue ongoing diversity recruitment and outreach to K-12 students. Transfer of technology into commercial practice is made feasible through partnership with industry.

A key tool for understanding and engineering Internet backbone is the analysis of packet traces. However, given the increasing backbone speed towards 100Gbps, it is prohibitive to monitor individual flows at all times. This project develops optimal online learning and adaptation strategies for accurate traffic sampling, inference, and detection under hard resource constraints (e.g., limited CPU or memory at routers) and dynamic network/traffic conditions. Based on theories and techniques in multi-arm bandits, group testing, and compressed sensing, optimal or near-optimal solutions will be developed by exploiting the unique structures of the specific measurement application under study. Challenges addressed include learning from observations with heavy-tailed distributions and long-range dependencies, coping with sparse and/or imperfect observations, and distributed learning strategies that involve multiple monitors and decision points.

If successful, this research will provide fundamental design principles for a flexible traffic measurement infrastructure under the software-defined networking (SDN) paradigm. Reconfigurable measurements based on a learning process can be realized in commodity router/switches using SDN APIs such as OpenFlow, leading to potential development of new services. As this project examines problems at the intersection of networking and stochastic learning/optimization, it provides interdisciplinary training to graduate and undergraduate students in a team environment.

This research studies the behavior and performance of a transportation corridor made of a freeway and arterial streets under a Connected Vehicles (CV) environment, where vehicles equipped with wireless communication and sensing devices collect, process, and share traffic information among themselves along with roadside sensors. First, methods of fusing/combining real-time traffic data from both vehicles and roadside sensors will be explored to automate the detection of incidents (e.g., accidents), to estimate the number of cars waiting in line and to populate the tables that contain the number of trips from origins to destinations. Second, the research studies how congestion, particularly traffic jams, emerge and spread, and how this information can help drivers cope with congestion. Finally, the research makes use of the results obtained from the first two tasks to explore algorithms that will enable the adaptive, coordinated control of freeway ramp meters and nearby arterial traffic lights, and the re-routing of traffic in response to traffic incidents.

If successful, the results of this research will lead to a better understanding of traffic congestion in corridor networks and new ways to monitor and control vehicular traffic. These can enable applications with significant societal benefits such as reduced traffic congestion and fuel consumption. The results of this research will also be disseminated to public agencies (such as Departments of Transportation (DOTs)) and the general public through presentations and brochures, and other means. This research is at the intersection of vehicular traffic flow and computer networks, it is expected to contribute to the understanding of how corridor based transportation networks work, and provides interdisciplinary training to the students involved. Minority graduate and undergraduate students will be recruited to participate in this project through college-level minority programs such as CAMP (California Alliance for Minority Participation) at the University of California Davis.

The project at UC Davis will establish the UC Davis TETRAPODS Institute of Data Science (UCD4IDS), which will be composed of thirty-five researchers (four PIs and thirty-one senior personnel) coming from four departments (Computer Science, Electrical & Computer Engineering, Mathematics, and Statistics) and will break interdepartmental barriers and promote interdisciplinary research collaborations among faculty members, postdocs, and graduate students. The project will encourage innovative and robust research, and provide education and mentoring of graduate students and postdocs in data science. Students and postdocs engaged in this project will be trained to be the next generation of interdisciplinary data scientists: they will gain deep knowledge of some focused areas, and at the same time, broaden their perspectives in other diverse fields. The UCD4IDS will bring in the insights gained by the experience of the faculty members in the four primary departments as well as application fields such as neuroscience, medical and health sciences, and veterinary medicine. The UCD4IDS will organize: a) round-table discussions and breakout sessions after weekly seminars related to data science; b) quarterly colloquia on data science; and c) annual three-day workshops. The project will also coordinate and develop diverse courses at UC Davis, with graduate students involved in the project taking at least one course in each of the four departments. The PI team will also leverage local programs to recruit, support, and retain graduate students, postdocs, and new faculty members from underrepresented groups by matching them to appropriate mentors. For the dissemination of the research and educational results, the PI team plans to: 1) make colloquia and workshop talk slides, lecture notes, and codes available online, which will reach out to our current and future collaborators and the general public; and 2) organize mini-symposia and workshops on foundations of data science at targeted conferences.

Research at the UCD4IDS will focus on three broad themes: 1) Fundamentals of machine learning directed toward biological and medical applications; 2) Optimization theory and algorithms for machine learning including numerical solvers for large-scale nontrivial learning problems; and 3) High-dimensional data analysis on graphs and networks. The algorithms and software tools to be developed will make a positive impact in solving practical data-analysis and machine-learning problems in diverse fields, e.g., computer science (analyzing friendship relations in social networks); electrical engineering (monitoring and controlling sensor networks); civil engineering (monitoring traffic flow on a road network); and in particular, biology and medicine (analyzing data measured on real neural networks, detecting changes in the brain structures due to diseases, imaging live biological cells for analyzing their growth, etc.). The technical goals of this project are: 1) geometric understanding of high-dimensional data, which may allow efficient (re)sampling from manifolds representing certain phenomena of interest and classifying subtle yet critical differences that often appear in biological and medical applications; 2) providing theoretical guarantees and efficient numerical algorithms for non-convex optimization, which is crucial to machine learning; and 3) deepening understanding of how local interactions between individual entities (e.g., neurons) lead to global coordination and decision making.

This project is part of the National Science Foundation's Harnessing the Data Revolution (HDR) Big Idea activity.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.