TY - GEN
T1 - BUFFALO
T2 - 2009 ACM Conference on Emerging Networking Experiments and Technologies, CoNEXT'09
AU - Yu, Minlan
AU - Fabrikant, Alex
AU - Rexford, Jennifer L.
PY - 2009
Y1 - 2009
N2 - In enterprise and data center networks, the scalability of the data plane becomes increasingly challenging as forwarding tables and link speeds grow. Simply building switches with larger amounts of faster memory is not appealing, since high-speed memory is both expensive and power hungry. Implementing hash tables in SRAM is not appealing either because it requires significant overprovisioning to ensure that all forwarding table entries fit. Instead, we propose the BUFFALO architecture, which uses a small SRAM to store one Bloom filter of the addresses associated with each outgoing link. We provide a practical switch design leveraging flat addresses and shortest-path routing. BUFFALO gracefully handles false positives without reducing the packet-forwarding rate, while guaranteeing that packets reach their destinations with bounded stretch with high probability. We tune the sizes of Bloom filters to minimize false positives for a given memory size. We also handle routing changes and dynamically adjust Bloom filter sizes using counting Bloom filters in slow memory. Our extensive analysis, simulation, and prototype implementation in kernel-level Click show that BUFFALO significantly reduces memory cost, increases the scalability of the data plane, and improves packet-forwarding performance.
AB - In enterprise and data center networks, the scalability of the data plane becomes increasingly challenging as forwarding tables and link speeds grow. Simply building switches with larger amounts of faster memory is not appealing, since high-speed memory is both expensive and power hungry. Implementing hash tables in SRAM is not appealing either because it requires significant overprovisioning to ensure that all forwarding table entries fit. Instead, we propose the BUFFALO architecture, which uses a small SRAM to store one Bloom filter of the addresses associated with each outgoing link. We provide a practical switch design leveraging flat addresses and shortest-path routing. BUFFALO gracefully handles false positives without reducing the packet-forwarding rate, while guaranteeing that packets reach their destinations with bounded stretch with high probability. We tune the sizes of Bloom filters to minimize false positives for a given memory size. We also handle routing changes and dynamically adjust Bloom filter sizes using counting Bloom filters in slow memory. Our extensive analysis, simulation, and prototype implementation in kernel-level Click show that BUFFALO significantly reduces memory cost, increases the scalability of the data plane, and improves packet-forwarding performance.
KW - Bloom filter
KW - Enterprise and data center networks
KW - Packet forwarding
UR - http://www.scopus.com/inward/record.url?scp=76749169068&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=76749169068&partnerID=8YFLogxK
U2 - 10.1145/1658939.1658975
DO - 10.1145/1658939.1658975
M3 - Conference contribution
AN - SCOPUS:76749169068
SN - 9781605586366
T3 - CoNEXT'09 - Proceedings of the 2009 ACM Conference on Emerging Networking Experiments and Technologies
SP - 313
EP - 324
BT - CoNEXT'09 - Proceedings of the 2009 ACM Conference on Emerging Networking Experiments and Technologies
Y2 - 1 December 2009 through 4 December 2009
ER -