کدگذاری خطی شبکه

در شبکه‌های مخابراتی، **کدگذاری خطی شبکه**، یا ساده‌تر،  **کدگذاری شبکه**، یا **کدینگ شبکه**، روشی برای انتقال داده‌هاست که در آن گره‌های میانی شبکه، داده‌ها را با بهره‌گیری از ترکیب‌های خطی آنها، از گره‌های مبدأ به گره‌های مقصد منتقل می‌کنند.

کدگذاری خطی شبکه، برای بهبود گذرداد، کارایی و مقیاس‌پذیری شبکه، یا برای امنیت انتقال داده‌ها با جلوگیری از شنود به‌کار می‌رود. گره‌های شبکه چندین بستۀ داده (data packets) را از مبدأ (و گره‌های پیشین) گرفته و آنها را برای رساندن به مقصد، ترکیب خطی می‌کنند. این فرآیند، بیشتر برای دستیابی به حداکثر نرخ انتقال اطلاعات ممکن در شبکه استفاده می‌شود.

از دیدگاه تئوری، ثابت شده‌است که کدگذاری خطی برای دستیابی به کران بالایی نرخ انتقال داده‌ها در شبکه‌ای با یک مبدأ (منبع داده‌ها) و چند مقصد، کافی است. بااین‌حال، کدگذاری خطی به‌طور کلی برای هر شبکه‌ای کافی نیست؛ حتی با بهره‌گیری از نسخه‌های عمومی‌تر خطی‌بودن، مانند کدگذاری کانولوشنال و کدگذاری بانک فیلتر. یافتن کدگذاری بهینه برای شبکه‌ها و با هر نیاز دلخواه، یک مسئله دشوار است که می‌تواند اِن‌پی سخت و حتی غیرقابل تصمیم‌گیری باشد.

## کدگذاری و کدگشایی
در مسئله کدگذاری خطی شبکه، گروهی از گره‌ها (P)، بسته‌های داده‌ را از گره‌های مبدأ (S) به گره‌های مقصد (K) منتقل می‌کنند. هر گره، بسته‌های جدیدی تولید می‌کند که ترکیبی خطی از بسته‌های دریافت‌شدۀ آن هستند. ضرایب این ترکیب خطی، از یک میدان متناهی - معمولاً GF(2^s) - هستند، که *s*، طول بسته بر حسب بیت است.

هر گرۀ p_k با InDeg(p_k) = S، پیام (بستۀ داده) X_k را تولید می‌کند که ترکیب خطی پیام‌های دریافت‌شده \{M_i\}_{i = 1}^S است: 

: X_k = \sum_{i=1}^S g_k^i\cdot M_i

که g_k^iها، ضرایبی هستند که از GF(2^s) انتخاب شده‌اند. ازآنجاکه این محاسبات در یک میدان متناهی انجام می‌شود، طول پیام تولیدشده و پیام‌های اصلی برابر است. هر گره، X_k محاسبه‌شدۀ را به‌همراه ضرایب g_k^i که در مرحله k^\text{th} استفاده شده‌اند به گره‌های بعدی گسیل می‌کند.

گره‌های مقصد، این پیام‌های کدِشبکه‌شده را دریافت کرده، آنها را در یک ماتریس، گرد می‌آورند. پیام‌های (بسته‌های) اصلی را می‌توان با حذف گاوسی این ماتریس، بازیافت. اگر این ماتریس به‌شکل سطری پلکانی در آید، پیام‌های کدگشایی‌شده، همان ردیف‌های ماتریس، e_i=[0 ... 0 1 0 ... 0]، خواهند بود. 

## پیش‌زمینه
یک شبکه با یک گراف جهت‌دار \mathcal{G}=(V, E, C) نشان داده‌می‌شود؛ V مجموعۀ گره‌ها، E مجموعۀ لینک‌های جهت‌دار (یال‌های گراف)، و C ظرفیت هر لینک است. فرض کنید T(s, t)، گذرداد بیشینه از گره s به گره t باشد. با قضیۀ جریان-بیشینه برش-کمینه ، کران بالای T(s, t)، برابر با کمترین ظرفیت همه برش‌هاست؛ که مجموع ظرفیت‌های یال‌های یک برش میان این دو گره است.

کارل مِنگِر ثابت کرد که در یک شبکه با یک مبدأ و یک مقصد (تک‌پخشی، Unicast)، همیشه مجموعه‌ای از مسیرها با یال‌های متمایز هست که به کران بالای گذرداد شبکه دست می‌یابند. این، همان قضیۀ جریان-بیشینه برش-کمینه است. بعدها، الگوریتم فورد-فولکرسون برای یافتن چنین مسیرهایی پیشنهاد شد که مدت زمان لازم برای اجرای آن، تابعی چندجمله‌ای از شمار گره‌های شبکه است (polynomial time).

اما مسئلۀ شبکۀ دارای چند مبدأ و چند مقصد (چندپخشی، Multicast)، پیچیده‌تر است و در واقع، با استفاده از روش‌های مسیریابی سنتی نمی‌توان به کران بالای گذرداد دست یافت. رودُلف آلس‌وِیده و همکارانش ثابت کردند که اگر در گره‌های میانی، محاسباتی اضافی انجام شوند (بسته‌های دادۀ رسیده به یک گره شبکه،  در یک یا چند بسته خروجی ترکیب شوند)، این کران بالا دست‌یافتنی خواهد بود.

## شبکۀ پروانه‌ای
بندانگشتی| شبکۀ پروانه‌ای.
شبکه پروانه‌ای اغلب برای نشان دادن این‌که چگونه کدگذاری خطی شبکه می‌تواند بهتر از مسیریابی عمل کند، استفاده می‌شود. دو گره منبع (در بالای شکل) دارای پیام‌های A و B هستند که باید به دو گره مقصد (در پایین شکل) منتقل شوند. هر گرۀ مقصد می‌خواهد هر دو پیام  A و B را دریافت کند. هر یال می‌تواند تنها یک پیام را گذر دهد.

اگر تنها مسیریابی، مجاز بود، یال وسطی تنها می‌توانست تنها A یا B (اما نه هر دو) را گذر دهد. فرض کنید که A را از این یال بفرستیم؛ پس گرۀ مقصد چپ، A را دو بار دریافت می‌کند، درحالی‌که B به آن نمی‌رسد. با فرستادن B، مشکل مشابهی برای گرۀ مقصد راست درست می‌شود. بنابراین، مسیریابی به‌تنهایی کافی نیست، زیرا هیچ مسیریابی‌ای نمی‌تواند A و B را همزمان به هر دو گرۀ مقصد برساند. از سوی دیگر، روی‌هم‌رفته چهار بازۀ زمانی طول می‌کشد تا هر دو گرۀ مقصد، A و B را دریافت کنند.

با بهره‌گیری از یک روش کد کردن ساده، همان‌گونه که در شکل نشان داده شده‌است، A و B را می‌توان همزمان با فرستادن مجموع پیام‌ها از راه دو گره میانی و با کد کردن A و B به‌صورت A+B، به هر دو گرۀ مقصد رساند. گرۀ مقصد چپ A و A+B را دریافت می‌کند و سپس می‌تواند B را با کم کردن آن دو از هم به‌دست آورد. گرۀ مقصد راست هم B و A+B را دریافت می‌کند و هر دو A و B را به‌دست می‌آورد. بنابراین، با کدگذاری شبکه، تنها سه بازۀ زمانی طول می‌کشد تا پیام‌ها به هر دو مقصد برسند و گذرداد شبکه هم بهتر شده‌است.

## کدگذاری خطی تصادفی شبکه
کدگذاری خطی تصادفی شبکه (RLNC) یک کدگذاری ساده اما نیرومند است که با بهره‌گیری از یک الگوریتم نامتمرکز، گذرداد کم‌وبیش بهینه را فراهم می‌کند. گره‌ها، ترکیبات خطی بسته‌هایی را که دریافت می‌کنند، با ضرایبی که تصادفی از توزیع احتمال یکنواخت از یک میدان متناهی انتخاب می‌شوند، انتقال می‌دهند. اگر اندازه میدان به‌اندازۀ کافی بزرگ باشد، احتمال اینکه ترکیب‌های مستقل خطی بسته‌ها به گیرنده یا گیرنده‌ها برسند (و بنابراین بتوانند بسته‌ها را ازین ترکیب‌ها استخراج کنند) به 1 نزدیک می شود. بااین‌حال، اگرچه کدگذاری خطی تصادفی شبکه، گذرداد را بیشتر می‌کند، اگر شمار بسته‌های کافی به گیرنده نرسد، بعید است که بتواند هر یک از بسته‌های اصلی را بازیابد. این را می‌توان با فرستادن ترکیبات خطی تصادفی اضافی تاوقتی‌که گیرنده شمار بسته‌های کافی را به دست آورد، حل کرد.

### باورهای نادرست
کدگذاری خطی شبکه، کم‌وبیش یک موضوع جدید است. بااین‌حال، در بیست سال گذشته دربارۀ آن گسترده پژوهش شده‌است. اما هنوز هم برخی تصورات غلط هستند که دیگر نامعتبرند:

**پیچیدگی محاسباتی کدگشایی:** کدگشاهای شبکه در طول این سال‌ها بهبود یافته‌اند. امروزه الگوریتم‌ها بسیار کارآمد و قابل موازی‌سازی هستند. سال 2016، پردازنده‌های Core i5 اینتل با دستورالعمل‌های SIMD، نرخ انتقال داده در کدگشایی شبکه، 750 مگابایت‌برثانیه برای اندازه نسل 16 بسته و 250 مگابایت‌برثانیه برای اندازۀ نسل 64 بسته بود. افزون‌براین، الگوریتم‌های امروزی می‌توانند بسیار قابل موازی‌سازی باشند و نرخ کدگذاری و کدگشایی را حتی بیشتر افزایش دهند. 

**سربار انتقال:** معمولا تصور می‌شود که سربار انتقال در کدگذاری شبکه، به‌سبب نیاز به الحاق ضرایب کدگذاری به هر بسته کدگذاری‌شده زیاد است. در واقع، این سربار در بیشتر کاربردها ناچیز است. سربار در اثر ضرایب کدگذاری را می‌توان چنین محاسبه کرد؛ هر بسته، M ضریب ضمیمه‌شده دارد. اندازه هر ضریب، شمار بیت‌های لازم برای نشان دادن یک عنصر از میدان نامتناهی است. در عمل، بیشتر کدگذاری‌های شبکه، از اندازه نسل کمتر از 32 بسته در هر نسل و میدان‌های نامتناهی 256 عنصری (باینری-8) بهره می‌برند. با این اعداد، هر بسته به M * log_2(s) = 32 بایت سربار نیاز دارد. اگر هر بسته 1500 بایت طول داشته باشد (یعنی اترنت MTU)، آنگاه 32 بایت، تنها 2 درصد  سربار می‌شود.
بندانگشتی|448x448پیکسل| بسته‌های وابسته خطی ممکن در مراحل مختلف انتقال برای یک میدان متناهی <math>GF(2)</math> و اندازه نسل 16 بسته. در آغاز انتقال، وابستگی‌های خطی، کم هستند. آخرین بسته انتقال به احتمال زیاد، وابسته خطی خواهد شد.
بندانگشتی|445x445پیکسل| تعداد بسته‌های وابستۀ خطی ممکن در هر نسل، مستقل از اندازه نسل است.
**سربار در اثر وابستگی‌های خطی:** ازآنجاکه ضرایب کدگذاری در RLNC، تصادفی هستند، احتمال می‌رود که برخی از بسته‌های کدشدۀ ارسال‌شده، به‌درد مقصد نخورند، چراکه از ترکیب بسته‌های وابستۀ خطی تشکیل شده‌اند. اما، این سربار در بیشتر کاربردها ناچیز است. وابستگی‌های خطی به اندازه میدان‌ متناهی بستگی دارد و عملاً مستقل از اندازه نسل به‌کاررفته است.

## کاربردها
پژوهشگران و شرکت‌ها، کدگذاری شبکه را در  کاربردها و محصولاتشان به‌کار گرفته‌اند. می‌توان برخی از کاربردهای کدگذاری شبکه را در حوزه‌های مختلف فهرست کرد.

## همچنین ببینید

* پروتکل اشتراک مخفی
* امضاهای هم‌شکل برای کدگذاری شبکه
* کدگذاری شبکه مثلثی

## منابع

* فراگولی، سی. Le Boudec, J. & Widmer, J. "Coding Network: An Instant Primer" در *Computer Communication Review* ، 2006. https://doi.org/10.1145/1111322.1111337

## لینک‌ها به بیرون

* صفحه اصلی کدگذاری شبکه
* کتابنامه کدگذاری شبکه
* ریموند دبلیو یونگ، نظریه اطلاعات و کدگذاری شبکه، اسپرینگر 2008، http://iest2.ie.cuhk.edu.hk/~whyeung/book2/
* ریموند دبلیو یونگ و همکاران، نظریه کدگذاری شبکه، اکنون ناشران، 2005، http://iest2.ie.cuhk.edu.hk/~whyeung/netcode/monograph.html
* کریستینا فراگولی و همکاران، کدگذاری شبکه: آغازگر فوری، ACM SIGCOMM 2006، http://infoscience.epfl.ch/getfile.py?mode=best&recid=58339 .
* Avalanche Filesystem، http://research.microsoft.com/en-us/projects/avalanche/default.aspx
* کدگذاری شبکه تصادفی، https://web.archive.org/web/20060618083034/http://www.mit.edu/~medard/coding1.htm
* کدهای دیجیتال فواره، http://www.icsi.berkeley.edu/~luby/
* مسیریابی آگاه از کدگذاری، https://web.archive.org/web/20081011124616/http://arena.cse.sc.edu/papers/rocx.secon06.pdf
* MIT دوره آموزشی را ارائه می دهد: مقدمه ای بر برنامه نویسی شبکه
* کدگذاری شبکه: انقلاب بعدی شبکه؟
* طراحی پروتکل کدنویسی برای شبکه های بی سیم: http://scholarcommons.sc.edu/etd/230/
رده:شبکه بی‌سیم حسگر
رده:بازده شبکه
رده:میدان‌های متناهی
رده:نظریه اطلاعات
رده:نظریه کدگذاری