Single Network

We first present results on a single network for both the random graph and the geographical graph. Each result for the random graph is averaged over 10 runs, while the result for the geographic graph is from a single run, since the node locations are all fixed.

Figure 5.2: Variation on Server Service Range

[Single Random Network: $n = 100$, scale = 100, k = 1]

[width=0.8]figure/chap5/random_service_range.eps

[Single Geographical Network: $n = 50$, k = 1]

[width=0.8]figure/chap5/geo_service_range.eps

Figure 5.2 shows the number of required servers when varying service range. In general, both the IR and the greedy algorithm performs closely with the lower bound. With increasing service range, the number of servers needed drops significantly. In most cases, the IR algorithm outperforms the greedy algorithm.

Figure 5.3: Variation on Different Service Requirement

[Single Random Network: $n = 100$, scale = 100, range = 10]

[width=0.8]figure/chap5/random_service_compare.eps

[Single Geographical Network: $n = 50$, range = 400 km]

[width=0.8]figure/chap5/geo_service_compare.eps

Figure 5.3 shows the performance against the different service requirements. We perform simulations on the following three scenarios: (a) $k = 1$, with only one primary server required to cover each node; (b) $k = 1$ and requiring one backup server; (c) $k = 1$ with relaxation on the server to client distance. The last scenario allows a compromise on the service standard for a limited number of clients. This allows service providers to be more cost effective and not to install servers just for a few remotely located nodes. The backup server range is twice that of the primary server for both networks. The relaxation is done by including every node in at least $l$ server sets, even if it is not within the range of $l$ servers. That is, if a node is in the range of $l' < l$ servers, we add it to the sets for the next $l-l'$ servers that it is closest to.

Figure 5.3 shows that the addition of the backup servers only increases the number of total servers slightly. The service range relaxation is also effective in reducing number of servers to about 75% and 55% of the original number, with $l = 3$ and $l = 5$ respectively. However, the relaxation is useful only when the service range is small. In Figure 5.3, the service range is 10 units and 400 km in the two network configurations, which covers about 7% and 8% of the maximum distance in their respective networks. If we double the service range, we find that the relaxation becomes irrelevant since each node is likely to be included in multiple sets already. Table 5.2 shows the average node to server distance with and without the service range relaxation. Since there may be multiple servers covering a node, we select the closest server when computing the distance. The result for the random graph are the worst case among 10 runs. These results quantifies the compromises made to service quality in order to reduce the server cost.

Table 5.2: Average Client to Server distance

	Random Graph (unit)			Geographic Graph (km)
	range = 10			range = 400 km
	mean	std.	max	mean	std.	max
$l = 0$	4.94	3.74	9.83	167.49	140.11	398.79
$l = 3$	6.30	4.47	14.82	259.78	222.65	1013.42
$l = 5$	8.45	5.56	25.36	304.69	238.59	1114.78