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 interco nnected by links with different bandwidth and do not share file system s. The software is modelled as a directed acyclic graph. Each node in the graph represents a logical step in processing the software while t he edges describe the order of execution. The problem is to construct the software at a particular LAN with minimum Internet communication c ost. An optimal polynomial algorithm, SOFTCON, with time complexity O( NC+E+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 num ber of LANs in the Internet environment, and O(A(N,E)) is the time com plexity of the network flow algorithm on the flow network with N nodes and E edges transformed from the directed acyclic graph of the softwa re.