در اين نوع صف بندی تا زمانی که بسته ای برای ارسال وجود داشته باشد، پهنای باند تخصيص می يابد و يا بعبارت ديگر، پهنای باند، بلا استفاده نخواهد ماند.
در شكل(2-3)، ريل نشانگر ظرفيت موجود و هر واگن نشانگر يك بسته مي باشد و همواره ظرفيت خط مورد استفاده قرار مي گيرد. كه دراين دسته مي توان روش هاي صف بندي با اولويت مطلق4 و روش صف بندي عادلانه5 را نام برد. در روش اولويت مطلق به برخي ارتباط ها بطور مطلق و بدون شرط حق استفاده از منابع لينك را مي دهند ولي در روش صف بندي عادلانه هر ارتباط بر حسب يك وزن خاص حق استفاده از منابع را دارد.
الگوريتم هاي صف بندي با كار مداوم از قبيل WFQ6، WRR7 ، FIFO8، GPS9 و … در روش مورد استفاده براي انتخاب صف مناسب با هم متفاوتند[36-42]. در ساده ترين نوع، از تقدم محض براي الگوريتم صف بندي استفاده مي شود كه در آن صف هاي با اولويت كمتر فقط وقتي سرويس دهي
مي شوند كه هيچ بسته اي در صف هاي با اولويت بالاتر موجود نباشد.
بر خلاف روش صف بندي FIFO و يا با اولويت مطلق كه بصورتي ناعادلانه به تخصيص پهناي باند مابين جريان هاي عبوري مي پردازد و در واقع در برهه هاي كوتاه زماني ترافيكهائي كه بيشتر ماهيت هجومي10 دارند بيشتر پهناي باند را به خود اختصاص مي دهند تا ترافيكهاي داراي الگوي ملايم، روش هاي صف بندي عادلانه داراي اين قابليت هستند كه كرانهاي مشخصي را از نظر تأخير براي كليه جريانهاي عبوري تضمين كنند و در همه برهه هاي زماني ظرفيت را بنحوي عادلانه مابين اين جريانها به اشتراك بگذارند.
شكل2-3: شمائي از يك الگوريتم صف بندي با كار مداوم[45]
2-3-1 روش صف بندی FIFO
در اين روش که به روش FCFS1 نيز موسوم است، بسته های ورودی به صف، به همان ترتيب ورود به صف، مورد سرويس دهی قرار می گيرند. اين روش نيز از نظر پياده سازي در سطح شبکه بسيار ساده است.
2-3-2 روش صف بندي با اولويت مطلق
در اين روش، براي هر اولويت يك صف وجود دارد و تا زماني كه يك بسته در اولويت بالا وجود دارد بسته هاي موجود در اولويت پائين سرويس دهي نمي شوند. اين روش نيز از نظر پياده سازي بسيار ساده است و داراي پيچيدگي از O(1) مي باشد. روش صف بندي با اولويت، روشي موثر براي برخورد با ترافيك هاي مهم مي باشد.
اگر بسته هاي دريافت شده در صف با اولويت بالا داراي نرخي بيشتر يا مساوي با توان سرويس دهي رابط خروجي باشند، هيچگونه سرويس دهي به بسته هاي موجود در صف هاي با اولويت پائين صورت
نمي گيرد و اين صف ها دچار فقر2 در سرويس دهي مي شوند به همين منظور اين روش سرويس دهي فقط در برخي موارد خاص يا برای سرويس های حياتی و مهم در شبكه استفاده مي شود.
يك كاربرد عمده اين روش در ارسال اطلاعات كنترلي بين سوئيچهاي شبكه مي باشد. اين روش
صف بندي ميتواند به همراهي با روش هاي ديگر صف بندي مورد استفاده قرار گيرد. مثلاً
مي توان از يك صف با اولويت بالا براي ارسال اطلاعات كنترلي شبكه استفاده كرد در حالي كه چندين صف با اولويت پائين تر پهناي باند باقي مانده را بصورتي عادلانه مابين ترافيك خود تقسيم مي كنند.
2-3-3 روش GPS
در حالت ايده آل، در اين روش براي هر ارتباط يك صف جداگانه در نظر گرفته مي شود سپس هر صف غير خالي بترتيب بررسي شده و به مقداري بي نهايت كوچك سرويس دهي مي شود. بنابراين در هر بازة زماني حداقل يكبار به تمامي صف ها سركشي شده و به آنها سرويس دهي مي شود. ارتباط ها مي توانند داراي وزن بوده و متناسب با اين وزنشان سرويس دريافت كنند. سرويس دهنده از روي صف هاي خالي جهش مي كند. اين روش منجر به تقسيم عادلانه حداكثر-حداقل پهناي باند مي شود.
فرض كنيد در شكل(2-4)، سوئيچ داراي N ارتباط با وزنهاي مساوي بوده كه هر كدام با سرعتي معادل 1/N سرعت سرويس دهنده، داده براي بلوك زمان بندي1 ارسال مي كنند. سرويس دهنده طبق قانون حداكثر-حداقل بايد 1/N پهناي باند را به هر كدام تخصيص دهد. چون سرويس دهنده در هر بار سرويس به مقدار بي نهايت كوچك از هر ارتباط را سرويس مي دهد به اين هد ف نائل خواهد شد. حال اگر همه منابع بجز A بيش از سهم خود داده ارسال كنند و منبع A، با نرخي كمتر از سهم خود داده ارسال كند صف منبع A خالي خواهد شد. اگر اين اتفاق افتاد، سرويس دهنده از روي صف خالي پرش كرده و به خاطر نحوة سرويس گردشي آن [38]، زمان ذخيره شده بين بقية ارتباط ها بطور مساوي تقسيم خواهد شد.
اگر ارتباط B با نرخي بيش از حد سرويس 1/N ولي كمتر از ميزان سرويسي كه پس از خالي شدن صف A تحويل مي گيرد، داده ارسال كند سرانجام صف آن نيز خالي خواهد شد. بنابراين بقيه ارتباط ها به جز B و A كمي بيشتر سرويس مي گيرند كه خود مي تواند باعث خالي شدن صف هاي ديگر شود. بدين ترتيب ارتباط هائي كه كمتر از سهمشان پهناي باند تقاضا مي كنند به خواستة خود مي رسند در حالي كه بقية ارتباط ها كه تقاضائي بيش از سهم خود دارند پهناي باند مساوي دريافت مي كنند. بنابراين طبق تعريف، GPS روشي براي رسيدن به تقسيم عادلانه حداكثر- حداقل است.
معمولاً عملكرد اين روش بعنوان مرجع مقايسه براي ديگر روشها بكار مي رود.
لازم به توضيح است كه در معيار حداكثر-حداقل كه سعي در حداكثر كردن حداقل سهم كاربر ناراضي دارد رعايت اصول زير الزامي است:
- منابع به ترتيب ميزان درخواستهاي صعودي تخصيص مي يابند.
- هيچ كاربري بيش از درخواست خود منبع در اختيارش قرار نمي گيرد.
- كاربراني كه به تقاضاي خود نرسيده اند مقدار سهم مساوي از منبع دريافت مي كنند.
- سهم كاربران ناراضي كمتر از سهم كاربران راضي نمي باشد.
اگر ارتباط ها وزن دار باشند، در هر دور سرويس GPS به هر ارتباط غير خالي متناسب با وزنش سرويس داده مي شود. گسترش بحث فوق نشان مي دهد كه GPS مي تواند روشي براي دستيابي به تقسيم عادلانه وزن دار حداكثر-حداقل باشد.
شكل2-4: سرويس دهنده GPS
2-3-4 روش صف بندي Round Robin
ساده ترين مشابه سازي از GPS روش round-robin است كه در آن به جاي يك مقدار بي نهايت كوچك، يك بسته از هر ارتباط انباشته1 سرويس مي گيرد.
در اين روش بصورت دوراني از هر صف يك بسته برداشته مي شود و اين عمل بطور پيوسته تا اتمام
بسته ها تداوم مي يابد. پيچيدگي اين الگوريتم از مرتبه O(1) مي باشد و در صورتي كه مطابق شكل(2-5) بسته هاي موجود در صف ها داراي طول مساوي باشند. تأخير حداكثر يك صف عبارت است از:
(2-2)
كه در آن N تعداد صف ها يا جريان ها و P بزرگترين اندازه بسته مورد سرويس دهي و r نرخ بيتي است كه سرويس دهنده بر اساس آن سرويس دهي مي كند.
يكي از معايب روش Round robin اين است كه در شبكه هاي Packet Switched كه طول بسته ها متفاوت است سرويس دهي به بسته ها بطور عادلانه صورت نمي گيرد و بيشتر پهناي باند صرف سرويس دهي به صف هاي با بسته هاي با طول بزرگتر مي شود.
شكل2-5: برقراري عدالت بين بسته هاي ورودي در حالتي كه بسته ها طول مساوي دارند[45]
2-3-5 روش Bitwise Round Robin
اگر بر خلاف روش Round robin، واحد تخليه شده از صف به جاي بسته، بيت در نظر گرفته شود، به هر جريان مستقل از اندازه بسته ها 1/N ظرفيت اختصاص پيدا مي كند و اين همان ايده روش Bitwise Round Robin مي باشد.
اگر چه سرويس دهي به يك بيت از هر ارتباط در عمل ناممكن بنظر مي رسد ولي Keshav، Demres و Shenker در [37] تقريبي عملي براي پياده سازي اين الگوريتم ارائه كرده اندكه اساس روش صف بندي عادلانه ارائه شده در قسمت بعد مي باشد.
2-3-6 روش عملي صف بندي عادلانه Bitwise Round Robin
در اين روش، به هر بسته يك ”زمان اتمام“ نسبت داده مي شود كه در واقع زماني است كه بسته بطور كامل به روش Bitwise Round Robin بطور تئوري سرويس دهي مي شود سپس بسته ها بر اساس زمان اتمام خود در يك ليست مرتب مي گردند و بر اساس ترتيب، از ليست سرويس دهي مي شوند
)شكل(2-6)(.
شكل2-6: سرويس دهي به بسته هاي با طول نامساوي [45]
بعلت نياز به ليست براي مرتب كردن بسته ها پيچيدگي محاسباتي اين روش از مرتبه O(log(N))
مي باشد و بنابراين اين الگوريتم را مي توان در سوئيچ هاي سريع مورد استفاده قرار داد.
2-3-7 روش WRR
در اين روش نيز بصورت دوراني از هر صف يك بسته برداشته مي شود و اين عمل بطور پيوسته تا اتمام بسته ها تداوم مي يابد. همانگونه كه قبلاً بيان شد، ساده ترين مشابه سازي از GPS روش round-robin است كه در آن به جاي يك مقدار بي نهايت كوچك، يك بسته از هر ارتباط انباشته سرويس مي گيرد.
اگر ارتباط ها داراي وزن باشند از روش WRR كه متناسب با وزن ارتباط به آن سرويس مي دهد استفاده مي شود. دو روش RR و WRR زماني GPS را خوب تقريب مي زنند كه طول بسته ها ثابت باشد. اگر طول بسته ها ثابت نباشد سرويس دهندة WRR وزن هر ارتباط را به متوسط طول بسته هاي آن ارتباط تقسيم مي كند تا وزنهاي نرماليزه شده بدست آيند.
بنابراين WRR نياز دارد كه متوسط طول بسته هاي ارسالي از هر ارتباط را از قبل بداند اما در عمل طول بسته هاي ارسالي از منبع مي تواند كاملاً متغير باشد.
مشكل ديگر اين است كه WRR فقط در بازه هاي زماني طولاني تر از زمان يك دور سرويس مي تواند پهناي باند را عادلانه تقسيم كند. در بازه هاي كوچك زمان، بعضي از ارتباط ها ممكن است بيشتر از
ارتباط هاي ديگر سرويس بگيرند.
اگر يك ارتباط وزن كمي داشته باشد يا تعداد ارتباط ها زياد باشد عدم رعايت عدالت به بازه هاي زماني بزرگتر هم كشيده مي شود. روش WRR معمولاً در شبكه هاي با سرعت زياد ATM كه طول بسته ها ثابت است، به طورنسبتاً خوبي روش GPS را تقريب مي زند[39].
2-3-8 روش Deficit Round Robin (DRR)
روش DRR كه نخستين بار توسط Shreedhar و Varghese معرفي گرديد [40] همان ويژگي هاي روش صف بندي عادلانه را با پيچيدگي از مرتبه O(1) دارا مي باشد. اين الگوريتم در واقع تصحيح شدة الگوريتم WRR مي باشد و مي تواند بسته هاي با طول متغير را بدون نياز به دانستن متوسط طول بسته، سرويس دهد. در روش DRR سرويس دهي بصورت Round Robin انجام مي شود بدينصورت كه در هر دور يك مقدار كوانتم در هر صف به وديعه گذاشته مي شود و هنگامي كه مجموع اين كوانتم ها بزرگتر يا مساوي با اندازه بسته شود آن بسته ارسال مي شود. در مدل DRR وزن دار، سرويس دهنده به مقدار حاصلضرب وزن ارتباط در مقدار كوانتم بيت از هر ارتباط را سرويس مي دهد. مهمترين ويژگي DRR سادگي پياده سازي آن است. در مقابل نقطة ضعف اصلي آن مانند WRR آن است كه روي بازه هاي زماني كوچكتر از يك دور گردش كه معادل بيشترين زماني است كه سرويس دهنده ارتباطي را با در نظر گرفتن وزن آن سرويس دهي كند، عدالت را رعايت نمي كند. لازم به توضيح است كه DRR در شبكة با طول بستة ثابت به WRR مبدل مي گردد.
2-3-9 روش بهبود يافته DRR (DRR+)
اين روش نيز توسط Shreedhar و Varghese ارائه شد و در واقع هدف از ارائه آن ايجاد كران تأخير قابل قبول براي ترافيك هاي بلادرنگ است. در روش DRR+ از دو كلاس براي سرويس دهي به ترافيك ها استفاده مي شود. براي ترافيك هاي بلادرنگ از يك كلاس با اولويت بالا استفاده مي شود كه ارتباط هاي موجود در آن بصورت روش عملي صف بندي عادلانه Bitwise Round Robin سرويس دهي مي شوند و ترافيك هاي غير حساس به تأخير در يك كلاس با اولويت پائينتر با روش DRR سرويس دهي مي شوند.
2-3-10 روش صف بندي عادلانه وزن دهي شده (WFQ)
در بسياري از كاربردها مايل هستيم كه ظرفيت موجود بصورت نامساوي بين جريانها تقسيم شود مثلاً هنگامي كه يك ترافيك از نوع بلادرنگ به همراهي با يك ترافيك ديتا مورد سرويس دهي قرار مي گيرند ترافيك بلادرنگ پهناي باند كمتري را نياز خواهد داشت ولي در عين حال، كران هاي پائينتر و مطمئن تري را از نظر تأخير نياز خواهد داشت. در اينگونه موارد از وزن خاصي براي هر صف استفاده مي شود و مقدار پهناي باند اختصاص يافته به هر ارتباط بر اساس اين وزن تعيين خواهند شد و اين اساس روش WFQ را تشكيل مي دهد. در عمل، اين وزن ها براي هرارتباط1 تعيين نمي شوند بلكه به مجموعه اي از ارتباط ها بصورت تلفيقي2 ، يك صف و با يك وزن خاص تخصيص مي يابد.
در روش WFQ بسته ها به نسبت زمان اتمامي كه بطور تئوري در روش GPS متناظر دارند، سرويس دهي مي شوند.
2-3-11 روش WF2Q 3
اختلاف بين سرويس دهندة GPS و يك سرويس دهندة عملي بسته اي در آن است كه در هر لحظة زمان در سرويس دهندة GPS چندين بسته از اتصالات مختلف مي توانند سرويس بگيرند در حالي كه در سيستم بسته اي فقط يك بسته مي تواند سرويس بگيرد.
در حالي كه زمان سرويس يك بسته با طول L بيت در سيستم بسته اي با نرخ سرويس r بيت در ثانيه برابر L/r ثانيه است اين مقدار در GPS مي تواند بسيار بيش از اين باشد. بنابراين با اينكه ممكن است سرويس يك بسته در سيستم بسته اي ديرتر از GPS شروع شود، مي تواند زودتر از GPS به پايان برسد چرا كه در زمان سرويس كل پهناي باند را در اختيار دارد.
حال اگر بستة دوم در الگوريتم بسته اي شروع به دريافت سرويس كند در حالي كه هنوز سرويس آن در GPS شروع نشده است اين اختلاف مي تواند زيادتر هم شود. البته در بازة زماني طولاني مقدار سرويسي كه يك ارتباط دريافت مي كند تحت هر دو نوع سرويس دهنده يكسان خواهد بود و ارتباطي كه در سيستم بسته اي زودتر سرويس گرفته در بازه هاي زماني بعدي نسبت به GPS ديرتر سرويس خواهد گرفت.
براي به حداقل رساندن اختلاف فوق و كاهش هجوم1 ترافيك ايجاد شده، الگوريتم تصحيح شدة WFQ به نام WF2Q معرفي مي گردد.
در WF2Q براي انتخاب بستة بعدي جهت سرويس، به جاي انتخاب از بين تمام بسته هاي موجود، انتخاب از بين مجموعة بسته هائي كه سرويسشان در GPS متناظر شروع و يا احتمالاً تمام شده است صورت مي گيرد و از آن ميان، بسته اي كه زودتر از همه سرويسش تمام مي شود انتخاب خواهد شد.
2-3-12 روش هاي Delay-EDD و Jitter-EDD
در روش كلاسيك EDD2 بر اساس حداكثر ميزان مجاز تأخير، به هر بسته يك زمان انقضاء نسبت داده مي شود و سرويس دهنده، بسته ها را بترتيب اين زمان ها سرويس مي دهد. در اين روش، بسته هائي كه زمان انقضايشان نزديكتر است زودتر سرويس مي گيرند. D-EDD گسترش يافتة EDD است و در آن روشي براي محاسبة زمان انقضاي بسته ها ارائه شده است [41]. در زمان ايجاد يك ارتباط، بين منبع و سرويس دهنده قراردادي وضع مي شود مبني بر آنكه مادامي كه منبع در ارسال ترافيك ازحداكثر نرخ تعريف شده تجاوز نكرده است، تأخير بسته هايش از مرز مشخصي كمتر خواهد بود.
براي اينكه اجازة برقراري ارتباط صادر شود سرويس دهنده نه تنها بايد مطمئن باشد كه مجموع نرخهاي حداكثر ارتباط ها از ظرفيت خط تجاوز نمي كند بلكه بايد در نظر بگيرد كه در بدترين حالت زماني كه همگي ارتباطها با حداكثر نرخ خود ارسال مي كنند تأخير هيچكدام از مرز تعريف شده تجاوز نكند.[41]
در D-EDD متناظر با حداكثر نرخ ارسال يك ارتباط پهناي باند برايش ذخيره مي گردد. اين امر باعث اتلاف پهناي باند و كاهش ميزان مالتي پلكس آماري مي شود ولي در عوض همواره كران تأخير بسته ها
حتي در بدترين حالت (ارسال با نرخ حداكثر) حفظ مي شود. بايد توجه داشت كه الگوريتم هاي مشابه WFQ پهناي باند را متناسب با متوسط نرخ هر ارتباط ذخيره مي كنند.
در J-EDD يك تنظيم كنندة نوسان تأخير قبل از بلوك EDD قرار مي گيرد. بدين ترتيب در اين روش سرويس علاوه بر پهناي باند و تأخير، ميزان نوسانات تأخير هم در كل شبكه براي يك ارتباط تضمين مي شود. در اينجا نيز پهناي باندي معادل با حداكثر نرخ ارتباط براي آن ذخيره مي شود [42].
5-Fair Queuing 6-Weighted Fair Queueing
7- Weighted Round Robin 8-First In First Out
9-General Processor Sharing 10-Aggressive
1-First Come First Served 2-Starvation
1-Per-connection 2-Aggregate
1-Burst 2- Earliest Due Date