A computer-implemented method for performing video compression comprising: encoding a plurality of video frames or portions thereof according to a first encoding format, wherein the video frames contain the graphical output of a game or application executed at one or more servers in response to control signals (406a-b) representing user input transmitted from a client device; transmitting the plurality of encoded video frames (612, 613) or portions to the client device; receiving feedback information from the client device, the feedback information usable to determine whether data contained in the video frames (612, 613) or portions has been successfully received and decoded; in response to detecting that one or more video frames (612, 613) or portions thereof have not been successfully received and decoded, determining a number of video frames (612, 613) or portions thereof which have not been successfully received and decoded and: if the number of video frames (612, 613) or portions thereof which have not been successfully received and decoded is below a specified threshold, then encoding new video frames or portion thereof according to a second encoding format, the second encoding format using only P-frames unless I-frames are necessary or smaller than said P-frames, and transmitting the new video frames or portion thereof to the client device; or if the number of video frames (612, 613) or portions thereof which have not been successfully received and decoded is above a specified threshold, then continuing to encode and transmit the plurality of video frames according to the first encoding format, the first encoding format including periodic I-frames that enable rewind from a nearest preceding I-frame of said periodic I-frames. encoding a plurality of video frames or portions thereof according to a first encoding format, wherein the video frames contain the graphical output of a game or application executed at one or more servers in response to control signals (406a-b) representing user input transmitted from a client device; transmitting the plurality of encoded video frames (612, 613) or portions to the client device; receiving feedback information from the client device, the feedback information usable to determine whether data contained in the video frames (612, 613) or portions has been successfully received and decoded; in response to detecting that one or more video frames (612, 613) or portions thereof have not been successfully received and decoded, determining a number of video frames (612, 613) or portions thereof which have not been successfully received and decoded and: if the number of video frames (612, 613) or portions thereof which have not been successfully received and decoded is below a specified threshold, then encoding new video frames or portion thereof according to a second encoding format, the second encoding format using only P-frames unless I-frames are necessary or smaller than said P-frames, and transmitting the new video frames or portion thereof to the client device; or if the number of video frames (612, 613) or portions thereof which have not been successfully received and decoded is above a specified threshold, then continuing to encode and transmit the plurality of video frames according to the first encoding format, the first encoding format including periodic I-frames that enable rewind from a nearest preceding I-frame of said periodic I-frames. if the number of video frames (612, 613) or portions thereof which have not been successfully received and decoded is below a specified threshold, then encoding new video frames or portion thereof according to a second encoding format, the second encoding format using only P-frames unless I-frames are necessary or smaller than said P-frames, and transmitting the new video frames or portion thereof to the client device; or if the number of video frames (612, 613) or portions thereof which have not been successfully received and decoded is above a specified threshold, then continuing to encode and transmit the plurality of video frames according to the first encoding format, the first encoding format including periodic I-frames that enable rewind from a nearest preceding I-frame of said periodic I-frames.