توکن باکت

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

بررسی اجمالی

الگوریتم توکن باکت بر اساس تشابه یک سطل با ظرفیت ثابت است که در آن توکن(ژتون)‌هایی که به طور معمول نمایانگر یک واحد بایت یا یک بسته واحد با اندازه‌ی از پیش تعیین شده هستند، با نرخ ثابت اضافه می‌شوند. وقتی قرار است بسته‌ای از نظر انطباق با محدودیت‌های تعیین شده بررسی شود، سطل بازرسی می‌شود تا مشخص شود آیا در آن زمان دارای توکن‌‌های کافی است. در صورت وجود تعداد مناسبی از توکن‌ها، مثلاً معادل طول بسته در واحد بایت، حذف می‌شوند ("مصرف می‌شوند")، و بسته ارسال می‌شود. (به عنوان مثال، برای انتقال.) اگر توکن‌های کافی در سطل وجود نداشته باشد و محتوای سطل تغییر نکند، بسته ارسال نمی‌شود (بسته‌های غیرمطابق). با بسته‌هایی که ارسال نمی‌شوند می‌توان کارهای متفاوتی کرد:

• ممکن است رها شوند.
• ممکن است برای انتقال‌های بعدی نگه‌ داشته شوند، تا وقتی که توکن کافی در سطل جمع شود.
• ممکن است منتقل شوند، اما به عنوان غیرمطابق علامت‌گذاری شوند و در صورت بارگیری بیش از حد شبکه، شاید بعداً حذف شوند.

بنابراین جریان مطابق می‌تواند شامل ترافیکی با سرعت متوسط حداکثر به اندازه‌ی سرعت افزودن توکن‌ها به سطل باشد و دارای میزان انفجار متناسب با عمق سطل باشد. این انفجار ممکن است به صورت تحمل لرزش بیان شود، یعنی چقدر زودتر از حد انتظار برای نرخ متوسط، یا تحمل انفجار یا حداکثر اندازه انفجار بسته ارسال شود (مثلاً وارد شود یا منتقل شود). یعنی چقدر بیشتر از سطح متوسط ترافیک ممکن است در بازه‌های محدودی مطابقت داشته باشد.

الگوریتم

الگوریتم توکن باکت را می‌توان از نظر مفهومی به شرح زیر درک کرد:

• هر توکن در هر $1/r$ ثانیه به سطل اضافه می‌شود.
• سطل حداکثر می‌تواند $b$ توکن در خود جای دهد. اگر توکنی هنگام پر بودن سطل رسید، آن را کنار می‌گذاریم.
• هنگامی که یک بسته (لایه شبکه PDU) از n بایت وارد می‌شود،
  • اگر حداقل n توکن در سطل باشد، n توکن از سطل برداشته می‌شود و بسته به شبکه ارسال می‌شود.
  • اگر کمتر از n توکن در دسترس باشد، هیچ توکنی از سطل حذف نمی‌شود و بسته غیرمطابق در نظر گرفته می‌شود.

انواع پیاده‌سازی

برای پیاده‌سازی‌ این الگوریتم در سیستم‌هایی که دقت زمانی لازم برای افزودن یک توکن به سطل در هر $1/r$ ثانیه را ندارند، ممکن است یک فرمول جایگزین در نظر گرفته شود. با توجه به قابلیت به روزرسانی توکن‌ باکت در هر S میلی‌ثانیه، تعداد توکن‌ها برای اضافه شدن در هر S میلی‌ثانیه برابر است با $(r*S)/1000$.

خواص

نرخ متوسط

در طولانی مدت، تعداد بسته‌های مطابق با نرخ توکن (token rate) $r$ محدود می شوند.

اندازه انفجار

$M$ را حداکثر سرعت انتقال ممکن در بایت/ثانیه در نظر بگیرید.

سپس $T_{\text{max}}={\begin{cases}b/(M-r)&{\text{ if }}r<M\\\infty &{\text{ otherwise }}\end{cases}}$ حداکثر زمان انفجار است، یعنی زمانی که نرخ$M$ کاملاً استفاده شده است.

بنابراین حداکثر اندازه‌ی انفجار $B_{\text{max}}=T_{\text{max}}*M$ است.

کاربرد‌ها

توکن باکت را می‌توان در شکل‌دهی ترافیک یا کنترل ترافیک استفاده کرد. در کنترل ترافیک، بسته‌های غیرمطابق ممکن است کنار گذاشته شوند (رها شوند) یا ممکن است از اولویت آنها کاسته شود (برای مدیریت ترافیک پایین‌دستی، در صورت ازدحام، رها می‌شوند). در شکل‌‌دهی ترافیک، بسته‌ها تا زمانی که غیرمطابق هستند نگه داشته می‌شوند. کنترل ترافیک و شکل‌دهی ترافیک معمولاً برای محافظت از شبکه در برابر ترافیک بیش از حد یا پرانفچار استفاده می‌شوند، به مدیریت پهنای باند و جلوگیری از ازدحام مراجعه کنید. برای جلوگیری از نادیده‌گرفتن انتقال توسط توابع مدیریت ترافیک در شبکه، از شکل‌دهی ترافیک معمولاً در رابط‌های شبکه در میزبان استفاده می‌شود.

منابع

• Wikipedia contributors, "Token bucket," Wikipedia, The Free Encyclopedia, https://en.wikipedia.org/wiki/Token_bucket (accessed March 31, 2021).