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

From: 邓灵莉/Lingli Deng <[email-masked]>
Date: Wed, 3 Jul 2013 13:46:30 +0800

Hi all,

We have just submitted a new draft proposing to use bloom filters to compress the chunk bitmap information exchanged between peers and the tracker. 
http://datatracker.ietf.org/doc/draft-deng-ppsp-bfbitmap/ 

Besides the basic algorithms and high level message flow, it also provides an initial discussion on how to integrate with the current tracker and peer protocol.

Your comments would be highly appreciated.

BR
Lingli

-----邮件原件-----
发件人: [email-masked] [mailto:[email-masked]] 
发送时间: 2013年7月3日 11:55
收件人: Deng Lingli; Yunfei Zhang; Jin Peng; Lingli Deng
主题: New Version Notification for draft-deng-ppsp-bfbitmap-00.txt

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

Filename:	 draft-deng-ppsp-bfbitmap
Revision:	 00
Title:		 Efficient Chunk Availability Compression for PPSP
Creation date:	 2013-07-03
Group:		 Individual Submission
Number of pages: 10
URL:             http://www.ietf.org/internet-drafts/draft-deng-ppsp-bfbitmap-00.txt
Status:          http://datatracker.ietf.org/doc/draft-deng-ppsp-bfbitmap
Htmlized:        http://tools.ietf.org/html/draft-deng-ppsp-bfbitmap-00

Abstract:
   This document proposes to employ bloom filter algorithms in
   compressing chunk availability information in exchange between peers
   and the tracker through the PPSP-TP protocol and PPSPP protocol.

The IETF Secretariat

---

From: "Huangyihong (Rachel)" <[email-masked]>
Date: Mon, 15 Jul 2013 07:24:40 +0000

Hi Lingli,

It's a very interesting topic. It's very useful for messages with ContentMap exchanges. Thanks for bring this.  I have following comments when I review it:

1. In section 3.1, the description following the figure 2 doesn't quite correspond to the figure. For example, the item 3 and 4 couldn't be found in the figure. And I think it's better to show the difference between leech mode and seeder mode in the figure. 

2. I think section 4 should be placed in the section 3. Otherwise, people will have the question why BF conf could be obtained from both the portal and the tracker. 

3. In section 3.2, clause a, I don't think the base TP protocol has JOIN request message.

4. In section 3.2, clause b "Integration to the extended TP protocol", there's no corresponding message (like FIND) found in the figure 3.

5. In section 3.2, clause b, " Peers use the BF(S,m,H) algorithm for indicating its query", should the "S" be replaced with "S'"? And what's the difference between F(S) and BF(S). Sorry, I can't understand the operation "F(S) equals (BF(S) bitwise OR (BF(S) bitwise XOR BF(S'))". I think if BF(S') equals (BF(S) bitwise XOR BF(S'), the peer should be included in the peer list of the FIND response. So would you clarify more about it?

6. In section 4.1 option 1, there are some sentences have been duplicated. It's an editorial error.

Best regards,
Rachel

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of 邓灵莉/Lingli Deng
Sent: Wednesday, July 03, 2013 1:47 PM
To: 'ppsp'
Subject: [ppsp] 转发: New Version Notification for draft-deng-ppsp-bfbitmap-00.txt

Hi all,

BR
Lingli

-----邮件原件-----
发件人: [email-masked] [mailto:[email-masked]] 
发送时间: 2013年7月3日 11:55
收件人: Deng Lingli; Yunfei Zhang; Jin Peng; Lingli Deng
主题: New Version Notification for draft-deng-ppsp-bfbitmap-00.txt

Abstract:

The IETF Secretariat

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

---

From: 邓灵莉/Lingli Deng <[email-masked]>
Date: Mon, 15 Jul 2013 16:05:17 +0800

Hi Rachel,

Thanks a lot for your comments. Plz see my remarks inline below.
I have uploaded a revision for the draft this morning. http://www.ietf.org/internet-drafts/draft-deng-ppsp-bfbitmap-01.txt 
Luckily, some of the issues you raised are fixed in this revision, some are still await amendments^^

BR
Lingli

-----邮件原件-----
发件人: Huangyihong (Rachel) [mailto:[email-masked]] 
发送时间: 2013年7月15日 15:25
收件人: 邓灵莉/Lingli Deng; 'ppsp'
主题: RE: [ppsp] 转发: New Version Notification for draft-deng-ppsp-bfbitmap-00.txt

Hi Lingli,

1. In section 3.1, the description following the figure 2 doesn't quite correspond to the figure. For example, the item 3 and 4 couldn't be found in the figure. And I think it's better to show the difference between leech mode and seeder mode in the figure. 
[dll] Both the figure and text description are updated and coordinated in the 01 version.

2. I think section 4 should be placed in the section 3. Otherwise, people will have the question why BF conf could be obtained from both the portal and the tracker. 
[dll] I modified the description to explain that the two are alternatives to one question.

3. In section 3.2, clause a, I don't think the base TP protocol has JOIN request message.
[dll] You are right, I have corrected this in the 01 version. Thank you.

4. In section 3.2, clause b "Integration to the extended TP protocol", there's no corresponding message (like FIND) found in the figure 3.
[dll] FIND related messages are included in the revision.

5. In section 3.2, clause b, " Peers use the BF(S,m,H) algorithm for indicating its query", should the "S" be replaced with "S'"? And what's the difference between F(S) and BF(S). Sorry, I can't understand the operation "F(S) equals (BF(S) bitwise OR (BF(S) bitwise XOR BF(S'))". I think if BF(S') equals (BF(S) bitwise XOR BF(S'), the peer should be included in the peer list of the FIND response. So would you clarify more about it?
[dll] You are right. There are typos around here. What I mean by "BF(S) equals (BF(S) bitwise OR (BF(S) bitwise XOR BF(S'))", is the condition that every marked bit in the array BF(S') is also marked in the array BF(S), where BF(S) stands for the BF-bitmap stored at the tracker for the peer in question "whether to be included in the returned peer list for the FIND message or not". I shall try to add more clarification about this point.

6. In section 4.1 option 1, there are some sentences have been duplicated. It's an editorial error.
[dll] Thanks for pointing it out. The duplication are removed.

Best regards,
Rachel

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of 邓灵莉/Lingli Deng
Sent: Wednesday, July 03, 2013 1:47 PM
To: 'ppsp'
Subject: [ppsp] 转发: New Version Notification for draft-deng-ppsp-bfbitmap-00.txt

Hi all,

BR
Lingli

-----邮件原件-----
发件人: [email-masked] [mailto:[email-masked]] 
发送时间: 2013年7月3日 11:55
收件人: Deng Lingli; Yunfei Zhang; Jin Peng; Lingli Deng
主题: New Version Notification for draft-deng-ppsp-bfbitmap-00.txt

Abstract:

The IETF Secretariat

---

From: "Huangyihong (Rachel)" <[email-masked]>
Date: Mon, 15 Jul 2013 09:05:01 +0000

Hi lingli,

The changes you made make sense to me.

Best regards,
Rachel

-----Original Message-----
From: 邓灵莉/Lingli Deng [mailto:[email-masked]] 
Sent: Monday, July 15, 2013 4:05 PM
To: Huangyihong (Rachel); 'ppsp'
Subject: 答复: [ppsp] 转发: New Version Notification for draft-deng-ppsp-bfbitmap-00.txt

Hi Rachel,

BR
Lingli

-----邮件原件-----
发件人: Huangyihong (Rachel) [mailto:[email-masked]] 
发送时间: 2013年7月15日 15:25
收件人: 邓灵莉/Lingli Deng; 'ppsp'
主题: RE: [ppsp] 转发: New Version Notification for draft-deng-ppsp-bfbitmap-00.txt

Hi Lingli,

Best regards,
Rachel

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of 邓灵莉/Lingli Deng
Sent: Wednesday, July 03, 2013 1:47 PM
To: 'ppsp'
Subject: [ppsp] 转发: New Version Notification for draft-deng-ppsp-bfbitmap-00.txt

Hi all,

BR
Lingli

-----邮件原件-----
发件人: [email-masked] [mailto:[email-masked]] 
发送时间: 2013年7月3日 11:55
收件人: Deng Lingli; Yunfei Zhang; Jin Peng; Lingli Deng
主题: New Version Notification for draft-deng-ppsp-bfbitmap-00.txt

Abstract:

The IETF Secretariat

---

From: Arno Bakker <[email-masked]>
Date: Tue, 30 Jul 2013 12:25:44 +0200

> Your comments would be highly appreciated.

Hi all

some initial comments:

1. The number of chunks in which a content item is divided will be large 
in PPSPP as they are at most 64 KiB (UDP limit) and most likely 1 KiB 
(small chance of loss due to fragmentation). Does your compression 
method still yield low errors for small m when the initial bitmap is large?

2. The peer protocol does not prescribe what chunk availability 
information is sent in HAVE messages, as this depends on the needs of 
the chunk picking algorithm. For example, when the chunk picker uses 
rarest first it may need more up-to-date information than in other 
designs. Typically, as Riccardo remarks, it will provide a more-or-less 
complete overview in the beginning (which may be easily compressed, see 
3.) and then only updates. The latter are also small and easily 
expressed as chunk ranges.

3. The bitmap representation of the chunk availability will depend on 
the chunk picking policy. For video-on-demand, a peer will usually have 
all chunks of the initial parts of the content (or starting at the point 
in the content where it seek-ed to). So the bitmap starts with a large 
number of ones. How the part that follows looks depends on the chunk 
picker. When e.g. rarest first is used with 3 priorities (cf. BitOS) the 
following part will be sparser. For live, there will be a small dense 
window of 1s.

It is not yet clear to me that your method is better at compressing 
these typical maps than the current chunk addressing methods, and that 
it is more efficient given most chunk-availability-exchanges are small 
updates. In this context, you may also want to look at the binmap 
datastructure for representing bitmaps:

	Grishchenko, V. and J. Pouwelse, "Binmaps: hybridizing bitmaps
	and binary trees", Technical Report PDS-2011-005, Parallel and
	Distributed Systems Group, Fac. of Electrical Engineering,
	Mathematics, and Computer Science, Delft University of
	Technology,  The Netherlands, Apr 2009.

Regards,
      Arno Bakker