۲-۴- شبکه نوری غیرفعال اترنت
باتوجه به مزایای اترنت به سایر فناوریها، این فناوری به عنوان پروتکل لایهی پیوند داده انتخاب شده است. شبکهی نوری غیرفعال اترنت، یک شبکهی مبتنی بر فیبر نوری غیرفعال است که ترافیک داده را به شکل محصور در فریمهای اترنت، حمل و منتقل میکند. این شبکه به گونهای است که نمیتوان آن را یک شبکه با رسانهی مشترک یا یک شبکهی نقطه به نقطه دانست و در واقع ترکیبی از این دو نوع شبکه است. با توجه به شکل ۲-۶ در مسیر رو به پایین، فریمهای اترنت توسط ترمینال از طریق یک رابط غیرفعال ۱ به به واحدها فرستاده میشوند. معمولا عددی بین ۴ تا ۶۴ است که تعداد واحدهای نوری شبکه است. این رفتار مشابه یک شبکه با رسانهی انتقال مشترک است. در مسیر رو به پایین، از آنجایی که اترنت ذاتا انتشار دهنده است کاملا با معماری شبکه نوری غیرفعال اترنت تطابق دارد، بستهها توسط ترمینال انتشار مییابند و واحد مقصد براساس آدرس MAC آنها را دریافت میکند[۷].
شکل ۲-۶- ترافیک مسیر رو به پایین [۷]
در مسیر رو به بالا، فریمهای دادهی هر واحد فقط توسط ترمینال دریافت میشوند و نه واحدهای دیگر. در این حالت در مسیر رو به بالا، رفتار شبکه نوری غیرفعال اترنت مشابه معماری نقطه به نقطه است. اگرچه بر خلاف شبکهی نقطه به نقطهی واقعی، اگر واحدهای مختلف به طور همزمان فریمهای داده ارسال کنند ممکن است برخورد و تداخل به وجود آید. بنابراین در مسیر رو به بالا، شبکه به یک مکانیزم داوری برای جلوگیری از تداخل داده و تقسیم عادلانهی ظرفیت کانال نوری نیاز دارد. در واقع چالش دیگر در طراحی شبکه نوری غیرفعال، تقسیم کانال رو به بالاست که به تمامی واحدها تعلق دارد. اگر تقسیم کانال به شکل عادلانه و کارامد صورت نگیرد، احتمال دارد دو واحد انتقال اطلاعات خود را به گونهای آغاز کنند که وقتی فریمهای آنها به ارتباط دهنده میرسند، همپوشانی و تداخل داشته باشند. به عنوان مثال شکل ۲-۷ یک روش تقسیم کانال مبتنی بر زمان را در شبکه نوری غیرفعال اترنت مطرح میکند. به هر کدام از واحدها یک بازهی زمانی اختصاص داده میشود که در هر بازه چندین فریم اترنت میتواند منتقل شوند. هر واحد فریمهای ریافتی از مشترکان را بافر میکند تا زمانی که بازهی زمانی مربوطه فرا برسد. وقتی بازهی زمانی فرا میرسد، واحد تمام فریمهای ذخیره شده در بافر را با نهایت سرعت کانال براساس یکی از نرخهای استاندارد اترنتMbps 10/100/1000/10000 ارسال میکند. روش تخصیص بازهی زمانی میتواند یک روش تخصیص ثابت[۵۹] یا روش تخصیص پویا براساس اندازهی فعلی صف در هر واحد باشد[۷].
شکل ۲-۷- ترافیک مسیر رو به بالا [۷]
در شبکه دسترسی نوری تنها یک مسیر ارتباطی از ترمینال به هر کدام از واحدها و از هر واحد به ترمینال وجود دارد که در تمام همبندیهای مبتنی بر شبکه نوری غیرفعال صدق میکند. بنابراین ترمینال میتواند دسترسی به کانال مشترک را مدیریت و داوری کند. البته چالش این نوع پیادهسازی این است که ترمینال نمیداند هر واحد چند بایت اطلاعات را بافر کرده است. برای آنکه ترمینال بتواند تخصیص صحیح بازههای زمانی را انجام دهد، باید وضعیت دقیق واحد را بداند. یکی از راه حل ها استفاده از سرکشی[۶۰] براساس پیامهای اعطا[۶۱] و درخواست[۶۲] است. پیام درخواست از یک واحد به ترمینال فرستاده میشود تا تغییرات وضعیت واحد مانند مقدار دادهی بافر شده را گزارش کند. سپس ترمینال درخواستها را پردازش کرده، بازههای زمانی متفاوت را به واحدها تخصیص میدهد و اطلاعات مربوط به این تخصیص را با پیام اعطا به واحدها ارسال میکند[۷].
برای پشتیبانی از تخصیص پهنای باند توسط ترمینال، پروتکل کنترل چند نقطهای[۶۳] ارائه شده است. این پروتکل مبتنی بر دو پیغام اترنت دروازه[۶۴] و گزارش[۶۵] است. پیغام دروازه از ترمینال به یک واحد فرستاده میشود تا یک بازهی زمانی را به آن اختصاص دهد. پیغام گزارش توسط یک واحد استفاده میشود تا شرایط محلی خود مانند میزان فضای پر شدهی بافر را به ترمینال اطلاع دهد بدین منظور که به ترمینال در تخصیص هوشمندانه کانال کمک کند. هر دو پیغام، فریمهای کنترلی MAC هستند که توسط زیرلایهی کنترلی MAC در لایه پیوند داده پردازش میشوند[۷].
۲-۵- چالش تخصیص پهنای باند در شبکه فیبر نوری غیرفعال اترنت
یکی از مهمترین چالشها در شبکههای نسل آینده، تامین، تخصیص و تضمین منابع موردنیاز برای فراهم آوردن و پشتیبانی از انواع مختلف سرویس است. منابع در شبکههای نسل آینده شامل توان پردازشی(پردازنده)، حافظه و پهنای باند میباشند که مدیریت و کنترل صحیح هرکدام از این منابع منجر به ارائه سرویس با کیفیت سرویس مطلوب کاربر است. همانطور که در بخش ۲-۴ توضیح داده شد، شبکهی فیبر نوری غیرفعال اترنت، شبکهای یک به چند نقطهای و یک همبندی رایج است. در مسیر رو به پایین، ترمینال خط نوری[۶۶]، فریمها را به واحدهای شبکهی نوری[۶۷] ارسال میکند و هر واحد فریمهای مربوط به خود را دریافت میکند. در مسیر رو به بالا، واحدهای شبکهی نوری فریمها را از طریق شبکهی توزیع نوری، مستقیما به ترمینال میفرستد اما نمیتواند به سایر واحدها دسترسی داشته باشند. در صورتی که تمامی واحدها به طور همزمان فریمی ارسال کنند، یک الگوریتم تخصیص پهنای باند مناسب برای جلوگیری از برخورد موردنیاز است تا منبع پهنای باند سیستم را به واحدها، به طور مساوی و کارامد تخصیص دهد[۹].
به منظور تخصیص پهنای باند (یا بازه زمانی) برای هر واحد، ترمینال باید یک الگوریتم تخصیص پهنای باند براساس درخواستهای واحدها، چند سیاست تخصیص و/یا قرارداد سطح سرویس، اجرا کند. در این زمینه الگوریتمهای تخصیص پهنای باند بسیاری ارائه شدهاند که در دو دستهبندی گستردهی تخصیص پهنای باند ایستا[۶۸] و تخصیص پهنای باند پویا[۶۹] قرار میگیرند. در روش ایستا، به هر واحد یک بازهی زمانی با طول ثابت اختصاص مییابد که پیادهسازی راحتی دارد. اما در این روش ذات دورهای[۷۰] ترافیک شبکه، ممکن است منجر به موقعیتی شود که در آن بعضی بازههای زمانی حتی در بار کم، سرریز کنند و بستهها دچار تاخیر شوند، در حالی که برخی بازههای زمانی دیگر حتی در بار زیاد به طور کامل استفاده نشوند و پهنای باند رو به بالا کمتر از حد استفاده شود[۹].
به همین علت تخصیص پهنای باند ایستا مورد توجه قرار نمیگیرد و برای افزایش بهرهوری از پهنای باند، ترمینال باید به طور پویا یک بازهی زمانی متغیر را براساس تقاضای لحظهای واحدها به آنها تخصیص داد. برای پیادهسازی تخصیص پهنای باند پویا، سرکشی بسیار مورد استفاده قرار گرفته است. با سرکشی، ترمینال میتواند به طور پویا پهنای باند را به واحدها تخصیص دهد و به طور انعطاف پذیر انتقال چند واحد را مدیریت میکند که منجر به افزایش بهرهوری پهنای باند و بهبود کارایی شبکه میشود. با در نظر گرفتن این حقیقت که کیفیت سرویس مهمترین دغدغه در شبکهی فیبر نوری غیرفعال اترنت است، الگوریتمهای تخصیص پهنای باند پویا به دو دستهی الگوریتمهای تخصیص پهنای باند پویا بدون تامین کیفیت سرویس و با تامین کیفیت سرویس نیز تقسیم میشوند که در هر کدام از این دسته ها، روشهای متعددی ارائه شدهاند[۹]. در ادامه در بخش پیشینه تحقیق به بررسی این روشها و الگوریتمها میپردازیم.
۲-۶- پیشینه تحقیق
۲-۶-۱- روش IPACT[71]
روش پیشنهادی در [۱۳] اولین روش تخصیص پهنای باند پویا برای شبکهی فیبر نوری غیرفعال اترنت است که یک فرایند مذاکرهی منبع را برای سهولت در گزارشدهی صف و تخصیص پهنای باند، به کار میگیرد. ترمینال به واحدها سرکشی میکند و به هر واحد با روش دورهای[۷۲]، بازهی زمانی اعطا میکند. بازهی زمانی اعطا شده به هر واحد به وسیلهی وضعیت صف که از سمت واحد گزارش داده میشود، مشخص میگردد. بنابراین ترمینال قادر خواهد بود تا بار ترافیکی پویای هر واحد را بداند و پهنای باند رو به بالا را براساس تقاضای هر واحد تخصیص دهد. علاوه بر این، این روش قرارداد سطح سرویس کاربران نهایی را به کار میگیرد تا پهنای باند مخصوص هر واحد را محدود کند. برای سادگی در بیان نحوهی عملکرد این الگوریتم، فرض میکنیم سیستم دارای ۳ واحد است:
۱- فرض میکنیم ترمینال در زمان t0 میداند دقیقا چه تعداد بایت در بافر هر واحد در حال انتظار است و زمان رفت و برگشت[۷۳] به هر واحد را نیز میداند. ترمینال این اطلاعات را در یک جدول سرکشی همانطور که در شکل ۲-۸ قسمت الف میبینیم، نگهداری میکند. در زمان t0 ترمینال یک پیغام کنترلی به واحد اول میفرستد تا به این واحد اجازه دهد ۶۰۰۰ بایت ارسال کند. این نوع پیغام، مجوز[۷۴](همان دروازه در مباحث قبلی) نامیده میشود. از آنجاییکه در جهت رو به پایین، ترمینال اطلاعات را به تمام واحدها اطلاعرسانی می کند، یک مجوز باید شامل شناسهی واحد مقصد و اندازهی مجوز برحسب بایت باشد.
۲- پس از دریافت مجوز از ترمینال، واحد ۱ شروع به ارسال دادهی خود به اندازهی مجوز اعطا شده میکند که در این مثال با توجه به شکل ۲-۸ قسمت ب، واحد ۱ تا ۶۰۰۰ بایت داده ارسال می کند. به طور همزمان واحد ۱ از کاربران بستههای داده نیز دریافت میکند. پس از پایان انتقال، واحد ۱ پیغام کنترلی خود (گزارش) را تولید میکند. در گزارشی که توسط واحد ۱ ارسال شده به ترمینال گفته میشود که در بافر این واحد لحظهای که گزارش اعطا شده، چند بایت وجود داشته است. در این مثال این مقدار ۵۵۰ بایت است.
۳- حتی پیش از آن که ترمینال پاسخی از جانب واحد دریافت کند، میداند که چه زمانی آخرین بیت انتقال واحد میرسد. چگونه این مسئله را میداند؟
الف- اولین بیت دقیقا بعد از زمان رفت و برگشت، می رسد. زمان رفت و برگشت در گردش ما، شامل زمان رفت و برگشت واقعی، زمان پردازش مجوز، زمانی برای تنظیم بیت و بایت براساس دادهی دریافتی است، که مجموع این موارد دقیقا برابر بازهی زمانی از هنگام ارسال مجوز به یک واحد تا هنگام رسیدن داده از همان واحد، است.
ب- از آن جایی که ترمینال میداند مجوز ارسال چه تعداد بایت را به واحد ۱ داده است، اطلاع دارد که آخرین بیت چه زمانی از این واحد میرسد. با دانستن زمان رفت و برگشت برای واحد ۲، ترمینال میتواند یک مجوز را برای این واحد برنامهریزی کند، بنابراین اولین بیت از واحد ۲ بلافاصله بعد از آخرین بیت از واحد ۱ با یک بازهی محافظ[۷۵] کوچک فی مابین میرسد. بازههای محافظ، در مقابل نوسانات زمان رفت و برگشت و زمان پردازش پیغامهای کنترلی از واحدهای مختلف، حفاظت را تامین می کنند. علاوه بر این، ترمینال به زمانی نیاز دارد تا حساسیت خود را با توجه به این حقیقت که واحدها در فواصل مختلفی نسبت به ترمینال قرار دارند، مجددا تنظیم کند.
۴- پس از مدتی مطابق شکل ۲-۸ قسمت ج داده از واحد ۱ میرسد. در پایان انتقال از واحد ۱، گزارش جدیدی وجود دارد که شامل اطلاعاتی مبنی بر این مسئله است که چه تعداد بایت در بافر واحد ۱ هنگام ارسال گزارش باقی مانده است. ترمینال از این اطلاعات برای به روز رسانی جدول سرکشی خود استفاده می کند.
۵- مشابه مرحلهی فوق، ترمینال می تواند زمانی که واحد ۲ آخرین بیت خود را ارسال میکند، محاسبه کند. بنابراین ترمینال میداند چه زمانی مجوز را به واحد ۳ ارسال کند لذا دادهی آن به انتهای دادهی واحد ۲ متصل میشود. پس از مدتی با توجه به شکل ۲-۸ قسمت د دادهی واحد ۲ میرسد و ترمینال مجددا جدول خود را این بار برای واحد ۲ به روز رسانی میکند. باید توجه داشت که اگر واحد بافر خود را به طور کامل تخلیه کند، صفر بایت را به ترمینال گزارش میدهد. به همین علت در چرخهی بعدی به واحد به اندازه صفر بایت مجوز داده میشود به این معنا که میتواند گزارش جدیدی ارسال کند(نه هیچ دادهای).
براساس توضیحات فوق بدیهی است که هیچ نیازی به همگامسازی واحدها و همچنین نیازی به اجرای محدوده گذاری[۷۶](با ایجاد تاخیر در پاسخدهی از طرف واحد به یک اندازهی مشخص، اینگونه به نظر میآید که همهی واحدها در یک فاصلهی مساوی از ترمینال قرار دارند)که در گذشته در طرحهای تقسیم زمانی چندگانه به کار گرفته میشد، نیست.
در IPACT طرحهای تخصیص پهنای باند متعددی شامل تخصیص سرویس ثابت[۷۷]، سرویس محدود[۷۸]، اعتبار ثابت [۷۹]، ، اعتبار خطی[۸۰] و تخصیص ارتجاعی[۸۱]، بررسی شده اند که هر کدام از آنها به شکلی متفاوت به درخواست پهنای باند واحدها پاسخ میدهند.
شکل ۲-۸- مراحل الگوریتم IPACT [۱۳]
تخصیص سرویس ثابت به حداکثر دادهی دریافتی موردتقاضا توجهی ندارد و همواره حداکثر دادهی دریافتی را به واحد اختصاص می دهد. در طرح تخصیص سرویس محدود، ترمینال به سادگی تعداد بایتهایی که واحد تقاضا کرده است در اختیارش قرار میدهد اما از حداکثر دادهی دریافتی در یک مرحله[۸۲]، تجاوز نمیکند. این طرح قدیمیترین روش است زیرا فرض می کند که پس از اینکه واحد درخواست خود را ارسال کرد، هیچ بستهای وارد نمیشود. در عمل، به خاطر زمان دورهای میان ترمینال و هر واحد، ممکن است بستههای بیشتری از لحظهای که واحد پیغام گزارش خود را ارسال میکند تا لحظهای که پیغام دروازه را دریافت میکند، وارد شوند. در این شرایط بستههای تازه وارد نمی توانند در چرخهی جاری ارسال شوند که منجر به افزایش تاخیر بسته میشود. برای حل این مشکل، طرحهای اعتبار ثابت و خطی ارائه شدند.
در تخصیص اعتبار ثابت، به حداکثر دادهی دریافتی مورد تقاضا، اعتباری اضافه میشود و در حداکثر دادهی دریافتی اعطا شده، در نظر گرفته میشود. اندازهی اعتبار ثابت است و هیچ اهمیتی ندارد که حداکثر دادهی دریافتی مورد تقاضا چقدر بزرگ باشد. وقتی واحد پیغام دروازه را دریافت میکند، بستهها را به اندازهی حداکثر دادهی دریافتی به اضافهی ترافیک ثابت، میفرستد. نحوهی انتخاب اندازهی اعتبار ممکن است بر عملکرد شبکه تاثیر بگذارد. اگر اندازه خیلی کوچک باشد نمیتواند تاخیر بسته را بهبود دهد و اندازهی خیلی بزرگ، بهرهوری پهنای باند کانال رو به بالا را کاهش میدهد. انتخاب اندازهی اعتبار بهتر است براساس ویژگیهای ترافیک و دادهی تجربی باشد.
در تخصیص اعتبار خطی نیز اعتباری به حداکثر دادهی دریافتی مورد تقاضا اضافه میشود البته اندازهی اعتبار خطی متناسب با حداکثر دادهی دریافتی مورد تقاضا است. این طرح از آنجا نشات میگیرد که ترافیک شبکه معمولا به اندازهی مشخصی قابل پیش بینی است به این معنا که اگر انفجار داده[۸۳] رخ دهد این انفجار به احتمال بسیار زیاد برای زمان طولانیتر ادامه مییابد.
در تخصیص ارتجاعی، هیچ محدودیتی بر حداکثر دادهی دریافتی اعمال نمیشود و تنها محدودیت، حداکثر چرخهی زمانی است. حداکثر دادهی دریافتی به گونهای اعطا میشود که اندازهی انباشتهی اعطا شده به آخرین N از تجاوز نکند، N تعداد واحدهاست. بدین روش اگر فقط یک واحد داده برای ارسال داشته باشد، حداکثر دادهی دریافتی اعطا شده است.در میان طرحهای تخصیص پهنای باند فوق، تخصیص محدود بهترین عملکرد را ارائه میدهد.
الگوریتم IPACT پهنای باند را براساس نیاز دقیق هر واحد، توزیع می کند به همین خاطر هیچ بازهی زمانی بلااستفادهای وجود ندارد. در این روش، ترمینال فریمهای گزارش را از واحدهای مختلف از طریق سرکشی آمیخته دریافت میکند سپس فریم دروازه (مجوزدهی) را به هر واحد به طور مستقل براساس درخواست پهنای باند در فریم گزارش، میفرستد. با این روش سرکشی آمیخته، انتقال رو به بالای فریم گزارش و انتقال رو به پایین فریم دروازه، با زمان ارسال داده به واحدها همپوشانی دارد لذا زمان بیکاری وجود ندارد. این در حالی است که در تخصیص پهنای باند به روش ایستا در هر چرخه، ترمینال پهنای باند ثابتی را به هر واحد اختصاص میدهد و واحد هیچ درخواستی ندارد. به همین علت میزان بهرهوری روش IPACT از پهنای باند نسبت به روش ایستا بسیار بیشتر است. البته این روش برای سرویسهای با الویت بالا که نسبت به تاخیر و واریانس تاخیر حساس هستند، مناسب نیست.
۲-۶-۲- روش صف دو مرحلهای
روش صف دو مرحلهای مطرح شده در [۱۴] یک روش سلسله مراتبی پویا برای تخصیص پهنای باند براساس تقاضای واحدها است. در این روش ابتدا پهنای باند به کلاسهای سرویسهای متمایز دارای اولویت بالا، متوسط و کم تخصیص داده میشود که این مرحله، مرحلهی تخصیص لایهی کلاس[۸۴] نام دارد. پس از اتمام این مرحله، کل پهنای باند تخصیص داده شده به هر کلاس توسط ترمینال میان تمام واحدهای متعلق به همان کلاس براساس تقاضای آنها با روش عدالت حداکثر-حداقل[۸۵] توزیع میشود. این مرحله نیز مرحلهی تخصیص لایهی واحد[۸۶] نام دارد. در این روش یک شبکه نوری غیرفعال اترنت با N واحد و سه کلاس سرویس مختلف با اولویتهای بالا، متوسط و کم در نظر گرفته شده است. ترمینال از یک جدول برای ذخیرهسازی درخواستهای واحدها، نگهداری میکند و بلافاصله پس از دریافت پیغام گزارش، این جدول را به روزرسانی میکند. در صورتی که پهنای باند رو به بالا نتواند تمام درخواستهای واحدها را تامین کند، ترمینال برخی تقاضاها را نادیده میگیرد. از آنجایی که ترمینال، پهنای باند را متناسب با تقاضاها تقسیم میکند، یک مقدار تقاضای زیاد ممکن است تمام پهنای باند را به تصرف دراورد. بنابراین برای جلوگیری از به انحصار درامدن پهنای باند در ترافیک بالا، یک آستانهی پهنای باند برای هر کلاس سرویس به شکل در نظر گرفته میشود که برابر با حاصلضرب دو مقدار و است به طوری که پهنای باند موردنیاز یک فریم است و شرط را با تامین میکند. زمانی که هر کلاس پهنای باند موردنیاز خود را اعلام میکند، پهنای باند تخصیص داده شده به آن توسط معادله (۲-۱) محاسبه میشود.
(۲-۱)
در صورتی که پهنای باند موردنیاز یک کلاس از آستانهی پهنای باند آن کمتر باشد، پهنای باند باقیمانده به تناسب میان سایر کلاسها براساس وزن آنها توزیع میشود. آستانهی پهنای باند همچنین، حداقل مقداری را برای گذردهی یک کلاس سرویس در ترافیک بالا، تضمین میکند. این روش حداقلِ سهم از یک منبع را میان متقاضیان آن که نمیتوانند تمامی سهم موردنیاز خود را دریافت کنند توسط مراحل زیر به حداکثر میرساند.
-
- منبع به اشتراک گذاشته شده به طور مساوی میان تمام کاربران تقسیم میشود.
-
- هیچ کاربری بیشتر از تقاضایش، منبع دریافت نمیکند.
-
- کاربرانی که به اندازهی تقاضای خود، منبع دریافت نکردهاند، منبع باقیمانده را به طور مساوی به اشتراک میگذارند.
علیرغم مزایایی که این روش دارد، برای سرویسهای با الویت بالا، تاخیر بسته را افزایش میدهد و گذردهی آن برای بستههای با الویت کم، پایین است.
۲-۶-۳- روش BGP[87]
روش سرکشی تضمین شدهی پهنای باند در [۱۵]، به پهنای باند رو به بالا اجازه میدهد براساس قرارداد سطح سرویس میان مشترکین به اشتراک گذاشته شود. در این روش واحدهای شبکه به دو دستهی مجزا تقسیم میشوند، دستهی اول شامل تعدادی از واحدها با پهنای باند تضمین شده است در حالی که دستهی دیگر شامل واحدهایی است که به سرویس با پهنای باند تضمین شده نیاز ندارند. این سیستم طراحی شده تا تضمین کند واحدها با پهنای باند تضمین شده، زمان انتقال کافی که میان مشترک و تامین کنندهی سرویس در قرارداد سطح سرویس توافق شده است را دریافت خواهند کرد، درحالی که از هر پهنای باند بلااستفاده برای تامین سرویس بدون تضمینِ تحویل[۸۸] برای واحدها با پهنای باند تضمین نشده، استفاده میکند.
این روش، سرکشی تضمین شدهی پهنای باند نامیده میشود زیرا یک سیستم سرکشی حضور و غیاب [۸۹] است که در آن ترمینال به واحدها یکی پس از دیگری به ترتیب سرکشی می کند تا به آنها اجازه دهد به ترمینال داده ارسال کنند. ترمینال، کنترل کنندهی مرکزی است که به واحدها با ارسال پیغام سرکشی دائما سرکشی می کند تا به آنها بازهی انتقال اعطا کند. پس از دریافت پیغام سرکشی، واحد شروع به ارسال داده به ترمینال می کند. پهنای باند رو به بالای کلی به واحدهای(ورودیها) پهنای باند مساوی تقسیم میشود. ترمینال یک جدول ورودی شامل دنبالهای از ورودیهای سرکشی شده را نگهداری میکند. هر ورودی یک واحد پهنای باند را فرا میگیرد که یا به یک واحد با پهنای باند تضمین شده تخصیص خواهد یافت یا به طور پویا به یک واحد با پهنای باند تضمین نشده اختصاص مییابد. هر ورودی دو بخش دارد، بخش اول شامل شماره شناسهی واحدی است که ورودی را تصرف می کند و بخش دوم شامل تاخیر انتشار واحد به ترمینال است. تعداد ورودیهای نهایی جدول برابر حداکثر تعداد واحدهای پهنای باند است. ترمینال همچنین لیستی از واحدها با پهنای باند تضمین نشده دارد که دنبالهی سرکشی به واحدها را مشخص میکند. این لیست ساختاری مانند جدول ورودی دارد و هر المان دارای دو بخش است. بخش اول شامل شماره شناسهی واحد با پهنای باند تضمین نشده و بخش دوم شامل تاخیر انتشار واحد به ترمینال است، تعداد نهایی المانها در لیست ثابت نیست. به هر واحد با پهنای باند تضمین شده میتوان یک یا چند واحد پهنای باند(ورودی) براساس نیازمندیهای پهنای باند در قرارداد سطح سرویس که مرتبط به پرداخت کاربران نهایی است، تخصیص داد یعنی هرچه واحد با پهنای باند تضمین شده، ورودی بیشتری دریافت کند، پهنای باند بیشتری از مسیر رو به بالا را تصرف می کند و بیش از یکبار در دورهی سرکشی توسط ترمینال به آن سرکشی خواهد شد. ورودیهایی که توسط واحد با پهنای باند تضمین شده تصرف نشدهاند به طور پویا میتوانند به واحدها با پهنای باند تضمین نشده اختصاص یابند.
ترمینال برای تخصیص این ورودیهای موجود به واحدها با پهنای باند تضمین نشده به ترتیب لیست سرکشی میکند. علاوه بر این میتوان پس از استفادهی یک واحد با پهنای باند تضمین شده از یک ورودی، میتوان پهنای باند زائد و اضافی باقی مانده را به واحدی با پهنای باند تضمین نشده به طور پویا تخصیص داد. در این شرایط باید یک آستانهی از پیش تعریف شده برای تشخیص این مسئله که آیا پهنای باند اضافی باقی مانده قابل استفاده است یا خیر، وجود داشته باشد. اگر پهنای باند اضافی از آستانه کمتر باشد، قابل تخصیص به واحدی با پهنای باند تضمین نشده است، در غیر این صورت پهنای باند اضافی رها خواهد شد. ترمینال به واحدها به ترتیب ورودیها در جدول ورودی به همراه اشارهگری که ورودی جاری را نشان میدهد، سرکشی میکند. اگر یک ورودی در جدول ورودی به واحدی با پهنای باند تضمین شده تخصیص نیافته باشد، میتوان آن را به واحدی با پهنای باند تضمین نشده که توسط اشارهگر دیگری در لیست مربوط به این واحدها مشخص میشود، اختصاص داد. روش BGP شامل دو قسمت است، قسمت اول الگوریتم زمانبندی برای سرکشی و قسمت دوم الگوریتم توزیع عادلانه[۹۰] برای توزیع عادلانهی چند ورودی از میان تمام ورودیها به یک واحد با پهنای باند تضمین شده است.
قسمت اول:
۱- در ابتدا ترمینال، جدول ورودی واحدها با پهنای باند تضمین شده و لیست واحدها با پهنای باند تضمین نشده را براساس نیازمندیهای پهنای باند واحدها در قرارداد سطح سرویس و سایر پارامترهای سیستم مانند تاخیر انتشار برای واحد مستقل و حداکثر اندازهی دادهی دریافتی ، مقداردهی اولیه میکند. در مقداردهی اولیه، الگوریتم توزیع عادلانه نیز به کار گرفته میشود.
۲- ترمینال شروع به سرکشی به واحدها با پهنای باند تضمین شده به ترتیب مشخص شده در جدول ورودی یا سرکشی به طور پویا به واحدها با پهنای باند تضمین نشده به ترتیب لیست میکند که این کار را با ارسال پیغام اعطا با اندازهی مناسب دادهی دریافتی در مسیر رو به پایین انجام می دهد.