Subject: Re: [ppsp] Selection of PPSP peer protocol draft

From: Rui Cruz <[email-masked]>
Date: Thu, 1 Dec 2011 13:22:25 +0000

On 30/11/2011, at 08:53, Arno Bakker wrote:

> On 29/11/2011 14:26, Rui Cruz wrote:
> >
>> And if the encoded complex structured media is segmented in rather large
>> sized chunks (of 10x or 100x KiB) *each chunk* would have to be mapped,
>> I suppose, to a quite large Hash tree to split the data in byte ranges
>> for the datagrams. So, instead a a single Bin tree, a complex Structured
>> Media with a duration of an hour (3600 seconds) would require at least
>> 18000 Root hashes for chunks with 2 seconds encoded in 10 layers. Would
>> this not be overkill?
>> 
> 
> Hi
> 
> I don't quite follow what you mean here. If the content consists of 1800 intervals encoded in 10 layers, there will be 18,000 addressable chunks of content. In the simplest case in swift, these are mapped into a single tree with 18,000 hashes as leaves that is identified by a single root hash. As 18,000 hashes consume about 360 kilobytes with 20-byte SHA1 hashes, I'd hardly call that overkill.

Hi Arno,

The default swift-over-UDP "chunk" size is 1 KiB, and unless I misinterpret  sections 6.1.1 and 6.1.8 of the draft, for a very common quality H.264 movie file of the size I mentioned (around 1 GiB size for one hour duration), even if not coded in layers, would require a single tree with 1,000,000 hashes as leaves, i.e., would consume 20 MiB with 20-byte SHA-1hashes.

But with the given example of a Structured Media with 18,000 addressable "content chunks" having an average of 50 KiB each, the math are similar, it would require 900,000 hashes, i.e., would consume 18 MiB with 20-byte SHA-1hashes.

How feasible and efficient would it be to handle such a huge single tree? 

> 
> Please explain how you intend to do content integrity protection in this case.

Integrity is fundamental, and I do understand what is is clearly stated in section 9.2 of the draft, i.e., that the usage of Merkle hash trees restricts the technique for "exclusively single-file transfers".

So, for high quality "Structured Media", other techniques might need to be considered, for example, with media files split in multiple addressable (eventually hierarchical) segments, organized as a directory of files, or in multiple stream files, using multiple swift "channels", i.e., swarms. 
Again, for the same example, with 10 coded layers, (not to mention a few selectable audio language streams) would require joining and controlling  >10 swarms in order to stream the media with the same content integrity conditions. 

> 
> Regards,
>    Arno
> 
> _______________________________________________
> ppsp mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/ppsp

---

From: Martin Stiemerling <[email-masked]>
Date: Thu, 1 Dec 2011 13:54:52 +0000

[speaking as individual contributor and not as chair of the PPSP WG]

Hi all,

I have just posted the review of draft-grishchenko-ppsp-swift and draft-gu-ppsp-peer-protocol. 

I have to repeat what I have said during the PPSP session at the IETF-82 meeting: 
draft-gu-ppsp-peer-protocol is missing many, many important parts which make a protocol, such as what are the responses to the requests, the semantics of the protocol, etc. 
I know that there are some messages defined, which can be the response messages, but it is not obvious at all from reading the document.

draft-grishchenko-ppsp-swift makes a pretty good start in defining a p2p tv protocol and I can imagine to implement it, given that there would be better syntax defintions. It has most of the important parts described, e.g., message exchanges or how bit maps look like and are treated, though also important parts like the error treatment/messages is missing.
It is debatable if certain choices, such as the Merkle trees, are acceptable for everybody or the current implementation in the protocol is acceptable. However, you can see from this type of point raised, that there is more meat to start discussions about the details IMHO.  

I would say:
Let's take draft-grishchenko-ppsp-swift as PPSP peer protocol, work on the rough edges, and add things which are missing. 

  Martin

[email-masked]

NEC Laboratories Europe - Network Research Division NEC Europe Limited | Registered Office: NEC House, 1 Victoria Road, London W3 6BL | Registered in England 2832014 

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On Behalf Of
> Martin Stiemerling
> Sent: Thursday, November 24, 2011 3:43 PM
> To: [email-masked]
> Subject: [ppsp] Selection of PPSP peer protocol draft
> 
> Dear all,
> 
> The working group has to make a decision which peer protocol proposal to
> choose as basis for the PPSP peer protocol.
> 
> We have to independent proposals:
> - draft-gu-ppsp-peer-protocol-03
>   (http://tools.ietf.org/html/draft-gu-ppsp-peer-protocol-03)
> - draft-grishchenko-ppsp-swift-03
>   (http://tools.ietf.org/html/draft-grishchenko-ppsp-swift-03)
> 
> Both proposals for a peer protocol have been presented at the IETF meeting.
> The slides are available here:
> - draft-gu-ppsp-peer-protocol-03:
>   http://www.ietf.org/proceedings/82/slides/ppsp-3.pptx
> - draft-grishchenko-ppsp-swift-03
>   http://www.ietf.org/proceedings/82/slides/ppsp-1.pdf
> 
> The feedback given at the IETF meeting about both proposals is documented in
> the draft meeting minutes:
> http://www.ietf.org/proceedings/82/minutes/ppsp.txt
> 
> Please state your **technical** opinion about which peer protocol proposal
> you would prefer on the PPSP mailing list until November 30th.
> 
> With best regards
> 
>   Yunfei and Martin
>      PPSP co-chairs
> 
> [email-masked]
> 
> NEC Laboratories Europe - Network Research Division NEC Europe Limited |
> Registered Office: NEC House, 1 Victoria Road, London W3 6BL | Registered in
> England 2832014
> 
>

---

From: Johan Pouwelse <[email-masked]>
Date: Thu, 1 Dec 2011 15:30:57 +0100

On 1 December 2011 14:54, Martin Stiemerling
<[email-masked]> wrote:
> I would say: Let's take draft-grishchenko-ppsp-swift as PPSP peer protocol, work on the rough edges, and add things which are missing.

Yes, I think nobody has disagreed with this approach in the recent
activity burst.
Hopefully we can set the following as our ambition for 83rd IETF March
2012 in Paris :

  - Polished&finished tracker+peer protocol
  - Conducted open field trials with the reference implementations
{willing to organize this}
  - All PPSP members submitted their contributions in text to the
draft + real-world code to the Open Source reference implementation
  - Reference implementation has passed Quality Assurance testing, has
no outstanding known bugs and is ready for production-level usage

Given that our original planning was IESG "Proposed Standard" status
last Aug 2011, I hope was can commit to making up some time.

Greetings from Delft, johan.

---

From: zhangyunfei <[email-masked]>
Date: Fri, 2 Dec 2011 00:20:53 +0800

Hi all,
    Please see in line.

Yunfei

zhangyunfei

From: Arno Bakker
Date: 2011-11-30 16:41
To: [email-masked]
Subject: Re: [ppsp] Selection of PPSP peer protocol draft
On 29/11/2011 08:13, Y. Richard Yang wrote:
 >
> * Are there any experimental results of swift at large scale real
> experiments?
>

Hi Richard

we test swift using manifold testing with up to 200 emulated peers, with 
varying network configurations. We have plans to conduct another 
experiment with the WikiMedia foundation, and Yunfei, the co-chair is 
willing to conduct experiments with the PPSP peer protocol with 
ChinaMobile customers.

[Yunfei]As an execution of "engineering practice talks"culture in IETF, PPSP WG values much on the real experiments result at large scale. In this sense, I am going to say that it's better to have a test result report in next PPSP meeting, which helps the WG better evaluate the proposals, rather than in a pure theoretical sense. We are interested in participating in such trails with agreed protocol.
> * According to our experiences at building an experimental p2p streaming
> system at Yale, a real protocol quickly becomes complex as we continue
> to extend it to handle challenges in real settings. The extension scheme
> of the protocol needs careful thinking.
>

IMHO, the protocol should provide the mechanisms that support many 
different policies (chunk selection, peer discovery & selection, etc.), 
without becoming overly generic. The latter is the complex bit ;o)

>
>      - page 4 top: "... peer connects to a random set of other peers ..."
> why random?
>

I think I wrote random to distinguish swift from strictly tree-based 
protocols. Peer selection is pluggable in swift, to also allow input 
from e.g. ALTO servers.

>      - page 4 "... omits HAVE messages as a way of choking A."
>
>         Also Page 7 on withholding HAVE. Also on Page 7 on withholding
> error messages.
>
>         I typically do not like such information-hiding designs. Informed
> decisions often are better, faster decisions.

The reason why we don't have explicit CHOKE/UNCHOKE is because in 
practice they do not guarantee that a peer will actually send you data 
(the "snubbed" syndrome). Hence, we decided to go with observed 
behaviour (if a peer responds, fine, ask more, otherwise leave it).
But apparently you feel differently?

>      - page 4 (also page 9) "... A sends a datagram containing HAVE
> messages for the chunks it just received to all its peers." Specifying
> such a push-just-received model may not be necessary.
>

We needed push-just-received in our current chunk-selection policies for 
live and VOD. We have to look into Fabio Picconi's remarks about 
lastest-useful policies for live that may not need it. In which 
situations does your system use another policy?

>      - The design is essentially pushing for an uploader centric design.
> This is unnecessary.
>

Can you elaborate a bit on that, I'm not sure what you mean. Normally, 
receivers explicitly request chunks via HINTs. Swift allows for live 
streaming protocols which push chunks.

>         - I am wondering is the scheme is patented. CK Wong and Simon Lam
> presented such a design in 1998 (for disclosure, Simon Lam is my PhD
> advisor):
> http://www.cs.utexas.edu/users/lam/395t/slides/DigitalSignature.pdf
>

Wesley Eddy, the transport area director already contacted the SEC area 
directors about it. Apparently there was a patent that might have 
covered the hash tree as we use it (I am not a lawyer), but it expired, 
no. 4,309,569:

http://patft.uspto.gov/netacgi/nph-Parser?Sect2=PTO1&Sect2=HITOFF&p=1&u=%2Fnetahtml%2FPTO%2Fsearch-bool.html&r=1&f=G&l=50&d=PALL&RefSrch=yes&Query=PN%2F4309569

In any case, it is the desire of the working group to support multiple 
methods of chunk addressing and content integrity protection (and I am 
rewriting the draft to reflect this), so patents do not impact selection.

>         - On the other hand, I am wondering if using such a binary tree
> based design is necessary, as elaborated schemes typically can have
> limit extensibility, compared with simple straightforward schemes . In
> particular, how much savings are we talking about, at the cost of
> choosing a particular binary tree based representation scheme? Such
> information can be helpful.
>

The binmap representation is described and compare to others in
http://www.pds.ewi.tudelft.nl/fileadmin/pds/reports/2011/PDS-2011-005.pdf
And, the new draft will allow different addressing methods, as just 
mentioned.

[Yunfei] The basic bitmap expression should be addressed first and elaorated schemes can be optional.
But currently I am not clear if the current swift chunk availability expression still works well in SVC or MDC envrionment.

CU,
     Arno

---

From: zhangyunfei <[email-masked]>
Date: Fri, 2 Dec 2011 01:12:41 +0800

Hi Johan，
    I would say your proposal on the outcome of IETF83 is beneficial for evaluating the protocol candidates. It's good to have the field trial report in next IETF. Regarding the timeline, we are not hastily publish a RFC in order to catch up with or make up the time. We need solid discussion and verification of the effect on the proposed protocols while trying to balance between the quality and the time.

Yunfei

zhangyunfei

From: Johan Pouwelse
Date: 2011-12-01 22:30
To: Martin Stiemerling
CC: [email-masked]

---

From: Arno Bakker <[email-masked]>
Date: Fri, 2 Dec 2011 08:53:59 +0100

On 01/12/2011 14:22, Rui Cruz wrote:
>
> The default swift-over-UDP "chunk" size is 1 KiB, and unless I
> misinterpret sections 6.1.1 and 6.1.8 of the draft, for a very common
> quality H.264 movie file of the size I mentioned (around 1 GiB size for
> one hour duration), even if not coded in layers, would require a single
> tree with *1,000,000* hashes as leaves, i.e., would consume *20 MiB*
> with 20-byte SHA-1hashes.
>

Hi

your calculation is correct for the default 1K. For that default, the 
size of the Merkle hash tree is 3.9% of the content, following this formula:

     hashsize * math.pow(2,math.log(nleaves,2)+1)

3.9% is not negligible on simple hardware, but we don't consider it 
overkill. On such hardware, one can use larger UDP chunks (4K, 8K) to 
get a smaller tree (as nleaves becomes smaller). On normal PC hardware, 
39 MiB is negligible, IMHO.

With the right implementation of SHA1 (we use Torvald's as used in git), 
hashing 1 MiB as one big chunk is just marginally faster than hashing it 
as 1024 chunks of 1 kilobyte.

Note that the number of hashes involved is a direct consequence of 
choosing UDP (for NAT/firewall and flexible congestion control reasons). 
The problem with UDP is that the larger a UDP datagram is, the higher 
the chance it gets lost, because the loss of a single IP packet carrying 
a fragment causes the loss of the whole UDP datagram.

The choices are then (1) add a fragmentation/reassembly mechanism to the 
P2P protocol such that a large P2P chunk can be reliably sent using 
multiple UDP datagrams, with a single hash per P2P chunk. Or (2) use 
small P2P chunks sent in a single UDP datagram and have more hashes. 
Disadvantages of (1) are increased complexity and vulnerability. 
Malicious peers can send you all but the last subchunk that you need to 
get the full P2P chunk and thus waste your bandwidth.
In swift, we chose (2), i.e., the atomic datagram principle such that 
every UDP datagram that you receive can be integrity checked. So far, 
this choice has not lead to any showstoppers.

If the size of the hash tree is a problem on your hardware of choice,
one can run swift over TCP and have only 1800 hashes in the example of 1 
hour in 2 second intervals.

> Again, for the same example, with 10 coded layers, (not to mention a few
> selectable audio language streams) would require joining and controlling
> *>10 swarms* in order to stream the media with the same content
> integrity conditions.
>

In the cited example, each swarm would have a 3.5 MiB hashtree, so the 
complete 900 MiB SVC download would consume 35 MiB in total. Swift has 
been designed to have low per-peer administration cost, so having many 
peers should not be a problem. Hence, I don't really see your point.

Furthermore, we haven't finished evaluating the impact of SVC/MDC on 
swift, so mapping different layers into a single swarm is still an option.

I'm still interested in hearing how content integrity protection works 
in SARACEN.

CU,
       Arno

---

From: zhangyunfei <[email-masked]>
Date: Fri, 2 Dec 2011 16:44:51 +0800

Hi Arno,
    Please see inline.

BR
Yunfei

zhangyunfei

From: Arno Bakker
Date: 2011-12-02 15:53
To: [email-masked]

Hi

[Yunfei] There is a potential conflict between the UDP packet size and the network environment, i.e., in mobile networks, in order to 
decrease the overhead of hash tree expression, a bigger chunk is better. However this will create more possibility of higher loss rate.

CU,
       Arno

BR
Yunfei

---

From: Arno Bakker <[email-masked]>
Date: Fri, 2 Dec 2011 09:56:49 +0100

On 02/12/2011 09:44, zhangyunfei wrote:
> [Yunfei] There is a potential conflict between the UDP packet size and 
> the network environment, i.e., in mobile networks, in order to
> decrease the overhead of hash tree expression, a bigger chunk is better. 
> However this will create more possibility of higher loss rate.

Exactly. But note that hash tree size depends primarily on the size of
the content, and an 1 gigabyte video may be a bit much in the mobile
domain ;o) That said, with a 4K UDP packet the tree is already down to
~10 MB for that gigabyte video, so when you have the bandwidth plan the
tree will easily fit on your mobile.

CU,
    Arno

---

From: Johan Pouwelse <[email-masked]>
Date: Fri, 2 Dec 2011 15:16:48 +0100

2011/12/1 zhangyunfei <[email-masked]>:
>     I would say your proposal on the outcome of IETF83 is beneficial for
> evaluating the protocol candidates. It's good to have the field trial report
> in next IETF.

OK, a "field trial report" is then the goal for March 2012, IETF83.

In you role as co-chair, do you see that the WG could accept a
"field trial report" as an official WG document?

If so, then we're looking for "informational RFC" volunteers/co-authors....
  - has access to network equipment
  - time to conduct measurements / create scripted tests
  - experience with operational/low-level protocol stack matters
  - wireshark or other packet capture tools

Several field trial have been held now with Libswift. First field trial focused
on downloading and congestion with 200 peers on numerous servers.
Plus two early field trial with Libswift focussed on NAT puncturing.
First NAT-trial had 900 unique Internet participants.
Next field trial had NAT puncture improvements involved 1500 participants.
Field trial report focused on NAT puncturing only, does not mention
that swift is used:

http://pds.twi.tudelft.nl/reports/2010/PDS-2010-007.pdf

 -j

> in next IETF. Regarding the timeline, we are not hastily publish a RFC in
> order to catch up with or make up the time. We need solid discussion and
> verification of the effect on the proposed protocols while trying to balance
> between the quality and the time.
>
> Yunfei
> ________________________________
> zhangyunfei
>
> From: Johan Pouwelse
> Date: 2011-12-01 22:30
> To: Martin Stiemerling
> CC: [email-masked]

---

From: Rui Cruz <[email-masked]>
Date: Fri, 2 Dec 2011 17:11:56 +0000

> tree will easily fit on your mobile.

Hi,

I would say that this type of severe constraint or limitation should be addressed and discussed in PPSP. 
PPSP is chartered to standardize protocols to last long and to be supported on current and future (IP) network technologies.
LTE is just around the corner, providing higher bandwidth for mobile devices, and so, PPSP should not constrain its usage/implementation to a limited set of P2P TV distribution architectures, of device types, of networks, of multimedia types (either sizes or structures) or streaming modes (e.g., live, live-interactive, on-demand, etc).

Using jumbo packets should not even be equated due to the high risk that losses bring, and therefore the simplest and safest measure would be to "run swift over TCP" as suggested before.
 
For mobile networks (3G/HSPA/EV-DO) it is currently possible to stream very large high quality contents, adaptive to the varying nature of these mobile wireless networks, and using "limited" capacity devices (not PCs).
Even live streaming of these contents is already available, with a fairly short start delay of around 10 seconds (for HLS).

So, the "big technical problem" to stream a "single-file" common movie of 120 minutes, i.e., typically a >2 GiB size coded media, can perfectly be split in several fairly addressable issues by segmenting the media and handling the segments separately, with the advantage of turning possible handling multiple representations (adaptive multi-rate), or layers (adaptive quality), or layer views (3D with adaptive quality).

We have some results from an early version (proof of concept) of the prototype, described in the attached paper with complementary results in the presentation slides, also attached:

P. Moscoso, R. S. Cruz, and M. S. Nunes, “Internet TV Architecture Based on Scalable Video Coding,” in Proceedings of the 9th European Interactive TV Conference Workshop on Quality of Experience for Multimedia Content Sharing: Ubiquitous QoE Assessment and Support, EuroITV QoEMCS’11, Jun. 2011.

-------
There are already commercial high quality media streaming to mobile devices, using or not P2P, e.g., Bloomberg TV (live and on-demand to iPad with 3G/WiFi), BBC iPlayer for iPad (on-demand with 3G/WiFi), Spotify (P2P assisted audio streaming).  

Regards,

Rui Cruz
[email-masked]

IST/INESC-ID/INOV - Lisbon, Portugal
__________________________________________
ppsp mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/ppsp

---

From: Rui Cruz <[email-masked]>
Date: Fri, 2 Dec 2011 23:09:31 +0000

On 02/12/2011, at 07:53, Arno Bakker wrote:

> one can run swift over TCP and have only 1800 hashes in the example of 1 hour in 2 second intervals.
> 

So, the advantage of running swift over UDP might be restricted to specific types of content, as, for "difficult" multimedia contents, the safest option would be to run swift over a guaranteed delivery transport protocol.

> In the cited example, each swarm would have a 3.5 MiB hashtree, so the complete 900 MiB SVC download would consume 35 MiB in total. Swift has been designed to have low per-peer administration cost, so having many peers should not be a problem. Hence, I don't really see your point.

What is then the purpose of a P2P swarm to distribute only a layer of a content that would be completely useless without the remaining hierarchical layers?

For instance, if layer 2 out of 10, or the audio layer, were not available (no active peer sharing those content components, for some reason), then the stream would not reach higher quality nor have audio, even if the swarms for higher layers would still be available.
The administration cost in this case is not on having many peers but, on the peer side, to figure out what to join, and at Distribution System side, ensuring the availability of all the components of a media at any moment. Without that guarantee, i.e., if there is no implementation of a controlled view-upload decoupling scheme, the impact of churn would ruin completely the purpose of scalability and adaptability that seeks to maximize the end-user QoE even in difficult network environment conditions.

> Furthermore, we haven't finished evaluating the impact of SVC/MDC on swift, so mapping different layers into a single swarm is still an option.

I do really understand the "problem".

> I'm still interested in hearing how content integrity protection works in SARACEN.

P2PNext project is two years advanced (started in 2008) in relation to SARACEN (started in 2010). Content integrity, is being addressed in SARACEN, but due to the nature of the SARACEN Platform architecture, the issue is primarily related with content protection and licensing and only then with content integrity in the distribution network. For integrity when P2P is used, a "content chunk" signing approach is being addressed, using signature-amortization or sign-and-correct techniques, as the most promising.

IMHO we should not be discussing each EU project here, but the technical issues of PPSP protocols (related or not with the techniques used on those projects).

Regards,

Rui Cruz
[email-masked]

---

From: zhangyunfei <[email-masked]>
Date: Mon, 5 Dec 2011 10:40:33 +0800

Hi Johan,
    Please see inline.

zhangyunfei

From: Johan Pouwelse
Date: 2011-12-02 22:16
To: zhangyunfei
CC: Martin Stiemerling; ppsp
Subject: Re: Re: [ppsp] Selection of PPSP peer protocol draft

[Yunfei] Personally I see the necessity of such a document. If there are ENOUGH interest 
in the WG, we have no reason to refuse such kind of WG draft. I would say that the field trial 
is a good measure to evalute the effect of the proposed protocols in answering the questions rasied by the WG.

 -j

---

From: Arno Bakker <[email-masked]>
Date: Mon, 5 Dec 2011 08:57:31 +0100

> addressed and discussed in PPSP.

Let me rephrase: "That said, with a 1K UDP packet the tree is just 39 MB 
for that gigabyte video, so when you have the bandwidth plan the
tree will easily fit on your mobile."

The resource requirements of the swift Merkle hash tree content 
integrity protection can be met by current mobile (my EUR 125 phone has 
512 MB) and STB hardware. These hardware capabilities will grow with 
advances in network technology, so that part of swift is present and 
future proof.

Regards,
     Arno

---

From: Arno Bakker <[email-masked]>
Date: Mon, 5 Dec 2011 09:22:27 +0100

On 03/12/2011 00:09, Rui Cruz wrote:
> What is then the purpose of a P2P swarm to distribute only a layer of a
> content that would be completely useless without the remaining
> hierarchical layers?
>
> For instance, if layer 2 out of 10, or the audio layer, were not
> available (no active peer sharing those content components, for some
> reason), then the stream would not reach higher quality nor have audio,
> even if the swarms for higher layers would still be available.

All peers interested in the content would also join the audio swarm. 
Peers interested in the higher layers would join the higher layer 
swarms, including, of course, some initial seeders. I don't see your 
problem.

> The administration cost in this case is not on having many peers but, on
> the peer side, to figure out what to join, and at Distribution System
> side, ensuring the availability of all the components of a media at any
> moment.

A nice specification, I believe some people call it a Media Presentation 
Description, can tell the client-side software exactly which layers and 
streams there are.

>For
> integrity when P2P is used, a "content chunk" signing approach is being
> addressed, using signature-amortization or sign-and-correct techniques,
> as the most promising.
>

Do these schemes have any impact on the protocol as specified in the 
draft-cruz-ppsp-http-peer-protocol (expired at present) and 
draft-gu-ppsp-peer-protocol?

> IMHO we should not be discussing each EU project here, but the technical
> issues of PPSP protocols (related or not with the techniques used on
> those projects).
>

To get a fully working P2P streaming system it will have to be clear how 
all requirements can be met, even with a simple reference to existing 
work that is compatible.

Regards,
     Arno

---

From: Csaba Kiraly <[email-masked]>
Date: Mon, 05 Dec 2011 10:49:30 +0100

On 12/05/2011 09:22 AM, Arno Bakker wrote:
> All peers interested in the content would also join the audio swarm. Peers interested in the higher layers would join the higher layer swarms, including, of course, some initial seeders. I don't see your problem.

Arno,
I have also considered changing to a model of several swarms (each layer is a swarm, audio is a separate swarm) per channel. It has some advantages, but it also complicates many other things.
Pros:
- it simplifies chunk ID schemes
- it simplifies integrity check
- it allows for some nice topology optimizations among peers interested in this or that part of the stream only.

Cons:
- it also complicates topology management, since you have to handle several swarms
- it complicates rate-control algorithms, since you have to sync some of these methods between the various swarms.

As a consequence, I would prefer a protocol that does not mandate a model that e.g. audio and video must be handled as separate swarms ... if it can be avoided.

Csaba

---

From: Arno Bakker <[email-masked]>
Date: Mon, 5 Dec 2011 11:12:47 +0100

On 05/12/2011 10:49, Csaba Kiraly wrote:
>
>> All peers interested in the content would also join the audio
>> swarm. Peers interested in the higher layers would join the higher
>> layer swarms, including, of course, some initial seeders. I don't
>> see your problem.
>
> Arno, I have also considered changing to a model of several swarms
> (each layer is a swarm, audio is a separate swarm) per channel. It
> has some advantages, but it also complicates many other things.
> Pros: - it simplifies chunk ID schemes
 >       - it allows for some nice topology optimizations among peers
> interested in this or that part of the stream only.
>
> Cons: - it also complicates topology management, since you have to
>         handle several swarms
>       - it complicates rate-control algorithms, since you have to
>         sync some of these methods between the various swarms.
>
> As a consequence, I would prefer a protocol that does not mandate a
> model that e.g. audio and video must be handled as separate swarms
> ... if it can be avoided.
>

Hi

I don't think handling several swarms is a problem. Whether your SVC 
chunk selection algorithm says "download chunk X" or "download chunk X 
from swarm S" doesn't really matter. I assume the SVC algorithm will be 
doing download rate control implicitly by means of its choice of chunks 
and layers, right? Doing global upload rate control on a set of swarms 
is not complex, IMHO, and you may need to do that already for seeding 
management of previous swarms.

Orthogonally, we haven't finished evaluating the impact of SVC/MDC on
swift, so mapping different layers into a single swarm (as you suggest 
elsewhere) is another option to use.

Finally, the working group wants swift to support different chunk 
addressing schemes, for which we are rewriting the draft, so if you have 
another mapping from layers/streams to chunks and swarms, you are free 
to implement that.

CU,
     Arno

-- 
(faculty email system is being migrated, email address will remain
[email-masked])

---

From: Csaba Kiraly <[email-masked]>
Date: Mon, 05 Dec 2011 11:44:50 +0100

On 12/05/2011 11:12 AM, Arno Bakker wrote:
> I don't think handling several swarms is a problem. Whether your SVC chunk selection algorithm says "download chunk X" or "download chunk X from swarm S" doesn't really matter. I assume the SVC algorithm will be doing download rate control implicitly by means of its choice of chunks and layers, right? Doing global upload rate control on a set of swarms is not complex, IMHO, and you may need to do that already for seeding management of previous swarms.

It is definitely more complex than for one swarm :). Jokes apart, I think doing rate control and topology decision on multiple swarms is a bit more complex than doing it for one, so I would leave the liberty to a user of the protocol to use just one swarm (again, if it is possible). I do support the multi-swarm model, I think it is more powerful, but we should better not restrict the power of the single swarm model for the sake of it. It could be better to waste some bits on the wire (e.g. having composite chunkIDs made up of sub-stream ID and a sequential ID) and leave more liberty to the user, than super-optimizing the wire format and restricting possibilities.

> swift, so mapping different layers into a single swarm (as you suggest elsewhere) is another option to use.

Indeed, I was meditating on this a bit more. I think your hashing scheme can be nicely improved to a scheme where separate sub-streams are kept on distinct sub-trees and merged into a master hash at the top (or in case of live, at every level of the tree). This way, you could substitute any sub-stream with a small amount of hashes, providing integrity protection over a the rest.

>
> Finally, the working group wants swift to support different chunk addressing schemes, for which we are rewriting the draft, so if you have another mapping from layers/streams to chunks and swarms, you are free to implement that.
>
> CU,
>     Arno
>

Csaba

---

From: Rui Cruz <[email-masked]>
Date: Mon, 5 Dec 2011 11:05:12 +0000

On 05/12/2011, at 07:57, Arno Bakker wrote:

> Let me rephrase: "That said, with a 1K UDP packet the tree is just 39 MB for that gigabyte video, so when you have the bandwidth plan the

For a content composed by different source files (video segments, audio segments, text, etc.), organized in a directory, you hash each file separately (section 3.1.1 of swift draft).
Naturally that you may need to have the "rules" associated with the content (the Media Presentation Description), but MUST have the directory list of the hashes (root hashes for each file). 
And that directory list is not such a large file, perhaps a few 10s KiB for a one hour movie, and each file hash tree are significantly smaller.

> 
> The resource requirements of the swift Merkle hash tree content integrity protection can be met by current mobile (my EUR 125 phone has 512 MB) and STB hardware. These hardware capabilities will grow with advances in network technology, so that part of swift is present and future proof.

Right, but retrieving such large hash tree file from the beginning will have impact in start-up delay for mobile environments. 
But if the procedure can be split in several smaller hash tree files, fetched when necessary, the impact is reduced.

>    Arno

---------------------------
Best Regards,

Prof. Rui Santos Cruz
Chairman
IEEE Portugal Section
Av. Prof. Dr. Aníbal Cavaco Silva, IST-TagusPark, Office 1-5, 2744-016 Porto Salvo, Portugal
+351 214 233 200 (ext 5044), +351.939 060 939 (mobile)
[email-masked] 
[email-masked]
[email-masked]
www.ieee-pt.org
Advancing technology for humanity.

---

From: Rui Cruz <[email-masked]>
Date: Mon, 5 Dec 2011 11:24:40 +0000

> All peers interested in the content would also join the audio swarm. Peers interested in the higher layers would join the higher layer swarms, including, of course, some initial seeders. I don't se…

You are not considering the risks associated with unavailable substream (swarm), nor the sync problems, and you should. 

> A nice specification, I believe some people call it a Media Presentation Description, can tell the client-side software exactly which layers and streams there are.
> 

Right, that is exactly what we have considered in our drafts, not directly related with the protocol semantics, but with the operation logic. 

> Do these schemes have any impact on the protocol as specified in the draft-cruz-ppsp-http-peer-protocol (expired at present) and draft-gu-ppsp-peer-protocol?

The impact is similar to the one described in draft-grishchenko-ppsp-swift, but with a different logic in order to support Structured Media and interaction.

> To get a fully working P2P streaming system it will have to be clear how all requirements can be met, even with a simple reference to existing work that is compatible.

We can be perfectly clear without marketing it all the time.

Prof. Rui Santos Cruz
Chairman
IEEE Portugal Section

---

From: Arno Bakker <[email-masked]>
Date: Mon, 5 Dec 2011 12:58:35 +0100

On 05/12/2011 12:05, Rui Cruz wrote:
>>
>> Let me rephrase: "That said, with a 1K UDP packet the tree is just 39
>> MB for that gigabyte video, so when you have the bandwidth plan the
> For a content composed by different source files (video segments, audio
> segments, text, etc.), organized in a directory, you hash each file
> separately (section 3.1.1 of swift draft).
> Naturally that you may need to have the "rules" associated with the
> content (the Media Presentation Description), but MUST have the
> directory list of the hashes (root hashes for each file).
> And that directory list is not such a large file, perhaps a few 10s KiB
> for a one hour movie, and each file hash tree are significantly smaller.
>

I'm confused. The example was about a non-SVC 1 gigabyte file.
In any case, the size of the hash tree depends on the size of the 
content, whether as 1 file or split in parts.

> Right, but retrieving such large hash tree file from the beginning will
> have impact in start-up delay for mobile environments.
> But if the procedure can be split in several smaller hash tree files,
> fetched when necessary, the impact is reduced.
>

Huh? Hash trees do not need to be downloaded completely before a 
download can commence. A hash tree is downloaded incrementally with the 
chunks they cover.

CU,
     Arno

---

From: Rui Cruz <[email-masked]>
Date: Mon, 5 Dec 2011 12:25:18 +0000

On 05/12/2011, at 11:58, Arno Bakker wrote:

> In any case, the size of the hash tree depends on the size of the content, whether as 1 file or split in parts.

Right, could you then explain a bit more how it would work for a content organized as a directory of files (those 1800 segments of 50 KiB each, for example)?

> Huh? Hash trees do not need to be downloaded completely before a download can commence. A hash tree is downloaded incrementally with the chunks they cover.

OK, but the integrity verification of each chunk needs all the "necessary" uncle hashes. For such a deep hash tree, is it not a bit...too expensive in the size for the datagram and computation resources?
Could you elaborate a bit more for that example of 1,000,000 hash tree leaves (a 1 GiB movie in 1 KiB DATA Chunks)?

Prof. Rui Santos Cruz
Chairman
IEEE Portugal Section

---

From: Riccardo Petrocco <[email-masked]>
Date: Mon, 5 Dec 2011 18:17:16 +0100

Dear Rui, Arno and all,

Just to give my personal opinion on the SVC integration discussion.
I do not see the problems in distributing SVC, or other layered content,
over Swift.

The architecture is flexible enough to support multiple ways of
distributing different content.
The simplest solution for distributing SVC, in my opinion, would be to have
a single swarm
in which the layers are sequentially addressed by different sub-trees.

Considering this scenario, the cost of a higher layer, for a peer that is
not interested in retrieving it, would just be *at most* the size of a
single 20-byte uncle hash. The more layers
are distributed, the smaller the cost will be.

Just my 2 cents.

Best Regards,
Riccardo Petrocco

2011/12/5 Rui Cruz <[email-masked]>

> Right, could you then explain a bit more how it would work for a content
> organized as a directory of files (those 1800 segments of 50 KiB each, for
> example)?
>
>
>
> Huh? Hash trees do not need to be downloaded completely before a download
> can commence. A hash tree is downloaded incrementally with the chunks they
> cover.
>
>
> OK, but the integrity verification of each chunk needs all the "necessary"
> uncle hashes. For such a deep hash tree, is it not a bit...too expensive in
> the size for the datagram and computation resources?
> Could you elaborate a bit more for that example of 1,000,000 hash tree
> leaves (a 1 GiB movie in 1 KiB DATA Chunks)?
>
>
> CU,
>    Arno
> *Prof. Rui Santos Cruz
> *Chairman
> *IEEE Portugal Section
> *Av. Prof. Dr. Aníbal Cavaco Silva, IST-TagusPark, Office 1-5, 2744-016
> Porto Salvo, Portugal

---

From: Rui Cruz <[email-masked]>
Date: Tue, 6 Dec 2011 00:09:34 +0000

Dear Riccardo,

On 05/12/2011, at 17:17, Riccardo Petrocco wrote:

> I do not see the problems in distributing SVC, or other layered content, over Swift.
> 
> The architecture is flexible enough to support multiple ways of distributing different content.
> The simplest solution for distributing SVC, in my opinion, would be to have a single swarm 

I see your point but as layers have different sizes the number of "DATA chunks" of 1 KiB addressed would also be different among layers, meaning that, for example, chunks 232 to 240 of layer_0 (large size) would eventually correspond (in terms of media presentation time or synched video frames) to data in chunk 23 of layer_3 (a layer 1/10th of the size of layer0). How would HINTS for chunks figure out the correct ones to get in order to have the media layers combined in synch? 
Synching by byte ranges in this case seems quite hard to achieve, unless there is a "special rule" or media decoding time information for each layer (another large media map file ?) .

> Considering this scenario, the cost of a higher layer, for a peer that is not interested in retrieving it, would just be at most the size of a single 20-byte uncle hash. The more layers

The problem with SVC layers is different (hierarchy) from the problem of media representations of a content (i.e., separate audio and video streams, etc.) as each would have its size,  with or without dependencies (several selectable audio languages, for example).
Addressing by byte ranges does not seem to be the most adequate solution, as these media representations for the same presentation duration have different sizes.
But if content is addressed by media segments (independent of their relative size) they are synched and addressed by their ID.

Regards,

Rui Cruz
[email-masked]

---

From: Riccardo Petrocco <[email-masked]>
Date: Tue, 6 Dec 2011 01:49:02 +0100

Dear Rui,

I understand your view, but I do not share your concerns.
There are easy ways to work around it. We could easily set a fixed size per
layer chunk
based on the biggest chunk. We could set the rest of the bits to '0' and
not transmit them,
since the receiving peer will be able to authenticate them based on the
hashes.

I'm sure there are more elegant solutions than what I could come up in few
minutes. For
sure the codec experts will be able to suggest a better approach :-).
I'm also a bit resilient to your approach of saving one file per chunk,
resulting in a huge
number of small files on disk, even through Swift is still able to handle
it by addressing
multiple swarms.

I would like to see the discussion on the PPSP mailing list moving over the
details of a
specific codec approach.
I do not see Swift limiting any type implementation, but please correct me
if you think I'm
wrong.

Best regards,
Riccardo Petrocco

2011/12/6 Rui Cruz <[email-masked]>

> I see your point but as layers have different sizes the number of "DATA
> chunks" of 1 KiB addressed would also be different among layers, meaning
> that, for example, chunks 232 to 240 of layer_0 (large size) would
> eventually correspond (in terms of media presentation time or synched video
> frames) to data in chunk 23 of layer_3 (a layer 1/10th of the size of
> layer0). How would HINTS for chunks figure out the correct ones to get in
> order to have the media layers combined in synch?
> Synching by byte ranges in this case seems quite hard to achieve, unless
> there is a "special rule" or media decoding time information for each layer
> (another large media map file ?) .
>
> The problem with SVC layers is different (hierarchy) from the problem of
> media representations of a content (i.e., separate audio and video streams,
> etc.) as each would have its size,  with or without dependencies (several
> selectable audio languages, for example).
> Addressing by byte ranges does not seem to be the most adequate solution,
> as these media representations for the same presentation duration have
> different sizes.
> But if content is addressed by media segments (independent of their
> relative size) they are synched and addressed by their ID.
>
>
> Just my 2 cents.
>
> Best Regards,
> Riccardo Petrocco
>
>
>> OK, but the integrity verification of each chunk needs all the
>> "necessary" uncle hashes. For such a deep hash tree, is it not a bit...too
>> expensive in the size for the datagram and computation resources?

---

From: Arno Bakker <[email-masked]>
Date: Tue, 6 Dec 2011 09:41:38 +0100

On 05/12/2011 12:24, Rui Cruz wrote:
>
> You are not considering the risks associated with unavailable substream
> (swarm), nor the sync problems, and you should.
>

Why would a substream swarm become unavailable? The publisher of the 
content will have to ensure base capacity for the content he publishes. 
Whether it consists of one or multiple swarms. As replied to Csaba,
I don't think handling several swarms is a problem. Whether your SVC
chunk selection algorithm says "download chunk X" or "download chunk X
from swarm S" doesn't really matter.

> The impact is similar to the one described in
> draft-grishchenko-ppsp-swift, but with a different logic in order to
> support Structured Media and interaction.
>

Err... are you also using Merkle hash trees for content integrity 
protection? And I don't see how interaction impacts integrity verification.

Regards,
     Arno

---

From: Arno Bakker <[email-masked]>
Date: Tue, 6 Dec 2011 09:58:23 +0100

On 05/12/2011 13:25, Rui Cruz wrote:
> organized as a directory of files (those 1800 segments of 50 KiB each,
> for example)?
>

We covered this case already. A single piece of content consisting of 
1800 chunks would normally be mapped to a single swift swarm. As I said 
in my mail of Nov 30, the swift protocol specification does not say 
anything about how chunks are mapped to disk, so if you for some reason 
want to store it as a directory of files, your implementation is free to 
do so (cf. BitTorrent multi-file torrents).

> "necessary" uncle hashes. For such a deep hash tree, is it not a
> bit...too expensive in the size for the datagram and computation resources?

As explained in Sec. 3.5.3 each hash in the tree needs to be sent only 
once, when there is no packet loss. So the on-the-wire overhead for 
hashes is ideally the size of the hash tree:

Each hash also needs to be checked only once.

Regards,
     Arno

---

From: Rui Cruz <[email-masked]>
Date: Tue, 6 Dec 2011 10:32:18 +0000

Dear Riccardo,

On 06/12/2011, at 00:49, Riccardo Petrocco wrote:

> I'm sure there are more elegant solutions than what I could come up in few minutes. For 
> I'm also a bit resilient to your approach of saving one file per chunk, resulting in a huge 
> number of small files on disk, even through Swift is still able to handle it by addressing
> multiple swarms.

We have been working in this area for some time, and when we started, Nx10 GiB hard disks, 32 bit addressing and SD media were commodity.
Now, Nx TiB hard disks, 64 bit addressing and HD/3D media are commodity.
On the codec experts, I would say MPEG working group of ISO/IEC is a reference, and just came up with the new standard ISO/IEC 23009, from joint efforts of MPEG, 3GPP, Open IPTV Forum, W3C and industries. 
The standard addresses the formats to enable efficient and high-quality delivery of streaming services over the Internet, considering any multimedia content (2D, 3D, animation, graphics, multiview, subtitles, text, etc.), not just AV, supporting On-Demand, Live and Time-shift (nPVR) streaming.
And the standard considers media representations in segments (small pieces of video streams/files), short (≈1-10 sec) and long (≈10sec – 2h),  with hierarchical structuring for efficient access.
So, the concerns have shifted from number of files on disk, to efficient, adaptive and dynamic (including interactive) technique for streaming, independent of the codecs.

In our drafts we have referenced precisely this approach but for P2P. 

> I do not see Swift limiting any type implementation, but please correct me if you think I'm
> wrong.

Well, considering just the Generic Multiparty Transport Protocol that you know well, we would point to the architectural issue of signaling information conveyed in the media plane (media DATA transport) and I cannot see how it could be separated, as PPSP charter is not addressing media transport but signaling. But this may just be an aesthetic problem...

Prof. Rui Santos Cruz
Chairman
IEEE Portugal Section

---

From: Rui Cruz <[email-masked]>
Date: Tue, 6 Dec 2011 11:02:02 +0000

On 06/12/2011, at 08:58, Arno Bakker wrote:

> As explained in Sec. 3.5.3 each hash in the tree needs to be sent only once, when there is no packet loss. So the on-the-wire overhead for hashes is ideally the size of the hash tree:
> 

It appears that you are referring something different from what is written, therefore my confusion. Can you elaborate what you mean in 3.5.3 by the following: 

"any chunk is verified using its uncle hashes the necessary hashes MUST be put into the same datagram as the chunk’s data.
The hashes necessary to verify a chunk are in principle its sibling’s hash and all its uncle hashes"

In the worst case, when only a few previous hashes are known, how many sibling and uncle hashes would be necessary to be transported in datagrams (on-the-wire overhead) to verify a single chunk in such a huge tree?

Prof. Rui Santos Cruz
Chairman
IEEE Portugal Section

---

From: Arno Bakker <[email-masked]>
Date: Tue, 6 Dec 2011 12:43:28 +0100

On 06/12/2011 12:02, Rui Cruz wrote:
>
> In the worst case, when only a few previous hashes are known, how many
> sibling and uncle hashes would be necessary to be transported in
> datagrams (on-the-wire overhead) to verify a single chunk in such a huge
> tree?
>

The height of the tree for 1 GiB of content is 20. So in the worst case
you have to send 20-1 (receiver already knows the root hash) = 19 
hashes. After that first packet, the number of hashes will be lower.

To see how the number of hashes decreases it is simpler to look at the
tree of height 4 in the swift spec in a simple progressive download.

Chunk		Hashes sent
0		2,5,11
1		- (receiver already knows all)
4		6
6		-
8		10,13,3
10		-
12		14
14		-

==========================
Total # hashes	8

So the number of hashes sent in total is even less than the total number 
of hashes in the tree here, as you don't need to send hashes that are 
calculated and verified as part of earlier chunks.

Regards,
      Arno