[dtn-security] Re: SDNV-new : OK

Manikantan Ramadas <mramadas@masaka.cs.ohiou.edu> Sat, 04 June 2005 20:29 UTC

Received: from masaka.cs.ohiou.edu (masaka.cs.ohiou.edu [132.235.3.154]) by webbie.berkeley.intel-research.net (8.11.6/8.11.6) with ESMTP id j54KTuV22416 for <dtn-security@mailman.dtnrg.org>; Sat, 4 Jun 2005 13:29:56 -0700
Received: from masaka.cs.ohiou.edu (localhost [127.0.0.1]) by masaka.cs.ohiou.edu (8.12.10+Sun/8.12.8) with ESMTP id j54KTovP013506 for <dtn-security@mailman.dtnrg.org>; Sat, 4 Jun 2005 16:29:51 -0400 (EDT)
Received: (from mramadas@localhost) by masaka.cs.ohiou.edu (8.12.10+Sun/8.12.10/Submit) id j54KToNo013505 for dtn-security@mailman.dtnrg.org; Sat, 4 Jun 2005 16:29:50 -0400 (EDT)
Date: Sat, 04 Jun 2005 16:29:50 -0400
From: Manikantan Ramadas <mramadas@masaka.cs.ohiou.edu>
To: dtn-security@mailman.dtnrg.org
Message-ID: <20050604202950.GC14707@masaka.cs.ohiou.edu>
References: <200505241854.j4OIsx724035@smtp-bedford-dr.mitre.org> <42944BEF.7090007@cs.tcd.ie> <20050525152006.GA7633@pisco.cs.berkeley.edu> <42949E83.9050000@cs.tcd.ie> <20050525163707.GB14911@pisco.cs.berkeley.edu> <4294ABB9.5010009@jpl.nasa.gov> <4295D547.9080808@cs.tcd.ie> <20050531172941.GA30682@pisco.cs.berkeley.edu> <20050601160110.GF9319@masaka.cs.ohiou.edu>
Mime-Version: 1.0
Content-Type: multipart/signed; micalg="pgp-sha1"; protocol="application/pgp-signature"; boundary="DSayHWYpDlRfCAAQ"
Content-Disposition: inline
In-Reply-To: <20050601160110.GF9319@masaka.cs.ohiou.edu>
User-Agent: Mutt/1.4.1i
Subject: [dtn-security] Re: SDNV-new : OK
Sender: dtn-security-admin@mailman.dtnrg.org
Errors-To: dtn-security-admin@mailman.dtnrg.org
X-BeenThere: dtn-security@mailman.dtnrg.org
X-Mailman-Version: 2.0.13
Precedence: bulk
Reply-To: dtn-security@mailman.dtnrg.org
List-Unsubscribe: <http://mailman.dtnrg.org/mailman/listinfo/dtn-security>, <mailto:dtn-security-request@mailman.dtnrg.org?subject=unsubscribe>
List-Id: DTN Security Discussion <dtn-security.mailman.dtnrg.org>
List-Post: <mailto:dtn-security@mailman.dtnrg.org>
List-Help: <mailto:dtn-security-request@mailman.dtnrg.org?subject=help>
List-Subscribe: <http://mailman.dtnrg.org/mailman/listinfo/dtn-security>, <mailto:dtn-security-request@mailman.dtnrg.org?subject=subscribe>
List-Archive: <http://mailman.dtnrg.org/pipermail/dtn-security/>

Hi folks,

  After an offline discussion with Scott, I have come around to joining the
consensus for dropping the SDNV-8/SDNV-16s in favour of the proposed SDNV
scheme (the 1/2/3/4/5/6/7/8) which allows an SDNV of total size atmost 9
bytes with value range 0-2^68-1. We don't have a real feel for how
frequently the range 4096-32767 is likely to be used in LTP, and our current
speculations don't predict a large hit-ratio for the range. Therefore, 
it seems better to be homogeneous with the rest of the bundle protocol suite
and adopt the proposed SDNV scheme.

- Mani.

On Wed, Jun 01, 2005 at 12:01:10PM -0400, Manikantan Ramadas wrote:
> Folks,
> 
>   My apologies for falling way beyond on this thread, but I have caught up
> finally.
> 
> To summarize this "one true SDNV" scheme,   
> we have eaten up 4 bits into the SDNV discriminant at the cost of the
> maximum size of SDNV; it was 2^1024-1, which now becomes 2^68-1.
> 
> I tend to agree with the general consensus in this thread that we should
> probably quit worrying about fitting cryptographic keys in an SDNV, as they
> are ever bit hungry, and it is only a matter of time before they overflow
> any SDNV scheme we offer. It seems like a good idea for crypto. fields in
> the DTN security specs, LTP extension specs, and other places to be encoded
> to have their length field be an SDNV, and have the data of the indicated
> length follow. Good.
> 
> I think Rajesh mentioned that the real value of the SDNV scheme shows up
> only for relatively smaller values. I tend
> to agree with that, and hence would like to point out a key point that was
> missing in our discussion here. SDNV-16's were designed to let you store
> values from 128-32767 in just two octets (as opposed to SDNV-8 - the original
> SDNV - which takes 2 octets for 128-255, 3 octets for 256-65535). SDNV16s,
> as you can see, were designed to be optimal for data typically falling in
> this range 128-32767. Note that they do need two bytes even to store data in
> the range 0-127, and less optimal for this range compared to SDNV8s.
> 
> With our current proposal, we can store only values from 128-4095 in two
> octets, and requires three octets for 4096-2^20-1. While this is clearly
> more optimal than SDNV8's, it is not so when compared to SDNV16s.
> Laying them out :
> 
> 	Octets Required			SDNV16			proposed SDNV
>     ---------------         ------			-------------
>     	1					  --			0-127					
>     	2					0-32767			128-4095
> 		3					32768-65535		4096-2^20-1
>         4					2^16-2^24-1		2^20-2^28-1
>         5					2^24-2^32-1		2^28-2^36-1
> 		..........
> 
> Note that the way SDNV16 is defined, it always needs atleast 2 octets to
> encode. 
> 
> So, when we go to the octets required field being greater than 4, the
> benefits of eating into the discriminant begin to show. It is the 2 octet
> case that makes me a little nervous about the new scheme. It costs an octet
> more for values in the range 4096-32767. We have quite a few fields like 
> blockoffsets and chunk length, in LTP reception reports that might fall in
> this range, and we lose the benefits of SDNV16 with this scheme. If those
> fields take values greater than 32768, the new scheme beats it, sure. 
> 
> Hence I can't yet make up my mind on giving away SDNV16's altogether. That
> said, I am in principle, in favor of having a one true SDNV scheme that
> would make life simpler. But can't make up my mind just yet on how
> frequently the range 4096-32767 is likely to be used in LTP.
> 
> Thoughts?
> 
> - Mani.
> 
> On Tue, May 31, 2005 at 10:29:41AM -0700, Michael Demmer wrote: 
> > 
> > I took a pass at changing the language from the original LTP spec to
> > match my new proposal for SDNV encodings:
> > 
> > ---
> > 
> > Self-Delimiting Numeric Value (SDNV)
> > 
> >    The design of LTP attempts to reconcile minimal consumption of
> >    transmission bandwidth with
> > 
> >       (a) extensibility to satisfy requirements not yet identified and
> >       (b) scalability across a very wide range of network sizes and
> >           transmission payload sizes.
> > 
> >    A key strategic element in the design is the use of self-delimiting
> >    numeric values (SDNVs) that are similar in design to the Abstract
> >    Syntax Notation One [ASN1] encoding of data structures. An SDNV can
> >    be used to encode a numeric value in the range 0 .. (2^68 - 1),
> >    using 1 to 9 octets.
> > 
> >    The first octet of an SDNV -- the "discriminant" -- characterizes
> >    the SDNV. If the most significant bit of the discriminant is zero,
> >    the length of the SDNV is 1 octet and the remaining 7 bits of the
> >    discriminant, treated as an unsigned integer, is the value of the
> >    SDNV. An integer in the range of 0 to 127 can be encoded this way.
> > 
> >    Otherwise (if the most significant bit of the discriminant is 1),
> >    the next 3 bits of the discriminant encode the length of the SDNV.
> >    If the content of these 3 length bits, treated as an unsigned
> >    integer, has the value N, then N+1 additional octets are used to
> >    represent the value. The value is found by concatenating the
> >    remaining 4 bits of the discriminant with octets 2 through N+2 of
> >    the SDNV, and treating this result as an unsigned integer.
> > 
> >    The following table outlines the SDNV encoding for all value
> >    ranges, their associated discriminant encodings, and the total
> >    length in octets of the SDNV.
> > 
> >    Value Range         Discriminant     SDNV Length 
> >    ----------------    ------------     -----------
> >    0        127         0XXX XXXX            1
> >    128      4095        1000 XXXX            2
> >    4096     1048575     1001 XXXX            3
> >    2^20     2^28 - 1    1010 XXXX            4
> >    2^28     2^36 - 1    1011 XXXX            5
> >    2^36     2^44 - 1    1100 XXXX            6
> >    2^44     2^52 - 1    1101 XXXX            7
> >    2^52     2^60 - 1    1110 XXXX            8
> >    2^60     2^68 - 1    1111 XXXX            9
> > 
> >    An SDNV can therefore be used to efficiently represent both large
> >    and small integer values. However, SDNV is clearly not the best way
> >    to represent every numeric value. When the maximum possible value
> >    of a number is known without question, the cost of an additional 8
> >    bits of discriminant may not be justified. For example, an SDNV is
> >    a poor way to represent an integer whose value typically falls in
> >    the range 128 to 255.
> > 
> >    In general, though, we believe that SDNV representation of selected
> >    numeric values in LTP segments yields the smallest segment sizes
> >    without sacrificing scalability.
> > _______________________________________________
> > dtn-security mailing list
> > dtn-security@mailman.dtnrg.org
> > http://mailman.dtnrg.org/mailman/listinfo/dtn-security
> 
> -- 
> "'Beauty is truth, truth beauty,'--that is all
>   Ye know on earth, and all ye need to know." - John Keats
> ____________________________________________________________________
>   
> * Manikantan Ramadas * IRG, OU * http://irg.cs.ohiou.edu/~mramadas *
> ____________________________________________________________________



-- 
"'Beauty is truth, truth beauty,'--that is all
  Ye know on earth, and all ye need to know." - John Keats
____________________________________________________________________
  
* Manikantan Ramadas * IRG, OU * http://irg.cs.ohiou.edu/~mramadas *
____________________________________________________________________