Article Preview
Top1. Introduction
The numerous internet applications involving several receivers have triggered the notion of communication groups (Kou, Markowsky, & Berman, 1981; Kompella, Pasquale, & Polyzos, 1993; Chen, Gunluk, & Yener, 2000), where the standard unicast routing protocol has shown its incapacity to manage the multi-source side of these applications. In fact, the unicast protocol builds applications involving a large number of network points, giving rise to the new mode of multicast communication (Kuipers & Van Mieghem, 2002; Wang, Liang, & Jan, 2002; Kodialam, Lakshman, & Sengupta, 2003).
Multicasting is an effective method of routing information flow from multiple sources to multiple destinations. One source transmits the data simultaneously to receivers of an identified group (multicast group). Its effectiveness lies in the conservation of the bandwidth and the flows routing in minimal time. Indeed, in unicast, each recipient has a dedicated transmission from the source. In broadcast communication, every part of the network receives the data stream, even if it is not concerned by this data. Multicast communication adopts a cleverer approach, where a single packet is sent from the source and duplicated only on branches going to the concerned receivers.
Whereas the unicast context requires finding an optimal path, the multicast context requires finding an optimal forest. Other aspects have added some difficulty in the support of multicast, we cite:
- •
Internet applications are multimedia, multiple quality of service (QoS) criteria, then multiple metrics.
- •
Multiple providers are considered in each session, which mean multiple sources.
- •
Several sessions are launched simultaneously from the same source.
- •
Several multicast groups can compete on all sessions.
We focus here, on multiple sources multicast transfer in the context of multi-flow and multi-session of each provider.
Contribution: This paper proposes a new linear programming model which ensures load balancing between sources, by enforcing equity between those providing different flows, and by considering thoroughly multicast, multi-source and multi-flow aspects. Our linear integer program integrates the multiple QoS criteria corresponding to the respective multiple sources, falling down into a multi-criteria decision problem, which is than transformed into a mono-objective problem, thanks to the ordered weighted average (OWA) aggregators, where the weights are fixed such that the equity is mathematically guaranteed.
After a brief description of the related works in section 2, we introduce the MILP model of multicast diffusion in Section 3. Section 4 introduces basic concepts on multi-criteria optimization, by detailing the OWA operator and equity properties. In Section 5, we present our load balancing approach in multicast communication, while showing, through an example, the interest of multi-criteria compared to the single-criterion optimization. Section 6 details our experimental results. Finally, Section 7 concludes this paper by drawing perspectives.
Top2. State Of The Art
The basic problem underlying our main problem of load balancing between sources, is the multicast context, which requires finding an optimal forest instead a simple single optimal path. The usual technique that solves this problem is to find, in the network graph, a partial minimum spanning tree covering the multicast group, well known as the Steiner Tree Problem (Kou, Markowsky, & Berman, 1981), which is an NP-complete problem (Kompella, Pasquale, & Polyzos, 1993). But, many approaches to solve this problem have been proposed in the literature: exact approaches (linear relaxation, branch and bound, enumerative approaches, etc.) and heuristics. For details, see (Chen, Radhakrishnan, Dhall, & Karabuk, 2013). The technique of routing based on the construction of the Steiner Tree has shown its limits in new Internet applications such as teleconferencing, distance learning, cooperative applications, network games, scattering radio and television, etc., for the following reasons: