حافظه قابل آدرس دهی با محتوا (TCAM) و معماری چند خط لوله ای موازی مبتنی بر SRAM
شابک پرینت: 9781424420254 وبسایت مرجع 30 رفرنس دارد
18,500 تومانشناسه فایل: 7246
چکیده
رشد مداوم نرخ ارتباطات شبکه، تقاضای موتورهای جستجو با سرعت بالا IP را شدت بخشیده است. در حالی که راهکارهای مبتنی بر حافظه قابل آدرس دهی با محتوا (TCAM) در بسیاری مسیریاب های پیشرفته امروزی به کار گرفته می شوند برای نسل بعدی مناسب نیست. از سوی دیگر، راهکارهای الگوریتمی مبتنی بر SRAM جذاب می شوند. به طور منطقی، چندین خط لوله را می توان به طور موازی به کار گرفت تا تاثیری چندگانه بر توان عملیاتی داشته باشند. با این حال، برای محقق کردن توان عملیاتی بالا چالش های متعددی را باید برای این راهکارها باید حل کنیم. اول، توزیع حافظه در سطوح هر خط لوله و نیز در خط لوله های مختلف را باید متوازن کرد. دوم، ترافیک موجود بر روی خط لوله های مختلف باید متعادل شود.
در این مقاله یک معماری چند خط لوله ای مبتنی بر SRAM موازی را برای جستجوی IP ترابیت پیشنهاد می دهیم. برای متوازن کردن الزامات حافظه بر روی سطح، یک نقشه برداری دو سطحی ارائه شده است. با تقسیم بندی ترای (درخت پیشوندی) و نقشه برداری ساب ترای به خط لوله، اطمینان حاصل می کنیم که هر خط لوله تقریباً حاوی تعداد گره های ترای برابر است. سپس، در هر خط لوله برای دستیابی به توزیع یکنواخت حافظه در سطح، یک نقشه برداری دقیق گره به سطح مورد استفاده قرار می گیرد. برای متوازن کردن ترافیک روی خط لوله های مختلف، نهان سازی خط لوله ای پیشوند و نقشه برداری مجدد پویای ساب ترای به خط لوله به کار گرفته می شود. شبیه سازی با استفاده از داده های واقعی نشان می دهد که معماری پیشنهادی با 8 خط لوله می تواند یک جدول مسیریابی اصلی با بیش از 200 هزار پیشوند مسیریابی منحصر به فرد را با استفاده از 3.5 مگابایت حافظه ذخیره کند. این ظرفیت به توان عملیاتی تا 3.2 میلیارد بسته در هر ثانیه می رسد، یعنی 1 ترابیت بر ثانیه برای بسته های کوچک (40 بایت).
مقدمه مقاله
جستجوی IP با همخوانی طولانی ترین پیشوند، وظیفه اصلی مسیریاب های اینترنت است. هر چه اینترنت به رشد سریع خود ادامه می دهد این موضوع تبدیل به مانع بزرگی برای مسیریاب های پشتیبان شده است. با پیشرفت تکنولوژی شبکه بندی نوری، نرخ ارتباط در مسیریاب های پرسرعت از OC-768 (40 گیگابیت بر ثانیه) به نرخ هایی حتی بالاتر رسیده است. چنین نرخ های بالایی مستلزم آن است که جستجوی IP باید در سخت افزار انجام شود. برای نمونه، ارتباطات 40 Gbps مستلزم یک توان عملیاتی برابر با 8ns در هر جستجو برای بسته ای با حداقل اندازه (40 بایت) است. این توان عملیاتی با استفاده از راهکارهای موجود مبتنی بر نرم افزار، غیرممکن است.
اکثر راهکارهای مبتنی بر سخت افزار برای جستجوی پرسرعت IP در دو دسته اصلی قرار می گیرند: راهکارهای مبتنی بر TCAM (حافظه قابل آدرس دهی با محتوا) و راهکارهای مبتنی بر DRAM/SRAM (حافظه دسترسی تصادفی پویا/ استاتیک). اگرچه موتورهای مبتنی بر TCAM می توانند نتایج جستجوی IP را فقط در یک سیکل ساعت بازیابی کنند، توان عملیاتی آن ها با سرعت نسبتاً پایین TCAM ها محدود شده است. آن ها گران هستند و انعطاف پذیری کمی برای انطباق با پروتکل های جدید آدرس دهی و مسیریابی دارند. همان گونه که در جدول 1 نشان داده شده است، از نظر سرعت، تراکم و مصرف انرژی، SRAM بهتر از TCAM عمل می کند. با این وجود، راهکارهای سنتی مبتنی بر SRAM (که اکثر آنها را می توان به عنوان شکلی از پیمایش درخت در نظر گرفت) به سیکل های ساعت بیشتری برای انجام یک جستجو نیاز دارند. برای مثال، ترای (یک ساختار درخت مانند که نمایانگر مجموعه ای از پیشوندها است) به طور گسترده در راهکارهای مبتنی بر SRAM استفاده می شود. برای جستجوی یک ترای به منظور یافتن طولانی ترین پیشوند برای یک بسته IP، نیازمند چندین دسترسی حافظه است.
پژوهشگران مختلف، به منظور بهبود قابل توجه توان عملیاتی، پردازش لوله ای را مورد بررسی قرار داده اند. به عنوان مثال راهکارهای مبتنی بر ترای را در نظر بگیرید، یک روش پرداز لوله ای، نگاشت هر سطح ترای به یک سطح خط لوله با حافظه و منطق پردازش خود آن است. یک جستجوی IP را می توان در هر سیکل ساعت انجام داد. با این وجود، این روش منجر به توزیع نامتوازن گره ترایبر روی سطوح خط لوله می شود. این موضوع به عنوان مسئله مهمی برای معماری های خط لوله ای شناخته شده است. در یک خط لوله نامتوازن، ضخیم ترین سطح که بیشترین تعداد گره های ترای را ذخیره می کند، به یک مانع تبدیل می شود. این سطح به دلایل زیر به طور معکوس بر عملکرد کلی خط لوله تأثیر می گذارد. اولاً برای دسترسی به حافظه محلی بیشتر به زمان بیشتری نیاز دارد. این منجر به کاهش نرخ کلی ساعت می شود. ثانیاً یک سطح ضخیم به دلیل ارتباط تناسبی بین تعداد به روز رسانی ها و تعداد گره های ترای ذخیره شده در آن سطح، منجر به به روز رسانی های متعدد می شود. به خصوص در طی فرایند به روز رسانی که باتعبیه کامل مسیر ایجاد شده است، ضخیم ترین سطح نیز می تواند منجر به سربار حافظه شود. علاوه بر این، از آنجایی که در زمان طراحی سخت افزار روشن نیست کدام سطح ضخیم تر خواهد بود، باید حافظه را با حداکثر اندازه برای هر مرحله تخصیص بدهیم. این منجر به اتلاف حافظه می شود.
برای دستیابی به توزیع متوازن حافظه در سطوح، چند معماری جدید خط لوله پیشنهاد شده است. با این وجود، ساختار غیر خطی خط لوله آن ها منجر به کاهش توان عملیاتی می شود و اکثر آنها باید عملیات مستمر را در طول به روز رسانی یک مسیر مختل کنند. پژوهش قبلی ما برای توزیع یکنواخت گره های یک ترای تک بیتی با برگ های فشرده در سطوح مختلف خط لوله، یک معماری خط لوله خطی را به همراه یک طرح دقیق نگاشت گره به مرحله ارائه کرد. این معماری می تواند به توان عملیاتی بالای یک جستجو در هر سیکل ساعت دست پیدا کند و نیز از write bubbles برای به روز رسانی های افزایشی بدون مختل کردن عملیات مسیریاب پشتیبانی کند.
با این وجود، بهبود سرعت دسترسی به حافظه محدودتر است. بنابراین به کارگیری چند خط لوله که بتوانند برای افزایش سرعت جستجوی IP به طور همزمان عمل کنند، ضروری می شود. متوازن کردن حافظه و ترافیک در میان چند خط لوله به مشکلات جدید تبدیل شده اند. مشابه با تحلیل فوق از نحوه تاثیرگذاری ضخیم ترین سطح بر عملکرد کلی یک خط لوله، بزرگترین خط لوله که بیشترین تعداد گره های ترای را ذخیره می کند به مانع عملکرد معماری خط لوله تبدیل خواهد شد. جدا از راهکارهای مبتنی بر TCAM، متوازن کردن حافظه، چالش اصلی برای راهکارهای خط لوله مبتنی بر SRAM است. از سوی دیگر، مشابه با راهکارهای مبتنی بر TCAM، متوازن کردن ترافیک مستلزم دستیابی به بهبود مضاعف توان عملیاتی است. پژوهش های قبلی در مورد موتورهای جستجوی IP مبتنی بر TCAM یا از یک الگوریتم یادگیری برای پیش بینی رفتار آتی ترافیک ورودی بر اساس توزیع فعلی آن استفاده می کنند یا نهان سازی IP یا پیشوند را برای استفاده از مجاورت ترافیک اینترنت به کار می گیرند. ما ادعا می کنیم که هر دو طرح را می توان برای راهکارهای مبتنی بر SRAM منطبق کرد.
این مقاله هر دو مشکل را مورد توجه قرار می دهد: متوازن کردن حافظه و ترافیک برای یک معماری چند خط لوله ای موازی مبتنی بر SRAM. این مقاله، دستاوردهای عمده زیر را ایجاد می کند.
- تا جایی که ما می دانیم این پژوهش اولین بحث بر روی راهکارهای خط لوله مبتنی بر SRAM برای مسیریابهای ترابیتی نسل بعد است.
- یک طرح نگاشت دوسطحی جدید برای متوازن کردن توزیع حافظه بر روی چند خط لوله و بر روی تمام سطوح خط لوله ارائه شده است.
- بر اساس تحلیل جدول های مسیریابی فعلی، یک روش ساده اما کارآمد برای تقسیم بندی ترای ارائه شده است.
- نهان سازی پردازش لوله ای پیشوندو نگاشت مجدد پویای ساب ترای برای متوازن کردن ترافیک در میان چند خط لوله وارد شده است.
- نتایج ما نشان می دهد که راهکار الگوریتمی پردازش لوله ای مبتنی بر SRAM جایگزین امیدوارکننده ای برای راهکارهای مبتنی بر TCAM برای مسیریاب های پیشرفته آینده است. معماری 8 خط لوله ای پیشنهادی می تواند یک جدول مسیریابی اصلی با بیش از 200 هزار پیشوند منحصر به فرد را با استفاده از 3.5 مگابایت حافظه ذخیره کند. این معماری می تواند به یک توان عملیاتی تا 3.2 میلیارد بسته در هر ثانیه دست پیدا کند یعنی 1 ترابیت بر ثانیه برای بسته هایی با حداقل اندازه (40 بایت).
بقیه این مقاله به این شرح است. بخش 2 پس زمینه و پژوهش های مرتبط را بررسی می کند. بخش 3 یک معماری موازی با چند خط لوله خطی با حافظه متوازن را پیشنهاد می کند که معماری خط لوله خطی بهینه شده موازی (POLP) نامیده می شود. دو مشکل متوازن کردن حافظه و ترافیک به ترتیب در بخش های 4 و 5 مورد بحث قرار می گیرند. برای ارزیابی عملکرد POLP، آزمایشات در بخش 6 انجام شده است. بخش 7، مقاله را به پایان می رساند.
ABSTRACT Beyond TCAMs: An SRAM-Based Parallel Multi-Pipeline Architecture for Terabit IP Lookup
Continuous growth in network link rates poses a strong demand on high speed IP lookup engines. While Ternary Content Addressable Memory (TCAM) based solutions serve most of today’s high-end routers, they do not scale well for the next-generation. On the other hand, pipelined SRAM- based algorithmic solutions become attractive. Intuitively multiple pipelines can be utilized in parallel to have a multiplicative effect on the throughput. However, several challenges must be addressed for such solutions to realize high throughput. First, the memory distribution across different stages of each pipeline as well as across different pipelines must be balanced. Second, the traffic on various pipelines should be balanced. In this paper, we propose a parallel SRAM-based multi- pipeline architecture for terabit IP lookup. To balance the memory requirement over the stages, a two-level mapping scheme is presented. By trie partitioning and subtrie-to-pipeline mapping, we ensure that each pipeline contains approximately equal number of trie nodes. Then, within each pipeline, a fine-grained node-to-stage mapping is used to achieve evenly distributed memory across the stages. To balance the traffic on different pipelines, both pipelined prefix caching and dynamic subtrie-to-pipeline remapping are employed. Simulation using real-life data shows that the proposed architecture with 8 pipelines can store a core routing table with over 200 K unique routing prefixes using 3.5 MB of memory. It achieves a throughput of up to 3.2 billion packets per second, i.e. 1 Tbps for minimum size (40 bytes) packets.
Introduction
IP lookup with longest prefix matching is a core function of Internet routers. It has become a major bottleneck for backbone routers as the Internet continues to grow rapidly [2]. With the advances in optical networking technology, link rates in high speed IP routers are being pushed from OC- 768 (40 Gbps) to even higher rates. Such high rates demand that IP lookup in routers must be performed in hardware. For instance, 40 Gbps links require a throughput of 8 ns per lookup for a minimum size (40 bytes) packet. Such throughput is impossible using existing software-based solutions [3].
Most hardware-based solutions for high speed IP lookup fall into two main categories: TCAM (ternary content addressable memory)-based and DRAM/SRAM (dynamic/static random access memory)-based solutions. Although TCAMbased engines can retrieve IP lookup results in just one clock cycle, their throughput is limited by the relatively low speed of TCAMs. They are expensive and offer little flexibility for adapting to new addressing and routing protocols [4]. As shown in Table I, SRAM outperforms TCAM with respect to speed, density and power consumption. However, traditional SRAM-based solutions, most of which can be regarded as some form of tree traversal, need multiple clock cycles to complete a lookup. For example, trie [3], a tree-like data structure representing a collection of prefixes, is widely used in SRAM-based solutions. It needs multiple memory accesses to search a trie to find the longest matched prefix for an IP packet.
Several researchers have explored pipelining to improve the throughput significantly. Taking trie-based solutions as an example, a simple pipelining approach is to map each trie level onto a pipeline stage with its own memory and processing logic. One IP lookup can be performed every clock cycle. However, this approach results in unbalanced trie node distribution over the pipeline stages. This has been identified as a dominant issue for pipelined architectures [11], [12].
In an unbalanced pipeline, the “fattest” stage, which stores the largest number of trie nodes, becomes a bottleneck. It adversely affects the overall performance of the pipeline for the following reasons. First, it needs more time to access the larger local memory. This leads to reduction in the global clock rate. Second, a fat stage results in many updates, due to the proportional relationship between the number of updates and the number of trie nodes stored in that stage. Particularly during the update process caused by intensive route insertion, the fattest stage can also result in memory overflow. Furthermore, since it is unclear at hardware design time which stage will be the fattest, we need to allocate memory with the maximum size for each stage. This results in memory wastage.
To achieve a balanced memory distribution across stages, several novel pipeline architectures have been proposed [13], [14]. However, their non-linear pipeline structures result in throughput degradation, and most of them must disrupt ongoing operations during a route update. Our previous work[15] proposed a linear pipeline architecture with a fine-grained node-to-stage mapping scheme to distribute nodes of a leafpushed uni-bit trie evenly to different pipeline stages. It can achieve a high throughput of one lookup per clock cycle, as well as support write bubbles [12] for incremental updates without disrupting router operations.
However, improvement in memory access speed is rather limited. Thus it becomes necessary to employ multiple pipelines which can operate concurrently to speed up IP lookup. Memory and traffic balancing among multiple pipelines become new problems. Similar to the above analysis of how the fattest stage affects the global performance of a pipeline, the largest pipeline which stores the largest number of trie nodes will become a performance bottleneck of the multipipeline architecture. Distinct from TCAM-based solutions, memory balancing is the primary challenge for SRAM-based pipeline solutions. On the other hand, similar to TCAM-based solutions, traffic balancing is needed to achieve multiplicative throughput improvement. Previous works on parallel TCAMbased IP lookup engines use either a learning algorithm to predict the future behavior of incoming traffic based on its current distribution [16], [17], or IP or prefix caching to utilize the locality of Internet traffic [18], [19]. We claim that both schemes can be adapted for SRAM-based solutions.
This paper addresses both problems: memory and traffic balancing for an SRAM-based parallel multi-pipeline architecture. This paper makes the following main contributions.
- To the best of our knowledge, this work is the first discussion of parallel SRAM-based pipeline solutions for next-generation terabit routers.
- A novel two-level mapping scheme is proposed to balance the memory distribution over multiple pipelines and over all pipeline stages.
- Based on the analysis of current routing tables, a simple but efficient method is proposed for trie partitioning.
- Both pipelined prefix caching and dynamic subtrie remapping are incorporated to balance the traffic among multiple pipelines.
- Our results demonstrate that the SRAM-based pipelined algorithmic solution is a promising alternative to TCAMbased solutions for future high-end routers. The proposed 8-pipeline architecture can store a full core routing table with over 200K unique prefixes using 3.5 MB of memory. It can achieve a high throughput of up to 3.2 billion packets per second, i.e. 1 Tbps for minimum size (40 bytes) packets.
The remainder of this paper is organized as follows. Section II reviews the background and related works. Section III proposes a parallel architecture with multiple memory-balanced linear pipelines, called the Parallel Optimized Linear Pipeline (POLP) architecture. The two problems of memory and traffic balancing are discussed in Sections IV and V, respectively. Experiments are conducted in Section VI to evaluate the performance of POLP. Section VII concludes the paper.
- مقاله درمورد حافظه قابل آدرس دهی با محتوا (TCAM) و معماری چند خط لوله ای موازی مبتنی بر SRAM
- معماری چند خط لوله ای مبتنی بر SRAM موازی برای جستجوی IP ترابیتی
- فراتر از TCAM ها: یک موازی مبتنی بر SRAM معماری چند خطی برای Terabit IP Lookup
- پروژه دانشجویی حافظه قابل آدرس دهی با محتوا (TCAM) و معماری چند خط لوله ای موازی مبتنی بر SRAM
- معماری چند خط لوله ای موازی مبتنی بر SRAM
- پایان نامه در مورد حافظه قابل آدرس دهی با محتوا (TCAM) و معماری چند خط لوله ای موازی مبتنی بر SRAM
- تحقیق درباره حافظه قابل آدرس دهی با محتوا (TCAM) و معماری چند خط لوله ای موازی مبتنی بر SRAM
- مقاله دانشجویی حافظه قابل آدرس دهی با محتوا (TCAM) و معماری چند خط لوله ای موازی مبتنی بر SRAM
- حافظه قابل آدرس دهی با محتوا (TCAM) و معماری چند خط لوله ای موازی مبتنی بر SRAM در قالب پايان‌نامه
- پروپوزال در مورد حافظه قابل آدرس دهی با محتوا (TCAM) و معماری چند خط لوله ای موازی مبتنی بر SRAM
- گزارش سمینار در مورد حافظه قابل آدرس دهی با محتوا (TCAM) و معماری چند خط لوله ای موازی مبتنی بر SRAM
- گزارش کارورزی درباره حافظه قابل آدرس دهی با محتوا (TCAM) و معماری چند خط لوله ای موازی مبتنی بر SRAM