Skip to main content
SUPERVISOR
Seyed MohammadAli Khosravifard
سیدمحمدعلی خسروی فرد (استاد راهنما)
 
STUDENT
Niloufar Ahmadypour
نیلوفر احمدی پور

FACULTY - DEPARTMENT

دانشکده مهندسی برق و کامپیوتر
DEGREE
Master of Science (MSc)
YEAR
1392

TITLE

Source Coding Based Caching Methods
: Congestion of users’ demands during peak-traffic times forces the link to transfer a large amount of data with a high transmission rate in a short time and to be useless for a long time. This problem causes inefficiency of using the network. One method for overcoming this problem and reducing the transmission rate during the peak hours is "Caching". In this method, when the number of the requests is small, some contents are stored in memories (caches) which have been distributed in the network (Placement phase) and during peak hours will provide part of the users’ requests. In the second phase (Delivery phase), the server receives the demands and sends out a common message to all users, so that they can recover their requested content from this message. The bottle-neck in the placement phase is "the size of the cache memories in the network" and in the delivery phase is "the rate required to serve the requested content". Till now, caching has been studied from different viewpoints. Some studies have been focused on the delivery phase and the others have focused on the placement phase. With the first approach, for fixed cache contents and specified demands, the delivery phase is optimized. These studies are almost similar to the source coding problem with side information. In fact, the message must be coded such that all users can recover their demands by using the coded message and the available information in their own caches (as the side information). Index-coding is the most important achievement with this approach. In the index-coding problem, there are some receivers that have some bits of the other receivers in their cache and try to recover their desired message from the code which is sent by the server. The side information graph indicates the bits which are stored in the cache of each receiver. In another approach, optimization of both phases is considered. These studies are focused on the use of caching in specific applications such as "video on-demand" (VoD). In this thesis, in addition to reviewing the coded caching and decentralized coded caching methods, as the new achievements in this area, the main focus is on the study of index-coding. In particular, the importance of linear index-coding and its relationship with network coding problem is reviewed. The main question that is raised in this study and the author seeks to answer is, if some delay is tolerable such that users can wait for recovering two (or more) consecutive requests together (instead of sequential recovering), can code length be reduced by index-coding of two (or more) side information graphs in a jointly manner? Our observations shows that in some cases a significant code length reduction (approximately 50%) is possible. Specifically, an upper bound on the length of joint index code is derived in the case that union of side information graphs is the complete graph. On the other hand, there are conditions (in terms of side information graphs) that joint index coding does not result in any advantage in comparison with the conventional index coding. Keywords: Coded Caching, Source Coding with Side Information, Index Coding, Joint Index Coding.
تراکم درخواست‌های کاربران در اوج ترافیک، باعث می‌شود لینک متصل به سرور در مدت زمان کوتاهی مجبور به انتقال حجم زیادی داده با نرخ ارسال بالا باشد و مدتی طولانی کم استفاده بماند که این مشکل باعث کاهش بازده شبکه می‌شود. یکی از روش‌های غلبه بر این مشکل و کاهش نرخ ارسال در زمان اوج ترافیک ، استفاده از روش «کشینگ» است. در این روش هنگامی که تعداد در‌خواست‌ها کم است، مقداری از محتواها در حافظه‌هایی که در سراسر شبکه توزیع شده‌اند (کش ‌ها) ذخیره می‌شوند (فاز جانشانی) و در ساعات اوج ترافیک بخشی از درخواست‌‌های کاربران را تامین می‌کنند. در فاز دوم (فاز تحویل) سرور درخواست‌های کاربران را دریافت می‌کند و پیام مشترکی برای همه کاربران ارسال می‌کند، به طوری که همه آن‌ها قادر به بازیابی محتوای درخواستی خود از این پیام باشند. محدودیت اصلی در فازجانشانی «اندازه حافظه‌های درون شبکه» و در فاز تحویل «نرخ ارسال اطلاعات از سرور به کاربران» است. مسئله کشینگ تا کنون با رویکرد‌های مختلفی بررسی شده است. تمرکز برخی مطالعات بر فاز تحویل بوده و بعضی دیگر بر فاز جانشانی متمرکز بوده‌اند. در رویکرد اول با فرض مشخص بودن محتوای حافظه و درخواست‌های کاربران، فاز تحویل بهینه می‌شود. این مطالعات از جنبه‌هایی به مسئله کدینگ منبع با وجود اطلاعات جانبی نزدیک می‌شوند. در ‌واقع پیام مورد نظر سرور باید به نحوی کد شود که کاربران با استفاده از پیام کد شده و اطلاعات موجود در حافظه‌ها (به عنوان اطلاعات جانبی) بتوانند محتوای در‌خواستی خود را استخراج نمایند. ایندکس-کدینگ شاخص‌ترین دستاورد با این رویکرد است. در مسئله ایندکس-کدینگ تعدادی گیرنده وجود دارد که هر کدام برخی بیت‌های مربوط به سایر گیرنده‌ها را در اختیار دارد و در پی استخراج پیام مورد نظر خود از کد ارسال شده از طرف سرور است. این‌که هر گیرنده بیت مربوط به کدام یک از سایر گیرنده‌ها را در اختیار دارد به صورت گرافی موسوم به «گراف اطلاعات جانبی» مدل می‌شود. در رویکردی دیگر بهینه‌سازی هر دو فاز مدنظر است.‌‌ این تحقیقات بیشتر معطوف به استفاده از کشینگ در کاربرد خاص «ویدئو مبتنی بر درخواست» (VoD) هستند. در این پایان‌نامه علاوه بر مرور روش‌های کشینگ کدشده و کشینگ غیر متمرکز که از جمله جدیدترین دستاوردهای این حوزه هستند ، تمرکز اصلی بر مطالعه ایندکس-کدینگ بوده است. به طور خاص اهمیت ایندکس-کدینگ خطی و ارتباط آن با مسئله کدینگ شبکه مرور گردیده است. سوال اصلی که در این تحقیق مطرح گردید و نگارنده در پی پاسخ به آن بوده این است که اگر مقداری تاخیر قابل تحمل باشد ، یعنی کاربران بتوانند آن‌قدر صبر کنند تا دو (یا چند) درخواست متوالی خود را به صورت یک‌جا استخراج کنند (به جای استخراج پی در پی درخواست‌ها)، آیا می‌توان با ایندکس-کدینگ توام دو (یا چند) گراف اطلاعات جانبی به طول کد کمتری رسید؟ مشاهدات حاکی از آن است که در برخی حالات کاهش قابل توجهی حدود 50 درصد در طول کد امکان‌پذیر است ، از سوی دیگر شرایطی هم وجود دارد (از نظر گراف های اطلاعات جانبی) که ایندکس-کدینگ توام هیچ مزیتی نسبت به ایندکس کدینگ مرسوم ندارد . به طور مشخص در این پایان‌نامه یک کران بالا برای طول کد ایندکس-کد توام در حالتی که اجتماع گراف‌ها کامل باشد ارائه گردید.

ارتقاء امنیت وب با وف بومی