Methods, systems, and devices may implement a header repair mechanism to deal with a loss of successive compressed headers (e.g., due to radio interface). The present methods and apparatus exploit the fact that once a correct timestamp (TS) from a previous decompression success (called “last successfully decomp_TS”) is known, another (e.g., a subsequent) TS should be in the form: last successfully decomp_TS+n*min_TS_STRIDE, where n is a positive integer if the estimated sequence number (SN) is higher than the last successfully decompressed SN, and a negative integer if the estimated SN is lower than the last successfully decompressed SN, and min_TS_STRIDE is the expected minimum TS increment, which is known and directly related to the medium sample rate and frame rate, for example.