Performance improvement of an optical network providing services based on multicast

Vincent Reinhard, Johanne Cohen, Joanna Tomasik, Dominique Barth, Marc-Antoine Weisser2013

TL;DR

This paper tackles the problem of efficiently placing expensive "branching routers" in optical networks to minimize bandwidth usage for recurring multicast services. They introduce a polynomial-time algorithm that optimally determines these router locations, leading to significant bandwidth savings for network operators.

What Problem Does This Paper Address?

Modern optical networks are increasingly supporting complex services beyond simple data transmission, like multicast services for virtual providers. While optical networks offer high bandwidth and low energy consumption, certain components like "branching routers" (which can duplicate data for multiple destinations) are more costly and power-hungry than standard "transparent" routers. Network operators want to maximize profit by offering quality services while minimizing infrastructure investment. This paper addresses the challenge of deciding where to place a limited number of these expensive branching routers within a multicast tree to achieve the lowest possible bandwidth consumption, especially for recurring multicast demands where the source and destinations are known in advance.

Methods

The core of the paper is a dynamic programming approach to solve the "Diffusing Nodes in Multicast Tree Problem" (DNMTP). They define a recursive method to compute optimal placements of branching nodes within sub-trees, working from the leaves of the multicast tree up to the root. This involves defining "windows" for each arc in the tree, which represent the path number, number of diffusing nodes, and the associated load (bandwidth consumption). The algorithm iteratively builds up solutions for larger sub-trees based on the solutions for smaller ones, ensuring optimality. They also compare two common methods for constructing the initial multicast tree: a shortest path (ShP) approach and a Steiner tree (StT) approach.

Datasets

Not discussed in the paper. The authors generated their own network topologies using the Waxman model (BRITE) for their experiments.

Key Insights and Ideas

  • Strategic placement is key: The exact location of a limited number of branching routers has a significant impact on overall bandwidth usage. Placing them strategically can drastically reduce costs.
  • Dynamic programming for optimality: A bottom-up dynamic programming approach, working from sub-problems (sub-trees) to the main problem (the entire multicast tree), is effective for finding the optimal placement of branching nodes.
  • Trade-off between ShP and StT trees: While shortest path trees are generally more efficient, Steiner trees can sometimes be more advantageous when branching nodes are introduced, especially in loosely connected networks. The "critical point" where one approach becomes better than the other depends on network characteristics and the number of branching nodes.
  • Network topology matters: The efficiency of branching node placement and the choice between ShP and StT trees are influenced by the network's average degree. Denser networks favor ShP, while sparser ones might benefit more from StT with branching nodes.

Key Results

  • The paper presents a polynomial-time algorithm for optimally placing a given number of branching nodes in a multicast tree to minimize bandwidth.
  • Their algorithm demonstrated significant bandwidth reduction compared to multicast trees without any branching nodes. For example, for ShP trees, they observed up to a 31% reduction with 4 branching nodes, and for StT trees, up to a 65% reduction.
  • The introduction of branching nodes can lead to substantial improvements, with StT trees showing a greater percentage improvement than ShP trees in many scenarios.
  • They identified a "critical point" in network characteristics (number of destinations, branching nodes, and average degree) where the utility of ShP versus StT trees shifts.

Limitations and Future Work

  • Heuristic for Steiner Tree: The paper uses a 2-approximable algorithm for the Steiner tree problem. They acknowledge that more precise Steiner tree algorithms might yield even better results.
  • Specific Network Types: The current work focuses on undirected graphs. Future work could explore optimal multicast deployment in oriented graphs or graphs with bounded treewidth.
  • Algorithm Implementation: The authors plan to implement and test more advanced algorithms to further validate their findings.
  • Real-world deployment: While the paper provides theoretical and computational insights, practical implementation and testing in real optical networks would be a valuable next step.

Summary updated

Abstract

Operators of networks covering large areas are confronted with demands from some of their customers who are virtual service providers. These providers may call for the connectivity service which fulfils the specificity of their services, for instance a multicast transition with allocated bandwidth. On the other hand, network operators want to make profit by trading the connectivity service of requested quality to their customers and to limit their infrastructure investments (or do not invest anything at all). We focus on circuit switching optical networks and work on repetitive multicast demands whose source and destinations are a ̀ priori known by an operator. He may therefore have corresponding trees “ready to be allocated ” and adapt his network in-frastructure according to these recurrent transmissions. This adjustment consists in setting available branching routers in the selected nodes of a predefined tree. The branching nodes are opto-electronic nodes which are able to duplicate data and re-transmit it in several directions. These nodes are, however, more expensive and more energy consuming than transparent ones. In this paper we are interested in the choice of nodes of a multicast tree where the limited number of branching routers should be located in order to minimize the amount of required bandwidth. After formally stating the problem we solve it by proposing a polynomial algorithm whose optimality we prove. We perform exhaustive computations to show an operator gain obtained by using our algorithm. These computations are 1 ar
BibTeX
@misc{reinhard2013performance,
  author = {Vincent Reinhard and Johanne Cohen and Joanna Tomasik and Dominique Barth and Marc-Antoine Weisser},
  title = {{Performance improvement of an optical network providing services based on multicast}},
  year = {2013},
}
Figure