A Low-Cost Algorithm for Multicast Routing

Pingyan Tan Frederick C. Harris, Jr.

Department of Computer Science University of Nevada Reno, Nevada 89557 fredh@cs.unr.edu

Abstract

• This paper presents a low-cost algorithm for multicast routing in computer networks.

• For performance evaluation, it is compared with Link-State multicast routing, which is a low-delay algorithm used by the Internet MOSPF protocol [1].

• This new algorithm supports the group concept and the unknown-destination delivery. It uses a minimum average distance method to select the forwarding links to achieve the low-cost goal.

• Another important feature of this algorithm is that no delivery tree has to be maintained, which eliminates the problem of memory and CPU congestion. Moreover, its computation time complexity is only linear in the group size.

• Simulation study shows that this algorithm can lower delay by as much as 40 percent for the same offered load, compared with the low-delay algorithm.

Outline of the Talk

• A brief review of routing

• A short description of our algorithm

• Presentation of a simple example

• The simulation model

• Simulation results

• Conclusions and Future Work

A BRIEF Review of Routing

• Routing is one of the most important aspects of computer networks.

• Multicast Routing can be defined as follows:

– Given a network (N, L), where N is a set of nodes and L a set of links,

– a source node s ∈ N,

– and a set of destination nodes G⊆N (the subset G is called a group),

∗ If 1 < |G| < |N|−1, then the problem is a multicast problem.

∗ If |G| = 1, it is a unicast problem and

∗ If |G| = |N| − 1, it is a broadcast problem.

A BRIEF Review of Routing (cont.)

• Algorithms for solving the multicast routing problem can be divided into two categories:

– Low-delay routing algorithms ∗ minimize the path length from the source to every destination node. This usually requires that the message be sent to every destination along the shortest path.

– Low-cost routing algorithms ∗ minimize the total traffic. The total traffic is equivalent to the total length of the paths in a delivery tree. (this is equivalent to solving for the Steiner Tree in a graph)

A Short Description of our Algorithm

• The main idea behind our algorithm is that we use the minimum average distance method to select the forwarding links.

– When a packet arrives at a node, the algorithm computes the average distance for each neighbor of the current node, where the average distance is the average distance from the neighbor node to all nodes in its responsible destination set.

– Then we select the neighbor node which has the minimum average distance to forward the packet.

– This procedure continues until all destination members are processed.

A Simple Example

• Assume that the source node is S,

• The destination set G = {E, F, M}.

• Each node in the graph has a letter which is the name of the node and numbers which represent an ordering of their neighbors.

• The result shows that the cost generated by our algorithm is 11, but with shortest path algorithm, the total cost is

A Simple Example: At node S

1. The packet is generated, R = ∞, and A_{S} = ∅.

2. G_{S} = {E, F, M}

3. N_{S} = {H, C, B, M}, A_{S} = ∅ D_{H} = {E} L_{H} = 3 + 2 = 5 D_{C} = {E, F } L_{C} = (3 + 4 + 2)/2 = 4.5 D_{B} = {F, M} L_{B} = (2 + 2 + 3)/2 = 3.5 D_{M} = {M, F } L_{M} = (4 + 0 + 2)/2 = 3

4. J = M, R_{J} = 2 —send packet p to M with p.radius = 2

5. G_{S} = {E}, A_{S} = {M} — go to step 3

3. N_{S} − A_{S} = {H, C, B}

D_{H} = {E} L_{H} = 5
D_{C} = {E} L_{C} = 7
D_{B} = ∅ L_{B} = ∞

4. J = H, R_{J} = 2 —send packet p to H with p.radius = 2

5. G_{S} = ∅ — stop

A Simple Example: At node M

1. G = {E, F, M}, R = 2, A_{M} = {S}

2. G_{M} = {M, F }

3. N_{M} = {B, S, F }, A_{M} = {S}, N_{M} − A_{M} = {B, F } D_{B} = ∅ L_{B} = ∞ D_{F} = {F } L_{F} = 2/1 = 2

4. J = F, R_{J} = 0 —send packet p to F with p.radius = 0

5. G_{M} = {M}, A_{M} = {S, F } — go to step 3

3. N_{M} − A_{M} = {B}

D_{B} = ∅ — stop

A Simple Example: At node H

1. G = {E, F, M}, R = 2, A_{H} = {S}

2. G_{H} = {E}

3. N_{H} = {E, S}, N_{H} − A_{H} = {E} D_{E} = {E} L_{E} = 2

4. J = E, R_{J} = 0 —send packet p to E with p.radius = 0

5. G_{H} = ∅ — stop

Simulation Studies

• Simulation studies were performed on our algorithm and the Link-State multicast algorithm described in [2], which is a low-delay algorithm.

• The Link-State multicast algorithm was chosen because it assumes roughly the same network information as does our algorithm and because it is the multicast version of the Internet standard protocol OSPF and is used in the experimental MOSPF protocol [1].

• Also, by comparing with a low-delay algorithm, we were able to study the impact on delay by traffic reductions.

Simulation Studies (cont.)

• We studied two relationships: – Delay vs. Offered load

– Utilization vs. Offered load

• Informal Definitions:

– Delay – the interval between the time a packet is generated and the time the pacet arrives at the destination.

∗ In a multicast environment, the delay is the average delay for all destinations.

– Offered Load – the rate of packet generation.

– Utilization – the average utilization of all links.

Simulation Testbed

• We randomly generated four networks with 40, 75, 97, and 123 nodes respectively.

• We selected parameters that were reasonable and made the Link-State Algorithm perform well.

– The key for the Link-State Algorithm is the group birth/death rate, since this causes a reconstruction of a group delivery tree.

• The first 3,000 packets (on average) received at each node were discarded to ensure that the network reaches a steady state;

• Then statistics are collected for the subsequent 10,000 packets (on average) received at each node.

A Low-Cost Algorithm for Multicast Routing 14

Results: Delay

A Low-Cost Algorithm for Multicast Routing 15

Results: Utilization

A Low-Cost Algorithm for Multicast Routing 16

Results: Reductions

Conclusions & Future Work

• It is known that a low-cost algorithm can reduce traffic and delay.

• This study shows that with our simple algorithm that requires only a linear time complexity, the delay can be substantially lower than that offered by always taking the shortest path, and yet this algorithm has all the elements that are required for multicasting, such as efficient computation, group addressing, and compatibility with unicasting.

• For more efficiency, we can allow the packet to carry a limited number of member addresses. Suppose we let the packet carry the addresses of the four most remote members, the radius R will be smaller and the algorithm will converge faster. As shown by Aguilar [3] the IP header usually has 40 bytes for optional use; therefore, such consideration is highly feasible.

Results(cont.)

Figure 1: Delays (lower message rates)

Figure 2: Delays for N = 40 Figure 3: Utilizations for N = 40

Multicast Routing Algorithm Requirements

• For a general multicast routing algorithm, some basic requirements should be considered:

1. The algorithm should be computationally efficient: an algorithm is not useful if it requires more than linear time to determine to which link a packet is to be sent. A constant-time complexity is preferred.

2. The algorithm should be scalable: it should not be heavily dependent on network size, group size, etc.

3. The algorithm should be compatible with unicast routing: it should not require excessive information when compared with unicast routing and should not change dramatically from the unicast environment.

4. The algorithm should seek a minimization of delay and traffic: these two goals may or may not conflict with each other. A minimum-cost tree may require packets to reach some member host along a path that is not the shortest path. But when the minimum-cost tree is utilized, the entire traffic is reduced, which may help reduce the delay.

Algorithm Description - Preliminaries

• To describe the algorithm, we first define the following variables:

G The destination set, that is, a group.

G_{i} Node i’s responsible destination set. It is the subset of G to which node i is responsible for delivering the message. N_{i} Node i’s open neighborhood set, i.e., all of node i’s neighbor

nodes except for node i itself. D_{j} Neighbor j’s responsible destination set. L_{j} Average distance from neighbor node j to j’s responsible

destination set. A_{i} The assigned neighbor set, i.e., the subset of G_{i} that has

been assigned to a link. d_{ij} The shortest path distance from node i to node j.

• In addition to the routing table of its own, each node also keeps the routing table of its neighbors, which is the common practice in the distributed Bellman-Ford algorithms [9]. As usual, the routing table at each node is assumed to contain the following entries that are related to our work:

• destination

• shortest distance

• next hop where “next hop” tells which link to take to reach the destination on the shortest path from the current node. We do not use the tabled next hop directly, but compute the next hop based on our algorithm. In the algorithm, each packet p is required to carry a small integer p.radius that is used in conjunction with the next-hop entries to compute the routing path.

An Informal Algorithm Description

• When a packet arrives at a node i and is addressed to group G, we give a condition to limit the size of the destination set – that is, to decide to which members of group G should be sent the packet from the current node i.

• We use a variable p.radius as the condition. The value of p.radius is the path distance between the current node and the most remote destination member. That is, the current node i sends packets only to those members (in G_{i}) whose shortest-path distance from node i is less than or equal to p.radius.

– If node i is the source node, then we set p.radius = ∞. This means that at the beginning, we consider all members of the group G as the destination set.

– If node i is not the source node, the packet must have come from its parent node; the packet then carries a radius with it which was computed at the parent node.

The Formal Algorithm Description

Suppose packet p arrives at node i via a neighbor node k or is generated at node i. The description of the algorithm is as follows:

1. If i is the source node,

R = ∞; A_{i} = ∅; else

R = p.radius; A_{i} = {k};

If R = 0, stop.

2. Compute node i’s responsible set

G_{i} = {g | g ∈ G, d_{ig} ≤ R and g ≠ i}

3. For each j ∈ N_{i} and j ∉ A_{i}, compute j’s destination set

D_{j} = {g|g ∈ G_{i} and d_{jg} < d_{ig}} (1)

and the average length

L_{j} = (d_{ij} + _{g∈D_{j}}^{∑} d_{jg} − L̂_{j})/|D_{j}| (2)

where L̂_{j} is the sum of the overlapping next-hop links, defined as

L̂_{j} = _{n_{jk}>1}^{∑}(n_{jk} − 1)l_{jk}

where n_{jk} is the number of members in D_{j} that will be sent via link jk from node j to node k, and l_{jk} is the length of the link. If (all D_{j} = ∅) or (N_{i} = A_{i}), stop.

4. Let J be the subscript such that

L_{J} = min_{j∈N_{i},j∉A_{i}} L_{j}

and define

R_{J} = max_{g∈D_{J}} d_{Jg} (3)

Send a packet with radius R_{J} to node J.

5. G_{i} = G_{i} − D_{J} A_{i} = A_{i} ∪ {J}

If G_{i} = ∅

stop else

go to step 3. □

References

[1] C. Huitema, Routing in the Internet, Prentice Hall PTR, Englewood Cliffs, New Jersey 07632, 1995.

[2] S. E. Deering, Multicast routing in a datagram internetwork, PhD thesis, Dept. of Electrical Engineering, Stanford University, December 1991.

[3] L. Aguilar, “Datagram routing for internet multicasting,” in Proc. ACM SIG-COMM ’84 Communications Architectures and Protocols, pp. 58–63. ACM, June 1984.

[4] F. Hwang, D. Richards, and P. Winter, The Steiner Tree Problem, volume 53 of Ann. Discrete Math., North-Holland, Amsterdam, 1992.

[5] K. Bharath-Kumar and J. M. Jaffe, “Routing to multiple destinations in computer networks,” IEEE Trans. Comm., vol. COM-31, no. 3, pp. 343–351, March 1983.

[6] G. I. Stassinopoulos, “Optimal dynamic routing in multidestination networks,” IEEE Trans. Comm., vol. COM-35, no. 4, pp. 472–475, April 1987.

[7] G. I. Stassinopoulos and M. G. Kazantzakis, “A computationally efficient iterative solution of the multidestination optimal dynamic routing problem,” IEEE Trans. Comm., vol. 39, no. 9, pp. 1370–1378, 1991.

[8] N. E. Belkeir and M. Ahamad, “Low cost algorithms for message delivery in dynamic multicast groups,” in Proc. 9th Intl. Conf. Distributed Computing Systems, pp. 110–117. IEEE, June 1989.

[9] D. Bertsekas and R. Gallager, Data networks, Prentice-Hall, Inc., 2nd edition, 1992.

[10] R. Sedgewick, Algorithms, Addison-Wesley Publishing Company, Inc, New York, 2nd edition, 1989.