JP5280933B2 - Server parallel distribution system and method and program - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To improve network throughput by, in order to avoid congestion, effectively balancing a link load to level "link utilizations" when performing streaming distribution of super high definition content. <P>SOLUTION: In a data parallel distribution system wherein a plurality of mirror servers are disposed on a network and a plurality of servers are used for distribution responding to each distribution request to reduce a transfer bit rate of each flow, a server disposition designing device 102 and a server selection designing device 103 are provided, and nodes where servers are to be disposed are selected so as to minimize the maximum link utilization. Thus a total distribution request amount (network throughput) allowable in the entire network is maximized. <P>COPYRIGHT: (C)2011,JPO&amp;INPIT

Description

  The present invention relates to a technique for distributing one moving image in parallel using a plurality of servers in order to distribute the load of a distribution server when distributing moving image streaming data or the like in a network such as the Internet. The present invention relates to a technique suitable for determining how a distribution server can be arranged at a node in a network to achieve efficient load distribution.

  In recent years, the number of users who use video streaming services such as YouTube (registered trademark) on the Internet has increased rapidly. Users demand for high-quality video distribution is high, and it is expected that HDTV (High Definition TV) having a bit rate of about 25 Mbps will be available on the Internet in the future. Further, UHDV (Ultra High Definition Video) with further improved quality has been proposed by the Japan Broadcasting Corporation.

  The uncompressed bit rate of the UHDV image is 24 Gbps, and it has a high rate of 180 to 600 Mbps even after compression.

  Such a high-definition video streaming service using HDTV, UHDV, or the like is considered to be one of important services on the Internet. However, the transmission rate of the generated traffic flow is very high, which causes a server or link congestion.

  Hereinafter, the maximum value of the total traffic demand between the arrival and departure nodes that can be carried in the entire network (NW) is defined as NW throughput, and the congestion in the network will be described.

  If a particular “link utilization” is exceptionally high compared to other links, that link becomes a bottleneck and many links remain at low utilization resulting in lower NW throughput and congestion. Will be invited.

  In order to avoid such congestion, it is important to equalize the “link usage rate” by distributing the link load effectively when streaming high-definition content.

  In OSPF (Open Shortest Path First), the standard AS (Autonomous System) routing protocol of the Internet, the reciprocal of the link capacity recommended by Cisco, or the same fixed value for all links is used as the link weight. The set minimum cost route is generally used.

  However, in OSPF, in any case, since a value unrelated to the “link usage rate” is used for the link weight, the link load cannot be leveled by route setting.

  A technology that optimally designs link weights to “minimize the maximum link usage rate” for statically given AC demand matrix has also been proposed, but for all services provided on the Internet, It is difficult to estimate the AC demand matrix in advance, and it has not become widespread.

  In addition, traffic engineering that optimizes the route between each incoming / outgoing node has been widely studied so that the link usage rate is leveled, but the number of routes to be managed increases in proportion to the square of the number of nodes. In addition, it has not become widespread, for example, because it is necessary for all routers in the NW to have a function of switching the route for each pair of arrival and departure nodes. Therefore, it is difficult to distribute the link load by controlling the content distribution route.

  By the way, as an effective technique for distributing the load on a server, for example, a CDN (Content Delivery Network) described in Non-Patent Document 1 or the like is widely known.

  In this CDN, a CDN provider independent of ISP (Internet Service Provider) prepares a large number of servers on NWs of a plurality of ISPs, and copies of contents are arranged on these servers. Distribute the load.

  However, CDNs are installed and operated by a CDN operator independent of ISP, so it is difficult to use NW information such as NW topology and route, and it is difficult to level NW link usage rate. is there.

  In addition, since the CDN always selects one server for each distribution request, the bit rate of each generated distribution flow cannot be reduced, and even if NW information can be used, The utilization leveling effect is limited.

  In order to “level the link usage rate”, it is important to reduce the bit rate of the streaming distribution flow of the ultra-high definition content. For this purpose, it is effective to perform parallel distribution using a plurality of servers for each distribution request.

  For example, by using two servers for one distribution session, the transfer rate of each generated flow can be reduced to half.

  “BitTorrent” (registered trademark), which is a P2P file sharing service, also uses such a parallel distribution technique, but each user needs to upload a data segment to another user while receiving the distribution.

  Therefore, the performance of BitTorrent (registered trademark) greatly depends on the user's behavior and the uplink access line rate. However, the distribution bit rate of ultra-high-definition content is extremely large, and there are many users who have a large capacity uplink access link, and it cannot be expected to use these services stably.

  Therefore, it is difficult to provide ultra high-definition streaming distribution on a P2P file sharing system such as BitTorrent (registered trademark).

  In order to alleviate the impact of these service flows on the NW, level the link usage rate, and improve the NW throughput, ISPs that can use NW information such as the NW topology can install multiple servers on their NW. It is necessary to install and perform parallel delivery from multiple servers.

A. Su, D.D. Coffnes, A.D. Kuzmanovic, and F.K. Bustamante, “Drafting Behind Akamai (Travelity-Based Detouring)”, ACM SIGCOMM 2006.

  Regarding parallel distribution, for example, there is one described in Japanese Patent Application No. 2008-054321 by the present inventors. In this technology, for example, in a streaming streaming distribution, in a distribution form in which moving image data is downloaded in parallel using a plurality of servers storing the requested moving image content in response to one distribution request, an average distribution flow In order to shorten the hop length, a server is preferentially allocated to a node having a small average hop length to other nodes.

  For each distribution request, in addition to the nearest server with the shortest hop length, a server existing within a position within plus B hops from the number of hops is also selected as the distribution server. Furthermore, in order to increase the effect of parallel distribution, super hub nodes connected to most other nodes are arranged in a plurality of networks, and servers are installed in these super hub nodes.

  Thereby, it is possible to reduce the bias of the link load while suppressing the average hop length of the distribution flow in the parallel distribution of data.

  As described above, in the technique described in Japanese Patent Application No. 2008-054321 described above, “average link load” and “link load variation coefficient” are used as evaluation scales when selecting a distribution server.

  However, since the NW throughput is determined by the maximum link usage rate, it is important to minimize the maximum link usage rate and level the link usage rate. However, in the technique described in the above-mentioned Japanese Patent Application No. 2008-054321. The “link usage rate” is not considered.

  The problem to be solved is that, in the prior art, for example, the link usage rate is not considered in the arrangement and selection of servers that distribute data such as streaming of ultra-high definition content in parallel.

  The object of the present invention is to solve these problems of the prior art, and to arrange and select servers that perform parallel data distribution, and to minimize the maximum link usage rate and level the link usage rate, thereby greatly increasing the NW throughput. It is to improve.

  In order to achieve the above object, in the present invention, for example, in streaming streaming distribution, for a single distribution request, distribution in which moving image data is downloaded in parallel using a plurality of servers storing the requested moving image content The embodiment is characterized in that a node on which a server is arranged is selected so as to maximize NW throughput (total amount of distribution requests that can be accommodated in the entire network) by minimizing the maximum link usage rate.

  According to the present invention, NW throughput (total amount of distribution requests that can be accommodated in the entire network) is greatly improved by arranging and selecting servers that perform parallel data distribution so as to minimize the maximum link usage rate. It becomes possible to make it.

It is a block diagram which shows the structural example of the data parallel delivery system which concerns on this invention. It is an algorithm which shows the example of a process sequence which concerns on this invention of the server arrangement | positioning design apparatus in FIG. 2 is an algorithm showing a first processing procedure example according to the present invention of the server selection design apparatus in FIG. 1. It is an algorithm which shows the 2nd process sequence example which concerns on this invention of the server selection design apparatus in FIG. It is explanatory drawing which shows the distribution state of the node order according to the topology of the network used as the process target of the data parallel delivery system which concerns on this invention. It is explanatory drawing which shows the topology example of the network used as the process target of the data parallel delivery system which concerns on this invention. It is explanatory drawing which shows the example of a characteristic of each network used as the process target of the data parallel delivery system which concerns on this invention. It is explanatory drawing which shows the 1st effect example of the process by the data parallel delivery system which concerns on this invention. It is explanatory drawing which shows the 2nd effect example of the process by the data parallel delivery system which concerns on this invention. It is explanatory drawing which shows the 3rd effect example of the process by the data parallel delivery system which concerns on this invention. It is explanatory drawing which shows the 4th example of a process by the data parallel delivery system which concerns on this invention. It is explanatory drawing which shows the list of the backbone networks used as the process target of the data parallel delivery system which concerns on this invention.

Hereinafter, embodiments for carrying out the present invention will be described with reference to the drawings. 1 shows an example of the configuration of a data parallel distribution system according to the present invention, 101 the present invention according the input condition data (the server installation number S, NW topology T, the distribution request amount ratio R _n of each node, An input data setting device for inputting the transmission capacity C _e of each link and the cost c _e ) of each link, a server arrangement design device 102 for selecting nodes on which S servers are arranged, and 103 for parallel data distribution A server selection design apparatus 104 that selects a server to be used, and a design result output apparatus 104 that outputs the processing results of the server arrangement design apparatus 102 and the server selection design apparatus 103.

  The data parallel distribution system in FIG. 1 has a computer configuration including a CPU (Central Processing Unit), a main memory, and the like. As means for executing programmed computer processing, an input data setting device 101, a server layout design device 102, and Each of the server selection design device 103 and the design result output device 104 is provided. The server selection design device 103 and the design result output device 104 constitute server arrangement selection means according to the present invention.

The input data setting device 101 receives the number of installed servers S, the NW topology T, and the distribution request amount ratio R _{n of} each node, which are input via an input device such as a keyboard or mouse (not shown) or a data communication device. Each input data such as the transmission capacity C _e of each link and the cost c _{e of} each link is acquired and stored in a storage device (not shown).

  The NW topology T is represented by a matrix having a scale of N nodes, and its element ij (the matrix element in the i-th row and j-th column in the topology matrix T and the link position connecting the node i and the node j) is , A binary variable that takes “1” when a link exists between the node i and the node j and takes “0” when the link does not exist.

Distribution request amount ratio R _n of node n, the distribution demand arising from node n, represents the percentage of the distribution request amount generated across NW, it takes a value of 0.05, or the like.

Cost c _e of each link is the weight used in the routing, for example, a "1" in the case of using a minimum hop path, also when setting the path to through a large capacity link aggressively Is set to the inverse of the link capacity.

  The server arrangement design device 102 uses the input data to select S servers so that the maximum link usage rate is minimized when only one server with the minimum cost of the via link is used for each node. Specify the node to be placed.

  When a plurality of servers are used for distribution for each node, the server selection design device 103 specifies a server set used for distribution of requested data so that the maximum link usage rate is minimized.

  The design result output device 104 displays the result of specifying the node where the S servers are placed by the server placement design device 102 and the result of specifying the server set for data distribution by the server selection design device 103 as a display device, storage device, or Output via a data communication device.

  With such a configuration, the data parallel distribution system in FIG. 1, for example, distributes video data in parallel using a plurality of servers storing the requested video content in response to a video streaming distribution request. In the embodiment, the node on which the server is arranged is selected so as to maximize the NW throughput (the total amount of distribution requests that can be accommodated in the entire network) by minimizing the maximum link usage rate.

  Hereinafter, the content parallel distribution technology for maximizing the NW throughput will be described in detail in the order of [Precondition], [Optimal server layout design method], [Optimal server selection design method], and [Evaluation results]. explain.

First, [Precondition] will be described.
[Prerequisites]:
NW the number of nodes of N, bidirectional link number is M, the transmission capacity of link e and C _e.

  It is assumed that mirror servers are arranged in S nodes among N nodes, and copies of all ultra-high-definition contents are prepared in these S mirror servers. For this reason, when designing and evaluating a distribution system, it is not necessary to consider the request generation ratio for each content.

  As a route setting method, there are two cases where the link weight is set to “1” (denoted as “min.hop”) and is set to the reciprocal of the link capacity recommended by Cisco (registered trademark) (denoted as “inv.cap”). Assume that Dijkstra's minimum cost path is used for each of the two weighting methods.

  Note that “min.hop” corresponds to a case where the shortest hop route is used, and “inv.cap” corresponds to a case where a link having a large capacity is actively used.

  When there are multiple minimum cost routes between the same arrival and departure nodes, it is also possible to implement a mode in which traffic is divided and sent equally to these multiple routes, but when packets belonging to the same flow pass different routes, Because the receiving terminal needs extra processing such as sorting and the communication quality is not stable, in fact, the route with the youngest router port identification number is selected. Often only one minimum cost path is used.

  Therefore, in the “evaluation result” described later, an evaluation in which one route is selected at random for each node pair is repeated 100 times, and all the average values are evaluated.

The total traffic volume of the entire NW, that is, the average traffic demand per unit time generated from all N nodes is V (bps), and further the average traffic per unit time generated from node s to node d _{Let the} amount be v _sd (bps). Further, the ratio of v _sd to V is r _sd (r _sd = v _sd / V).

Given the NW topology, link capacity, and static link weights for route setting in addition to the average traffic volume v _sd , the average usage rate u _e of each link e is unique according to the following equation (1). Determined.

ただし、Ｎをノード集合、ｘ（ｓ，ｄ，ｅ）はノードｓからノードｄに至る配信経路がリンクｅを通る場合に「１」を、通らない場合に「０」をとる２値変数とする。

However, N is a node set, and x (s, d, e) is a binary variable that takes “1” when the distribution route from the node s to the node d passes through the link e, and takes “0” when it does not pass. To do.

Let ε be the link that maximizes the link usage rate. When a route and an AC demand matrix r _ij (traffic demand amount from node i to node j) are given, the link ε having the maximum link usage rate is always the same link even if the traffic demand average V changes. This link ε becomes a bottleneck link that determines the maximum value V _max (NW throughput) of the average traffic demand V that can be achieved in the entire NW.

In this example, V _max is defined as the value of the traffic demand average V when “u _ε = 1” in the equation (1) expressed by the above equation (1).

Let R _n be the ratio of the distribution request amount generated from each node n to the distribution request amount of the entire NW. In this example, it is assumed that the static value is given as the ratio R _n.

In general, it is difficult to estimate the AC demand matrix r _ij for any service that occurs on the Internet, but it is relatively easy to estimate the ratio R _n limited to ultra-high-definition streaming delivery. Seem.

The ISP cannot directly control the ratio R _n described above, but if the requested content exists in multiple servers, the ISP controls the AC demand matrix r _ij by the server placement method and the server selection method. Is possible.

That is, even when the route is statically set using a fixed link weight, the NW throughput V _max can be optimized by optimizing the server arrangement and the server selection.

Therefore, in this example, a server arrangement design method and a server selection method for parallel distribution that maximizes V _max , that is, minimizes the maximum link usage rate, are examined.

  When performing parallel distribution of contents, an ISP needs to arrange a plurality of mirror servers in advance for its own NW node set.

  Further, it is necessary to select a server to be used for each distribution request.

  The usage rate of each link depends not only on the server location but also on the server selection method for each delivery session. Therefore, in order to design the server so that the maximum link usage rate during parallel delivery is minimized, And server selection must be optimized at the same time.

  However, since the number of combinations is enormous and it is difficult to obtain a solution in a realistic time, in this example, each design problem is separated into [Optimal Server Placement Design Method] and [Optimum Server Selection Design Method]. To consider.

First, the “optimum server layout design method” will be described.
[Optimum server layout design method]:
In general, given the transfer cost between nodes, the NW topology, the amount of demand generated at each node, and the number of installed nodes K, the problem of selecting the facility location of K that minimizes the total transfer cost is UKM ( It is known as Uncapacitated K-Media), and since it is NP-hard, various approximate solutions are being studied.

  These design methods aim at minimizing the total transfer cost, but in this example, an approximate optimal placement method for servers that minimizes the maximum link usage rate using the greedy calculation method is newly examined.

In a state where _j servers are arranged in the node set N _j , the maximum link usage rate when a server is arranged in any node i not included in the node set N _j is represented by u _max (N _j , i). And

  In order to calculate the link usage rate, it is necessary to determine the server to be used for each distribution for convenience. Therefore, it is assumed that one server having the minimum distribution cost (total of the costs of the via links) is used.

That is, for any node d, when the server having the smallest delivery cost δ _sd from each server s included in the server set S = {N _j + i} is σ, “r _σd = 1”. On the other hand, “r _sd = 0” is set for all s of “s ≠ σ”.

At this time, the usage rate of each link is calculated from the equation (1) expressed by the above equation 1, and the maximum value u _max (N _j , i) is obtained. However, the value of the total traffic volume V of the entire network is set to “V = 1” because it is irrelevant when obtaining a link having the maximum usage rate.

Then, the maximum value of the link utilization for all nodes i of "I∈N\N _{j" u} max _(N j, i) is calculated, and place the j + 1-th server to a node that this value is minimum To do.

  By repeating this process a given number of times S, the nodes where S servers are arranged can be identified.

  FIG. 2 shows a procedure (server optimal placement algorithm) for specifying a node on which such S servers are placed. When the CPU executes this server optimum arrangement algorithm, server arrangement nodes are obtained as a set S.

Next, the “optimum server selection design method” will be described.
[Optimum server selection design method]:
The collection of servers that use the user of the delivery request belonging to the node d and S _d. This server set S _d is optimally designed in advance, and all servers included in the obtained set S _d are always used for delivery to the node d.

  First, when a single server is used for distribution to each node, an optimum server that minimizes the maximum link usage rate for a given server arrangement is selected. Then, the obtained server selection is set as an initial state, and the optimum server in parallel distribution is selected so as to reduce the maximum link usage rate.

In the initial state, the server σ _d having the smallest distribution cost δ _sd is set as the distribution server for the node d (S _d = {σ _d }). Hereinafter, this state is referred to as minimum cost single server delivery (MSD: Minimum cost Single Delivery).

The usage rate of each link in this MSD is calculated from Equation (1) shown in Equation 1 above, and the link ε having the maximum usage rate and its usage rate u _max are obtained.

Then, for each node d belonging to the distribution destination node set D _ε through which the path ε passes, the maximum link usage rate u _{max, d, k} when the server used for distribution is changed to each other server _k is obtained. The minimum server k ^* is changed to the distribution server for the node d (S _d = {k ^* }).

This process is repeated for all nodes belonging to the node set D _ε, and as long as the maximum link usage rate u ′ _max obtained as a result is lower than the value u _max before the correction, the correction of the used server is repeated. .

  The optimal single server selection state obtained in this way is called optimal single server delivery (OSD: Optimum Single Delivery).

  FIG. 3 shows a procedure (server optimal selection algorithm) for selecting such an OSD server. When the CPU executes this server optimum selection algorithm, OSD server selection can be performed.

  Then, with the OSD as an initial state, an optimal server selection that minimizes the maximum link usage rate in parallel distribution is designed by adding a server used for distribution to each node.

The number of servers used for distribution to the node d is n _d, and traffic is evenly distributed to the n _d distribution flows used for distribution to the node d.

The usage rate of each link in the OSD is calculated from the equation (1) shown in Equation 1 above, and the link ε having the maximum usage rate and the usage rate u _max are obtained.

Then, for each node d belonging to the destination node set D _epsilon through which acquired the link epsilon path, in the case of n d _<S is the respective server k servers set S\S _d unused 1 One only the maximum link utilization _{u max} when added to _{S d, d, k} is a server ^{k *} that minimizes, to add to _{S d.}

This processing is repeated for all the nodes belonging to the delivery destination node set _Dε, and as long as the maximum link usage rate u ′ _max obtained as a result is lower than the value u _max before correction, additional processing of the use server Repeat.

  The optimal multiple server selection state obtained as a result of this is called optimal parallel delivery (OPD: Optimum Parallel Delivery).

  FIG. 4 shows a procedure (addition server selection algorithm) for selecting such an additional server of OPD. When the CPU executes this additional server selection algorithm, it is possible to select servers to be distributed in parallel.

  Hereinafter, the effect of the parallel distribution server selected in this way will be described as [Evaluation Result].

[Evaluation results]:
First, the NW topology used for evaluation will be described.

[NW topology used for evaluation]:
Of the backbone NWs of commercial ISPs whose topology and link capacity are disclosed on the CAIDA Web page, 23 NWs with 20 or more nodes are used for evaluation.

  In FIG. 12, the number of nodes N of these 23 NWs, the number of bidirectional links M, the average node order g, the maximum node order G, and the high-order node number ratio R are summarized.

However, R is defined by a value obtained by dividing the number of nodes having an order larger than the average order g by N. Also, the normalized maximum order G _r is defined as G _r = G / N. This means that a hub node connected to a large number of nodes exists in an NW with a large G _r , and a large number of high-order nodes exist in an NW with a large R.

  Here, for convenience, the 23 NWs are classified into three topology types of Star type, H & S type, and Ladder type according to the following rules.

  First, NWs satisfying “Gr <0.4” and “g <3” are classified into the Ladder type.

For each NW of 23, a scatter diagram of the normalized maximum order G _r and the average order g is shown in FIG. 5 (a). In the figure, NWs existing in the region indicated by the solid line frame on the lower left are Ladder type. Although it will be classified, 11 NWs fall under this category.

  Then, among the NWs not classified into the Ladder type, NWs with “R ≧ 0.25” are further classified as H & S types, and NWs with “R <0.25” are classified as Star types.

  FIG. 5B shows a scatter diagram of the maximum node degree G and the high-order node number ratio R with respect to 12 NWs not classified into the Ladder type. Each of the six NWs is classified into a Star type and an H & S type.

  FIG. 6 shows an example of an NW topology classified into each of three NW types. These three NWs all exist in the United States, but it can be confirmed that the shapes differ greatly depending on the NW type. Each NW type has the following tendency.

  As shown in FIG. 6A, the Star type has a structure in which a very small number of high-order nodes (hub nodes) are connected to a large number of low-order nodes. Most of the nodes other than the hub node are often connected to only one of the hub nodes, and there are many nodes having the degree “1”. However, only the NW12 (LL) is exceptionally in a shape in which a large number of nodes are connected to a plurality of hub nodes as shown in FIG. 6B.

  Since this Star type can reach other nodes with a small number of hops via the hub node, the hop distance between the nodes tends to be short, but the load tends to concentrate on the hub node.

  As shown in FIG. 6C, the H & S type has a larger number of hub nodes than the Star type NW, and these hub nodes tend to be interconnected. Since many low-order nodes have a structure connected to one or more hub nodes, they are called hub and spoke types. It is known that an air route network is in this form. Like the Star type, the hop distance between nodes tends to be small, but the load tends to concentrate on the hub node.

  As shown in FIG. 6D, the Ladder type has a topology structure in which a hub node does not exist and several loops are combined. While the total link length can be suppressed, the hop distance between nodes tends to be long. It is known that the highway network is in this form.

In this example, there is no regional bias in the demand for rich content delivery, the delivery request ratio R _n generated from the node n, matching ratio p _n for population overall NW population node n to accommodate to accommodate Assume that.

In FIG. 7 (a), of the NW 23, the correlation coefficient of the degree _{g n} and population ratio _{p n} nodes: the (CC Correlation Coefficient), shows a state plotted against the number of nodes N .

  From FIG. 7A, in many NWs, there is a positive correlation between the degree of each node and the population ratio, and it can be confirmed that the degree of the nodes arranged in the big city tends to increase.

  However, the strength of the correlation varies greatly depending on the NW, and the Star type NW has a low degree of correlation with many Star type NWs because the majority of nodes have a low order.

  FIG. 7B shows a state in which the average value of the shortest hop distance between all the nodes of each NW of 23 is plotted against the number N of nodes.

  From FIG. 7B, it can be confirmed that the average node distance of the Ladder type NW tends to be long, and that the average hop distance tends to increase gradually as the number N of nodes increases.

  On the other hand, the average hop distance between the Star-type NW and the H & S-type NW is independent of the NW scale, and the presence of a high-order hub node greatly contributes to the reduction of the inter-node distance.

  Next, the effect of parallel distribution will be described.

[Performance evaluation of parallel delivery]:
In this example, the effect of parallel distribution (OPD) when the server selection design apparatus 102 and the server selection design apparatus 103 in FIG.

When the traffic amount ratio r _ij between each node pair (node i, node j) is given, the usage rate u of each link is uniquely determined with respect to an arbitrarily determined static link weight.

Therefore, even if the traffic volume V (bps) changes resulting from distribution request generated across NW per single time, under the assumption that the traffic amount ratio R _n is unchanged, bottles link utilization u is maximum The neck link is unchanged, and the maximum link usage rate u _max is proportional to the traffic volume V. Therefore, assuming that the usage rate of the bottleneck link when V = 1 is u _{max, 1} , u _max = u _{max , 1} V.

_{Here, u max} = 1 and a V when made to define the maximum NW throughput, average maximum NW throughput of each NW link capacity _{C e} in dividing normalized maximum NW throughput _{V max (= 1 / u max} , 1 / C _a ) to evaluate the performance of each distribution system.

The comparison target for measuring the effect on the single distribution of OPD is OSD, and the average effect ξ _OPD of OPD is defined as a value obtained by dividing NW throughput V _{max in OPD, OPD} divided by V _{max and OSD} (ξ _OPD = V _{max OPD} / Vmax _{, OSD} ).

FIG. 8 shows a state in which the average effect ξ _{OPD of} OPD when the number of servers is changed from 2 to the range of ceiling (N / 2) is plotted for each NW against the server number ratio s. Yes.

  As shown in FIGS. 8A and 8C, NW10 and NW23 do not show the effect of OPD. Other NWs have the effect of OPD, but the effect largely depends on the number of installed servers.

  As shown in FIG. 8A, the Star type NW can improve the NW throughput even if parallel distribution is performed when the order of a large number of nodes is 1 and the links connected to these nodes become a bottleneck. The effect of OPD is low.

  However, since NW12 (GoodNet indicated by CAIDA) has a plurality of hub nodes and a large number of nodes are connected to the plurality of hub nodes, the NW throughput is greatly improved by performing parallel distribution.

The NW 20 has a low OPD effect over a wide range of servers S, but only when the server number S = 7, ξ _OPD = 1.8, and the OPD effect is high.

  The NW 20 is a “Telstra Internet” indicated by CAIDA. Specifically, in this NW 20, the node 3 (Hobart) is connected to the node 4 (Laucanceston) and the node 5 (Melbourne), but the link ( The ratio of the capacity of (4, 3) and (5, 3) to the maximum link capacity of the main NW is as small as 0.019, which tends to be a bottleneck.

  When the number of servers S = 7, servers are arranged on both the nodes 4 and 5, but since only one of the servers is used for distribution to the node 3 in the OSD, the link (4, 3) or the link ( 5) or 3) is likely to become a bottleneck.

  In OPD, both servers installed in node 4 and node 5 are used for distribution with respect to node 3, and the load applied to each link is halved. As a result, the effect of OPD increases.

  As shown in this example, OPD is effective when the capacities of two links connected to a node of degree 2 are both small.

  By the way, in NW20 (Telstra Internet), when the number of servers S ≦ 4, there is no server installed in both node 4 and node 5, and there are no servers that can be used effectively for distribution to node 3. Therefore, when 5 ≦ S ≦ 6 or S ≧ 8, the other link becomes a bottleneck and the effect of OPD is hardly seen.

  On the other hand, as shown in FIGS. 8B and 8C, in the H & S type NW and the Ladder type NW, the effect of OPD can be seen for a large number of installed servers.

  Among these NWs, as shown in FIG. 8B, the effect of OPD in the NW 19 (Sprint indicated by CAIDA) varies greatly with respect to the number of servers S in particular.

  This NW 19 is “Sprint” indicated by CAIDA. Specifically, when the number of servers S = 5, the link (17, 20) connected to the node 20 (Sydney) of degree 1 is a bottleneck in the OSD. Therefore, in parallel delivery, the load on the bottleneck link cannot be reduced, and the effect of OPD is not seen.

  However, when the number of servers S ≧ 6, as a result of installing servers in the node 20, the bottleneck moves to another link, and the effect of OPD is seen. Even when 2 ≦ S ≦ 4, the other links are bottlenecks, and the effect of OPD can be seen.

For example, when the number of servers S = 3, ξ _OPD = 1.75 and the effect of OPD is high, but two of the three servers are installed in node 8 (Chicago) and node 15 (London), and the ratio of population The large node 5 (NewYork) is not arranged with a server, but is adjacent to these two nodes.

  The capacity of the link (8, 5) is as large as 2.488 Gbps, whereas the capacity of the link (15, 5) is as small as 155 Mbps. Distribution to the node 5 is only from the node 8 in the OSD, and is installed between the hub nodes. The link (8, 5) was a bottleneck.

  However, since the OPD is distributed from the node 8 and the node 15 to the node 5, the load on the bottleneck link is reduced.

  Thus, when a server is not installed in a node having a high population ratio and an order of 2 or more, and there are two or more servers that do not share a link, OPD is effective even when the link capacity is large. It becomes.

In FIG. 9A, the average value of ξ _OPD values in each S (number of servers) in the range of 2 ≦ S ≦ ceiling (N / 2) is plotted against N for 36 NWs. Indicates the state.

  The Star type NW is generally less effective in parallel distribution except for the NW 12 (Genuity indicated by CAIDA) in which a large number of nodes are connected to a plurality of hubs.

  The H & S type NW can greatly reduce the load on the bottleneck link by performing parallel distribution when a link connected to a node having an order of 2 or more becomes a bottleneck. high.

  In addition, the Ladder type NW has the effect of OSD, but NW throughput is further improved by performing parallel distribution.

  Two H & S type NWs (NW5 and NW21) and four Ladder type NWs (NW6, NW9, NW13, NW23) have a small effect of parallel delivery, but NW5 (AT & T WorldNet indicated by CAIDA) and NW21 (CAIDA) UUNET) has a small capacity for a large number of links, and NW6 (BBN PLANET indicated by CAIDA), 9 (EPOCH Networks Inc.), 13 (iSTAR Internet Inc.), 23 (XO Communications) Since there are many nodes of degree 1 and the link connecting them tends to be a bottleneck, the effect of parallel distribution is small.

In order to eliminate the influence of the link capacity and evaluate the influence of the topology structure on the effect of parallel distribution, the average value of ξ _OPD when all the link capacities are set to the average link capacity of each NW is shown in FIG. It shows in the same way.

  From the comparison between FIG. 9A and FIG. 9B, when only the topology structure is considered, the effect of parallel distribution in the H & S type NW is greatly improved. Although the H & S type NW has the effect of parallel distribution compared to the OSD, the capacity of the majority of links tends to be smaller than the average link capacity. Can be confirmed.

  If only the topology structure is considered, it can be said that the topology in which parallel distribution is most effective is an H & S type in which a plurality of servers can be easily used at low distribution cost.

Further, as seen in FIG. 8, the effect of parallel distribution largely depends on the number of installed servers S. Therefore, FIG. 10A shows a state in which the ξ _OPD in the server number S where the ξ _OPD is the maximum in each NW is plotted against the number N of nodes.

  From FIG. 10 (a), it is confirmed that the NW throughput can be improved by about 20% to 100% at the maximum by performing parallel delivery in a large number of NWs.

  However, in many Star type NWs (NW1, NW10, NW14, and NW16) and some Ladder type NWs (NW9, NW13, and NW23), the effect of parallel distribution is small. In particular, three Star type NWs (NW10, NW14, NW16) and one Ladder type NW (NW23) show no parallel distribution effect.

  Further, in FIG. 10B, for each of 32 NWs except for four NWs where no parallel distribution effect was observed, the number of installed servers S with the maximum parallel distribution effect is represented by the number of nodes N. The plotted state is shown for each.

  As shown in FIG. 10B, the Ladder type NW tends to have a large number of servers that maximize the effect of parallel distribution, and is often about 10 to 20 regardless of the node N. This is because the Ladder type NW has a tendency that almost all links are shared by paths between a large number of node pairs, and when the number of servers S is small, it is difficult to obtain an effect of avoiding a link with a high usage rate by parallel distribution. It is.

  In addition, since the H & S type NW can easily change the routed link by changing the hub node that is routed, except for the link connected to the node of degree 1, it is easy to obtain the effect of parallel distribution even when a small number of servers are arranged.

  FIG. 11 shows the cumulative complementary distribution of the number of servers used in each distribution at the time of parallel distribution in all server numbers S of “2 ≦ S ≦ ceiling (N / 2)” for each NW. .

  In all NWs, the number of servers used for 90% or more distribution is 2 or less, and there are a small number of servers used for parallel distribution for each distribution destination node, even when the number of installed servers is large.

  In some NWs (NW12 in FIG. 11 (a) and NW19 in FIG. 11 (b)) that have a high effect of parallel delivery, the number of servers used for parallel delivery is large. There is no correlation between the number of servers and the number of parallel distribution servers, and there are NWs that are effective for parallel distribution even in NWs with a small number of parallel distribution servers, such as NW17 (Savivis Communications) in FIG. .

  As described above with reference to FIGS. 1 to 12, in the data parallel distribution system of this example, a plurality of mirror servers are arranged on the network, and a plurality of servers are used for distribution for each distribution request. By reducing the transfer bit rate of the flow and further minimizing the maximum link usage rate, the total amount of distribution requests (network throughput) that can be accommodated in the entire network is maximized.

  In order to minimize the maximum link utilization rate, the link cost sum is first calculated using the data of the number of installed servers S, the network topology, the ratio of requested distribution generated from each node, the link capacity, and the static link cost. Optimum S servers to minimize the maximum link utilization when one minimum path is used for each node pair and the server used for distribution to each node is one minimum cost server. Deploy.

  In addition, by repeating the process of changing a single server used for each node to another server so that the maximum link usage rate is minimized, the maximum link usage is used when a single server is used for each distribution. The server to be used for each node is optimally selected so that the rate is minimized.

  Furthermore, a server set used for each node is optimally designed so as to minimize the maximum link usage rate when a plurality of servers are allowed to be used for distributing the same data to each node.

  That is, a server arrangement design device 102 and a server selection design device 103 as means for executing programmed computer processing in a data parallel distribution system that distributes data in parallel from a plurality of servers arranged on a network to a destination node. The server placement selection means comprising the above selects the node on which each server used for data distribution is placed so that the maximum usage rate (maximum link usage rate) of each link between the nodes is minimized.

  In particular, the server arrangement design device 102 obtains the maximum link usage rate of each link between the nodes in the network, specifies the predetermined number S nodes in ascending order of the obtained maximum link usage rate, and specifies the specified S This node is selected as a node for installing the server.

Then, the server selection design device 103 sequentially performs server replacement that minimizes the maximum link usage rate when the server that uses the link of the maximum usage rate for the delivery destination node through which the delivery flow passes is replaced with another server. From each server placed on S nodes,
Only one server arranged in the node having the minimum maximum link usage rate with the distribution destination node is selected as a distribution source server for the distribution destination node.

  In addition, the server selection design device 103 uses the maximum link usage rate when a new server is added to the set of servers that use the link with the maximum usage rate for the delivery destination node through which the delivery flow passes. By sequentially adding the servers, the maximum link usage rate with the distribution destination node is minimized for a plurality of servers used for parallel distribution from the servers arranged in the S nodes to the distribution destination node. select.

  As described above, according to this example, when a plurality of mirror servers are arranged on the network and a plurality of servers are used for distribution for each distribution request, the transfer bit rate of each flow is further reduced. By minimizing the link usage rate, the total distribution request amount (network throughput) that can be accommodated in the entire network can be maximized.

  In addition, this invention is not limited to the example demonstrated using FIGS. 1-12, A various change is possible in the range which does not deviate from the summary. For example, in this example, the server arrangement design device 102 and the server selection design device 103 are provided in one computer device, but may be provided in different computer devices.

  101: input data setting device, 102: server arrangement design device, 103: server selection design device, 104: design result output device.

Claims (4)

A data parallel distribution system for distributing data in parallel from a plurality of servers arranged on a network to a destination node,
As a means of performing programmed computer processing,
Pre-input data setting means for storing the transmission capacity C of each link between all nodes N in the network and the static link cost of each link in a storage device;
A server arrangement selection means for selecting a node where each server used for data distribution is arranged so that the maximum link usage rate, which is the maximum value of the usage rate with respect to the transmission capacity of each link between the nodes, is minimized ;
From each server arranged in S nodes selected by the server arrangement selection means, for each distribution destination node, a plurality of servers used for parallel distribution to the distribution destination node are used with the maximum link use with the distribution destination node. possess a server selection unit rate is selected so as to minimize,
The server arrangement selecting means is
In the state where j servers are arranged in the node set Nj, the maximum link usage rate u _max (Nj, i) when a server is arranged in an arbitrary node i not included in the node set Nj is The process calculated in step ( i) is performed for all nodes i of “i∈N \ N _j ”, and the process of placing the (j + 1) th server at the node where the calculated maximum link usage is minimum is arbitrarily given. A data parallel distribution system characterized by selecting S nodes where S servers used for the data distribution are arranged by repeating S times .
[procedure]
Based on the link cost of each link inputted in advance, for any node d, a server s with the lowest delivery cost from each server included in the server set S = {Nj + i} is obtained.
An average v _sd of traffic demand per unit time generated from the node s where the obtained server s is arranged to the node d is set, and the transmission capacity Ce of each link e in the distribution route between the node s and the node d It calculates an average usage rate u _e for each link e based on the equation (1) below using,
The maximum value u _max (Nj, i) of the calculated average usage rate of each link is calculated.

In Expression (1), x (s, d, e) is a binary variable that takes 1 when the distribution route from the node s to the node d passes through the link e and 0 when it does not pass. The data parallel distribution system according to claim 1,
The server selection means,
For each distribution destination d node, the distribution cost with the distribution destination node d in the data distribution from the S servers selected by the server arrangement selection means to the distribution destination node d for each distribution destination node d is as follows. The smallest server is selected as a server to deliver, and an average v _sd of traffic demand per unit time generated from the node where the selected server is placed to the delivery destination node d is set, and the usage rate of each link Is calculated by the above equation (1) to obtain the link ε having the maximum usage rate and the maximum link usage rate u _{max, ε} of the link ε ,
The maximum link usage rate u _{max, d, k} when the server used for distribution is changed to each of the other servers k for each distribution destination node d belonging to the distribution destination node set Dε through which the route ε passes. The process of changing the server k ^* having the smallest value to the distribution server for the node d is repeated for all the nodes belonging to the node set Dε, and the maximum link usage rate u ′ _max obtained as a result of each iteration is changed. Select a single distribution server for distribution destination node d for each distribution destination node d by iterating the distribution server change for node d as long as it is lower than the previous maximum link utilization u _max ,
For each distribution destination node d, an average v _sd of traffic demand per unit time generated from the node where the selected single distribution server is arranged to the distribution destination node d is set, and the usage rate of each link is set as above. The distribution destination node belonging to the distribution destination node set Dε through which the link ε having the maximum usage rate and the maximum link usage rate u _max of the link ε are calculated and the link ε is calculated. For the distribution server set Sd used for the distribution request of the user belonging to the distribution destination node d, only one server k of the unused server set other than the distribution server set Sd is included in the distribution server. maximum link utilization u _max of adding to the set S _{d, d, k} a server k ^* that minimizes, the process of adding to the set S _d of the distribution server, all belonging to the destination node set Dε Was repeated for over de maximum link utilization u _'max obtained as a result of the iteration, as long as it reduces from adding the previous value u _max, by repeating the process of adding the distribution server, the distribution destination node A data parallel distribution system , wherein a plurality of servers used for parallel distribution to a distribution destination node are selected from the servers arranged on the S nodes selected by the server arrangement selection means . A method of performing placement and selection of servers in a data parallel delivery system for delivering data in parallel to a delivery destination node from a plurality of servers arranged on a network by a programmed computer device,
As a process execution procedure by a programmed computer device,
Claim 1 or claim 2 Symbol mounting said data setting means in data parallel distribution system, the server arrangement selection means, and the data parallel delivery method characterized in that it comprises a processing procedure of the server selection means is executed. The computer, the data setting means in data parallel delivery system according to claim 1 or claim 2 Symbol placement, the server arrangement selection means, and a program to function as the server selection means.

Images