Subject: Re: [ppsp] on performance analysis for chunk addressing schemes/bitmap compression methods

From: lingli deng <[email-masked]>
Date: Thu, 28 Nov 2013 14:43:35 +0800

Hi Johan,

Thank you for the "critical" remarks.

Actually, as I understand it, there are basically two separate issues here:

1) Do we prefer to mandate a single scheme, such as binmap, or do we need
to allow different schemes to be available for implemention/trials?

  There are inconsistency between TP and Peer protocols about this issue,
(in terms of configuration, negotiation, translation, etc.) .

  Although we included relevant issues in the BF scheme discussions, it is
not necessarily bounded with the introduction of BF scheme.

2) Regarding the information exchange problem, I think there may be
different considerations for Tracker and Peer protocols.

  As for the tracker protocol, one may control the exchange frequency to
mitigate the problem, but at the cost of degraded accuracy of peer status
information.

  For peer protocol, the method is not feasible, as the peer needs to
report its latest content status to all neighbors as soon as a new chunk is
downloaded and verified.

  In case of unreliable transport, incremental update methods, as used in
binmap, may suffer from lossy channels and repeated application-level
retransmissions incurred.

As for BF scheme itself, whether it is a simple solution or not as compared
with other schemes (including binmap), is subject to analysis and testing.

BR

Lingli

-----邮件原件-----

发件人: Johan Pouwelse [mailto:[email-masked] <[email-masked]>]

发送时间: 2013年11月26日 17:17

收件人: 邓灵莉/Lingli Deng

抄送: ppsp

主题: Re: [ppsp] on performance analysis for chunk addressing schemes/bitmap
compression methods

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

----composed-on-my-mobile----

On Nov 26, 2013 7:36 AM, "邓灵莉/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.

> 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]<[email-masked]>]
代表

> 邓灵莉/Lingli Deng

> 发送时间: 2013年11月5日 8:35

> 收件人: 'ppsp'

> 主题: [ppsp] 转发: New Version Notification for

> draft-deng-ppsp-bfbitmap-04.txt

> 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]<[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

> _______________________________________________

> ppsp mailing list

> [email-masked]

> https://www.ietf.org/mailman/listinfo/ppsp

> _______________________________________________

> ppsp mailing list

> [email-masked]

> https://www.ietf.org/mailman/listinfo/ppsp

-- 
邓灵莉/Lingli Deng
中国移动通信研究院/China Mobile Research Institute
e-mail: [email-masked]
tel: 15801696688-3367
mobile: 13810597148