خوارزمية ناجل

الموسوعة الحرة

خوارزمية ناغل هي وسيلة لتحسين كفاءة شبكات TCP/IP عن طريق تقليل عدد الحزم التي يجب إرسالها عبر الشبكة. وقد وضعها جون ناغل أثناء عمله في شركة فورد للفضاء . ونُشرت عام 1984 كطلب تعليقات (RFC) بعنوان " التحكم في الازدحام في شبكات IP/TCP" في RFC 896 . 

يصف معيار RFC ما يسميه ناغل "مشكلة الحزم الصغيرة"، حيث يقوم تطبيق ما بإرسال البيانات بشكل متكرر في أجزاء صغيرة، غالبًا بحجم بايت واحد فقط. ونظرًا لأن حزم TCP تحتوي على رأس بحجم 40 بايت (20 بايت لـ TCP، و20 بايت لـ IPv4 )، ينتج عن ذلك حزمة بحجم 41 بايت تحتوي على بايت واحد من المعلومات المفيدة، وهو ما يمثل عبئًا كبيرًا. غالبًا ما يحدث هذا في جلسات Telnet ، حيث تُولّد معظم ضغطات المفاتيح بايتًا واحدًا من البيانات يتم إرساله فورًا. والأسوأ من ذلك، أنه عبر الروابط البطيئة، يمكن أن تكون العديد من هذه الحزم قيد النقل في الوقت نفسه، مما قد يؤدي إلى انهيار الازدحام .

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

الخوارزمية

تحدد وثيقة RFC الخوارزمية على النحو التالي:

منع إرسال أجزاء TCP جديدة عند وصول بيانات صادرة جديدة من المستخدم إذا لم يتم تأكيد استلام أي بيانات تم إرسالها مسبقًا على الاتصال.

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

إذا كانت هناك بيانات جديدة لإرسالها ، فإذا كان حجم النافذة ≥ MSS وكانت البيانات المتاحة ≥ MSS ، أرسل مقطع MSS كاملاً الآن أما إذا كانت هناك بيانات غير مؤكدة لا تزال قيد المعالجة، فـ قم بتخزين البيانات في المخزن المؤقت حتى يتم استلام إشعار تأكيد. آخر أرسل البيانات فوراً نهاية الشرط نهاية الشرط نهاية الشرط

التفاعل مع إقرار الاستلام المتأخر

يتفاعل هذا الخوارزمية بشكل سيئ مع خاصية إقرارات TCP المتأخرة (Dlayed ACK)، وهي ميزة أُضيفت إلى TCP في نفس الفترة تقريبًا في أوائل ثمانينيات القرن الماضي، ولكن من قِبل فريق مختلف. عند تفعيل كلا الخوارزميتين، تواجه التطبيقات التي تُجري عمليتي كتابة متتاليتين على اتصال TCP، متبوعتين بعملية قراءة لن تكتمل إلا بعد وصول بيانات الكتابة الثانية إلى الوجهة، تأخيرًا ثابتًا يصل إلى 500 مللي ثانية، وهو ما يُعرف بـ " تأخير ACK ". يُنصح بتعطيل أيٍّ منهما، مع أن تعطيل خوارزمية Nagle أسهل عادةً، نظرًا لوجود خيار مماثل مُتاح بالفعل لتطبيقات الوقت الحقيقي.

الحل الذي أوصى به ناجل، والذي يمنع الخوارزمية من إرسال الحزم قبل الأوان، هو تخزين عمليات الكتابة الخاصة بالتطبيق مؤقتًا ثم مسح المخزن المؤقت: [ 1 ]

الحل الأمثل على مستوى المستخدم هو تجنب تسلسلات الكتابة-الكتابة-القراءة على المقابس. تسلسل الكتابة-القراءة-الكتابة-القراءة مقبول، وكذلك تسلسل الكتابة-الكتابة-القراءة. لكن تسلسل الكتابة-الكتابة-القراءة يُعدّ كارثيًا. لذا، إن أمكن، قم بتجميع عمليات الكتابة الصغيرة إلى بروتوكول TCP مؤقتًا وأرسلها دفعة واحدة. عادةً ما ينجح استخدام حزمة الإدخال/الإخراج القياسية في أنظمة UNIX وتفريغ عملية الكتابة قبل كل عملية قراءة.

يعتبر ناغل تأخير إشعارات الاستلام "فكرة سيئة" لأن طبقة التطبيق لا تستجيب عادةً خلال فترة التأخير (مما يسمح بدمج إشعار الاستلام مع حزمة الاستجابة). [ 2 ] في حالات الاستخدام العادية (غير الآنية)، يوصي بتعطيل إشعارات الاستلام المتأخرة بدلاً من تعطيل خوارزميته، لأن إشعارات الاستلام "السريعة" لا تُسبب عبئًا إضافيًا كبيرًا مثل العديد من الحزم الصغيرة لتحقيق نفس التحسين في زمن الاستجابة. [ 3 ]

تعطيل إما Nagle أو ACK المؤجل

توفر تطبيقات بروتوكول TCP عادةً واجهةً لتعطيل خوارزمية Nagle. يُطلق على هذا TCP_NODELAYالخيار عادةً اسم "خيار تعطيل الخوارزمية". في نظام التشغيل Microsoft Windows، يُحدد مفتاح TcpNoDelayالتسجيل القيمة الافتراضية. TCP_NODELAYيُستخدم هذا الخيار منذ حزمة بروتوكولات TCP/IP في نظام 4.2BSD عام 1983، وهي حزمة لها العديد من الإصدارات اللاحقة. [ 4 ]

تختلف واجهة تعطيل إشعار الاستلام المتأخر بين الأنظمة. TCP_QUICKACKيتوفر هذا الخيار في نظام لينكس منذ عام 2001 (الإصدار 2.4.4)، وربما في نظام ويندوز، حيث الواجهة الرسمية هي [ 5 ]SIO_TCP_SET_ACK_FREQUENCY .

يؤدي ضبط القيمة TcpAckFrequencyعلى 1 في سجل نظام ويندوز إلى تعطيل خاصية تأكيد الاستلام المتأخر افتراضيًا. [ 6 ] في نظام FreeBSD، يتحكم إدخال sysctl net.inet.tcp.delayed_ack في السلوك الافتراضي. [ 4 ] لا يوجد مثل هذا الخيار في نظام لينكس. [ 7 ]

حالة الكتابة الكبيرة

يمتد التفاعل بين ACK المؤجل وخوارزمية Nagle ليشمل عمليات الكتابة الأكبر حجمًا. فإذا امتدت البيانات في عملية كتابة واحدة على 2 ^n حزمة، حيث يوجد 2 ^n - 1 مقطع TCP كامل الحجم متبوعًا بمقطع TCP جزئي، فإن خوارزمية Nagle الأصلية ستحجب الحزمة الأخيرة، منتظرةً إما المزيد من البيانات لإرسالها (لملء الحزمة)، أو ACK للحزمة السابقة (مما يشير إلى أن جميع الحزم السابقة قد غادرت الشبكة). ويضيف ACK المؤجل، مرة أخرى، مدة أقصاها 500  مللي ثانية قبل إرسال الحزمة الأخيرة. [ 8 ] يحد هذا السلوك من أداء بروتوكولات تطبيقات الطلب والاستجابة غير المتوازية، مثل HTTP، ذات الاتصال المستمر. [ 9 ]

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

التفاعلات مع الأنظمة الآنية

قد لا تتفاعل التطبيقات التي تتطلب استجابات فورية وزمن استجابة منخفض بشكل جيد مع خوارزمية ناغل. فعلى سبيل المثال، تتوقع تطبيقات مثل ألعاب الفيديو متعددة اللاعبين عبر الشبكة أو حركة الفأرة في نظام تشغيل يتم التحكم فيه عن بُعد، إرسال الأوامر فورًا، بينما تؤخر الخوارزمية الإرسال عمدًا، مما يزيد من كفاءة عرض النطاق الترددي على حساب زمن الاستجابة أحادي الاتجاه . [ 3 ] لهذا السبب، تستخدم التطبيقات ذات عمليات الإرسال الحساسة للوقت والتي تتطلب عرض نطاق ترددي منخفض عادةً تقنية TCP_NODELAYلتجاوز تأخير إقرار الاستلام (ACK) الناتج عن خوارزمية ناغل. [ 11 ]

خيار آخر هو استخدام بروتوكول UDP بدلاً من ذلك.

تنفيذ أنظمة التشغيل

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

مراجع

  1. ↑ جون ناجل (19 يناير 2006)، تحسين أداء المقابس على لينكس ، سلاش دوت
  2. ↑ ناغل، جون. "آه. إذا كنت تقوم بنقل ملفات بكميات كبيرة، فلن تواجه هذه المشكلة أبدًا. (الرد رقم 9048947)" . هاكر نيوز . تم الاطلاع عليه في 9 مايو 2018 .
  3. 1 2 ناغل، جون. "كان مؤقت تأخير الإقرار الثابت البالغ 200 مللي ثانية خطأً فادحًا. لماذا 200 مللي ثانية؟ زمن رد فعل الإنسان. (الرد 9050645)" . هاكر نيوز . تم الاطلاع عليه في 9 مايو 2018. [...] من الحالات القليلة المشروعة لإيقاف خوارزمية ناغل هي ألعاب إطلاق النار من منظور الشخص الأول التي تعمل عبر الإنترنت. في هذه الألعاب، يُعد زمن الاستجابة أحادي الاتجاه مهمًا؛ إذ يؤثر وصول طلقاتك وحركاتك إلى الخادم قبل اللاعبين الآخرين على أسلوب اللعب.
  4. 1 2 – دليل واجهات نواة FreeBSDtcp(4)  
  5. ↑ "sockets - تعطيل خاصية Delayed Ack في نظام ويندوز باستخدام لغة C++" . موقع Stack Overflow .
  6. ↑ "إدخال جديد في سجل النظام للتحكم في سلوك تأكيد TCP (ACK) في نظامي التشغيل Windows XP وWindows Server 2003" . 23 فبراير 2023.
  7. ↑ – دليل مبرمج لينكس – نظرة عامة، واصطلاحات، ومعلومات متنوعة من موقع Manned.orgtcp(7)  
  8. ↑ "مشاكل أداء بروتوكول TCP الناتجة عن التفاعل بين خوارزمية ناجل وتأخر إشعار الاستلام" . Stuartcheshire.org . تم الاطلاع عليه بتاريخ 14 نوفمبر 2012 .
  9. ↑ هايدمان، جون (أبريل 1997). "تفاعلات الأداء بين تطبيقات P-HTTP وTCP" . مجلة ACM SIGCOMM لمراجعة اتصالات الحاسوب . 27 (2). ACM: 65-73 . doi : 10.1145/263876.263886 . S2CID 6992265 . 
  10. ↑ تعديل مقترح لخوارزمية ناجل . IETF . 1999. المعرف draft-minshall-nagle.
  11. ↑ خطأ رقم 17868 - بعض تطبيقات جافا بطيئة على اتصالات X البعيدة .
  12. ↑ "مركز معارف IBM" . www.ibm.com .