Subject: [ppsp] chunk scheduling algorithm

From: Picconi Fabio <[email-masked]>
Date: Tue, 15 Nov 2011 04:29:50 +0100

Hi,

Here are the references on alternatives to rarest first for live streaming. The first study has theoretical/simulation results, while the second shows results based on a real prototype.

Thomas Bonald , Laurent Massoulié , Fabien Mathieu , Diego Perino , Andrew Twigg. Epidemic Live Streaming: Optimal Performance Trade-Offs. In Proc. of SIGMETRICS, 2008.
http://www.thlab.net/~lmassoul/sigmetrics_08.pdf

F. Picconi and L. Massoulié. Is there a future for mesh-based live video streaming? In Proc. of P2P, 2008.
http://www.thlab.net/~picconi/p2p08.pdf

The "latest useful" policy shows its benefits when the users' download windows overlap (which is usually the case for live streaming). For time-shifted media (e.g., VoD/catch-up), it's a good idea to distinguish between the download window next to the playback deadline, and the rest. For the download window, the simplest choice is "earliest useful"  (i.e., prefer the chunks closest to the deadline), although combining "earliest  useful" with "latest useful" will probably give better results if you have users with overlapping windows. For the remaining chunks (i.e., far from the playback deadline), you probably want to use "rarest first".

Fabio

---

From: Csaba Kiraly <[email-masked]>
Date: Tue, 15 Nov 2011 05:19:19 +0100

Hi Fabio, hi all,

Another alternative (for live streaming) is Deadline based chunk scheduling. You can find the description of the algorithm, theoretical background and some simulations here:

Abeni, L., C. Kiraly, and R. Lo Cigno, "On the Optimal Scheduling of Streaming Applications in Unstructured Meshes", NETWORKING 2009, vol. 5550: Springer Berlin / Heidelberg, pp. 117-130, 2009.
http://peerstreamer.org/content/optimal-scheduling-streaming-applications-unstructured-meshes
http://napa-wine.eu/twiki/pub/Public/DocumentsOld/abeni_optimal_scheduling-final.pdf

The paper presents a combination of a chunk selection and a peer selection algorithm (DLc and RLp, respectively), but the chunk selection algorithm can be used in itself as well. It shows nice behavior and good delivery properties where latest useful policies fail (chunk diffusion delay distribution tends to have a heavy tail with latest useful for many reasons, DLc tries to correct these shortcomings).

An extension of the above to structured streams (SVC, MDC and alike) is described in the following paper:

Kiraly, C., R. Lo Cigno, and L. Abeni, "Deadline-Based Differentiation in P2P Streaming", GLOBECOM 2010 - 2010 IEEE Global Communications Conference, Miami, FL, USA, IEEE, pp. 1 - 6, 2010.
http://peerstreamer.org/content/deadline-based-differentiation-p2p-streaming
http://disi.unitn.it/~kiraly/preprints/kiraly-globecom2010-extended.pdf

Csaba

On 11/15/2011 04:29 AM, Picconi Fabio wrote:
> http://www.thlab.net/~lmassoul/sigmetrics_08.pdf <http://www.thlab.net/%7Elmassoul/sigmetrics_08.pdf>
>
> http://www.thlab.net/~picconi/p2p08.pdf <http://www.thlab.net/%7Epicconi/p2p08.pdf>
>
> _______________________________________________
> ppsp mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/ppsp

---

From: Gyorgy Dan <[email-masked]>
Date: Tue, 15 Nov 2011 09:54:56 +0100

Hi Csaba, Fabio, all,

There are many alternatives for scheduling, but IMHO no extensive
comparison of recent algorithms.
It is also good to keep in mind that the performance of the algorithms
depends significantly on the assumptions made for the evaluation. This
study, for example, shows how the performance of random push policies
deteriorates if the evaluation accounts for the delay needed to exchange
signaling messages between the peers:

I. Chatzidrossos, G. Dán and V. Fodor, ``Delay and playout probability
trade-off in mesh-based peer-to-peer streaming with delayed buffer map
updates,'' in Peer-to-peer Networking and Applications, vol. 3., num.
1., Mar. 2010

György

On 11/15/2011 05:19 AM, Csaba Kiraly wrote:
> Hi Fabio, hi all,
> 
> Another alternative (for live streaming) is Deadline based chunk
> scheduling. You can find the description of the algorithm, theoretical
> background and some simulations here:
> 
> Abeni, L., C. Kiraly, and R. Lo Cigno, "On the Optimal Scheduling of
> Streaming Applications in Unstructured Meshes", NETWORKING 2009, vol.
> 5550: Springer Berlin / Heidelberg, pp. 117-130, 2009.
> The paper presents a combination of a chunk selection and a peer
> selection algorithm (DLc and RLp, respectively), but the chunk selection
> algorithm can be used in itself as well. It shows nice behavior and good
> delivery properties where latest useful policies fail (chunk diffusion
> delay distribution tends to have a heavy tail with latest useful for
> many reasons, DLc tries to correct these shortcomings).
> 
> Kiraly, C., R. Lo Cigno, and L. Abeni, "Deadline-Based Differentiation
> in P2P Streaming", GLOBECOM 2010 - 2010 IEEE Global Communications
> Conference, Miami, FL, USA, IEEE, pp. 1 - 6, 2010.
>> Here are the references on alternatives to rarest first for live
>> streaming. The first study has theoretical/simulation results, while
>> the second shows results based on a real prototype.
>>
>>  
>>
>> Thomas Bonald , Laurent Massoulié , Fabien Mathieu , Diego Perino ,
>> Andrew Twigg. Epidemic Live Streaming: Optimal Performance Trade-Offs.
>> In Proc. of SIGMETRICS, 2008.
>>
>> <http://www.thlab.net/%7Elmassoul/sigmetrics_08.pdf>
>>
>>  
>>
>> <http://www.thlab.net/%7Epicconi/p2p08.pdf>
>>
>>  
>>
>> The “latest useful” policy shows its benefits when the users’ download
>> windows overlap (which is usually the case for live streaming). For
>> time-shifted media (e.g., VoD/catch-up), it’s a good idea to
>> distinguish between the download window next to the playback deadline,
>> and the rest. For the download window, the simplest choice is
>> “earliest useful”  (i.e., prefer the chunks closest to the deadline),
>> although combining “earliest  useful” with “latest useful” will
>> probably give better results if you have users with overlapping
>> windows. For the remaining chunks (i.e., far from the playback
>> deadline), you probably want to use “rarest first”.
>>
>>  
>>
>> Fabio
>>
>>
>>
>> [email-masked] <mailto:[email-masked]>
> This body part will be downloaded on demand.

-- 
György Dán
School of Electrical Engineering
KTH Royal Institute of Technology
Stockholm, Sweden
http://www.ee.kth.se/~gyuri

---

From: Csaba Kiraly <[email-masked]>
Date: Tue, 15 Nov 2011 13:48:00 +0100

Hi Gyorgy,

nice paper! This is one of the reasons why we are working on some protocol changes to make it more delay tolerant, but this is still in the works.
I fully agree that detailed comparison and evaluation is largely missing. There are some spot results but far from being exhaustive. Anyone interested in a joint study of scheduling algorithms? I can throw in a simulator, an emulator and an implementation with configurable schedulers.

BTW, I hope the ppsp list does not mind that we jumped on the list with this discussion. I don't know how the topic came up (it was 3 a.m here while you had the discussion, so I wasn't able to follow it), but it seems there was some interest.

>From our experience, scheduling issues does have some mild influence on the protocol. Namely:
- simple buffer maps sent as bitmaps might not be enough, you might want to send some metadata associated with the chunk IDs as well.
- different scheduling algorithms match well or not with different protocols (push, pull, offer, negotiation, etc.). IMHO the ppsp peer protocol should support these all through a careful selection of messaging primitives instead of choosing one, especially because studies are still not satisfying to decide which one is the best, not even to decide which one is better in what scenario.

Csaba

---

From: Picconi Fabio <[email-masked]>
Date: Wed, 16 Nov 2011 02:59:50 +0100

Interesting discussion. I agree that a lot of scheduling algorithms have been proposed, and that a detailed comparison is missing. Maybe a good subject for the P2PRG? :-)

Regarding PPSP, given the absence of a clear winner among scheduling algorithms, I agree that PPSP should be as generic as possible to support the widest range of options. And that probably means supporting multiple forms of signaling (e.g., different representations of buffer maps), multiple request paradigms (push/pull/push-pull), multiple transports, etc. 

Fabio

-----Original Message-----
From: Csaba Kiraly [mailto:[email-masked]] 
Sent: mardi 15 novembre 2011 20:48
To: Gyorgy Dan
Cc: Picconi Fabio; [email-masked]
Subject: Re: [ppsp] chunk scheduling algorithm

Hi Gyorgy,

Csaba

On 11/15/2011 09:54 AM, Gyorgy Dan wrote:
>>> The "latest useful" policy shows its benefits when the users' download
>>> time-shifted media (e.g., VoD/catch-up), it's a good idea to
>>> "earliest useful"  (i.e., prefer the chunks closest to the deadline),
>>> although combining "earliest  useful" with "latest useful" will
>>> deadline), you probably want to use "rarest first".
>>>
>>>  
>>>
>>> Fabio
>>>
>>>
>>>

---

From: zhangyunfei <[email-masked]>
Date: Wed, 16 Nov 2011 13:44:59 +0800

Hi Fabio,Csaba and all（speak individually),
    Becasue PPSP doesn't cover the scheduling selection , I think PPSP peer protocol should be open to multiple request paradigms like push/pull/hybrid mode.  For the bitmap expression, I am not sure if a generic expression can work(supporting both structured and unstructured data). But if it works, it's better than having different bitmap expressions.
The selection of using what kind of PPSP request mode and scheduling algorithms, transport can be addressed in the "usage guide" document, which is explicit in the charter.

BR
Yunfei

zhangyunfei

From: Picconi Fabio
Date: 2011-11-16 09:59
To: [email-masked]

Fabio

-----Original Message-----
From: Csaba Kiraly [mailto:[email-masked]] 
Sent: mardi 15 novembre 2011 20:48
To: Gyorgy Dan
Cc: Picconi Fabio; [email-masked]
Subject: Re: [ppsp] chunk scheduling algorithm

Hi Gyorgy,

Csaba

---

From: Arno Bakker <[email-masked]>
Date: Tue, 22 Nov 2011 09:06:23 +0100

On 16/11/2011 06:44, zhangyunfei wrote:
> Becasue PPSP doesn't cover the scheduling selection , I think PPSP peer
> protocol should be open to multiple request paradigms like
> push/pull/hybrid mode. For the bitmap expression, I am not sure if a
> generic expression can work(supporting both structured and unstructured
> data). But if it works, it's better than having different bitmap
> expressions.
> The selection of using what kind of PPSP request mode and scheduling
> algorithms, transport can be addressed in the "usage guide" document,
> which is explicit in the charter.

Hi all

good input. The plan after Taipei is to make swift open to different 
chunk addressing methods and integrity protection mechanisms. With the 
former in mind, could you have a look at the swift proposal and see if 
there are things missing that you need to use the chunk+peer selection 
policies that you are currently using.

I.e., determine the requirements that your selection policies put on the 
protocol, and if they are currently met?

Thanks,
     Arno

---

From: Riccardo Petrocco <[email-masked]>
Date: Tue, 22 Nov 2011 11:29:26 +0100

Hi all,

I'm currently working on implementing the missing pieces in the swift
proposal.
The reference implementation will be modular enough to be able to plug
different algorithms in a transparent way.
Along with implementing important features, such as an availability tree
for the swarm and statistics about peer's
link capacity, I'm also designing a new VoD scheduling algorithm.

As Arno mentioned in the previous mail, please let us know if some
algorithms, you would like to integrate, have
special requirements.

Best regards,
Riccardo Petrocco

2011/11/22 Arno Bakker <[email-masked]>

> good input. The plan after Taipei is to make swift open to different chunk
> addressing methods and integrity protection mechanisms. With the former in
> mind, could you have a look at the swift proposal and see if there are
> things missing that you need to use the chunk+peer selection policies that
> you are currently using.
>
> ______________________________**_________________
> ppsp mailing list
> [email-masked]
> https://www.ietf.org/mailman/**listinfo/ppsp<https://www.ietf.org/mailman/listinfo/ppsp>
>

---

From: Csaba Kiraly <[email-masked]>
Date: Tue, 22 Nov 2011 11:41:56 +0100

Hi Arno, Riccardo,

I will check the current version and let you know about changes that might be needed. Can you also send me the ppt of your slides from the meeting? It might be help exchanging some ideas.

Best regards,
Csaba

On 11/22/2011 11:29 AM, Riccardo Petrocco wrote:
> Hi all,
>
> I'm currently working on implementing the missing pieces in the swift proposal.
> The reference implementation will be modular enough to be able to plug different algorithms in a transparent way.
> Along with implementing important features, such as an availability tree for the swarm and statistics about peer's
> As Arno mentioned in the previous mail, please let us know if some algorithms, you would like to integrate, have
> special requirements.
>
> Best regards,
> Riccardo Petrocco
>
> 2011/11/22 Arno Bakker <[email-masked] <mailto:[email-masked]>>
>
>     good input. The plan after Taipei is to make swift open to different chunk addressing methods and integrity protection mechanisms. With the former in mind, could you have a look at the swift proposal and see if there are things missing that you need to use the chunk+peer selection policies that you are currently using.
>
>     I.e., determine the requirements that your selection policies put on the protocol, and if they are currently met?
>
>     Thanks,
>        Arno
>

---

From: György Dán <[email-masked]>
Date: Tue, 22 Nov 2011 12:12:35 +0100

Hi all,

Coming back to the issue of buffer map encoding, I would argue for 
creating a mandatory structure/encoding, but allow for alternatives to 
be defined later. A mandatory (or recommended) structure/encoding that 
satisfies the requirements of most of the existing (proposed) chunk 
scheduling algorithms is excellent for demonstrating PPSP.   For 
example, based on state-of-the-art video coding, decoding and loss 
concealment technology, I could imagine information about the 
distortion, the interdependency between chunks (to reflect coding 
dependencies), the temporal vs. spatial scalability/layering to be 
conveyed by the buffer-map. With future development of video coding and 
decoding algorithms, the scheduling algorithms might want to make use of 
additional information, and new structures/encodings will have to be 
defined.

Best regards,
  György

On 2011.11.22. 11:41, Csaba Kiraly wrote:
> Hi Arno, Riccardo,
>
> I will check the current version and let you know about changes that 
> might be needed. Can you also send me the ppt of your slides from the 
> meeting? It might be help exchanging some ideas.
>
> Best regards,
> Csaba
>
>> The reference implementation will be modular enough to be able to 
>> plug different algorithms in a transparent way.
>> Along with implementing important features, such as an availability 
>> tree for the swarm and statistics about peer's
>>         Hi Fabio,Csaba and all(speak individually),
>>     good input. The plan after Taipei is to make swift open to
>>     different chunk addressing methods and integrity protection
>>     mechanisms. With the former in mind, could you have a look at the
>>     swift proposal and see if there are things missing that you need
>>     to use the chunk+peer selection policies that you are currently
>>     using.
>>
>>     I.e., determine the requirements that your selection policies put
>>     on the protocol, and if they are currently met?
>>
>>     Thanks,
>>        Arno
>>

---

From: Riccardo Petrocco <[email-masked]>
Date: Tue, 22 Nov 2011 13:23:05 +0100

Hi György and all,

In my personal opinion, at this stage, the proposal should be independent
from the coding details of the video stream.
It should be modular enough to provide an easy way of integrating different
codec specific "extensions".
The Swift proposal should not really care about what kind of stream will be
retrieved, but just focus on retrieving "bits".

Specific "extensions" can be added, that parse the data (or the metadata)
to get infos needed by download algorithms
(also specific to the type of stream).
That said, I'm In favor of including a "reference coding solution" using
state-of-the-art solutions as a proof of concept,
and the details could be added to the appendix of the proposal.

Just my 2 euro cents,
Regards,
Riccardo

2011/11/22 György Dán <[email-masked]>

> creating a mandatory structure/encoding, but allow for alternatives to be
> defined later. A mandatory (or recommended) structure/encoding that
> scheduling algorithms is excellent for demonstrating PPSP.   For example,
> based on state-of-the-art video coding, decoding and loss concealment
> technology, I could imagine information about the distortion, the
> interdependency between chunks (to reflect coding dependencies), the
> temporal vs. spatial scalability/layering to be conveyed by the buffer-map.
> With future development of video coding and decoding algorithms, the
> scheduling algorithms might want to make use of additional information, and
> new structures/encodings will have to be defined.
>
> Best regards,
>  György
>
>
> I will check the current version and let you know about changes that might
> be needed. Can you also send me the ppt of your slides from the meeting? It
> might be help exchanging some ideas.
>
> Best regards,
> Csaba
>
> ppsp mailing [email-masked]://www.ietf.org/mailman/listinfo/ppsp
>
>
>
>
> ppsp mailing [email-masked]://www.ietf.org/mailman/listinfo/ppsp
>
>

---

From: Martin Stiemerling <[email-masked]>
Date: Tue, 29 Nov 2011 15:57:15 +0000

Hi all chunk scheduling enthusiasts, 

It might be indeed a good idea to go with this to the IRSG. I'm not trying to turn you away guys, but this is of potential interest for the p2prg. 

My take from this is that the PPSP peer protocol should support multiple chunk scheduling algorithms.

The peer protocol would need a capability exchange where each peer can state what algorithm it supports. 

  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 

> From: [email-masked] [mailto:[email-masked]] On Behalf Of
> Picconi Fabio
> Sent: Wednesday, November 16, 2011 3:00 AM
> To: [email-masked]
> Interesting discussion. I agree that a lot of scheduling algorithms have been
> proposed, and that a detailed comparison is missing. Maybe a good subject for
> the P2PRG? :-)
> 
> Regarding PPSP, given the absence of a clear winner among scheduling
> algorithms, I agree that PPSP should be as generic as possible to support the
> widest range of options. And that probably means supporting multiple forms of
> signaling (e.g., different representations of buffer maps), multiple request
> paradigms (push/pull/push-pull), multiple transports, etc.
> 
> Fabio
> 
> 
> nice paper! This is one of the reasons why we are working on some protocol
> changes to make it more delay tolerant, but this is still in the works.
> I fully agree that detailed comparison and evaluation is largely missing. There
> are some spot results but far from being exhaustive. Anyone interested in a
> joint study of scheduling algorithms? I can throw in a simulator, an emulator
> and an implementation with configurable schedulers.
> 
> BTW, I hope the ppsp list does not mind that we jumped on the list with this
> discussion. I don't know how the topic came up (it was 3 a.m here while you
> had the discussion, so I wasn't able to follow it), but it seems there was some
> interest.
> 
> - simple buffer maps sent as bitmaps might not be enough, you might want to
> send some metadata associated with the chunk IDs as well.
> - different scheduling algorithms match well or not with different protocols
> (push, pull, offer, negotiation, etc.). IMHO the ppsp peer protocol should
> support these all through a careful selection of messaging primitives instead of
> choosing one, especially because studies are still not satisfying to decide which
> one is the best, not even to decide which one is better in what scenario.
> 
> Csaba
> 
> >> http://napa-
> wine.eu/twiki/pub/Public/DocumentsOld/abeni_optimal_scheduling-final.pdf
> >>