The media stream delivery system encodes and fragments media streams into numerous media stream fragments maintained on fragment servers. Devices obtain fragments to reconstruct media streams including live real-time media streams for playback on the devices. A device may perform caching of media stream fragments so that particular fragments need not be accessed again from a fragment server. A fragment server or even a content provider can analyze and monitor characteristics of media streams, viewing behavior, content popularity, etc., to identify fragments for caching at the playback devices. Caching indicators along with time period indicators may be included in the media stream fragments.