۱۱- پروتکل های لایه پیوند داده ها:
لایه پیوند داده ها، باید سه وظیف فریم بندی، مدیریت خطا و کنترل جریان را به نحوی انجام دهد. این کار به کمک پروتکلهایی انجام می شود که در این بخش آنها رابررسی می کنیم.
تمام پروتکلهایی که مورد بحث قرار می دهیم، با نمونه های واقعی خودشان از جهاتی تفاوت دارند:
اولا پروتکلهایی که ما در این قسمت مورد بررسی قرار می دهیم، تک جهته (unidirectional) هستند. یعنی داده ها همیشه در یک جهت از یک گره به نام فرستنده، به سمت گره دیگر به نام گیرنده ارسال می شوند. علاوه بر این فریم های خاصی که فریم های تایید یا تصدیق (ACK) و عدم تصدیق (NACK) نامیده می شوند در جهت مخالف از گیرنده به سمت فرستنده ارسال می شوند (جهت مقاصدی نظیر کنترل جریان و کنترل خطا که در ادامه بررسی خواهیم کرد)
در دنیای واقعی، پروتکل های لایه پیوند داده ها دو جهته (Bidirectional) هستند. در این پروتکل ها، اطلاعات مربوط به کنترل جریان و کنترل خطا نظیر، ACKها و NACK ها با استفاده از تکنیکی به نام سواری مجانی (piggy backing) بر روی فریم های داده ارسال می شوند. به دلیل پیچیدگی این نوع پروتکلها، از بحث در مورد این نوع پروتکلها در این بخش صرف نظر کرده و تنها به این نکته بسنده می کنیم که کلید فهم پروتکلهای اخیر در فهم پروتکل های تک جهته است.
دسته بندی پروتکل های کنترل جریان در لایه پیوند داده ها
۱۱٫۴- کانالهای بدون نویز:
در این بخش فرض می کنیم، کانال ایده آلی داریم که در آن هیچ فریمی گم نمی شود، تکرار نمی شود، خراب هم نمی شود (البته کاملا مشخص است که این فرض ها چه فرضهای ایده آلی است و چه قدر در دنیای واقعی نمود دارد!). دو پروتکل برای این نوع از کانالها معرفی خواهیم کرد. اولی، پروتکلی است که از هیچ مکانیزمی برای کنترل جریان، استفاده نمی کند و دومی از مکانیزم های کنترل جریان استفاده می کند. ضمنا، به دلیل ایده آل بودن کانال، هیچکدام از این دو پروتکل به کنترل خطا نیاز ندارند.
۱- یک پروتکل ساده:
به دلیل اینکه هیچ نام دیگری جهت توصیف این پروتکل نیافتیم، آن را ساده ترین پروتکل یا Simplest نامیده ایم. همانند سایر پروتکلهایی که در این فصل مورد بررسی قرار خواهند گرفت این پروتکل نیز تک جهته است. (یعنی داده ها از فرستنده به گیرنده ارسال می شوند). فرض بر این است که پس از دریافت هر فریم، گیرنده بلافاصله قادر به پردازش آن است. کار پردازش در زمان بسیار کوتاهی انجام می شود که قابل صرفنظر کردن است.
به دلیل اینکه فرستنده تاز مانی که لایه شبکه پکتی برای ارسال نداشته باشد، چیزی برای ارسال ندارد و گیرنده نیز تا زمانی که لایه فیزیکی پیغامی دریافت نکند، نمیتواند کاری انجام دهد، از ایده Event استفاده می کنیم. روال سمت فرستنده به صورت پیوسته در حال اجرا است اما کاری انجام نمی دهد، مگر اینکه درخواستی از لایه شبکه برسد. روال سمت گیرنده نیز به صورت پیوسته در حال اجر است، اما کاری انجام نمی دهد، مگر این که درخواستی از لایه فیزیکی به آن برسد. هر دوی این روال ها باید به صورت پیوسته در حال اجرا باشند، چرا که از زمان وقوع این رخدادها آگاه نیستند.
شکل زیر نمونه ای از استفاده از این پروتکل را در عمل نشان میدهد. فرستنده، دنباله ای از فریم ها را می فرستد، بدون اینکه در مورد گیرنده و میزان توانایی های آن در ذخیره و نگهداری فریم ها فکر کند. برای ارسال سه فریم، سه رخداد درخواست در سمت گیرنده رخ می دهد و متناظر با آن سه رخداد در سمت گیرنده رخ خواهد داد که رسیدن یک فریم را به لایه پیوند داده ها اطلاع می دهد.
الگوریتم سمت فرستند در پروتکل ساده
الگوریتم سمت گیرنده در پروتکل ساده
۱- پروتکل توقف و انتظار(stop and wait protocol)
اگر فریم های داده ای در سمت گیرنده، با سرعتی بیش از زمان لازم برای پردازش آنها دریافت شوند (نرخ ورود فریم ها از نرخ پردازش آنها بیشتر باشد) در این صورت، فریم ها می بایست تا زمان پردازششان ذخیره شوند. در حالت معمول ، گیرنده آنقدر فضای بافر در اختیار ندارد که بتواند فریم های داده ای دریافتی را ذخیره کند. بروز این حالت موجب می گردد تا گیرنده یا اقدام به دور انداختن فریم ها کند (discard) و یا قادر به سرویس دهی نباشد (denial of service).
برای پیشگیری از بروز این رخداد، گیرنده نیاز دارد که در مواقعی به فرستنده اعلام کند که سرعت ارسال را کاهش دهد. این امر مستلزم وجود بازخوردی از جانب گیرنده برای فرستنده است.
پروتکلی که در این بخش مورد بررسی قرار می گیرد، پروتکل Stop-and-wait یا توقف و انتظار نام دارد؛ چرا که در این روش، فرستنده یک فریم می فرستد، منتظر می ماند تا دریافت آن از جانب گیرنده تایید شود (OK گیرنده برسد تا ادامه دهد) و بعد از آن فریم های بعدی را ارسال می کند. در این حالت نیز همچنان تک جهته عمل می کنیم اما فریم های ACK کمکی (نشانه های ساده ای برای تایید دریافت اطلاعات) در جهت مخالف ارسال می شوند؛ با این مکانیزم ساده، کنترل جریان به پروتکل افزوده می شود.
شکل ۱۱-۸: طرح پروتکل توقف و انتظار
الگوریتم ۱۱٫۳-الگوریتم stop-and-wait سمت فرستنده
الگوریتم ۱۱٫۴- الگوریتم stop-and –wait سمت گیرنده
آنالیز ریاضی این الگوریتم:
ایده پروتکل stop-and-wait ایده خوبی است، به شرط آن که اطلاعات ارسالی به صورت چند فریم بزرگ و طولانی ارسال شود. اما در عمل فرستنده اطلاعات را به چندین فریم کوچکتر تقسیم می کند. این کار به چند دلیل صورت می یرد:
۱- ممکن است اندازه بافر گیرنده محدود باشد
۲- اگر انتقال طولانی باشد در صورتی که خطایی رخ دهد فرستنده مجبور است همان فریم طولانی را دوباره ارسال کند. در ارسال فریم های کوچک، اولا خطاها زودتر آشکار می شوند و ثانیا فقط بخش کوچکی از دیتا دوباره باید ارسال شود.
۳- در شبکه هایی که محیط انتقال مشترکی بین همه ایستگاهها وجود داشته باشد (مثل LANها) به یک ایستگاه اجازه داده نمی شود که محیط انتقال را به مدت زیادی اشغال کند و باعث معطل شدن بیش از حد دیگر ایستگاههای فرستنده شود.
با توجه به نحوه عملکرد پروتکل، می توان نوشت:
در میان این زمان ها با فرض اینکه زمان های پردازش و زمان لازم برا ی ارسال Ack قابل صرفنظر کردن باشند، خواهیم داشت
با فرض اینکه مقدارa برابر با مقدار زیر باشد، رابطه بهره وری را میتوان به شکل زیر نیز نوشت:
مقدار BL/Vحاصلضرب تاخیر در پهنای باند نامیده می شود. این حاصلضرب فاصله میان فرستنده و گیرنده بر حسب بیت را نشان میدهد. در این صورت در رابطه بالا مقدار a بیانگر نسبت فاصله گیرنده و فرستنده بر حسب بیت نسبت به اندازه فریم بر حسب بیت است.
حاصلضرب فوق (تاخیر در پهنای باند) در حقیقت نشاندهنده ماکزیمم ظرفیت کانال انتقال در هر زمان است. این حاصلضرب تعداد بیتهایی را نشان میدهید که کانال انتقال را پر می کنند
درک مفهومی از حاصلضرب تاخیر در پهنای باند
۱۱٫۵ کانالهای نویزی:
۱- پروتکل Stop-and-wait ARQ:
با توجه به ایده ای که از مرحله قبل در خصوص فریم های ACK گرفتیم، می توانیم فرض وجود کانالهای بدون نویز را نیز حذف کرده و با همان فریم ACK کنترل خطا را انجام دهیم. یکی از پروتکلهایی که از این رویکرد استفاده می کند، پروتکل توقف و انتظار با درخواست تکرار اتوماتیک است که در ادامه به شرح آن خواهیم پرداخت. قبل از ادامه ذکر این نکته ضروری به نظر می رسد که این گروه از پروتکل ها به نام ARQ (درخواست تکرار اتوماتیک) شناخته می شوند. به این دلیل که در مواجهه با خطا (مثلا پس از بررسی کد کشف خطای CRC و تشخیص دادن خطا در فریم) به گونه ای عمل می کنند که فرستنده مجبور به ارسال مجدد فریم خطادار شود (خواهیم دید که چگونه فرستنده را مجبور می کنند که این کار را انجام دهد). برای بررسی نحوه عملکرد این پروتکل حالتهای زیر را در نظر می گیریم:
برای کشف و تصحیح خطا، نیاز است که از بیت های افزونه، مطابق آنچه که در در بخش کنترل خطا مورد بررسی قرار گرفت، به فریم ها اضافه شود. زمانی که فریم ها به دست گیرنده رسید، گیرنده صحت آنها را بررسی می کند. اگر فریم در اثر رخداد خطا فاسد شده باشد، آن را دور انداخته (درسکوت کامل رسانه ای!) و عکس العملی نشان نمی دهد. این سکوت در سمت گیرنده توسط پروتکل، به منزله کشف خطا است.
فریم های گم شده و مدیریت آنها در این پروتکل، از کشف خطا و مدیریت آن سخت تر است. در پروتکلهای قبلی، هیچ مکانیزمی برای هویت بخشیدن به فریم ها تعریف نشده بود. در این جا، اما، فریمی که به دست گیرنده می رسد، میتواند همان فریمی باشد که باید برسد، یا می تواند یک فریم تکراری باشد و یا اینکه می تواند فریمی خارج از ترتیب باشد (بدون رعایت نظم فریم ها). چاره کار در شماره گذاری فریم ها است. هرگاه گیرنده فریمی دریافت کند که از لحاظ شماره ترتیب درست نباشد، به منزله آن است که یا فریم گم شده است یا اینکه فریم تکراری است.
اگر فریم گم شده و یا اینکه خراب شده باشد، می بایست مجددا ارسال گردد. اگر فرستنده راهی نداشته باشدکه مشخص کند کدام فریم می بایستی دوباره ارسال شود، چه باید کرد؟ راه حل این مشکل در این است که فرستنده یک کپی از فریم ارسالی را نگه میدارد و همزمان با ارسال، تایمری را فعال می کند. اگر تایمر منقضی شد و هیچ فریم ACK ای که نشان دهد فریم ارسالی به صورت صحیح دریافت شده است، دریافت نگردد، فریم مزبور مجددا ارسال می گردد.
نظر به اینکه محیط انتقال خطادار می باشد، فریم های ACK نیز میتوانند خراب شده و یا خطادار دریافت گردند. بنابراین فریم های ACK نیز بایستی به یک شماره ترتیب مجهز باشند
شماره ترتیب(Sequence Number): یکی از بحثهایی که در طول تشریح این پروتکل داشتیم، شماره ترتیب (
Seq. Number) بود؛ فیلدی که می بایستی به فریم داده ای اضافه شده و شماره ترتیب فریم را نگه دارد.
نکته مهمی که در اینجا نباید از نظر دور داشت، محدوده شماره ترتیب است، نظر به اینکه ما قصد داریم اندازه فریم ها را کمینه کنیم بنابراین باید به دنبال کوتاه ترین محدوده شماره ترتیب ها باشیم که بتواند بدون هیچ گونه ابهامی، نیازهای ارتباطی را برآورده کند. کاملا مشخص است که این دنباله از شماره ها می توانند به صورت چرخشی (wrap around) استفاده شوند؛ اگر بیت شماره ترتیب m بیت طول داشته باشد، شماره ترتیب می بایستی از ۰ تا باشند و پس از این، دوباره این شماره ها می توانند تکرار شوند.
حال ببینیم به چه میزان شار ترتیب نیاز داریم: فرض کنید x نمایشگر یک شماره ترتیب باشد. در این پروتکل تنها به شماره بعد از آن یعنی x+1 نیاز داریم (و پس از آن می توان با مکانیزم چرخش، شماره ها را مجددا مورد استفاده قرارداد). دلیل این امر را می توان با بررسی حالت های ممکن ارتباطی میان فرستنده و گیرنده تشریح کرد. سه حالت ممکن است رخ دهد:
الف- فریم شماره x صحیح و سالم به مقصد رسیده است. گیرنده ACK می فرستد. دریافت ACK توسط فرستنده باعث می شود که فرستنده فریم بعدی یعنی x+1 را بفرستد.
ب- فریم x صحیح می رسد. اما ACK در راه گم می شود (یا فاسد می شود). در این صورت فرستنده پس از انقضای مهلت توسط تایمر، اقدام به ارسال مجدد فریم (شماره گذاری شده با x) می کند. توجه دارید که فریم ارسالی توسط فرستنده در این حالت تکراری است. گیرنده این نکته را تشخیص می دهد (چرا که انتظار دریافت فریم x+1 رادارد اما فریم x را دریافت کرده است)
ج- اگر فریم x هرگز به مقصد نرسد، در این حالت پس از انقضا تایمر، فرستنده مجددا فریم شماره x را می فرستد.
در حقیقت نکته ای که در خصوص شماره ترتیب در این پروتکل و سایر پروتکل هایی که به این مکانیزم نیاز دارند باید مورد توجه قرار گیرد این است که تحت چه شرایطی استفاده مجدد از شماره ترتیب ها آزاد است. به عبارت دیگر ، الزامات پروتکل و نحوه استفاده مجدد از شماره ترتیب ها، محدوده مودنیاز شماره ترتیب ها را معین می کند. در این پروتکل یک فریم همیشه ارسال شده و منتظر دریافت تاییدیه است و یک فریم نیز هموراه آماده ارسال است. بنابر این دو شماره کافی است:۰ و ۱
ACK Numberها: در این پروتکل ACK Number ها، شماره فریم بعدی مورد انتظار را نمایش می دهند. یعنی زمانی که فریم شماره ۰ صحیح به مقصد رسید، گیرنده ACK(1) را ارسال میکند (یعنی بیان می کند که فریم صحیح رسیده و منتظر دریافت فریم شماره ۱ است) و بالعکس.
شبه کد الگوریتم مورد استفاده توسط فرستنده در پروتکل Stop-and-Wait ARQ در شکل زیر ارائه شده است
در این پروتکل فرستنده یک متغیر کنترلی (به نام ) دارد که شماره فریم بعدی که باید ارسال شود را نگهداری می کند. گیرنده نیز یک متغیر کنترلی (به نام ) دارد. این متغیر، شماره فریمی که انتظار دارد دریافت کند را نگهداری می کند. هر گاه فرستنده یک فریم ارسال کند Snیک واحد اضافه می شود (در مبنای ۲، یعنی اگر مقدار ۰ دارد به یک تبدیل می شود و اگر مقدار ۱ دارد به ۰ تبدیل می گردد). هرگاه گیرنده یک فریم تصدیق ارسال کند، به مقدار Rn یک واحد اضافه می شود (در مبنای ۲)
شبه کد الگوریتم مورد استفاده توسط پروتکل ARQ گیرنده را در زیر مشاهده می کنید:
در شکل زیر سناریوهای مختلفی از نحوه عملکرد stop-and-wait ARQ به تصویر کشیده شده است.
فریم ۰ ارسال و تایید شده است. فریم ۱ گم شده و پس از انقضای زمان توسط تایمر مجددا ارسال شده است. ارسال مجدد فریم ۱ تایید شده و تایمر متوقف می شود.
فریم ۰ ارسال و تایید شده است اما تاییدیه گم شده است. فرستنده قادر به تمایز و تعیین اینکه آیا فریم گم شده و یا اینکه تاییدیه گم شده است نیست؛ بنابراین پس از انقضا تایمر اقدام به ارسال مجدد فریم ۰ می کند –که قبلا ارسال و تایید شده است- در این حالت گیرنده با توجه به شمارنده ای که در اختیار دارد –که نشان میدهد منتظر فریم ۱ است اما فریم ۰ ارسال شده- متوجه گم شدن تاییدیه شده و اقدام به ارسال مجدد تاییدیه می کند.
آنالیز ریاضی پروتکل:
در ادامه برای بررسی کارآیی این پروتکل، یک لم مقدماتی را ارائه خواهیم داد
لم: اگر احتمال سالم نرسیدن یک فریم P باشد، با متد ARQ باید چندبار فریم را ارسال کرد تا مطمئنا فریم به گیرنده برسد؟
پاسخ: برای پاسخ به این سئوال، حالات مختلف را بررسی می کنیم (جدول را نگاه کنید)
اگر بخواهیم میانگینی از تعداد دفعات ارسال داشته باشیم کافی است احتمال رخداد هر تکرار را در تعداد دفعات ارسال ضری کنیم. به عبارت دیگر:
Loading ...
یک دیدگاه
با سلام
می خواستم بدونم این مطالبی که نوشتید مربوط به دوره کارشناسی هست یا کارشناسی ارشد ؟
به نظر شما آیا مطالبی که نوشتید، ممکن است با این جزئیات برای کنکور کارشناسی ارشد بیاید ؟
با تشکر