Compressing forwarding tables
Compressing forwarding tables
复制标题
DOI：
10.1109/infcom.2013.6566915
复制
发表时间：
2013-04
期刊：
影响因子：
--
通讯作者：
Ori Rottenstreich;Marat Radan;Yuval Cassuto;I. Keslassy;Carmi Arad;Tal Mizrahi;Yoram Revah;Avinatan Hassidim
中科院分区：
文献类型：
--
作者：
Ori Rottenstreich;Marat Radan;Yuval Cassuto;I. Keslassy;Carmi Arad;Tal Mizrahi;Yoram Revah;Avinatan Hassidim
随着数据中心虚拟化的兴起，转发表中的条目数量有望从数千个数百万人扩展到数百万。不幸的是，今天几乎无法在片上内存中实现这种转发桌子。在本文中，我们研究了转发表的可压缩性。我们首先介绍了一个新颖的转发桌体系结构，每列中都有单独的编码。它旨在继续支持快速的随机访问和固定宽度的内存单词。然后，我们建议一个编码，其每行条目的内存需求保证在最佳的较小的附加常数之内。接下来，我们分析了两列转发表的常见情况，并证明可以将这些表显示为两部分图。我们在编码大小上推断出图理论界限。我们还引入了一种算法，用于给定第一个列的编码第二列的最佳条件编码。此外，我们解释了我们的体系结构如何处理表更新。最后，我们评估了有关合成转发表以及现实表的建议编码技术。
With the rise of datacenter virtualization, the number of entries in forwarding tables is expected to scale from several thousands to several millions. Unfortunately, such forwarding table sizes can hardly be implemented today in on-chip memory. In this paper, we investigate the compressibility of forwarding tables. We first introduce a novel forwarding table architecture with separate encoding in each column. It is designed to keep supporting fast random accesses and fixed-width memory words. Then, we suggest an encoding whose memory requirement per row entry is guaranteed to be within a small additive constant of the optimum. Next, we analyze the common case of two-column forwarding tables, and show that such tables can be presented as bipartite graphs. We deduce graph-theoretical bounds on the encoding size. We also introduce an algorithm for optimal conditional encoding of the second column given an encoding of the first one. In addition, we explain how our architecture can handle table updates. Last, we evaluate our suggested encoding techniques on synthetic forwarding tables as well as on real-life tables.