Terabit Lookups

使用用于诸如IP查找(例如，尝试)、网桥查找(例如，哈希表)和分组过滤(例如，路径查找器)等功能的多个数据结构的网络协议查找状态。网络查找是当今互联网路由器的一个关键瓶颈。随着互联网链路速度达到10 Gbps(OC-192)和40 Gbps(OC-768)，状态查找必须在几十纳秒内完成。研究人员在这项提案中认为，这种下一代查找问题的解决方案必须跨越从算法到计算机体系结构的多个领域。该提案致力于调查在下一代网络查找环境中出现的此类横切问题。当前使用外部DRAM(动态RAM)的查找技术无法扩展到这种速度；因此，太比特查找将需要使用片上或片外SRAM(静态RAM)。这样的存储器受到成本或制造工艺的限制|例如，16MB的片内SRAM被认为是乐观的。在这项建议中，研究人员考虑了在提供可证明的保证的同时，使用有限的快速存储器以太比特的速度处理这种状态查找所涉及的问题。在该方案中考虑的一个重要问题是SRAM存储器利用率：如果查找芯片要提供关于其可以处理的状态量(例如，IP前缀的数量)的保证，则研究人员表明查找芯片必须使用能够保证可证明的存储器利用率的存储器分配器。然而，所有传统的内存分配算法(例如，First Fit、Best Fit、Buddy System)仅保证较差的最坏情况利用率：例如，对于大小为32的请求，由于可能的碎片，标准分配器只能保证1/log232=20%的利用率。该提案引入了新的针对特定问题的内存分配方案，可以对这些方案进行调整，以提供接近100%的最坏情况下的内存利用率。例如，使用研究人员的新分配方案进行IP查找的芯片可以保证处理几乎是传统分配器可以处理的前缀数量的5倍，而且还可以允许大约100微秒的插入/删除时间。研究人员的方案使用了新的算法；研究人员方案的最佳版本还需要新的SRAM存储器设计，除了正常的字访问外，还允许移位访问。该研究还建议调查其他问题，包括内存分配与流水线的相互作用(即，将内存动态分配给阶段)，以及引入能够支持记账和服务质量的新查找原语。例如，研究人员希望研究一种新的范例，用于基于深度而不是高度来流水线化Trie，这似乎具有更有限的内存使用。作为第二个例子，研究人员希望调查进行包含成本域的前缀查找的可能性；这样的查找可用于更新每个输入链路的累积成本域。该提案旨在调查在设计太比特查找时出现的这些和其他问题，寻找新的机制，并实施、评估和微调研究人员的新想法。

Network protocols lookup state using a number of data structures for functions such as IP lookups (e.g., tries), bridge lookups (e.g., hash tables), and packet filtering (e.g., Pathfinder). Network lookups are a key bottleneck for Internet routers today. As Internet link speeds move to 10 Gbps (OC-192) and 40 Gbps (OC-768), state lookups must complete in tens of nanoseconds. The researcher argues in this proposal that solutions to such next generation lookup problems must span a number of areas from algorithms to computer architecture. The proposal is devoted to investigating such crosscutting issues that arise in the context of next generation network lookups. Current lookup technology that uses external DRAM (Dynamic RAM) cannot scale to this speeds; thusTerabit lookups will require the use of on-chip or off-chip SRAM (Static RAM). Such memory is limited by either expense or manufacturing process | e.g., on-chip SRAM of 16 Mbits is considered optimistic. In this proposal, the researcher considers the issues involved in dealing with such state lookups at Terabit speeds using limited fast memory while providing provable guarantees. An important issue considered in this proposal is SRAM memory utilization: if the lookup chip is to provide guarantees about the amount of state (e.g., number of IP prefixes) it can handle, the resarcher shows that the lookup chip must use a memory allocator which can guarantee a provable memory utilization ratio. However, all conventional memory allocation algorithms (e.g., First Fit, Best Fit, Buddy System) only guarantee poor worst case utilizations: for example, for requests of size 32 standard allocators can only guarantee a utilization ratio of 1/log2 32 = 20% because of possible fragmention. The proposal introduces new problem-specific memory allocation schemes that can be tuned to provide worst-case memory utilization ratios close to 100%. For example, a chip that does IP lookups using the researcher's new allocation schemes can guarantee to handle almost 5 times the number of prefixes that can be handled by a conventional allocator, and yet can allow insert/delete times of around 100 microseconds. The researcher'sschemes use new algorithms; optimal versions of the researcher's schemes also require new SRAM memory designs that allow shifted access in addition to normal word access. The research also proposes to investigate other issues including the interaction of memory allocation with pipelining (i.e., dynamically allocating memory to stages), and the introduction of new lookup primitives that can support accounting and Quality of Service. For example, the researcher wishes to investigate a novel paradigm for pipelining a trie based on depth rather than height which appears to have a more bounded use of memory. As a second example,the researcher wishes to investigate the possibility of doing prefix lookups that contain a cost field; such a lookup can be used to update a accumulated cost field per input link. The proposal seeks to investigate these and other issues that arise when designing Terabit lookups, to search for new mechanisms, and implement, evaluate, and fine-tune the researcher's new ideas.