Re: streaming over Gnutella

Am Samstag, 6 de Oktober de 2007 07:14:24 schrieb Zlatin Balevsky:
> I believe most of these ideas are already implemented in the current
> download mesh.  What is missing are the ideas for queueing discipline.
>  That is a very interesting topic, and it would be a very exciting
> challenge to come up with schemes that can beat bittorrent's
> tit-for-tat.

I'd like to get back on topic. 

Does everyone agree with the points of Philippe Verdy about Streamning? 
Could we turn his mail into a proposal?

The points speaking against partial file search results in earlier times 
should be moot by now, since we now  have TigerTree. 

Are there any other problems with it? 

Best wishes, 
Arne

------ the two messages in question ------

Betreff: RE: [the_gdf] returning results for partial downloads
Datum: Samstag, 6 de Oktober de 2007
Von: "Philippe Verdy" <[email protected]>
An: [email protected]

I wrote:
> I have also suggested this since long (about 3 years ago), it was debated
> several times, but not implemented since, most probably because it caused
> problems in the reliability of swarmed downloaded.

In fact my idea beneath the need to support this would be to extend Gnutella
so that it will support ALSO swarmed downloads of LIVE CONTENTS (that have
NO known beginning and END): the only extension needed for this is to
replace the concept of FILES by the more general concept of STREAMS, where
positions may be identified either by a file offset, OR by an absolute
timestamp.

For this to work, it should be possible to ALSO:

* Share URNs for LIVE STREAMS, with matching keywords describing the live
event. The URN should be given some random GUID by the first uploader of the
live event, possibly complemented by some strong digest of the live event
Name.

* Find sources matching this live URN: this uses the standard Gnutella
protocol, using keywords and matching equal URNs on receipt.

* Share TigerTree Data about some time long intervals (identified by its
starting timestamp). A TigerTree Data fragment should be computable over a
reasonably long interval of about 15 minutes of timestamp (the duration of
this window mat depend on the encoding bandwidth of the stream: for voice
streams like MP3 webradios, with most often 128kbps in their encoding, i.e.
16 Kbytes/second, 15 minutes of timestamp will match 900 Kbytes of stream
data, so the maximum size of the TigerTreeData for this window is very
small; if TigerTree Data is computed on blocks of 1KB, the needed TigerTree
Data will contain 900 Tiger digests, i.e. a little more than 21 Kbytes,
something that is very fast to download once from any one source)

* Share all the already downloaded STREAM FRAGMENTS during the download of
the stream. If the stream is a file, these stream fragments are identified
by absolute file positions, if the stream is live, the stream fragments are
identified by the absolute timestamp.

Implementation notes:

* No change is needed to support absolute timestamps instead of absolute
file positions when sharing STREAM FRAGMENTS: this is also a range indicated
by a pair of integers. The only difference is that the origin is not
relative to the beginning of a file but to some arbitrary event starting
timestamp. The first uploader of the live event (that creates and shares the
URN) will determine the epoch to use as the reference timestamp.

* When you start downloading a live event from any source, this could be
from any sources that is not the initial uploader, and this source will noit
necessarily have recorded the start of the event. You may need to look for
other sources within some limited time window before the first data you
receive from that source. But many users will expect to see the event fast,
so your window is necessarily limited: this can be made by initial buffering
before playing the live event with the data you already have downloaded.

* The start of the event you will play will not be at timestamp 0, before
the epoch is arbitrary. But all sources will share the same epoch, as
determined by the first uploader.

* If we must allow multiple users sharing the same event without depending
on a single initial source, the choice of epoch for the encoding of each
independent sources should be synchronized (for example using the Unix time
epoch, or some easily remembered epoch like January 1st 2000 at 00:00 UTC). 

* If the same event is available from multiple independant sources, it
should be possible to use all of them if they agree about some data: for
example they share the same URN for service discovery, and the same epoch
for encoding their absolute timestamps. But each service should remain
encoded under their own URN if the live event is encoded separately (because
the data they transmit may use different codecs, with variable quality, and
variable encoding bandwidth). This would allow using in parallel sources
with low encoding bandwidth and sources with higher quality.

* The precision of timestamps can be specified as a single integer of
seconds. But for some stream encodings, it should be possible to specify a
higher precision by specifying also an exact position in the encoded stream
within that second.

* There's a standard in MPEG for handling such timestamps: it uses an
absolute timestamp in exact seconds since epoch, plus a frame counter (the
number of frames per second is fixed and determined only by the average
encoding bandwidth per second of the stream), plus a byte counter within
frames. If such identification is needed, we need some coherent
representation in the protocol to support multi-field timestamps (however
the frame counter should be encodable within a 1 or 2 byte, and the byte
position within a frame should be encodable in 3 or 4 bytes, so all you need
is to append the absolute timestamp since epoch by 4 to 6 bytes), so that
you can detect where you are missing some data.

* If the bitstream uses some variable bitrate, each frame must be encoded
with a leading length (similar to a filelength) as part of the transmitted
data, and when sharing fragments you must also pass this information, not
just the position of the start and end of the fragment, or this information
must be part of the data that will be checked by TigerTree data (I prefer
this solution because it does not complicate the protocol).

* When downloading from sources with distinct origin URNs (distinct original
codecs), only the absolute timestamps should be used to identify fragments
that share the same exact time. The frame counter should be used only if
each original source is encoded at the same frame rate. The byte positions
within frames should be used only if the service comes from the same
original delivery URN (i.e. the same codec), otherwise the data will not
match the TigerTree Data. Each origin delivery URN should be associated by
its own TigerTree Data.

* In TigerTreeData, each node should not represent partial frames. A single
TigerTree data node may represent several frames if needed only if these
frames where encoded from the same origin source identified by its delivery
URN.

This should be usable to support sharing live webcasts, demos, free
web-Radios, or free web-TVs, without having to pay the services of a costly
CDN network.

Another application of this protocol (although swarming will probably not be
used as there will be only one source) will be to support telephony
applications, but it could be interesting to organize conferences, where
each participant to the conference can download or upload to the others:
they use the same service URN for discovering themselves, as returned by a
standard search (by keyword if searching the conference by its descriptive
name or the name of its participants), and then each participant will
indicate the URN, stream format (basically the frame rate per second should
be enough), and epoch it uses in the stream it creates and delivers the
other participants, before actually delivering the stream data (whose
fragments will then be identified by timestamp+frame counter+byte position
within each frame)...

In a first attempt to support the protocol, we could start by implementing
it at a fixed frame rate (1 frame per second) and a common epoch (January
1st, 2000, 00:00 UTC). The byte position within the single frame that makes
one second will just be 32bit (thus, this will limit the supported maximum
bandwidth, or will limit the length in seconds of the time window for
buffering): under this simplified scheme, each one-second frame is seen as a
separate file whose length is fully determined by the origin codec, and
identifiable by its "delivery URN".

These multiple 1-second files making the same live stream (but each
identified by its is own "delivery URN"), are found on the network because
they share the same "service URN": we need to be able to search for service
URNs, but in a first implementation, we could search the services by its
name as long as there's no overlay network to search for URNs, using
traditional Gnutella searches by keyword: the "delivery URN" will be part of
the query result, as well as the "service URN" needed for making sure it
belongs to the same service.

Both the "service URN" and the collection of "delivery URN" making up the
same stream (from different origins) can use the simple "GUID:" scheme
followed by some randomly generated bit pattern.

What do you think of this concept? Why isn't there (still) any support for
searching and transferring live streams in Gnutella, so that it will replace
the costly CDN services?

It would allow building a completely free "GnuCDN" (GNUtella Content
Delivery Network) based on the existing capabilities of Gnutella agents for
swarmed download and the queueing policy based on maximum file fragment
sizes plus queueing? There are tons of associative webradios that hate
paying so much for being distributed to the Net, or that are currently
limited by the number of active streams.

With a Free CDN, these non-profit live event organizers would no longer be
limited in the number of users that can assist to these events and the
costly CDNs (made by very large corporations like Intel, Motorola, large
internet providers or national and international telecom companies) could be
avoided.

Note also that it would not prohibit recording the live events (you just
need to store locally the fragments you have received, in a file format
suitable for replaying it, such as a MPEG file format used as an envelope
format supporting the storage of timestamps for the fragments that have been
received). Once the live event is terminated, you just have to close the
envelope file, and this becomes a standard MPEG file, which can be shared
completely using the existing protocol.



----------  Weitergeleitete Nachricht  ----------

Betreff: RE: [the_gdf] returning results for partial downloads
Datum: Samstag, 6 de Oktober de 2007
Von: "Philippe Verdy" <[email protected]>
An: [email protected]



> -----Message d'origine-----
> De : [email protected] [mailto:[email protected]] De la part
> de Zlatin Balevsky
> Envoyé : vendredi 5 octobre 2007 20:22
> À : [email protected]
> Objet : [the_gdf] returning results for partial downloads
> 
> Christian suggested that it would help rare file distribution if
> search results are returned for partial downloads.  After a little
> deliberation, it seems like this idea is very feasible.  The results
> will have to contain the bitprint and the ranges which have been
> successfully verified.  On the receiving side, clients can use the
> range information to determine if the entire file is available over
> the network and use that to decide if the result should be displayed.
> 
> Comments?

I have also suggested this since long (about 3 years ago), it was debated
several times, but not implemented since, most probably because it caused
problems in the reliability of swarmed downloaded.

But in fact this was caused by implementation bugs, causing swarmed
downloads to fail quite often if the same source was changing during the
transfer the set of ranges it currently has for a file and if the range
supported by a source was not contiguous from the start of the file.

But if we want to support fast and reliable swarmed downloads, we must be
able to support downloading from any source not necessarily from the start
of the file, but from any position; so as long as the swarmed download does
not complete, our local file will have as many "holes" in it as the number
of active sources we have used, so our local copy will contain multiple, non
contiguous fragments.

But even in this case, we can still share the fragments we already have
downloaded provided that they have been FULLY checked according to the
fragment of TigerTree data that represents it. This is possible for each
localfile fragment that is FULLY covered by a node in the TigerTree data,
and of course, it requires having this TigerTree data ready for this check.

But the TigerTree datamay be downloaded asynchronously in a separate time
after the first fragments have been downloaded from one source (because that
source may not have TigerTree data for this file, and we need to find
another source for that TigerTree data).

Consequently, we'll have locally some fragments that are still missing, some
fragments that have been downloaded but can't be checked because they are
not fully covered by some matching TigerTree data node, and some fragments
that have been downloaded and that now match with the tigertree data. Only
these last fragments can be shared safely and immediately even if the file
is not complete.

For any fragment that was previously downloaded, but that reveal later to be
corrupted according to the TigerTree data node we have now and that covers
it completely, such fragments must be dropped and reloaded from another
source. But this will continue to work because we have still not shared it.

This scheme works only because file fragments are checked before being
shares. And it benefits not only to rare files (allowing the number of
sources supporting a rare file to augment during the download by multiple
clients that still don't have a complete copy), but for ALL files on general
More generally it will avoid one client to steal ALL the upload bandwidth
from any uploader, because the uploader will be able to distribute its own
workload to lots of clients, if it only gives them a limited fragment size
before queueing again multiple clients with ongoing transfers):

the idea is to have for example N clients with active uploads in progress
plus N (or 2N: this is tuneable) clients temporarily idled in the requeueing
list. All the other newcoming candidate clients are queued with a lower
priority with the existing mechanism. In fact I would militate for an
implementation where each file can only have at most one active upload in
progress to any source, so this upload should be as fast as possible, but
limited to a small fragment size that can be checked immediately by the
receipinet according to TreeData.

Then that client is requeued, and other clients are served, but will be able
to use also the upload resources of the first served clients even if what
they have is partial. Each client that has successfully downloaded a
fragment will need to inform as soon as possible the uploading source so
that it can inform the other candidate clients to the same file that another
supplementary source is available that will help supporting the charge.
Rapidely this system will converge to faster speed for everybody.


-- 
Unpolitisch sein
Heißt politisch sein
Ohne es zu merken. 
- Arne Babenhauserheide ( http://draketo.de )
-- Weblog: http://blog.draketo.de

-- Mein öffentlicher Schlüssel (PGP/GnuPG): 
http://draketo.de/inhalt/ich/pubkey.txt


[Non-text portions of this message have been removed]