Parallel computing using Network of Workstations (NOWs) has become very popular recently. However, the execution of parallel applications on such systems has been hampered by the high communication overhead. To reduce the communication overhead and to speedup the execution of parallel applications on NOWs, this paper proposes a Key Message approach that minimizes the cost of message-passing in a parallel application by prioritizing communications in the underlying shared communication network. In this paper, we first describe the queuing network model on which our approach is based, then introduce the algorithm that identifies the messages to be prioritized in a parallel application, and finally discuss the results obtained. Our preliminary analysis of the algorithm on randomly generated task graphs shows improvement over the system without using the prioritization scheme.