ИЗВЕСТИЯ РАН. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2011, № 5, с. 60-73
= КОМПЬЮТЕРНЫЕ МЕТОДЫ
UDC 62-40
TOWARD MICROECONOMIC ALLOCATION OF RESOURCES IN MULTI-SERVICE OVERLAY NETWORKS © 2011 г. M. Analoui, M. H. Rezwani
Iran, Department of Computer Engineering, University of science ana technology (IUST)
Received January 24, 2010
The main challenge in overlay multicasting is designing self-organizing mechanisms that can be able to exploit the inherent selfishness of the end-user nodes in such a way that the aggregate outcome of the activity of individual nodes behaving toward their own self-interests still leads to maximization of the network's aggregate utility. We believe that the microeconomic theory is a good candidate to investigate this problem. Since each consumer in the economy acts as a selfish utility maximizer, the behavior of each end-host in the overlay ¡network can be mapped to that of a consumer in the economy. We present a competitive economical framework in which a number of independent services are provided to the users by a number of origin servers. Each offered service can be thought of as a good and the origin servers and the users who relay the service to their downstream nodes can thus be thought of as firms of the economy. Also, the end-hosts can be viewed as consumers in the economy. On joining to the overlay network, each end-host is provided with an income and tries to obtain the services. The mechanism tries to regulate the price of each ''.sw Wtfn'rran.ii:'/* a way that general equilibrium holds. For this properly to hold in ail generality, it tries to find a ¡we/or of prices such that demand of each service becomes equal to its supply. So, all allocations will be Pareto optimal in the sense that maximize welfare of the users.
Introduction. Overlay multicasting solution has recently gained attention as a general solution. The overlay multicasting can approximate many of the same design goals of IP multicasting. Further, they are easier to deploy than IP multicasting.
We consider a multi-service overlay network, in which a number of independent services are provided by their corresponding servers. On joining to the overlay network, the end-user tries to obtain each service either from the corresponding server or from any member of multicast group which receives services from that server. In this manner, for each offered service in the overlay network, we have a multicast group whose members form a tree rooted at the corresponding server. On the other hand, each end-user node in the overlay multicast network may belong to several multicast groups, i.e. several multicast trees. It has been a desirable and well-known design philosophy to use multi-rate transmission, where the receivers of the same multicast group can receive the services at different rates. Multi-rate transmission allows a receiver to receive the data at a rate that is proportional to its requirements and downloading capacity and also with uploading capacity of its parent node. A crucial problem with the overlay networks is that the end-user nodes are inherently selfish. The reason lies at the fact that the nodes belong to different administrative domains. The end-user nodes seek the complete freedom to choose the best line of action that maximizes their utilities. If their self-interests are not satisfied, they may not accept any proposed global optimization algorithm. In this context, the most important question is the following; "how should we exploit the inherent selfishness of the end-user nodes, so that the aggregate outcome of the activity of individual nodes behaving toward their own self-interests still leads to the network's overall utility maximization?"
We believe that the so called problem could be examined by microeconomic theory. Since each consumer in the economy is in fact a selfish utility maximizer, the behavior of the end-user node in the overlay network could be mapped to that of a consumer. From microeconomic theory point of view, the service provided by each multicast server, plays the role of the "good" in an economy. Hence, we can model the overlay network as the "overlay ecuiromy" in which several goods (multicast services) are provided. The overlay economy has two types of firm for each good: one is the origin server that provides the service (good) for the first time, and the other is the relaying nodes which relay the service to their downstream nodes. Also, by means of "equilibrium" concept from microeconomic theory, we can tune the allocated rates of the overlay nodes in such a way that welfare can be maximized in the overlay economy. To this end, "Pareto optimality" as the major mathematical tool in the microeconomic theory can be used.
1. Statement of the Problem. There are two kinds of methods for construction of multicast tree: delay-efficient methods and bandwidth-efficient methods. Examples of delay-efficient methods and band-
Fig. 1. Underlying physical topology in a typical network
width-efficient solutions include [1—5] respectively. The tree construction is the most important problem of the overlay multicast when the bandwidth is concerned. Finding the optimal bandwidth-efficient allocation in the overlay multicast can be understood as a utility-based resource allocation problem. Here, each user is associated with a utility, which is defined as an increasing, concave, and twice continuously differentiable function of the user's receiving rate. Cui et al. [6] have shown that finding among all possible trees the one with the optimal "maximum utility" rate allocation is NP-hard. Also, Zhu et al. [7, 8] have shown that finding "maxim urn-bandwidth" multicast tree in an overlay network with linear capacity constraints is NP-complete.
As mentioned earlier, a major problem toward structure establishment in the overlay multicast tree is nodes' selfishness. The selfishness of nodes hinders the expected self-optimization methods. To address node selfishness in the information collection step some works has employed game theory [9—13]. Also, a few proposals exist in which node selfishness in tree construction step has been investigated [13]. However, due to inherent limitations of game theory, the above proposals have to unrealistically assume that some global information about the network is available by the overlay nodes. A few other works has also been proposed to -regulate the node selfishness by means of distributed pricing [5, 14].
For any given overlay multicast tree, there exist a unique "maximum utility" rate allocation, at which the network resource utilization is Pareto-optimal [5]. So, we shall not try to solve the NP problem of tree ¡Wiistruction here. Instead, we will try to optimize the rate allocation within the given tree setting in a distributed vnd self-organized fashion based on the concept of "general equilibrium" theory of microeconomics. The original contributions of our work, differing from the aforementioned priced-based approaches is that we -present an economical framework in which each node is provided with an income. Based on demand-supply theory, an exchange economy is formed in which the firms are either origin servers or end-user nodes who forward the media content to other nodes. The consumers of this economy are all of the end-user nodes either who forward the service to their downstream nodes or who are leaf nodes in the overlay tree. Also, the goods of this economy are the services provided by origin servers. We apply the general equilibrium theory and achieve the equilibrium prices of the economy. We also take into account the price of underlying physical links in economical transactions. To the best of our knowledge, there has been no investigation on designing the multiservice overlay networks based on exchange economy and general equilibrium in the sense of the theory of demand-supply in microeconomics.
The remainder of this paper is organized as follows: Section 2 introduces the network model. Section 3 presents the definitions concerned to equilibrium in perfectly competitive market systems and proposes the competitive overlay market system. Section 4 presents the formulation of the competitive overlay economy based on the premises and notations of the previous sections. Finally, we discuss the related work in Section 5, and conclude in Section 6.
2. Network Model. We consider an overlay network consisting of Fend hosts denoted as V={1, 2, ..., V}. Let us suppose that the overlay network consists of N media services, denoted as N = {1, 2, ..., N}. So, there are N servers among Vhosts (N < V), each serve a distinct type of media service. We denote S = {sb s2, ., sN) as a set containing N servers. Suppose the network is shared by a set of N multicast groups. Any multicast group (multicast session) consists of a media server, a set of receivers, and a set of links which the multicast group uses. Any server belongs to anyone multicast group. Note that the links are the physical connections between nodes and routers, and routers and routers.
Let us suppose that the overlay network consists of L physical links, denoted as L = {1, 2, ..., L}. The capacity of each link, that is the bandwidth of each physical link l e L is denoted as c. We collect these capacities into a link capacity vector C = (cl, l e L). Fig. 1 is an example of underlying physical topology
Fig. 2. Overlay network consisting of two multicast groups
S2
0
Fig. 3. Tree of each multicast group
in a typical network. The physical network consists of eight links (L = 8) and the capacity vector, C, is shown in transposed form as follows
Fig. 2 shows an overlay network consisting of two multicast groups. In this example there is S = {sb s2} in which s1 (node 0) indicates one group and s2 (node 3) indicates second group. Solid lines indicate one group and dashed lines indicate the second group.
The overlay tree is built by formation of the multicast group gradually. The initial f
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.