2017 IEEE First Ukraine Conference on Electrical and Computer Engineering (UKRCON)

Model of Multicast Routing With Support of Shared

Explicit Reservation of Link Resources

Amal Mersni Andriy Ilyashenko, Tetiana Vavenko

Department of Information systems Department of Infocommunication Engineering
National Technical University «Kharkiv Polytechnic Kharkiv National University of Radio Electronics
Institute» Kharkiv, Ukraine
Kharkiv, Ukraine andy.ilyashenko@gmail.com, tetiana.vavenko@nure.ua
elmersniamal@gmail.com

Abstract— In this paper the mathematical model of multicast allocated are not to one, but to multiple flows, the list of
routing of flows with support shared explicit reservation of link which is clearly indicated;
resources is proposed. The proposed model consists of a linear
expressions, which are responsible for providing the connectivity x Group Filter (Wildcard Filter, WF), which also
of the calculated multicast routes, and also the absence of loops in implements shared resource reservation for a plurality
them. The novelty of the model is the using of conditions of of flows, the list of which doesn't clearly indicated.
prevention the congestion in communication links due the
It should be noted that the reservation styles represented by
implementation of the shared explicit reservation, which allows
allocating the links resource between multiple flows, but at the SE and WF filters are focused mainly on service of multicast
same time the list of these flows is strictly defined. The flows.
optimization problem of multicast routing of flows with support An important disadvantage of IntServ architecture model is
shared explicit reservation of link resources is formulated as the that the efficiency of this protocol depends on routing protocol.
task of mixed integer linear programming. Using the proposed This significantly limits the functionality of the protocol
model allows to use the available link resource more efficient (on RSVP. If the routing protocol will calculate a route which
average 20-25%) by providing the coherence of solutions of
hasn't needing available resources the RSVP protocol is not
multicast routing problem and organization of shared explicit
reservation of link resources.
able to perform its functions and will be required to initiate a
recalculation of the route. Therefore the scientific task
Keywords— mathematical model; multicast routing; shared associated with providing coherence of solutions of multicast
explicit reservation; resource reservation protocol; Quality of routing problem and general explicit reservation of link
Service. resource in telecommunication networks is actual. The solution
to this problem requires improvement previously known flows
I. INTRODUCTION multicast routing models by taking into account features of the
Modern multiservice telecommunication networks have a reservation of link resource with using SE filter.
sufficiently broad capabilities in terms of Quality of Service
II. MATHEMATICAL MODEL OF MULTICAST ROUTING OF
(QoS). At the same time with using of differentiated services
FLOWS
(Differentiated services, DiffServ) is actively used a guaranteed
or integrated service (Integrated Services, IntServ), which Solutions of multicast routing should perform the following
based on the using of IP-based networks resource reservation important requirements: efficient using of available network
protocol RSVP (Resource ReSerVation Protocol), for example resources by minimizing the loading in telecommunication
[1]. Providing QoS-guarantees which associated with networks; guaranteed absence of loops in the calculated route;
reservation of link and buffer resources in telecommunication supporting of quality of service; an optimality of calculated
networks usually is accompanied by a decreasing in network routes; high scalability of solutions and providing a high level
scalability. This reason is that for each flow along the of security of transmitted data [2-4]. As a criterion of the
calculated path by the routing protocol is necessary to maintain effectiveness of solutions of multicast routing problem can be
the state of the reservation of network resources to which other used minimum or maximum of QoS parameter. For example, it
flows cannot apply. To improve scalability resource of can be a minimum of the average end-to-end delay, the cost of
reservation solutions of RSVP protocol are used several styles using the network resource, the network loading, the
reservation with following types of filters: maximizing of network performance.
x Fixed Filter (FF), used especially for service unicast The main advantage of combinatorial methods of solution
streams; problem of finding the shortest path is the low computational
complexity of their implementation [4-6]. However such
x Filter with a shared explicit reservation (Shared solutions may not always provide an optimality using of
Explicit, SE), in which a certain network resources are network resources and the highest QoS parameters. Therefore a
prospective direction in the modeling of multicast routing


ª
*&&& 
 2017 IEEE First Ukraine Conference on Electrical and Computer Engineering (UKRCON)
process is the using of flow models, which can adequately
describe the modern network traffic and processes of it
processing [7-9].
 ¦x
i:(i , j )E
k
(i , j ) t x(kj , p ) , k  K ; v j  s k  

As shown in [8-9] for modeling the processes of multicast

routing the structure of telecommunication networks can be The physical sense of these conditions is that the packets
represented by oriented weighted graph G (V , E ) . Then can appear on output interfaces of transit routers only if they
received at least to one of its input interfaces.
V ^v1..., vi ,...vm `
is the set of tops modeling the nodes
To provide connectivity of multicast routes and to avoid the
(routers) of the network; (i, j )  E is the set of arcs modeling appearance of loops in the transmission route of packets the
the network links. For each link it used its weight M (i , j ) , which following conditions for router variables are introduced:
characterizes the capacity of the modeling link.
To provide maximum taking into account features of
reservation of network resources according to the filter SE it
 ¦x i
k
(i , j )  ESi  
(i , j )ES
will introduce the following notation:
x K is a set of circulating in the network multicast where ESi is set of arcs of the graph, which forms i -th circuit
packet flows;
( S ); ESi is the number of arcs in the i -th network circuit.
x rk is an average packet rate of k -th flow at the input
The number of conditions (6) corresponds to the number of
to the network (1/s); independent paths in the network.
x sk is a router-source of packages of k -th flow, k  K ; III. CONDITIONS OF SHARED EXPLICIT RESERVATION OF LINK
RESOURCES IN ROUTING OF MULTICAST FLOWS
 d k* ^d 1 2 mk
k , d k ,..., d k `  For conditions of general explicit reservation of link
resources in routing of multicast flows additionally introduce
is the set of the router-receivers nodes of k -th multicast flow; some more notation:
mk is the number of such routers. x K sSE is s -th SE-group, which combines set of
Then the implementation of multicast routing it is required multicast flows (usually with different router-senders),
to calculate the set of the boolean variables: for which the shared explicit reservation of link
resource in telecommunication networks is produced;
 x(ki , j )  ^0;1`   x J (si , j ) is part of the capacity of the communication link,
modeling by arc (i, j )  E , which should be used to
which characterize the part of intensity of the k -th packet flow
reservation for multicast flows, which are in s -th SE-
transmitted via the link, which model by arc (i, j )  E ; k  K .
group, those k  K sSE .
In order to ensure the delivery of multicast packets of k - th
The novelty of the proposed model of general explicit
flow to all router-receivers are introduced following conditions:
reservation of link resources in routing of multicast flows is the
using of conditions of preventing the overload in
communication links of telecommunication networks:
 ¦x
i:(i , j )E
k
(i , j ) 1 , k  K ; v j  d k*  
rk ˜ x(ki , j ) d J (si , j ) ˜ M (i , j ) , k  K sSE , (7)
For router-receivers it is necessary to introduce the
condition: S

¦J
s 1
s
(i , j ) d1. (8)

 ¦x
j:(i , j )E
k
(i , j ) t 1 , k  K , vi s k  
Condition (7) was introduced into the model because during
process of shared explicit reservation it is reserved link
the implementation of which allows to send packets of k -th resource for the maximum demands of flow from the SE-group
flow to several neighbor routers, but not less than one. [1]. The value of these requirements for bandwidth in fact
defines the lower threshold of the expression J (si , j ) ˜ M (i , j ) .
For each router from a set of transit routers v j  V , which
includes all routers except the sender, the following conditions Equation (8) is responsible for ensuring that only available
are introduced: link resources will be used during the reservation.


 2017 IEEE First Ukraine Conference on Electrical and Computer Engineering (UKRCON)
IV. OPTIMALITY CRITERION OF MULTICAST ROUTING OF FLOWS 2
WITH SHARED EXPLICIT RESERVATION OF LINK RESOURCES
r2
The optimality criterion of routing of multicast flows with 1 5
500 700
shared explicit reservation of link recourses should consider the
following points. Firstly it is important to take into account the r1
r1 600
features of technological implementation of these processes, 400 r2
and secondly they should have effective methods of solving
300 300
this optimization problem.
r1
To determine the optimal solution of multicast routing with r2 300
r2
shared explicit reservation of link resources it is offered the 3 4
following optimality criterion, which is a minimum of linear
function: Fig. 1. An example of the network structure.

S Efficiency of using the network bandwidth of

 J ( x, J ) ¦ ¦
kK (i , j )E
f (ki , j ) x(ki , j )  ¦
s 1
g (si , j )J (si , j )   communication links was evaluated by the following parameter

ª S º
« ¦ M (i, j ) ¦ J (si, j ) »
where f (ki , j ) is a routing metric of link (i, j )  E , which is «1  (i , j )E s 1 »100% 
 P 
used by packages of k -th flow; g (si , j ) is the cost (metric) of « ¦ M (i , j ) »
« (i , j )E »
the shared explicit reservation the capacity of link (i, j )  E ¬ ¼
for multicast flows of s -th SE-group. In general case metric which is numerically characterized the percentage of the
g (si , j ) numerically can depend on both the number of multicast remaining unutilized link resource after shared explicit
streams and its priority, which are formed s -th SE-group, and reservation.
structural and functional parameters of the communication link In the case when every of the border routers were
(i, j )  E . The first summand in equation (9) represents the responsible for the solution of the problem, then one of the
total metric of solutions the routing problem, and the second solutions may be a plurality of two multicast routes, which are
summand is the total cost of solution the shared explicit shown in Fig. 2. In this figure the multicast route for the first
reservation of link recourses. flow shown by solid line and the multicast route for the second
flow shown by intermittently line. In the breaks of
V. ANALYSIS OF SOLUTIONS THE MULTICAST ROUTING communication links are indicated following parameters: in the
PROBLEM OF FLOWS WITH SHARED EXPLICIT RESERVATION OF numerators - the flow rate, which coincides with the value of
LINK RESOURCES the reserved bandwidth, in the denominators – the bandwidth
of communication links. The disadvantage of such solutions is
In the research the analysis of the effectiveness of the
that the link resource for each flow been reserved individually,
proposed solutions of routing the multicast flows with shared
and this has led to unnecessary using the bandwidth of
explicit reservation of link recourses (1) - (9) is used for
communication links. It corresponded to value of parameter
different network structures, which were differed by number of
(10) by 52%.
routers, communication links and its bandwidth. The efficiency
of the proposed model (1) - (9) which coordinates solutions of In Fig. 3 shows a variant of the solution of the problem
multicast routing and shared explicit reservation of link using a model (1) - (9), when the route metrics and reservation
recourses was compared with solutions in which these cost were equal to unity. This led to the calculation of routes
problems are solved separately. At the Fig. 1 an example of tree with the minimum number of links (four). At the breaks of
network structure is shown. The bandwidths of communication communication links are indicated fallowing parameters (top to
links are indicated at breaks of its. It is necessary to calculate bottom): the intensity of the first flow, the intensity of the
routes and to implement shared explicit reservation for two second flow, the bandwidth of communication link. The value
multicast flows: of the reserved resource in each of the links correspond to the
maximum intensity of the transmitted flow in it.
x for the first flow with intensity r1 =300 1/s, router-
Resulting solution is allowed to increase parameter (10) to
source was v1 , and router-receivers were d 1* ^v 4 , v5 ` ; 65%, but in this case three network links (1, 3), (3, 4), (4, 5) are
is almost overloaded. If we assume that the cost of the
x for the second flow with intensity r2 =200 1/s, router- reservation of bandwidth of communication links associated
source was v 3 , and router-receivers were with the bandwidth of these links by ratio g (si , j ) 10 7 M (i , j ) ,
d 2* ^v2 , v4 , v5 ` . then it will be obtained the solution, which is shown in Fig. 4.


 2017 IEEE First Ukraine Conference on Electrical and Computer Engineering (UKRCON)
2 allocate link resources to multiple flows. The list of these flows
is strictly determined by the content of the respective SE-
200
300 group. The problem of multicast routing of flows with support
1 300 5
500 700
for shared explicit reservation of link resources is formulated as
200
300 300 an optimization. The criterion for optimality of the solution is
300
400
600 200 the minimum of the function (9), which characterizes the total
200 cost of using the communication links by user flows and
300 reservation for them the necessary volumes of bandwidth.
200 300
200 300
4
200 Introduced route variables x(ki , j ) are responsible for the
3
resulting of multicast routing of flows and they have the
Fig. 2. Example of distributed solutions. boolean character. Variables J (si , j ) , which determine the shared
explicit reservation are real. The total number of control
2 ~
variables for the calculation is n( K  S ) . The control variables
200
must be taken into account the conditions of linear constraints
1 5 (1) - (8), and the objective function (9), which is minimized, is
300
0 300 also linear. Therefore this optimization problem belongs to the
200 200 class of mixed integer linear programming (MILP). The known
300 400 300
200 200
computational algorithms can be used for solving problems of
300 300 300 this class. For example the algorithm “Branch and Cut”
200 200 300 Algorithm, genetic algorithms and others.
300 200
3 4 Using the proposed model (1) - (9) in practice allow to
provide coherence between the decisions of interconnected
Fig. 3. Variant of the coordinated solution of the problem using a model (1) - network tasks: multicast routing of flows and shared explicit
(9), when the route metrics and reservation cost were equal to unity.
reservation of link resources. The decisions that were obtained
2 using the proposed model are oriented to the optimal using of
the available link resource in telecommunication network.
200 Using the proposed model allows to use the available link
300 300
1 0 200 5 resource more efficient (on average 20-25%) by providing the
500 300 700 coherence of solutions of multicast routing problem and
0 300
300 200 organization of shared explicit reservation of link resources.
200 200
600
400
REFERENCES
300 [1] M. Barreiros, P. Lundqvist. QOS-Enabled Networks: Tools and
200 Foundations. Wiley Series on Communications Networking &
200
3 4 Distributed Systems, 2nd Edition. Wiley, 2016, 254 p.
[2] B. Williamson. Developing IP Multicast Networks. Cisco Press, 2000,
Fig. 4. Variant of the coordinated solution of the problem using a model (1) - 592 p.
(9), when reservation costs are g (si , j ) 10 7 M (i , j ) . [3] E. Rosenberg. A Primer of Multicast Routing. Springer Briefs in
Computer Science, 2012, 117 p.
[4] V. Joseph. Deploying Next Generation Multicast-enabled Applications:
In this case the parameter (10) was be equal to 65%, and Label Switched Multicast for MPLS VPNs, VPLS, and Wholesale
one network was loaded more balanced than in the case which Ethernet. Kindle Edition. Elsevier Inc, 2011, 560 р.
shown in Fig. 3. Similar situation was observed for the other [5] P. Paul, S. Raghavan. "Survey of multicast routing algorithms and
source data. Thus using the proposed model allows to use the protocols", in Proc. of the Fifteenth International Conference on
available link resource more efficient (on average 20-25%) by Computer Communication (ICCC 2002), 2002, pp. 902-926.
providing the coherence of solutions of multicast routing [6] C.A. Oliveira, P.M. Pardalos. "A Survey of Combinatorial Optimization
problem and organization of shared explicit reservation of link Problems in Multicast Routing". Computers and Operations Research,
Vol. 32, Issue 8, pp. 1953-1981, 2005.
resources.
[7] Y. Seok, Y. Lee, Y. Choi, C. Kim. "Dynamic Constrained Traffic
VI. CONCLUSIONS Engineering for Multicast Routing", in Proc. Wired Communications
and Management, Vol. 2343, pp. 278-288, 2002.
In the paper the mathematical model of multicast routing of [8] O.V. Lemeshko, Kinan Mohamad Arous. "The flow-based model of
flows with support shared explicit reservation of link resources multicast routing", in Proc.the 23rd International Crimean Conference
was proposed. The model consists of linear expressions (1) - "Microwave and Telecommunication Technology (CriMiCo)", 2013,
pp. 523-524.
(8), which are responsible for providing connectivity between
calculating of multicast route and the absence of loops in them. [9] O. Lemeshko, Arous Kinan, A.wahhab Mohammed A.jabbar. "Multicast
Fast Re-Route Schemes for Multiflow Case", in Proc. of the XIIIth
The novelty of model is the using of system of conditions (7) International IEEE conference "The experience of designing and
and (8) which allow prevent overload in communication links application of CAD systems in microelectronics( CADSM’2015)", 2015,
with implementation the shared explicit reservation. It allows pp. 422-424.