Mathematical Aspects of Network Routing Optimization by Carlos A. S. Oliveira & Panos M. Pardalos

Author:Carlos A. S. Oliveira & Panos M. Pardalos
Language: eng
Format: epub
Publisher: Springer New York, New York, NY

8.2 Point-to-Point Connection and Multicast

The common definition of the multicast routing problem states it as finding routes from one source to several destinations. This is also commonly referred to as point-multipoint routing. On the other hand, situations arise when there may be multiple sources of available data. It is interesting to pose the question of how to minimize data transmission costs when the problem has this special structure. In this chapter, we study a special version of this general problem, called the PPC problem.

More formally, multicast routing is defined in this chapter as the process of sending information from one or more sources to multiple receivers in a network, with the use of a simple “transmit” operation (see Kurose and Ross [1999]). In such situations, three types of nodes can be distinguished, namely source nodes, from which data originates; destination nodes, which receive data; and link nodes.

All source, destination, and link nodes can be used to route information from sources to destinations. Thus, depending on the structure of the network, there is a large number of possibilities on how to route data. Consequently, optimization problems may be formulated based on the many possibilities and on particular optimization goals.

In the PPC, we are given a graph G = (V, E) and two sets: the set S of sources and the set D of destinations, each with the same number of elements. A feasible solution for the problem is one in which each source is connected to at least one destination. Each arc in the network has an associated cost, and the cost of a solution is given by the sum of all costs for the arcs used to connect sources to destinations. The objective of the problem is finding a feasible solution with minimum cost.

Similar to the Steiner tree problem in the PPC, we are interested in a subset of edges forming a forest, that is, no cycle is accepted in the final solution. The sources and destinations play the role of the set of required nodes in the Steiner tree problem. Other nodes in the network can act as transshipment nodes for traffic origination at the sources, which are represented in the Steiner problem as Steiner nodes.

In the remaining of this chapter, we concentrate our attention on algorithms for the PPC problem. After formalizing the problem in the next section, we present a parallel asynchronous methodology to solve it, called A-Teams. We also demonstrate an implementation of this methodology and present computational results obtained by the algorithm.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.