In this paper, novel techniques for packet loss robust speech coding are proposed. By exploiting knowledge of the receiving end packet loss concealment algorithm, an existing rate-distortion optimal time-segmentation algorithm is extended to taking packet losses into account. To increase robustness in highly nonstationary signals, the technique is complemented by a redundancy selection scheme. A jointly optimal approach ensures that the complementarity between time-segmentation and redundancies is fully exploited. The performance of the methods is investigated through Monte Carlo simulations under various conditions, such as rate, packet loss probability, and algorithmic delay. Finally, subjective listening tests demonstrate perceptual improvements as compared to conventional adaptive time-segmentation not taking packet losses into account.@en