تكون الإطارات تالفةً أحيانًا أثناء النقل كما ذُكر سابقًا، لذلك تُستخدَم شيفرة خطأ كشيفرة CRC لاكتشاف هذه الأخطاء. على الرغم من أنّ بعض شيفرات الأخطاء قويّة بما يكفي لتصحيح الأخطاء، إلا أنّ عدد البتات الإضافية عمليّا يكون أكبر من أن يعالِج نطاقَ أخطاء البتات وأخطاء الرشقات (burst) التي يمكن إدخالها إلى رابط (link) شبكة. ستكون بعض الأخطاء شديدة جدًا بحيث لا يمكن تصحيحها حتى عند استخدام شيفرات تصحيح الأخطاء (على الروابط اللاسلكية على سبيل المثال)، لذلك يجب إهمال بعض الإطارات الفاسدة. يجب أيضًا أن يستعيد بروتوكول مستوى الرابط، الذي يريد تسليم الإطارات بطريقةٍ موثوقة، بعضًا من هذه الإطارات المهمَلة أو المفقودة.
تجدر الإشارة إلى أن الوثوقية هي وظيفة يمكن توفيرها على مستوى الرابط، ولكن تهمل العديد من تقنيات الروابط الحديثة هذه الوظيفة، وعلاوةً على ذلك يُوفَّر التسليم الموثوق في كثيرٍ من الأحيان في مستويات أعلى، بما في ذلك طبقة النقل (transport) وأحيانًا طبقة التطبيق (application)، ولكن المكان الذي يجب توفيره فيه بالضبط هو موضوعٌ للنقاش ويعتمد على العديد من العوامل. سنشرح أساسيات التسليم الموثوق هنا، نظرًا لأن المبادئ شائعة عبر الطبقات، ولكن يجب أن تدرك أننا لا نتحدث عن وظيفة طبقة الربط فقط.
يُنجَز التسليم الموثوق باستخدام مزيجٍ من آليتين أساسيتين هما إشعارات الاستلام (acknowledgments) والمهلات الزمنية (timeouts). الإشعار (acknowledgment أو اختصارًا ACK) هو إطار تحكم (control frame) صغير يرسله البروتوكول إلى نظيره يخبره فيه أنه تلقى إطارًا سابقًا. يُقصد بإطار التحكم أنه ترويسة (header) بدون أي بيانات، وعلى الرغم من أن البروتوكول يمكن أن يحمِّل (piggyback) الإشعار على إطار البيانات، إلا أنه يرسَل في الاتجاه المعاكس فقط، حيث يشير "مستلم الإشعار" إلى أنه مرسل الإطار الأصلي الذي سُلِّم إطارُه بنجاح. إذا لم يتلقَّ المرسل إشعارًا بعد فترة زمنية معينة، فإنه يعيد إرسال الإطار الأصلي. يسمى هذا الإجراء المتمثل في الانتظار لفترة زمنية معينة مهلةً زمنية (timeout)، وتدعى الاستراتيجية العامة لاستخدام إشعارات الاستلام والمهلة الزمنية لتطبيق التسليم الموثوق أحيانًا طلب التكرار الآلي (automatic repeat request أو اختصارًا ARQ). يصف هذا القسم ثلاث خوارزميات ARQ مختلفة باستخدام لغة عامة، أي أننا لا نقدم معلومات مفصَّلة حول حقول ترويسة بروتوكولٍ معين.
خوارزمية توقف وانتظر (Stop-and-Wait)
أبسط مخطط لآلية ARQ هو خوارزمية توقف وانتظر. فكرة هذه الخوارزمية واضحة: ينتظر المرسل إشعارًا بعد إرسال إطارٍ واحد، قبل إرسال الإطار التالي، وإذا لم يصل الإشعار بعد فترة زمنية معينة، تنتهي مهلة المرسل ويعيد إرسال الإطار الأصلي.
يوضح الشكل السابق الخطوط الزمنية لأربعة سيناريوهات مختلفة ناتجة عن الخوارزمية الأساسية، حيث يُمثَّل جانب الإرسال على اليسار وجانب الاستقبال على اليمين، ويتدفق الوقت من الأعلى إلى الأسفل. يوضح الشكل (أ) الحالة التي يُستلم بها إشعار ACK قبل انتهاء مدة المؤقت. يوضح الشكلان (ب) و (ج) الحالة التي فُقد فيها الإطار الأصلي والإشعار ACK على التوالي، ويوضح الشكل (د) الحالة التي تنتهي فيها المهلة في وقتٍ مبكرٍ جدًا. تذكر أن كلمة (فَقد) تعني أن الإطار تالف أثناء النقل، وأن هذا التلف اُكتشف بواسطة شيفرة خطأٍ على المستقبل الذي أهمل هذا الإطار لاحقًا.
تُعد خطوط الرزم الزمنية الموضحة في هذا القسم أمثلةً لأداة مستخدمة بصورة متكررة في تدريس البروتوكولات وشرحها وتصميمها، فهي مفيدة لأنها توضح سلوك النظام الموزع بمرور الوقت، وهو أمر قد يكون من الصعب جدًا تحليله. يجب أن تكون مستعدًا لما هو غير متوقع عند تصميم بروتوكول مثل تعطل النظام أو فقد رسالة أو شيء توقعتَ حدوثه بسرعة ثم يتبين أنه يستغرق وقتًا طويلًا. يمكن أن تساعد هذه الأنواع من الرسوم البيانية في كثير من الأحيان في فهم الخطأ الذي قد يحدث في مثل هذه الحالات، وبالتالي مساعدة مصمم البروتوكول على الاستعداد لكل احتمال.
افترض أن المرسل يرسل إطارًا ثم يرسل المستقبل إشعار الاستلام، لكن هذا الإشعار إما فُقد أو تأخر في الوصول، حيث وُضحت هذه الحالة في الخطين الزمنيين (ج) و (د) من الشكل السابق. تنتهي مهلة المرسل في كلتا الحالتين ويعيد إرسال الإطار الأصلي، ولكن سيعتقد المستقبل أنه الإطار التالي، لأنه استلم الإطار الأول بصورة صحيحة وأرسل إشعارًا بذلك، وبالتالي ستزداد احتمالية التسبب في إنشاء نسخٍ مكرَّرة من الإطار لتسليمها. لمعالجة هذه المشكلة، تتضمن ترويسة بروتوكول توقف وانتظر عادةً رقمًا تسلسليًا مؤلفًا من بتٍ واحد، أي يمكن أن يأخذ الرقم التسلسلي القيمتين 0 و 1، وتتضمن الترويسةُ أيضًا الأرقامَ التسلسلية المستخدمة لكل إطار بديل، مثل ما هو موضح في الشكل الآتي. وهكذا عندما يعيد المرسل إرسال الإطار 0، يمكن للمستقبل أن يحدد أنه يرى نسخة ثانية من الإطار 0 بدلًا من أن يعتقد أنه النسخة الأولى من الإطار 1، وبالتالي يمكنه إهماله (لا يزال على المستقبل أن يرسل إشعارًا باستلامه، في حالة ضياع أول إشعار ACK).
يتمثل العيب الرئيسي في خوارزمية توقف وانتظر في أنها تسمح للمرسل بالحصول على إطار واحد فقط عن طريق الرابط في كل مرة، وقد يكون هذا أقل بكثير من سعة الرابط. افترض وجود رابط 1.5 ميجابت في الثانية مع وقت ذهاب وإياب (round-trip time أو اختصارًا RTT) يبلغ 45 ميلي ثانية على سبيل المثال. هذا الرابط لديه ناتج تأخير × حيز النطاق التراسلي (delay × bandwidth) يساوي 67.5 كيلو بت أو حوالي 8 كيلو بايت، ونظرًا لأن المرسل يمكنه إرسال إطار واحد فقط في كل RTT، وبافتراض أن حجم الإطار يبلغ 1 كيلو بايت، فهذا يعني أن الحد الأقصى لمعدل الإرسال يبلغ:
Bits-Per-Frame / Time-Per-Frame = 1024 x 8 / 0.045 = 182 kbps
أو يبلغ حوالي ثُمن سعة الرابط، وإذا كنت تريد استخدام الرابط بشكل كامل، فهذا يعني أن يتمكن المرسل من إرسال ما يصل إلى ثمانية إطارات قبل الاضطرار إلى انتظار الإشعار.
اقتباستكمن أهمية ناتج التأخير × حيز النطاق التراسلي في أنه يمثل كمية البيانات التي يمكن نقلها، حيث يجب أن تكون قادرًا على إرسال هذا القدر من البيانات دون انتظار الإشعار الأول. يشار إلى مبدأ العمل هنا غالبًا على أنه الحفاظ على الأنبوب ممتلئًا (keeping the pipe full)، حيث تقوم الخوارزميات في القسمين التاليين بهذا بالضبط.
النافذة المنزلقة (Sliding Window)
افترض مرةً أخرى السيناريو الذي يحتوي فيه الرابط على تأخير × حيز النطاق التراسلي يبلغ 8 كيلو بايت، ويكون حجم الإطارات 1 كيلو بايت. يجب أن يكون المرسل جاهزًا لإرسال الإطار التاسع في نفس اللحظة تقريبًا التي يصل فيها الإشعار ACK للإطار الأول. تسمى الخوارزمية التي تسمح لنا بالقيام بذلك بخوارزمية النافذة المنزلقة (sliding window)، ويُعطى الخط الزمني التوضيحي في الشكل التالي:
خوارزمية النافذة المنزلقة (The Sliding Window Algorithm)
تعمل خوارزمية النافذة المنزلقة على النحو التالي: أولًا يسند المرسل رقمًا تسلسليًا، يُرمز له SeqNum، لكل إطار. افترض حاليًا تجاهل حقيقة أن SeqNum يُطبَّق بواسطة حقل ترويسة ذي حجمٍ محدود، وافترض بدلًا من ذلك أنه يمكن أن يزداد لا نهائيًا. يحتفظ المرسل بثلاثة متغيرات هي: حجم نافذة الإرسال (send window size)، المشار إليه SWS، الذي يعطي الحد الأعلى لعدد الإطارات المعلَّقة (غير المعترف بها) التي يمكن للمرسل إرسالها. المتغير الثاني هو LAR الذي يشير إلى الرقم التسلسلي لآخر إشعار مُستلَم (last acknowledgment received). المتغير الثالث LFS ويشير إلى الرقم التسلسلي لآخر إطارٍ مُرسَل (last frame sent). يحتفظ المرسل أيضًا بالثابت التالي:
LFS - LAR <= SWS
هذه الحالة موضحة في الشكل التالي:
يحرّك المرسل المتغير LAR إلى اليمين عند وصول إشعارٍ بالاستلام، مما يسمح للمرسل بإرسال إطار آخر، ويربط المرسل مؤقِّتًا (timer) بكل إطارٍ يرسله، ويعيد إرسال الإطار في حالة انتهاء صلاحية المؤقت قبل استلام الإشعار ACK. لاحظ أن المرسل يجب أن يكون على استعداد لتخزين إطارات SWS مؤقتًا لأنه يجب أن يكون مستعدًا لإعادة إرسالها حتى يستلم إشعارًا بوصولها.
يحافظ المستقبل على المتغيرات الثلاثة التالية: متغير حجم نافذة الاستلام (receive window size)، والمشار إليه RWS، الذي يعطي الحد الأعلى لعدد الإطارات المخالفة للترتيب التي يرغب المستقبل في قبولها. المتغير الثاني هو LAF ويشير إلى الرقم التسلسلي لأكبر إطار مقبول (largest acceptable frame). المتغير الثالث هو LFR ويشير إلى الرقم التسلسلي لآخر إطارٍ مُستقبَلٍ (last frame received). يحافظ المستقبل أيضًا على الثابت التالي:
LAF - LFR <= RWS
هذه الحالة موضحة في الشكل التالي:
يتخذ المستقبل الإجراء التالي عند وصول إطار برقم تسلسلي SeqNum: إذا كان SeqNum <= LFR أو SeqNum > LAF، فسيكون الإطار خارج نافذة المستقبل وبالتالي يُهمَل. إذا كان LFR < SeqNum <= LAF، فسيكون الإطار داخل نافذة المستقبل ويُقبَل، ويحتاج المستقبل الآن أن يقرر ما إذا كان سيرسل إشعارًا ACK أم لا. افترض أن الرقم التسلسلي SeqNumToAck يشير إلى أكبر رقم تسلسلي لم يُرسَل إشعار استلامه بعد، بحيث تُستلَم جميع الإطارات ذات الأرقام التسلسلية الأقل من هذا الرقم التسلسلي أو تساويه. يرسل المستقبل إشعارًا باستلام الرقم التسلسلي SeqNumToAck، حتى إذا استلم رزمًا ذات أرقامٍ أعلى. يُقال أن هذه الإشعارات تراكمية (cumulative)، ثم يعيّن المستقبل LFR = SeqNumToAck ويضبط LAF = LFR + RWS.
افترض أن LFR = 5 على سبيل المثال (أي أن آخر إشعارٍ ACK أرسله المستقبل كان للرقم التسلسلي 5) وأن RWS = 4، وهذا يعني أن LAF = 9. ستُخزَّن الإطارات 7 و 8 مؤقتًا في حالة وصولها لأنها ضمن نافذة المستقبل، ولكن لا يلزم إرسال إشعار نظرًا لأن الإطار 6 لم يصل بعد، حيث يقال أن الإطارات 7 و 8 قد وصلت مخالفةً للترتيب. يمكن للمستقبل إعادة إرسال إشعار ACK للإطار 5 عند وصول الإطارات 7 و 8، ولكن هل سيصل الإطار 6؟ ربما أصبح الوقت متأخرًا لأنه فُقد في المرة الأولى وكان لا بد من إعادة إرساله، أو ربما تأخر ببساطة. يرسل المستقبل إشعارًا بوصول الإطار 8، ويزيد LFR إلى 8، ويضبط LAF على 12، في حين أنه من غير المحتمل أن تتأخر الرزمة أو تصل مخالفةً للترتيب على رابط نقطةٍ لنقطة. تُستخدم هذه الخوارزمية ذاتها في الاتصالات متعددة القفزات، حيث يكون مثل هذا التأخير ممكنًا. إذا فُقد الإطار 6 بالفعل، فستنتهي مهلة الانتظار (timeout) عند المرسل، مما يؤدي إلى إعادة إرسال الإطار 6.
لاحظ أنة تقل كمية البيانات المُرسَلة عند انتهاء المهلة، نظرًا لأن المرسل غير قادر على زيادة نافذته حتى يُرسَل إشعارٌ بوصول الإطار 6، وهذا يعني أن هذا المخطط لم يعد يحافظ على الأنبوب ممتلئًا عند حدوث فقدٍ لرزمة، وكلما طالت مدة ملاحظة حدوث فقد للرزمة، زادت خطورة هذه المشكلة. لاحظ أنه في هذا المثال كان من الممكن أن يرسل المستقبل إشعارًا سلبيًا (negative acknowledgment أو اختصارًا NAK) للإطار 6 بمجرد وصول الإطار 7، ولكن هذا غير ضروري لأن آلية مهلة المرسل الزمنية كافيةٌ لاكتشاف هذه الحالة، حيث يضيف إرسال إشعارات NAK تعقيدًا إضافيًا للمستقبل. يُسمَح أيضًا إرسال إشعارات إضافية للإطار 5 عند وصول الإطارات 7 و 8، ويمكن للمرسل في بعض الحالات استخدام إشعار ACK مُكرَّر كدليلٍ على فقد إطار. يساعد كلا الأسلوبين على تحسين الأداء من خلال السماح بالكشف المبكر عن فقدان الرزم، وهناك اختلاف آخر في هذا المخطط وهو استخدام إشعارات انتقائية (selective acknowledgments)، أي أن المستقبل يمكنه إرسال إشعارات بوصول تلك الإطارات التي استلمها بدلًا من مجرد استلام أعلى إطار مرقّمٍ بالترتيب، لذلك يمكن للمستقبل أن يرسل إشعارات باستلام الإطارات 7 و 8 في المثال أعلاه.
يسهّل تقديم المزيد من المعلومات إلى المرسل عليه الحفاظ على الأنبوب ممتلئًا ولكنه يضيف تعقيدًا للتطبيق. يُحدَّد حجم نافذة الإرسال وفقًا لعدد الإطارات التي نريد أن تكون معلّقة على الرابط في وقت معين، ومن السهل حساب SWS للتأخير × حيز النطاق التراسلي، ويمكن للمستقبل من ناحية أخرى ضبط RWS بالقيمة التي يريد. هناك إعدادان شائعان هما RWS = 1 الذي يعني أن المستقبل لن يخزن مؤقتًا أي إطارات تصل مخالفة للترتيب، و RWS = SWS الذي يعني أن المستقبل يمكنه تخزين أي من الإطارات التي يرسلها المرسل مؤقتًا. ليس من المنطقي تعيين RWS > SWS نظرًا لأنه من المستحيل وصول إطارات أكثر من SWS مخالفة للترتيب.
الأرقام التسلسلية المحدودة والنافذة المنزلقة (Finite Sequence Numbers and Sliding Window)
بالعودة إلى التبسيط الذي أُدخل في الخوارزمية وهو الافتراض أن الأرقام التسلسلية يمكن أن تزداد كثيرًا بصورة لا نهائية، ولكن يُحدَّد، من الناحية العملية بالطبع، رقم الإطار التسلسلي في حقل ترويسة بحجم محدد. يعني الحقل 3 بت على سبيل المثال أن هناك ثمانية أرقام تسلسلية محتملة، 0..7، وهذا يجعل من الضروري إعادة استخدام الأرقام التسلسلية أو، بطريقة أخرى، التفاف الأرقام التسلسلية (wrap around)، فيؤدي ذلك إلى مشكلة القدرة على التمييز بين التجسيدات المختلفة لنفس الأرقام التسلسلية، مما يعني أن عدد الأرقام التسلسلية الممكنة يجب أن يكون أكبر من عدد الإطارات المعلّقة المسموح بها. سمحت خوارزمية توقف وانتظر على سبيل المثال بإطار واحد في كل مرة وله رقمان تسلسليان متميزان.
افترض أن لديك رقمًا واحدًا في فضاء الأرقام التسلسلية أكثر من عدد الإطارات التي يحتمل أن تكون مميزة، وهذا يعني أن SWS <= MaxSeqNum - 1، حيث MaxSeqNum هو عدد الأرقام التسلسلية المتاحة، فهل هذا كافٍ؟ يعتمد الجواب على RWS، فإذا كانت RWS = 1، فإن MaxSeqNum > = SWS + 1 كافٍ، وإذا كانت RWS تساوي RWS، فإن وجود MaxSeqNum أكبر من حجم نافذة الإرسال ليس جيدًا بما يكفي. لفهم ذلك، افترض الحالة التي تكون فيها الأرقام التسلسلية الثمانية من 0 إلى 7، و SWS = RWS = 7، وافترض أن المرسل يرسل الإطارات 0..6، ثم تُستلم بنجاح، ولكن تُفقد إشعاراتها. يتوقع المستقبل الآن الإطارات 7 و 0..5، ولكن تنتهي مهلة المرسل ويرسل الإطارات 0..6، وبالتالي يتوقع المستقبل لسوء الحظ التجسيد الثاني للإطارات 0..5 لكنه يحصل على التجسيد الأول لهذه الإطارات، وهذه هي بالضبط الحالة التي يجب تجنبها.
اتضح أن حجم نافذة الإرسال لا يمكن أن يكون أكبر من نصف عدد الأرقام التسلسلية المتاحة عندما تكون RWS = SWS، أو تُحدَّد بدقة أكبر كما يلي:
SWS < (MaxSeqNum + 1)/ 2
وهذا يعني أن بروتوكول النافذة المنزلقة يتناوب بين نصفي فضاء الأرقام التسلسلية، تمامًا كما تبدّل خوارزمية توقف وانتظر بين الرقمين التسلسليين 0 و 1، والفرق الوحيد هو أنه ينزلق باستمرار بين النصفين بدلًا من التناوب بينهما. ولكن لاحظ أن هذه القاعدة خاصة بالحالة RWS = SWS. سنترك لك تمرين تحديد القاعدة الأعم التي تعمل مع قيم RWS و SWS العشوائية. لاحظ أيضًا أن العلاقة بين حجم النافذة وفضاء الأرقام التسلسلية تعتمد على افتراضٍ واضح جدًا بحيث يسهل التغاضي عنه وهو أن الإطارات لا يُعاد ترتيبها أثناء النقل. لا يمكن أن يحدث هذا على الروابط المباشرة نقطة لنقطة لأنه لا توجد طريقة تمكّن إطارًا ما من تجاوز إطارٍ آخر أثناء الإرسال، ولكنك سترى خوارزمية النافذة المنزلقة المستخدمة في بيئات مختلفة، وستحتاج إلى وضع قاعدة أخرى.
تطبيق النافذة المنزلقة (Implementation of Sliding Window)
توضح الشيفرة الآتية كيف يمكن تطبيق جانبي الإرسال والاستقبال لخوارزمية النافذة المنزلقة، حيث أن هذه الشيفرة مأخوذة من بروتوكول عمل يسمى بروتوكول النافذة المنزلقة (Sliding Window Protocol أو اختصارًا SWP). يُشار إلى البروتوكول الموجود فوق بروتوكول SWP على أنه بروتوكول عالي المستوى (high-level protocol ويُختصر إلى HLP)، ويشار إلى البروتوكول الموجود أسفل بروتوكول SWP على أنه بروتوكول مستوى الرابط (link-level protocol أو اختصارًا LLP). نبدأ بتعريف زوجٍ من بنيات البيانات، حيث أولًا ترويسة الإطار بسيطة للغاية، فهي تحتوي على رقم تسلسلي (SeqNum) ورقم إشعار (AckNum)، وتحتوي أيضًا على حقل الرايات Flags الذي يحدد إذا كان الإطار عبارة عن إشعار ACK أو أنه يحمل بيانات.
typedef u_char SwpSeqno;
typedef struct {
SwpSeqno SeqNum; /* رقم الإطار التسلسلي */
SwpSeqno AckNum; /* إشعار وصول الإطار المُستلَم */
u_char Flags; /*(flags) ما يصل إلى 8 بتات من الرايات */
} SwpHdr;
تحتوي حالة خوارزمية النافذة المنزلقة على البنية التالية: تتضمن هذه الحالة من جانب إرسال البروتوكول على المتغيرين LAR و LFS، كما هو موضح سابقًا، بالإضافة إلى طابور يحتوي على الإطارات التي أُرسلت ولكن لم تُرسَل إشعارات وصولها بعد (sendQ). تتضمن حالة الإرسال أيضًا متغير تقييد وصول خاصٍ بالعد (counting semaphore) يسمى sendWindowNotFull. يُعد متغير تقييد الوصول أداة مزامنة أولية تدعم عمليات semWait و semSignal. يزيد كل استدعاء للعملية semSignal متغيرَ تقييد الوصول بمقدار 1، وينقص كل استدعاءٍ للعملية semWait المتغير s بمقدار 1، ويجب أن يؤدي توقف عملية الاستدعاء أو تعليقها إلى تقليل قيمة متغير تقييد الوصول إلى أقل من 0، وسيُسمح للعملية التي توقفت أثناء استدعائها باستئناف العملية semWait بمجرد إجراء عمليات semSignal كافيةٍ لرفع قيمة متغير تقييد الوصول إلى أعلى من 0. تتضمن هذه الحالة من جانب استلام البروتوكول على المتغير NFE، وهو الإطار التالي المتوقع (next frame expected)، وهو الإطار الذي يحتوي على رقم تسلسلي واحد أكثر من آخر إطار مُستلَم (LFR). يوجد أيضًا طابور يحتوي على الإطارات المستلَمة المخالفة للترتيب (recvQ)، وتُحدَّد أخيرًا أحجام نافذة المرسل والمستقبل المنزلقة بواسطة الثوابت SWS و RWS على التوالي:
typedef struct { /* :حالة جانب المرسل */ SwpSeqno LAR; /* الرقم التسلسلي لآخر إشعار مستلَم */ SwpSeqno LFS; /* آخر إطار مُرسَل */ Semaphore sendWindowNotFull; SwpHdr hdr; /* ترويسة مُهيَّأة مسبقًا */ struct sendQ_slot { Event timeout; /* الحدث المرتبط بمهلة الإرسال الزمنية */ Msg msg; } sendQ[SWS]; /* :حالة جانب المستقبل */ SwpSeqno NFE; /* الرقم التسلسلي للإطار التالي المتوقَّع */ struct recvQ_slot { int received; /* هل الرسالة صالحة؟ */ Msg msg; } recvQ[RWS]; } SwpState;
يُطبَّق جانب الإرسال من بروتوكول SWP بواسطة الإجرائية sendSWP البسيطة نوعًا ما، حيث أولًا تتسبب العملية semWait في أن تحظر هذه الإجرائية الوصول إلى متغير تقييد الوصول إلى أن يُسمح بإرسال إطار آخر، حيث تضبط الإجرائيةُ sendSWP الرقمَ التسلسلي في ترويسة الإطار بمجرد السماح بالمتابعة، وتحفظ نسخةً من الإطار في طابور الإرسال (sendQ)، وتجدول حدث انتهاء المهلة لمعالجة الحالة التي لا يُرسَل فيها إشعار وصول الإطار، وترسل الإطار إلى بروتوكول المستوى الأدنى التالي الذي نشير إليه بـ LINK.
أحد التفاصيل الجديرة بالملاحظة هو استدعاء الدالة store_swp_hdr قبل استدعاء الدالة msgAddHdr، حيث تترجم هذه الشيفرة بنية لغة C التي تحتفظ بترويسة SWP (state-> hdr) كسلسلة بايتات يمكن ربطها بأمان بمقدمة الرسالة (hbuf). يجب أن تترجم هذه الإجرائية كل حقل عدد صحيح في الترويسة إلى ترتيب بايت شبكة وإزالة أي حشو أضافه المصرِّف (compiler) إلى بنية C. مسألة ترتيب البايتات هي مسألة غير بسيطة، ولكن يكفي افتراض أن هذه الإجرائية في الوقت الحالي تضع البت الأعلى أهمية من عددٍ صحيح متعدد الكلمات (multiword) في البايت ذي العنوان الأعلى. جزء آخر من التعقيد في هذه الشيفرة هو استخدام العملية semWait ومتغير تقييد الوصول sendWindowNotFull. يُهيَّأ المتغير sendWindowNotFull بحجم نافذة المرسل المنزلقة SWS (لا تُعرَض هذه التهيئة)، ثم تقلل العملية semWait هذا العدد في كل مرة يرسل فيها المرسل إطارًا وتوقِف المرسل إذا انتقل العدد إلى 0. تزيد العمليةُ semSignal التي تُستدعى ضمن الإجرائية deliverySWP هذا العددَ في كل مرة يُستلَم فيها إشعار ACK، وبالتالي يُستأنف أي مرسلٍ منتظرٍ.
static int sendSWP(SwpState *state, Msg *frame) { struct sendQ_slot *slot; hbuf[HLEN]; /* انتظر فتحَ نافذة المرسل */ semWait(&state->sendWindowNotFull); state->hdr.SeqNum = ++state->LFS; slot = &state->sendQ[state->hdr.SeqNum % SWS]; store_swp_hdr(state->hdr, hbuf); msgAddHdr(frame, hbuf, HLEN); msgSaveCopy(&slot->msg, frame); slot->timeout = evSchedule(swpTimeout, slot, SWP_SEND_TIMEOUT); return send(LINK, frame); }
يجب إصلاح بعض التناقض قبل المتابعة إلى جانب الاستلام، حيث قلنا أن البروتوكول عالي المستوى يستدعي خدمات بروتوكول مستوٍ منخفض عن طريق استدعاء العملية send، لذلك نتوقع أن يستدعي البروتوكول الذي يريد إرسال رسالة عبر SWP الدالة '(send(SWP, packet، ولكن يُطلق على الإجرائية التي تطبّق عملية إرسال SWP اسمsendSWP، وأول وسطائها هو متغير الحالة (SwpState)، حيث يوفّر نظام التشغيل شيفرةً لاصقة (glue code) تترجم استدعاءsendالعام إلى استدعاء برتوكولٍ خاصsendSWP. تربط الشيفرة اللاصقة الوسيطَ الأول من العمليةsend(متغير البروتوكول السحريSWP) مع كلٍ من الدالة المؤشرة إلى الإجرائيةsendSWP` والمؤشر إلى حالة البروتوكول التي يحتاجها SWP للقيام بعمله. السبب في أن البروتوكول عالي المستوى يستدعي بطريقة غير مباشرة الدالةََ الخاصة بالبروتوكول من خلال استدعاء الدالة العامة هو أننا نريد تحديد مقدار المعلومات التي شفّرها البروتوكول عالي المستوى حول البروتوكول منخفض المستوى، وهذا يجعل تغيير ضبط رسم البروتوكول البياني في وقت ما في المستقبل أمرًا سهلًا.
ننتقل الآن إلى تطبيق بروتوكول SWP المحدّد للعملية deliver الموجود ضمن الإجرائية deliverSWP، حيث تعالج هذه الإجرائية نوعين مختلفين من الرسائل الواردة: إشعارات الإطارات المرسلة سابقًا من هذه العقدة وإطارات البيانات التي تصل إلى هذه العقدة، أي نٍصفُ إشعارات هذه الإجرائية هو المقابل لجانب المرسل من الخوارزمية الواردة في الإجرائية sendSWP. يُتخذ قرار بشأن ما إذا كانت الرسالة الواردة عبارة عن إشعار ACK أو إطار بيانات عن طريق التحقق من الحقل Flags في الترويسة.
لاحظ أن هذا التطبيق لا يدعم حَملَ الإشعارات على إطارات البيانات. تبحث الإجرائية deliverySWP ببساطة عن الفتحة الموجودة في طابور الإرسال (sendQ) التي تتوافق مع الإشعار عندما يكون الإطار الوارد عبارة عن إشعار وتلغي حدث المهلة، وتحرر الإطار المحفوظ في تلك الفتحة. يُطبَّق هذا العمل في الواقع ضمن حلقة لأن الإشعار قد يكون تراكميًا. الشيء الآخر الوحيد الذي يجب ملاحظته حول هذه الحالة هو استدعاء الإجرائية الفرعية swpInWindow، حيث تضمن هذه الإجرائية الفرعية، الواردة أدناه، أن يكون رقم الإطار التسلسلي الذي يُرسَل إشعارٌ باستلامه ضمن نطاق مجموعة الإشعارات التي يتوقع المرسل استلامها حاليًا.
تستدعي الإجرائية deliverSWP أولًا الإجرائيتين msgStripHdr و load_swp_hdr عندما يحتوي الإطار الوارد على بياناتٍ لاستخراج الترويسة من الإطار، حيث تُعد الإجرائية load_swp_hdr هي المقابل للإجرائية store_swp_hdr التي نوقشت سابقًا، فهي تترجم سلسلة بايتات إلى بنية بيانات C التي تحتوي على ترويسة SW، ثم تستدعي الإجرائيةُ DeliverySWP الإجرائيةَ swpInWindow للتأكد من أن رقم الإطار التسلسلي يقع ضمن نطاق الأرقام التسلسلية المتوقعة. إذا كان الأمر كذلك، فستدور الإجرائية عبر مجموعة الإطارات المتعاقبة المستلَمة وتمررها إلى بروتوكول المستوى الأعلى من خلال استدعاء الإجرائية deliveryHLP. كما ترسل أيضًا إشعارًا تراكميًا إلى المرسل، ولكنها تفعل ذلك عن طريق تكرار طابور الاستلام (ولا تستخدم متغير الإجرائية deliveryHLP).
static int deliverSWP(SwpState state, Msg *frame) { SwpHdr hdr; char *hbuf; hbuf = msgStripHdr(frame, HLEN); load_swp_hdr(&hdr, hbuf) if (hdr->Flags & FLAG_ACK_VALID) { /* استلمتَ إشعارًا، إذًا نفّذ جانب المرسل*/ if (swpInWindow(hdr.AckNum, state->LAR + 1, state->LFS)) { do { struct sendQ_slot *slot; slot = &state->sendQ[++state->LAR % SWS]; evCancel(slot->timeout); msgDestroy(&slot->msg); semSignal(&state->sendWindowNotFull); } while (state->LAR != hdr.AckNum); } } if (hdr.Flags & FLAG_HAS_DATA) { struct recvQ_slot *slot; /* استلمتَ رزمة بيانات، إذًا نفّذ جانب المستقبل */ slot = &state->recvQ[hdr.SeqNum % RWS]; if (!swpInWindow(hdr.SeqNum, state->NFE, state->NFE + RWS - 1)) { /* أهمل الرسالة */ return SUCCESS; } msgSaveCopy(&slot->msg, frame); slot->received = TRUE; if (hdr.SeqNum == state->NFE) { Msg m; while (slot->received) { deliver(HLP, &slot->msg); msgDestroy(&slot->msg); slot->received = FALSE; slot = &state->recvQ[++state->NFE % RWS]; } /* :أرسل إشعارًا */ prepare_ack(&m, state->NFE - 1); send(LINK, &m); msgDestroy(&m); } } return SUCCESS; }
الإجرائية swpInWindow هي إجرائية فرعية بسيطة تتحقق فيما إذا كان الرقم التسلسلي يقع بين حدي الرقم التسلسلي الأدنى والأعلى كما يلي:
static bool swpInWindow(SwpSeqno seqno, SwpSeqno min, SwpSeqno max) { SwpSeqno pos, maxpos; pos = seqno - min; /* [0..MAX) يجب أن يكون ضمن المجال pos المتغير */ maxpos = max - min + 1; /* [0..MAX] يجب أن يكون ضمن المجال maxpos المتغير */ return pos < maxpos; }
ترتيب الإطارات والتحكم في التدفق (Frame Order and Flow Control)
قد يكون بروتوكول النافذة المنزلقة هو أفضل خوارزمية معروفة في شبكات الحاسوب، ولكن ما يربك بسهولة حول هذه الخوارزمية هو أنه يمكن استخدامها لإنجاز ثلاثة أدوار مختلفة. الدور الأول هو توصيل الإطارات بصورة موثوقة عبر رابطٍ غير موثوق به، أي يمكن استخدام الخوارزمية لتوصيل الرسائل بطريقة موثوقة عبر شبكة غير موثوقة، وهذه هي الوظيفة الأساسية للخوارزمية.
الدور الثاني الذي يمكن أن تؤديه خوارزمية النافذة المنزلقة هو الحفاظ على الترتيب الذي تُرسَل الإطارات به، حيث من السهل القيام بذلك عند المستقبل، نظرًا لأن كل إطار يحتوي على رقم تسلسلي، وبالتالي يتأكد المستقبل فقط من أنه لا يمرر إطارًا إلى بروتوكول المستوى الأعلى التالي حتى يمرر بالفعل جميع الإطارات ذات الأرقام التسلسلية الأصغر، وهذا يعني أن مخازن المستقبل المؤقتة لا تمرر إطارات مخالفة للترتيب. يحافظ إصدار خوارزمية النافذة المنزلقة الموصوف في هذا القسم على ترتيب الإطارات، على الرغم من أننا يمكن أن نتخيل اختلافًا عندما يمرر المستقبل الإطارات إلى البروتوكول التالي دون انتظار تسليم جميع الإطارات السابقة. السؤال الذي يجب طرحه الآن هو ما إذا كنا نحتاج حقًا إلى بروتوكول النافذة المنزلقة للحفاظ على ترتيب الإطارات على مستوى الرابط، أو يجب بدلًا من ذلك تطبيق هذه الوظيفة بواسطة بروتوكول أعلى في المكدس.
يتمثل الدور الثالث الذي تلعبه خوارزمية النافذة المنزلقة أحيانًا في دعم التحكم في التدفق (flow control)، وهي آلية للتغذية الراجعة التي يستطيع المستقبل بواسطتها خنق المرسل، حيث تُستخدم مثل هذه الآلية لمنع المرسل من الإفراط في تشغيل المستقبل، أي عدم إرسال بيانات أكثر مما يستطيع المستقبل معالجته. يتحقق ذلك عادةً عن طريق زيادة بروتوكول النافذة المنزلقة بحيث لا يرسل المستقبل إشعارًا باستلام الإطارات التي استقبلها فحسب، بل يُعلم المرسل أيضًا بعدد الإطارات التي يمكنه استقبالها. يتوافق عدد الإطارات التي يمكن للمستقبل استقبالها مع مقدار مساحة المخزَن المؤقت الحرة الموجودة. تحتاج، كما في حالة التسليم المرتّب، إلى التأكد من أن التحكم في التدفق ضروري على مستوى الرابط قبل دمجه في بروتوكول النافذة المنزلقة.
اقتباسأحد المفاهيم المهمة التي يجب استبعادها من هذه المناقشة هو مبدأ تصميم النظام الذي نسميه فصل الاهتمامات (separation of concerns)، ويجب أن تكون حريصًا على التمييز بين الوظائف المختلفة التي تُجمَّع أحيانًا معًا في آلية واحدة، ويجب التأكد من أن كل وظيفة ضرورية وتُدعَم بأكثر الطرق فعالية. ولكن يُدمَج أحيانًا في هذه الحالة بالذات التسليم الموثوق مع التسليم المرتَّب والتحكم في التدفق في بروتوكول نافذة منزلقة واحدة، ويجب أن تسأل نفسك ما إذا كان هذا هو الشيء الصحيح الذي يجب القيام به على مستوى الرابط.
القنوات المنطقية المتزامنة (Concurrent Logical Channels)
يوفّر بروتوكول ربط البيانات المستخدم في شبكات أربانت ARPANET الأصلية بديلًا مثيرًا للاهتمام لبروتوكول النافذة المنزلقة، حيث يمكنه الحفاظ على الأنبوب ممتلئًا مع الاستمرار في استخدام خوارزمية توقف وانتظر البسيطة. إحدى النتائج المهمة لهذا الأسلوب هي أن الإطارات المرسلَة عبر رابطٍ معين لا يُحتفَظ بها بأي ترتيب محدد، ولا يشير البروتوكول أيضًا إلى أي شيء يتعلق بالتحكم في التدفق.
الفكرة الأساسية لبروتوكول ARPANET، والتي يشار إليها بالقنوات المنطقية المتزامنة، هي دمج عدة قنوات منطقية على رابط من نقطة لنقطة واحدٍ وتشغيل خوارزمية توقف وانتظر على كل من هذه القنوات المنطقية. لا توجد علاقة محفوظة بين الإطارات المرسلة على أي من القنوات المنطقية، ولكن نظرًا لأن إطارًا مختلفًا يمكن أن يكون موجودًا على كل من القنوات المنطقية المتعددة، فيمكن للمرسل الاحتفاظ بالرابط ممتلئًا، وبتعبيرٍ أدق يحتفظ المرسل بثلاثة بتات من أجل حالة كل قناة: بت بولياني يوضح ما إذا كانت القناة مشغولة حاليًا، ورقم تسلسلي مؤلف من 1 بت لاستخدامه في المرة التالية التي يُرسَل فيها إطار على هذه القناة المنطقية، والرقم التسلسلي التالي الذي يمكن توقعه في إطار يصل إلى هذه القناة. تستخدم العقدةُ القناة الأدنى خمولًا عندما يكون لديها إطارٌ لإرساله، وبخلاف ذلك تتصرّف تمامًا مثل خوارزمية توقف وانتظر.
تدعم شبكات ARPANET ثماني قنوات منطقية عبر كل رابط أرضي و 16 قناة عبر كل رابط فضائي. تضمنت ترويسة كل إطار في حالة الرابط الأرضي رقم قناة مؤلف من 3 بتات ورقمًا تسلسليًا مؤلفًا من بت واحد، ليصبح المجموع 4 بتات، وهذا هو بالضبط عدد البتات الذي يتطلبه بروتوكول النافذة المنزلقة لدعم ما يصل إلى 8 إطارات على الرابط عندما تكون RWS = SWS.
ترجمة -وبتصرّف- للقسم Reliable Transmission من فصل Direct Links من كتاب Computer Networks: A Systems Approach
أفضل التعليقات
لا توجد أية تعليقات بعد
انضم إلى النقاش
يمكنك أن تنشر الآن وتسجل لاحقًا. إذا كان لديك حساب، فسجل الدخول الآن لتنشر باسم حسابك.