کدگذاری خطی شبکه کیست؟ توضیح بده.
در شبکه‌های مخابراتی، کدگذاری خطی شبکه، یا ساده‌تر، کدگذاری شبکه، یا کدینگ شبکه، روشی برای انتقال داده‌هاست که در آن گره‌های میانی شبکه، داده‌ها را با بهره‌گیری از ترکیب‌های خطی آنها، از گره‌های مبدأ به گره‌های مقصد منتقل می‌کنند.کدگذاری خطی شبکه، برای بهبود گذرداد، کارایی و مقیاس‌پذیری شبکه، یا برای امنیت انتقال داده‌ها با جلوگیری از شنود به‌کار می‌رود. گره‌های شبکه چندین بستۀ داده (data packets) را از مبدأ (و گره‌های پیشین) گرفته و آنها را برای رساندن به مقصد، ترکیب خطی می‌کنند. این فرآیند، بیشتر برای دستیابی به حداکثر نرخ انتقال اطلاعات ممکن در شبکه استفاده می‌شود.از دیدگاه تئوری، ثابت شده‌است که کدگذاری خطی برای دستیابی به کران بالایی نرخ انتقال داده‌ها در شبکه‌ای با یک مبدأ (منبع داده‌ها) و چند مقصد، کافی است. بااین‌حال، کدگذاری خطی به‌طور کلی برای هر شبکه‌ای کافی نیست؛ حتی با بهره‌گیری از نسخه‌های عمومی‌تر خطی‌بودن، مانند کدگذاری کانولوشنال و کدگذاری بانک فیلتر. یافتن کدگذاری بهینه برای شبکه‌ها و با هر نیاز دلخواه، یک مسئله دشوار است که می‌تواند اِن‌پی سخت و حتی غیرقابل تصمیم‌گیری باشد.کدگذاری و کدگشایی.در مسئله کدگذاری خطی شبکه، گروهی از گره‌ها (formula_1)، بسته‌های داده‌ را از گره‌های مبدأ (formula_2) به گره‌های مقصد (formula_3) منتقل می‌کنند. هر گره، بسته‌های جدیدی تولید می‌کند که ترکیبی خطی از بسته‌های دریافت‌شدۀ آن هستند. ضرایب این ترکیب خطی، از یک میدان متناهی - معمولاً formula_4 - هستند، که "s"، طول بسته بر حسب بیت است.هر گرۀ formula_5 با formula_6، پیام (بستۀ داده) formula_7 را تولید می‌کند که ترکیب خطی پیام‌های دریافت‌شده formula_8 است: که formula_10ها، ضرایبی هستند که از formula_4 انتخاب شده‌اند. ازآنجاکه این محاسبات در یک میدان متناهی انجام می‌شود، طول پیام تولیدشده و پیام‌های اصلی برابر است. هر گره، formula_7 محاسبه‌شدۀ را به‌همراه ضرایب formula_10 که در مرحله formula_14 استفاده شده‌اند به گره‌های بعدی گسیل می‌کند.گره‌های مقصد، این پیام‌های کدِشبکه‌شده را دریافت کرده، آنها را در یک ماتریس، گرد می‌آورند. پیام‌های (بسته‌های) اصلی را می‌توان با حذف گاوسی این ماتریس، بازیافت. اگر این ماتریس به‌شکل سطری پلکانی در آید، پیام‌های کدگشایی‌شده، همان ردیف‌های ماتریس، formula_15، خواهند بود. پیش‌زمینه.یک شبکه با یک گراف جهت‌دار formula_16 نشان داده‌می‌شود؛ formula_17 مجموعۀ گره‌ها، formula_18 مجموعۀ لینک‌های جهت‌دار (یال‌های گراف)، و formula_19 ظرفیت هر لینک است. فرض کنید formula_20، گذرداد بیشینه از گره formula_21 به گره formula_22 باشد. با قضیۀ جریان-بیشینه برش-کمینه ، کران بالای formula_20، برابر با کمترین ظرفیت همه برش‌هاست؛ که مجموع ظرفیت‌های یال‌های یک برش میان این دو گره است.کارل مِنگِر ثابت کرد که در یک شبکه با یک مبدأ و یک مقصد (تک‌پخشی، 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 بسته بود. افزون‌براین، الگوریتم‌های امروزی می‌توانند بسیار قابل موازی‌سازی باشند و نرخ کدگذاری و کدگشایی را حتی بیشتر افزایش دهند. سربار انتقال: معمولا تصور می‌شود که سربار انتقال در کدگذاری شبکه، به‌سبب نیاز به الحاق ضرایب کدگذاری به هر بسته کدگذاری‌شده زیاد است. در واقع، این سربار در بیشتر کاربردها ناچیز است. سربار در اثر ضرایب کدگذاری را می‌توان چنین محاسبه کرد؛ هر بسته، formula_24 ضریب ضمیمه‌شده دارد. اندازه هر ضریب، شمار بیت‌های لازم برای نشان دادن یک عنصر از میدان نامتناهی است. در عمل، بیشتر کدگذاری‌های شبکه، از اندازه نسل کمتر از 32 بسته در هر نسل و میدان‌های نامتناهی 256 عنصری (باینری-8) بهره می‌برند. با این اعداد، هر بسته به formula_25 بایت سربار نیاز دارد. اگر هر بسته 1500 بایت طول داشته باشد (یعنی اترنت MTU)، آنگاه 32 بایت، تنها 2 درصد سربار می‌شود.سربار در اثر وابستگی‌های خطی: ازآنجاکه ضرایب کدگذاری در RLNC، تصادفی هستند، احتمال می‌رود که برخی از بسته‌های کدشدۀ ارسال‌شده، به‌درد مقصد نخورند، چراکه از ترکیب بسته‌های وابستۀ خطی تشکیل شده‌اند. اما، این سربار در بیشتر کاربردها ناچیز است. وابستگی‌های خطی به اندازه میدان‌ متناهی بستگی دارد و عملاً مستقل از اندازه نسل به‌کاررفته است.کاربردها.پژوهشگران و شرکت‌ها، کدگذاری شبکه را در کاربردها و محصولاتشان به‌کار گرفته‌اند. می‌توان برخی از کاربردهای کدگذاری شبکه را در حوزه‌های مختلف فهرست کرد.