Internet is evolving to be an integrated service platform for promising future global information infrastructure. New multimedia services, e.g., Video-on-Demand, are expected to be provided on this platform, in conjuction with the existing rich information exchange and sharing services on Internet, such as E-mail, WWW. The paper proposes a service system architecture for Video-on -Demand on Internet, named MINS (Multimedia Internet Navigation System), which is capable of both realtime audio/video transmission and realtime and VCR like plya-out. MINS is composed of 1) servers maintaining both audio/video program lists and contents, and 2) clients retrieving the programs and play-out them. The paper focuses on the communication architecture in MINS, e.g., flow control, realtime media synchronization control, and audio/video session control. The performance of the prototype MINS is also evaluated in the paper.