[dtn-interest] [Fwd: Re: [IRSG] Review of draft-irtf-dtnrg-sdnv-05]

[Elwyn Davies <[e-mail]>]

Hi.

I realized that this set of comments were not sent to the list.

Lachlan Andrew reviewed the draft for the IRSG.

Wes and Lachhlan have settled on resolutions of the points below, and a
new version (-06) has been published.

If anybody has further issues with the draft please send email to the list asap.

Regards,
Elwyn

Eddy, Wesley M. (GRC-MS00)[ASRC AEROSPACE CORP] wrote:
> Hi Lachlan, thanks for the thorough review.  I'm working on an
> update that incorporates most of the changes.  A couple of
> places where I diverge are:
> 
> 1 - You're right, "bit-strings" would technically not be representable
>     due to leading zeros.  I'm changing this to be the value stored
>     in an arbitrary-length bit-field.  This is how some of the flags
>     fields in bundle protocol headers are encoded, and I think that's
>     what we really mean.  Thanks for the correction.
> 
> 2 - You note that O(log_2 n) should be O(log n) ... since we're
>     referring to the number of bits in n, rather than decimal digits,
>     isn't log_2 correct?
> 
> --
> Wes Eddy
> MTI Systems
> 
> 
>> -----Original Message-----
>> From: [e-mail] [mailto:[e-mail]]
>> On Behalf Of Lachlan Andrew
>> Sent: Monday, December 28, 2009 7:33 PM
>> To: Internet Research Steering Group; [e-mail]-
>> research.net
>> Subject: [IRSG] Review of draft-irtf-dtnrg-sdnv-05
>>
>> This is an IRSG review of   draft-irtf-dtnrg-sdnv-05.  (I'm sending it
>> to dtn-interest as instructed, but expect it to be blocked by their
>> members-only policy.  Lloyd, could you forward it to that list?)
>>
>> The draft is accessible to those outside the area, and the writing is
>> consistent.  The writing is also clear, although in my opinion some
>> sections could be improved according to the suggestions below.
>>
>> The issue of variable-length encoding has been studied extensively in
>> other contexts such as lossless compression.  I would recommend citing
>> more of this literature, and explaining the advantages and
>> disadvantages of the "current SDNV" compared with common existing
>> schemes.
>>
>> Detailed comments follow.
>>
>> Cheers,
>> Lachlan
>>
>> The SDNVs described only unambiguously code arbitrary length
>> bit-strings if those bit-strings start with 1, or consist of a single
>> '0'.  That is, they only encode binary representations of non-negative
>> integers.  I strongly recommend removing all text which suggests that
>> SDNVs can encode arbitrary bitstrings.  This would make unnecessary
>> the two comments on page 6 prefaced by "To be perfectly clear".  If
>> comment (1) on page 6 is retained, it should be explicit that the
>> leading 0 in the string '0' cannot be discarded.
>>
>> It is odd that no mention is made of standard Elias coding.  The
>> proposed SDNV is essentially a base-128 version of Elias gamma coding,
>> as described in Section 3.5 of Khalid Sayood, Lossless Compression
>> Handbook, Elsevier, 2003.  (The relevant section is available online
>> on Google books.)
>>
>> In Section 2, what is the role of the "early definition of the SDNV
>> format"?  I'd start this section by mentionining that the term SDNV
>> had been applied to several different formats, listing where the term
>> had been used to mean formats other than the format defined in this
>> document.
>>
>> The definition on page 6 seems a mixture of algorithm and definition.
>> It would be clearer if it describe a sequence of encoding operations
>> in the order in which they occur: zero-padding, followed by grouping
>> into groups of 7 bits, followed by prepending a flag bit to each group
>> of 7 bits to form a byte.  If, instead of an algorithm, its aim is to
>> be a formal definition, then it may be more appropriate to give a
>> mathematical definition than to give a collection of steps.
>>
>> Notions such as "call by reference" and "call by value" seem more
>> appropriate to a subroutine than an algorithm, since the algorithm
>> makes no mention "calling".  In the first step of the encoding
>> algorithm, it is misleading to say "set the return value to X" when X
>> is not the final value returned.  It is also misleading to talk of
>> right-shifting  n,  rather than a variable which was initialised to
>> n.  As a guide, I'd rephrase the algorithm as
>> * Set  Y  equal to  n,  and  X to a single byte whose least
>> significant bits are the least significant 7 bits of n, and whose most
>> significant bit is 0
>> * Divide Y by 128 (rightshift by 7 bits)
>> * While Y is non zero
>> *    Let  Z  be the byte formed by the bitwise OR of 0x80 and the 7
>> least significant bits of  Y
>> *    Prepend  Z  to  X
>> *    Divide Y by 128 (rightshift by 7 bits)
>> * end while
>> * Return X
>>
>> In the decoding algorithm, the use of the notions of "pointer", "left"
>> and "right" (within the encoded string) are unnecessarily ambiguous.
>> I'd start the description by stating that the input is a string of
>> bytes in the order produced by the encoding algorithm.
>>
>> The first paragraph of Section 3.2 seems unnecessary, given that the
>> point about memory allocation is made again after the algorithm.
>>
>>
>> Minor points:
>>
>>
>> First sentence of second paragraph of section 1:  I suggest changing
>> "describing a common problem encountered in network protocol
>> engineering" to "describing the drawbacks of using fixed-width
>> protocol fields".
>>
>> The phrase "in the wire format" on page 6 seems odd.  If it is
>> specifying order of the bits, then a reference should be given to the
>> definition of "wire format", and "taken in order" should presumably be
>> replaced by "taken from left to right".
>>
>> The draft would be more useful if it contained less unnecessary text,
>> such as "The format currently used is very simple" on page 6, and "can
>> easily be seen to have" (instead of "has").
>>
>> On page 7, "O(log_2 n)" should just be  "O(log n)".
>>
>> On page 18, the comment "and and integer l" should be "and an integer
>> slen".  (Note that using a lower-case letter "ell" as an integer can
>> lead to ambiguity with the integer one.)  The first sentence should
>> also presumably mention the second input argument.
>>
>>
>>
>> Typos:
>> Page 3: "acheive" --> "achieve"
>> Page 4: "unneccessary" --> "unnecessary"
>>
>> Punctuation:
>> On page 4, I'd add a comma after "since" in  "since due to high
>> delays, DTN protocols must".
>>
>>
>>
>> --
>> Lachlan Andrew  Centre for Advanced Internet Architectures (CAIA)
>> Swinburne University of Technology, Melbourne, Australia
>> <http://caia.swin.edu.au/cv/landrew> <http://netlab.caltech.edu/lachlan>
>> Ph [phone]
>> _______________________________________________
>> IRSG mailing list
>> [e-mail]
>> http://mailman.isi.edu/mailman/listinfo/irsg