موضوع مقاله: کدگذاری خطی شبکه | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # کدگذاری خطی شبکه | مقدمه: در شبکه‌های مخابراتی، کدگذاری خطی شبکه، یا ساده‌تر، کدگذاری شبکه، یا کدینگ شبکه، روشی برای انتقال داده‌هاست که در آن گره‌های میانی شبکه، داده‌ها را با بهره‌گیری از ترکیب‌های خطی آنها، از گره‌های مبدأ به گره‌های مقصد منتقل می‌کنند. | ## بخش 1: کدگذاری خطی شبکه | کدگذاری خطی شبکه، برای بهبود گذرداد، کارایی و مقیاس‌پذیری شبکه، یا برای امنیت انتقال داده‌ها با جلوگیری از شنود به‌کار می‌رود. این فرآیند، بیشتر برای دستیابی به حداکثر نرخ انتقال اطلاعات ممکن در شبکه استفاده می‌شود. از دیدگاه تئوری، ثابت شده‌است که کدگذاری خطی برای دستیابی به کران بالایی نرخ انتقال داده‌ها در شبکه‌ای با یک مبدأ (منبع داده‌ها) و چند مقصد، کافی است.S. 371–381, 2003 بااین‌حال، کدگذاری خطی به‌طور کلی برای هر شبکه‌ای کافی نیست؛ حتی با بهره‌گیری از نسخه‌های عمومی‌تر خطی‌بودن، مانند کدگذاری کانولوشنال و کدگذاری بانک فیلتر.R. کدگذاری و کدگشایی در مسئله کدگذاری خطی شبکه، گروهی از گره‌ها ، بسته‌های داده‌ را از گره‌های مبدأ به گره‌های مقصد منتقل می‌کنند. هر گره، بسته‌های جدیدی تولید می‌کند که ترکیبی خطی از بسته‌های دریافت‌شدۀ آن هستند. ضرایب این ترکیب خطی، از یک میدان متناهی - معمولاً - هستند، که s، طول بسته بر حسب بیت است. هر گرۀ با ، پیام (بستۀ داده) را تولید می‌کند که ترکیب خطی پیام‌های دریافت‌شده است: که ها، ضرایبی هستند که از انتخاب شده‌اند. ازآنجاکه این محاسبات در یک میدان متناهی انجام می‌شود، طول پیام تولیدشده و پیام‌های اصلی برابر است. هر گره، محاسبه‌شدۀ را به‌همراه ضرایب که در مرحله استفاده شده‌اند به گره‌های بعدی گسیل می‌کند. گره‌های مقصد، این پیام‌های کدِشبکه‌شده را دریافت کرده، آنها را در یک ماتریس، گرد می‌آورند. اگر این ماتریس به‌شکل سطری پلکانی در آید، پیام‌های کدگشایی‌شده، همان ردیف‌های ماتریس، ، خواهند بود. پیش‌زمینه یک شبکه با یک گراف جهت‌دار نشان داده‌می‌شود؛ مجموعۀ گره‌ها، مجموعۀ لینک‌های جهت‌دار (یال‌های گراف)، و ظرفیت هر لینک است. با قضیۀ جریان-بیشینه برش-کمینه ، کران بالای ، برابر با کمترین ظرفیت همه برش‌هاست؛ که مجموع ظرفیت‌های یال‌های یک برش میان این دو گره است. | ## بخش 2: کدگذاری خطی شبکه | کارل مِنگِر ثابت کرد که در یک شبکه با یک مبدأ و یک مقصد (تک‌پخشی، Unicast)، همیشه مجموعه‌ای از مسیرها با یال‌های متمایز هست که به کران بالای گذرداد شبکه دست می‌یابند. اما مسئلۀ شبکۀ دارای چند مبدأ و چند مقصد (چندپخشی، Multicast)، پیچیده‌تر است و در واقع، با استفاده از روش‌های مسیریابی سنتی نمی‌توان به کران بالای گذرداد دست یافت. رودُلف آلس‌وِیده و همکارانش ثابت کردند که اگر در گره‌های میانی، محاسباتی اضافی انجام شوند (بسته‌های دادۀ رسیده به یک گره شبکه، در یک یا چند بسته خروجی ترکیب شوند)، این کران بالا دست‌یافتنی خواهد بود. اغلب برای نشان دادن این‌که چگونه کدگذاری خطی شبکه می‌تواند بهتر از مسیریابی عمل کند، استفاده می‌شود. دو گره منبع (در بالای شکل) دارای پیام‌های A و B هستند که باید به دو گره مقصد (در پایین شکل) منتقل شوند. اگر تنها مسیریابی، مجاز بود، یال وسطی تنها می‌توانست تنها A یا B (اما نه هر دو) را گذر دهد. فرض کنید که A را از این یال بفرستیم؛ پس گرۀ مقصد چپ، A را دو بار دریافت می‌کند، درحالی‌که B به آن نمی‌رسد. بنابراین، مسیریابی به‌تنهایی کافی نیست، زیرا هیچ مسیریابی‌ای نمی‌تواند A و B را همزمان به هر دو گرۀ مقصد برساند. از سوی دیگر، روی‌هم‌رفته چهار بازۀ زمانی طول می‌کشد تا هر دو گرۀ مقصد، A و B را دریافت کنند. با بهره‌گیری از یک روش کد کردن ساده، همان‌گونه که در شکل نشان داده شده‌است، A و B را می‌توان همزمان با فرستادن مجموع پیام‌ها از راه دو گره میانی و با کد کردن A و B به‌صورت A+B، به هر دو گرۀ مقصد رساند. گرۀ مقصد چپ A و A+B را دریافت می‌کند و سپس می‌تواند B را با کم کردن آن دو از هم به‌دست آورد. بنابراین، با کدگذاری شبکه، تنها سه بازۀ زمانی طول می‌کشد تا پیام‌ها به هر دو مقصد برسند و گذرداد شبکه هم بهتر شده‌است. کدگذاری خطی تصادفی شبکه کدگذاری خطی تصادفی شبکه (RLNC) یک کدگذاری ساده اما نیرومند است که با بهره‌گیری از یک الگوریتم نامتمرکز، گذرداد کم‌وبیش بهینه را فراهم می‌کند. گره‌ها، ترکیبات خطی بسته‌هایی را که دریافت می‌کنند، با ضرایبی که تصادفی از توزیع احتمال یکنواخت از یک میدان متناهی انتخاب می‌شوند، انتقال می‌دهند. | ## بخش 3: کدگذاری خطی شبکه | اگر اندازه میدان به‌اندازۀ کافی بزرگ باشد، احتمال اینکه ترکیب‌های مستقل خطی بسته‌ها به گیرنده یا گیرنده‌ها برسند (و بنابراین بتوانند بسته‌ها را ازین ترکیب‌ها استخراج کنند) به 1 نزدیک می شود. بااین‌حال، اگرچه کدگذاری خطی تصادفی شبکه، گذرداد را بیشتر می‌کند، اگر شمار بسته‌های کافی به گیرنده نرسد، بعید است که بتواند هر یک از بسته‌های اصلی را بازیابد. این را می‌توان با فرستادن ترکیبات خطی تصادفی اضافی تاوقتی‌که گیرنده شمار بسته‌های کافی را به دست آورد، حل کرد. اما هنوز هم برخی تصورات غلط هستند که دیگر نامعتبرند: پیچیدگی محاسباتی کدگشایی: کدگشاهای شبکه در طول این سال‌ها بهبود یافته‌اند. سال 2016، پردازنده‌های Core i5 اینتل با دستورالعمل‌های SIMD، نرخ انتقال داده در کدگشایی شبکه، 750 مگابایت‌برثانیه برای اندازه نسل 16 بسته و 250 مگابایت‌برثانیه برای اندازۀ نسل 64 بسته بود. افزون‌براین، الگوریتم‌های امروزی می‌توانند بسیار قابل موازی‌سازی باشند و نرخ کدگذاری و کدگشایی را حتی بیشتر افزایش دهند. سربار انتقال: معمولا تصور می‌شود که سربار انتقال در کدگذاری شبکه، به‌سبب نیاز به الحاق ضرایب کدگذاری به هر بسته کدگذاری‌شده زیاد است. سربار در اثر ضرایب کدگذاری را می‌توان چنین محاسبه کرد؛ هر بسته، ضریب ضمیمه‌شده دارد. در عمل، بیشتر کدگذاری‌های شبکه، از اندازه نسل کمتر از 32 بسته در هر نسل و میدان‌های نامتناهی 256 عنصری (باینری-8) بهره می‌برند. اگر هر بسته 1500 بایت طول داشته باشد (یعنی اترنت MTU)، آنگاه 32 بایت، تنها 2 درصد سربار می‌شود. سربار در اثر وابستگی‌های خطی: ازآنجاکه ضرایب کدگذاری در RLNC، تصادفی هستند، احتمال می‌رود که برخی از بسته‌های کدشدۀ ارسال‌شده، به‌درد مقصد نخورند، چراکه از ترکیب بسته‌های وابستۀ خطی تشکیل شده‌اند. وابستگی‌های خطی به اندازه میدان‌ متناهی بستگی دارد و عملاً مستقل از اندازه نسل به‌کاررفته است. کاربردها پژوهشگران و شرکت‌ها، کدگذاری شبکه را در کاربردها و محصولاتشان به‌کار گرفته‌اند. | ## جمع‌بندی | لینک‌ها به بیرون صفحه اصلی کدگذاری شبکه کتابنامه کدگذاری شبکه ریموند دبلیو یونگ، نظریه اطلاعات و کدگذاری شبکه، اسپرینگر 2008، ریموند دبلیو یونگ و همکاران، نظریه کدگذاری شبکه، اکنون ناشران، 2005، کریستینا فراگولی و همکاران، کدگذاری شبکه: آغازگر فوری، ACM SIGCOMM 2006، .