ارائه ي يك الگوريتم مسيريابي كيفيت خدمات چند بخشي مقياس پذير

چكيده انگليسي :

A Scalable Quality of Service Multicast Routing Algorithm Fatemeh Farhadian f farhadian@ec iut ac ir Date of Submission 2012 02 22 Department of Electrical and Computer Engineering Isfahan University of Technology Isfahan 84156 83111 Iran Degree M Sc Language FarsiSupervisor Mehdi Mahdavi m mahdavi@cc iut ac irAbstractThe rapid evolution of real time multimedia applications requires the multicast routing in underlyingcommunication networks Multicast aims at sending information from one or more sources to a set ofdestinations in the network A multicast tree is the required solution for the multicast routing problem On the other hand the multimedia applications including video conferencing interactive distributedgames and video and audio on demand have a wide diversity of Quality of Service QoS requirementsfor traffic including the cost bandwidth end to end delay delay jitter packet loss ratio and hopcount and etc So the real time multimedia applications have been stimulating the demand for QoSbased multicast routing in the computer communication networks QoS multicast routing is animportant technique to support data transmission in computer networks Solution to the QoS multicastrouting problem is to build a multicast tree which spans from the source node to all destinations andsatisfies certain QoS requirements The main goals of QoS multicast routing are to efficiently allocatenetwork resources and provide adequate QoS guarantees for end users of multimedia applications Onthe other word given a network a source node and a set of destinations the problem of routing on amulticast network can be quantified using several objectives or metrics such as delay minimization congestion minimization and cost minimization A common objective is simply to minimize the costsassociated with the connections used to route packets that is minimizing the total cost of the routingtree The resulting problem is known as minimum cost multicast routing In this case the optimizationgoal can be proved to be equivalent to the minimum Steiner tree a classical NP Complete problem Each link cost is normally defined as the bandwidth utilization or network resource cost on the link Thus minimizing the cost means minimizing the link utilization which is one of the main goals oftraffic engineering Furthermore most real world applications of multicast routing problems are delay sensitive for data delivery bandwidth intensive and have another several QoS constraints Theunderpinning mathematical structure of the QoS multicast routing problem is the constrained SteinerTree problem which is a well known NP complete problem In the set of NP Complete Problem thetime required to solve the problem using any currently known algorithm increases very quickly as thesize of the problem grows As a result the time required to solve even moderately sized versions ofmany of these problems easily reaches into the billions or trillions of years using any amount ofcomputing power available today Thus scalability issue is being emerged An algorithm is said toscale if it is practical when applied to a large input data set i e we should be able to obtain appropriateand suboptimal answer in an acceptable time even with large size of the problem Most of theproposed algorithms for Steiner tree and constrained Steiner tree problems use heuristic and meta heuristic approaches In this thesis first we discuss about basic and main concepts of multicastrouting and then study some of previous QoS Multicast routing algorithms We suggest a multicastrouting algorithm to establish a least cost tree with four constraints bandwidth constraint in all thelinks of the tree end to end delay loss ratio constraint from the source node to each of thedestinations and delay jitter constraint of the tree It applies ant colony algorithm in order to generatea multicast tree Furthermore our purpose is to improve the scalability Simulation results show thatour algorithm performs well in creating a tree with low c

فرهاديان، فاطمه

ارائه ي يك الگوريتم مسيريابي كيفيت خدمات چند بخشي مقياس پذير

درخت اشتاينر , كولوني مورچه ها , مقياس پذيري