الگوریتم نیگل

الگوریتم Nagle (نِیگِل) وسیله ای برای بهبود کارایی شبکه‌های TCP / IP بوسیله کاهش تعداد بسته‌هایی که لازم است بر بستر شبکه ارسال شوند. این الگوریتم توسط جان نِیگِل در هنگامی که مشغول کار در شرکت فورد بود، طراحی شد و در سال ۱۹۸۴ به عنوان یک (RFC) با عنوان کنترل ازدحام در شبکه‌های TCP / IP منتشر شد (به RFC 896 مراجعه کنید).

در این RFC آنچه که او (مشکل بسته‌های کوچک) می‌نامد را توصیف می‌کند، که در آن برنامه‌ای به‌طور مکرر داده‌ها را در تکه‌های کوچک (اغلب فقط با اندازهٔ ۱ بایت) منتشرمیکند. از آنجا که بسته‌های TCP دارای یک هدر ۴۰ بایتی (۲۰ بایت برای TCP و ۲۰ بایت برای IPv4)، در نتیجه تنها برای ارسال یک فایل ۱ بایتی از اطلاعات مفید یک بسته ۴۱ بایتی نیاز است، که این یک سربار بسیار بزرگ است. این وضعیت اغلب در جلسات Telnet به وقوع می‌پیوندد، که در آن بیشتر دستورات به وسیله فشار دادن صفحه کلید داده‌های یک بایتی تولید می‌کنند که سریعاً منتقل می‌شود. بدتر از آن، بر بستر لینک‌های کند، بسیاری از این بسته‌ها می‌توانند همزمان در حال ارسال باشند و پتانسیل رخ دادن یک فروپاشی ازدحامی وجود دارد.

الگوریتم نیگل با تلفیق تعدادی پیام کوچک خروجی و ارسال همه آنها به‌طور یکجا کار می‌کند. به‌طور خاص، تا زمانی که یک بسته ارسالی وجود داشته باشد که فرستنده برای آن هیچ گونه تأییدیه ای(ACK در TCP) دریافت نکرده باشد، فرستنده باید تا زمانی که یک خروجی کامل که ارزش ارسال داشته باشد باید بسته‌ها را بافر کند، بنابراین این کار باعث می‌شود که خروجی یک پکت بزرگ باشد و مشکل سربار حل شود.

 الگوریتم 
RFC الگوریتم نیگل را اینگونه تعریف می‌کند:

جلوگیری از ارسال سگمنت جدید TCP هنگامی که داده‌های خروجی جدید از کاربر وارد می‌شوند اگر که داده‌های منتقل‌شده قبلی بر روی این ارتباط همچنان تصدیق نشده باقی بماند.

MSS را حداکثر اندازه هر قطعه تعریف می‌کنیم، به عبارت دیگر بزرگترین قطعه ای که می‌تواند در این اتصال ارسال شود، و اندازه پنجره همان اندازه حداکثری از تعداد بسته‌های ACK نشده در TCP است، می‌توانیم این را به صورت سودوکد زیر بنویسیم:

  if there is new data to send
  if the window size>= MSS and available data is>= MSS
  send complete MSS segment now
  else
  if there is unconfirmed data still in the pipe
  enqueue data in the buffer until an acknowledge is received
  else
  send data immediately
  end if
  end if
 end if

این الگوریتم با حالت تأخیر ACK در پروتکل TCP (ACK تأخیری) به به مشکل می‌خورد، ویژگی ای که تقریباً در همان زمان در اوایل دهه ۱۹۸۰ درTCP توسط تیم دیگری معرفی شد. در حالت فعال بودن هر دو الگوریتم، برنامه‌هایی که دو خروجی پی در پی را در اتصال TCP انجام می‌دهند، که به دنبال آن یک خواندن وجود دارد که تا زمانی که داده‌های خروجی دوم به مقصد نرسیده باشند، تأخیر ثابت تا ۵۰۰ میلی ثانیه را تجربه می‌کنید ،(تأخیر ACK). به همین دلیل، پیاده‌سازی‌های TCP معمولاً برای غیرفعال کردن الگوریتم نیگل، در واسط کاربری خود یک گزینه قرار می‌دهند. این به‌طور معمول گزینه TCP_NODELAY نامیده می‌شود. در ویندوز رجیستری TcpNoDelay مقدار پیش فرض آن را تعیین می‌کند.

راه حل توصیه شده توسط نیگل این است، که جلوی الگوریتم گرفته شود تا بسته‌های تکمیل نشده را زود ارسال نکند و ابتدا آن‌ها را بافر کند و سپس بافر را در اتصال خالی کند:  راه حل در سطح کاربر جلوگیری از توالی نوشتن-نوشتن-خواندن در سوکت است. نوشتن-خواندن-نوشتن-خواندن خوب است. نوشتن-نوشتن-نوشتن خوب است. اما نوشتن-نوشتن-خواندن بلای جان این الگوریتم است؛ بنابراین، در صورت امکان، بسته‌های کوچک خود را در TCP بافر کنید و همه آنها را یکجا ارسال کنید. استفاده از بسته استاندارد UNIX I/O و ارسال بسته‌ها پیش از هر خواندن معمولاً مؤثر واقع می‌شود.  نیگل، ACK های تأخیری را -ایده بد- در نظر می‌گیرد، زیرا معمولاً لایه کاربردی معمولاً در پنجره زمانی پاسخ نمی‌دهد. در سطح پروتکل، او توصیه می‌کند به جای الگوریتم خود "تأخیر ACK" (به عنوان مثال توسط TCP_QUICKACK در لینوکس) را غیرفعال کنید، زیرا ACK های "سریع" به اندازه بسته‌های کوچک سربار ندارند. در ویندوز، تنظیم کردن TcpAckFrequency به ۱ در رجیستری تأثیر مشابهی خواهد داشت. در ضمن مقدار، TcpAckFrequency ، نیز حداکثر زمان تأخیر برای ACK را کنترل می‌کند. درنتیجه می‌توان آن را روی صفر تنظیم کرد تا ACKS با تأخیر غیرفعال شود.

 تأثیر منفی بر روی ارسال‌های بزرگتر 
این الگوریتم برای داده‌هایی از هر اندازه اعمال می‌شود. اگر داده‌های یک ارسال در بسته‌های به تعداد 2n باشد، آخرین بسته نگه داشته می‌شود و منتظر ACK برای بسته قبلی می‌ماند. در هر پروتکل لایه کاربردی درخواست-پاسخ محور که در آن داده‌های درخواست می‌توانند از یک بسته بزرگتر باشند، این الگوریتم می‌تواند تأخیر چند صد میلی ثانیه ای را بین درخواست کننده و پاسخ دهنده تحمیل کند، حتی اگر درخواست کننده داده‌های درخواست را به درستی بافر کرده باشد. در این حالت، الگوریتم نیگل باید توسط درخواست کننده غیرفعال شود. اگر داده‌های پاسخ می‌توانند بزرگتر از یک بسته باشند، پاسخ دهنده نیز همچنین باید الگوریتم نیگل را غیرفعال کند تا درخواست کننده بتواند سریعاً کل پاسخ را دریافت کند.

به‌طور کلی، از آنجا که الگوریتم نیگل فقط یک لایه التیام دهنده برای برنامه‌های بی دقت لایه کابرد است، درنتیجه برای یک برنامه که با دقت نوشته شده و با دقت بافر خود را مدیریت می‌کند فایده ای ندارد و حتی بعضاً تأثیر منفی بر کارکرد برنامه دارد.

 تعامل با سیستم‌های بی درنگ 
برنامه‌های کاربردی که انتظار پاسخ‌های بدون درنگ و زمان تأخیر کم دارند، نیز ممکن است در مواجه با این الگوریتم بسیار ضعیف عمل کنند. برنامه‌های نظیر شبکه چند نفره بازی‌های ویدئویی یا حرکت ماوس در یک کنترل از راه دور سیستم عامل انتظار می‌رود که دستورات بی درنگ فرستاده شوند در حالی که این الگوریتم به صورت هدفمند ارسال را به تأخیر میندازد و افزایش بهره‌وری پهنای باند را به بهای افزایش زمان تأخیر انجام می‌دهد. به همین دلیل برنامه‌های با پهنای باند کم و حساس به زمان انتقال به‌طور معمول با استفاده از TCP_NODELAY تاخیرهای الگوریتم نیگل در ارسال ACK را دور می‌زنند.Bug 17868 – Some Java applications are slow on remote X connections.

 پیاده‌سازی سیستم عامل‌ها 
اکثر سیستم عامل‌های مدرن الگوریتم‌های نیگل را پیاده‌سازی می‌کنند. در AIX و لینوکس و ویندوز این الگوریتم به‌طور پیش فرض فعال شده و با استفاده از گزینه TCP_NODELAY می‌تواند به صورت جداگانه در هر سوکت غیرفعال شود.

 منابع 



 پیوند به بیرون 
 Nagle delays in Nagle's Algorithm
 Nagle's algorithm
 TCP Performance problems caused by interaction between Nagle's Algorithm and Delayed ACK
 Design issues - Sending small data segments over TCP with Winsock

رده:الگوریتم‌های شبکه‌سازی
رده:قرارداد هدایت انتقال