فایل ورد کامل تطبیق پیشوند نام با استفاده از پیش جستجوی فیلتر بلوم برای شبکه محتوی محور

توجه : به همراه فایل word این محصول فایل پاورپوینت (PowerPoint) و اسلاید های آن به صورت هدیه ارائه خواهد شد

این مقاله، ترجمه شده یک مقاله مرجع و معتبر انگلیسی می باشد که به صورت بسیار عالی توسط متخصصین این رشته ترجمه شده است و به صورت فایل ورد (microsoft word) ارائه می گردد

متن داخلی مقاله بسیار عالی، پر محتوا و قابل درک می باشد و شما از استفاده ی آن بسیار لذت خواهید برد. ما عالی بودن این مقاله را تضمین می کنیم

فایل ورد این مقاله بسیار خوب تایپ شده و قابل کپی و ویرایش می باشد و تنظیمات آن نیز به صورت عالی انجام شده است؛ به همراه فایل ورد این مقاله یک فایل پاور پوینت نیز به شما ارئه خواهد شد که دارای یک قالب بسیار زیبا و تنظیمات نمایشی متعدد می باشد

توجه : در صورت مشاهده بهم ریختگی احتمالی در متون زیر ،دلیل ان کپی کردن این مطالب از داخل فایل می باشد و در فایل اصلی فایل ورد کامل تطبیق پیشوند نام با استفاده از پیش جستجوی فیلتر بلوم برای شبکه محتوی محور،به هیچ وجه بهم ریختگی وجود ندارد

تعداد صفحات این فایل: ۲۵ صفحه

۱ مقدمه

برنامه‌های اینترنتی نوظهور مانند شبکه‌های اجتماعی، به صورت وسیعی فایل‌های تصویری، ویدئویی و صوتی را به اشتراک می‌گذارند. این ترافیک به عنوان محتواهای حجیم و  با تقاضای مکرر، به صورت کارآمدی در اینترنت امروزی که زیرساختی مبتنی بر میزبان دارد، انتقال داده نمی‌شود. شبکه‌ی محتوی محور(CCN) یک شبکه‌ی نسل آینده طراحی شده  و نوید بخش برای حل این مشکلات در اینترنت امروزی است. شبکه‌ی CCN با نام شبکه اطلاعات محور(ICN) یا شبکه‌ی داده‌‌ی نامگذاری شده (NDN) نیز شناخته می‌شود. شبکه‌ی CCN ارتباط داده ها را بر اساس نام های محتوی انجام می دهند، در حالی که اینترنت موجود از ارتباطات میزبان-به-میزبان مبتنی بر آدرس‌های IP استفاده می‌‌نماید. (Jacobson et al., 2009;Vasilakos et al., 2015;Bari et al., 2012;Xu et al., 2014; Qiao et al., 2015; Wang et al., 2012; Esteve et al., 2008; Perino and Varvello, 2011). در مقاله‌ی ژاکوبسن و همکاران ۲۰۰۹، ویژگی‌های پایه‌ی CCN پیاده‌سازی شده و تاب آوری و کارآیی معماری CCN با ارتباط مبتنی بر میزبان از نظر انتقال فایل، توزیع محتوا و تماس‌های صوتی مقایسه می شود.

CCN به جای مفهوم میزبان‌های منبع یا مقصد، از مولد و مصرف‌کننده‌ی محتوا استفاده می‌کند. مولد‌ها،‌ محتوا را تولید و مشتریان آن‌ها را دریافت و مصرف می‌کنند. روترها با استفاده از نام‌های محتوا به جای آدرس‌های IP، مسیر یابی را انجام می‌دهند. برخلاف روترهای مرسوم، روترهای CCN قابلیت ذخیره در کش هم دارند، که محتوا را به صورت موقت ذخیره و آن را به کاربران درخواست کننده ارسال می‌کنند. بدین طریق، کاربران CCN می‌توانند به سرعت محتوای درخواستخود را به دست آورده، و لزومی ندارد که همان محتوا به صورت مکرر در طول شبکه انتقال داده شود.

CCN از دو نوع بسته استفاده می‌کند: بسته درخواست و داده. بسته درخواست توسط مصرف کننده، پخش می‌گردد. بسته‌ی داده توسط مولد محتوا تولید شده و به هر نودی که پیام درخواست را شنیده و پیام داده را در اختیار دارد، ارسال می‌شود. یک روتر CCN سه جدول مختلف را تشکیل می‌دهد: جدول محتواها (CS)، جدول تعلیق پیام‌های درخواست(PIT)، و پایه‌ی اطلاعات ارسال (FIB). CS یک کش ذخیره‌‌کننده‌ی بسته‌های داده است. PIT برای ارسال بسته‌های داده استفاده می‌شود، و FIB برای ارسال بسته‌های درخواستبه کار می‌رود. برای فورواردینگ بسته به صورت پرسرعت، باید الگوریتم‌های جستجوی کارآمدی در اختیار داشت که طولانی‌ترین تطبیق نام را برای هر بسته درخواستورودی اجرا می‌کنند.

trie یک ساختار داده‌ی منظم مبتنی بر درخت است که نام آن از کلمه‌ی retrieval (بازیابی) نشأت گرفته است. عبارت trie را از کلمه‌ی tree هم گرفته‌ایم. در یک ساختار trie، همه‌ی اولاد یک نود، دارای پیشوند مشترکی مرتبط با آن نود هستند، در حالی که این مسئله همیشه در یک ساختار درختی صحیح نیست. یک پیشوند نام trie (NPT) به عنوان یک trie تعمیم داده شده برای الگوریتم جستجوی نام، پیشنهاد داده شده است (ونگ و همکاران، ۲۰۱۱). NPT یک روش ابتکاری برای جستجوی نام با طولانی‌ترین تطبیق است، اما مشکلی از نظر عملکرد جستجو دارد، چرا که یک جدول FIB ممکن است میلیون‌ها نام محتوا داشته و هر نام محتوا می‌تواند بسیار طولانی باشد.

هدف این مقاله، ارائه‌ی یک روش جدید برای تطبیق طولانی‌ترین نام استفاده شده در جستجوهای FIB در روترهای CCN است. روش پیشنهادی بر اساس پیشوند نام trie می‌باشد. به منظور حل مسئله‌ی عملکرد جستجو در NPT، پیشنهاد کرده‌ایم که یک فیلتر بلوم در درون تراشه ایاضافه شود که قبل از دسترسی به NPT پرس و جو را انجام دهد که این جستار ها در جدول هش برون تراشه ای، ذخیره می‌گردند. چون یک ساختار داده‌ی احتمالاتی و فضا-کارآمد برای تست اینکه آیا یک عنصر، عضوی از یک مجموعه است یا خیر، بکار می‌رود، فیلترهای بلوم عموماً به الگوریتم‌های شبکه اعمال می‌شوند ((Song et al., 2005; Tong et al., 2014;Mun and Lim, 2015; Lim et al., 2014a, 2014b ). چون دسترسی به یک حافظه‌ی برون تراشه ای، ۱۰ تا ۲۰ برابر بیشتر از دسترسی به یک حافظه‌ی درون تراشه ایزمان نیاز دارد (پاندا و همکاران، ۲۰۰۰)، با پیش‌جستجوی فیلتر بلوم درون تراشه ایدر روش پیشنهادی ما، جدول هشبرون تراشه ایکه نودهای trie را ذخیره می‌کند، تنها زمانی قابل دسترسی است که احتمال بالایی برای تطبیق ورودی، وجود داشته باشد. نسخه‌ی قبلی و خلاصه‌تر این مقاله در لیم و همکاران، ۲۰۱۵ ارائه شده بود.

عملکرد الگوریتم‌های پیشنهادی از طریق شبیه‌سازی، ارزیابی شده است. چون فرمت نام‌های CCN هنوز تعریف نشده است، نام‌های URL که مشخصات سلسله‌مراتبی مشابهی با نام‌های CCN دارند، برای شبیه‌سازی ما مورد استفاده قرار می‌گیرند (ونگ و همکاران، ۲۰۱۱). حافظه‌ی مورد نیاز برای ایجاد یک فیلتر بلوم و ذخیره‌سازی NPT نیز ارزیابی شده است. با استفاده از ورودی‌هایی که ۳ برابر تعداد URLهای ذخیره شده هستند، عملکرد جستجو مورد ارزیابی قرار می‌گیرد.

این مقاله به صورت زیر ساماندهی شده است. بخش ۲، کارهای مرتبط از جمله پیشوند نام trie، الگوریتم‌های قبلی جستجوی نام و تئوری فیلتر بلوم را توصیف می‌کند. بخش ۳، روش های ایجاد و جستجوی الگوریتم‌های پیشنهادی را معرفی می‌نماید. در بخش ۴، نتایج ارزیابی عملکرد نشان داده شده است، و بخش ۵ مربوط به نتیجه‌گیر‌ی‌های مقاله می‌باشد.

عنوان انگلیسی:Name prefix matching using bloom filter pre-searching for content centric network~~en~~

۱ Introduction

Emerging Internet applications such as social network services largely share image, video, and music files. As large and repeatedly requested contents, this traffic is not efficiently transferred in the current Internet, which has a host-based infrastructure. Content centric network (CCN) is a promising next-generation network designed to solve such issues of the current Internet. The CCN is also known as the information centric network (ICN) or named data network (NDN). While the current Internet uses host-to-host communication based on IP addresses, the CCN performs data communication based on content names (Jacobson et al., 2009; Vasilakos et al., 2015; Bari et al., 2012; Xu et al., 2014; Qiao et al., 2015; Wang et al., 2012; Esteve et al., 2008; Perino and Varvello, 2011). In Jacobson et al. (2009), basic CCN features are implemented and the resilience and the performance of CCN architecture are compared with the host-based communication in terms of file transfer, content distribution, and voice calls. Instead of the concept of source hosts or destination hosts, the CCN uses the concept of content generator and content consumer. Content generators produce contents, and content consumers receive and consume the contents. Routers perform routing using content names instead of IP addresses. Unlike conventional routers, CCN routers have an additional role of caching, which stores contents temporarily, and sends them to consumers requesting the contents. In this way, CCN consumers can rapidly acquire the desired contents, and the same contents are not repeatedly transferred over a network. CCN uses two types of packets: Interest and Data. The Interest is broadcasted by a consumer. The Data is produced by a content generator and transmitted by any node hearing the Interest and having the Data. A CCN router has three different tables: Contents Store (CS), Pending Interest Table (PIT), and Forwarding Information Base (FIB). The CS is a cache storing Data packets. The PIT is used to forward Data packets, and the FIB is used to forward Interest packets. For wire-speed packet forwarding, it is essential to have efficient lookup algorithms that perform the longest name matching for every incoming Interest packet. A trie is an ordered tree-based data structure, the name of which originates from the word retrieval. We differentiate the term trie from the tree as follows. In a trie structure, all the descendants of a node have a common prefix of the string associated with that node, while this is not always true in a tree structure. A name prefix trie (NPT) has been proposed as an extended trie for a name lookup (Wang et al., 2011). The NPT provides an intuitive way for the name lookup with the longest name matching, but has an issue in search performance, since an FIB table can have many millions of content names and each content name can be excessively long. The motivation of this paper is to propose a new approach for the longest name matching used in FIB lookups in CCN routers. The proposed approach is based on the name prefix trie. In order to solve the search performance issue of the NPT, we propose to add an on-chip Bloom filter which is queried before the access to the NPT, which is stored in an off-chip hash table. As a space-efficient probabilistic data structure used to test whether an element is a member of a set, Bloom filters have been popularly applied to network algorithms (Song et al., 2005; Tong et al., 2014; Mun and Lim, 2015; Lim et al., 2014a, 2014b). Since an access to an off-chip memory takes 10–۲۰ times longer than an access to an on-chip memory (Panda et al., 2000), by pre-searching the on-chip Bloom filter, the off-chip hash table storing trie nodes is only accessed when there is a high possibility of a matching entry in our proposed approach. The earlier and shorter version of this paper was presented in (Lim et al., 2015). The performance of our proposed algorithms is evaluated through simulation. Since the format of CCN names is not yet defined, URL names that have hierarchical characteristics similar to CCN names are used for our simulation (Wang et al., 2011). Memory requirements for creating a Bloom filter and storing the NPT are also evaluated. Using inputs with 3 times the number of stored URLs, the search performance is also evaluated. This paper is organized as follows. Section 2 describes related works such as the name prefix trie, previous name lookup algorithms, and the Bloom filter theory. Section 3 introduces the building and searching procedures of the proposed algorithms. Section 4 shows the performance evaluation results, and Section 5 concludes the paper.

$$en!!