دانشجویان کامپیوتر اصفهان

وب سایت سابق(( دانشجویان کامپیوتر جهاد دانشگاهی یزد - خرم آباد ))

مختصری در مورد خطا در شبکه های کامپیوتری

 

سلام به دوستان عزیز......

تقدیم به آنهایی که حقیقت بر دل و جانشان تجلی کرده است ، اگر چه از این اوراق بی بها مستغنیند......

در این مطلب تحقیقی هست که توسط استاد مومنی  مربوط به درس نفوذگری در شبکه به ما داده شده است . امیدوارم در نوشتن این تحقیق کمک کنه.

 

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


نویز حرارتی :

این نویز به دلیل حرکت اتفاقی الکترونها بوجود می آید و با افزایش دما ، شدت این نویز هم به صورت خطی تقویت می شود. بخصوص در مداراتی مثل تقویت کننده های نیمه هادی با ضرایب تقویت و بهره بالا ، تاثیر این نویز حساسیت بیشتری دارد. اثر این خطا کاملاً تصادفی است و احتمال خطا در هر بیت از دیگری است.

 

 

شوکهای الکتریکی :

این نوع از نویز به دلیل قطع و وصل کلیدها ، سیمها ، سوئیچهای الکترونیکی یا رعد و برق بوجود می آید و نوعی خطای انفجاری را باعث می شود؛یعنی مجموعه گسترده ای از بیتها که روی کانال ها در جریانند، به یکباره خراب می شوند. به عنوان مثال اگر یک شوک الکترونیکی به اندازهMS 10  ادامه یابد و اطلاعات روی کانال با سرعتMBPS1 در جریان باشد ، با فرض آنکه طول متوسط فریمها KB 1در نظر گرفته شود، این شوک می تواند تا ده فریم را به کل نابود کند ؛ به این معنا که فرستنده 10 فریم را فرستاده ولی گیرنده هیچ فریمی دریافت نکرده است. کشف یا تصحیح خطای انفجاری احتمال خطا در هر بیت مستقل از بیتهای مجاور نیست.

 

نویز کیهانی :

این نوع خطا ناشی از حرکات کیهانی ، کهکشانها ، وضعیت ستارگان و خورشید و امثال آن می باشد و تاثیر آن بیشتر بر روی کانال های رادیویی است .

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

 

ساده ترین روش کشف خطا:

ساده ترین روش کشف خطا ، اضافه کردن بیت توازون به داده هاست. در این روش به ازای هر بایت از اطلاعات یک بیت توازون اضافه می شود؛ این بیت باید به گونه ای انتخاب و اضافه شود که مجموع تعداد بیت های 1، همیشه زوج یا فرد باشد.

مثال :

 

01101001   بایت اصلی

Odd  parity  1   بیت توان فرد

Even Parity0  بیت توان زوج

 

بیت توازن در انتها یا گاه در ابتدای هر بایت ( یا کلمه ) اضافه و ارسال می شود. گیرنده می تواند با بررسی بیت توازن خطای احتمالی در بایتهای داده را کشف کند ، ولی این روش وقتی موثر است که تعداد خطاهای رخ داده زوج نباشد. 

 

چک سام (Checksum) چیست ؟
**********

این اصطلاح از ترکیب دو واژه "Check" به معنی مقایسه و تطبیق و "Sum" به معنی مقدار ایجاد شده است .
چک سام عموماً قسمتی از یک فایل است که وظیفه آن حفاظت از کل فایل در برابر تغییرات میباشد . این قسمت از فایل شامل بایت یا بایتهایی (تیبلی) است که وظیفه آن نگهداری مقدار چک سام کل فایل منهای خود همین بایتها و ( Ignore Bytes ) میباشد . به زبان ساده تر میتوان گفت که اگر چک سام کل یا یک قسمت از فایلی را بر اساس الگوریتمی خاص محاسبه کرده و خروجی آن را در محلی از یک فایل و در لابلای بایتها یا پکتها قرار دهیم ، چک سامی برای فایل تعریف کرده ایم که در این فایل ،اگر تنها مقدار چک سام قسمتی از فایل را محاسبه کرده باشیم ، به قسمت محاسبه نشده این فایل اصطلاحاً ( Ignore Bytes ) گفته میشود . یعنی این قسمت در محاسبه چک سام منظور نشده است و از آن چشم پوشی کرده ایم . پس در محاسبه بعدی چک سام هم بایستی از آن چشم پوشی کنیم .

مثال کاملا واضح :
در امیولیتور سامسونگ 9500 محل قرار گیری چک سام در بایتهای ابتدایی 10 و 11 فایل قرار دارند . اگر هر آفست را بر مبنای هگزادسیمال (16) در نظر بگیریم ، این چک سام در آفست اول و در بایتهای 10 و 11 امیولیتور قرار گرفته است . پس از تغییرات در پیکر فایل ، نوبت به محاسبه چک سام میرسد . ما در امولیتور سامسونگ با چک سام از نوع الگوریتم Chechsum16 بیتی روبرو هستیم .

نکته : هر 1 بایت (Byte) برابر با 8 بیت (Bit) دیتا میشود .

پس چک سام 16 بیتی ما برابر با دوبایت میشود ! که گفتیم مکان قرار گیری آن در آفست نخست و در بایتهای 10 و 11 قرار دارد .
ولی در امیولیتور سامسونگ 9500 ما با بایتهای خنثی ( Ignore Bytes ) هم روبرو هستیم و میدانید که در الگوریتم محاسبه چک سام ، از بایتهای نامبرده باید چشم پوشی کرد . محل این بایتهای ایگنور در امیولیتور سامسونگ همان آفست نخست میباشد . یعنی آفست نخست این امیولیتور که 16 بایت فرض میشود، شامل دو بایت چک سام و 14 بایت خنثی (Ignore Bytes) است . پس برای محاسبه چک سام این فایل بایستی آفست نخست را اصلاً محاسبه نکنیم . به گویش ساده تر ما از آفست دوم یا بایت 17 تا آفست آخر فایل را بر اساس الگوریتم Chechsum16 بیتی محاسبه و مقدار بدست آمده را در بایت 10 و 11 آفست نخست (محل قرار گیری مقدار چک سام) مینویسیم .


برخی از الگوریتمهای چک سام :

برخی از الگوریتمهای سادهء چک سام ، الگوریتم 8 - 16 - 32 - 64 بیتی و CRC32 - CRC16 بیتی و ... میباشند .
دقت کنید که بین الگوریتم چک سام و الگوریتم CRC تفاوتهایی هم هست که بعداً براتان توضیح خواهم داد .
چک سام بر اساس هر الگوریتمی که باشد تعداد بیتهای (Bit) آن تقسیم بر 8 برابر با تعداد بایت (Byte) میشود .
مثلاً اگر چک سام بر اساس الگوریتم Checksum8 بیتی باشد مقدار چک سام ما 1 بایت است .
اگر چک سام بر اساس الگوریتم Checksum16 باشد مقدار چک سام ما 2 بایت است .
و اگر چک سام بر اساس الگوریتم Checksum32 باشد مقدار چک سام ما 4 بایت است ... الی آخر ...

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

 

دانستنیهای لازم برای محاسبه چک سام :
برای محاسبه چک سام یک فایل ، نخست باید بدانیم که چک سام ما بر اساس چه الگوریتمی محاسبه شده است سپس بایستی مکان قرار گیری چک سام را شناسایی کنیم .
و در آخر هم باید بدانیم که آیا با " Ignore Bytes " هم طرف هستیم یا نه و اگر بله مکان آن کجاست ؟

اکنون در زمان تغییرات معقول یک فایل میتوانیم به سادگی چک سام تازه آنرا هم محاسبه و جایگزین کنیم .
گاهی وقتها هم در ویرایش یک فایل برای تعدیل مقدار چک سام ، بایتهایی به انتهای فایل اضافه میکنند که البته در این راه هم به دانستن الگوریتم چک سام در آن فایل و هم به اطلاعات پیش زمینه دیگری نیاز داریم .

 

کدهای کشف خطای CRC

***********

در روش CRC به ازای مجموعه بیت های کل یک فریم ، تعدادی بیت کنترلی به نام کد CRC محاسبه و به انتهای فریم اظافه می شود. تعداد بیتهای کد کشف خطای CRC مستقل از طول فریم و ثابت است. مبنای محاسبه کدهای CRC با استفاده از تقسیم چند جمله ای است که روش محاسبه آن با ارائه یک مثال توضیح داده شده است:

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

11100101 داده اصلی

11100101  رشته داده

76543210  موقعیت توانی

D ( X ) = 1.x7+ 1.x6+ 1.x5+ 0.x4+ 0.x4 + 0.x3 + + 1.x2+ 0.x1 + 1.x0

D( x ) = x7 + x6 + x5+ x2+ 1

ب ) بین گیرنده و فرستنده یک جمله به نام مولد قرارداد می شود . این چند جمله ای انتخابی است ولی دادای ویژگی (( کاهش ناپذیری در میدان گالوای ( 2 ) GF )) است . بحث در مورد این ویژگی خارج از حیطه این تحقیق است فعلاً فرض کنید که این چند جمله ای ، به نحوه مناسبی انتخاب شده است . در مثال مان چند جمله ای زیر را انتخاب کرده ایم:

G ( x ) = x2+ 1

ج ) برای تولید کد CRC ، ابتدا چند جمله ای داده در جمله با بزرگترین توان مولد ضرب می شود . سپس چند جمله ای xn. D ( x )  بر چند جمله ای مولد تقسیم می شود . ( n بالاترین توان چند جمله ای مولد است . ) تقسیم در مبنای 2 انجام می شود ، یعنی ضرایب جملات با توان مساوی با هم XOR خواهد شد  و تفریق معنا ندارد.

D ( x ) .x2 = x9 + x8 + x7+ x4+ x2

x9 + x8 + x7+ x4+ x2       mod  G ( x )

جواب : که در اینجا  x9 + x8 + x7+ x4+ x2 تقسیم بر x2+1  می شود .

که خارج قسمت آن : x7 + x6 + x4+ 1 و باقی مانده آن +1 بدست می آید.

د) باقیمانده xn.D ( x )  بر  D ( x ) با مقسوم جمع می شود و نتیجه به عنوان داده جدید به شکل رشته بیت ارسال می گردد. با این کار در حقیقت باقیمانده تقسیم به عنوان کد های کنترل خطا در انتهای داده ها ارسال خواهد شد.

x9 + x8 + x7+ x4+ x2+1                11100101 01

 

چند جمله ای های مولد زیر در دنیای شبکه کامپیوتری شبکه های کامپیوتری از شهرت بیشتری برخوردار دارند:

CRC- 12  G ( x ) =  x12 + x11+ x3+ x2+1

CRC- 16    G ( x ) =  x16+ x15+ x2+1

CRC – CCITT   G ( x ) =  x16+ x12+ x5+1

IEEE 802.x      G ( x ) = x32 + x26+ x23+ x22+ x12 + x11+ x10 + x8 + x7+x5+ x4+ x2+ x+1

چند جمله ای آخر برای تولید کشف خطای 32 بیتی در شبکه های مشهوری مثل اترنت و بی سیم  Wifi کاربرد دارد.

کدهای محاسبه شده CRC ، معمولاً در انتهای اطلاعات ارسال خواهد شد و پس از دریافت اطلاعات در گیرنده، مجدداً کدهایCRC برای داده ها محاسبه می شوند و نتیجه با کد ارسالی  CRC مقایسه می گردد و در صورت عدم تطابق ، خطایی در داده ها وجود دارد و داده ها فاقد اعتبار است. اگر مولد CRC مناسب انتخاب شود، احتمال آنکه خطای بروز کند ولی گیرنده قادر به کشف آن نباشد، کمتر از0.002 است. دقت کنید که عمل محاسبه کدهای CRC و همچنین بررسی خطا از طریق تراشه های سخت افزاری انجام می شود تا سرعت عمل بالا برود. این تراشه ها بسادگی و از طریق شیفت ریجستری فیدبک دار و گیتهای منطقی ساده مثل XOR پیاده می شود.

 

 

                                                                                         پایان


نویسنده : م . رحمتی - ساعت ۱٢:٤٦ ‎ق.ظ روز سه‌شنبه ۱۳۸۸/٩/۳
نظرات ()    |   لینک ثابت    |   تگ کامپیوتر


Powered By Persianblog.ir - Designed By Payam salami pargoo