Backpressure routing
قطار کے نظریہ میں، امکان کے ریاضیاتی نظریہ کے اندر ایک نظم، بیک پریشر روٹنگ الگورتھم قطار کے نیٹ ورک کے ارد گرد ٹریفک کو ہدایت دینے کا ایک طریقہ ہے جو زیادہ سے زیادہ نیٹ ورک تھرو پٹ حاصل کرتا ہے، جو لیاپونوف ڈرفٹ کے تصورات کا استعمال کرتے ہوئے قائم کیا جاتا ہے۔ بیک پریشر روٹنگ اس صورت حال پر غور کرتی ہے جہاں ہر کام نیٹ ورک میں متعدد سروس نوڈس کا دورہ کر سکتا ہے۔ یہ زیادہ سے زیادہ وزن کے شیڈولنگ کی توسیع ہے جہاں ہر کام صرف ایک سروس نوڈ پر جاتا ہے۔ تعارف بیک پریشر روٹنگ ایک الگورتھم ہے جو بھیڑ کے میلان کا استعمال کرتے ہوئے ملٹی ہاپ نیٹ ورک پر ٹریفک کو متحرک طور پر روٹ کرنے کے لیے ہے۔ الگورتھم کا اطلاق وائرلیس مواصلاتی نیٹ ورکس پر کیا جا سکتا ہے، بشمول سینسر نیٹ ورک، موبائل ایڈہاک نیٹ ورک (MANETS)، اور وائرلیس اور وائر لائن اجزاء کے ساتھ متنوع نیٹ ورک۔ بیک پریشر کے اصولوں کا اطلاق دیگر شعبوں پر بھی کیا جا سکتا ہے، جیسے کہ پروڈکٹ اسمبلی سسٹم اور پروسیسنگ نیٹ ورک کا مطالعہ۔ یہ مضمون مواصلاتی نیٹ ورکس پر مرکوز ہے، جہاں متعدد ڈیٹا اسٹریمز سے پیکٹ پہنچتے ہیں اور انہیں مناسب مقامات تک پہنچایا جانا چاہیے۔ بیک پریشر الگورتھم مقررہ وقت میں کام کرتا ہے۔ ہر بار سلاٹ یہ ڈیٹا کو ان سمتوں میں روٹ کرنے کی کوشش کرتا ہے جو پڑوسی نوڈس کے درمیان تفریق بیک لاگ کو زیادہ سے زیادہ کرتے ہیں۔ یہ اسی طرح ہے کہ پانی دباؤ کے میلان کے ذریعے پائپوں کے نیٹ ورک سے کیسے بہتا ہے۔ تاہم، بیک پریشر الگورتھم کا اطلاق ملٹی کموڈٹی نیٹ ورکس (جہاں مختلف پیکٹوں کی مختلف منزلیں ہو سکتی ہیں)، اور نیٹ ورکس پر کیا جا سکتا ہے جہاں ٹرانسمیشن کی شرحوں کو (ممکنہ طور پر وقت کے لحاظ سے مختلف) آپشنز کے سیٹ سے منتخب کیا جا سکتا ہے۔ بیک پریشر الگورتھم کی پرکشش خصوصیات یہ ہیں: (i) یہ زیادہ سے زیادہ نیٹ ورک تھرو پٹ کی طرف لے جاتا ہے، (ii) یہ وقت کے لحاظ سے مختلف نیٹ ورک کے حالات کے لیے ثابت طور پر مضبوط ہے، (iii) اسے ٹریفک کی آمد کی شرح یا چینل اسٹیٹ کے امکانات کو جانے بغیر نافذ کیا جا سکتا ہے۔ تاہم، الگورتھم بڑی تاخیر متعارف کرا سکتا ہے، اور مداخلت کے ساتھ نیٹ ورکس میں بالکل نافذ کرنا مشکل ہو سکتا ہے۔ بیک پریشر کی تبدیلیاں جو تاخیر کو کم کرتی ہیں اور عمل درآمد کو آسان بناتی ہیں، ذیل میں بہتر تاخیر اور تقسیم شدہ بیک پریشر کے تحت بیان کی گئی ہیں۔ بیک پریشر روٹنگ کا بنیادی طور پر نظریاتی تناظر میں مطالعہ کیا گیا ہے۔ عملی طور پر، ایڈہاک وائرلیس نیٹ ورکس نے عام طور پر مختصر ترین راستے کے حسابات یا نیٹ ورک فلڈنگ پر مبنی متبادل روٹنگ کے طریقوں کو نافذ کیا ہے، جیسے ایڈہاک آن ڈیمانڈ ڈسٹنس ویکٹر روٹنگ (اے او ڈی وی)، جغرافیائی روٹنگ، اور انتہائی موقع پرست روٹنگ (ایکس او آر)۔ تاہم، بیک پریشر کی ریاضیاتی بہترین خصوصیات نے جنوبی کیلیفورنیا یونیورسٹی اور نارتھ کیرولائنا اسٹیٹ یونیورسٹی میں وائرلیس ٹیسٹ بیڈز پر اس کے استعمال کے حالیہ تجرباتی مظاہروں کو متحرک کیا ہے۔ اصل بیک پریشر الگورتھم ٹاسیولاس اور ایفریمائڈز نے تیار کیا تھا۔ انہوں نے بے ترتیب پیکٹ کی آمد اور لنک کے انتخاب کے اختیارات کے ایک مقررہ سیٹ کے ساتھ ایک ملٹی ہاپ پیکٹ ریڈیو نیٹ ورک پر غور کیا۔ ان کا الگورتھم زیادہ سے زیادہ وزن والے لنک کے انتخاب کے مرحلے اور ایک تفریقی بیک لاگ روٹنگ مرحلے پر مشتمل تھا۔ بیک پریشر سے متعلق ایک الگورتھم، جو ملٹی کموڈٹی نیٹ ورک کے بہاؤ کی کمپیوٹنگ کے لیے ڈیزائن کیا گیا تھا، اویربچ اور لیٹن میں تیار کیا گیا تھا۔ بیک پریشر الگورتھم کو بعد میں نیلی، مودیانو اور روہرس نے موبائل نیٹ ورک کے شیڈولنگ کا علاج کرنے کے لیے بڑھایا۔ بیک پریشر کا ریاضیاتی طور پر لیاپونوف ڈرفٹ کے نظریہ کے ذریعے تجزیہ کیا جاتا ہے، اور نیٹ ورک کی افادیت کو زیادہ سے زیادہ فراہم کرنے کے لیے فلو کنٹرول میکانزم کے ساتھ مشترکہ طور پر استعمال کیا جا سکتا ہے۔ (یوٹیلیٹی آپٹیمائزیشن اور پینلٹی کم سے کم کرنے کے ساتھ بیک پریشر بھی دیکھیں)۔ یہ کس طرح کام کرتا ہے بیک پریشر روٹنگ کو ایسے فیصلے کرنے کے لیے ڈیزائن کیا گیا ہے جو (تقریبا) نیٹ ورک میں قطار کے بیک لاگ کے مربعوں کے مجموعے کو ایک ٹائم سلاٹ سے دوسرے تک کم سے کم کریں۔ اس تکنیک کی عین مطابق ریاضیاتی ترقی کو بعد کے حصوں میں بیان کیا گیا ہے۔ یہ سیکشن اس ماڈل کے حوالے سے عمومی نیٹ ورک ماڈل اور بیک پریشر روٹنگ کے عمل کو بیان کرتا ہے۔ ملٹی ہاپ قطار نیٹ ورک ماڈل N نوڈس کے ساتھ ملٹی ہاپ نیٹ ورک پر غور کریں (شکل دیکھیں۔ 1 ایک مثال کے لیے N = 6 کے ساتھ)۔ نیٹ ورک مقررہ وقت میں کام کرتا ہے۔ ہر سلاٹ پر، نیا ڈیٹا نیٹ ورک تک پہنچ سکتا ہے، اور تمام ڈیٹا کو اس کی مناسب منزل تک پہنچانے کی کوشش میں روٹنگ اور ٹرانسمیشن شیڈولنگ کے فیصلے کیے جاتے ہیں۔ نوڈ کے لیے مقرر کردہ ڈیٹا کو کموڈٹی سی ڈیٹا کے طور پر لیبل کیا جائے۔ ہر نوڈ میں ڈیٹا اس کی اجناس کے مطابق محفوظ کیا جاتا ہے۔ اور کے لیے، نوڈ n میں کموڈٹی c ڈیٹا کی موجودہ رقم ہونے دیں، جسے کیو بیک لاگ بھی کہا جاتا ہے۔ نوڈ کے اندر قطار کے بیک لاگ کا ایک قریبی اپ شکل میں دکھایا گیا ہے۔ 2. کی اکائیاں مسئلہ کے سیاق و سباق پر منحصر ہوتی ہیں۔ مثال کے طور پر، بیک لاگ پیکٹوں کی انٹیجر یونٹس لے سکتا ہے، جو ان صورتوں میں مفید ہے جب ڈیٹا کو مقررہ لمبائی کے پیکٹوں میں تقسیم کیا جاتا ہے۔ متبادل طور پر، یہ بٹس کی حقیقی قدر والی اکائیاں لے سکتا ہے۔ یہ فرض کیا جاتا ہے کہ تمام اور تمام ٹائم سلاٹس کے لیے، کیونکہ کوئی نوڈ اپنے لیے مقرر کردہ ڈیٹا کو محفوظ نہیں کرتا ہے۔ ہر ٹائم سلاٹ پر، نوڈس دوسروں کو ڈیٹا منتقل کر سکتے ہیں۔ ڈیٹا جو ایک نوڈ سے دوسرے نوڈ میں منتقل ہوتا ہے اسے پہلے نوڈ کی قطار سے ہٹا دیا جاتا ہے اور دوسرے کی قطار میں شامل کیا جاتا ہے۔ جو ڈیٹا اپنی منزل پر منتقل کیا جاتا ہے اسے نیٹ ورک سے ہٹا دیا جاتا ہے۔ ڈیٹا نیٹ ورک پر خارجی طور پر بھی پہنچ سکتا ہے، اور اس کی تعریف نئے ڈیٹا کی مقدار کے طور پر کی جاتی ہے جو سلاٹ t پر نوڈ n پر پہنچتا ہے جسے بالآخر نوڈ c تک پہنچانا ہوتا ہے۔ آئیے نیٹ ورک کے ذریعے سلاٹ t پر لنک (a، b) پر استعمال ہونے والی ترسیل کی شرح، ڈیٹا کی مقدار کی نمائندگی کرتی ہے جو موجودہ سلاٹ پر نوڈ a سے نوڈ b میں منتقل ہو سکتی ہے۔ ٹرانسمیشن ریٹ میٹرکس ہونے دیں۔ ان ترسیل کی شرحوں کو ممکنہ طور پر وقت کے لحاظ سے مختلف اختیارات کے ایک سیٹ کے اندر منتخب کیا جانا چاہیے۔ خاص طور پر، نیٹ ورک میں وقت کے لحاظ سے مختلف چینلز اور نوڈ کی نقل و حرکت ہو سکتی ہے، اور یہ ہر سلاٹ میں اس کی ترسیل کی صلاحیتوں کو متاثر کر سکتا ہے۔ اس ماڈل کے لیے، ایس (ٹی) نیٹ ورک کی ٹوپولوجی حالت کی نمائندگی کرتا ہے، جو سلاٹ ٹی پر نیٹ ورک کی خصوصیات کو پکڑتا ہے جو ٹرانسمیشن کو متاثر کرتا ہے۔ آئیے ٹوپولوجی اسٹیٹ S (t) کے تحت دستیاب ٹرانسمیشن ریٹ میٹرکس آپشنز کے سیٹ کی نمائندگی کریں۔ ہر سلاٹ ٹی، نیٹ ورک کنٹرولر ایس (ٹی) کا مشاہدہ کرتا ہے اور سیٹ کے اندر ٹرانسمیشن کی شرحوں کا انتخاب کرتا ہے۔ ہر سلاٹ ٹی پر کس میٹرکس کا انتخاب کرنا ہے اس کا انتخاب اگلے ذیلی حصے میں بیان کیا گیا ہے۔ یہ وقت کے لحاظ سے مختلف نیٹ ورک ماڈل سب سے پہلے اس معاملے کے لیے تیار کیا گیا تھا جب ٹرانسمیشن کی شرحوں کا تعین چینل اسٹیٹ میٹرکس اور پاور الاٹمنٹ میٹرکس کے عمومی افعال کے ذریعے کیا جاتا تھا۔ ماڈل کا استعمال اس وقت بھی کیا جا سکتا ہے جب شرحوں کا تعین دیگر کنٹرول فیصلوں، جیسے سرور الاٹمنٹ، ذیلی بینڈ کا انتخاب، کوڈنگ کی قسم وغیرہ کے ذریعے کیا جاتا ہے۔ یہ فرض کرتا ہے کہ قابل حمایت ترسیل کی شرحیں معلوم ہیں اور ترسیل کی کوئی غلطیاں نہیں ہیں۔ بیک پریشر روٹنگ کی توسیعی فارمولیشنز کو ممکنہ چینل کی غلطیوں والے نیٹ ورکس کے لیے استعمال کیا جا سکتا ہے، بشمول وہ نیٹ ورک جو ملٹی ریسیور ڈائیورسٹی کے ذریعے وائرلیس براڈکاسٹ فائدے کا استحصال کرتے ہیں۔ بیک پریشر کنٹرول کے فیصلے ہر سلاٹ ٹی بیک پریشر کنٹرولر ایس (ٹی) کا مشاہدہ کرتا ہے اور مندرجہ ذیل 3 مراحل انجام دیتا ہے: سب سے پہلے، ہر لنک (اے، بی) کے لیے، یہ استعمال کرنے کے لیے ایک بہترین شے کا انتخاب کرتا ہے۔ اگلا، یہ طے کرتا ہے کہ کون سا میٹرکس استعمال کرنا ہے۔ آخر میں، یہ اس چیز کی مقدار کا تعین کرتا ہے جو یہ لنک (a، b) پر منتقل کرے گا (زیادہ سے زیادہ ہونا، لیکن ممکنہ طور پر کچھ معاملات میں کم ہونا)۔ بہترین شے کا انتخاب ہر نوڈ اپنے موجودہ پڑوسیوں میں اپنے قطار کے بیک لاگ اور بیک لاگ کا مشاہدہ کرتا ہے۔ نوڈ a کا موجودہ پڑوسی نوڈ b ایسا ہے کہ موجودہ سلاٹ پر غیر صفر ترسیل کی شرح کا انتخاب کرنا ممکن ہے۔ اس طرح پڑوسیوں کا تعین سیٹ کے ذریعے کیا جاتا ہے۔ انتہائی صورت میں، ایک نوڈ میں تمام N−1 دوسرے نوڈس پڑوسیوں کے طور پر ہو سکتے ہیں۔ تاہم، ایسے سیٹوں کا استعمال کرنا عام ہے جو نوڈس کے درمیان ترسیل کو روکتے ہیں جو ایک مخصوص جغرافیائی فاصلے سے زیادہ سے الگ ہوتے ہیں، یا جن میں ایک مخصوص حد سے نیچے سگنل کی طاقت ہوتی ہے۔ اس طرح، پڑوسیوں کی تعداد N−1 سے بہت کم ہونا عام ہے۔ شکل میں مثال۔ 1 پڑوسیوں کو لنک کنکشن کے ذریعے بیان کرتا ہے، تاکہ نوڈ 5 کے پڑوسی 4 اور 6 ہوں۔ مثال پڑوسیوں کے درمیان ہم آہنگی کے تعلقات کی تجویز کرتی ہے (تاکہ اگر 5 4 کا پڑوسی ہے، تو 4 5 کا پڑوسی ہے)، لیکن عام طور پر ایسا ہونا ضروری نہیں ہے۔ دیئے گئے نوڈ کے پڑوسیوں کا سیٹ باہر جانے والے لنکس کے سیٹ کا تعین کرتا ہے جو موجودہ سلاٹ پر ٹرانسمیشن کے لیے استعمال ہو سکتا ہے۔ ہر باہر جانے والے لنک (اے، بی) کے لیے، بہترین شے کی تعریف اس شے کے طور پر کی گئی ہے جو درج ذیل تفریق بیک لاگ مقدار کو زیادہ سے زیادہ کرتی ہے: بہترین شے کے انتخاب میں کوئی بھی تعلق من مانی طور پر ٹوٹ جاتا ہے۔ ایک مثال شکل میں دکھائی گئی ہے۔ 2. مثال یہ ہے کہ ہر قطار میں فی الحال صرف 3 اشیاء ہیں: سرخ، سبز اور نیلے، اور ان کی پیمائش پیکٹوں کی عدد اکائیوں میں کی جاتی ہے۔ ہدایت شدہ لنک (1,2) پر توجہ مرکوز کرتے ہوئے، تفریق بیک لاگ یہ ہیں: لہذا، سلاٹ ٹی پر لنک (1,2) پر بھیجنے کے لیے بہترین شے گرین کموڈٹی ہے۔ دوسری طرف، سلاٹ ٹی پر ریورس لنک (2,1) پر بھیجنے کے لیے بہترین شے نیلی شے ہے۔ μab (t) میٹرکس کا انتخاب ایک بار جب ہر لنک (a، b) کے لیے زیادہ سے زیادہ اشیاء کا تعین ہو جاتا ہے، تو نیٹ ورک کنٹرولر درج ذیل وزن کا حساب لگاتا ہے: وزن لنک (a، b) کے لیے زیادہ سے زیادہ اشیاء سے وابستہ تفریقی بیک لاگ کی قیمت ہے، جسے 0 کے ساتھ زیادہ سے زیادہ کیا جاتا ہے۔ اس کے بعد کنٹرولر ٹرانسمیشن کی شرحوں کو مندرجہ ذیل زیادہ سے زیادہ وزن کے مسئلے کے حل کے طور پر منتخب کرتا ہے (من مانی طور پر تعلقات کو توڑنا): زیادہ سے زیادہ وزن کے فیصلے کی ایک مثال کے طور پر، فرض کریں کہ موجودہ سلاٹ ٹی پر، 6 نوڈ نیٹ ورک کے ہر لنک پر تفریق بیکلاگ لنک ویٹ کی طرف لے جاتے ہیں: اگرچہ سیٹ میں ممکنہ ٹرانسمیشن ریٹ میٹرکس کی بے شمار لامحدود تعداد ہو سکتی ہے، لیکن سادگی کے لیے فرض کریں کہ موجودہ ٹوپولوجی حالت صرف 4 ممکنہ انتخاب کو تسلیم کرتی ہے: موجودہ ٹوپولوجی حالت ایس (ٹی) کے تحت 4 ممکنہ ٹرانسمیشن کی شرح کے انتخاب کی مثال۔ آپشن (اے) کی ترسیل کی شرح کے ساتھ واحد لنک (1,5) کو چالو کرتا ہے۔ دیگر تمام آپشنز دو لنکس کا استعمال کرتے ہیں، جن میں سے ہر ایک فعال لنک پر 1 کی ترسیل کی شرح ہوتی ہے۔ ان چار امکانات کو میٹرکس کی شکل میں اس طرح پیش کیا جاتا ہے: مشاہدہ کریں کہ نوڈ 6 ان میں سے کسی بھی امکان کے تحت نہ تو بھیج سکتا ہے اور نہ ہی وصول کر سکتا ہے۔ یہ اس لیے پیدا ہو سکتا ہے کیونکہ نوڈ 6 فی الحال مواصلاتی حد سے باہر ہے۔ 4 امکانات میں سے ہر ایک کے لیے شرحوں کا وزنی مجموعہ یہ ہے: انتخاب (a): انتخاب (ب): انتخاب (ج): انتخاب (د): چونکہ زیادہ سے زیادہ وزن 12 کے لیے ٹائی ہے، اس لیے نیٹ ورک کنٹرولر کسی بھی آپشن یا آپشن کو منتخب کر کے من مانی طور پر ٹائی توڑ سکتا ہے۔ روٹنگ متغیرات کو حتمی شکل دینا فرض کریں کہ اب ہر لنک کے لیے بہترین اشیاء کا تعین کر لیا گیا ہے، اور ترسیل کی شرحوں کا بھی تعین کر لیا گیا ہے۔ اگر کسی دیئے گئے لنک (a، b) پر زیادہ سے زیادہ اشیاء کے لیے تفریق بیک لاگ منفی ہے، تو موجودہ سلاٹ پر اس لنک پر کوئی ڈیٹا منتقل نہیں کیا جاتا ہے۔ بصورت دیگر، نیٹ ورک اس لنک پر اجناس کے ڈیٹا کی اکائیاں بھیجنے کی پیشکش کرتا ہے۔ یہ ہر لنک (a، b) اور ہر کموڈٹی c کے لیے روٹنگ متغیرات کی وضاحت کر کے کیا جاتا ہے، جہاں: کی قیمت سلاٹ t پر لنک (a، b) پر کموڈٹی c ڈیٹا کو پیش کردہ ترسیل کی شرح کی نمائندگی کرتی ہے۔ تاہم، نوڈس میں ان کے تمام باہر جانے والے لنکس پر پیش کردہ نرخوں پر ترسیل کی حمایت کرنے کے لیے کافی مخصوص شے نہیں ہو سکتی ہے۔ یہ نوڈ این اور کموڈٹی سی کے لیے سلاٹ ٹی پر پیدا ہوتا ہے اگر: اس صورت میں، تمام ڈیٹا بھیجا جاتا ہے، اور نیل ڈیٹا کو پیش کردہ نرخوں کے غیر استعمال شدہ حصوں کو پر کرنے کے لیے استعمال کیا جاتا ہے، اصل ڈیٹا اور نیل ڈیٹا کو من مانی طور پر متعلقہ باہر جانے والے لنکس پر مختص کیا جاتا ہے (پیش کردہ نرخوں کے مطابق)۔ اسے قطار کے نیچے بہاؤ کی صورتحال کہا جاتا ہے۔ اس طرح کے زیر بہاؤ نیٹ ورک کی تھرو پٹ یا استحکام کی خصوصیات کو متاثر نہیں کرتے ہیں۔ بدیہی طور پر، اس کی وجہ یہ ہے کہ انڈر فلو صرف اس وقت پیدا ہوتا ہے جب ٹرانسمیٹنگ نوڈ میں بیک لاگ کی مقدار کم ہوتی ہے، جس کا مطلب ہے کہ نوڈ کو عدم استحکام کا خطرہ نہیں ہے۔ تاخیر کو بہتر بنانا بیک پریشر الگورتھم کسی بھی پہلے سے طے شدہ راستے کا استعمال نہیں کرتا ہے۔ راستے متحرک طریقے سے سیکھے جاتے ہیں، اور مختلف پیکٹوں کے لیے مختلف ہو سکتے ہیں۔ تاخیر بہت بڑی ہو سکتی ہے، خاص طور پر جب سسٹم کو ہلکے سے لوڈ کیا جاتا ہے تاکہ ڈیٹا کو منزل کی طرف دھکیلنے کے لیے کافی دباؤ نہ ہو۔ مثال کے طور پر، فرض کریں کہ ایک پیکٹ نیٹ ورک میں داخل ہوتا ہے، اور کچھ اور کبھی داخل نہیں ہوتا ہے۔ یہ پیکٹ نیٹ ورک کے ذریعے ایک پاگل چہل قدمی کر سکتا ہے اور کبھی بھی اپنی منزل پر نہیں پہنچ سکتا کیونکہ کوئی دباؤ میلان نہیں بنتا ہے۔ یہ بیک پریشر کی تھرو پٹ اصلاح یا استحکام کی خصوصیات سے متصادم نہیں ہے کیونکہ نیٹ ورک میں کسی بھی وقت زیادہ سے زیادہ ایک پیکٹ ہوتا ہے اور اس لیے معمولی طور پر مستحکم ہوتا ہے (0 کی ترسیل کی شرح حاصل کرنا، آمد کی شرح کے برابر)۔ پہلے سے طے شدہ راستوں کے ایک سیٹ پر بیک پریشر کو نافذ کرنا بھی ممکن ہے۔ یہ صلاحیت کے علاقے کو محدود کر سکتا ہے، لیکن ان آرڈر ڈیلیوری اور تاخیر کو بہتر بنا سکتا ہے۔ صلاحیت کے علاقے کو متاثر کیے بغیر تاخیر کو بہتر بنانے کا ایک اور طریقہ یہ ہے کہ وزن کو مطلوبہ سمتوں کی طرف جوڑنے کے لیے ایک بہتر ورژن کا استعمال کیا جائے۔ اس طرح کے تعصب کے تخروپن نے تاخیر میں نمایاں بہتری دکھائی ہے۔ نوٹ کریں کہ بیک پریشر کے لیے قطاروں میں فرسٹ ان فرسٹ آؤٹ (ایف آئی ایف او) سروس کی ضرورت نہیں ہے۔ یہ مشاہدہ کیا گیا ہے کہ لاسٹ ان فرسٹ آؤٹ (ایل آئی ایف او) سروس تھرو پٹ کو متاثر کیے بغیر پیکٹوں کی اکثریت کے لیے تاخیر کو ڈرامائی طور پر بہتر بنا سکتی ہے۔ تقسیم شدہ بیک پریشر نوٹ کریں کہ ایک بار ٹرانسمیشن کی شرحوں کا انتخاب ہو جانے کے بعد، روٹنگ کے فیصلے کے متغیرات کو سادہ تقسیم شدہ انداز میں شمار کیا جا سکتا ہے، جہاں ہر نوڈ کو صرف اپنے اور اپنے پڑوسیوں کے درمیان قطار کے بیک لاگ کے فرق کے علم کی ضرورت ہوتی ہے۔ تاہم، ترسیل کی شرحوں کے انتخاب کے لیے EQs میں زیادہ سے زیادہ وزن کے مسئلے کے حل کی ضرورت ہوتی ہے۔ (1)-(2)۔ خاص صورت میں جب چینل آرتھوگنل ہوتے ہیں، الگورتھم کا قدرتی تقسیم شدہ نفاذ ہوتا ہے اور ہر نوڈ پر الگ الگ فیصلوں تک کم ہوجاتا ہے۔ تاہم، بین چینل مداخلت والے نیٹ ورکس کے لیے زیادہ سے زیادہ وزن کا مسئلہ ایک مرکزی کنٹرول کا مسئلہ ہے۔ مرکزی طریقے سے بھی اسے حل کرنا بہت مشکل ہو سکتا ہے۔ لنک کی شرحوں کے ساتھ مداخلت نیٹ ورکس کے لیے ایک تقسیم شدہ نقطہ نظر جو سگنل سے شور سے زیادہ مداخلت کے تناسب (ایس آئی این آر) کے ذریعے طے کیا جاتا ہے، بے ترتیب کاری کا استعمال کرتے ہوئے انجام دیا جا سکتا ہے۔ ہر نوڈ تصادفی طور پر ہر سلاٹ ٹی کو منتقل کرنے کا فیصلہ کرتا ہے (اگر اس کے پاس فی الحال بھیجنے کے لیے پیکٹ نہیں ہے تو "نیل" پیکٹ منتقل کرنا)۔ اصل ترسیل کی شرح، اور بھیجنے کے لیے متعلقہ اصل پیکٹ کا تعین 2 مراحل والے ہینڈ شیک کے ذریعے کیا جاتا ہے: پہلے مرحلے پر، بے ترتیب طور پر منتخب کردہ ٹرانسمیٹر نوڈس ایک پائلٹ سگنل بھیجتے ہیں جس میں سگنل کی طاقت حقیقی ترسیل کے متناسب ہوتی ہے۔ دوسرے مرحلے پر، تمام ممکنہ رسیور نوڈس نتیجے میں مداخلت کی پیمائش کرتے ہیں اور اس معلومات کو ٹرانسمیٹر کو واپس بھیجتے ہیں۔ تمام باہر جانے والے لنکس (این، بی) کے لیے ایس آئی این آر کی سطحیں پھر تمام نوڈس این کو معلوم ہوتی ہیں، اور ہر نوڈ این اس معلومات کی بنیاد پر اس کے اور متغیرات کا فیصلہ کر سکتا ہے۔ نتیجے میں آنے والا تھرو پٹ لازمی طور پر زیادہ سے زیادہ نہیں ہے۔ تاہم، بے ترتیب ترسیل کے عمل کو چینل اسٹیٹ کے عمل کے ایک حصے کے طور پر دیکھا جا سکتا ہے (بشرطیکہ زیر بہاؤ کی صورت میں نیل پیکٹ بھیجے جائیں، تاکہ چینل اسٹیٹ کا عمل ماضی کے فیصلوں پر منحصر نہ ہو)۔ لہذا، اس تقسیم شدہ نفاذ کا نتیجہ تھرو پٹ تمام روٹنگ اور شیڈولنگ الگورتھم کی کلاس پر بہترین ہے جو اس طرح کی بے ترتیب ترسیل کا استعمال کرتے ہیں۔ متبادل تقسیم شدہ نفاذ کو تقریبا دو کلاسوں میں تقسیم کیا جا سکتا ہے: الگورتھم کی پہلی کلاس زیادہ سے زیادہ وزن کے مسئلے کے لیے مستقل ضرب عنصر کے تخمینوں پر غور کرتی ہے، اور مستقل عنصر تھرو پٹ کے نتائج دیتی ہے۔ الگورتھم کی دوسری کلاس وقت کے ساتھ زیادہ سے زیادہ وزن کے مسئلے کے حل کو اپ ڈیٹ کرنے کی بنیاد پر زیادہ سے زیادہ وزن کے مسئلے کے اضافی تخمینوں پر غور کرتی ہے۔ اس سیکنڈ کلاس میں الگورتھم کو جامد چینل کے حالات اور طویل (اکثر غیر کثیر الجہتی) کنورجنس اوقات کی ضرورت ہوتی ہے، حالانکہ وہ مناسب مفروضوں کے تحت زیادہ سے زیادہ تھرو پٹ حاصل کر سکتے ہیں۔ اضافی تخمینے اکثر بیک پریشر کی اصلاح کو ثابت کرنے کے لیے مفید ہوتے ہیں جب اسے پرانی قطار کے بیک لاگ کی معلومات کے ساتھ لاگو کیا جاتا ہے (نیلی متن کی مشق 4.10 دیکھیں)۔ لیاپونوف ڈرفٹ کے ذریعے ریاضیاتی تعمیر یہ سیکشن ظاہر کرتا ہے کہ کس طرح بیک پریشر الگورتھم ایک سلاٹ سے دوسرے سلاٹ میں قطار کے بیک لاگ کے مربعوں کے مجموعے میں تبدیلی پر لالچ سے باؤنڈ کو کم کرنے کے قدرتی نتیجے کے طور پر پیدا ہوتا ہے۔ فیصلے کی رکاوٹوں اور قطار کی اپ ڈیٹ مساوات کو کنٹرول کریں N نوڈس کے ساتھ ملٹی ہاپ نیٹ ورک پر غور کریں، جیسا کہ اوپر والے حصے میں بیان کیا گیا ہے۔ ہر سلاٹ ٹی، نیٹ ورک کنٹرولر ٹوپولوجی اسٹیٹ ایس (ٹی) کا مشاہدہ کرتا ہے اور ٹرانسمیشن کی شرحوں اور روٹنگ متغیرات کو درج ذیل رکاوٹوں کے تابع منتخب کرتا ہے: ایک بار جب یہ روٹنگ متغیرات کا تعین ہو جاتا ہے، تو ترسیل کی جاتی ہے (اگر ضروری ہو تو آئیڈل فل کا استعمال کرتے ہوئے)، اور اس کے نتیجے میں قطار کے بیکلاگ مندرجہ ذیل کو مطمئن کرتے ہیں: نئے کموڈٹی سی ڈیٹا کی بے ترتیب مقدار کہاں ہے جو سلاٹ ٹی پر نوڈ این پر بیرونی طور پر پہنچتی ہے، اور کیا سلاٹ ٹی پر لنک (این، بی) پر کموڈٹی سی ٹریفک کو مختص کردہ ٹرانسمیشن ریٹ ہے۔ نوٹ کریں کہ یہ کموڈٹی سی ڈیٹا کی مقدار سے زیادہ ہو سکتا ہے جو دراصل سلاٹ ٹی پر لنک (اے، بی) پر منتقل ہوتا ہے۔ اس کی وجہ یہ ہے کہ نوڈ این میں کافی بیک لاگ نہیں ہو سکتا ہے۔ اسی وجہ سے، ای کیو (6) مساوات کے بجائے ایک عدم مساوات ہے، کیونکہ یہ سلاٹ ٹی پر کموڈٹی سی سے نوڈ این کی اصل اینڈوجینس آمد سے زیادہ ہو سکتی ہے۔ Eq کی ایک اہم خصوصیت۔ (6) یہ ہے کہ یہ برقرار رہتا ہے یہاں تک کہ اگر فیصلہ متغیر قطار کے بیک لاگ سے آزادانہ طور پر منتخب کیے جاتے ہیں۔ یہ فرض کیا جاتا ہے کہ تمام سلاٹس t اور سبھی کے لیے، کیونکہ کوئی قطار اپنے لیے مقرر کردہ ڈیٹا کو محفوظ نہیں کرتی ہے۔ لیاپونوف ڈرفٹ موجودہ قطار کے بیک لاگ کے میٹرکس کے طور پر بیان کریں۔ مندرجہ ذیل غیر منفی فنکشن کی وضاحت کریں، جسے لیاپونوف فنکشن کہا جاتا ہے: یہ قطار کے بیک لاگ کے مربعوں کا مجموعہ ہے (بعد کے تجزیے میں سہولت کے لیے صرف 1/2 سے ضرب)۔ مندرجہ بالا مجموعہ تمام n، c کا خلاصہ کرنے کے برابر ہے کیونکہ تمام اور تمام سلاٹس t کے لیے مشروط لیاپونوف ڈرفٹ کی وضاحت کی گئی ہے: نوٹ کریں کہ درج ذیل عدم مساوات سب کے لیے ہے،: قطار اپ ڈیٹ مساوات (Eq. (6)) اور مذکورہ بالا عدم مساوات کا استعمال کرتے ہوئے، یہ ظاہر کرنا مشکل نہیں ہے کہ تمام سلاٹس t کے لیے اور ٹرانسمیشن اور روٹنگ متغیرات کو منتخب کرنے کے لیے کسی بھی الگورتھم کے تحت اور: جہاں B ایک محدود مستقل ہے جو آمد کے دوسرے لمحات اور ٹرانسمیشن کی شرح کے زیادہ سے زیادہ ممکنہ دوسرے لمحات پر منحصر ہے۔ رقم کو تبدیل کرکے ڈرفٹ باؤنڈ کو کم سے کم کرنا بیک پریشر الگورتھم کو ہر سلاٹ ٹی کا مشاہدہ کرنے اور ڈرفٹ باؤنڈ Eq کے دائیں طرف کو منتخب کرنے اور کم سے کم کرنے کے لیے ڈیزائن کیا گیا ہے۔ (7)۔ چونکہ B ایک مستقل ہے اور مستقل ہے، اس لیے یہ زیادہ سے زیادہ کرنے کے مترادف ہے: جہاں زیادہ سے زیادہ فیصلے کو روشن کرنے کے لیے محدود رقوم کو توقعات کے ذریعے آگے بڑھایا گیا ہے۔ کسی توقع کو موقع پر زیادہ سے زیادہ کرنے کے اصول کے مطابق، مذکورہ بالا توقع کو اس کے اندر کے فنکشن کو زیادہ سے زیادہ کرکے زیادہ سے زیادہ کیا جاتا ہے (مشاہدہ کردہ،)۔ اس طرح، کوئی Eqs کا انتخاب کرتا ہے اور پابندیوں کے تابع ہوتا ہے۔ (3)-(5) زیادہ سے زیادہ کرنا: یہ فوری طور پر واضح نہیں ہے کہ کون سے فیصلے مذکورہ بالا کو زیادہ سے زیادہ کرتے ہیں۔ یہ رقم کو تبدیل کر کے روشن کیا جا سکتا ہے۔ درحقیقت، مندرجہ بالا اظہار نیچے کی طرح ہی ہے: وزن کو نوڈس a اور b کے درمیان کموڈٹی c کا موجودہ تفریق بیک لاگ کہا جاتا ہے۔ خیال یہ ہے کہ فیصلہ متغیرات کا انتخاب کیا جائے تاکہ مذکورہ بالا وزن کی رقم کو زیادہ سے زیادہ کیا جا سکے، جہاں وزن متفرق بیک لاگ ہوتے ہیں۔ بدیہی طور پر، اس کا مطلب ہے کہ بڑے تفریقی بیک لاگ کی سمت میں بڑی شرحیں مختص کرنا۔ واضح طور پر کسی کو جب بھی انتخاب کرنا چاہیے۔ مزید برآں، کسی خاص لنک کے لیے دیا گیا ہے، یہ دکھانا مشکل نہیں ہے کہ زیادہ سے زیادہ انتخاب، Eqs کے تابع ہیں۔ (3)-(5)، کا تعین مندرجہ ذیل طریقے سے کیا جاتا ہے: پہلے ایسی چیز تلاش کریں جو لنک (a، b) کے لیے تفریق بیک لاگ کو زیادہ سے زیادہ کرے۔ اگر زیادہ سے زیادہ تفریق والا بیک لاگ لنک (a، b) کے لیے منفی ہے، تو لنک (a، b) پر موجود تمام اشیاء کے لیے تفویض کریں۔ بصورت دیگر، اس لنک پر اجناس کے لیے مکمل لنک ریٹ اور دیگر تمام اجناس کے لیے صفر ریٹ مختص کریں۔ اس انتخاب کے ساتھ، یہ مندرجہ ذیل ہے کہ: سلاٹ ٹی (0 کے ساتھ زیادہ سے زیادہ) پر لنک (a، b) کے لیے بہترین شے کا تفریق بیک لاگ کہاں ہے: یہ صرف انتخاب کرنے کے لیے باقی رہتا ہے۔ یہ مندرجہ ذیل کو حل کرکے کیا جاتا ہے: مندرجہ بالا مسئلہ Eqs میں زیادہ سے زیادہ وزن کے مسئلے سے ملتا جلتا ہے۔ (1)-(2)۔ بیک پریشر الگورتھم زیادہ سے زیادہ وزن کے فیصلوں کا استعمال کرتا ہے، اور پھر اوپر بیان کردہ زیادہ سے زیادہ تفریقی بیک لاگ کے ذریعے روٹنگ متغیرات کا انتخاب کرتا ہے۔ بیک پریشر الگورتھم کی ایک قابل ذکر خاصیت یہ ہے کہ یہ ہر سلاٹ ٹی کو صرف مشاہدہ شدہ ٹوپولوجی اسٹیٹ ایس (ٹی) اور اس سلاٹ کے لیے قطار کے بیک لاگ کی بنیاد پر لالچ سے کام کرتا ہے۔ اس طرح، اسے آمد کی شرحوں یا ٹوپولوجی ریاستی امکانات کے بارے میں علم کی ضرورت نہیں ہے۔ کارکردگی کا تجزیہ یہ سیکشن بیک پریشر الگورتھم کی تھرو پٹ اصلاح کو ثابت کرتا ہے۔ سادگی کے لیے، وہ منظر نامہ جہاں واقعات آزاد اور یکساں طور پر تقسیم ہوتے ہیں (یعنی) اوور سلاٹس پر غور کیا جاتا ہے، حالانکہ اسی الگورتھم کو non-i.i.d میں کام کرتے ہوئے دکھایا جا سکتا ہے۔ منظرنامے (ذیل میں Non-i.i.d کے تحت دیکھیں۔ آپریشن اور یونیورسل شیڈولنگ)۔ متحرک آمد آئیے سلاٹ ٹی پر بیرونی آمد کا میٹرکس بنیں۔ فرض کریں کہ یہ میٹرکس آزاد اور یکساں طور پر تقسیم شدہ ہے (یعنی) محدود دوسرے لمحات کے ساتھ اور ذرائع کے ساتھ سلاٹس پر: یہ فرض کیا جاتا ہے کہ سب کے لیے، جیسا کہ کوئی ڈیٹا نہیں آتا ہے وہ اپنے لیے متعین ہوتا ہے۔ اس طرح، آمد کی شرحوں کا میٹرکس غیر منفی حقیقی اعداد کا ایک میٹرکس ہے، جس میں اخترن پر صفر ہوتے ہیں۔ نیٹ ورک کی صلاحیت کا علاقہ فرض کریں کہ ٹوپولوجی کی حالت ایس (ٹی) یعنی ڈی ہے۔ امکانات کے ساتھ سلاٹس پر (اگر S (t) حقیقی قدر والے اندراجات کے ساتھ ویکٹروں کے بے شمار لامحدود سیٹ میں اقدار لیتا ہے، تو یہ امکان کی تقسیم ہے، نہ کہ امکان ماس فنکشن)۔ نیٹ ورک کے لیے ایک عمومی الگورتھم S (t) ہر سلاٹ t کا مشاہدہ کرتا ہے اور Eqs میں رکاوٹوں کے مطابق ٹرانسمیشن کی شرحوں اور روٹنگ متغیرات کا انتخاب کرتا ہے۔ (3)-(5)۔ نیٹ ورک کی صلاحیت کا علاقہ تمام آمد کی شرح میٹرکس کے سیٹ کی بندش ہے جس کے لیے ایک الگورتھم موجود ہے جو نیٹ ورک کو مستحکم کرتا ہے۔ تمام قطاروں کے استحکام کا مطلب یہ ہے کہ نیٹ ورک میں ٹریفک کی کل ان پٹ شرح اس کی منزل تک پہنچائے گئے ڈیٹا کی کل شرح کے برابر ہے۔ یہ دکھایا جا سکتا ہے کہ صلاحیت کے علاقے میں کسی بھی آمد کی شرح میٹرکس کے لیے، ایک اسٹیشنری اور بے ترتیب الگورتھم ہوتا ہے جو فیصلہ متغیرات کا انتخاب کرتا ہے اور ہر سلاٹ ٹی صرف ایس (ٹی) پر مبنی ہوتا ہے (اور اس لیے قطار کے بیکلاگ سے آزادانہ طور پر) جو سب کے لیے درج ذیل نتیجہ دیتا ہے: ایسا اسٹیشنری اور بے ترتیب الگورتھم جو صرف ایس (ٹی) پر فیصلوں کی بنیاد رکھتا ہے اسے صرف ایس الگورتھم کہا جاتا ہے۔ یہ فرض کرنا اکثر مفید ہوتا ہے کہ یہ اندرونی ہے، تاکہ ایسا ہو کہ، جہاں 1 ہے اگر، اور صفر ہے۔ اس صورت میں، ایک ایس-اونلی الگورتھم ہے جو سب کے لیے درج ذیل حاصل کرتا ہے: ایک تکنیکی ضرورت کے طور پر، یہ فرض کیا جاتا ہے کہ ٹرانسمیشن کی شرحوں کے دوسرے لمحات ان شرحوں کو منتخب کرنے کے لیے کسی بھی الگورتھم کے تحت محدود ہیں۔ اگر ایک محدود زیادہ سے زیادہ شرح ہو تو یہ معمولی طور پر برقرار رہتا ہے۔ صرف S الگورتھم سے موازنہ کرنا کیونکہ بیک پریشر الگورتھم مشاہدہ کرتا ہے اور S (t) ہر سلاٹ t اور فیصلوں کا انتخاب کرتا ہے اور ڈرفٹ باؤنڈ Eq کے دائیں طرف کو کم سے کم کرتا ہے۔ (7)، ہمارے پاس: EQs کو مطمئن کرنے والے کوئی بھی متبادل فیصلے کہاں اور کہاں ہیں۔ (3)-(5)، بشمول بے ترتیب فیصلے۔ اب فرض کریں۔ پھر ایک S-صرف الگورتھم موجود ہے جو Eq کو مطمئن کرتا ہے۔ (8)۔ اسے Eq کے دائیں جانب پلگ کرنا۔ (10) اور یہ نوٹ کرتے ہوئے کہ اس ایس-اونلی الگورتھم کے تحت دی گئی مشروط توقع غیر مشروط توقع کے برابر ہے (کیونکہ ایس (ٹی) یعنی ڈی ہے۔ سلاٹس پر، اور صرف S الگورتھم موجودہ قطار کے بیک لاگ سے آزاد ہے) پیداوار: اس طرح، ایک کواڈریٹک لیاپونوف فنکشن کا بہاؤ تمام سلاٹس t کے لیے ایک مستقل B سے کم یا اس کے برابر ہے۔ یہ حقیقت، اس مفروضے کے ساتھ مل کر کہ قطار کی آمد نے دوسرے لمحات کو محدود کیا ہے، تمام نیٹ ورک قطاروں کے لیے درج ذیل کا اشارہ کرتی ہے: اوسط قطار کے سائز کی مضبوط تفہیم کے لیے، کوئی یہ فرض کر سکتا ہے کہ آمد کی شرحیں اندرونی ہیں، لہذا ایک ایسی Eq ہے۔ (9) کچھ متبادل ایس-صرف الگورتھم کے لیے ہے۔ Eq پلگ کرنا۔ (9) Eq کے دائیں جانب۔ (10) پیداوار: جس سے کوئی فوری طور پر حاصل کرتا ہے (دیکھیں): یہ اوسط قطار کا سائز بڑھتا ہے جیسے جیسے صلاحیت والے علاقے کی حد تک کا فاصلہ صفر ہوتا جاتا ہے۔ یہ آمد کی شرح اور سروس کی شرح کے ساتھ ایک واحد ایم/ایم/1 قطار کی طرح ہی معیاری کارکردگی ہے، جہاں اوسط قطار کا سائز متناسب ہے، کہاں۔ مندرجہ بالا فارمولیشن Non-i.i.d کی توسیع۔ آپریشن اور یونیورسل شیڈولنگ مندرجہ بالا تجزیہ فرض کرتا ہے یعنی۔ سادگی کے لیے خصوصیات۔ تاہم، اسی بیک پریشر الگورتھم کو non-i.i.d میں مضبوطی سے کام کرتے ہوئے دکھایا جا سکتا ہے۔ حالات۔ جب آمد کے عمل اور ٹوپولوجی کی حالتیں ایرگوڈک ہوتی ہیں لیکن ضروری نہیں کہ یعنی، بیک پریشر تب بھی نظام کو مستحکم کرتا ہے۔ زیادہ عام طور پر، ایک عالمگیر شیڈولنگ نقطہ نظر کا استعمال کرتے ہوئے، یہ صوابدیدی (ممکنہ طور پر غیر ارگوڈک) نمونے کے راستوں کے لیے استحکام اور بہترین خصوصیات پیش کرنے کے لیے دکھایا گیا ہے۔ یوٹیلیٹی آپٹیمائزیشن اور پینلٹی کم سے کم بیک پریشر کے ساتھ بیک پریشر کو ڈرفٹ پلس پینلٹی تکنیک کے ذریعے فلو کنٹرول کے ساتھ مل کر کام کرنے کے لیے دکھایا گیا ہے۔ یہ تکنیک لالچ سے ڈرفٹ کے مجموعے اور بھاری جرمانے کے اظہار کو زیادہ سے زیادہ کرتی ہے۔ جرمانے کا وزن ایک پیرامیٹر V کے ذریعے کیا جاتا ہے جو کارکردگی کے تبادلے کا تعین کرتا ہے۔ یہ تکنیک اس بات کو یقینی بناتی ہے کہ تھرو پٹ افادیت زیادہ سے زیادہ O (1/V) کے اندر ہو جبکہ اوسط تاخیر O (V) ہو۔ اس طرح، یوٹیلیٹی کو اوسط تاخیر میں متعلقہ ٹریڈ آف کے ساتھ من مانی طور پر اصلاح کے قریب دھکیل دیا جا سکتا ہے۔ اسی طرح کی خصوصیات کو اوسط پاور کم سے کم کرنے اور زیادہ عام نیٹ ورک صفات کی اصلاح کے لیے دکھایا جا سکتا ہے۔ نیٹ ورک کی افادیت کو زیادہ سے زیادہ کرتے ہوئے قطاروں کو مستحکم کرنے کے لیے متبادل الگورتھم سیال ماڈل تجزیہ، مشترکہ سیال تجزیہ اور لگرینج ضرب تجزیہ، کنویکس اصلاح، اور اسٹاکسٹک گریڈینٹس کا استعمال کرتے ہوئے تیار کیے گئے ہیں۔ یہ نقطہ نظر او (1/وی)، او (وی) افادیت میں تاخیر کے نتائج فراہم نہیں کرتے ہیں۔ مزید دیکھیں اے او ڈی وی ڈائیورسٹی بیک پریشر روٹنگ (ڈی آئی وی بی اے آر) ڈرفٹ پلس پینلٹی ایکزور جیوگرافک روٹنگ ایڈہاک روٹنگ پروٹوکولز کی فہرست لیاپونوف آپٹیمائزیشن حوالہ جات بنیادی ذرائع ایل ٹاسیولاس اور اے ایفریمائڈز، "ملٹی ہاپ ریڈیو نیٹ ورکس میں زیادہ سے زیادہ تھرو پٹ کے لیے محدود قطار کے نظام اور شیڈولنگ پالیسیوں کی استحکام کی خصوصیات"، آٹومیٹک کنٹرول پر آئی ای ای ای ٹرانزیکشنز، جلد۔ 37، نہیں۔ 12، پی پی۔ 1936-1948، دسمبر 1992۔ ایل جارجائڈس، ایم جے نیلی، اور ایل ٹاسیولاس، "ریسورس الاکیشن اینڈ کراس لیئر کنٹرول ان وائرلیس نیٹ ورکس"، فاؤنڈیشنز اینڈ ٹرینڈز ان نیٹ ورکنگ، جلد۔ 1، نہیں۔ 1، پی پی۔ 1-149، 2006۔ ایم جے نیلی۔ مواصلات اور قطار کے نظام پر اطلاق کے ساتھ اسٹاکسٹک نیٹ ورک آپٹیمائزیشن، "مورگن اینڈ کلیپول، 2010۔ نیٹ ورکنگ الگورتھم قطار تھیوری روٹنگ الگورتھم