**BANDWIDTH GUARANTEED**

**MULTICAST ROUTING ALGORITHM**

Tran Cong Hung^{1}, Huynh Thach Thao^{2} and Cao Thai Phuong Thanh^{3}

^{1}Post & Telecommunications Institute of Technology, Vietnam

^{2}VP bank FE Credit, Vietnam

^{3}Saigon University, Vietnam

**ABSTRACT**

Computer network is becoming more popular and common, the need to use the broadband connection services (e-learning – online training, video conferencing – online conference, IPTV – digital TV …) of organizations and individuals is increasing. Multicast is an effective mechanism for the transmission of information and data to many recipients simultaneously. Multicast is a routing problem from a source node to a receiver node set, also known as the routing from one point to multipoint. The advances in technology and multimedia applications emerge quickly has provided great motivation for the application of new real-time multi-point. Many multi-point applications will not function properly if the QoS (quality of service) can not be guaranteed. Therefore, multi-point algorithms must be able to meet the QoS constraints (cost, reliability, bandwidth, jitter, delay…). The objective of multicast routing algorithms guarantee QoS is to provide routing algorithms have the ability to recognize the tree to satisfy the maximum of traffic streams with QoS requirements. Most multicast algorithms on MPLS (MultiProtocol Label Switching) considered the unique QoS constraint as bandwidth. The other QoS constraints can be converted into bandwidth efficiency. Starting from this reality, this paper research multicast routing algorithms guarantee bandwidth and propose new algorithm compares with existing ones.

**KEYWORDS**

multicast, quality of service (QoS), routing, guarantee QoS

**1.INTRODUCTION**

IP network models only provide “best effort”, ie the network will try to exploit all possibilities within the limits but not guaranteed delay and data loss. So when traffic on the network transmissions exceed the capability of the network, services are not denied but reduced service quality (delay increases, speed reduces, data loss). IP networks are not suitable for applications that require real-time [1]. Today, with the explosion of Internet multimedia applications, IPTV and other broadcast as broadcast TV, video-on-demand (VoD) and similar VoD generated multicast requirements for core-network service providers. The core-network provides high availability and QoS to reduce network congestion and use resource efficiency. MPLS multicast (Figure 1) are best suited to these requirements. Studies on IP multicast over MPLS network (also known as MPLS multicast) starting from 1999-2000 when only the drafts in the IETF and the scientific paper is published in IEEE. By 2002, a framework was published in RFC 3353 by D.Ooms shows an overview of IP multicast in MPLS environment. Currently MPLS multicast is the big network providers prevail deployment [2], [3], [4].

MPLS multicast support Layer 2 forwarding on the explicit P2M LSP (point-to-multipoint label switched path) rather than the conventional shortest path. MPLS multicast routing are described as follows: (1) the packet is assigned to the difference FEC (Forwarding Equivalence Class) on the path to an egress LSR (Label Switching Router); (2) the FEC then grouped into traffic trunks, this is an routing object inside the LSP; (3) the P2M LSP is established between the ingress and egress LSR. While MPLS provides flexibility in packet switching, but the problems persist when link the multicast tree layer 3 with P2M LSP layer 2 as well as the integration of QoS for resources reservation in MPLS multicast. The multicast routing protocols over MPLS recently [5], [6], [7] are in place to try to overcome these problems.

Figure 1: MPLS Multicast

The paper is divided into four sections: section 1 introduces the MPLS multicast, section 2 presents the related multicast algorithms, section 3 introduces the proposed algorithm, section 4 is experiment and evaluation, part 5 is conclusion and future development.

**2. PROBLEM DEFINITION & RELATED WORK**

Quality of Service (QoS) include bandwidth, delay, jitter…but most scientific studies use bandwidth constrained for other QoS constraints can be converted into efficient bandwidth requirement [8]. The proposed algorithm select multicast tree guaranteed bandwidth to settle for multicast scenarios in multi-point applications.

**2.1. PROBLEM DEFINITION**

Given directed graph G(V,E,C). V is the set of all network nodes (includes switches, routers and hosts…), v∈V is a node, N=|V| is the total number of nodes. E is the set of edges, (u,v)∈E is a path (u,v)=u→v, L=|E| is the total number of edges. C is the set of link bandwidth, c(u,v)∈C is capacity of link (u,v). Cr is the set of residual capacity, cr(u, v)∈Cr remaining bandwidth of link (u,v). A multicast request guaranteed bandwidth is represented by req(s,R,b) with s is source node, the R is set of receivers (which r∈R is a receiver node), b is the request bandwidth. Assume that all receiver nodes in the multicast group with the same bandwidth requirements. This scenario occurs in multicast applications such as video conference. Multicast tree T(s,R) which satisfies b≤min(Cr) so max[Σ req(s,R,b)]. The aim of the problem is to satisfy as many routing requests as possible and optimal use of network resources. Many heuristic methods are proposed for this problem. In particular, the general method is weight the link and apply techniques to find optimal multicast tree with lowest cost min[cost(T(s,R)] (eg SPT, MST or Steiner Tree). However each algorithm has idea with various calculations. Table 1 shows the general steps of this algorithm.

Table 1: The general steps of the heuristic bandwidth guaranteed multicast routing algorithm

**2.2. RELATED WORK**

In a survey of F.F.Punjab [9], the QoS multicast tree selection algorithms is classified according to three criteria: non-MPLS/MPLS, single/multi QoS constraints, heuristic/unicast/artificial-intelligence optimization techniques. Survey shows MPLS is new effective research in reducing congestion and network resource utilization.

Typically among MPLS multicast algorithms are two algorithms inspired by MIRA (Minimum Interference Routing Algorithm) [10]. K. Kar, M. Kodialam, and TV Lakshman proposed MIRA in 2000 for point-to-point routing on the MPLS network. The algorithm introduces the concept of critical links are links easily blocked by calculating the maximum flow-minimum cut. LSP find path avoiding those links to meet many potential requirements. 3 years later, the authors had recommended M-MIRA algorithm (Multicast Minimum Interference Routing Algorithm) [11] find P2M LSP with some changes of MIRA to match the multicast environment. Then in 2009, L-MMIRA algorithm (Light Multicast Routing Algorithm Minimum Interference) [12] was proposed by L.Xuan and L.Ying reducing calculation time significantly.

L-MMIRA algorithms have good performance with less complexity than M-MIRA. While L-MMIRA handle requests through two phases (offline and online), MMIRA has only one phase (online). Phase offline means that the algorithm will calculate the weight of available network parameters before receiving routing requests. Phase online receive requests and find multicast tree based weight, must to calculate if it is not available. In L-MMIRA, two phase calculation parallel and phase offline complies with certain cycle based on change of critical links. Critical link in two algorithms also differ. M-MIRA algorithms define a link is critical when multicast max flow reduced if reducing the bandwidth capacity of the link. MMF (maximum multicast flow) calculation is extremely complex and time consuming due to capacity at scaling – a technique used in the study of network flow with decreasing bandwidth. The consideration of all links between MMF and new MMF is not a simple thing especially for large network. Therefore, the computation time to find tree for a routing request is much greater than L-MMIRA. In L-MMIRA algorithms, multicast requests are generated randomly to predict future demands. For each request generated randomly, find k shortest paths for each path picked out highest initiate weighted link as critical links. Initial weight for each link is inversely proportional to residual bandwidth, i.e link with low bandwidth has high weight. This is understandable because they are capable of highest congestion.

Both algorithms calculate critical link differently but depend much on random requests. The better random requests, the more accuracy of critical link. Random requests in L-MMIRA are not presented clearly and random any request set in phase online. M-MIRA has good idea to generate random set based on history routing. Number of requests as well as receiver node in each request is averaged from collective history request but not interested in source node set and receiver node set.

These algorithms are compared with other traditional multicast routing as SPT (Shortest Path Tree) or MST (Minimal Spanning Tree) [13]. The problem of traditional multicast routing based primarily on costs link as SPT, MST will make link capacity saturation quickly constant for multicast tree with same multicast request. The proposed algorithm continue the idea of MIRA and combine two algorithms M-MIRA and L-MMIRA to achieve the best efficiency routing with relatively computation time. As algorithm design, the requirements are will be presented and evaluate experiment in a later section.

**3. PROPOSED ALGORITHM**

This is the improved algorithm of L-MMIRA for practicing random request was based on realistic parameters and more reliable, not the parameters are generated randomly. The same of M-MIRA, set of source-receivers and number of receivers in each random number request are calculated in advance based on the routing history. This calculation helps critical value flexibility with the practical requests. The possibility of future requests similar to the routing requests, thus predicting the critical links will be more accurate than L-MMIRA. The rest of the phase offline similar to L-MMIRA. During phase online, multicast tree is identified to satisfy the routing requests with the possible lowest cost for efficient resource use. The identification of minimum cost tree for multicast group can resolve by Steiner tree problem, which is NP-hard [10]. In the M-MIRA algorithm, this problem is solved by the simple calculation that is Directed Steiner tree. The proposed algorithm called New-LMMIRA find critical links to restrict the path through these links. It is combine of M-MIRA and L-MMIRA. This reduces bottleneck at the future request. The algorithm has two phases: offline and online. Phase offline executes random requests to find critical links. Phase online finds a multicast tree according Directed Steiner tree algorithm based on link weights. The objective of the proposed algorithm is increasing acceptance ratio and reserve bandwidth for future requests with reasonable computation time and reduce waste network resources.

**Phase Offline:**

**Step 1: Calculate Critical: Determine weight for link**

Number of receivers in each request is predicted based on the average receivers used in the previous requests. Similar to the source and the receivers. Any nodes which were requested will be appeared in the source-receivers set for random requests.

Purpose of the calculation link’s weight is changing the path flexibility with network so weighted formula should be based on bandwidth. The initialize weight for each link (wl) is inversely proportional to the residual bandwidth (cr). The lower the link’s bandwidth, the higher the link’s weight. The path will prioritize passing the links with lower weight because they have less capable of congestion.

(4) Identify critical link

Dijkstra’s algorithm runs k times from source to each receiver m, find the k paths, not select the link with the largest weighting of each route for the CPS (critical path set). Then remove the link from the network model to ensure that the link does not appear on a different shortest path.

(5) Assign the weight for the critical links

CPS includes (k x m) results. Link’s weight is the times each link appears in the CPS. The formula like Eq(3):

**4. PERFORMANCE EVALUATION**

New-proposed algorithm were compared with three routing algorithms such as SPT, M-MIRA, L-MMIRA according to two criteria: the acceptance ratio and the average computation time. The first criteria is the percentage of accepted request set multicast route on total request. Sub-criteria for the acceptance ratio is hard accepted and soft accepted: Hard accepted is which request meets all multicast receiver. Soft accepted is which request meet at least 1 receiver. The second criteria average computing time is algorithm’s processing time receipt of the request.

**4.1 SIMULATION ENVIRONMENT**

Experimental key is NS (Network Simulator) which is inspired by the key operation of NS-2 and some other network simulator environment. It is used to simulate unicast and multicast routing algorithms.

In this section multicast routing algorithms were tested on MIRA and ANSNET topologies. Two schemes are used in a variety of routing bandwidth guaranteed researches [13]. All links bi-directed links. Bandwidth is 1200 MB and 4800 MB in Figure 2 and 2000 MB in Figure 3. For MIRA network topology, the random request are generate according to probability distribution. Source set consisting of {0, 4, 3} and receiver set consisting of {12, 8, 1, 14}, similar to the ANSNET is {1, 4, 7, 18, 21} and {6, 17, 23, 29, 31}.

Experiments were conducted under static routing scenarios. In static routing, requests to sequentially and evenly. Moreover, if request accepted, the multicast tree will keep bandwidth till the end of the experiment. Each dataset consists of 500 requests for MIRA topology and 1000s request for ANSNET topology. Each request includes 1 source and from 2 to 4 receivers are generated randomly according to the uniform distribution. Bandwidth requirement is from 10 to 20 units under the uniform distribution.

**4.2 SIMULATION RESULT**

**MIRA Topology**:

For SPT, initial weights are initialized to 1 for all the links.

For the M-MIRA, MMF limit is set by 200 due to complex calculation.

For L-MMIRA and New-LMMIRA, k = 3 is chosen because good results in the testing process.

100 first requests were generated randomly. In the New-LMMIRA after actual requests, information about the source, receivers and number of receiver will be collected to calculate link’s weights. Phase offline runs periodically in the first time as 1000ms.

**Figure 4: Comparison of experimental results on the MIRA topology**

Figure 4 compares hard accepted results of New-LMMIRA with other algorithms. SPT has the lowest acceptance ratio than the proposed algorithm New-LMMIRA. Specifically, the accepted request of New-LMMIRA is the highest while SPT is the lowest after 500 requests need to meet one of the receivers in each request so the number of soft accepted larger than hard accepted.

Conversely, acceptance ratio SPT is next fast algorithm after L-MMIRA in 500 requests. Meanwhile M-MIRA is the slowest because of MMF time consuming calculation. L-MMIRA has the lowest average computing time by weighted calculation in the offline phase. New-LMMIRA has calculated average time relatively. It can compared with SPT and L-MMIRA and much lower than M-MIRA.

**ANSNET Topology**:

Experiments on ANSNET topology also show results similar to MIRA topology (Figure 5).

Figure 5: Comparison of experimental results on the ANSNET topology

**5. CONCLUSIONS**

While some value-added service is constantly being brought into the Internet, the demand for bandwidth and quality of service is becoming increasingly more urgent. Multicast solves a point-to-multipoint problem efficiently and to reduce network burden. SPT is the easiest algorithm to find the optimal multicast tree. There are many protocols extended to support IP multicast service quality assurance service, but the downside is they do not provide important QoS features such as the distribution, reserve bandwidth for backup and fast reroute. MPLS core network was proposed for solving these problems. Two algorithm on MPLS network are M-MIRA and L-MMIRA but many limits.

This paper has inherited research to calculate the optimal routing tree. Through utilizing the routing information in the past and predicting future request, the proposed algorithm New-LMMIRA give accepted higher than other algorithms with equivalent processing time. However, limitations of the algorithm old the weighted calculation method and experiment only in a static network. Future development direction is evaluating proposed the algorithm on the dynamic network, in which QoS requests can come in any time, and the change of joining or leaving group of recievers multicast.

**REFERENCES**

[1] H.T.Cong (2012), “Multi-protocol Label Switching”, Information and Transmission publisher, p. 89.

[2] S.Natu (2006), “Fast Reroute for Triple Play Networks”, Tech. Report, Redback Networks, APRICOT.

[3] J.Le Roux (2008), “Designing a Carrier Class TV Broadcast Network using P2MP MPLS-TE”, Tech. Report, Orange France Telecom Group.

[4] N.Neate (2009), “RSVP-TE Point-to-Multipoint: An overview of the RSVP-TE P2MP Extensions, Their Applications to IPTV, and Support for Other (G) MPLS Features”, Tech. Report, Data Connection ltd.

[5] Q.Zhao, D. King, F. Verhaeghe, T. Takeda, Z. Ali, J. Meuric (2010), “Extensions to the Path Computation Element Communication Protocol (PCEP) for Point-to-Multipoint Traffic Engineering Label Switched Paths”, RFC 6006.

[6] IJ.Wijnands, I. Minei, K. Kompella, B. Thomas (2011), “Label Distribution Protocol Extensions for Point-to-Multipoint and Multipoint-to-Multipoint Label Switched Paths”, RFC 6388.

[7] E.Rosen, R. Aggarwal (2012), “Multicast in MPLS/BGP IP VPNs”, RFC 6513

[8] P.-T. C. Thai and H. T. Cong (2013), “A Study of Bandwidth Guaranteed Routing Algorithms for Traffic Engineering,” in Advanced Methods for Computational Collective Intelligence, vol. 457, N. T. Nguyen, B. Trawiński, R. Katarzyniak, and G.-S. Jo, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 313–322.

[9] F.Farooq, S. Aslam, and S. Sarwar (2009), “QoS-based MPLS multicast tree selection algorithms”, p. 1.

[10] K. Kar, M. Kodialam, and T. V. Lakshman (2000), “Minimum interference routing of bandwidth guaranteed tunnels with MPLS traffic engineering applications,” IEEE J. Sel. Areas Commun., vol. 18, no. 12, pp. 2566–2579.

[11] M.Kodialam, T. V. Lakshman, and S. Sengupta (2003), “Online multicast routing with bandwidth guarantees: A new approach using multicast network flow,” IEEEACM Trans. Netw., vol. 11, no. 4, pp. 676–686.

[12] L.Xuan and L. Ying (2008), “L-MMIRA: Light Multicast Minimal Interference Routing Module in MPLS Network,” Seventh International Conference on Networking, pp. 421–426.

[13] E.Crawley, R. Nair, B. Jajagopalan, H.Sandick (1998), “A Framework for QoS-based Routing in the Internet,” RFC 2386.

**Authors**

**Tran Cong Hung** was born in Vietnam in 1961.He received the B.E in electronic and Telecommunication engineering with first class honors from HOCHIMINH University of technology in Vietnam, 1987. He received the B.E in informatics and computer engineering from HOCHIMINH University of technology in Vietnam, 1995. He received the master of engineering degree in telecommunications engineering course from postgraduate department Hanoi University of technology in Vietnam, 1998. He received Ph.D at Hanoi University of technology in Vietnam, 2004. His main research areas are B – ISDN performance parameters and measuring methods, QoS in high speed networks, MPLS. He is, currently, Associate Professor PhD. of Faculty of Information Technology II, Posts and Telecoms Institute of Technology in HOCHIMINH, Vietnam.

**Huynh Thach Thao** was born in Vietnam in 1990.She received B.E. in Information Engineering from Saigon University, Vietnam in 2012. She is currently a MSc. Candidate in Information System from Post & Telecommunications Institute of Technology, Vietnam in 2015. She is working as reporting specialist in VP bank FE Credit, Vietnam.

**Cao Thai Phuong Thanh** was born in Vietnam in 1983.He received B.E. in Information Technology from Ho Chi Minh City University of Science, Vietnam in 2005; MSc. in Computer Science from University of East Anglia, UK in 2007, and currently a PhD candidate in Information System from Post & Telecommunications Institute of Technology, Vietnam. He is working as lecturer in Faculty of Information Technology, Saigon University, Vietnam.

%d bloggers like this: