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

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

کدگذاری خطی شبکه، برای بهبود گذرداد، کارایی و مقیاس‌پذیری شبکه، یا برای امنیت انتقال داده‌ها با جلوگیری از شنود به‌کار می‌رود. گره‌های شبکه چندین بستۀ داده (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...010...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 درصد سربار می‌شود.

بسته‌های وابسته خطی ممکن در مراحل مختلف انتقال برای یک میدان متناهی

GF(2)

و اندازه نسل 16 بسته. در آغاز انتقال، وابستگی‌های خطی، کم هستند. آخرین بسته انتقال به احتمال زیاد، وابسته خطی خواهد شد.

تعداد بسته‌های وابستۀ خطی ممکن در هر نسل، مستقل از اندازه نسل است.

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

کاربردها

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

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

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

منابع

↑ S. Li, R. Yeung, and N. Cai, "Linear Network Coding"(PDF), in IEEE Transactions on Information Theory, Vol 49, No. 2, pp. 371–381, 2003
↑ R. Dougherty, C. Freiling, and K. Zeger, "Insufficiency of Linear Coding in Network Information Flow" (PDF), in IEEE Transactions on Information Theory, Vol. 51, No. 8, pp. 2745-2759, August 2005 ( erratum)
↑ Langberg, M.; Sprintson, A.; Bruck, J. (2006). "The encoding complexity of network coding". IEEE Transactions on Information Theory. 52 (6): 2386–2397. doi:10.1109/TIT.2006.874434.
↑ Li, C. T. (2023). "Undecidability of Network Coding, Conditional Information Inequalities, and Conditional Independence Implication". IEEE Transactions on Information Theory. 69 (6): 1. arXiv:2205.11461. doi:10.1109/TIT.2023.3247570.
↑ Kühne, L.; Yashfe, G. (2022). "Representability of Matroids by c-Arrangements is Undecidable". Israel Journal of Mathematics. 252: 95–147. arXiv:1912.06123. doi:10.1007/s11856-022-2345-z.
↑ Chou, Philip A.; Wu, Yunnan; Jain, Kamal (October 2003), "Practical network coding", Allerton Conference on Communication, Control, and Computing, Any receiver can then recover the source vectors using Gaussian elimination on the vectors in its h (or more) received packets.
↑ ^۷٫۰ ^۷٫۱ Ahlswede, Rudolf; N. Cai; S.-Y. R. Li; R. W. Yeung (2000). "Network Information Flow". IEEE Transactions on Information Theory. 46 (4): 1204–1216. CiteSeerX 10.1.1.722.1409. doi:10.1109/18.850663. خطای یادکرد: برچسب <ref> نامعتبر؛ نام «Ahlswede2000» چندین بار با محتوای متفاوت تعریف شده است. (صفحهٔ راهنما را مطالعه کنید.).
↑ Wunderlich, Simon; Cabrera, Juan A.; Fitzek, Frank H. P.; Reisslein, Martin (August 2017). "Network Coding in Heterogeneous Multicore IoT Nodes With DAG Scheduling of Parallel Matrix Block Operations" (PDF). IEEE Internet of Things Journal. 4 (4): 917–933. doi:10.1109/JIOT.2017.2703813. ISSN 2327-4662. Archived from the original (PDF) on 8 Apr 2022.
↑ "Coding the Network: Next Generation Coding for Flexible Network Operation | IEEE Communications Society". www.comsoc.org. Retrieved 2022-06-06.

فراگولی، سی. 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/

[1] S. Li, R. Yeung, and N. Cai, "Linear Network Coding"(PDF), in IEEE Transactions on Information Theory, Vol 49, No. 2, pp. 371–381, 2003

[2] R. Dougherty, C. Freiling, and K. Zeger, "Insufficiency of Linear Coding in Network Information Flow" (PDF), in IEEE Transactions on Information Theory, Vol. 51, No. 8, pp. 2745-2759, August 2005 ( erratum)

[langberg_nc-3] Langberg, M.; Sprintson, A.; Bruck, J. (2006). "The encoding complexity of network coding". IEEE Transactions on Information Theory. 52 (6): 2386–2397. doi:10.1109/TIT.2006.874434.

[li_nc-4] Li, C. T. (2023). "Undecidability of Network Coding, Conditional Information Inequalities, and Conditional Independence Implication". IEEE Transactions on Information Theory. 69 (6): 1. arXiv:2205.11461. doi:10.1109/TIT.2023.3247570.

[kuhne_matroid-5] Kühne, L.; Yashfe, G. (2022). "Representability of Matroids by c-Arrangements is Undecidable". Israel Journal of Mathematics. 252: 95–147. arXiv:1912.06123. doi:10.1007/s11856-022-2345-z.

[6] Chou, Philip A.; Wu, Yunnan; Jain, Kamal (October 2003), "Practical network coding", Allerton Conference on Communication, Control, and Computing, Any receiver can then recover the source vectors using Gaussian elimination on the vectors in its h (or more) received packets.

[Ahlswede2000-7] ۷٫۰ ^۷٫۱ Ahlswede, Rudolf; N. Cai; S.-Y. R. Li; R. W. Yeung (2000). "Network Information Flow". IEEE Transactions on Information Theory. 46 (4): 1204–1216. CiteSeerX 10.1.1.722.1409. doi:10.1109/18.850663. خطای یادکرد: برچسب <ref> نامعتبر؛ نام «Ahlswede2000» چندین بار با محتوای متفاوت تعریف شده است. (صفحهٔ راهنما را مطالعه کنید.).

[8] Wunderlich, Simon; Cabrera, Juan A.; Fitzek, Frank H. P.; Reisslein, Martin (August 2017). "Network Coding in Heterogeneous Multicore IoT Nodes With DAG Scheduling of Parallel Matrix Block Operations" (PDF). IEEE Internet of Things Journal. 4 (4): 917–933. doi:10.1109/JIOT.2017.2703813. ISSN 2327-4662. Archived from the original (PDF) on 8 Apr 2022.

[9] "Coding the Network: Next Generation Coding for Flexible Network Operation | IEEE Communications Society". www.comsoc.org. Retrieved 2022-06-06.

[۱]

[۲]

[۳]

[۴]

[۵]

[۶]

[۷]

[۸]

[۹]