Events Calendar

Ph.D. Defense

Speaker: Hoang Le, Ming Hsieh Department of Electrical Engineering

Talk Title: High Performance Architectures for Packet Forwarding and String Pattern Matching

Abstract: Internet routers in the backbone must move traffic to the correct destination as fast as possible. However, packet forwarding has long been a performance bottleneck. While the throughput requirements continue to grow, memory efficiency has also been an additional critical concern. Along with the rapid development of the Internet, network security has arisen as a major challenge. Computer networks are constantly assailed by attacks and scams, ranging from nuisance hacking to more nefarious probes and activities. Therefore, network traffic must be filtered to protect the network from these malicious activities.

The focus of my Ph.D research has been on the use of low-power memory, such as static random access memory (SRAM), combined with application-specific integrated circuit (ASIC) and/or field programmable gate array (FPGA) technology. The goals are to develop high-throughput, memory-efficient, and flexible algorithmic solutions for packet forwarding (used in core routers) and string pattern matching (used in network intrusion detection systems).

We have proposed tree-based algorithms and data structures for the IP lookup problem. The algorithm partitions a routing table into groups of prefixes to minimize the total memory consumption. Data structures that achieve superior memory efficiency and support quick incremental updates are also introduced. We have developed two algorithms to compress the uni-bit trie representation of a given routing table. These algorithms determine the optimal maximum skip distance at each node of the trie to minimize the total memory requirement. For IP lookup in virtual routers, we have given a simple merging algorithm whose performance is not sensitive to the number of routing tables considered is offered. The performance solely depends on the total number of prefixes. For string pattern matching problem, we have also designed an algorithm called leaf-attaching to efficiently disjoint a given dictionary without increasing the number of patterns is given. Our proposed solutions are evaluated using state-of-the-art ASIC/FPGA platforms. The implementation results demonstrate superior performance over the state-of-the-art, with respect to throughput and memory consumption.

Biography: Hoang Le received a B.S. (summa cum laude) and a M.S. in Computer Engineering from George Mason University, in 2005 and 2007, respectively. He also received a MS degree in Electrical Engineering from the University of Southern California in 2010. Hoang is currently a Ph.D. candidate in the Department of Electrical and Computer Engineering at USC. His research spans from high-performance architectures in network router to dictionary-based pattern matching in network security. He has also done research in secured embedded systems and cryptographic hardware. His primary focuses are on algorithm design, algorithm mapping on custom hardware, memory efficient data structures, and high-speed architectures.

Host: Viktor K. Prasanna (Committee Chair)

Audiences: Everyone Is Invited

Contact: Janice Thompson