طراحی الگوریتم های جدید مسیر یابی مبتنی بر کیفیت سرویس برای مهندسی ترافیک شبکه های MPLS

STUDENT

DEGREE

YEAR

The rapid growth and scope of multimedia applications has caused a tremendous impact on the way people communicate. The mission of next generation networks (NGN) is facilitating multimedia applications creation and deployment as well as supporting interoperability and network convergence. A key technology, IP Multimedia Subsystem (IMS) is the definitive means of achieving such goals. IMS has been proposed to support newly emerged multimedia IP based applications such as voice over IP (VOIP), video on-demand (VOD), IPTV and etc using a core IP backbone. Clearly, such applications cause huge amount of traffic load and require specified QoS constrains. It is worth pointing out that IP protocol only provides best effort service and use destination based routing which causes packets to reach their destination through different paths. Since multimedia applications require specified QoS constrains, IP cannot guarantee the reception of packets in order which is essential for the real-time applications. In this way traffic engineering (TE) is a technique which has been used to guarantee the QoS as well as optimal use of infrastructure networks. In order to implement TE, multiprotocol label switching (MPLS) is the useful solution among other existing techniques. This is because MPLS packets belong to a traffic source are routed through a same path which is essential for TE implementation. In addition to this, MPLS is one of the crucial protocols which have important rules in IMS. The major technical challenge in TE is the paths selection in which both QoS constraints and best possible resources utilization are satisfied. One of the key issues in providing QoS guarantees is the paths selection where both QoS constraints and best possible resources utilization are satisfied. The problem of finding such paths is known as QoS routing and is NP-complete problem in general. Such problems can be solved using heuristic algorithm in polynomial time. Although much work has been done on laying MPLS paths to optimize performance, most has focused on satisfying bandwidth requirements. Relatively little research has been done on QoS routing where QoS constraints is both bandwidth and delay. In this thesis we explain QoS based routing along with MPLS and TE requirements. We first propose a new Bandwidth Guarantee with Low Complexity (BGLC) algorithm. Our simulation results are compared with previously published algorithms which are known as MHA, WSP, MIRA and BCRA. The simulation results reveal that BGLC presents lower rejection rate compare to the rejection rate of MHA, WSP, MIRA and BCRA. Furthermore the computational time of BGLC is much smaller than those belong to WSP, MIRA and BCRA and is close to the computational time of MHA which itself presents the lowest computational time. The aforementioned algorithms Key words Quality of Service, Traffic Engineering, MPLS, QoS-based routing

ظهور کاربردهای جدید و بلادرنگ در شبکه های ارتباطی و رشد سریع شبکه های مبتنی بر IP، باعث پیدایش بحث جدید یکپارچه کردن شبکه ها با عنوان سیستم های چندرسانه ایIP (IMS) که خود توسعه ای نوین بر مفهوم شبکه های نسل جدید(NGN) می باشد، گردیده است. همانگونه که انتظار می رود این گونه کاربردها باعث رشد سریع حجم ترافیک در شبکه شده است. کاربردهای چندرسانه ای نظیر تلفن اینترنتی، ویدئوکنفرانس، جراحی از راه دور و غیره نیازمند برآورده شدن کیفیت سرویس مطلوب می باشند. رشد سریع ترافیک و نوع های متفاوت ترافیک، شرکت های ارائه کننده خدمات شبکه را بر آن داشته که با استفاده بهینه از زیرساخت های موجود، علاوه برآورده کردن کیفیت سرویس درخواستی و رضایت مشتریان، درآمد بیشتری نیز کسب کنند. از طرفی با توجه به ماهیت پروتکل IP که برمبنای بیشترین تلاش استوار است، مسیریابی براساس آدرس مقصد انجام می شود. بسته ها مسیرهای متفاوتی را جهت رسیدن به مقصد می پیمایند و هیچ گونه تضمینی در رسیدن بسته ها به مقصد وجود ندارد. مهندسی ترافیک یکی از ابزارهای است که این شرکت ها از آن بهره گرفته hy;اند تا نیازمندی های کیفیت سرویس و استفاده بهینه از شبکه را برآورده نمایند. از میان را حل های گوناگون مهندسی ترافیک فن آوری جابجایی برچسب چندپروتکلی (MPLS) بعنوان مؤثرترین راه حل شناخته می شود. این فن آوری با بهره گیری از مسیرهای برچسبی صریح امکان استفاده از مهندسی ترافیک را به بهترین شکل ممکن میسر می سازد. هم اکنون نیز MPLS بعنوان یکی از پروتکل های اصلی در IMS شناخته شده است. از آنجا که مسیر عبور بسته ها در شبکه های MPLS مشخص است لذا می توان روی این مسیرها مهندسی ترافیک انجام داد و نیازمندی های کیفیت سرویس را برآورده کرد. یکی از مهمترین چالش های مهندسی ترافیک در شبکه های MPLS، مسیریابی مسیرهای برچسبی است، بگونه ای که علاوه بر برآورده کردن معیارهای موردنیاز برای کیفیت سرویس از امکانات شبکه نیز استفاده بهینه شود. ارائه چنین الگوریتم های از دسته الگوریتم های NP-complete است. برای حل این دسته از مسائل الگوریتم های ابتکاری ارائه شده است. مهمترین معیار کیفیت سرویسی که در تحقیقات گذشته مد نظر قرار گرفته است پهنای باند می باشد. در این پایان نامه ابتدا به بررسی مسیریابی مبتنی کیفیت سرویس و MPLS و نیازمندی های مهندسی ترافیک پرداخته می شود. سپس یک الگوریتم مسیریابی نوین به نام BGLC که پهنای باند را با کمترین مقدار پیچیدگی برآورده می کند، ارائه می گردد. نتایج حاصل از شبیه سازهای انجام شده در این پایان نامه بهبود چشمگیری را در مقایسه با الگوریتم های موجود نشان می دهد. در الگوریتم هایی که قید پهنای باند را برآورده می کنند به تأخیر انتها به انتها توجه نشده است. در این پایان نامه همچنین الگوریتم مسیریابی جدیدی با عنوان BGDG ارائه می گردد که علاوه بر تضمین پهنای باند، حداکثر تأخیر انتها به انتها را نیز تضمین می کند. نتایج شبیه سازی این الگوریتم با توجه به این که کلمات کلیدی: کیفیت سرویس، مهندسی ترافیک، MPLS، مسیریابی مبتنی بر کیفیت سرویس