A computer-implemented method for executing an online video game comprising: receiving a control signal (406a-b) for the online video game, the control signal (406a-b) being received by a server, the control signal being transmitted from a client device to the server; executing the online video game by the server while receiving the control signal (406a-b), the executing causes generation of a plurality of video frames; encoding the plurality of video frames according to a first encoding format to produce a plurality of encoded video frames, the first encoding format being dependent on a prior video frame, the plurality of video frames encoded according to the first encoding format comprising P-frames; transmitting the plurality of encoded video frames to the client device; receiving feedback information from the client device, the feedback information usable to determine whether data contained in the plurality of encoded video frames has not been successfully received and decoded by the client device; in response to detecting that one or more encoded video frames have not been successfully received and decoded by the client device, then encoding a new video frame to produce a new encoded video frame wherein the new encoded video frame is encoded according to a second encoding format that is not dependent on the prior video frame, the new video frame encoded according to the second format comprising an I-frame; and if no forward error correction coding is used to transmit the plurality of encoded video frames, then encoding the new video frame includes using FEC coding; or if a first FEC coding is used to transmit the plurality of encoded video frames, then encoding the new video frame includes using a second FEC coding, the second FEC coding being a stronger FEC coding than the first FEC coding; and transmitting the new encoded video frame to the client device. receiving a control signal (406a-b) for the online video game, the control signal (406a-b) being received by a server, the control signal being transmitted from a client device to the server; executing the online video game by the server while receiving the control signal (406a-b), the executing causes generation of a plurality of video frames; encoding the plurality of video frames according to a first encoding format to produce a plurality of encoded video frames, the first encoding format being dependent on a prior video frame, the plurality of video frames encoded according to the first encoding format comprising P-frames; transmitting the plurality of encoded video frames to the client device; receiving feedback information from the client device, the feedback information usable to determine whether data contained in the plurality of encoded video frames has not been successfully received and decoded by the client device; in response to detecting that one or more encoded video frames have not been successfully received and decoded by the client device, then encoding a new video frame to produce a new encoded video frame wherein the new encoded video frame is encoded according to a second encoding format that is not dependent on the prior video frame, the new video frame encoded according to the second format comprising an I-frame; and if no forward error correction coding is used to transmit the plurality of encoded video frames, then encoding the new video frame includes using FEC coding; or if a first FEC coding is used to transmit the plurality of encoded video frames, then encoding the new video frame includes using a second FEC coding, the second FEC coding being a stronger FEC coding than the first FEC coding; and if no forward error correction coding is used to transmit the plurality of encoded video frames, then encoding the new video frame includes using FEC coding; or if a first FEC coding is used to transmit the plurality of encoded video frames, then encoding the new video frame includes using a second FEC coding, the second FEC coding being a stronger FEC coding than the first FEC coding; and transmitting the new encoded video frame to the client device.