التراجع الأسي

📅 آخر تحديث: ١ أغسطس ٢٠٢٦
✍️ نُشر في: ١ أغسطس ٢٠٢٦
📷 يحتوي على 12 صور
الموسوعة الحرة

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

خوارزمية التراجع الأسي

خوارزمية التراجع الأسي هي شكل من أشكال أنظمة التحكم ذات الحلقة المغلقة، تعمل على تقليل معدل عملية مُتحكَّم بها استجابةً للأحداث الطارئة. على سبيل المثال، إذا فشل تطبيق جوال في الاتصال بخادمه، فقد يُعاود المحاولة بعد ثانية واحدة، ثم إذا فشل مرة أخرى، يُعاود المحاولة بعد ثانيتين، ثم بعد أربع ثوانٍ، وهكذا. في كل مرة، يتضاعف زمن التوقف بمقدار ثابت (في هذه الحالة، 2). في هذه الحالة، يتمثل الحدث الطارئ في فشل الاتصال بالخادم. تشمل الأمثلة الأخرى للأحداث الطارئة تصادمات حركة مرور الشبكة ، وفقدان الحزم ، واستجابة خطأ من خدمة ما، أو طلب صريح لتقليل المعدل (أي التراجع ).

يمكن نمذجة انخفاض المعدل كدالة أسية :

ت=بج{\displaystyle t=b^{c}}

أو

و=1بج{\displaystyle f={\frac {1}{b^{c}}}}

هنا، يُمثل t التأخير الزمني بين الإجراءات، و b عامل الضرب أو الأساس ، و c عدد الأحداث السلبية المُلاحظة. أو f تردد (أو معدل) العملية (أي عدد الإجراءات في وحدة الزمن). تزداد قيمة c مع كل حدث سلبي مُلاحظ، مما يؤدي إلى زيادة أسية في التأخير، وبالتالي معدل يتناسب عكسيًا. تُسمى خوارزمية التراجع الأسي حيث b = 2 بخوارزمية التراجع الأسي الثنائي .

عندما ينخفض ​​معدل التشغيل استجابةً لحدثٍ معاكس، فإنه عادةً لا يبقى عند هذا المستوى المنخفض إلى الأبد. إذا لم تُلاحظ أي أحداث معاكسة لفترةٍ زمنيةٍ معينة، تُعرف غالبًا بفترة التعافي أو فترة التهدئة ، يُمكن زيادة المعدل مرةً أخرى. يُمكن تحديد الفترة الزمنية التي يجب أن تنقضي قبل محاولة زيادة المعدل مجددًا بواسطة خوارزمية التراجع الأسي. عادةً ما يكون تعافي المعدل أبطأ من انخفاضه بسبب التراجع، وغالبًا ما يتطلب ضبطًا دقيقًا لتجنب تذبذب المعدل. [ 1 ] يختلف سلوك التعافي الدقيق باختلاف التطبيق، وقد يتأثر بعددٍ من العوامل البيئية.

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

تحديد معدل الاستخدام

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

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

في نسخة مبسطة من الخوارزمية، تتأخر الرسائل بفترة زمنية محددة مسبقًا (غير عشوائية). على سبيل المثال، في بروتوكول SIP عبر وسائل نقل غير موثوقة (مثل UDP )، يعيد العميل إرسال الطلبات على فترات تبدأ من T1 ثانية (عادةً).500  مللي ثانية (وهو تقدير لوقت الرحلة ذهابًا وإيابًا ) ويتضاعف بعد كل إعادة إرسال حتى يصل إلى T2 ثانية (وهو القيمة الافتراضية لـ4  ثوانٍ ). ينتج عن ذلك فترات إعادة إرسال من500  مللي ثانية ، ثانية واحدة ،2  ثانية ،4  ثوانٍ ، ثم 4 ثوانٍ4  ثوانٍ . [ 2 ]

تجنب الاصطدام

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

لا تُناسب خوارزمية التراجع الأسي الحتمية هذه الحالة ، إذ سيتراجع كل مُرسِل لنفس المدة الزمنية، مما يؤدي إلى إعادة إرسالهم في وقت واحد، وبالتالي حدوث تصادم آخر. بدلاً من ذلك، ولأغراض تجنب التصادم، يتم اختيار الفترة الزمنية بين عمليات إعادة الإرسال عشوائيًا ، وتُحدد خوارزمية التراجع الأسي نطاق قيم التأخير الممكنة. يُقاس التأخير الزمني عادةً بوحدات زمنية ثابتة على الشبكة. في خوارزمية التراجع الأسي الثنائية (أي الخوارزمية التي يكون فيهاب=2{\displaystyle b=2}بعد حدوث c تصادمات، يتم تأخير كل عملية إعادة إرسال بعدد عشوائي من أوقات الفتحات الزمنية بين 0 و2ج-1{\displaystyle 2^{c}-1}بعد التصادم الأول، ينتظر كل مُرسِل إما صفرًا أو دورة زمنية واحدة. بعد التصادم الثاني، ينتظر المُرسِلون من صفر إلى ثلاث دورات زمنية ( شاملة ). بعد التصادم الثالث، ينتظر المُرسِلون من صفر إلى سبع دورات زمنية (شاملة)، وهكذا. مع ازدياد عدد محاولات إعادة الإرسال، يزداد عدد احتمالات التأخير بشكلٍ كبير . هذا يُقلل من احتمالية التصادم ولكنه يزيد من متوسط ​​زمن الاستجابة.

يُستخدم التراجع الأسي أثناء إعادة إرسال الإطارات في شبكات الوصول المتعدد مع استشعار الناقل وتجنب التصادم (CSMA/CA) وشبكات الوصول المتعدد مع استشعار الناقل وكشف التصادم (CSMA/CD)، حيث تُعد هذه الخوارزمية جزءًا من طريقة الوصول إلى القناة المستخدمة لإرسال البيانات على هذه الشبكات. في شبكات الإيثرنت ، تُستخدم هذه الخوارزمية عادةً لجدولة عمليات إعادة الإرسال بعد التصادمات. ويتأخر الإرسال بمقدار زمني مُستمد من زمن الفتحة (على سبيل المثال، الوقت اللازم لإرسال 512 بت؛ أي 512 زمن بت ) وعدد محاولات إعادة الإرسال.

مثال

هذا المثال مأخوذ من بروتوكول الإيثرنت [ 3 ] ، حيث يستطيع المضيف المُرسِل معرفة وقت حدوث تصادم (أي محاولة مضيف آخر الإرسال في نفس وقت إرساله) أثناء إرساله إطارًا. إذا حاول كلا المضيفين إعادة الإرسال فور حدوث التصادم، فسيحدث تصادم آخر ، وسيستمر هذا النمط إلى ما لا نهاية. يجب على المضيفين اختيار قيمة عشوائية ضمن نطاق مقبول لضمان عدم حدوث ذلك. ولذلك، تُستخدم خوارزمية التراجع الأسي.يُستخدم 51.2  ميكروثانية كمثال هنا لأنه يمثل وقت الفتحة الزمنية لـإيثرنت بسرعة 10  ميجابت/ثانية . ومع ذلك، في تطبيقات أخرى،يمكن استبدال 51.2  ميكروثانية بأي قيمة موجبة.

  1. عند حدوث تصادم لأول مرة، يتم إرسال إشارة تشويش لمنع إرسال المزيد من البيانات.
  2. أعد إرسال الإطار بعد 0 ثانية أو51.2  ميكروثانية ، تم اختيارها عشوائياً.
  3. إذا فشل ذلك، فأعد إرسال الإطار بعد أي من0  ثانية ،51.2  ميكروثانية ،102.4  ميكروثانية ، أو153.6  ميكروثانية .
  4. إذا استمر ذلك في الفشل، فأعد إرسال الإطار بعد k ·51.2  ميكروثانية ، حيث k هو عدد صحيح عشوائي بين 0 و 2 3 − 1 .
  5. في حالة حدوث المزيد من حالات الفشل، بعد المحاولة الفاشلة رقم c ، أعد إرسال الإطار بعد k ·51.2  ميكروثانية ، حيث k هو عدد صحيح عشوائي بين 0 و 2 c − 1 .

التاريخ والنظرية

في ورقة بحثية رائدة نُشرت في مؤتمر AFIPS عام 1970، [ 4 ] طرح نورمان أبرامسون فكرة مشاركة عدة مستخدمين، في جزر مختلفة، قناة راديو واحدة (أي تردد واحد) للوصول إلى الحاسوب الرئيسي في جامعة هاواي دون أي تزامن زمني. يتعامل المرسلون مع تصادمات الحزم عند مستقبل الحاسوب الرئيسي بعد انقضاء مهلة زمنية محددة على أنها أخطاء مُكتشفة. كل مرسل لا يتلقى تأكيدًا إيجابيًا من الحاسوب الرئيسي يُعيد إرسال حزمته المفقودة. افترض أبرامسون أن تسلسل الحزم المُرسلة إلى القناة المشتركة يتبع عملية بواسون بمعدل G ، وهو مجموع معدل S لوصول الحزم الجديدة إلى المرسلين ومعدل إعادة إرسال الحزم إلى القناة. وبافتراض حالة الاستقرار، بيّن أن معدل إنتاجية القناة هوS=جيهـ-2جي{\displaystyle S=Ge^{-2G}}بقيمة قصوى تبلغ 1/(2 e ) = 0.184 نظريًا.

درس لاري روبرتس قناة ألوها ذات الفترات الزمنية المحددة ، حيث تكفي كل فترة زمنية لإرسال حزمة بيانات. (تُعتبر قناة الأقمار الصناعية التي تستخدم بروتوكول TDMA ذات فترات زمنية محددة). وباستخدام نفس افتراضات عملية بواسون والحالة المستقرة التي استخدمها أبرامسون، أثبت لاري روبرتس أن معدل الإنتاجية الأقصى نظريًا هو 1/ e = 0.368. [ 5 ] كان روبرتس مدير برنامج مشروع أبحاث ARPANET . واستلهامًا من فكرة قناة ألوها ذات الفترات الزمنية المحددة، أطلق روبرتس مشروعًا جديدًا لنظام أقمار ARPANET (ASS) لدمج روابط الأقمار الصناعية في شبكة ARPANET.

أظهرت نتائج المحاكاة التي أجراها أبرامسون وزملاؤه وآخرون أن قناة ألوها، سواءً كانت مُقسّمة إلى فترات زمنية محددة أم لا، غير مستقرة، وقد تتعرض أحيانًا لانهيار الازدحام . ويعتمد الوقت اللازم لحدوث هذا الانهيار على معدل وصول الحزم الجديدة، بالإضافة إلى عوامل أخرى غير معروفة. في عام ١٩٧١، طلب لاري روبرتس من البروفيسور ليونارد كلاينروك وطالبه في الدكتوراه، سيمون لام ، في جامعة كاليفورنيا في لوس أنجلوس، الانضمام إلى مشروع نظام الأقمار الصناعية التابع لشبكة أربانت . سيعمل سيمون لام على استقرار قناة ألوها المُقسّمة إلى فترات زمنية محددة، وتقييم أدائها، والتحكم التكيفي فيها، وذلك ضمن أبحاث أطروحته للدكتوراه. وكانت أول ورقة بحثية شارك في تأليفها مع كلاينروك هي مذكرة نظام الأقمار الصناعية لشبكة أربانت (ASS) رقم ١٢، والتي وُزّعت على مجموعة ASS في أغسطس ١٩٧٢. [ ٦ ] في هذه الورقة، استُخدمت فترة زمنية محددة عشوائيًا ضمن نطاق K فترة زمنية لإعادة الإرسال. من النتائج الجديدة التي توصل إليها النموذج أن زيادة قيمة K تزيد من إنتاجية القناة، والتي تتقارب إلى 1/ e عندما تقترب قيمة K من اللانهاية. وقد احتفظ هذا النموذج بافتراضات وصول البيانات وفقًا لتوزيع بواسون وحالة الاستقرار، ولم يكن مصممًا لفهم السلوك الإحصائي وانهيار الازدحام.

الاستقرار والتراجع التكيفي

لفهم الاستقرار، ابتكر لام نموذج سلسلة ماركوف منفصلة الزمن لتحليل السلوك الإحصائي لبروتوكول ألوها المُقسّم إلى فترات زمنية محددة، وذلك في الفصل الخامس من أطروحته. [ 7 ] يحتوي النموذج على ثلاثة معايير: N و s و p . يُمثل N العدد الإجمالي للمستخدمين. في أي وقت، قد يكون كل مستخدم خاملاً أو محظوراً. يمتلك كل مستخدم حزمة واحدة على الأكثر لإرسالها في الفترة الزمنية التالية. يُنشئ المستخدم الخامل حزمة جديدة باحتمالية s ويرسلها فوراً في الفترة الزمنية التالية. أما المستخدم المحظور، فيرسل حزمته المتراكمة باحتمالية p ، حيث 1/ p = ( K + 1)/2 للحفاظ على متوسط ​​فترة إعادة الإرسال ثابتاً. تمت مقارنة نتائج معدل النقل والتأخير لطريقتي إعادة الإرسال من خلال محاكاة مكثفة، ووُجد أنها متطابقة تقريباً. [ 8 ]

يُقدّم نموذج لام إجابات رياضية دقيقة لمسائل استقرار بروتوكول ألوها المُقسّم إلى فترات زمنية، بالإضافة إلى خوارزمية فعّالة لحساب أداء الإنتاجية مقابل التأخير لأي نظام مستقر. توجد ثلاث نتائج رئيسية، موضحة أدناه، من نموذج سلسلة ماركوف الخاص بلام في الفصل الخامس من أطروحته (والتي نُشرت أيضًا بالاشتراك مع البروفيسور لين كلاينروك، في مجلة IEEE Transactions on Communications ) . [ 9 ]

  1. تُعتبر خوارزمية ألوها ذات الفترات الزمنية المحددة مع وصولات بواسون (أي عدد لا نهائي من الموجات ) غير مستقرة بطبيعتها، لعدم وجود توزيع احتمالي ثابت . (كان الوصول إلى حالة الاستقرار فرضية أساسية استُخدمت في نماذج أبرامسون وروبرتس).
  2. بالنسبة لبروتوكول ALOHA ذي الفتحات الزمنية مع N و K محدودين ، يمكن استخدام نموذج سلسلة ماركوف لتحديد ما إذا كان النظام مستقرًا أم غير مستقر لمعدل إدخال معين ( N × s )، وإذا كان مستقرًا، يتم حساب متوسط ​​تأخير الحزمة ومعدل إنتاجية القناة.
  3. تؤدي زيادة قيمة K إلى زيادة الحد الأقصى لعدد المستخدمين الذين يمكن استيعابهم بواسطة قناة ALOHA مستقرة ذات فترات زمنية محددة. [ 10 ]

نتيجة

بالنسبة لقيمة محدودة ( N × s )، يمكن جعل القناة غير المستقرة لقيمة K الحالية مستقرة عن طريق زيادة K إلى قيمة كبيرة بما يكفي، والتي يشار إليها باسم K ( N , s ). [ 11 ]

التحكم الاستدلالي للتراجع التكيفي

استخدم لام نظرية ماركوف لاتخاذ القرار وطوّر سياسات تحكم مثلى لبروتوكول ألوها المُقسّم إلى فترات زمنية، إلا أن هذه السياسات تتطلب من جميع المستخدمين المحظورين معرفة الحالة الحالية (عدد المستخدمين المحظورين) لسلسلة ماركوف. في عام 1973، قرر لام أنه بدلاً من استخدام بروتوكول معقد لتقدير المستخدمين لحالة النظام، سيُنشئ خوارزمية بسيطة لكل مستخدم لاستخدام معلوماته المحلية، أي عدد التصادمات التي واجهتها حزمته المتراكمة. [ 13 ] بتطبيق النتيجة المذكورة أعلاه، ابتكر لام فئة من خوارزميات التراجع التكيفي أطلق عليها اسم إجراء التحكم في إعادة الإرسال الاستدلالي (Heuristic RCP). [ 12 ] : 894

تتألف خوارزمية RCP الاستدلالية من الخطوات التالية: (1) لنفترض أن m يمثل عدد التصادمات السابقة التي تعرضت لها حزمة بيانات عند المستخدم، كمعلومات تغذية راجعة في حلقة التحكم الخاصة بها . بالنسبة لحزمة بيانات جديدة، يتم تهيئة K (0) إلى 1. (2) تزداد فترة إعادة إرسال الحزمة K ( m ) مع ازدياد m (حتى تستقر القناة، كما هو موضح في النتيجة السابقة). للتنفيذ، مع K (0) = 1، يمكن زيادة K ( m ) بالضرب (أو الجمع) مع ازدياد m.

ملاحظة

يُعدّ التراجع الأسي الثنائي (BEB)، المستخدم في الإيثرنت بعد عدة سنوات، حالة خاصة من التحكم الاستدلالي في التحكم (RCP).ك(م)=2م{\displaystyle K(m)=2^{m}}.

يُعدّ تطبيق خوارزمية BEB سهلاً للغاية. مع ذلك، فهي ليست الأمثل للعديد من التطبيقات لأنها تستخدم العدد 2 كمُضاعِف وحيد، مما يحدّ من مرونة التحسين. على وجه الخصوص، في الأنظمة ذات عدد المستخدمين الكبير، تزيد خوارزمية BEB قيمة K ( m ) ببطء شديد. في المقابل، في الأنظمة ذات عدد المستخدمين القليل، تكفي قيمة K صغيرة نسبيًا لضمان استقرار النظام، ولا حاجة إلى التراجع.

لتوضيح مثال على مسألة RCP ضربية تستخدم عدة مضاعفات، انظر الصف السفلي في الجدول 6.3 في الصفحة 214 من الفصل 6 من أطروحة لام، أو الصف السفلي في الجدول III في الصفحة 902 من ورقة لام-كلاينروك. في هذا المثال:

  1. يتم إرسال حزمة بيانات جديدة فورًا، m = 0، K (0) = 1
  2. بالنسبة لحزمة بيانات ذات تصادم سابق واحد، K (1) = K (0) × 10 = 10 (يقفز المضاعف مباشرة إلى K * = 10 والذي تم العثور عليه كقيمة K المثلى في حالة الاستقرار لهذا النظام المحدد (ALOHA الموقّت لقناة قمر صناعي).
  3. بالنسبة لحزمة بها تصادمان سابقان، فإن K (2) = K (1) × 10 = 100 (تصادم آخر، K يقفز 10 مرات).
  4. K (3) = K (2) × 2 = 200
  5. K ( m ) = K ( m - 1) لـ m ≥ 4

في هذا المثال، تكفي قيمة K = 200 لنظام ALOHA مستقر ذي فتحات زمنية، حيث N تساوي حوالي 400، وهو ما يُستنتج من النتيجة 3 أعلاه. لا حاجة لزيادة قيمة K أكثر من ذلك.

التراجع الأسي المقتطع

يُدخل الإصدار "المختصر" من الخوارزمية حدًا أقصى لقيمة c . وهذا يعني ببساطة أنه بعد عدد معين من الزيادات، يتوقف الرفع الأسي. وبدون حد أقصى لقيمة c ، قد يصبح التأخير بين عمليات الإرسال طويلًا بشكل غير مرغوب فيه إذا لاحظ المرسل بشكل متكرر أحداثًا سلبية، مثل تدهور أداء الشبكة . في نظام عشوائي، قد يحدث هذا بالصدفة، مما يؤدي إلى زمن استجابة غير متوقع؛ أما التأخيرات الأطول الناتجة عن زيادات غير محدودة في قيمة c فهي أقل احتمالًا بشكل كبير، ولكنها حتمية فعليًا في شبكة مزدحمة بسبب قانون الأعداد الكبيرة جدًا . يساعد تحديد قيمة c على تقليل احتمالية حدوث زمن استجابة طويل غير متوقع في الإرسال وتحسين أوقات الاستعادة بعد انقطاع مؤقت.

على سبيل المثال، إذا تم تحديد السقف عند i = 10 في خوارزمية التراجع الأسي الثنائي المقتطع، (كما هو الحال في معيار IEEE 802.3 CSMA/CD [ 14 ] )، فإن الحد الأقصى للتأخير هو 1023 مرة فتحة، أي 2 10 − 1 .

يتطلب اختيار حد التراجع المناسب للنظام تحقيق توازن بين احتمالية التصادم وزمن الاستجابة. فبزيادة الحد الأقصى، تنخفض احتمالية التصادم في كل محاولة إرسال انخفاضًا كبيرًا. وفي الوقت نفسه، تؤدي زيادة الحد أيضًا إلى زيادة كبيرة في نطاق أزمنة الاستجابة المحتملة للإرسال، مما يؤدي إلى أداء أقل قابلية للتنبؤ وزيادة في متوسط ​​زمن الاستجابة. وتختلف قيمة الحد الأمثل للنظام باختلاف كل من التنفيذ والبيئة. [ 15 ]

التراجع المتوقع

بافتراض توزيع منتظم لأوقات التراجع، فإن متوسط ​​وقت التراجع المتوقع هو متوسط ​​الاحتمالات. بعد حدوث c تصادم في خوارزمية التراجع الأسي الثنائي، يتم اختيار التأخير عشوائيًا من [0، 1، ...، N ] خانة، حيث N = 2c - 1 ، ويكون متوسط ​​وقت التراجع المتوقع (بالخانات) هو

هـ⁡(ج)=1شمال+1∑أنا=0شمالأنا=1شمال+1شمال(شمال+1)2=شمال2.{\displaystyle \operatorname {E} (c)={\frac {1}{N+1}}\sum _{i=0}^{N}i={\frac {1}{N+1}}{\frac {N(N+1)}{2}}={\frac {N}{2}}.}

على سبيل المثال، بالنسبة لوقت التراجع المتوقع للتصادم الثالث ( c = 3 )، يمكن للمرء أولاً حساب الحد الأقصى لوقت التراجع، N :

شمال=2ج-1{\displaystyle N=2^{c}-1}
شمال=23-1=8-1{\displaystyle N=2^{3}-1=8-1}
شمال=7،{\displaystyle N=7,}

ثم احسب متوسط ​​احتمالات وقت التراجع:

هـ⁡(ج)=1شمال+1∑أنا=0شمالأنا=1شمال+1شمال(شمال+1)2=شمال2=2ج-12{\displaystyle \operatorname {E} (c)={\frac {1}{N+1}}\sum _{i=0}^{N}i={\frac {1}{N+1}}{\frac {N(N+1)}{2}}={\frac {N}{2}}={\frac {2^{c}-1}{2}}}.

وهذا يعني، على سبيل المثال، E (3) = 3.5 فتحات.

انظر أيضاً

مراجع

  1. ^ تانينباوم وويذرال 2010 ، ص. 395 
  2. ↑ روزنبرغ وآخرون. RFC3261 – SIP: بروتوكول بدء الجلسة . جمعية الإنترنت. 2002.
  3. ↑ بيترسون، لاري ل.؛ ديفي، بروس س. (2022). "الفصل 2: ​​الروابط المباشرة" . شبكات الحاسوب: منهج النظم (  الطبعة السادسة). دار مورغان كوفمان للنشر. ص  120. ISBN 978-0-12-818200-0.
  4. ↑ أبرامسون، نورمان (1970). نظام ألوها - بديل آخر لاتصالات الحاسوب (ملف PDF) . وقائع مؤتمر الحاسوب المشترك لخريف 1970. مطبعة AFIPS.
  5. ↑ روبرتس، لورانس ج. (أبريل 1975). "نظام حزم ألوها مع وبدون فتحات والتقاط". مجلة ACM SIGCOMM لمراجعة اتصالات الحاسوب . 5 (2): 28-42 . doi : 10.1145/1024916.1024920 .
  6. ↑ كلاينروك، ليونارد؛ سيمون س. لام (أغسطس 1972). نتائج تحليلية لنموذج نظام أقمار ARPANET الصناعية، بما في ذلك تأثيرات توزيع تأخير إعادة الإرسال (ملف PDF) (تقرير فني). مركز معلومات شبكة ARPA، معهد ستانفورد للأبحاث ، مينلو بارك، كاليفورنيا. مذكرة ASS رقم 12 (NIC 11294).
  7. ↑ لام، سيمون س. (مارس 1974). تبديل الحزم في قناة بث متعددة الوصول مع تطبيق على الاتصالات عبر الأقمار الصناعية في شبكة حاسوب، أطروحة دكتوراه، 306 صفحات (رسالة). UCLA-ENG-7429 (ARPA)، كلية الهندسة والعلوم التطبيقية بجامعة كاليفورنيا في لوس أنجلوس.
  8. ↑ الشكل 5-1 في الصفحة 100، الفصل 5، في أطروحة لام
  9. ↑ كلاينروك، ليونارد؛ لام، س.، سيمون (أبريل 1975). "تبديل الحزم في قناة بث متعددة الوصول: تقييم الأداء" (ملف PDF) . معاملات IEEE في الاتصالات . COM-23 (4): 410-423 . Bibcode : 1975ITCom..23..410K . doi : 10.1109/TCOM.1975.1092814 . تاريخ الاسترجاع : 16 فبراير 2023 .
  10. ↑ الشكل 5-9 في الصفحة 114 في الفصل 5 من أطروحة لام، أو الشكل 10 في الصفحة 418 في ورقة كلاينروك-لام لعام 1975.
  11. ↑ الشكل 5-10 في الصفحة 116 في الفصل 5 من أطروحة لام، أو الشكل 11 في الصفحة 418 في ورقة كلاينروك-لام لعام 1975.
  12. لام ، سيمون س.؛ كلاينروك ، ليونارد (سبتمبر 1975). "تبديل الحزم في قناة بث متعددة الوصول: إجراءات التحكم الديناميكي" (ملف PDF) . معاملات IEEE في الاتصالات . COM-23 (9): 891-904 . Bibcode : 1975ITCom..23..891L . doi : 10.1109/TCOM.1975.1092917 . تاريخ الاسترجاع: 16 يوليو 2023 .
  13. ↑ انظر الخوارزمية 4 في الصفحات 901-902 في ورقة لام-كلاينروك [ 12 ] أو القسم الفرعي 6.7.2، في الصفحات 209-210 في الفصل 6 من أطروحة لام.
  14. ↑ "معيار IEEE 802.3-2015" . IEEE . تم الاطلاع عليه بتاريخ 20 مارس 2022 .(شراء)
  15. ^ تانينباوم وويذرال 2010 ، ص. 285 . 

فهرس

  • تانينباوم، أندرو؛ ويذرال، ديفيد (2010). شبكات الحاسوب (  الطبعة الخامسة). بيرسون. ISBN 978-0132126953.

المجال العام تتضمن هذه المقالة موادًا متاحة للعموم من المعيار الفيدرالي 1037C ، إدارة الخدمات العامة . مؤرشفة من الأصل في 22 يناير 2022.