روش CRC

روش CRC: این روش یکی از قوی ترین روش های تشخیص خطا بود . و بیشترین استفاده را در محیط شبکه دارد . در این روش طی یک فرایند پردازشی اندازه یا تعداد بیت های ارسالی افزایش می یابد و این افزونگی ما را قادر به تشخیص خطا می کند «  information Redundancy » افزونگی هایی که به اطلاعات اضافه می شوند تا امکان اجرای الگوریتم های خطایابی به وجود آید را می توان به دو دسته تقسیم کرد. افزونگی های Separable در این روش اطلاعات دست نخورده باقی می ماند و افزونگی به انتهای آن اضافه می شود .

با استفاده از این روش ها همزمان با عملیات خطایابی می توان از اطلاعات استفاده کرد که در صورت تشخیص خطا استفاده از اطلاعات متوقف خواهد شد . معمولاً در سیستم های Real Time استفاده می شود . روش دوم الگوریتم های Non Separable هستند در این روش ها اطلاعات افزونه با اطلاعات اصلی ترکیب شده و اطلاعاتی با طول بیشتر به وجود می اید در این حالت در نگاه اول اطلاعات اصلی در دسترس نیستند و بایستی پردازش تشخیص خطا بر روی آن انجام شود تا هم اطلاعات اصلی استخراج شوند و هم در صورت وجود خطا تشخیص داده شوند روش CRC نمونه ای از این حالت است

 در روش CRC یک رشته بیتی در 2 طرف شبکه به عنوان مبنای عملکرد CRC مورد توافق قرار می گیرد به طور خلاصه در روش CRC در طرف ارسال کننده رشته اصلی در رشته مبناء ضرب شده و نتیجه ارسال می شود در مقصد نتیجه به همان رشته مبناء تقسیم خواهد شد رشته در صورتی قابل قبول است که باقی مانده تقسیم صفر شود . فرآیند عملکرد به این شرح است که ابتدا هر دو رشته را به صورت نمایش چند جمله ای می نویسیم سپس این دو چند جمله ای را به هم ضرب می کنیم . هنگام جمع نتایج به دست آمده از ضرب هر رقم عدد مبناء در داده ضرایب 2 را از نتیجه کم می کنیم . با جمع به پیمانه 2 انجام می شود ( جمع ماجول 2 )  ( a + b ) mod 2  در نتیجه توان هائی که دارای ضرایب زوج هستندحذف شده و توان هائی که دارای توان فرد هستند با ضریب 1 نوشته خواهد شد. معادل باینری حاصلضرب اطلاعاتی است که بایستی ارسال شونداگر طول داده اولیه n بیت و درجه جمله مبناء k باشد.   طول خروجی  ( Data ) بقیه برابر  n + k بیت خواهد بود .

در طرف گیرنده رشته دریافت شده  به رشته مبناء تقسیم شده رشته خارج قسمت نشان دهنده اطلاعات اصلی ماست و باقی مانده صفر نشان دهنده قبول اطلاعات و نبود خطا در آن است .توجه داشته باشید که در هنگام تقسیم نیز جمع اعداد در پیمانه 2 انجام خواهد شد . در محیط هایی که خطای ما تک بیتی است در صورت بروز خطا مقدار باقی مانده شماره بیت ( با خطا مواجه شده ) خواهد بود

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

11110001011                     

کنترل جریان یا Flow control در لایه Data Link احتمال اینکه اطلاعات کم شوند وجود ندارد ولی ممکن است اطلاعات با خطا روبرو شوند در این شرایط یا بایستی توسط الگوریتم های تصحیح خطا داده اصلی را بازیابی کنیم که این روش معمولاً کند و پرهزینه است و یا در شبکه های پرسرعت معمولاً از درخواست مجدد اطلاعات خطا دار استفاده می کنیم این فرآیند یکی از وظایف کنترل جریان در لایه Data link است . کار دیگری که در عملیات کنترل جریان انجام می شود کنترل کردن ایستگاههای سریع و تنظیم کردن آنها با سرعت ایستگاههای کند است . این عمل به چند روش صورت می گیرد که عبارتند از این روش ( Stop & wait ) ساده ترین روش کنترل جریان است عملکرد آن بدین صورت است که ایستگاه فرستنده پس از ارسال هر سیستم منتظر حصول اطمینان از دریافت صحیح بسته می ماند برای امکان استفاده از این روش یک Frame استاندارد به نام ACK در پروتکل تعریف می شود که دریافت کننده پس از دریافت یک Frame صحیح آن را به فرستنده بر می گرداند . فرستنده پس از دریافت ACK می تواند فرم بعدی را ارسال کند.

در شبکه ها می توان 2 نوع تأخیر را برای ارسال اطلاعات در نظر گرفت :

1-  تأخیر انتشار که وابسته به طول سیم و سرعت انتشار موج بر روی سیم است و مقدار آن برای سیم همیشه ثابت است

رادیو     10⁸  *   3

سرعت انتشار= رادیو   10⁸  * 3  و سیم   رادیو 10⁸ *  2   یا

     طول سیم /سرعت انتشار  T=

تأخیر کل انتقال برابر با حاصل جمع این در مقدار خواهد بود « البته می توان تأخیر پردازش را در نظر گرفت که در کل ربطی به تأخیر انتقال ندارد » یکی ازاشکالات مهم این روش امکان از بین رفتن Frame ACK  در موقع انتقال است در این صورت ارسال کننده ه یک انتظار دائم و بی نهایت خواهد رفت برای حل این مشکل ارسال کننده بایستی از یک Timer استفاده کند و فقط تا هنگامTime out  شدن Timer منتظر خواهد بوددرصورت Time out  شدن ارسال کننده می فهمد که یا Frame اولیه به درستی ریافت نشده است و یا اینکه ACK خطا مواجه شدهاست که در هر دو صورت Frame  از ابتداارسال خواهد شد  اشکال دوم هنگامی رخ می دهد که Frame اولیه ریافت شده و ACK با خطا مواجه شود در این صورت Frame بعدی نیز همان Frame اول خواهد بود که در صورت قبول شدن توسط دریافت کننده باعث نامعتبر شدن کل اطلاعات خواهد شد  برای رفع این مشکل Frame ها شماره  گذاری شده که این شماره با Sequenced number شناخته می شود گیرنده با دریافت Frame ی که قبلاً Frame با همان Sequenced number  t دریافت کرده است Frame جدید را حذف خواهد کرد ولی ACK برای آن تولید خواهد کرد  حسن این روش در این است که ارسال کننده و دریافت کننده نیازی به بافر اضافی برای Frame های دریافت شده ندارد در این روش تأخیر به وجود آمده برای ارسال یک Frame برابر با تأخیر ارسال Frame به اضافه تأخیر انتشارFrame به اضافه تأخیر انتشارACK  می باشد.

به دو تأخیر انتشاری که برای رفت و برگشت لازم است RTT یا Run trip time زمان سفر دوره ای گفته می شود.

روش دوم  ARQ: برای از بین بردن زمان انتظار منتظر دریافت ACK برای Frame نمی ماند و فریم ها را پشت سر هم ارسال می کنند پس از ارسال هر فریم آن فریم تا زمان دریافت ACK مربوط به آن در بافر ذخیره می شود و هنگام دریافت ACK  از بافر حذف خواهد شد . در این روش به ترتیبی که فریم ها دریافت می شوند با همان ترتیب Ack ها نیز دریافت خواهند شد .دراین روش در طرف فرستنده یک بافر وجود دارد ولی در طرف دیگر گیرنده بافری وجود ندارد در نتیجه گیرنده در هر لحظه منتظر دریافت یک Frame مشخص است . در صورتی که آن Frame را دریافت نکند و یا با خطا دریافت کند یک Frame ( NACK ) برای شماره آن فریم تولید می کند تمام فریم هایی که تا فریم مورد انتظار طرف گیرنده دریافت نشود برسد حذف خواهند شد.

هنگامی که طرف ارسال کننده فریم NACK دریافت می کند از خراب شدن تمام فرم هائی که پس از فریم با شماره NACK مطلع می شود و پس از آن شروع به ارسال همان فریم ها خواهد کرد . بنابراین عمل ارسال را از چند فریم قبل تر انجام می دهد . به همین خاطر به این روش GOBACKN- ARQ گفته می شود همانطوریکه دیده می شود اطلاعاتی که به طور صحیح پس از دریافت یک فریم خراب دریافت می شوند حذف می شوند که این عیب برای این روش است . مزیت این روش هنگامی مشخص می شود که فریم ها بدون خطا پشت سر دریافت شوند در این صورت فرستنده برای دریافت ACK  منتظر نمی ماند بنابراین تأخیر انتقال  تنها برابر با تأخیر ارسال خواهد بود . تأخیر متوسط را در این روش می توان با به دست آوردن درصد فریم های خطادار و تعداد فریم های discard شده پس از دریافت یک فریم خطا دار به دست آورد.

روش سوم : روش selective reject بارزترین شکل در روش back n Go حذف شدن فریم هائی که به ترتیب نیامده اند است . بنابراین به سادگی با اضافه کردن یک بافر در گیرنده تمام فریم هایی که به درستی دریافت شده اند در آن ذخیره می شوند و فقط فریم های خطا دار دوباره فراخوانی می شوند در این صورت گیرنده فریم ها را تا دریافت ACK از گیرنده دربافر نگه می دارد و گیرنده تا وقتی که ترتیب فریم ها در بافر کامل شود به عنوان مثال در شکل بالا فریم های 2 و 3 و 4 تا وقتی که فریم 1 دوباره ارسال نشده و دریافت نشده باشد در بافر باقی می ماند و هنگام دریافت فریم 1 تمام اطلاعات به طور یکجا به لایه بالاتر تحویل داده می شود مشکل دیگری که 2 روش قبل داشتند تعداد فریم هایی که می توانستند پشت سر هم ارسال شوند بود بدین معنی که فرض کنید تأخیر انتشار بسیار طولانی بود و تا بازگشت Nack شماره 1 می توانستیم 100فریم پشت سر هم ارسال کنیم بنابراین طول بافری که در گیرنده و فرستنده بایستی تخصیص می یافت ممکن بود به طور نامحدود افزایش می یافت برای حل این مشکل از روش پنجره لرزان یا Sliding  Windows استفاده می شود در این روش یک بافر با طول محدود در هر دو طرف تعیین می شود و مدیریت آن به صورت یک صف چرخشی خواهد بود یک مشکل دیگر روش های بالا اندازهS.N   ( شماره ترتیب ) بود چرا که فریم های پشت سر هم بایستی شماره های متفاوتی را داشته باشند و این شماره از 1 شروع شد و می تواند تا بی نهایت ادامه یابد . بنابراین ذخیره این عدد می تواند بسیار پرحجم باشد  دراین روش بسته به اندازه بافر یک S.N   ( شماره ترتیب ) کوچک برای فریم ها در نظر می گیریم  و فقط توسط مدیریت صف معین می کنیم که شماره هر فریم بایستی چه عددی باشد به عنوان مثال فریم شماره 300 در یک بافر 8 خانه ای شماره ترتیب 4 را خواهد داشت 300 mod 8 = 4 فقط در طرف گیرنده یک اشاره گر وجود دارد که در هر لحظه شماره index فریمی را که بایستی دریافت شود را مشخص کنیم.

لایه data link کلاً به دو قسمت  ( LLC ) LOGIC Link Control و MAC ( Medium Access Control ) تقسیم می شود سه وظیفه گفته شده فریم بندی – چک کردن خطا – کنترل جریان وظیفه LLC و کنترل دستیابی کارت شبکه بر رسانه انتقال هنگامی که رسانه انتقال بین چندین ایستگاه مشترک است وظیفه لایه MAC است . هنگامی که یک رسانه انتقال بین چندین ایستگاه مشترک باشد فقط یکی از آنها در آن واحد می تواند ارسال یا دریافت داشته باشد. بنابراین مکانیزمی لازم است تا از ارسال همزمان 2 ایستگاه جلوگیری کند وگرنه اطلاعات ارسال شده با هم برخورد کرده و هر دو از بین می روند ( تصادم ) ساده ترین روش برای این کار عدم کنترل دسترسی به شبکه است . در این صورت این لایه خود به خود حذف شده و اصلاً وجود نخواهد داشت جبران مشکل پیش آمده در هنگام Error checking  انجام خواهد شد یعنی هر دو ارسال کننده بسته های خود را به طور همزمان ارسال می کنند و دریافت کننده ها پس از دریافت فریم خطا را در آنها تشخیص داد و به گیرنده NAck بر می گرداند. بنابراین هر دو فریم بایستی مجدداً ارسال شوند و ارسال صحیح فریم ها در کل به شانس و مقدار بار موجود بر روی شبکه بستگی دارد به این روش ، روش ALOHA گفته می شود همانطور که دیده می شود کارائی این روش بسیار پایین است .

روش دوم : روش دوره ای در این روش به طور ثابت زمان را بین ایستگاههای مختلف تقسیم می کنیم و هر ایستگاه فقط در زمان متناظر با خود می تواند ارسال کند تنها محل مدیریتی دراین روش فقط همزمان کردن ایستگاهها و مشخص کردن برهه مربوط به هر ایستگاه است مشکل این روش نیز کمی کا رآیی آن است . چرا که اگر یک ایستگاه در مدت زمان مخصوص به خود داده ای برای ارسال نداشته باشد در آن مدت نهایی باند شبکه به هدر می رود برای حل مشکل روش فوق بایستی یک ایستگاه برای مدیریت برهه ها تعیین شود در ابتداء شروع به کار هر مجموعه از برهه ها ابتدا ایستگاه مدیریت از تمام ایستگاهها می پرسد که آیا اطلاعاتی برای ارسال دارد یا نه پس از جمع کردن نتایج نتیجه را به تمام ایستگاهها اعلام می کند و به ایستگاههای ارسال کننده اعلام می کند که در چه برهه ای می توانند اطلاعات خود را ارسال کنند پس از اینکه هر ایستگاه یک  برهه ارسال کرد. عمل فوق از ابتدا اجرا می شود این کار باعث تخصیص پویایی برهه ها شده و از هدر رفتن برهه ها جلوگیری می کند . یکی از روش های که می تواند این حالت را پیاده سازی کرد در شبکه های مبتنی بر Token  است روش های فوق نمی توانستند از وجود ارسال اطلاعات بر روی رسانه انتقال اطلاعاتی کسب کنند در حالی که اگر یک ایستگاه بتواند این قابلیت را داشته باشد می تواند هنگام ارسال ابتدا به رسانه انتقال گوش دهد و فقط در صورتی ارسال می کند که اطلاعاتی بر روی رسانه وجود نداشته باشد به این روش ها اصطلاحاً CSM   ( carrier Sense multiple access ) گفته می شود .