Multicast Flows

Lecture Outline

• Introduction
• Integer Programming Formulations
• Cost Problem
• Network Design Problem
• Maximum Delay Problem
• Throughput Problem
• Multicast Packing Problem
• Concluding Remarks

Lecture Outline

• Introduction

• Integer Programming Formulations
• Cost Problem
• Network Design Problem
• Maximum Delay Problem
• Throughput Problem
• Multicast Packing Problem
• Concluding Remarks

Introduction (1)

• In traditional networks two basic techniques 

are used for routing:

– Unicast (one-to-one)
– Broadcast (one-to-all)

• Both routing methods are not sufficient when 

information is to be delivered to a relatively large 

group of users, geographically separated and 

with similar interest on content

• This situation has triggered development 

multicast routing defined as one-to-many 

transmission

Introduction (2)

Example application of multicasting:
• IP TV
• Video on Demand (VoD)
• Radio Streaming
• Content Delivery Networks (CDN)
• Distance learning
• Software updates
• Monitoring
• Result distribution (computing systems)

Introduction (3)

• Multicast modeling can use two classical network 

problems:

– Steiner tree problem. Given a set V of points 

(network nodes), interconnect them by a subgraph 

of shortest length (sum of the lengths of all edges)

– Minimum Spanning Tree (MST) problem is a 

subgraph of the orginal graph (network) which is a 

tree (no loops) and connects all the vertices 

together

• The difference between both problems is that, in the 

Steiner tree problem, extra intermediate vertices 

(Steiner vertices) and edges may be added to the 

graph in order to reduce the length of the spanning 

tree

Introduction (4)

Multicasting can be divided into two categories:
• Traditional IP multicast is a method to send 

packets to a group of interested receivers in a 

single transmission. The multicasting is in layer 3 

and IP routers are responsible to create the 

delivery tree. End hosts (receivers) are leafs of 

the tree

• Overlay multicast (P2P multicast, application-

layer multicast) is realized in layer 7. End hosts 

can also upload the stream to other peers

Traditional IP multicast (1)

• Protocol-Independent Multicast (PIM) is a 

family of IP multicast protocols that provide one-to-

many and many-to-many distribution of data over 

an IP network. PIM is protocol-independent, since it 

does not include its own topology discovery 

mechanism, but instead uses routing information 

supplied by other traditional routing protocols (e.g., 

BGP)

• Internet Group Management Protocol (IGMP) is 

a protocol used to manage the membership of IP 

multicast groups. IGMP is used by hosts and 

adjacent multicast routers to establish multicast 

group memberships

Traditional IP multicast (2)

2

1

3

4

11

8

7

6

9

Root 
node

IP Router

Multicast 
tree

12

5

10

1

End host 
(receiver
)

P2P Multicast

1

2

3

4

5

6

7

Lecture Outline

• Introduction

• Integer Programming Formulations

• Cost Problem
• Network Design Problem
• Maximum Delay Problem
• Throughput Problem
• Multicast Packing Problem
• Concluding Remarks

Formulations

• Canonical Formulation
• Flow Formulation
• Level  Formulation
• Candidate Tree Formulation

Canonical Formulation (1)

• Multicast is modeled using Steiner tree problem
• For each edge e, there is a variable x

e

 indicating 

whether e is in the Steiner tree (x

e

 = 1) or not (x

e

 

= 0)

• The formulation uses cuts of the original network 

graph G=(V,E), where V denotes set of nodes and 

E set of links

• Set T denotes set of terminals (receivers)




(W) denotes the cut induced by WV, i.e., the set 

of edges with the source node in W and the 

destination node in its complement (V \ W)

Canonical Formulation (2)

2

1

3

4

11

8

7

6

9

Root 
node

Terminal 
(receiver)

Multicast 
tree

8

9

12

5

10

1

7

Cut

Canonical Formulation (3)

sets
V 

network nodes

E

links (directed edges)

T

terminals (receivers)

constants



(W)  cut induced by WV, including edges with the 

source node in W and end node in its 

complement 

(V \ W)

s

root node of multicast tree

h   

volume (bandwidth requirement) of multicast

c

e

    capacity of link e

Canonical Formulation (4)

variables
x

e

 

= 1, if multicast tree uses link e; 0, otherwise 

(binary)

constraints
x(



(W))  1,   for all WV, sW, (V \ W)T  0

x(



(W)) = 

e



(W) 

x

e

,

x

e

h

 

 c

e

    e = 1,2,…,E.

Flow Formulation (1)

• Node-Link formulation developed for unicast flows 

can be modified to be used in multicast flows

• For easy of reference this formulation is named 

flow

• The flow to each receiver of the multicasting is 

modeled as unicast path

• Additional variable associated with each link is in 

the model to assure that the flow goes through 

the link at most one time

Flow Formulation (2)

2

1

3

4

11

8

7

6

9

Root 
node

Receiver 
(leaf) node

7

Unicast 
path
Multicast 
tree

8

9

12

5

10

1

Flow Formulation (3)

indices
v = 1,2,…,V 

network nodes

e = 1,2,…,Elinks
k = 1,2,…,K(terminals) receivers
constants
a

ev

   = 1, if link e originates at node v; 0, otherwise 

b

ev

   = 1, if link e terminates in node v; 0, 

otherwise

s

root node of multicast tree

h   

volume (bandwidth requirement) of multicast

c

e

    capacity of link e

Flow Formulation (4)

variables
x

ek

 

= 1, if multicast flow to receiver k uses link e; 0, 

otherwise (binary)

x

e

 

= 1, if multicast tree uses link e; 0, otherwise 

(binary)

constraints


e

 a

ev

x

ek

 – 

e

 b

ev

x

ek

 = 1,   if v = s

  

v = 1,2,…,V  

 

k = 

1,2,…,K



e

 a

ev

x

ek

 – 

e

 b

ev

x

ek

 = –1,   if v = k

   

v = 1,2,…,V  

 

k = 1,2,

…,K



e

 a

ev

x

ek

 – 

e

 b

ev

x

ek

 = 0,   if v  s,k

   

v = 1,2,…,V  k = 1,2,

…,K

x

ek 

 x

e

,   e = 1,2,…,E  

 

k = 1,2,…,K

x

e

h

 

 c

e

,   e = 1,2,…,E.

Level Formulation (1)

• We assume that the root of the tree is located on 

level 1 

• All children of the root (nodes that have a direct 

link from the root) are located on level 2

• If a father node of v is on level l, then v is located on 

level (l + 1)

• For easy of reference this formulation is named level
• Variable x

wvl

 is 1 if the link (w,v) is used in multicast 

tree and w is located on level l of the tree t

• In the literature this formulation is also called 

Layered Graphs (Gouveia et al.)

Level Formulation (2)

2

1

3

4

11

8

7

6

9

Root 
node

Receiver 
(leaf) node

Multicast 
tree

8

9

12

5

10

1

Level 1 
node

Level 2 
node

7

Level 3 
node

Level Formulation (3)

indices
v,w,b = 1,2,…,V  network nodes
k = 1,2,…,K

receivers

l = 1,2,…,L

levels (parent nodes)

constants
s

root node of multicast tree

e(w,v)

=1, if there is a direct link (w,v) in 

graph; 0, otherwise

h   

volume (bandwidth requirement) of multicast

c

wv

    capacity of link (w,v)

Level Formulation (4)

variables
x

wvl

  = 1, if the link (w,v) is used in multicast tree 

and w is  located on level l of the tree; 0, 
otherwise (binary)

x

wv

 

= 1, if multicast tree uses link (w,v); 0 

otherwise 

(binary)

Level Formulation (5)

constraints


w:e(w,v)=1 



l

 x

wvl

 = 0,   v = s   v = 1,2,…,V



w:e(w,k)=1 



l

 x

wkl

 = 1,    k = 1,2,…,K



v:e(w,v)=1 

x

wv1

 = 0,   w  s   w = 1,2,…,V

x

wv(l+1)

  

b

 x

bwl

,   e(w,v) = 1  w = 1,2,…,V v = 1,2,

…,V l = 1,2,…,L - 1



l

x

wvl

  x

wv

,  e(w,v) = 1   w = 1,2,…,V  v = 1,2,…,V

x

wv

  

l

x

wvl

, e(w,v) = 1 w = 1,2,…,V  v = 1,2,…,V

x

wv

h

 

 c

wv

,  e(w,v) = 1   w = 1,2,…,V  v = 1,2,…,V.

Candidate Tree Formulation 

(1)

• Analogy to Link-Path unicast formulation
• There are candidate trees (topologies) with the 

same root node and connecting all terminals 
(receivers)

Candidate Tree Formulation 

(2)

2

1

4

11

8

7

6

9

Root 
node

Terminal 
(receiver)

Candidate 
tree

8

9

12

5

10

7

Candidate 
tree

Candidate 
tree

1

3

Candidate Tree Formulation 

(3)

indices
e = 1,2,…,Elinks
p = 1,2,…,Pcandidate trees
constants



ep

= 1, if link e belongs to tree p; 0, otherwise

h   

volume (bandwidth requirement) of multicast

c

e

    capacity of link e

Candidate Tree Formulation 

(4)

variables
x

p

 

flow allocated to tree p (continuous non-

negative)

constraints


p 

x

p

 = h



p 



ep

x

p

  c

e

,   e = 1,2,…,E.

Lecture Outline

• Introduction
• Integer Programming Formulations

• Cost Problem

• Network Design Problem
• Maximum Delay Problem
• Throughput Problem
• Multicast Packing Problem
• Concluding Remarks

Cost Problem (1)

• FA (Flow Allocation) problem
• The stream is split and multiple trees are used 

to deliver the content to receivers

• Each tree has the same root
• Objective is to minimize overall cost of the 

streaming

• Level limit to improve QoS and reliability
• Level formulation

Cost Problem (2)

Given: network topology, link capacity, location of 

root, set of receivers, volume of each trees, level 
limit, link cost

Minimize: cost

Over: multicast routing

Cost Problem (3)

indices
v,w,b = 1,2,…,V  network nodes
k = 1,2,…,K

receivers

t = 1,2,…,T

trees

l = 1,2,…,L

levels (parent nodes)

Cost Problem (4)

constants
s

root node of multicast tree

e(w,v)

=1, if there is a direct link (w,v) in 

graph; 0, otherwise

h

t

   

volume (bandwidth requirement) of tree t

c

wv

    capacity of link (w,v)



wv

 

routing cost of link (w,v)

Cost Problem (5)

variables
x

wvtl

  = 1, if the link (w,v) is used in multicast tree t 

and w is  located on level l of the tree; 0, 

otherwise (binary)

x

wvt

  = 1, if multicast tree t uses link (w,v); 0 

otherwise 

(binary)

objective
minimize F = 

w 



v 



t 

x

wvt 

h

t 



wv

 

Cost Problem (6)

constraints


w:e(w,v)=1 



l

 x

wvtl

 = 0,

v = s   v = 1,2,…,V   t = 1,2,

…,T



w:e(w,k)=1 



l

 x

wktl

 = 1,     k = 1,2,…,K   t = 1,2,…,T



v:e(w,v)=1 

x

wvt1

 = 0,   

w  s   w = 1,2,…,V   

t = 1,2,…,T

x

wvt(l+1)

  

b

 x

bwtl

,   

e(w,v) = 1 w = 1,2,…,V 

v = 1,2,…,V   l = 1,2,…,L - 1   

t = 1,2,…,T



l

x

wvtl

  x

wvt

,  e(w,v) = 1   

w = 1,2,…,V  v = 1,2,

…,V   

t = 1,2,…,T

x

wvt

  

l

x

wvtl

, e(w,v) = 1 

w = 1,2,…,V  v = 1,2,

…,V   

t = 1,2,…,T



t 

x

wvt

h

t 

 c

wv

,  e(w,v) = 1   w = 1,2,…,V   v = 1,2,…,V.

Optimization

• The problem is linear, integer (binary) and 

NP-complete (equivalent to Steiner tree 
problem)

• To find optimal solutions solvers like CPLEX and 

GuRoBi can be used

• Heuristics can be used, e.g., construction 

algorithms, greedy approach, evolutionary 
algorithm, etc.

Lecture Outline

• Introduction
• Integer Programming Formulations
• Cost Problem

• Network Design Problem

• Maximum Delay Problem
• Throughput Problem
• Multicast Packing Problem
• Concluding Remarks

Network Design Problem (1)

• CFA (Capacity and Flow Allocation) problem for 

multicast flows

• A number of multicast demands, each is 

defined by the root node, set of receivers and 
volume

• Modular links
• Flow formulation of multicast flows

Network Design Problem (2)

Given: network topology, link capacity, multicast 

demands (root, receivers and volume)

Minimize: network cost

Over: multicast routing, link allocation

Network Design Problem (3)

indices
v = 1,2,…,V 

network nodes

e = 1,2,…,Elinks
d = 1,2,…,D

multicast demands (multicast 

group)

k = 1,2,…,K

d

receivers in multicast demand d

Network Design Problem (4)

constants
a

ev

   = 1, if link e originates at node v; 0, otherwise 

b

ev

   = 1, if link e terminates in node v; 0, 

otherwise

s

d

root node of multicast demand d

h

d

    volume of multicast demand d



e

 

cost of one capacity module on link e

M 

size of the link capacity module

Network Design Problem (5)

variables
x

edk

  = 1, if multicast flow of multicast demand d to 

receiver  k uses link e; 0, otherwise (binary)

x

ed

 

= 1, if multicast demand d uses link e; 0, 

otherwise (binary)

y

e

capacity of link e expressed in the number of 
modules  (non-negative integer)

objective
minimize F = 

e 



e

y

e

Network Design Problem (6)

constraints


e

 a

ev

x

edk

 – 

e

 b

ev

x

edk

 = 1,   

if v = s

d  

   v = 1,2,…,V    

d = 1,2,…,D

   

k = 1,2,…,K

d



e

 a

ev

x

edk

 – 

e

 b

ev

x

edk

 = –1,    if v = k

   

v = 1,2,…,V  

 

d = 1,2,…,D

   

k = 1,2,…,K

d



e

 a

ev

x

edk

 – 

e

 b

ev

x

edk

 = 0,   

if v  s

d

,k

   

v = 1,2,…,V 

d = 1,2,…,D

   

k = 1,2,…,K

d

x

edk 

 x

ed

,    e = 1,2,…,E   d = 1,2,…,D   

k = 1,2,…,K

d



d 

x

ed

h

t 

 My

e

,    e = 1,2,…,E.

Optimization

• The problem is linear, integer, and NP-

complete (equivalent to Steiner tree problem)

• To find optimal solutions solvers like CPLEX and 

GuRoBi can be used

• Heuristics can be used

Lecture Outline

• Introduction
• Integer Programming Formulations
• Cost Problem
• Network Design Problem

• Maximum Delay Problem

• Throughput Problem
• Multicast Packing Problem
• Concluding Remarks

Maxium Delay Problem (1)

• FA (Flow Allocation) problem
• Objective is to minimize the maximum (worst) 

delay to receiver (QoS requirement)

• Flow formulation, since the level formulation 

does not include the path to receiver

Maxium Delay Problem (2)

Given: network topology, link capacity, location of 

root, set of receivers, tree volume, link delays

Minimize: maximum delay

Over: multicast routing

Maxium Delay Problem (3)

indices
v = 1,2,…,V 

network nodes

e = 1,2,…,Elinks
k = 1,2,…,Kreceivers
constants
a

ev

   = 1, if link e originates at node v; 0, otherwise 

b

ev

   = 1, if link e terminates in node v; 0, 

otherwise

s

root node of multicast tree

Maxium Delay Problem (4)

constants
h   

volume of multicast transmission t



e

 

delay of link e

c

e

 

capacity of link e

variables
x

ek

 

= 1, if multicast flow to receiver k uses link e; 

0,  otherwise (binary)

x

e

 

= 1, if multicast tree uses link e; 0, otherwise 

(binary)

x

maximum delay (non-negative continuous)

Maxium Delay Problem (5)

objective
minimize x
constraints


e

 a

ev

x

ek

 – 

e

 b

ev

x

ek

 = 1,   

if v = s

     

v = 1,2,…,V  

 

k = 1,2,…,K



e

 a

ev

x

ek

 – 

e

 b

ev

x

ek

 = –1,

if v = k

    

v = 1,2,…,V  

 

k = 1,2,…,K



e

 a

ev

x

ek

 – 

e

 b

ev

x

ek

 = 0, if v  s,k

    

v = 1,2,…,V  

k = 1,2,…,K



e

 



e

x

ek 

 x,   

k = 1,2,…,K

x

ek 

 x

e

,   

e = 1,2,…,E  

 

k = 1,2,…,K

x

e

h

 

 c

e

,    e = 1,2,…,E.

Optimization

• The problem is linear, integer, and NP-

complete (equivalent to Steiner tree problem)

• To find optimal solutions solvers like CPLEX and 

GuRoBi can be used

• Heuristics can be used

Lecture Outline

• Introduction
• Integer Programming Formulations
• Cost Problem
• Network Design Problem
• Maximum Delay Problem

• Throughput Problem

• Multicast Packing Problem
• Concluding Remarks

Throughput Problem (1)

• FA (Flow Allocation) problem
• Objective is to maximize the throughput 

(streaming rate)

• Multiple trees are used for streaming
• Level limit to improve QoS and reliability
• Level formulation of multicast flows

Throughput Problem (2)

Given: network topology, link capacity, location of 

root, set of receivers, number of trees

Maximize: throughput

Over: multicast routing

Throughput Problem (3)

indices
v,w,b = 1,2,…,V  network nodes
k = 1,2,…,K

receivers

t = 1,2,…,T

trees

l = 1,2,…,L

levels (parent nodes)

Throughput Problem (4)

constants
s

root node of multicast tree

e(w,v)

=1, if there is a direct link (w,v) in 

graph; 0, otherwise

c

wv

    capacity of link (w,v)

M

large number

Throughput Problem (5)

variables
x

wvtl

  streaming rate on an overlay link (w,v) (no 

other 

peer nodes in between) in multicast tree 

t and w is 

located on level l of tree t; 

(continuous, non-

negative) 

x

wvt

  = 1, if multicast tree t uses link (w,v); 0 

otherwise 

(binary)

q

t

   

throughput (bandwidth requirement) of tree t 
(continuous, non-negative)

objective
maximize F = 

t 

q

t

Throughput Problem (6)

constraints


w:e(w,v)=1 



l

 x

wvtl

 = 0,

v = s   v = 1,2,…,V   t = 1,2,

…,T



w:e(w,k)=1 



l

 x

wktl

 = q

t

,     k = 1,2,…,K   t = 1,2,…,T



v:e(w,v)=1 

x

wvt1

 = 0,   

w  s   w = 1,2,…,V   

t = 1,2,…,T

x

wvt(l+1)

  

b

 x

bwtl

,   

e(w,v) =1   w = 1,2,…,V 

v = 1,2,…,V   l = 1,2,…,L - 1   

t = 1,2,…,T



l

x

wvtl

  Mx

wvt

,  

e(w,v) = 1  w = 1,2,…,V 

v = 1,2,…,V   t = 1,2,…,T

x

wvt

  

l

x

wvtl

, 

e(w,v) = 1 w = 1,2,…,V 

v = 1,2,…,V   t = 1,2,…,T



t



l 

x

wvtl 

 c

wv

,  e(w,v) = 1   w = 1,2,…,V   v = 1,2,…,V.

Optimization

• The problem is linear, integer, and NP-

complete (equivalent to Steiner tree problem)

• To find optimal solutions solvers like CPLEX and 

GuRoBi can be used

• Heuristics can be used

Lecture Outline

• Introduction
• Integer Programming Formulations
• Cost Problem
• Network Design Problem
• Maximum Delay Problem
• Throughput Problem

• Multicast Packing Problem

• Concluding Remarks

Multicast Packing Problem 

(1)

• FA (Flow Allocation) problem
• Objective is to minimize maximum link 

congestion

• Classical problem related to multicasting 
• Flow formulation is used
• Level formulation can also be used

Multicast Packing Problem 

(2)

Given: network topology, link capacity, location of 

root, set of receivers, number of trees

Minimize: maximum link congestion

Over: multicast routing

Multicast Packing Problem 

(3)

indices
v = 1,2,…,V 

network nodes

e = 1,2,…,Elinks
d = 1,2,…,D

multicast demands (multicast 

group)

k = 1,2,…,K

d

receivers in multicast demand d

constants
a

ev

   = 1, if link e originates at node v; 0, otherwise 

b

ev

   = 1, if link e terminates in node v; 0, 

otherwise

Multicast Packing Problem 

(4)

constants
s

d

root node of multicast demand d

h

d

    volume of multicast demand d

M 

size of the link capacity module

variables
x

edk

  = 1, if multicast flow of multicast demand d to 

receiver  k uses link e; 0, otherwise (binary)

x

ed

 

= 1, if multicast demand d uses link e; 0, 

otherwise 

(binary)



maximum link congestion

Multicast Packing Problem 

(5)

objective
minimize 



constraints


e

 a

ev

x

edk

 – 

e

 b

ev

x

edk

 = 1,   

if v = s

d  

   v = 1,2,…,V    

d = 1,2,…,D

   

k = 1,2,…,K

d



e

 a

ev

x

edk

 – 

e

 b

ev

x

edk

 = –1,   

if v = k

   

v = 1,2,…,V  

 

d = 1,2,…,D

   

k = 1,2,…,K

d



e

 a

ev

x

edk

 – 

e

 b

ev

x

edk

 = 0,   

if v  s

d

,k

   

v = 1,2,…,V 

d = 1,2,…,D

   

k = 1,2,…,K

d

x

edk 

 x

ed

,    e = 1,2,…,E   d = 1,2,…,D   

k = 1,2,…,K

d



d 

x

ed

h

t 

 



,   

e = 1,2,…,E.

Optimization

• The problem is linear, integer, and NP-

complete

• To find optimal solutions solvers like CPLEX and 

GuRoBi can be used

• Heuristics can be used

Lecture Outline

• Introduction
• Integer Programming Formulations
• Cost Problem
• Network Design Problem
• Maximum Delay Problem
• Throughput Problem
• Multicast Packing Problem

• Concluding Remarks

Concluding Remarks

• Due to growing popularity of various streaming 

services in the Internet, the multicast 

transmission has been gaining much attention 

recently

• Modeling of multicasting makes use of traditional 

unicast multicommodity flows, however new 

models can be proposed

• Most of problems formulated in the context of 

unicast flows can be also formulated for 

multicast flows

Further Reading

• Minoli D. , IP Multicast with Applications to IPTV and Mobile DVB-H, 

John Wiley & Sons, 2008

• http://www.cisco.com/en/US/tech/tk828/technologies_white_paper09

186a0080092942.shtml

• Koch T. and  Martin A., Solving Steiner tree problems in graphs to 

optimality, Networks, vol.32, no. 3, 1998, pp. 207-232 

• Oliveira C.A.S., Pardalos P.M. and Resende M.G.C., Optimization 

problems in multicast tree construction, Handbook of Optimization in 

Telecommunications, Springer, 2006

• Wu C. and Li B., Optimal Rate Allocation in Overlay Content 

Distribution, in Proc. of the 6th Networking Conf., 2007, pp. 678-690

• Allen J., Kubat P., Reliable Video Broadcast via Protected Steiner 

Trees, IEEE Comm. Magazine, Vol. 48, No. 2, 2010, pp. 70-76

• Gouveia L., Luidi Simonetti L., Uchoa E., Modelling Hop-Constrained 

and Diameter-Constrained Minimum Spanning Tree Problems as 

Steiner Tree Problems over Layered Graphs, Mathematical 

Programming, 2009