SUPERVISOR
Mehdi Mahdavi
مهدی مهدوی (استاد راهنما)
STUDENT
Mohammad Darvishan
محمد درویشان
FACULTY - DEPARTMENT
دانشکده مهندسی برق و کامپیوتر
DEGREE
Master of Science (MSc)
YEAR
1388
TITLE
A New Algorithm for Load Balancing in Metro Ethernet using Multiple Spanning Tree Protocol
The flexibility, simplicity, high speed and low cost of ethernet technology along with increasing use of this technology in local area networks, makes ethernet an ideal technology for use in metro networks. But according to the fact that ethernet is primarily designed for small local area networks, there are some challenges in the way of expanding ethernet to large networks such as metro network. Load balancing in the network is one of the main challenges ahead in metro ethernet networks. Due to the large size of the metro ethernet networks and large number of users in these networks and also providing various services with high bandwidth, it is a critical issue how to utilize all the capacity of the network. Thus, traffic engineering is a major subject in such networks in order for the better management of network resources. Spanning tree protocol is used in the ethernet local area networks to prevent making loops in the network. In spanning tree protocol, all the network subscribers use a common single spanning tree. Thus, due to large number of users in metro ethernet network, spanning tree protocol do not use network resources in an optimal manner and has no capability to implement traffic engineering in metro ethernet network. Using multiple spanning tree protocol is a good solution to implement traffic engineering methods in metro ethernet networks. Multiple spanning tree protocol allows building several trees in the network leading to better load distribution in the network and prevents from overloading in the links. The suggested algorithm in this thesis makes use of multiple spanning trees. This algorithm makes use of dynamic link weights to create multiple instances of spanning trees in the network. In order to update the weights of network links, the suggested algorithm uses an exponential relationship. In this exponential relationship, there is an inverse exponential relationship between weights of the links and traffic of the links. The suggested algorithm creates one instance of the spanning tree for each vlan and in order to obtain optimal spanning tree for vlan, there is a mechanism that uses feedback in creating spanning tree for vlan. In this mechanism if constructing spanning tree and assigning traffic to it leads to overloading in the links, the proposed algorithm first assigns proper weights to the links and then reconstructs a new spanning tree for that vlan. This procedure is repeated until obtaining the appropriate tree. Selecting root node of the tree is another important part of creating the spanning tree. In the suggested algorithm, a node with the highest sum of incoming and outgoing traffic is selected as the root node of each tree. This is because of all ports of the root node can be in the activate mode. Therefore the algorithm distributes traffic in a better way and prevents saturation in the links near the root node. Comparing the results of the algorithm simulation demonstrates that there is a proper use of network links. These results show that suggested algorithm prevents overloading in the network and provides more uniform traffic distribution. Also the average load on the links is good. Keywords: Metro Ethernet, Traffic Engineering, Multiple Spanning Tree, Load Balancing
انعطاف¬پذیری، سرعت زیاد، سادگی و ارزان¬قیمت بودن تکنولوژی اترنت در کنار افزایش روز¬افزون استفاده از این تکنولوژی در شبکه¬های محلی، اترنت را به عنوان یک تکنولوژی عالی برای استفاده در شبکه¬های مترو مطرح کرده است. اما با توجه به اینکه اترنت مخصوص شبکه¬های کوچک محلی طراحی شده است، گسترش آن به شبکه¬های بزرگ مترو با چالش¬هایی همراه می¬باشد. یکی از چالش¬های پیش رو در شبکه¬های مترو¬اترنت، ایجاد تعادل بار در شبکه می¬باشد. در شبکه¬های مترو¬اترنت با توجه به بزرگی شبکه و تعداد بسیار زیاد کاربران شبکه و همچنین ارائه سرویس¬های متنوع و با پهنای باند بالا، چگونگی استفاده از تمام ظرفیت شبکه مسئله¬ای حیاتی می¬باشد. در نتیجه در شبکه¬های مترو¬اترنت جهت مدیریت بهتر منابع شبکه، موضوع مهندسی ترافیک به عنوان یکی از موضوعات مهم مورد توجه در این نوع شبکه¬ها واقع شده است. در شبکه¬های محلی اترنت از پروتکل درخت پوشا جهت جلوگیری از ایجاد حلقه در شبکه استفاده می¬شود. در پروتکل درخت پوشا تمام کاربران شبکه از یک درخت پوشای مشترک استفاده می¬کنند. بنابراین با توجه به تعداد زیاد کاربران در شبکه مترو¬اترنت، پروتکل درخت پوشا استفاده بهینه¬ای از منابع شبکه را به دست نداده و توانایی پیاده¬سازی مهندسی ترافیک در شبکه مترو¬اترنت را ندارد. یک راه¬کار مناسب استفاده از پروتکل درخت پوشای چندگانه می¬باشد. پروتکل درخت پوشای چندگانه اجازه ساخت چندین درخت را برای شبکه می¬دهد که می¬توان از طریق اعمال راه¬کار¬های مهندسی ترافیک در این پروتکل، ساخت درخت¬های پوشا را به نحوی انجام داد که استفاده از منابع شبکه بهینه شده و تعادل بار در لینک¬های شبکه به¬وجود آید. در این پایان¬نامه روشی برای پیاده¬سازی مهندسی ترافیک در شبکه مترو¬اترنت با استفاده از درخت¬های پوشای چندگانه ارائه می¬شود. این روش توزیع بار بهتری را در لینک¬های شبکه موجب شده و از ایجاد اضافه¬باری در لینک¬های شبکه جلوگیری می¬کند. الگوریتم ارائه شده، برای ساخت درخت¬های پوشای چندگانه، از هزینه لینک پویا استفاده می¬کند. در این الگوریتم از یک رابطه نمایی برای به¬روز کردن هزینه لینک استفاده می¬شود. در این رابطه نمایی، هزینه لینک رابطه نمایی معکوس با ترافیک لینک دارد. همچنین در الگوریتم پیشنهادی از یک راه¬کار فیدبک برای یافتن درخت پوشای بهینه استفاده می¬ شود. در این راه¬کار در صورتی که بر اثر ساخت درخت در شبکه و اعمال ترافیک به آن، لینکی دچار اضافه¬باری شده باشد، الگوریتم با اختصاص وزن¬ مناسب به لینک¬ها، ساخت درخت را مجددا انجام می¬دهد. این رویه تا به دست آمدن درخت مناسب تکرار می¬شود. انتخاب گره ریشه یکی دیگر از بخش¬های مهم ساخت درخت پوشا می¬باشد. در الگوریتم ارائه شده گره¬ای با بیشترین مجموع ترافیک ورودی و خروجی به عنوان گره ریشه هر درخت انتخاب می¬شود. زیرا می¬توان تمام پورت¬های گره ریشه را در حالت فعال قرار داد تا بدین وسیله از اشباع لینک¬های گره ریشه جلوگیری کرده و همچنین توزیع مناسب¬تری برای ترافیک¬ها به دست آید. مقایسه نتایج حاصل از شبیه¬سازی الگوریتم، نشان¬دهنده استفاده مناسب از تمام لینک¬های شبکه می¬باشد. این نتایج نشان می دهند که در الگوریتم پیشنهادی به خوبی از ایجاد اضافه¬باری در لینک¬های شبکه جلوگیری شده است، توزیع بار در لینک¬ها یکنواخت¬تر بوده و همچنین میانگین بار روی لینک¬های شبکه مناسب می¬باشد. کلمات کلیدی: 1- مترو¬اترنت 2- مهندسی ترافیک 3- درخت پوشای چندگانه 4- تعادل بار