[theora] Indexing Ogg files for faster seeking

[Michael Dale]

This looks very good :)

I like the embedded approach because it won't require server side 
modification. (ie just have to run the indexer prior to being 
published). This keeps things simple works with existing http 
byte-offset system. Thinking about the problem a bit ...  this is of 
course "the way to do it" because people like to keep things simple and 
its an uphill battle to update server infrastructure, CDNs, proxy 
systems, shared hosting accounts ... improvements in the infrastructure 
layer that touches everything are very difficult.

The only minor down side I see is sending the extra delta encoded byte 
offset track and the second round trip. Ie you first have to download 
the index(s) then do the byte request. ( instead of just sending the 
time request to the server and directly getting back the stream from the 
necessary byte offset ) But not really that big of a deal. The ideal 
server side system would send back byte-offset hint for a second round 
trip anyway (to be compatible with normal http byte range request proxy 
systems)

Also the server side solution (ogg_chop) can work with that keframe 
index to avoid long server side seek times and support clients playback 
systems that don't use yet support the index system or "wget" a segment 
as a distinct resource.

To quickly take a look at the near worst case of overhead we can 
consider a 13 hour stream: 
http://mvbox2.cse.ucsc.edu/media/senate_proceeding_07-16-09.ogg
... or not... I am having trouble building the library getting:
"libtool: definition of this LT_INIT comes from an older release.
libtool: You should recreate aclocal.m4 with macros from libtool 2.2.6"
any tips?

To make indexing Ogg happen I think we would need:

1) index per track as described later in the thread

2) Mozilla to quickly push out the patch as a "critical" update to 
encourage adoption and to not have a large percentage of users avoiding 
its usage because of lack of seeking for existing Firefox clients. (as I 
understand present version of Firefox does not let you do normal seeking 
on the indexed file because of a bug with liboggplay? )

3) As Silvia mentions we want to push this we want to integrate the 
indexer into the ffmpeg2theora encoder output.

And ideally:

4) Integrate support into the cortado applet.  (the fall back basic 
seeking is pretty bad right now with cortado as well)

5) Create a PHP port. So that stand alone web app can check for the 
index and add it if its missing then send the content-duration header 
and keyframe indexed stream and handle byte-offsets.  I just started a 
quick hack on a similar solution (its storing the key-frame index in a 
separate file) and if I get some more time to push forward on it I will 
try and port the indexer.
http://svn.wikimedia.org/svnroot/mediawiki/trunk/extensions/MetavidWiki/skins/mv_embed/oggServer/

presently it at least sends out the x-content-duration header which is 
better than nothing ;) Although sending things through php won't be fun 
for high traffic sites... but could simplify improved seeking 
performance for small to medium sized video projects...  Especially if 
the library can seed the index on content ingestion and use normal 
apache/webserver for serving the video.

--michael


Silvia Pfeiffer wrote:
> Hi Chris,
>
> I love the idea and even more that you already have working code.
>
> I think this is probably the cleanest approach to Ogg seeking that I
> have seen in a while. I think the additional overhead is tolerable.
>
> Please note that there will be a third solution to the problem of
> seeking over HTTP which will not require Ogg files with keyframe index
> tracks, but can make use of them. The idea here is to use media
> fragment URIs to address into a media file and retrieve the relevant
> byte ranges. This is based on communicating it to the server and the
> server then composing together the relevant byte ranges as a reply. If
> the file on the server had your keyframe index track, it could
> probably identify the right byte range faster, so that's a good thing.
>
> I think this is awesome and should be added to the Xiph wiki. Also, it
> should go into ffmpeg2theora, IMHO, but of course that's up to others
> to decide.
>
> Cheers,
> Silvia.
>
>
> On Tue, Sep 22, 2009 at 1:27 PM, Chris Pearce <chris at pearce.org.nz> wrote:
>   
>> I've developed an indexer which embeds a keyframe index track in Ogg
>> files. It embeds the index in its own track, so that players that don't
>> understand or don't want to use the index can just ignore it.
>>
>> Ogg needs this to make seeking over networks faster and more efficient.
>>
>> Currently we must do a bisection search when seeking, which usually
>> takes aound 6 HTTP requests, give or take a few. If we are to compete
>> with existing internet video (AKA the "YouTube" case) we need to do that
>> faster and more efficiently - using fewer HTTP requests. We need an
>> index so that seeking only takes 1 HTTP request.
>>
>> Using an index of keyframes also makes it easier to seek without visual
>> artifacts - though of course robust players should be able to do that in
>> the absence of an index.
>>
>> You can download the source code for my indexer here:
>> http://github.com/cpearce/OggIndex
>>
>> My specification for the index track is stored in that repo, here:
>> http://tinyurl.com/l4c9yg
>>
>> I'd appreciate comments on the spec...
>>
>> To see how it improves network seeking performance, you can download a
>> version of Firefox which can take advantage indexes here:
>> http://pearce.org.nz/video/firefox-indexed-ogg-seek.linux.tar.bz2
>> http://pearce.org.nz/video/firefox-indexed-ogg-seek.macosx.dmg
>> http://pearce.org.nz/video/firefox-indexed-ogg-seek.win32.zip
>>
>> Then point that browser here:
>> http://pearce.org.nz/video/indexed-seek-demo.html
>> (There's a couple of other indexed ogg files in
>> http://pearce.org.nz/video/ too)
>>
>> In terms of compatibility, currently the following players can play and
>> seek in indexed files (i.e. aren't broken when playing/seeking indexed
>> files):
>> * VLC
>> * Cortardo
>> * XiphQT plugin
>>
>> The following players can play indexed files, but can't seek:
>> * Anything that uses liboggz (including Firefox 3.5).
>> * The DirectShow filters (do these use liboggz?)
>>
>> It only takes a pretty trivial patch to enable liboggz (and thus FF3.5)
>> to seek in files with an index; liboggz refuses to seek because it
>> doesn't understand metrics for the index track. It shouldn't be too hard
>> to fix other players as well.
>>
>> Totem on Ubuntu9.04 refuses to play the indexed files, though it decodes
>> the first few frames. That may require a gstreamer patch.
>>
>> So... what do you guys think?
>>
>>
>> _______________________________________________
>> theora mailing list
>> theora at xiph.org
>> http://lists.xiph.org/mailman/listinfo/theora
>>
>>     
> _______________________________________________
> theora mailing list
> theora at xiph.org
> http://lists.xiph.org/mailman/listinfo/theora
>