العمليات الحسابية على الرقم التسلسلي
تتطلب العديد من البروتوكولات والخوارزميات تسلسل أو تعداد الكيانات ذات الصلة. على سبيل المثال، يجب أن يعرف بروتوكول الاتصال ما إذا كانت حزمة بيانات ما تأتي "قبل" أو "بعد" حزمة بيانات أخرى. تحاول وثيقة RFC 1982 الصادرة عن فريق عمل هندسة الإنترنت ( IETF ) تعريف "حساب الأرقام التسلسلية" لأغراض معالجة ومقارنة هذه الأرقام التسلسلية . باختصار، عندما تنخفض القيمة المطلقة للرقم التسلسلي بأكثر من نصف القيمة القصوى (مثل 128 في قيمة 8 بت)، يُعتبر أنه "بعد" الرقم السابق، بينما تُعتبر الانخفاضات الأخرى "قبل".
هذه المهمة أكثر تعقيدًا مما تبدو عليه للوهلة الأولى، لأن معظم الخوارزميات تستخدم تمثيلات ثنائية (ذات حجم ثابت ) لأرقام التسلسل. من المهم غالبًا ألا تتعطل الخوارزمية عندما تصبح الأرقام كبيرة جدًا لدرجة أنها تُزاد مرة أخيرة وتتجاوز نطاقاتها العددية القصوى (أي تنتقل فجأة من عدد موجب كبير إلى صفر أو عدد سالب كبير). تتجاهل بعض البروتوكولات هذه المشكلات وتستخدم ببساطة أعدادًا صحيحة كبيرة جدًا لعداداتها، على أمل أن يتم استبدال البرنامج (أو إيقافه) قبل حدوث المشكلة (انظر مشكلة عام 2000 ).
تُطبّق العديد من بروتوكولات الاتصال عمليات حسابية على الأرقام التسلسلية لأرقام تسلسل الحزم في تطبيقها لبروتوكول النافذة المنزلقة . وتستخدم بعض إصدارات بروتوكول TCP الحماية من الأرقام التسلسلية الملتفة (PAWS) . تُطبّق PAWS نفس العمليات الحسابية على الأرقام التسلسلية على الطوابع الزمنية للحزم، باستخدام الطابع الزمني كامتداد للبتات ذات الرتبة العليا من رقم التسلسل. [ 1 ]
العمليات على أرقام التسلسل
يقتصر النقاش على إضافة عدد صحيح موجب صغير إلى رقم تسلسلي ومقارنة رقمين تسلسليين. ويقتصر النقاش على تطبيقات النظام الثنائي غير الموقّع، مع تحديد حجم عشوائي بالبتات في جميع أنحاء RFC (وما يليه) بالرمز "SERIAL_BITS".
إضافة
إضافة عدد صحيح إلى رقم تسلسلي هي عملية جمع بسيطة للأعداد الصحيحة غير الموقعة، متبوعة بعملية باقي القسمة غير الموقعة لإعادة النتيجة إلى النطاق (عادةً ما تكون ضمنية في عملية الجمع غير الموقعة، في معظم البنى):
- s' = ( s + n ) modulo 2 SERIAL_BITS
إضافة قيمة أقل من 0 أو أكبر من 2 SERIAL_BITS−1 − 1 غير مُعرَّفة. بمعنى آخر، إضافة قيم خارج هذا النطاق ستؤدي إلى التفاف رقم التسلسل الناتج، وغالبًا ما ينتج عنه رقم يُعتبر "أقل من" رقم التسلسل الأصلي.
مقارنة
يتم تقديم وسيلة لمقارنة رقمي التسلسل i 1 و i 2 (التمثيلات العددية الصحيحة غير الموقعة لأرقام التسلسل s 1 و s 2 ).
تُعرَّف المساواة بأنها مساواة عددية بسيطة.
الخوارزمية المعروضة للمقارنة معقدة، إذ يجب أن تأخذ في الحسبان ما إذا كان رقم التسلسل الأول قريبًا من "نهاية" نطاق قيمه، وبالتالي قد يُعتبر رقم "مُغلّف" أصغر "أكبر" من رقم التسلسل الأول. لذا، يُعتبر i1 أصغر من i2 فقط إذا
- ( i 1 < i 2 و i 2 − i 1 < 2 SERIAL_BITS−1 ) أو
- ( i 1 > i 2 and i 1 − i 2 > 2 SERIAL_BITS−1 )
أوجه القصور
تعاني الخوارزميات المُقدمة في طلب التعليقات (RFC) من عيبٍ جوهري واحد على الأقل: وجود أرقام تسلسلية لا يُمكن تعريف المقارنة بينها. ونظرًا لأن العديد من الخوارزميات تُنفذ بشكل مستقل من قِبل جهات تعاونية مستقلة متعددة، فإنه غالبًا ما يكون من المستحيل منع حدوث جميع هذه الحالات.
يقرّ مؤلفو RFC 1982 بهذا الأمر دون تقديم حل عام:
مع أنه من الممكن تعريف الاختبار بطريقة لا تتضمن فيها المتباينة هذه الخاصية المفاجئة، مع تعريفها لجميع أزواج القيم، إلا أن هذا التعريف سيكون مرهقًا بلا داعٍ في التنفيذ، وصعب الفهم، وسيظل يسمح بوجود حالات حيث
s1 < s2 و (s1 + 1) > (s2 + 1)وهو أمر غير بديهي بنفس القدر.
وبالتالي، تبقى حالة المشكلة غير محددة، وللتطبيقات حرية إرجاع أي من النتيجتين، أو الإشارة إلى وجود خطأ، ويجب على المستخدمين توخي الحذر وعدم الاعتماد على أي نتيجة معينة. عادةً ما يعني هذا تجنب السماح بتواجد أزواج الأرقام تلك معًا.
لذا، غالبًا ما يكون من الصعب أو المستحيل تجنب جميع المقارنات "غير المُعرَّفة" لأرقام التسلسل. مع ذلك، يتوفر حل بسيط نسبيًا. من خلال ربط أرقام التسلسل غير المُوقَّعة بعمليات حسابية بنظام المتمم الثنائي المُوقَّع ، تُصبح كل مقارنة لأي رقم تسلسل مُعرَّفة، وتُبسَّط عملية المقارنة نفسها بشكل كبير. تحتفظ جميع المقارنات المُحدَّدة في RFC بقيمها الأصلية؛ ولا تتأثر إلا المقارنات التي كانت "غير مُعرَّفة" سابقًا.
حل عام
تحدد خوارزمية RFC 1982 أنه بالنسبة لأرقام التسلسل المكونة من N بت، توجد 2^ N - 1 - 1 قيمة تُعتبر "أكبر من" و2 ^N - 1 - 1 قيمة تُعتبر "أصغر من". وتُعتبر المقارنة مع القيمة المتبقية (التي تبعد عنها مسافة 2 ^N - 1 بالضبط) "غير مُعرّفة".
تُنفذ معظم الأجهزة الحديثة عمليات حسابية ثنائية باستخدام نظام المتمم الثنائي المُوَقَّع. هذه العمليات مُعَرَّفة بالكامل لجميع قيم أي مُعاملات تُعطى لها، حيث أن أي عدد ثنائي مكون من N بت يمكن أن يحتوي على 2^ N قيمة مختلفة، وبما أن إحدى هذه القيم مشغولة بالقيمة 0، فإن هناك عددًا فرديًا من الخانات المتبقية لجميع الأعداد الموجبة والسالبة غير الصفرية. ببساطة، يوجد عدد سالب واحد أكثر من عدد الأعداد الموجبة التي يمكن تمثيلها. على سبيل المثال، قد تحتوي قيمة المتمم الثنائي المكونة من 16 بت على أعداد تتراوح من-32768 إلى+32 767 .
لذا، إذا قمنا ببساطة بإعادة صياغة أرقام التسلسل كأعداد صحيحة متممة 2 وسمحنا بوجود رقم تسلسل واحد يعتبر "أصغر من" مقارنة بأرقام التسلسل التي تعتبر "أكبر من"، فيجب أن نكون قادرين على استخدام مقارنات حسابية بسيطة موقعة بدلاً من الصيغة غير الكاملة منطقيًا التي اقترحتها RFC.
فيما يلي بعض الأمثلة (بـ 16 بت، مرة أخرى)، لمقارنة بعض أرقام التسلسل العشوائية، مقابل رقم التسلسل ذي القيمة 0:
ثنائي غير موقع ثنائي موقع مسافة قيمة التسلسل -------- ------ -------- 32767 == 0x7FFF == 32767 1 == 0x0001 == 1 0 == 0x0000 == 0 65535 == 0xFFFF == −1 65534 == 0xFFFE == −2 32768 == 0x8000 == −32768
من السهل ملاحظة أن التفسير المُوَقَّع لأعداد التسلسل يكون بالترتيب الصحيح، طالما أننا "نُدَوِّر" عدد التسلسل المعني بحيث يتطابق صفره مع عدد التسلسل الذي نقارنه به. ويتضح أن هذا يتم ببساطة باستخدام عملية طرح غير مُوَقَّعة ، وتفسير النتيجة ببساطة على أنها عدد مُوَقَّع بنظام المتمم الثنائي. والنتيجة هي "المسافة" المُوَقَّعة بين عددي التسلسل. ومرة أخرى، إذا كان وi1 هما التمثيلi2 الثنائي غير المُوَقَّع لعددي التسلسل s1 و s2 ، فإن المسافة من s1 إلى s2 هي
المسافة = ( إشارة ) ( i1 - i2 )إذا كانت المسافة تساوي صفرًا، فإن العددين متساويان. أما إذا كانت أقل من صفر، فإن s1 يكون "أصغر من" أو "قبل" s2 . معادلة بسيطة وواضحة وفعّالة ومحددة بدقة. مع ذلك، لا تخلو من بعض المفاجآت.
يجب أن تتعامل جميع العمليات الحسابية على الأعداد المتسلسلة مع "التفاف" هذه الأعداد؛ فالعدد 2N - 1 متساوي البعد في كلا الاتجاهين، وفقًا لمعيار RFC 1982 للأعداد المتسلسلة. في حساباتنا، يُعتبر كل منهما "أصغر من" الآخر.
المسافة 1 = ( مُوَقَّع )( 0x8000 - 0x0 ) == ( مُوَقَّع ) 0x8000 == -32768 < 0 المسافة 2 = ( مُوَقَّع )( 0x0 - 0x8000 ) == ( مُوَقَّع ) 0x8000 == -32768 < 0من الواضح أن هذا ينطبق على أي رقمين متتاليين بمسافة 0x8000 بينهما.
علاوة على ذلك، يتطلب تنفيذ العمليات الحسابية على الأرقام التسلسلية باستخدام نظام المتمم الثنائي أرقامًا تسلسلية بطول بتات يطابق أحجام الأعداد الصحيحة للجهاز؛ عادةً 16 بت، 32 بت، و64 بت. ويتطلب تنفيذ الأرقام التسلسلية ذات 20 بت عمليات إزاحة (بافتراض أن الأعداد الصحيحة 32 بت).
المسافة = ( مُوَقَّع )(( i1 << 12 ) - ( i2 << 12 ))انظر أيضاً
مراجع
روابط خارجية
- نظام أسماء النطاقات
- الأرقام التسلسلية