Terabit Lookups

网络协议使用用于诸如IP查找（例如，尝试），桥接查找（例如，散列表），以及分组过滤（例如，Pathfinder）。 网络查找是当今互联网路由器的关键瓶颈。 随着互联网链路速度提高到10 Gbps（OC-192）和40 Gbps（OC-768），状态查找必须在数十纳秒内完成。 研究人员认为，在这一建议，这样的下一代查找问题的解决方案必须跨越从算法到计算机体系结构的许多领域。 该建议是专门调查这种交叉问题，出现在下一代网络查找的背景下。 目前使用外部DRAM（动态RAM）的查找技术无法扩展到这个速度;因此，太比特查找将需要使用片内或片外SRAM（静态RAM）。 这种存储器受到费用或制造工艺的限制|例如，在一个实施例中，16 Mbits的片上SRAM被认为是乐观的。 在这个建议中，研究人员认为，在处理这样的状态查找在太比特的速度使用有限的快速存储器，同时提供可证明的保证所涉及的问题。 在该提议中考虑的一个重要问题是SRAM存储器利用率：如果查找芯片要提供关于状态量的保证（例如，的IP前缀的数目），它可以处理，resarcher表明，查找芯片必须使用一个内存分配器，可以保证一个可证明的内存利用率。 然而，所有传统的存储器分配算法（例如，First Fit、Best Fit、Buddy System）只能保证较差的最坏情况利用率：例如，对于大小为32的请求，标准分配器只能保证1/log 2 32 = 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.