Skip to main content
SUPERVISOR
Hossein Saidi,MasoudReza Hashemi
حسین سعیدی (استاد راهنما) مسعودرضا هاشمی (استاد مشاور)
 
STUDENT
Hassan Halabian
حسن حلبیان

FACULTY - DEPARTMENT

دانشکده مهندسی برق و کامپیوتر
DEGREE
Master of Science (MSc)
YEAR
1384
With the advent of packet based networks and new applications in such networks, efficient use of network resources, congestion control and fair allocation of bandwidth become very important. Traffic scheduling algorithms provide a mean to reach these goals. Such algorithms determine the service order of packets of different sessions which are sharing an outgoing link. Two main objectives in designing scheduling algorithms are to reach fairness in bandwidth allocation and to reduce the worst case delay of packets. In addition, time complexity of the algorithms is also a very important factor, especially in broadband networks. The service time of a packet is very short in these networks and the algorithm must complete its run in such a short period. Hence, designing low complexity algorithms with desirable fairness properties and limited worst case delay of packets is the goal. This thesis tries to categorize different scheduling algorithms and study the properties of each category. Sorted-priority based scheduling algorithms as a main and important class of traffic scheduling algorithms is concentrated on and algorithms of this category are studied and compared in terms of time complexity, fairness and delay. Golestani's fairness index is used to compare their fairness properties and LR-servers theory is invoked to compare worst case delay of packets in these algorithms. Two main approaches are introduced to improve current algorithms; one is based on achieving lower fairness index and the other is based on reaching lower worst cast delay for packets. According to these approaches, two algorithms called LVT-SCFQ and FPFQ are introduced and their performances are evaluated in terms of fairness, delay and complexity.
با ظهور شبکه های مبتنی بر بسته و کاربرد های جدید و متنوع در این شبکه ها، استفاده مناسب و بهینه از منابع شبکه، کنترل ازدحام و تسهیم عادلانه پهنای باند در این شبکه ها از اهمیت زیادی برخوردار شده است. الگوریتم های زمان بندی ترافیک از ابزارهای اصلی، جهت نیل به اهداف فوق هستند. این الگوریتم ها، تعیین کننده ترتیب ورود بسته های محاوره های ورودی مختلف به یک لینک خروجی است. دو هدف اصلی در طراحی این الگوریتم ها، رسیدن به عدالت مناسب در تسهیم پهنای باند لینک خروجی و حداکثر تأخیر محدود برای بسته هاست. در شبکه های باند وسیع، پیچیدگی زمانی الگوریتم نیز از اهمیت زیادی برخوردار خواهد شد. در حقیقت، در این شبکه ها زمان ارسال بسته ها بسیار کوچک است و الگوریتم می بایست در این زمان کوچک به طور کامل اجرا شود. بنابراین، طراحی الگوریتم هایی ساده با عدالت رفتار مناسب و حداکثر تأخیر هر چه محدودتر، از مهمترین اهداف پیش روست. این پایان نامه، تلاش کرده است الگوریتم های زمان بندی ترافیک را به نحو مناسبی دسته بندی نماید و ویژگی های منحصر بفرد هر دسته را مورد بررسی قرار دهد. الگوریتم های مبتنی بر اولویت مرتب شده به عنوان دسته ای مهم و اساسی از الگوریتم های زمان بندی ترافیک مورد توجه این پایان نامه قرار خواهند گرفت و الگوریتم های مهم و اصلی این دسته از سه جنبه پیچیدگی زمانی الگوریتم، تأخیر و عدالت به طور دقیق بررسی خواهند شد. معیار عدالت گلستانی به عنوان معیار مقایسه از نظر عدالت رفتار و تئوری سرورهای LR به عنوان ابزار اصلی مقایسه از نظر حداکثر تأخیر استفاده خواهند شد. دو جهت گیری کلی در طراحی این الگوریتم ها و بهبود رفتار آنها، یکی براساس طراحی بر مبنای رسیدن به معیار عدالت کوچکتر و دیگری بر مبنای رسیدن به رفتار تأخیر مناسب تر مطرح می شوند. بر این اساس، دو الگوریتم LVT-SCFQ و FPFQ معرفی خواهند شد و رفتار آنها از سه دیدگاه مطرح شده، مورد بررسی قرار خواهند گرفت.

تحت نظارت وف ایرانی