A method of and apparatus for efficiently communicating between a provider of video on demand services and a cable television subscriber. The communication is implemented using a message protocol specifically optimized to communicate between a multimedia application server and a set top subscriber box. The message format includes unique identifiers for addressing and synchronization to permit the multimedia application server to manage the communication process.