Terabit Lookups

太比特查找

• 批准号: 0074004
• 负责人: George Varghese
• 金额: $ 30万
• 依托单位: University of California-San Diego
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2000
• 资助国家: 美国
• 起止时间: 2000-10-01 至 2003-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0074004&HistoricalAwards=false
• 关键词: Terabit; Lookups

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.

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