برای تمام اهداف عملی باید اندازه ماتریس­ها برای کد­گذاری شبکه محدود باشد. این مساله برای کد­گذاری جبری شبکه­ ها مستقیما بدست می ­آید. اما در صورت کد­گذاری تصادفی

( اینجا فقط تکه ای از متن فایل پایان نامه درج شده است. برای خرید متن کامل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. )

شبکه­ ها این امر بسیار مشکل می­باشد. در مورد آخر معمولا بسته­ها به دوره­هایی گروه­بندی می­شوند و تنها بسته­هایی که در یک دوره یکسان قرار دارند می­توانند با هم ترکیب شوند. اندازه و ترکیب دوره­ها می ­تواند تاثیر مهمی روی اجرای کد­گذاری شبکه داشته باشد. ملاحضاتی مشابه نیز برای اندازه میدان متناهی برقرار است. هر دو پارامتر باعث کاهش حافظه مورد نیاز و پیچیدگی­های مثلثاتی می­ شود [۴].
تاخیر
تاخیر یک مشخصه اجرایی مهم در شبکه ­های کامپیوتری است. تاخیر در یک شبکه عبارت است از مدت زمانی که به طول می­انجامد تا یک بیت از داده ­ها در شبکه از یک گره به گره دیگر برود که معمولا به صورت مضربی از ثانیه­ها یا کسری از ثانیه اندازه ­گیری می­ شود. کاربران تنها به تاخیر کلی شبکه توجه می­ کنند، اما مهندسان میانگین تاخیر و ماکزیمم تاخیر را مورد توجه قرار می­ دهند و تاخیر را به قسمت­ های مختلفی تقسیم ­بندی می­ کنند که عبارتند از:
تاخیر پردازش: زمانی که به طول می­انجامد تا مسیریاب بسته­ها را پردازش کند.
تاخیر به صف کردن: زمانی که به صف کردن داده ­ها اختصاص می­یابد.
تاخیر انتقال: زمانی که به طول می­انجامد تا بیت­های بسته­ها در خط ارتباطی قرار گیرند.
تاخیر انتشار: زمان مورد نیاز برای رسیدن یک سیگنال به مقصد.
بسته­هایی که نیاز به از کد­ درآوردن دارند تاثیرات اندکی در تاخیر دارند. معمولا لازم نیست که تمام بسته­های کد­گذاری شده قبل از اینکه تعدادی از بسته­ها بتوانند از کد خارج شوند، دریافت شوند. (یعنی هرگاه قاعده حذفی گاوس منجر به ایجاد یک سطر به شکل شود.) در مجموع با کاهش انتقالات مورد نیاز، تاخیرات کلی در شبکه ­های کد­گذاری شده بزرگتر از تاخیرات در شبکه ­های عادی نیست [۴].
۲-۲-۶- مزایای کد­گذاری شبکه چیست؟
بازده مورد نظر در محیط استاتیک
اولین نتایجی که در کد­گذاری شبکه درخشید این است که کد­گذاری شبکه قادر است ظرفیت شبکه را برای جریان در توزیع با چند گیرنده افزایش دهد. شبکه­ ای را در نظر بگیرید که به صورت یک گراف جهت­دار نشان داده می­ شود ( عموما این شبکه سیمی است). رئوس گراف نظیر ترمینال­ها و یال­های گراف نظیر کانال­ها هستند. فرض کنید منبع داشته باشیم که هر یک اطلاعات را به نسبت مشخص ارسال می­ کنند و گیرنده داریم. تمام گیرنده­ها تمایل دارند که تمام منابع را دریافت کنند.
قضیه ۱. اگر نسبت­های منبع به گونه ­ای باشد که بدون کد­گذاری شبکه، شبکه بتواند هر گیرنده را به تنهایی حمایت کند. (یعنی هر گیرنده می ­تواند تمام منابع را هنگامی که تنها یک گیرنده در شبکه موجود باشد، از کد خارج کند.) در این صورت با انتخاب مناسب از ضرایب کد­گذاری خطی شبکه قادر است تمام گیرنده­ها را همزمان حمایت کند [۴].
به عبارت دیگر هنگامی که گیرنده در منابع شبکه مشترک هستند هر یک از آن­ها می ­تواند ماکزیمم نسبتی را که امید به دریافت آن داشته است دریافت کند. حتی اگر تمام منابع شبکه را خودش استفاده کند. از این رو کد­گذاری شبکه می ­تواند به اشتراک بهتر منابع شبکه در دسترس کمک کند.
قدرت­مندی و انطباق­پذیری
مهمترین مزیت کد­گذاری شبکه، قدرت­مندی و انطباق­پذیری آن است. به صورت شهودی فکر می­­کنیم که کد­کذاری شبکه مشابه کد­گذاری سنتی، بسته­­های اطلاعات را دریافت می­ کند و بسته­های کد­گذاری شده را تولید می­نماید، جایی­که هر بسته کد­گذاری شده به یک میزان اهمیت دارند، مشروط به اینکه تعداد کافی از بسته­های کد­گذاری شده را دریافت کرده باشیم (مهم نیست کدام بسته دریافت شده باشد) می­توانیم آن­ها را از کد درآوریم. شکل جدیدی که کد­گذاری شبکه فراهم می ­آورد این است که ترکیبات خطی به صورتی مصلحت ­اندیشانه و نه تنها روی گره منبع انجام می­شوند، بنابراین کد­گذاری شبکه در مواردی که گره­ها تنها اطلاعات ناکافی در مورد موقعیت کلی شبکه دارند بسیار مناسب می­باشد.
مجددا مثال شکل ۲-۱ را در نظر بگیرید و فرض کنید که و به صورت تصادفی و بدون توجه به موقعیت فعال نباشند (یا ممکن است از محدوده خارج شده باشند)، اگر ، یا را توزیع کند، از آن­جایی که گیرنده مورد نظر ممکن است قادر به دریافت بسته­ها نباشد، انتقالات کاملا بی­فایده خواهد بود. در حالی که اگر ، یا به صورت کلی­تر ترکیب خطی تصادفی از بسته­های اطلاعات را توزیع کند، انتقال می ­تواند اطلاعاتی جدید را به گره­های فعال منتقل کند[۴].
۲-۲-۷- مثال
در این قسمت شبکه پروانه­ای^[۶۶] را مورد بررسی قرار می­دهیم. در شبکه پروانه­ای ( شکل ۲-۲ ) دو منبع داریم (در بالای تصویر) که یکی دارای داده و دیگری دارای داده است. دو گره مقصد نیز موجود است (در پایین تصویر) که هر یک مایلند و را دریافت کنند. هر یال تنها قادر به انتقال یک مقدار است. اگر از روش­های عادی برای انتقال داده ­ها استفاده کنیم یال مرکزی تنها قادر به انتقال یا است و نمی­تواند هر دو را انتقال دهد. حال فرض کنید را از طریق یال مرکزی عبور دهیم. مقصد سمت چپ را دو بار دریافت می­ کند در حالی که را اصلا دریافت نمی­کند. مساله­ای مشابه در حالتی که تنها را از یال مرکزی عبور دهیم نیز رخ می­دهد. حال با بهره گرفتن از یک کد ساده می­توانیم و را همزمان به هر دو مقصد ارسال کنیم. با فرستادن داده از یال مرکزی مقصد سمت چپ با دریافت و قادر است را نیز تولید کند و مقصد سمت راست با دریافت و ، را تولید می­ کند. این کد­گذاری یک کد­گذاری خطی است، زیرا اعمال کد­گذاری و از کد خارج کردن هر دو خطی می­باشند.
شکل ۲-۲- شبکه پروانه­ای
۲-۲-۸- موارد استفاده از کد­گذاری شبکه.
در زیر تعدادی از کاربردهای کد­گذاری شبکه را مورد بررسی قرار می­دهیم.
توزیع فایل ^[۶۷]
احتمالا شناخته­ شده­ترین استفاده از کد­گذاری شبکه­ ها در است. به توزیعی در شبکه نظیر به نظیر گفته می­ شود که توسط پابلو رودریگز^[۶۸] و کریستس گانتسیدیس^[۶۹] در مایکروسافت^[۷۰] طراحی شد که در آن پهنای باند نسبت به سیستم نظیر به نظیر معمولی بهبود یافته است. برای توزیع­های با حجم زیاد در شبکه ­های نظیر به نظیر استفاده می­ شود و در آن کد­گذاری شبکه به کار گرفته می­ شود. در این­گونه شبکه توزیع سرویس دهنده، یک فایل بزرگ را به تعدادی بلوک می­شکند. گره­های هم­تراز سعی می­ کنند که فایل اصلی را با دانلود بلوک­ها از سرویس دهنده بازیابی کنند و بلوک­های دانلود شده را بین خودشان توزیع کنند. بدین منظور گره­های هم­تراز ارتباط خود را با تعداد محدودی از گره­های هم­تراز همسایه خود حفظ می­ کنند که این گره­های همسایه به صورت تصادفی از بین مجموعه گره­های هم­تراز انتخاب می­شوند. در بلوک­هایی که توسط سرویس دهنده فرستاده می­شوند به صورت ترکیب خطی تصادفی از بلوک­های اصلی هستند. به صورت مشابه گره­های هم­تراز، ترکیبات خطی تصادفی از تمام بلوک­هایی که در دسترس دارند را ارسال می­ کنند. یک گره می ­تواند تعیین کند که چه تعداد بلوک تغییر­یافته را می ­تواند به یکی از همسایگانش ارسال کند. این کار با مقایسه ماتریس ضرایب از کد درآوردن خود و همسایه­اش انجام می­گردد، یا اینکه به آسانی بلوک­های کد شده را ارسال می­ کند تا هنگامی که همسایه­اش اولین بلوک تغییر­نیافته را دریافت کند، سپس گره انتقالاتش را به این همسایه قطع می­ کند تا هنگامی که بلوک­های تغییر­یافته بیشتری را از دیگر گره­ها دریافت کند. ضرایب کد­گذاری به همراه بلوک­ها انتقال می­یابند. اما از آن­جایی که معمولا بلوک­ها دارای اندازه­ای در حدود هزاران کیلو بایت هستند، این اضافات اندک و نا چیز است. در اطلاعات به سرعت به تمام کاربران در شبکه می­رسد. یک گره جدید می ­تواند در طول مدت زمانی که عملیات توزیع در شبکه صورت می­گیرد به شبکه افزوده شود. کاربر جدید ابتدا به سرویس دهنده مرکزی متصل می­گردد و سپس با گره­هایی که در همسایگی­اش قرار دارند به تبادل جریان می ­پردازد.
کد­گذاری شبکه از جهات بسیاری به مساله­های زیر کمک می­ کند:

1. 1. زمان دانلود را می­نیمم می­ کند. در یک سیستم توزیع با اندازه بزرگ طرح ریزی بهینه بسته­ها بسیار پیچیده است، به خصوص اگر کاربران اطلاعات بسیار محدودی در مورد ساختار شبکه داشته باشند. با بهره گرفتن از کد­گذاری شبکه، عملکرد سیستم بسیار کمتر به ساختار شبکه وابسته می­گردد. در نتیجه مکانیزم بسیار ساده­ای که یک پوشش تصادفی را می­سازد مورد استفاده قرار می­گیرد.

1. 1. با توجه به عدم تشابه یا تفاوت بلوک­های کد شده، جواب بر پایه کد­گذاری شبکه در حالتی که سرور کارش را قبل از اینکه تمام جفت­ها دانلودشان را تمام کرده باشند یا در رویارویی با نسبت به شدت بالا ( هنگامی که گره­ها تنها برای مدت زمان کوتاهی با هم مرتبط باشند یا اینکه سریعا بعد از اتمام دانلودشان ارتباط آن­ها قطع شود .)، قطع کند، دارای قدرت بالاتری می­باشد.

1. 1. کد­گذاری شبکه به گره­های شبکه این اجازه را می­دهد که به کد­گذاری بپردازند و این امر باعث ماکزیمم شدن بازده شبکه می­گردد.

1. 1. بر­خلاف ارسال پروتکل­های اصلی، پروتکل کد­گذاری شبکه تنها خطای کوچکی را متحمل می­شوند [۴، ۲۹].

شبکه ­های بی­سیم
جریان دو طرفه در شبکه ­های بی­سیم
همان­گونه که در مثال شکل ۲-۱ دیدیم، متوجه شدیم که کد­گذاری شبکه می ­تواند هنگامی که دو گره با ارتباط بی­سیم تحت یک ایستگاه پایه­ای با هم ارتباط دارند، بازده را افزایش دهد. این حالت را می­توان به حالت در یک شبکه بی­سیم گسترش داد، جایی­که جریان بین دو گره انتهایی دو طرفه است و هر دو گره تعداد یکسانی بسته برای تغییر دارند. اگر برنامه­ای داشته باشیم که مسیریاب­های مجاور با هم مبادله داشته باشند بعد از چند گام اولیه، تمام مسیریاب­های میانی بسته­هایی را برای انتقال دو طرفه در مسیر در حافظه خود ذخیره کرده ­اند. هرگاه فرصت انتقال افزایش یابد یک مسیریاب دو بسته را هر یک برای یک جهت با عمل ساده با هم ترکیب و به همسایگانش توزیع می­ کند. هر دو مسیریاب گیرنده یکی ازبسته­هایی که در توزیع کدگذاری شده است را می­شناسند، در حالی که بسته دیگر برای آن­ها جدید است. بنابراین هر توزیع به دو گیرنده اجازه می­دهد که یک بسته جدید را دریافت کند که این کار ظرفیت مسیر را به طور موثری افزایش می­دهد.
شبکه ­های بی­سیم مش محلی^[۷۱]
حتی اگر کد­گذاری شبکه تنها از عمل محدود XOR برای ترکیب بسته­ها استفاده کند، می ­تواند به طور موثری کارایی شبکه ­های بی­سیم مش را افزایش دهد. تمام انتقال­ها توزیع و توسط همسایگان دریافت می­شوند. بسته­ها با خلاصه­ای از اطلاعات در مورد تمام بسته­های دیگری که یک گره تاکنون دریافت شده است حاشیه­نگاری می­ شود. بدین طریق اطلاعات در مورد اینکه کدام گره­ها کدام بسته­ها را در یک همسایگی توزیع می­ کنند نگهداری می­شوند. یک گره می ­تواند چندین بسته را تحت عمل XOR برای همسایگان متفاوت کد­گذاری کند و آن­ها را تحت یک انتقال ارسال نماید، مشروط بر اینکه هر همسایه هنوز اطلاعاتی برای از کد درآوردن اطلاعات داشته باشد [۴].
امنیت شبکه
در هر شبکه امنیت اطلاعات باید مد نظر قرار گیرد.
امنیت در برابر شنود که تلاش به احیاسازی بخش داده ­ها دارد. امنیت در برابر مهاجمان بدخواه که تلاش برای محروم کردن گیرنده­ها از اطلاعات با کاهش بسته­ها دارد و امنیت در برابر هجوم پارازیت.
کد­گذاری شبکه، محافظت در برابر شنود را بسیار آسان می­ کند، زیرا اطلاعات بیشتر گسترش می­یابند و شنیدن آن­ها مشکل است. مبدا، داده ­های اصلی را با اطلاعات تصادفی ترکیب می­ کند و یک کد شبکه را به طریقی که تنها گیرنده­ها قادر به از کد خارج کردن بسته­ها باشند، تولید می­ کند. علاوه بر این اطلاعات مشترک بین بسته­هایی که توسط شنود کننده دریافت می­ شود و بسته­های اصلی صفر است. نوع ضعیف­تری از امنیت بر این حقیقت استوار است که تنها گره­هایی می­توانند بسته­ها را از کد درآورند که به تعداد کافی بردارهای مستقل خطی دریافت کرده باشند کاری که شنود کننده­ها نمی ­توانند انجام دهند. کد­گذاری شبکه حفاظت در برابر کاهش بسته­ها در شبکه را نیز آسان می­ کنند. در یک شبکه بدون هیچ حفاظت اضافی، مهاجمان میانی می­توانند به دلخواه در بسته­ای تقلیل ایجاد کنند. در حالتی که از کد­گذاری شبکه استفاده شده باشد، مهاجم نمی­تواند به عمل از کد درآوردن بسته­ها در مقصد بدون داشتن تمام بسته­های کد­گذاری شده که توسط مقصد دریافت شده ­اند، غلبه کند. بسته­ها از طریق مسیرهای متفاوت جریان پیدا می­ کنند و این کار مهاجم را مشکل می­سازد. از سویی دیگر به نظر می ­آید که کد­گذاری شبکه امنیت شبکه در برابر هجوم پارازیت را ارتقا
می­بخشد. پارازیت می ­تواند عملکرد شبکه را مختل گرداند. در شبکه­ ای که پارازیت ایجاد
می­ شود، گره­هایی وجود دارند که بسته­های نامعتبر و خراب را منتشر می­ کنند. هنگامی که این بسته­های خراب توسط گیرنده­ها دریافت می­شوند، گیرنده­ها توانایی بازخوانی و از کد درآوردن آن­ها را ندارند، از این رو شبکه دچار اختلال می­گردد. چون در یک شبکه سرویس دهنده بسته داده ­ها را ارسال می­ کند، این بسته­ها معتبر و درست هستند در حالی که در شبکه­ ای که پارازیت وجود دارد گره­های میانی نیز موجودند که به ارسال بسته­های خراب و نامعتبر
می­پردازند. اگر از کد­گذاری در شبکه استفاده کنیم که در آن بردارهای کد­گذاری به صورت تصادفی انتخاب شده ­اند، از آنجایی که گره­های میانی که عمل کد­گذاری را انجام می­ دهند ممکن است پیش از این بسته­های خراب را نیز دریافت کرده باشند، بسته­های کد شده جدید نیز نامعتبر خواهند بود و از این رو تعداد بسته­های نامعتبر در شبکه افزایش می­یابد. در
این­گونه شبکه­ ها از کد­گذاریی استفاده می­ شود که در آن با بهره گرفتن از یک تابع به نام تابع هش^[۷۲] عمل کد­گذاری صورت می­گیرد و یک گره قبل از اینکه بسته­ای را دریافت کند، بررسی می­ کند که آیا این بسته معتبر است یا نه و در صورت معتبر بودن این بسته وارد ترکیب
کد­گذاری می­گردد. از آن­جایی که بررسی معتبر بودن بسته­ها عملی وقت­گیر است، هنگامی که یک گره یک بسته نامعتبر را می­شناسد به سایر گره­های همسایه اطلاع می­دهد که این بسته نامعتبر است تا آن­ها نیز آن را دریافت نکنند و در نهایت این امر باعث می­گردد تا گره­ها از پذیرش بسته­های نامعتبر خودداری کنند[۳، ۴].