Generic cell rate algorithm
عام سیل ریٹ الگورتھم (جی سی آر اے) نیٹ ورک شیڈولر کے لیے ایک لیک بالٹی قسم کا شیڈولنگ الگورتھم ہے جو اسنکرونس ٹرانسفر موڈ (اے ٹی ایم) نیٹ ورکس میں استعمال ہوتا ہے۔ یہ وی سی یا وی پی کے لیے ٹریفک معاہدے میں موجود بینڈوتھ اور جٹر حدود کے خلاف ورچوئل چینلز (وی سیز) اور یا ورچوئل پاتھز (وی پیز) پر خلیوں کے وقت کی پیمائش کرنے کے لیے استعمال ہوتا ہے جس سے خلیات تعلق رکھتے ہیں۔ وہ خلیے جو ٹریفک معاہدے کے ذریعہ دی گئی حدود کے مطابق نہیں ہیں پھر ٹریفک کی تشکیل میں دوبارہ وقت (تاخیر) کیا جا سکتا ہے، یا ٹریفک پولیسنگ میں گرایا جا سکتا ہے (ضائع کیا جا سکتا ہے) یا ترجیحی طور پر کم کیا جا سکتا ہے (کم کیا جا سکتا ہے)۔ غیر مطابقت پذیر خلیات جنہیں ترجیحی لحاظ سے کم کیا جاتا ہے، انہیں پھر اعلی ترجیحی خلیات کو ترجیح دیتے ہوئے، نیٹ ورک میں نیچے کی طرف والے اجزاء کے ذریعے گرایا جا سکتا ہے جو بھیڑ کا سامنا کر رہے ہیں۔ متبادل طور پر وہ اپنی منزل (وی سی یا وی پی ٹرمینیشن) تک پہنچ سکتے ہیں اگر ان کے لیے کافی گنجائش ہو، اس کے باوجود کہ وہ اضافی سیل ہیں جہاں تک معاہدے کا تعلق ہے: ترجیحی کنٹرول دیکھیں۔ جی سی آر اے نیٹ ورک میں کنکشن پر ٹریفک کی جانچ کے لیے حوالہ کے طور پر دیا گیا ہے، یعنی۔ یوزر نیٹ ورک انٹرفیس (یو این آئی) یا انٹر نیٹ ورک انٹرفیس یا نیٹ ورک نیٹ ورک انٹرفیس (آئی این آئی/این این آئی) پر استعمال/نیٹ ورک پیرامیٹر کنٹرول (یو پی سی/این پی سی)۔ یہ میزبان میں نیٹ ورک انٹرفیس کارڈ (این آئی سی) کے ذریعے اے ٹی ایم نیٹ ورک پر منتقل ہونے والے خلیوں (اے ٹی ایم پی ڈی یو ڈیٹا _ ریکویسٹ) کے وقت کے حوالے کے طور پر بھی دیا جاتا ہے، یعنی۔ یو این آئی کے صارف کی طرف۔ یہ اس بات کو یقینی بناتا ہے کہ خلیات کو پھر نیٹ ورک میں یو پی سی/این سی پی کے ذریعے خارج نہیں کیا جاتا، یعنی۔ یو این آئی کے نیٹ ورک سائیڈ پر۔ تاہم، چونکہ جی سی آر اے صرف ایک حوالہ کے طور پر دیا گیا ہے، نیٹ ورک فراہم کرنے والے اور صارفین کوئی بھی دوسرا الگورتھم استعمال کر سکتے ہیں جو ایک ہی نتیجہ دیتا ہے۔ جی سی آر اے کی تفصیل جی سی آر اے کو اے ٹی ایم فورم نے اپنے یوزر نیٹ ورک انٹرفیس (یو این آئی) میں اور آئی ٹی یو-ٹی نے بی-آئی ایس ڈی این میں ٹریفک کنٹرول اور بھیڑ کنٹرول کی سفارش میں بیان کیا ہے۔ دونوں ذرائع جی سی آر اے کو دو مساوی طریقوں سے بیان کرتے ہیں: ایک ورچوئل شیڈولنگ الگورتھم کے طور پر اور ایک مسلسل اسٹیٹ لیک بالٹی الگورتھم کے طور پر (شکل 1)۔ لیک بالٹی تفصیل لیک بالٹی الگورتھم کے لحاظ سے تفصیل کو تصوراتی نقطہ نظر سے سمجھنا دونوں میں سے آسان ہو سکتا ہے، کیونکہ یہ لیک کے ساتھ بالٹی کی سادہ مشابہت پر مبنی ہے: لیک بالٹی پیج پر شکل 1 دیکھیں۔ تاہم، ایک الگورتھم تیار کرنے کے لیے لیک بالٹی مشابہت کے اطلاق پر ادب میں الجھن پیدا ہوئی ہے، جو جی سی آر اے کو عبور کر چکی ہے۔ جی سی آر اے کو قطار کے طور پر رسنے والی بالٹی کے بجائے میٹر کے طور پر رسنے والی بالٹی کا ایک ورژن سمجھا جانا چاہیے۔ تاہم، اگرچہ اس لیک ہونے والی بالٹی کی تفصیل کو سمجھنے میں ممکنہ فوائد ہیں، لیکن اگر براہ راست لاگو کیا جائے تو یہ ضروری نہیں کہ بہترین (تیز ترین) کوڈ کا نتیجہ ہو۔ اس کا ثبوت دو وضاحتوں (شکل 1) کے لیے بہاؤ کے خاکے میں انجام دیے جانے والے اعمال کی نسبتا تعداد سے ملتا ہے۔ مسلسل ریاستی لیک بالٹی الگورتھم کے لحاظ سے تفصیل آئی ٹی یو-ٹی کی طرف سے درج ذیل دی گئی ہے: "مسلسل ریاستی لیک بالٹی کو ایک محدود صلاحیت والی بالٹی کے طور پر دیکھا جا سکتا ہے جس کا حقیقی قدر والا مواد 1 یونٹ فی ٹائم یونٹ کی مسلسل شرح سے باہر نکلتا ہے اور جس کے مواد میں ہر کنفارمنگ سیل کے لیے انکریمنٹ ٹی سے اضافہ ہوتا ہے۔ اگر سیل کی آمد پر بالٹی کا مواد لمٹ ویلیو τ سے کم یا اس کے برابر ہے، تو سیل مطابقت رکھتا ہے ؛ بصورت دیگر، سیل غیر مطابقت رکھتا ہے۔ بالٹی (کاؤنٹر کی اوپری باؤنڈ) کی گنجائش (T + τ) "ہے۔ یہ بات قابل غور ہے کہ چونکہ رساو مواد کی ایک اکائی فی اکائی وقت ہے، اس لیے ہر سیل T کے لیے اضافہ اور حد کی قیمت τ وقت کی اکائیوں میں ہوتی ہے۔ مسلسل حالت لیک بالٹی الگورتھم کے بہاؤ کے خاکے پر غور کرتے ہوئے، جس میں T اخراج کا وقفہ ہے اور τ حد کی قیمت ہے: جب کوئی خلیہ آتا ہے تو کیا ہوتا ہے کہ بالٹی کی حالت کا حساب اس کی حالت سے لگایا جاتا ہے جب آخری مطابقت پذیر خلیہ آتا ہے، X، اور وقفے میں کتنا باہر نکل گیا ہے، ta-LCT۔ اس موجودہ بالٹی ویلیو کو پھر X 'میں محفوظ کیا جاتا ہے اور اس کا موازنہ لمٹ ویلیو τ سے کیا جاتا ہے۔ اگر X 'میں قدر τ سے زیادہ نہیں ہے، تو سیل بہت جلد نہیں پہنچا اور اس لیے معاہدہ کے پیرامیٹرز کے مطابق ہے۔ اگر X' میں قدر τ سے زیادہ ہے، تو یہ مطابقت نہیں رکھتا ہے۔ اگر یہ مطابقت رکھتا ہے، اگر یہ دیر ہونے کی وجہ سے مطابقت رکھتا ہے، یعنی۔ بالٹی خالی (X '<= 0)، X کو T پر سیٹ کیا جاتا ہے ؛ اگر یہ جلدی تھی، لیکن بہت جلدی نہیں، (τ> = X'> 0)، X کو X '+ T پر سیٹ کیا جاتا ہے۔ اس طرح بہاؤ کا خاکہ لیک بالٹی کی مشابہت (میٹر کے طور پر استعمال ہوتا ہے) کی براہ راست نقل کرتا ہے، جس میں X اور X' بالٹی کے ینالاگ کے طور پر کام کرتے ہیں۔ ورچوئل شیڈولنگ تفصیل ورچوئل شیڈولنگ الگورتھم، اگرچہ اتنا واضح طور پر لیک بالٹی جیسی آسانی سے قابل رسائی مشابہت سے متعلق نہیں ہے، لیکن یہ اس بات کی واضح تفہیم فراہم کرتا ہے کہ جی سی آر اے کیا کرتا ہے اور اسے کس طرح بہترین طریقے سے نافذ کیا جا سکتا ہے۔ نتیجے کے طور پر، اس ورژن کے براہ راست نفاذ کے نتیجے میں لیک بالٹی کی تفصیل کے براہ راست نفاذ کے مقابلے میں زیادہ کمپیکٹ، اور اس طرح تیز تر کوڈ ہو سکتا ہے۔ ورچوئل شیڈولنگ الگورتھم کے لحاظ سے تفصیل آئی ٹی یو-ٹی کی طرف سے درج ذیل دی گئی ہے: "ورچوئل شیڈولنگ الگورتھم ایک نظریاتی آمد کے وقت (ٹی اے ٹی) کو اپ ڈیٹ کرتا ہے، جو سیل کا 'برائے نام' آمد کا وقت ہے، یہ فرض کرتے ہوئے کہ خلیات کو T کے اخراج کے وقفے پر یکساں فاصلے پر بھیجا جاتا ہے جو سیل کی شرح λ [= 1/T] کے مطابق ہوتا ہے جب ماخذ فعال ہوتا ہے۔ اگر سیل کی اصل آمد کا وقت سیل کی شرح سے وابستہ ٹی اے ٹی اور رواداری τ کے مقابلے میں 'بہت جلد' نہیں ہے، یعنی۔ اگر اصل آمد کا وقت اس کے نظریاتی آمد کے وقت مائنس لمٹ ویلیو (ta> TAT-τ) کے بعد ہے، تو خلیہ مطابقت پذیر ہے ؛ بصورت دیگر، خلیہ غیر مطابقت پذیر ہے۔ اگر خلیہ غیر مطابقت پذیر ہے تو ٹی اے ٹی کو تبدیل نہیں کیا جاتا ہے۔ اگر خلیہ مطابقت رکھتا ہے، اور اپنے ٹی اے ٹی سے پہلے پہنچ جاتا ہے (بالٹی کے خالی نہ ہونے کے برابر لیکن حد کی قیمت سے کم ہونے کے برابر)، تو اگلے خلیے کا ٹی اے ٹی محض ٹی اے ٹی + ٹی ہوتا ہے۔ تاہم، اگر کوئی خلیہ اس کے ٹی اے ٹی کے بعد آتا ہے، تو اگلے خلیے کے لیے ٹی اے ٹی کا حساب اس خلیے کی آمد کے وقت سے لگایا جاتا ہے، نہ کہ اس کے ٹی اے ٹی سے۔ یہ ٹرانسمیشن میں فرق ہونے پر کریڈٹ کی تعمیر کو روکتا ہے (بالٹی کے خالی ہونے سے کم ہونے کے برابر)۔ الگورتھم کا یہ ورژن کام کرتا ہے کیونکہ τ اس بات کی وضاحت کرتا ہے کہ اگر کوئی جٹر نہ ہوتا تو خلیہ اس سے کتنی جلدی پہنچ سکتا ہے: لیک بالٹی دیکھیں: تاخیر کی تغیر رواداری۔ اسے دیکھنے کا ایک اور طریقہ یہ ہے کہ ٹی اے ٹی اس بات کی نمائندگی کرتا ہے کہ بالٹی اگلی بار کب خالی ہوگی، لہذا اس سے پہلے ایک وقت τ ہوتا ہے جب بالٹی بالکل حد کی قیمت پر بھری جاتی ہے۔ لہذا، دونوں نقطہ نظر میں، اگر یہ ٹی اے ٹی سے پہلے τ سے زیادہ پہنچتا ہے، تو اس کے مطابق ہونا بہت جلد ہوگا۔ ٹوکن بالٹی کے ساتھ موازنہ جی سی آر اے، ٹوکن بالٹی الگورتھم کے نفاذ کے برعکس، بالٹی کو اپ ڈیٹ کرنے کے عمل کی تقلید نہیں کرتا ہے (رساو یا باقاعدگی سے ٹوکن شامل کرنا)۔ بلکہ، ہر بار جب کوئی سیل آتا ہے تو یہ اس رقم کا حساب لگاتا ہے جس سے بالٹی لیک ہوگی کیونکہ اس کی سطح کا آخری بار حساب لگایا گیا تھا یا بالٹی اگلی بار کب خالی ہوگی (= ٹی اے ٹی)۔ یہ بنیادی طور پر رساو کے عمل کو ایک (ریئل ٹائم) گھڑی سے تبدیل کر رہا ہے، جو زیادہ تر ہارڈ ویئر کے نفاذ میں پہلے سے ہی ہونے کا امکان ہے۔ آر ٹی سی کے ساتھ عمل کی یہ تبدیلی ممکن ہے کیونکہ اے ٹی ایم خلیوں کی ایک مقررہ لمبائی (53 بائٹس) ہوتی ہے، اس طرح ٹی ہمیشہ ایک مستقل ہوتا ہے، اور نئی بالٹی کی سطح (یا ٹی اے ٹی) کے حساب میں کوئی ضرب یا تقسیم شامل نہیں ہوتا ہے۔ نتیجے کے طور پر، حساب سافٹ ویئر میں تیزی سے کیا جا سکتا ہے، اور جب کوئی سیل آتا ہے تو ٹوکن بالٹی کے مقابلے میں زیادہ اقدامات کیے جاتے ہیں، کام انجام دینے والے پروسیسر پر بوجھ کے لحاظ سے، علیحدہ اپ ڈیٹ کے عمل کی کمی اس کی تلافی سے زیادہ ہے۔ مزید برآں، کیونکہ بالٹی اپ ڈیٹ کا کوئی تخروپن نہیں ہے، جب کنکشن خاموش ہوتا ہے تو کوئی پروسیسر لوڈ بالکل نہیں ہوتا ہے۔ تاہم، اگر جی سی آر اے کو متغیر لمبائی والے پیکٹوں (لنک لیئر پی ڈی یوز) والے پروٹوکول میں پیکٹ/فریم ریٹ کے بجائے بینڈوڈتھ تک محدود رکھنے کے لیے استعمال کیا جائے، تو اس میں ضرب شامل ہوگی: بنیادی طور پر بالٹی میں شامل کی گئی قیمت (یا ٹی اے ٹی) ہر مطابقت پذیر پیکٹ کے لیے پیکٹ کی لمبائی کے متناسب ہونی چاہیے: جبکہ، جیسا کہ بیان کیا گیا ہے، جی سی آر اے کے ساتھ، بالٹی میں موجود پانی میں وقت کی اکائیاں ہوتی ہیں، متغیر لمبائی والے پیکٹوں کے لیے اس میں ایسی اکائیاں ہونی چاہئیں جو پیکٹ کی لمبائی اور وقت کی پیداوار ہوں۔ لہذا، تیز رفتار، ہارڈ ویئر ضرب (جیسا کہ ایف پی جی اے میں) تک رسائی کے بغیر متغیر لمبائی کے پیکٹوں کی بینڈوتھ کو محدود کرنے کے لیے جی سی آر اے کا اطلاق عملی نہیں ہو سکتا۔ تاہم، یہ ہمیشہ پیکٹ یا سیل کی شرح کو محدود کرنے کے لیے استعمال کیا جا سکتا ہے، جب تک کہ ان کی لمبائی کو نظر انداز کیا جائے۔ ڈوئل لیک بالٹی کنٹرولر جی سی آر اے کے متعدد نفاذات کو بیک وقت وی سی یا وی پی پر، ڈوئل لیک بالٹی ٹریفک پولیسنگ یا ٹریفک کی تشکیل کے فنکشن میں، مثال کے طور پر لاگو کیا جا سکتا ہے۔ متغیر بٹ ریٹ (وی بی آر) وی سی پر لاگو ہوتا ہے۔ یہ اس وی بی آر وی سی پر اے ٹی ایم خلیوں کو سسٹینڈ سیل ریٹ (ایس سی آر) اور زیادہ سے زیادہ برسٹ سائز (ایم بی ایس) تک محدود کر سکتا ہے۔ ایک ہی وقت میں، دوہری لیک بالٹی ٹریفک پولیسنگ فنکشن پھٹنے میں خلیوں کی شرح کو پیک سیل ریٹ (پی سی آر) اور زیادہ سے زیادہ سیل تاخیر تغیر رواداری (سی ڈی وی ٹی) تک محدود کر سکتی ہے: ٹریفک Contract#Traffic پیرامیٹرز دیکھیں۔ یہ بہتر طور پر سمجھا جا سکتا ہے کہ وی بی آر وی سی پر ٹرانسمیشن مقررہ لمبائی کے پیغامات (سی پی سی ایس-پی ڈی یو) کی شکل میں ہے، جو کچھ مقررہ وقفے یا انٹر میسج ٹائم (آئی ایم ٹی) کے ساتھ منتقل ہوتے ہیں اور انہیں لے جانے کے لیے کئی سیل، ایم بی ایس لیتے ہیں ؛ تاہم، وی بی آر ٹریفک کی تفصیل اور دوہری لیک بالٹی کا استعمال ایسے حالات تک محدود نہیں ہے۔ اس صورت میں، آئی ایم ٹی کے وقفے پر سیل کی اوسط شرح ایس سی آر (= ایم بی ایس/آئی ایم ٹی) ہے۔ انفرادی پیغامات پی سی آر پر منتقل کیے جا سکتے ہیں، جو فزیکل لنک (1/δ) اور ایس سی آر کے لیے بینڈوتھ کے درمیان کوئی بھی قدر ہو سکتی ہے۔ یہ پیغام کو پیغام کے وقفے آئی ایم ٹی سے کم مدت میں منتقل کرنے کی اجازت دیتا ہے، جس میں پیغام کی مثالوں کے درمیان فرق ہوتا ہے۔ دوہری رسنے والی بالٹی میں، 1/ایس سی آر کے اخراج کے وقفے اور ایک حد قیمت τSCR کے ساتھ ٹریفک پر ایک بالٹی لگائی جاتی ہے جو ایک ایم بی ایس دیتی ہے جو پیغام میں موجود خلیوں کی تعداد ہے: لیک bucket#Maximum برسٹ سائز دیکھیں۔ دوسری بالٹی میں 1/پی سی آر کا اخراج کا وقفہ ہوتا ہے اور ایک حد قدر ٹی ٹی پی سی آر ہوتی ہے جو سی ڈی وی کو کنکشن کے راستے میں اس مقام تک جانے کی اجازت دیتی ہے: لیک bucket#Delay تغیر رواداری دیکھیں۔ اس کے بعد خلیوں کو پی سی آر میں، ٹی ٹی پی سی آر کے جھٹکنے کے ساتھ، زیادہ سے زیادہ ایم بی ایس خلیوں تک جانے دیا جاتا ہے۔ ایم بی ایس خلیوں کے اگلے پھٹنے کی اجازت پہلے کے بعد ایم بی ایس ایکس 1/ایس سی آر کو شروع کرنے کے ذریعے دی جائے گی۔ اگر خلیات 1/پی سی آر سے زیادہ کی شرح سے پھٹتے ہیں (ایم بی ایس خلیات (ایم بی ایس-1)/پی سی آر-ٹی پی سی آر) سے کم میں پہنچتے ہیں، یا ایم بی ایس خلیات سے زیادہ پی سی آر پر پہنچتے ہیں، یا ایم بی ایس خلیات کے پھٹنا آئی ایم ٹی کے علاوہ قریب پہنچتے ہیں، تو دوہری رسنے والی بالٹی اس کا پتہ لگائے گی اور کنکشن کو مطابقت دلانے کے لیے کافی خلیات کو تاخیر (تشکیل) یا ڈراپ یا ڈی ترجیحی (پولیسنگ) کرے گی۔ شکل 3 سیل لاس ترجیحی (سی ایل پی) اقدار 1 (کم) اور 0 (زیادہ) سیل کے بہاؤ، یعنی دونوں کے لیے ایس سی آر اور پی سی آر کنٹرول کے لیے حوالہ الگورتھم دکھاتا ہے۔ جہاں دونوں ترجیحی اقدار والے خلیوں کے ساتھ یکساں سلوک کیا جاتا ہے۔ اسی طرح کے حوالہ الگورتھم جہاں اعلی اور کم ترجیحی خلیوں کے ساتھ مختلف سلوک کیا جاتا ہے وہ ضمیمہ A سے I.371 میں بھی دیے گئے ہیں۔ اسنکرونس ٹرانسفر موڈ لیک بالٹی یو پی سی اور این پی سی این این آئی ٹریفک کنٹریکٹ کنکشن ایڈمیشن کنٹرول ٹریفک کی تشکیل ٹریفک پولیسنگ (مواصلات) ٹوکن بالٹی حوالہ جات نیٹ ورکنگ الگورتھم ٹیلی ٹریفک نیٹ ورک شیڈولنگ الگورتھم اسنکرونس ٹرانسفر موڈ بھی دیکھیں۔