Modern high-speed
routers forward packets from incoming ports to outgoing ports via switching
fabric, bypassing main memory and CPU. New technologies are pushing line speeds
beyond OC-768 (40Gb/s) to reach 100Gb/s or even tera bits per second. In order
to keep up with such high throughput,
online network functions
for traffic measurement, packet scheduling, access control, and quality of
service will also have to be implemented using on-chip cache memory and
bypassing main memory and CPU almost entirely. However, fitting these network
functions in fast but small on-chip memory represents a major technical
challenge today.
Implementation of
many online functions relies heavily on several fundamental building blocks for
data processing and storage. These building blocks are called
online primitives. Three fundamental online primitives are of particular
importance: (1)
spread estimators
for measuring the number of distinct elements in each flow, (2)
size estimators
for measuring the size of each flow, and (3)
high-performance Bloom
filters
for membership check against large data sets. Spread estimators can be used to
detect address/port scans or DDoS attacks, assist resource allocation in a
server farm, and determine popular web contents for caching. Size estimators has
applications in service provision, capacity planning, accounting and billing,
and anomaly detection. Bloom filters have been applied in routing-table lookup,
per-flow traffic measurement, flow label identification, firewall design, and
intrusion detection. Hence, improving the performance of these fundamental
primitives has significant impact on the performance of a wide range of network
applications.
The key technical challenge is to how to make online primitives both fast and compact. Being fast, the requirement is that these fundamental primitives should only make one memory access or update one counter in the worst case when processing each packet. Being compact, the requirement is that online primitives should use a minimum amount of memory and be able to handle a large, unpredictable number of flows. Even when the number of available bits is smaller than the number of flows, it should still be possible to measure per-flow state although the measurement accuracy will gracefully degrade due to limited memory. These requirements rule out virtually all existing methods of designing aforementioned online primitives. This project will advance the state-of-the-art technologies for fast and compact online primitives. It strives to fulfil the above requirements with new methodologies, called virtual bit vectors and virtual counting vectors, for online data storage and retrieval. The project consists of four research components: 1. one-memory- access compact spread estimators, 2. one-counter-update compact size estimators, 3. one-memory-access fast Bloom filters, and 4. architecture-aware online primitive designs.
Related Publications:
1.
1.
X. Tao,
Y. Qiao, Jih-Kwon Peir, S. Chen, Z. Huang, and S. Liu, "Guided Multiple Hashing:
Achieving Perfect Balance with Fast Lookup,"
21st IEEE International Conference on
Network Protocols (ICNP), Gottingen Germany, Oct. 2013.
3.
Zhuo Huang, Jih-Kwon Peir, Shigang Chen, "Approximately-Perfect Hashing:
Improving Network Throughput through Efficient Off-chip Routing Table Lookup",
30th IEEE International Conference on
Computer Communications (INFOCOM), Shanghai China, April 2011.
4.
Z.
Huang, D. Lin, S. M. Iftekharul Alam, S. Chen, and Jih-Kwon Peir, "'Fast Routing
Table Lookup Based on Deterministic Multi-hashing,"
18th IEEE International Conference on
Network Protocols (ICNP), Kyoto Japan, Oct. 2010.
5. M.K. Yoon, T. Li, S. Chen, J-K. Peir, "Fitting a Spread Estimator in a Small Memory," 28th IEEE International Conference on Computer Communications, (INFOCOM), Atlanta GA, April, 2009.