Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, are described for fragmenting a media stream (e.g., for HTTP streaming) by generating fragments that can have variable relative durations. The disclosed technologies enable fragmenting the media stream by two or more media streaming server systems to obtain respective sets of fragments having a framing structure that is consistent across the two or more media streaming server systems. Consequently, a client computer system can place HTTP requests for fragments of the media stream, e.g. for switching mid-stream, to any of the two or more media streaming server systems that generated the respective sets of fragments.