دانلود ترجمه مقاله کاربرد خطوط لوله دو طرفه موازی جهت جستجوی IP چند ترابیتی – مجله CiteSeerX

• فهرست مطالب:

 چکیده
۱ مقدمه
۲ پیشینه
۱ ۲ جستجوی IP مبتنی بر Trie
۲ ۲ خطوط لوله متعادل شده با حافظه
۳ ۲ موتورهای موازی مبتنی بر پارتیشن
۳ کلیات معماری
۱ ۳ Front End
۲ ۳ Back End
۳ ۳ به روزرسانی های مسیر
۴ تعادل بار حافظه
۱ ۴ پارتیشن بندی Trie
۲ ۴ نگاشت subtrie به خط لوله
۱ ۲ ۴ فرمول بندی مسئله
۲ ۲ ۴ الگوریتم نگاشت
۳ ۲ ۴ نتایج آزمایش
۳ ۴ نگاشت گره برای مرحله
۲ ۳ ۴ انگیزه نگاشت دانه ریز دو جهته
۳ ۳ ۴ وارونگی subtrie
۴ ۳ ۴ الگوریتم نگاشت
۵ ۳ ۴ مسائل پیاده سازی
۱ ۵ تعادل بار ترافیک با کش شدن
۶ ارزیابی عملکرد
۱ ۶ تعادل بار حافظه در میان مراحل خط لوله
۲ ۶ مقیاس بندی کارایی
۳ ۶ عملکرد کلی
۷ نتیجه گیری

• بخشی از ترجمه:

مقاله حاضر یک معماری چند خط لوله ای مبتنی بر SRAM برای جستجوی IP مبتنی بر trie چند ترابیتی پیشنهاد نمود. معماری پیشنهادی از چندین خط لوله خطی دو جهته تشکیل می شود که هر یک از آنها بخشی از جدول مسیریابی را ذخیره می کنند. معماری انعطاف پذیری بیشتری برای نگاشت trie های مسیریابی برای خط لوله فراهم می کند، به گونه ای که توزیع حافظه روی خطوط لوله مختلف و همچنین در میان مراحل مختلف در هر خط لوله متعادل می باشد. به علاوه، برای مقیاس بندی اصلاح و بهبود کارایی، کش شدن IP به شکلی موثر یکپارچه می شود. با استفاده از ۱٫۸MB حافظه جهت ذخیره جدول مسیریابی مرکزی با تقریباً ۲۳۷K پیشوند، معماری ۴ خط لوله ای پیشنهادی می تواند به کارایی بالای ۶ Tbps، به عبارتی ۳۷٫۵× نرخ OC-3072 دست یابد. کار آتی ما شامل تهیه نمونه اولیه از معماری پیشنهادی روی FPGA و ارزیابی عملکردش تحت سناریوهای زندگی واقعی می شود. 

• بخشی از مقاله انگلیسی:

The advent of terabit networks [21] poses a major challenge on the design of next generation IP routers. Some leading industrial vendors are already making efforts to offer multi-terabit core routers [8]. High link rates demand that IP lookup in routers must be performed in hardware. For instance, OC-3072 (160 Gbps) links require a throughput of 1 packet per 2 ns, i.e. 500 million packets per second (MPPS), for a minimum size (40 bytes) packet. Such throughput is impossible using existing software-based solutions [18]. Most hardware-based high-speed IP lookup engines fall into two main categories: TCAM (Ternary Content Addressable Memory)-based and DRAM/ SRAM (dynamic/ static random access memory)-based solutions. Although TCAM-based engines can retrieve IP lookup results in just one clock cycle, their throughput is limited by the relatively low clock rate of TCAMs. TCAMs are expensive and offer little flexibility to adapt to new addressing and routing protocols [7]. As shown in Table 1, SRAMs outperform TCAMs 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 [18], a tree-like data structure representing a collection of prefixes, is widely used in DRAM/SRAM-based solutions. Multiple memory accesses are needed to search a trie to find the longest matched prefix for an IP address. A number of researchers have explored pipelining to improve significantly the throughput. 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 [3, 2]. 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 in the following aspects. First, more time is needed to access the larger local memory. This leads to a 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 may 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. Such an over-provisioning results in memory wastage [2]. To balance the memory distribution across stages, several novel pipeline architectures have been proposed [2, 11, 6]. However, none of them can achieve a perfectly balanced memory distribution over stages. Some of them use non-linear structures, which result in throughput degradation, delay variation, and packet blocking during a route update. Furthermore, the “memory wall” [۱۴] tends to impede the performance improvement of a single pipeline architecture. Thus it becomes necessary to employ multiple pipelines operating in parallel to speed IP lookup. Each pipeline stores part of the routing table so that both power and memory efficiency can be achieved. Similar to the above analysis of how the fattest stage affects the global performance of a pipeline, the fattest pipeline is a performance bottleneck of the multi-pipeline architecture as well. Hence an efficient routing table partitioning and mapping scheme is needed to balance the memory requirement over different pipelines. On the other hand, traffic balancing is needed to achieve multiplicative throughput improvement. Previous work on parallel TCAM-based IP lookup engines uses either a learning algorithm to predict the future behavior of incoming traffic based on its current distribution [24], or IP/prefix caching to utilize the locality of Internet traffic [1]. The former requires periodic reconstruction of the entire routing table, resulting in high overhead of route updates for SRAM-based pipeline solutions. Hence we adopt caching in our architecture. Due to caching and queuing, packets within a flow1 may go out of order. This adversely affects some network applications [20]. Hence, expensive reorder buffers and complicated logic are usually needed. The proposed solution preserves the intra-flow packet order without using large reorder buffers. We propose an SRAM-based multi-pipeline architecture that consists of multiple bidirectional linear pipelines, for high throughput IP lookup.