In this chapter, we study another subproblem of the overlay network design problem: the placement of the MSNs with constraints on the client to server paths, reflecting the quality of service within the regional access networks. We envision that this imposition of service quality constraints on server to client paths is essential for the newer network services to achieve better service quality in order to attract and retain customers. While the server-to-server paths can be explicitly provisioned in order to ensure available bandwidth and routed to satisfy a delay constraint, this approach is generally not cost-effective on the more numerous client access paths. Consequently, the quality of the service is determined largely by network locations of the deployed servers. However, operating and maintaining these distributed servers represents a major cost for service providers and limits the number of servers that can be deployed.
To examine the trade-off between service quality and network cost, we ask the following question: Given multiple networks and their estimated service parameters, how many servers are needed and where should an overlay service provider locate them to ensure a desired service quality to all its clients. The measure of quality of service can vary from application to application: it can be delay for real-time applications, or bandwidth for content distribution applications, or a combination of both. The connection from a client to its designated MSN can stay within an ISP domain or may cross multiple domains. With the emergence of co-location services in major metropolitan areas, we expect that fewer clients would need to be routed through multiple ISPs to reach their designated MSNs. Within an ISP network, the service provider can estimate these service quality parameters for a given client to a potential server location based on the client's network access technology and the capacities of the internal routing paths. Across the ISP domains, such estimation is also possible if the peering path between networks is explicitly indicated or if both networks guarantee a service level agreement from which we can infer the service parameters. Therefore, we assume that we can decide in advance whether or not placing an MSN at a specific location can provide a given client with the desired level of service quality. In the rest of this chapter, we use regional routers from different ISP networks to represent the aggregation of clients and use the network distance between a regional router and an MSN as the service parameter, however, our methods can apply to any generic metrics.
To answer the above question, we transform the placement problem to
the set cover problem [#!clr-algorithm!#] and solve it using both
linear programming (LP) relaxation and greedy heuristics. An instance
of the set cover problem is that given a base set of elements and a
family of sets that are subsets of this base set, find the minimum
number of sets such that their union includes all elements in the base
set. The server placement maps to the set cover problem as follows: an
element corresponds to the network location of an edge router, which
represents the aggregation of regional clients in an ISP network; The
base element set contains all the network locations of edge routers; A
set represents a potential server placement at one of the network
locations; Each set includes all the network locations that are within
the service range from the server location represented by the same
set. By solving the set cover problem, we find the minimum number of
servers and their locations, that will cover all clients within the
service range. We will only consider the uncapacitated version of the
set cover problem, where the servers do not have capacity limits and
can serve as many clients as possible. We think this uncapacitated
version is adequate since it is typically cheaper to buy more
bandwidth at one location than to install a separate server. The set
cover problem is NP-Hard [#!karp72!#] and has approximation ratio of
[#!feige96!#,#!raz97subconstant!#]. We introduce a rounding
technique to solve the integer-programming formulation of the set
cover problem based on linear programming (LP) relaxation methods.
The super-optimality of the LP problem provides a lower bound to the
IP formulation of the set cover problem. Using simulation, we show
that this rounding technique approaches the lower bound very closely;
in fact, it reaches the lower bound for a number of network
configurations. Meanwhile, the greedy heuristic also provides good
performance in all instances with significantly less computation
complexity.
One contribution of our approach is that we have investigated several variations of the placement strategy and their associated costs. For example, what is the cost if each client should be served by a backup MSN as well as a primary MSN? What is the cost if backup MSNs are allowed to be placed at twice the range of the primary? What is the cost saving if service range can be relaxed? Or if we can compromise the service quality of some non-premier clients? Answers to these questions offers guidance to service providers on the economy of their planned services. These different placement strategies can be mapped to different node inclusion criteria when constructing a set, and we can then solve the resulting set cover instances with the same algorithms.
Another important aspect of our study is the network modeling used in our simulation. Existing network modeling tools, such as GT-ITM [#!gt-itm!#] and Tiers [#!tiers!#], can generate hierarchical network graphs with probabilistic network interconnections, however, they do not explicitly model the geographical locations of the network elements. In our model, we consider the potential of co-located servers which can access multiple networks from the same geographical location; this mirrors the behavior of co-location service providers in the current Internet. Therefore, when two network nodes of different networks are within a geographical vicinity, a server placed at this location can service clients, who are within the service range, in both networks. We show that these co-locations can greatly reduce the number of required servers, since they avoid long indirect paths through the network peering points by providing shortcuts from one network to another.
The rest of the chapter is organized as follows: we introduce the formal problem definitions and the algorithms in Section 5.1; we then describe the network models used in our simulations in Section 5.2; Section 5.3 presents simulation results; Section 5.4 discusses some of the related work; and in Section 5.5, we summarize our results.