Minimal communication cost software construction in the Internet environment

This paper investigates the issue of building software in the Internet environment, where local area network (LAN) based systems are interconnected by links with different bandwidth and do not share file systems. The software is modeled as a directed acyclic graph. Each node in the graph represents a logical step in processing the software while the edges describe the order of execution. The problem is to construct the software at a particular LAN with minimum Internet communication cost. An optimal polynomial algorithm, SOFTCON, with time complexity \({\cal O}(N C + E + {\cal A}(N, N + E))\) is presented, where \(N\) and \(E\) are the number of nodes and edges in the graph describing the software respectively, \(C\) is the number of LANs in the Internet environment, and \({\cal O}({\cal A}({\cal N}, {\cal E}))\) is the time complexity of the network flow algorithm on the flow network with \({\cal N}\) nodes and \({\cal E}\) edges transformed from the directed acyclic graph of the software.

Authors and Affiliations

1. Department of Computer Science, The Hong Kong University of Science and Technology, Clear Water Bay, Hong Kong (e-mail: {cchui,chanson}@cs.ust.hk) , , , , , , HK

   Chi-Chung Hui & Samuel T. Chanson

Received: 6 December 1995 / 1 May 1996

Reprints and permissions