ما هو بروتوكول الانتقال الشجري التكيفي في الشبكات ATWP

في شبكات الحاسوب وفي البروتوكولات القائمة على التصادم مثل “ALOHA” يُسمح لجميع المحطات بنقل إطار دون محاولة اكتشاف ما إذا كانت قناة الإرسال خاملة أو مشغولة، وهذا يعمل بشكل جيد للغاية في ظل الأحمال الخفيفة، وتحت الأحمال الثقيلة تُعتبر البروتوكولات الخالية من الاصطدامات مناسبة حيث يتم حل الوصول إلى القناة في فترة التنازع التي تقضي على احتمالات الاصطدام.

ما هو بروتوكول Adaptive Tree Walk

بروتوكول “Adaptive Tree Walk”: هو تقنية لنقل البيانات عبر القنوات المشتركة التي تجمع بين مزايا البروتوكولات، كالبروتوكولات القائمة على التصادم والبروتوكولات الخالية من الاصطدام.

• “ATWP” هي اختصار لـ “Adaptive Tree Walk”.

أساسيات بروتوكول Adaptive Tree Walk

في بروتوكول “Adaptive Tree Walk” يتم تقسيم المتمركزين إلى مجموعات بطريقة هرمية، كما يتم تقسيم فترة التنازع إلى فترات زمنية منفصلة، ولكل فترة زمنية تكون حقوق التنازع للمحطات محدودة وتحت الأحمال الخفيفة يمكن لجميع المحطات المشاركة للتنافس على كل فتحة مثل “ALOHA“، ومع ذلك في ظل الأحمال الثقيلة يمكن فقط لمجموعة واحدة أن تجرب فتحة معينة.

بروتوكول “ATWP” هو بروتوكول محدود التنازع يمكن استخدامه لتحديد الترتيب الذي يرسل به عدد من المحطات إطاراتها في الشبكة، حيث في هذه المهمة تحتاج إلى كتابة برنامج يقوم بتنفيذ “ATWP” وفي هذه المهمة يكون هناك الافتراضات التالية:

1- الوقت المحدد

الوقت المحدد: هو الوقت مقسم إلى سلسلة من الفترات الزمنية مثل: الفترة الزمنية 0 والفترة الزمنية 1 والفترة الزمنية 2.

2- نموذج الشبكة

هناك محطات “N” في الشبكة قيد التحقيق، كما أنّه في هذا التخصيص يمكن أن تكون N هي 2 أو 4 أو 8 أو 16، وبعد تهيئة الشبكة يكون لبعض المحطات في الشبكة إطار لإرساله وكما أنّ كل من هذه المحطات لديها إطار واحد فقط لإرساله.

3- اسم المحطة

اسم المحطة: هو ببساطة حرف كبير. عندما تكون هناك محطات N في الشبكة، يتم استخدام الأحرف الكبيرة “N” الأولى وتبدأ من “A” لتسمية هذه المحطات، وعلى سبيل المثال عندما تكون هناك محطتان في الشبكة، فإنّ أسمائهما هي “A” و”B”، وعندما تكون هناك 4 محطات في الشبكة فإنّ أسمائها هي “A” و”B” و”C” و”D”.

4- قناة واحدة

لا توجد سوى قناة إرسال واحدة في الشبكة قيد التحقيق.

مبدأ عمل بروتوكول Adaptive Tree Walk

في بروتوكول المشي الشجري التكيفي يتم ترتيب المحطات أو العقد في شكل شجرة ثنائية كما هو موضح في الرسم التخطيطي، كما تمثل العقد الداخلية أي المميزة من 0 إلى 6 المجموعات بينما تمثل العقد الطرفية أي المميزة من A إلى H المحطات المتنافسة للوصول إلى الشبكة.

في البداية يُسمح لجميع العقد (“A” و”B”……. و”G” و”H”) بالتنافس على القناة، حيث إذا نجحت العقدة في الحصول على القناة فإنّها تنقل إطارها، وفي حالة الاصطدام يتم تقسيم العقد إلى مجموعتين هما:

• المحطات ضمن المجموعة 1، أي “A” و”B” و”C” و”D”.

• المحطات ضمن المجموعة 2، أي “E” و”F” و”G” و”H”.

والعقد التي تنتمي إلى واحد منهم فقط مسموح لها بالمنافسة، حيث بالنسبة إلى الفتحة 1 يُسمح لجميع المحطات ضمن المجموعة 1 بالمنافسة، وإذا نجحت إحدى المحطات في الحصول على القناة فإنّها تنتقل حتى اكتمالها، وفي الفتحة التالية أي الفتحة 2 يمكن لجميع المحطات ضمن المجموعة 2 التنافس، ومع ذلك في حالة حدوث تصادم يتم تقسيم المحطات إلى مجموعات على النحو التالي:

• المحطات ضمن المجموعة 3، أي “A” و”B”.

• المحطات ضمن المجموعة 4، أي “C” و”D”.

• المحطات ضمن المجموعة 5، أي “E” و”F”.

• المحطات ضمن المجموعة 6، أي “G” و”H”.

ومن أجل تحديد موقع المحطات المتنافسة يتم استخدام خوارزمية بحث العمق أولاً، كما يتم تطبيق نفس مبدأ الخلاف وفقط لتلك المجموعات التي لديها بعض المحطات المتنافسة، كما يستمر التقسيم في حالة حدوث تصادمات حتى تحتوي كل مجموعة على عقدة واحدة فقط، وفي البداية يُسمح لجميع العقد بمحاولة الحصول على القناة، وإذا كانت قادرة على الحصول على القناة فإنّها ترسل إطارها.

وإذا كان هناك تصادم يتم تقسيم العقد إلى مجموعتين متساويتين وتتنافس واحدة فقط من هذه المجموعات على الفتحة 1، حيث إذا استحوذ أحد أعضائها على القناة فسيتم حجز الفتحة التالية للمجموعة الأخرى، ومن ناحية أخرى إذا كان هناك تصادم فسيتم تقسيم هذه المجموعة مرة أخرى وتتبع نفس العملية.

خصائص بروتوكول Adaptive Tree Walk

• يقسّم مجموعة المحطات وحدد التنازع على كل فجوة.

• تحت الحمل الخفيف، يمكن للجميع تجربة كل فتحة مثل “aloha”.

• تحت الحمل الثقيل، يمكن لمجموعة فقط تجربة كل فتحة.

• تعامل مع كل محطة على أنّها ورقة شجرة ثنائية.

• الفتحة الأولى بعد الإرسال الناجح وجميع المحطات.

• يمكن محاولة الحصول على الفتحة أي تحت عقدة الجذر.

• إذا لم يكن هناك تعارض فلا بأس في حالة وجود تعارض، وفقط العقد الموجودة أسفل الشجرة الفرعية هي التي تحاول المحاولة مع العقد التالية.

أساسيات عمل بروتوكول ATW

عندما تحاول محطتان أو أكثر إرسال إطاراتها في نفس الفترة الزمنية، فسيحدث تضارب بسبب وجود قناة مشتركة واحدة فقط في الشبكة، وفي هذا السيناريو سوف تتلف الإطارات وبالتالي يجب إعادة إرسال هذه الإطارات، لذلك يكون هناك حاجة إلى:

• استرداد القيمة المحددة لـ “N” والمحطات التي لديها إطار لإرساله من ملف الإدخال، وعرض قيمة “N” والمحطات التي لديها إطار لإرساله على الشاشة.

• استخدم “ATWP” لتحديد المحطات التي سترسل إطاراً خلال الفترات الزمنية القادمة، وعرض أسماء المحطات التي قد ترسل إطاراً خلال الفترات الزمنية القادمة على الشاشة.

• كما يوجد ملف الإدخال وفي هذه المهمة يوجد ملف إدخال واحد “Input.txt”، وهذا الملف يتضمن سطرين.

• يتم تحديد القيمة المحددة لـ “N” في السطر الأول، ويتم سرد المحطات التي لديها إطار لإرساله في السطر الثاني.

إنّ أسماء المحطات مفصولة بفواصل ويتم توفير مثال “Input.txt”، حيث محتوى المثال “Input.txt” هو: 8 C، E، F، H بالنسبة لهذا المثال لملف الإدخال، يجب عرض الجمل التالية على الشاشة وبالنسبة إلى مثال الشبكة سينظم “ATWP” المحطات باستخدام الشجرة التالية، وبمجرد توفر قيمة “N” والمحطات التي تحتوي على إطار لإرساله يمكن استخدام “ATWP” لتحديد المحطات التي سترسل إطاراً خلال الفترات الزمنية القادمة.

كما يجب عرض المعلومات حول المحطات التي سترسل إطاراً في الفترات الزمنية القادمة على الشاشة وعلى وجه التحديد يجب أن يكون هناك سطر واحد لكل فترة زمنية، كما يتضمن كل سطر ثلاثة أجزاء وهي رقم الفترة الزمنية وقائمة المحطات التي سترسل إطاراً في الفترة الزمنية، ونتائج الفترة الزمنية وإذا تم إرسال إطار بنجاح خلال الفترة الزمنية تكون نتيجة المهلة الزمنية “نجاح”، وبخلاف ذلك تكون نتيجة المهلة الزمنية “تعارض” وبمجرد عرض السطر المقابل للمهلة الزمنية المستخدمة لإرسال الإطار الأخير بنجاح ،