ردن نقائص فوق الذکر و ضمن برقراری عدالت تناسبی (?,?) به روشهای تخصیص نرخ با سرعت های همگرائی بالاتر دست می یابیم و ضمناً به بررسی ریاضی پایداری الگوریتمهای مطرح شده می پردازیم.
الگوریتمهای سلسله مراتبی، بر اساس لینکهای گلوگاه6 موجود، شبکه را به دو سطح سلسله مراتب افراز می کنند. اینگونه الگوریتمها کاربرهای شبکه را بر اساس عبور دسته های کاربرها بطور مشترک از لینکهای گلوگاه به کاربرهای مجازی تفکیک می کنند. سپس عمل تخصیص نرخ به این کاربرهای مجازی بصورت مشترک و توسط گره های مرزی موجود در مرز میان دو سطح سلسله مراتب، انجام می پذیرد.

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

1-3 ترتیب ارائه مطالب

در فصل دوم مفهوم کیفیت سرویس در شبکه های داده و روشهای مختلف زمانبندی مورد بررسی قرار خواهند گرفت. در فصل سوم به مسئله کنترل نرخ و روشهای دستیابی به آن در شبکه های داده
می پردازیم و معیار های مختلف برای برقراری عدالت در تخصیص نرخ به کاربرها در این فصل بررسی خواهند شد. در فصل چهارم ضمن مرور نتایج کارهای انجام شده قبلی، بیان شده است که مسئله تخصیص نرخ عادلانه و بهینه به کاربرهای شبکه را می توان به یک مسئله بهینه سازی عمومی مقید بر اساس محدودیت های مربوط به منابع شبکه تبدیل کرد. فصل پنجم به بررسی روشهای کلی برای حل مسائل بهینه سازی محدب مقید اختصاص یافته است که از این میان می توان به روشهای تصویر گرادیان1، تصویر جاکوبی2، لاگرانژ و … اشاره کرد[15]. در فصل ششم به ارائه و پیشنهاد چند الگوریتم تخصیص نرخ به کاربرهای سطح شبکه می پردازیم. این الگوریتم ها در نهایت به نقطه بهینه پاسخ همگرا می شوند. در این بخش، به بیان ریاضی مسئله پایداری الگوریتم های تخصیص نرخ خواهیم پرداخت.
همچنین، در فصل ششم مسئله ورود و خروج کاربرها به شبکه (با در نظر گرفتن توزیع های مشخص برای فرایند ورود و خروج) بررسی می شود.
در فصل هفتم با انجام شبیه سازی کامپیوتری بر روی چند توپولوژی دلخواه شبکه به بررسی نحوه عملکرد الگوریتم های مطرح شده در فصل پنجم و مقایسه نتایج حاصل با الگوریتمهای متعارف می پردازیم.
در خاتمه، در فصل هشتم ضمن مرور بر نتایج حاصله از این تحقیق به بیان راهکارهائی جهت ادامه آن خواهیم پرداخت.
فصل دوم
بررسی مفهوم کیفیت سرویس در شبکه های داده
2-1 مقدمه
بر اساس یک تعریف، مفهوم کیفیت سرویس در شبکه های کامپیوتری عبارتست از ” قابلیت کنترل مکانیسم های برخورد با ترافیک شبکه بقسمی که نیازمندی های سرویسها و کاربرهای مشخص، بر طبق سیاستهای شبکه تأمین گردد ” [45] .
نیازمندی های سرویس شامل پهنای باند مورد نیاز، تأخیر، تغییرات تأخیر و اتلاف1 قابل قبول سرویس می باشد. در یک شبکه با یک مجموعه از مکانیسم های QoS مفروض، یک موازنه بین Q وE وجود دارد. بعبارت دیگر، با افزایش هرکدام از این کمیتها، دیگری کاهش می یابد (شکل 2-1)).
شبکه ها ممکن است در نقاط مختلفی از این منحنی به کار گرفته شوند. مثلاً اغلب LAN های موجود در شبکه Microsoft قادر به ارائه کیفیت مناسب برای سرویس IP telephony هستند و بنابراین در نقطه P1 به کار گرفته شده اند.
برعکس، اغلب لینک های WAN بین المللی بعلت مسائل مربوط به هزینه از نظر کارآمدی مورد توجه قرار دارند و کیفیت مناسبی را برای سرویس IP telephony دارا نمی باشند و عملاً در نقطه P2 به کار گرفته شده اند [45] و باید توجه داشت که همانگونه که ذکر شد اغلب LAN هائی که با تمهیدات زیاد3
در نقطه P1 به کار گرفته شده اند از نظر کارآمدی وضعیتی نامناسب را دارا هستند. هدف کلی از ارائه مکانیسم های مختلف QoS افزایش کارآمدی مرتبط با یک شبکه خاص می باشد و هرچه مکانیسم کارآمدتر باشد عملکرد بهتری را برای شبکه بدست خواهد داد مطابق با شکل (2-2).

شکل 2-1: یک منحنی نوعی بیان کننده رابطه بین کیفیت و کارآمدی[45]

شکل2-2: تاثیر پیچیدگی مکانیسم QoS بر عملکرد شبکه[45]

2-2 مکانیسم های موجود در شبکه برای ایجاد QoS
بعضی از مکانیسم های بکار رفته برای برقراری QoS در شبکه ها به قرار زیر می باشند[45]:

* انواع مکانیسم های صف بندی1
* سرویس های مجتمع
* سیگنالینگ RSVP
* سرویس های تفکیک شده
* مدیریت پهنای باند زیر شبکه2 برای شبکه های 802
*
* QoS در لایه 2 بغیر از شبکه های 802 (…,ISSLOW1,ATM)

مکانیسم های صف بندی بکاررفته در شبکه ها به دو دسته عمومی کار مداوم2 و کار غیر مداوم3 تقسیم
می شوند.

2-3 روش های صف بندی با کار مداوم
در این نوع صف بندی تا زمانی که بسته ای برای ارسال وجود داشته باشد، پهنای باند تخصیص می یابد و یا بعبارت دیگر، پهنای باند، بلا استفاده نخواهد ماند.
در شکل(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
در حالت ایده آل، در این روش برای هر ارتباط یک صف جداگان