A two-tier framework for transmission-cost minimization of high-performance communication applications

In two-tier high-performance networks (HPNs), some facilities are constructed to form a powerful supercomputing environment, and to alleviate server load. Then, the applications are provided by them in co-operated, parallel and distributed manners. A proper way to select facilities is crucial to the performance of two-tier HPNs The problem of selecting facilities can be regarded as a kind of the facility location problem, which is to determine an optimal subset of facilities that will be open to serve users. The traditional facility location problem aims to minimize the incurred costs between the users/servers and their assigned facilities. In two-tier HPNs, the incurred costs can be regarded as the transmission costs, e.g. transmission latency, bandwidth overhead. We observe that most of the packets are transmitted among the facilities for application servicing and framework maintaining. In this paper, we address the problem of selecting facilities in two-tier HPNs by minimizing the transmission costs from servers to users by passing through the selected facilities. Our problem is different from the traditional facility location problem, which only considers the transmission costs between the users/servers and their assigned facilities. In our problem, the transmission costs between the selected facilities are further considered. The problem is formulated as a 0/1 integer non-linear programming (0/1 INLP) and 0/1 integer linear programming (0/1 ILP). Further, a simple heuristic algorithm is proposed for obtaining a feasible solution when the network sizes increase, since solving INLPs and ILPs for large-scale problems takes long time.