Subject: [ppsp] 转发: New Version Notification for draft-deng-ppsp-bfbitmap-04.txt

From: 邓灵莉/Lingli Deng <[email-masked]>
Date: Tue, 5 Nov 2013 08:34:47 +0800

Hi forks,

We are happy to announce the latest version of BFbitmap draft.
In this version, we discussed open issues for accommodating several chunk addressing schemes in general as well as how to integrate the BF scheme with PPSP protocols.
Your comments and suggestions would be highly appreciated.

BR
Lingli

-----邮件原件-----
发件人: [email-masked] [mailto:[email-masked]] 
发送时间: 2013年11月5日 8:29
收件人: Deng Lingli; Yunfei Zhang; Yihong Huang; Jin Peng; Lingli Deng; Rachel Huang
主题: New Version Notification for draft-deng-ppsp-bfbitmap-04.txt

A new version of I-D, draft-deng-ppsp-bfbitmap-04.txt
has been successfully submitted by Lingli Deng and posted to the
IETF repository.

Filename:	 draft-deng-ppsp-bfbitmap
Revision:	 04
Title:		 Efficient Chunk Availability Compression for PPSP
Creation date:	 2013-11-05
Group:		 Individual Submission
Number of pages: 13
URL:             http://www.ietf.org/internet-drafts/draft-deng-ppsp-bfbitmap-04.txt
Status:          http://datatracker.ietf.org/doc/draft-deng-ppsp-bfbitmap
Htmlized:        http://tools.ietf.org/html/draft-deng-ppsp-bfbitmap-04
Diff:            http://www.ietf.org/rfcdiff?url2=draft-deng-ppsp-bfbitmap-04

Abstract:
   Bloom filters are proposed to be used in compressing chunk
   availability information, periodically exchanged between peers and
   the tracker through PPSP-TP and PPSPP protocols, to reduce relevant
   cost and enhance scalability.

Please note that it may take a couple of minutes from the time of submission
until the htmlized version and diff are available at tools.ietf.org.

The IETF Secretariat

---

From: 邓灵莉/Lingli Deng <[email-masked]>
Date: Tue, 26 Nov 2013 14:35:46 +0800

Hi all,

As requested in the Vancouver meeting, we are planning to elaborate the previous performance analysis for bitmap compression schemes in the following way.
Plz let me know if you have any comments or suggestion with this analysis setting.

1, we consider the following existing proposals for chunk availability information in this analysis
	a) Original bitmap Scheme uses a bit-array to represent the chunk set, and mark those bits corresponding to the locally available chunks.
	b) Chunk range scheme uses a array of starting+ending chunk index pairs to represent continuous intervals. 
	c) Byte range scheme uses an array of starting+ending byte index pairs to represent continuous intervals. 
	d) Bin number scheme uses a universally assigned bin number (integer) for any given continuous interval.  
2, for simplicity, we assume that No hybrid is deployed. In other words, a single scheme is used for both storage and transmission.
3, Tracker/Peer operations on chunk availability information, which are to be considered include: 
	a) Formation, to translate a specific set of available chunks of a given swarm into a compact form of representation.
		In this case, Representation storage overhead wrt. the number of all chunks n and available chunks k, is considered.
	b) Transmission, to transmit a specific representation of currently available chunks of a given swarm to another neighboring peer.
		In this case, Representation transmission overhead wrt. n and k, is considered.
	c) Update, to update a specific representation of currently available chunks of a given swarm as result of a given (group) of newly downloaded and verified chunk(s).
		A special type of update operation, Partial update, where the sender only transfer the relevant part of available chunks and requires a merge operation at the receiver’s side, is considered separately.
		For updates, Update computation overhead wrt. n, k and the number of new chunks p, is considered.
		In addition, Delta transmission overhead wrt. n, k and the number of new chunks d, is also considered.
	d) Inquiry, to check whether a specific representation of available chunks of a given swarm contains a given (group) of requesting chunk(s).
		In this case, Inquiry computation overhead wrt. n, k and the number of requesting chunks g, is considered.

BR
Lingli

-----邮件原件-----
发件人: [email-masked] [mailto:[email-masked]] 代表 邓灵莉/Lingli Deng
发送时间: 2013年11月5日 8:35
收件人: 'ppsp'
主题: [ppsp] 转发: New Version Notification for draft-deng-ppsp-bfbitmap-04.txt

Hi forks,

BR
Lingli

-----邮件原件-----
发件人: [email-masked] [mailto:[email-masked]] 
发送时间: 2013年11月5日 8:29
收件人: Deng Lingli; Yunfei Zhang; Yihong Huang; Jin Peng; Lingli Deng; Rachel Huang
主题: New Version Notification for draft-deng-ppsp-bfbitmap-04.txt

Abstract:

The IETF Secretariat

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

---

From: Johan Pouwelse <[email-masked]>
Date: Tue, 26 Nov 2013 10:16:43 +0100

Dear Lingli Deng,
Please find a review of your I-D below. Apologies for the critical
nature of my remarks.

After reading of this proposal it was still unclear what problem is
being addressed and why it's needed.

Using Bloom filters adds a lot of complexity, while at this stage PPSP
needs I believe: simplicity, running code and additional real-world
trials.
PPSP has a unique and efficient datastructure of representing
availability of video chunks using "binmaps". Using one number to
compress both pieces and intervals is not easy to improve.  For the
given example of 2GByte, a binmap indicating the availability of the
whole file or an ongoing live stream is less than a KByte. Even in an
UltraHD scenario with bitrates of 42Mbps it should scale. Obviously
normal bitmaps get in trouble then, but not binmaps.

The I-D states "frequent exchange of large volume of bitmap
information, is among the key factors that set a limit to the system's
efficiency and scalability [P2P-limit]".
This cited INFOCOM paper does not support the claims made. It merely
states that the period T of periodic buffer map exchanges should not
be too short, then it will impact performance.

Prof. Johan Pouwelse
Delft University of Technology

---

From: Arno Bakker <[email-masked]>
Date: Wed, 27 Nov 2013 08:34:37 +0100

Hi all

IMHO, a comparison cannot be done until the all the methods to be
evaluated are clear. It is not clear how the fact that Bloomfilters
are lossy is handled to ensure that peers do not stall on false
negatives, as raised in my previous mail. The lossy property of
Bloomfilters also implies they cannot be used for storage, otherwise
you may continuously download a chunk because the Bloomfilter cannot
properly record that you already have it.

Regards,
   Arno

---

From: 邓灵莉/Lingli Deng <[email-masked]>
Date: Wed, 27 Nov 2013 15:53:36 +0800

Hi Arno,

Thank you for pointing out the lossy nature of BF scheme. Yes, this needs to be considered.

Just for clarification, the problem that "you may continuously download a chunk because the Bloomfilter cannot properly record that you already have it" is not going to happen in reality.
An already downloaded chunk would never be missed by a BF-based inquiry.

BR
Lingli

-----邮件原件-----
发件人: ppsp [mailto:[email-masked]] 代表 Arno Bakker
发送时间: 2013年11月27日 15:35
收件人: [email-masked]
主题: Re: [ppsp] on performance analysis for chunk addressing schemes/bitmap compression methods

Hi all

Regards,
   Arno

---

From: Dave Cottlehuber <[email-masked]>
Date: Wed, 27 Nov 2013 15:47:10 +0100

On 26. November 2013 at 07:36:02, 邓灵莉/Lingli Deng ([email-masked]) wrote:
>  
> Hi all,
>  
> As requested in the Vancouver meeting, we are planning to elaborate  
> the previous performance analysis for bitmap compression schemes  
> in the following way.
> a) Original bitmap Scheme uses a bit-array to represent the chunk  
> set, and mark those bits corresponding to the locally available  
> chunks.

> 2, for simplicity, we assume that No hybrid is deployed. In other  
> words, a single scheme is used for both storage and transmission. 

> a) Formation, to translate a specific set of available chunks  
> of a given swarm into a compact form of representation.
> In this case, Representation storage overhead wrt. the number  
> of all chunks n and available chunks k, is considered.
> b) Transmission, to transmit a specific representation of currently  
> available chunks of a given swarm to another neighboring peer.  
> c) Update, to update a specific representation of currently  
> available chunks of a given swarm as result of a given (group)  
> of newly downloaded and verified chunk(s).
> A special type of update operation, Partial update, where the  
> sender only transfer the relevant part of available chunks and  
> requires a merge operation at the receiver’s side, is considered  
> separately.
> d) Inquiry, to check whether a specific representation of available  
> chunks of a given swarm contains a given (group) of requesting  
> chunk(s).

Thanks Lingli,

This should be comprehensive.

We should consider these perspectives:

Swarm characteristics:
- total number of peers (view of tracker)
- average connected peer set (view of normal peer)
- size of file, and # of chunks

Peer type:
- a super-peer that has the full dataset available, and is actively seeding as many peers as possible
- user-level peer that is both retrieving and transmitting data, to a small peer set
- tracker

Transfer mode:
- streaming, where keeping very old chunks makes no sense
- copying, where chunks are being written to e.g. disk, all data must be obtained

Finally, I am very interested to see your constraints (n,k,p above, swarm characteristics), as I hope this will provide the motivation that lead you propose this enhancement. Did this arise in development, testing, simulation etc?

A+
Dave