لایه پیوند داده

لایه پیوند داده

اسلاید 1: 1فصل سوملایه پیوند داده

اسلاید 2: 2ملاحظات طراحی لایه پیوند دادهارایه سرویس های مشخص به لایه شبکهفریم بندیداده اصلیسرآیندپی آیند مدیریت خطاهای انتقالتنظیم جریان داده هاکلیدی ترین وظیفه لایه پیوند داده

اسلاید 3: 3ملاحظات طراحی لایه پیوند داده(ادامه)رابطه بین بسته و فریم

اسلاید 4: 4سرویس هایی ارایه شده به لایه شبکه انتقال داده ها از لایه شبکه مبدا به لایه ماشین مقصدسرویس غیر متصل(connection less) بدون تصدیق دریافت(Ack)سرویس غیر متصل با تصدیق دریافتسرویس اتصال-گرا ( connection oriented )با تصدیق دریافت

اسلاید 5: 5سرویس هایی ارایه شده به لایه شبکه(ادامه)(a)ارتباط مجازی (b)ارتباط واقعی

اسلاید 6: 6سرویس هایی ارایه شده به لایه شبکه (ادامه-2) سرویس غیر متصل بدون تصدیق دریافت(مانند سیستم پست)اتصال منطقی وجود ندارداین سرویس برای نرخ پایین خطا مناسب استتشخیص خطا ندارد برای ترافیک realtime مناسب استمقابله با خطا در لایه بالاتراغلب LANها و سرویس صدا

اسلاید 7: 7سرویس هایی ارایه شده به لایه شبکه (ادامه-3) سرویس غیر متصل با تصدیق دریافتاتصال منطقی بین مبدا و مقصد وجود ندارددریافت فریم ها از سوی مقصد تصدیق می شودمناسب برای کانال های غیر قابل اعتمادسیستم های بیسیم

اسلاید 8: 8سرویس هایی ارایه شده به لایه شبکه (ادامه-4) سرویس اتصال گرا با تصدیق دریافتبهترین سرویس لایه پیوند دادهشماره گذاری فریمتصدیق دریافت توسط ماشین مقصدارسال داده ها در سه مرحلهبرقراری اتصال و مقداردهی متغیر های لازمانتقال فریم هاقطع اتصال و آزاد سازی منابع

اسلاید 9: 9سرویس هایی ارایه شده به لایه شبکه (ادامه-5)محل فعالیت لایه پیوند داده

اسلاید 10: 10فریم بندیتعریف فریم بندیروش های کشف خطاشمارش کارکترهابایت های پرچم، با درج بایت (byte/character stuffing)پرچم های شروع وپایان، با درج بیت (bit stuffing)حالت های غیر مجاز کدگذاری لایه فیزیکی

اسلاید 11: 11فریم بندی(ادامه)استریم کارکترها (a) بدون خطا (b) باخطا

اسلاید 12: 12فریم بندی(ادامه-2)(a) تعیین ابتدا و انتهای فریم با استفاده از بایت پرچم (b) چهارتوالی بایت قبل و بعد از درج بایت

اسلاید 13: 13فریم بندی(ادامه-3)درج بیت: (a) داده اولیه (b) داده هابصورتی که روی خط فیزیکی ارسال می شود. (c) داده ها به صورت که درگیرنده دریافت می شود.

اسلاید 14: 14کنترل خطا و کنترل جریانکنترل خطا چگونگی ارسال فریم ها به ترتیب وسالماطلاع از رسیدن بسته به مقصدتایمر برای حل مشکل فریم ناپدید شدهکنترل جریانکنترل جریان براساس بازخورکنترل جریان براساس نرخ

اسلاید 15: 15کشف و تصحیح خطاکدهای تصحیح خطا (error-correcting code)قابل استفاده در کانال های پر از خطا مانند لینک های بیسیمکدهای کشف خطا (error-detecting codes)قابل استفاده در کانال های قابل اطمینان مانند فیبرنوریفاصله همینگبه ازای کشف d خطا به کدی بافاصله همینگ d+1طراحی کدی با m بیت داده اصلی و r بیت افزونگیبه منظور کشف تمام خطاهای تک بیتی

اسلاید 16: کشف و تصحیح خطا (ادامه)کلمه کد = داده چک کننده(افزونگی) + داده اصلیn = m + rوزن کد(W): تعداد بیت‌های 1 موجود در کدفاصله همینگ (d): تعداد بیت‌های 1 متفاوت در دو کدبا XOR دو کد به دست می‌آیدفاصله همینگ یک مجموعه کد = حداقل فاصله همینگ آن مجموعه16 10011011= c1 XOR 10101101 = c2 ------------------ W(00110110) = 4D(c1, c2) = 4

اسلاید 17: کنترل خطاپیش رو (Forward Error Correction) : کدهای افزونه برای تشخیص و تصحیح خطاپس رو(Backward Error Correction): کدهای افزونگی فقط برای تشخیص خطا17

اسلاید 18: کشف خطاسوال: اگر فاصله همینگ در یک مجموعه کد برابر 5 باشد. چند بیت خطا قابل تشخیص است؟ چند بیت خطا قابل تصحیح است؟ چرا؟18

اسلاید 19: کشف خطاجواب:برای تشخیص d خطا به کدی با فاصله همینگ d+1 نیاز استبرای تصحیح d خطا به کدی با فاصله همینگ 2d+1 نیاز است19

اسلاید 20: تشخیص خطا20روش Block Sum Check

اسلاید 21: تشخیص خطا21روش Block Sum Check

اسلاید 22: تشخیص خطاروش Block Sum Check22R6b6b5b4b3b2b1b0010100101010010010110011010010010011011100111011

اسلاید 23: سوالبرای ایجاد کدی با m بیت داده اصلی و r بیت داده افزونه که بتواند یک بیت خطا را تصحیح کند، حداقل r چقدر باید باشد؟23

اسلاید 24: جوابکلمه کد: n=m+r تعداد پیام های مجاز 2mبرای تشخیص و تعیین محل وقوع یک بیت خطا: هر پیام به n کد غیر مجاز با فاصله یک نیاز داردحداقل تعداد کدهای لازم که نبایستی همپوشانی داشته باشند: 2m(n+1)کل ترکیبات ممکنه:2n24

اسلاید 25: همینگ کدبرای تصحیح خطاهای تک بیتی بکار می‌رودشماره گذاری بیت‌ها از چپ به راستشماره هایی که توانی از دو هستند (1،2،4،8،...) بیتهای افزونه چک کننده (r) و مابقی (3،5،6،7،9،...) داده اصلی(m)مثال: توازن بیت داده 13 توسط بیت‌های افزونه 8+4+1 چک می‌شود25

اسلاید 26: همینگ کد برای تصحیح خطاهای فورانیتصحیح حداکثر k بیت خطای پشت سرهمقرار دادن k کلمه کد m+r بیتی کنار هم (سطر به سطر)ارسال ستونی به جای ارسال سطریاگر حداکثر k خطای فورانی اتفاق بیافتد، یعنی در هر کلمه حداکثر یک بیت خطا اتفاق افتاده استr بیت لازم برای تصحیح t بیت خطا26

اسلاید 27: 27کشف و تصحیح خطا(ادامه)استفاده از کد همینگ برای تصحیح خطاهای فورانی

اسلاید 28: کد افزونگی چرخه‌ای (CRC)قوانین:استفاده از تقسیم مبنای دوجمع و تفریق پیمانه دو (XOR)نمایش عدد با چند جمله‌ای (10111 = x4+x2+x1+1)توافق فرستنده و گیرنده بر یک چند جمله ای G(x)کم ارزش‌ترین و پر ارزش‌ترین بیت‌های G(x) باید یک باشد28

اسلاید 29: کد افزونگی چرخه‌ای (ادامه)روال تولید CRC:اضافه کردن r بیت صفر به سمت راست داده اصلی(m)r یکی کمتر از تعداد بیت‌های G(x) تقسیم داده جدید بر G(x)افزودن باقیمانده تقسیم به صورت r بیتی به سمت راست داده اصلی و ارسال29

اسلاید 30: 30کد افزونگی چرخه‌ای (ادامه)محاسبه مجموع چک کد چند جمله ای

اسلاید 31: کد افزونگی چرخه‌ای (ادامه)اگر در گیرنده کد ارسالی بر G(x) تقسیم شود باقیمانده باید صفر شود در غیر این‌صورت خطا سوال: در روش CRC چه هنگام خطا در گیرنده غیر قابل تشخیص خواهد بود?31

اسلاید 32: کد ارسالیبا بروز خطای E(x) داریمبا انجام عمل تقسیم در گیرنده ...کد افزونگی چرخه‌ای (ادامه)32M(x)R(x)T(x) =M(x)R(x)T’(x) =T(x)+E(x)

اسلاید 33: می‌توان ثابت کرد که هیچ چند جمله‌ای با تعداد جملات فرد بر x+1 بخش‌پذیر نیست. اگر تعداد خطاها فرد باشد، چند جمله‌ای خطا فرد است لذا بر x+1 بخش‌پذیر نخواهد بوداثبات: برهان خلف، E(x) یک چند جمله‌ای با تعداد جملات فرد که بر x+1 بخش‌پذیر است آنگاه قابلیت تشخیص کد CRC33کلیه خطاهای تک بیتی قابل تشخیص هستند (E(x) = xi)E(x) باید حداقل دو جمله داشته باشد تا قابل شناسایی نباشداگر G(x) بر x+1 بخش‌پذیر باشد آنگاه تمامی خطاهای فرد قابل تشخیص هستند. چرا؟

اسلاید 34: قابلیت تشخیص کد CRC(ادامه)اگر G(x) حداقل دارای 3 جمله باشد آنگاه تمامی خطاهای دو بیتی قابل تشخیصاگر باقیمانده r بیتی باشد آنگاه تمام خطاهای فورانی با طول کوچک‌تر یا مساوی rاکثر خطاهای فورانی با طول بیشتر از r احتمال عدم تشخیص خطاهای فورانی به طول r+1 برابر 1/(2r-1)احتمال عدم تشخیص خطاهای فورانی به طول بیشتر از r+1 برابر 1/2r34

اسلاید 35: توابع مولد استاندارد در CRCCRC-12 وقتی بکار میرود که طول کاراکتر 6 بیت باشدCSC-16 وقتی بکار میرود که طول کاراکتر 8 بیت باشددر CRC-CCITT تمام خطاهای منفرد، مضاعف، تمام خطاهایی با تعداد بیت فرد، تمام خطاهای پیوسته به طول 16 و یا کمتر، درصد بالایی از خطاهای 17و 18 بیتی و بیشتر قابل تشخیص است35

اسلاید 36: 36پروتکل های ساده لینک داده فرض های اساسی در مدل ارتباطی زیر بنایی مستقل بودن پروسس های فعال ارتباط لایه ها از طریق ردوبدل کردن پیامسرویس اتصال-گرای قابل اعتمادماشین مبدا منبع بی پایانی از داده ها داردکامپیوتر ها هیچ گاه از کار نمی افتندفقط داده خالص به لایه شبکه داده می شود

اسلاید 37: 37تعاریف پروتکل به زبان C

اسلاید 38: 38تعاریف پروتکل به زبان c (ادامه)

اسلاید 39: 39پروتکل های ساده لینک داده پروتکل یکطرفه نامحدودداده ها فقط در یک جهت منتقل می شوند.لایه شبکه در گیرنده و فرستنده آماده به کار.زمان پردازش نادیده گرفته می شود.بافر محدودیتی ندارد.کانال ارتباطی کامل و بدون خطا.

اسلاید 40: 40پروتکل یکطرفه نامحدود

اسلاید 41: 41پروتکل های ساده لینک داده(ادامه) پروتکل توقف-انتظار یکطرفهداده ها در یک جهت منتقل می شوند(دوطرفه ناهمزمان)کانال ارتباطی کامل و بدون خطابرگردان بازخور به عنوان مجوز ارسال فریم بعدیپروتکل توقف-انتظار (stop-and-wait)

اسلاید 42: 42پروتکل توقف-انتظار یکطرفه

اسلاید 43: 43پروتکل های ساده لینک داده(ادامه-2) پروتکل یکطرفه برای کانال های نویز دارداده ها در یک جهت منتقل می شوند.(دوطرفه ناهمزمان)کانال ارتباطی می تواند دارای نویز باشد.فریم ها دارای یک شماره ترتیبی هستند.نام های دیگر این پروتکل PAR (تصدیق دریافت مثبت با ارسال مجدد) یا ARQ (درخواست تکرار خودکار)

اسلاید 44: 44پروتکل یکطرفه برای کانال های نویز دار

اسلاید 45: 45پروتکل یکطرفه برای کانال های نویز دار (ادامه)

اسلاید 46: 46پروتکل های پنجره لغزندهکانال های دوطرفه و راه های دستیابی به آنسوار(کول) کردن (piggyback)، مزایا و معایباصطلاحات پنجره دریافت، پنجره ارسالپروتکل پنجره لغزنده 1-بیتیپروتکل ”N تا به عقب برگرد“پروتکل تکرارانتخابی

اسلاید 47: 47پروتکل های پنجره لغزنده(ادامه)یک پنجره لغزنده یک واحدی، با شماره ترتیبی 3-بیتی. (a) درشروع کار.(b) بعد از ارسال اولین فریم. (c) بعد از آنکه اولین فریم دریافت شد.(d) بعد از آنکه فرستنده اولین تصدیق دریافت را گرفت

اسلاید 48: 48پروتکل های پنجره لغزنده (ادامه-2)پروتکل پنجره لغزنده 1-بیتیپنجره گیرنده و پنجره فرستندهپروتکل توقف-انتظاروضعیت ارسال اولین فریم بطور همزماننقش کلیدی فیلد تصدیق

اسلاید 49: 49پروتکل پنجره لغزنده 1-بیتی

اسلاید 50: 50پروتکل پنجره لغزنده 1-بیتی(ادامه)

اسلاید 51: 51پروتکل پنجره لغزنده 1-بیتی(ادامه-2)دوسناریوی پروتکل 4 (a) حالت عادی (b) حالت غیرعادی. اعداد داخل پرانتز از چپ به راست عبارتند از : seq، ackو شماره بسته. بسته هایی که پذیرفته و به لایه شبکه تحویل می شوند، با * مشخص شده اند.

اسلاید 52: 52پروتکل های پنجره لغزندهپروتکل ”N تا به عقب برگرد“فرستادن w فریم به جای یک فریماگر پهنای باند × تاخیر رفت وبرگشت عددی بزرگ باشدآنگاه پنجره ارسال بزرگ تکنیک لوله کشی(bR + l) / l = بهره خط در روش توقف و انتظار اگر bR > l کارایی خط زیر 50%مقابله با خطا : 1.رهیافت N تا به عقب برگرد 2.تکرار انتخابیl:طول فریم(بیت)b:پهنای باند(بیت بر ثانیه)R:تاخیر رفت و برگشت (ثانیه)

اسلاید 53: 53مثالمقابله با خطا در خط لوله .تاثیر خطا وقتی که (a) اندازه پنجره دریافت گیرنده 1 است، و (b) پنجره دریافت بزرگ است.

اسلاید 54: 54پروتکل ”N تا به عقب برگرد“ (ادامه)

اسلاید 55: 55پروتکل ”N تا به عقب برگرد“(ادامه-2)

اسلاید 56: 56پروتکل ”N تا به عقب برگرد“(ادامه-3)

اسلاید 57: 57پروتکل ”N تا به عقب برگرد“(ادامه-4)

اسلاید 58: 58شبیه سازی چند تایمر بوسیله نرم افزار

اسلاید 59: 59پروتکل های پنجره لغزنده پروتکل تکرار انتخابیمناسب برای خطوط پر نویزبافر کردن فریم های سالم بعد از یک یا چند فریم معیوب پنجره ارسال متغیر ولی پنجره دریافت ثابتمساله همپوشانیتصدیق دریافت منفی

اسلاید 60: 60پروتکل تکرار انتخابی

اسلاید 61: 61پروتکل تکرار انتخابی(ادامه)

اسلاید 62: 62پروتکل تکرار انتخابی (ادامه-2)

اسلاید 63: 63پروتکل تکرار انتخابی(ادامه-3)

اسلاید 64: 64پروتکل تکرار انتخابی(ادامه-4)(a) پنجره های ارسال ودریافت هفت تایی در لحظه شروع. (b) بعد از رسیدن هفت فریم به مقصد، وقبل از بازگشت تصدیق دریافت به فرستنده. (c) پنجره های ارسال و دریافت چهارتایی در لحظه شروع. (d) بعد از رسیدن چهار فریم به مقصد، و قبل از بازگشت تصدیق دریافت به فرستنده

اسلاید 65: 65چند نمونه از پروتکل های لینک دادهHDLC کنترل سطح بالای لینک دادهلایه پیوند داده در اینترنت

اسلاید 66: 66چند نمونه از پروتکل های لینک داده(ادامه)فرمت فریم در پروتکل های بیت-گرا

اسلاید 67: 67چند نمونه از پروتکل های لینک داده(ادامه-2)فیلد کنترل در یک (a) فریم اطلاعاتی (b) فریم سرپرستی (c) فریم بدون شماره

اسلاید 68: 68چند نمونه از پروتکل های لینک داده(ادامه-3)یک کامپیوتر خانگی می تواند نقش میزبان اینترنت رابازی کند.

اسلاید 69: 69چند نمونه از پروتکل های لینک داده(ادامه-4)فرمت فریم کامل PPP برای حالت بدون شماره

اسلاید 70: 70چند نمونه از پروتکل های لینک داده(ادامه-5)مراحل ساده شده برقراری و قطع خط در پروتکل PPP

اسلاید 71: 71چند نمونه از پروتکل های لینک داده(ادامه-6)انواع فریم های LCP

اسلاید 72: 72پایان