حداقل چارچوب مدیریت هزینه کش برای شبکه های اطلاعات محور با برنامه نویسی شبکه / A minimum cost cache management framework for information-centric networks with network coding

حداقل چارچوب مدیریت هزینه کش برای شبکه های اطلاعات محور با برنامه نویسی شبکه A minimum cost cache management framework for information-centric networks with network coding

  • نوع فایل : کتاب
  • زبان : فارسی
  • ناشر : الزویر Elsevier
  • چاپ و سال / کشور: 2016

توضیحات

رشته های مرتبط: مهندسی کامپیوتر و مهندسی فناوری اطلاعات، شبکه های کامپیوتری، برنامه نویسی کامپیوتر و معماری سیستم های کامپیوتری
۱٫ مقدمه در دهه گذشته، محتوای چند رسانه ای ترافیک غالب اینترنت شده است [۲-۴]. افزایش تقاضا برای محتوای غنی از رسانه ها، مستلزم روش های کارآمدتر برای بازیابی محتوا است. برای این منظور، شبکه اطلاعاتی محور (ICN) یک رویکرد امیدوار کننده طراحی است که این تقاضا را با ارائه دسترسی محتوا به نام و امکان ذخیره در شبکه در اختیار قرار می دهد [۵،۶]. در ICN ها، یک روتر محتوا (CR) با قابلیت ذخیره در شبکه می تواند برخی از (معمولا محبوبیت) تکه های داده را برای دسترسی را وساطت کند [۷]. ذخیره سازی در شبکه می تواند تاخیر بازیابی محتوا، ترافیک شبکه و بار سرویس بر روی سرورها را تا حد زیادی کاهش دهد [۸،۹] . برای مدیریت مخازن در شبکه در ICN، دو مساله مهم باید بصورت مشترک مورد توجه قرار گیرد. یکی استراتژی ذخیره سازی است که تعیین می کند که چه مقدار از داده ها باید در هر CR ذخیره شود، و دیگری مسیریابی محتوا است که تعیین می کند کجا برای مسیریابی محتوا لازم است و نحوه ارائه مطالب چگونه است. در متون، دو نوع استراتژی ذخیره سازی وجود دارد: غیر تعاونی و تعاونی. در استراتژی های ذخیره سازی غیر تعاونی، CR به طور تصادفی داده های دریافتی را ذخیره می کند، که ممکن است منجر به به روز رسانی حافظه پنهان مکرر، تخصیص حافظه پنهان غیرقابل کپی و کپی مجدد شود [۸]. در استراتژی های ذخیره سازی تعاونی، یک CR می تواند با CR های همسایه خود همکاری کند تا تعیین کند که کدام مجموعه داده ها برای حافظه پنهان است [۹-۱۲]. برای مسیریابی محتوا، دو روش مختلف برای استفاده از مخازن در شبکه وجود دارد. یکی از اینها فقط استفاده از حافظه های ذخیره شده در مسیر سرور اصلی محتوا برای آن درخواست است و دیگری استفاده از تمام مخازن ذخیره سازی نزدیک است. اولی نیازمند هیچ نوع همکاری بین CRها نیست اما ممکن است بصورت بالقوه تاخیر بازیابی محتوایی بیشتری را نشان دهد. دومی نیازمند همکاری میان CR ها برای ارسال درخواست به نزدیک ترین حافظه خارج از مسیر است [۱۳]. هر دو حالت با ذخیره محتوا ارتباط نزدیکی دارند. در این مقاله، ما بر روی استراتژی ذخیره سازی همکاری و مسیریابی محتوا تمرکز خواهیم کرد تا تمام مخازن توزیع شده در شبکه را به طور کامل استفاده کنیم. برای فعال کردن همکاری در میان CR های توزیع شده، برای جمع آوری اطلاعات مربوط به همکاری (به عنوان مثال، نرخ درخواست و وضعیت فعلی کش)، یک چارچوب مدیریت کش لازم است و تصمیم گیری های ذخیره سازی و مسیریابی را می گیرند. نرم افزار تعریف شبکه بندی (SDN)، که از نظر فیزیکی کنترل کننده هواپیما و هواپیما داده را جدا می کند، می تواند این نیاز را برآورده کند [۱۴،۱۵]. به طور معمول، در کنترل هواپیما، یک کنترل کننده مسئول جمع آوری اطلاعات شبکه و تصمیم گیری مسیریابی است که در روتر ها پیکربندی می شود. در هواپیما داده، روترها بسته های روبرو را با توجه به تنظیمات جریان توسط کنترل کننده تنظیم می کنند. طی چند سال گذشته، بسیاری از کنترل کننده های جدید با استفاده از سرورهای چند هسته ای قدرتمند برای رسیدگی به تعداد زیادی جریان داده در شبکه های بزرگ طراحی شده اند. به عنوان مثال، McNettle [16] می تواند حدود ۲۰ میلیون درخواست در هر ثانیه را برای یک شبکه با ۵۰۰۰ سوئیچ مدیریت کند. به تازگی، مطالعات مقدماتی برای امکان مدیریت کش در ICN ها براساس SDN انجام شده است [۱۷،۱۸]. با این حال، این مطالعات عمدتا بر چگونگی ادغام عملیات مرتبط با حافظه پنهان در معماری SDN موجود متمرکز شده و در مورد استراتژی ذخیره سازی واقعی بحث نمی کنند. در این مقاله، برای مطالعه استراتژی ذخیره سازی و مسیریابی محتوا ICN ها بر اساس SDN با هدف به حداقل رساندن پهنای باند شبکه و هزینه کش یک گام به جلو بر می داریم، که کل هزینه پهنای باند و مصرف حافظه پنهان در کل شبکه است. به طور خاص، ما برنامه نویسی خطی شبکه (LNC) را برای بهینه سازی مشترک استراتژی ذخیره سازی و مسیریابی محتوا برای به حداقل رساندن پهنای باند شبکه و هزینه کش بکار می بریم. ما از نمونه ای که در شکل ۱ نشان داده شده است برای نشان دادن مزایای استفاده از ذخیره سازی و LNC در ICN ها استفاده می کنیم. در این شکل، یک شبکه شامل هشت روتر (v 1 -v 8) و دو سرور (s 1 و s 2) است. کاربران همه به روترهای v1، v5 و v6 متصل می شوند و یک تکه محتوا را به عنوان f 1، که شامل دو تکه داده ای با اندازه یکسان، A و B است، درخواست می کنند. ما فرض می کنیم که هر لینک یک هزینه واحد برای ارسال یک تکه داده است و یک روتر یک هزینه واحد برای ذخیره یک تکه داده دارد. از لحاظ هزینه کل، یعنی مجموع هزینه پهنای باند و هزینه کش، ما در سه سناریوی تحویل محتوا مختلف، موارد زیر را داریم: • در شکل ۱ (a) سناریوی پایه ای را بدون کش در شبکه بررسی می کنیم، بنابراین بهترین راه برای به دست آوردن محتوای تعیین شده، استفاده از چندپخشی است که هفت پیوند در مسیریابی استفاده می شود.در این مورد، مخزن ذخیره شده در شبکه وجود ندارد. برای هر تکه داده، ۷ پیوند استفاده می شود و هر لینک دارای ظرفیت واحد است. بنابراین، برای انتقال دو قطعه داده، هزینه حافظه کش ۰ و هزینه پهنای باند ۲ × ۷ = ۱۴ است. هزینه کل ۱۴= ۱۴ + ۰ است. • در شکل ۱ (b)، ما فرض می کنیم که چهار CR (v 2، v 4، v 7 و v 8) وجود دارد و هر یک از آنها می توانند تنها یک تکه داده را ذخیره کنند. در این سناریو، ICN را بدون LNC در نظر می گیریم، بنابراین هر CR می تواند یک تکه داده اولیه را ذخیره کند. شکل ۱ (b) استراتژی ذخیره سازی بهینه و مسیریابی محتوا را نشان می دهد، که در آن نماد پررنگ نشان داده شده در هر CR نشان دهنده داده های تکه ای ذخیره شده در CR است. در این حالت، مجموع ۴ تکرار داده در CR ها ذخیره می شود، و انتقال دو تکه داده نیاز به ۷ واحد مصرف پهنای باند دارد. بنابراین، برای انتقال دو قطعه داده، هزینه ذخیره سازی ۴ است و هزینه پهنای باند ۷ است. هزینه کل ۴ + ۷ = ۱۱ است، که نشان دهنده پیشرفت ۲۱٫۴۲ درصدی است. • شکل ۱ (c) سناریو را با مدیریت کش بهینه در ICN ها با LNC نشان می دهد. در این مورد، CR ها می توانند ترکیب خطی داده های اصلی را ذخیره کنند؛ و برای بازیابی داده های اصلی داده های A و B، کاربر فقط باید هر دو تکه داده های مستقل خطی مستقل را بدست آورد. با راه حل مطلوب، هر روتر (i.e.، v1، v5 و v6) می تواند دو تکه داده های کد شده را از دو تا از نزدیکترین CR ها به آنها دانلود کند، بنابراین CR فقط نیاز به ذخیره ۳ تکه داده دارد و هزینه پهنای باند ۶ واحد است. بنابراین، هزینه کل برابر ۳ + ۶ = ۹ در مقایسه با بهترین راه حل در سناریو ۱ است، راه حل بهینه برای سناریو ۳ به افزایش ۳۵٫۷۱% می رسد؛ و در مقایسه با بهترین راه حل در سناریو ۲، به افزایش ۱۸٫۱۸% می رسد. مثال بالا مزیت مشترک در نظر گرفتن استراتژی ذخیره سازی در شبکه و مسیریابی محتوا با LNC در ICN ها، را نشان می دهد که کار این مقاله را پیش می برد. مفاد اصلی این مقاله به شرح زیر خلاصه شده است. • ما یک چارچوب جدید مبتنی بر SDN را برای تسهیل در پیاده سازی استراتژی ذخیره سازی و مسیر محتوا در ICN ها با LNC پیشنهاد می کنیم. چارچوب مبتنی بر مفهوم در حال ظهور SDN است، که در آن یک کنترل کننده مسئول تعیین استراتژی ذخیره سازی بهینه و همچنین مسیریابی محتوای بهینه از طریق LNC است. • ما یک مشکل مدیریت بهینه حافظه پنهان برای ICN ها را با LNC تحت یک استراتژی کش به عنوان یک مسئله برنامه نویسی خطی صحیح (ILP) تشکیل می دهیم. بر اساس این ILP پایه، ما فرموله سازی ILP را به منظور کاهش هزینه کل پهنای باند شبکه و هزینه ذخیره سازی به صورت مشترک با توجه به استراتژی ذخیره سازی و مسیر محتوا محاسبه می کنیم. • ما یک الگوریتم مدیریت رمزنگاری مبتنی بر کدگذاری شبکه (NCCM) را برای رسیدن به یک راه حل مدیریت نزدیک به مطلوب به کار می بریم. بر اساس آرامش لاگرانژی، مشکل فرموله شده را می توان کم کرد و سپس به یک مسئله برنامه ریزی خطی و چندین مسئله ساده بزرگ شدن وزن با عدد صحیح ساده، که می تواند به طور مطلوب در طی زمان چندجمله ای حل شود، تجزیه می شود. • ما انجام آزمایش های گسترده ای را برای مقایسه عملکرد الگوریتم NCCM پیشنهادی با حد پایین فرموله سازی ILP انجام می دهیم. ما همچنین عملکرد الگوریتم NCCM پیشنهاد شده را با سه حد بالایی از مشکل مقایسه می کنیم، یعنی بدون کش (بدون حافظه کش)، حافظه تصادفی (r-Cache) و کش های حریص (g-Cache). نتایج شبیه سازی اثربخشی الگوریتم NCCM پیشنهادی و چارچوب را اثبات می کند. بقیه مقاله به شرح زیر است: ما درباره کار مرتبط در بخش ۲ بحث می کنیم. در بخش ۳، یک چارچوب مدیریت کل کش برای ICN ها را بر اساس SDN معرفی می کنیم. سپس ما مشکل مدیریت بهینه حافظه پنهان برای ICN ها با LNC را مطرح می کنیم که هدف آن کاهش پهنای باند شبکه و هزینه ذخیره با استفاده از مخازن در شبکه و LNC در بخش ۴ می باشد. برای حل مشکل در عمل، در بخش ۵، ما یک الگوریتم کارآمد را بر اساس کاهش لاگرانژی طراحی می کنیم. سپس تجربه های گسترده ای را برای نشان دادن عملکرد چارچوب مان در بخش ۶ انجام می دهیم. در نهایت در مورد کاربرد طرح پیشنهادی در بخش ۷ بحث خواهیم کرد و مقاله را در بخش ۸ به پایان می رسانیم.

Description

In the past decade, multimedia content has become the dominating traffic over the Internet [2–۴]. The increasing demand for media-rich content calls for more efficient methods for content retrieval. To this end, Information-centric network (ICN) is a promising design approach that fulfills such a demand by introducing content access by name and enabling in-network caching [5,6]. In ICNs, a content router (CR) with in-network caching capability can buffer some (usually popular) data chunks for future access [7]. Innetwork caching can greatly reduce the retrieval delay of content, the traffic in the network, and the service load on the servers [8,9]. To manage in-network caches in ICNs, two major issues need to be jointly considered. One is the caching strategy that determines which data chunks shall be cached at each CR, and the other is content routing that determines where to route content requests and how to deliver content. In the literature, there are two types of caching strategies: noncooperative and cooperative. In non-cooperative caching strategies, a CR opportunistically caches the received data, which may lead to frequent cache updates, sub-optimal cache allocation and caching duplication [8]. In cooperative caching strategies, a CR can collaborate with its neighboring CRs to determine which set of data chunks to cache [9–۱۲]. For content routing, there are two different ways to utilize the in-network caches. One is to only use caches along the path to the original content server for that request and the other is to utilize all nearby caches. The former does not require any cooperation among CRs but may exhibit potentially longer content retrieval delay. The latter requires cooperation among CRs to forward the request to the nearest off-path caches [13]. Either way is closely coupled with content caching. In this paper, we will focus on cohoperative caching strategy and content routing to fully utilize all distributed in-network caches. To enable cooperation among distributed CRs, a cache management framework is needed to collect cooperation-related information (e.g., request rates and the current cache status) and make caching and routing decisions. Software defined networking (SDN), which physically decouples the control plane and data plane, can satisfy this requirement [14,15]. Typically, on the control plane, a controller is responsible for collecting network information and making routing decisions that will be configured at routers. On the data plane, routers forward packets according to the flow tables configured by the controller. Over the past few years, many new controllers have been designed by using powerful multicore servers to handle a large number of data flows in big networks. For example, McNettle [16] can manage around 20 million requests per second for a network with 5000 switches. Recently, preliminary studies have been conducted to enable cache management in ICNs based on SDN [17,18]. However, these studies mainly focused on how to incorporate cache related operations into the existing SDN architecture and did not discuss the actual caching strategy. In this paper, we will go one step further to study caching strategy and content routing of ICNs based on SDN with the aim of minimizing both the network bandwidth and cache cost, which is the total cost of bandwidth and cache consumption in the whole network. Specifically, we will employ linear network coding (LNC) to jointly optimize caching strategy and content routing to minimize the network bandwidth and cache cost. We use an example shown in Fig. 1 to illustrate the benefits of using caching and LNC in ICNs. In this figure, a network consists of eight routers (v1–v8), and two servers (s1 and s2). The users are all connected to routers v1, v5, and v6 and request a piece of content, denoted as f1, that contains two equal-sized data chunks, A and B. We assume that each link has a unit cost to transmit one data chunk and a router has a unit cost to cache one data chunk. In terms of the total cost, i.e., the sum of bandwidth cost and cache cost, we have the following results in three different content delivery scenarios: • In Fig. 1(a), we consider a basic scenario with no in-network cache, so the best way to obtain the designated content is by utilizing multicast with which seven links are used in the routing tree. In this case, there is non in-network cache used. For each data chunk, 7 links will be used and each link has unit capacity. Therefore, to transmit two data chunks, the cache cost is 0 and the bandwidth cost is 2 × ۷ =۱۴٫ The total cost is 0 + 14 =14. • In Fig. 1(b), we further assume that there are four CRs (v2, v4, v7 and v8) and each of them can cache only one data chunk. In this scenario, we consider an ICN without LNC, so each CR can cache one original data chunk. Fig. 1(b) shows the optimal caching strategy and content routing, in which the bold symbol shown on each CR denotes the data chunk cached at the CR. In this case, a total of 4 data chunks are cached in CRs, and transmitting the two data chunks requires 7 units of bandwidth consumption. Therefore, to transmit two data chunks, the cache cost is 4 and the bandwidth cost is 7. The total cost is 4 + 7 =11, representing a 21.42% improvement. • Fig. 1(c) shows the scenario with the optimal cache management in ICNs with LNC. In this case, the CRs can cache the linear combination of the original data chunks; and to recover the original data chunks A and B, a user only needs to obtain any two linearly independent coded data chunks. With the optimal solution, each router (i.e., v1, v5 and v6) can download two coded data chunks from its two nearest CRs, thus CRs only need to cache 3 data chunks and the bandwidth cost is 6 units. Therefore, the total cost is 3 + 6 =9. Compared to the best solution in Scenario 1, the optimal solution for scenario 3 achieves a 35.71% improvement; and compared to the best solution in Scenario 2, it achieves 18.18% improvement. The above example demonstrates the advantage of jointly considering in-network caching strategy and content routing with LNC in ICNs, which motivates the work of this paper. The main contributions of this paper are summarized as follows. • We propose a novel SDN-based framework to facilitate the implementation of caching strategy and content routing in ICNs with LNC. The framework is based on the emerging concept of SDN, in which a controller is responsible for determining the optimal caching strategy as well as the optimal content routing via LNC. • We formulate an optimal cache management problem for ICNs with LNC under a given cache strategy as an integer linear programming (ILP) problem. Based on this basic ILP, we further develop the ILP formulation to minimize the total network bandwidth cost and cache cost by jointly considering caching strategy and content routing. • We develop an efficient network coding based cache management (NCCM) algorithm to obtain a near-optimal cache management solution. Based on Lagrangian relaxation, the formulated problem can be relaxed and then decomposed into a linear programming problem and several simple integer maximum weight placement problems, all of which can be solved optimally within polynomial time. • We conduct extensive experiments to compare the performance of the proposed NCCM algorithm with the lower bound of the ILP formulation. We also compare the performance of the proposed NCCM algorithm with three upper bounds of the problem, i.e., no cache (no-Cache), random cache (r-Cache) and greedy cache (g-Cache) strategies. Simulation results validate the effectiveness of the proposed NCCM algorithm and the framework. The rest of the paper is organized as follows. We discuss related work in Section 2. In Section 3, we introduce a general cache management framework for ICNs based on SDN. Next, we formulate the optimal cache management problem for ICNs with LNC, which aims to minimize the network bandwidth cost and cache cost by exploiting in-network caches and LNC in Section 4. To solve the problem in practice, in Section 5, we design an efficient algorithm based on Lagrangian relaxation. We then conduct extensive experiments to illustrate the performance of our framework in Section 6. Finally, we discuss the applicability of the proposed scheme in Section 7, and we conclude the paper in Section 8.
اگر شما نسبت به این اثر یا عنوان محق هستید، لطفا از طریق "بخش تماس با ما" با ما تماس بگیرید و برای اطلاعات بیشتر، صفحه قوانین و مقررات را مطالعه نمایید.

دیدگاه کاربران


لطفا در این قسمت فقط نظر شخصی در مورد این عنوان را وارد نمایید و در صورتیکه مشکلی با دانلود یا استفاده از این فایل دارید در صفحه کاربری تیکت ثبت کنید.

بارگزاری