[Tsvwg] Re: [rdma] a proposal for a different No-Data-Touch framer for TCP

["John Hufferd" <[e-mail]>]

Step, Julian,
While looking at the calculations in fresh light, I think I spotted an
error that gave Julian's ESC approach, to high a probability.  That is I
multiplied both ex and ey by 361.  I think I should have only multiplied
one by that value.

"ey" should have been left at 2.3e-10  and the resulting total probability
(ex * ey) should have been 1.934e-19

This would mean that the probability of a False Positive, given a
segmentation occurred, to be 1.934e-19 for ESC and the current TUF value
would still be 1.962e-17.

That would mean that if the CRC was part of the PDU, then the probability
would be even less, and yet only use 2 extra words would be used in the
framing header.

It seems clear however, if three words of header are used with TUF, vrs
normal ESC, that the value probability of a false positive with the 3 word
TUF at 4.557e-27 is  a lot better then the 1.934e-19 in the normal 3 word
header of ESC.


 .
.
 .
John L. Hufferd
Senior Technical Staff Member (STSM)
IBM/SSG San Jose Ca
Main Office [phone], Tie: 276-0403,  eFax: [phone]
Home Office [phone], Cell: [phone]
Internet address: [e-mail]
---------------------- Forwarded by John Hufferd/San Jose/IBM on 02/10/2002
04:52 PM ---------------------------

John Hufferd
02/09/2002 05:05 PM

To:    Stephen Bailey <[e-mail]>, Julian
       Satran/Haifa/IBM@IBMIL
cc:    [e-mail]
From:  John Hufferd/San Jose/IBM@IBMUS
Subject:    Re: [rdma] a proposal for a different No-Data-Touch framer for
       TCP  (Document link: John Hufferd)

Steph, Julian,
The following is an attempt to determine the probability of a false
positive, both with the TUF approach as defined in
draft-ietf-tsvwg-tcp-ulp-frame-01.txt, and the semi draft that Julian
proposed.

Since we are only interested in the case of False Positives given a
re-segmentation occurs, I think it is possible to determine which of the
two approaches is less risky.

Here are the two layouts:

Current TUF has a 64 bit header at the beginning of Segment:
1. Length of 16 bits (Must match up with the physical length of the
segment)
2. Key  48 bits (Key Randomly Chosen by ULP,  -- Known by sender and
receiver, and changed as some undefined interval, if at all)

Julian's Eye-catcher-Salt-CRC approach (which I will call ESC) is 96 bits
1. Eye-catcher - 32 bits (Chosen by the ULP,  could also be chosen like the
Key in TUF, known by both sides)
2. Random number - 32 bits (Generated by ULP, unique to this PDU only)
3. CRC  - 32 bits (Generated by ULP based on 1. & 2.)

Lets first examine the ESC.

Once the Eye-catcher is determined, the Random number is chosen and the CRC
is computed, but to the Framer this is just string of bits passed from the
ULP.  The Receiving Framer (deFramer?) does not know the actual magic
string of bits which it should look for within the incoming payload.
Therefore it needs to do a computation at the start of each segment to make
sure the approprate string is received.

Given any beginning Eye-catcher, randomly chosen or not, there are a number
of 64 bit strings which can be interpreted as a valid salt and CRC.  That
is, for every 32 bit Salt, there is a valid 32 bit CRC.  Therefore, there
is as many valid 64-bit strings, which can follow the Eye-catcher as there
are unique 32-bit Salt numbers.  This means, there are (2**32) valid 8 byte
strings that can follow the Eye-catcher.

So in the case of ESC we have:

 The probability "ex" that a 32-bit Random Eye-catcher (or Key) is
"incorrectly" (do to re-segmentation) located at the beginning of a segment
, and the probability "ey" that one of the 2**32 valid 8 byte strings will
follow that Eye-catcher.  I think that makes it the total probability equal
to:
ex times  ey.

We have "ex" equal to the probability of the Eye-catcher occurring in any
word times the number of chances that might happen.  This means the
probability of any 32 bit value occurring  is 1/(2**32) times 361  where
361 is the number of possible segment points that could have been made in a
1460 byte payload (with a total of 3 header words and one byte of data).
Therefore:

ex = (1/2**32) times 361
ex = 2.3e-10 * 361
or
ex = 8.41e-8

The value of "ey" is equal to the probability that one of the 2**32 valid 8
byte strings will follow the Eye-catcher.  This is 1/2**32 times the number
of chances.  In this case the number of chances equals the number of
possible segment points that could have been made in a 1460 byte payload
(with a total of 3 header words and one byte of data), which is 361.
Therefore:

ey = 2.3e-10 * 361
or
ey = 8.41e-8

Therefore with ESC  we have the total probability of false positive of:

ex*ey = 8.41e-8 * 8.41e-8
or
ex*ey = 7.06 e-15


Now we will examine  the case of the current TUF proposal:

We have a probability "tx" that a 48-bit Random Key (or Eye-catcher) is
"incorrectly" (do to re-segmentation) located at + 2 bytes from the
beginning of a segment , and the probably "ty" that a 16 bit field
preceding it, will be a valid length of the current Segment.

I think that probability is equal to  tx  times  ty.

Now "ty" has 1 chance of occurring in 2**16 -10 (there must be at lease 8
bytes of TUF header + one byte of data, and zero is not valid so subtract
10 from the number of valid lengths)
ty = 1/((2**16)-10)
ty = 1/65526
ty = 1.526e-5

"tx" is the probability of a specific 48 bit string occurring at +2 bytes
into each possible segmentation point.  This is the probability of the
string occurring times the number of possible chances it has to occur.
Since there can be at most 365 TCP payload words in a normal Ethernet Frame
((1500-20-20)/4 =1460/4 = 365 words) then that means there are 365-3 or 362
possible segment point, which could leave at least a 2 word header and 1
byte of data.
Therefore:
tx = (1/2**48) times 362
tx = ((3.55e-15) * 362
tx = 1.286e-12).

Therefore with Current TUF we have the total probability of false positive
of:

tx*ty = 1.286e-12 * 1.526e-5
or
tx =  1.962e-17

Therefore, based on the calculations above, I believe that the Current TUF
approach offers a lower probability of False positive then does the
straight version of ESC.

But remember, Current TUF has a 64 bit header and ESC has a 96 bit header.
If we were to extend the TUF proposal to 96 bits the calculation would look
like:

ty = 1.526e-5 (Same as before)

AND,

tx =l (1/2**80) * 361
tx = 8.27e-25 * 361
tx = 2.986e-22

and
tx * ty = 2.986e-22 * 1.526e-5
tx * ty = 4.557e-27

However, ECS can also use a PDU header as part of the total salt.  The PDU
is not a fully random set of bits, but it does also reduce the probability
of False Positive a great deal more.  (I will let someone else compute that
probability.) The current probability of a false positive with a TUF's two
word header is 1.962e-17, but I think it is safe to guess that the ECS when
factoring in a PDU, would lower its probability a great deal lower then
7.06 e-15 (probably lower then current TUF), and it would then only need a
two word header like TUF.

Summary:
If you compare Current TUF (which has 2 word headers) to ECS (which has 3
word headers) you have a lower probability of False Positives with TUF.  If
you compare Current TUF with ECS that uses the CRC with the Header of the
PDU (so ECS only has a 2 byte Header) there is reason to believe that ECS
would have the lower probability of false positive.

So the questions should be: is  1.962e-17 a low enough probability of false
positives that we can get on with the Framing per the current TUFs
proposal?  Or do we need to add a third word to TUFs, or use the ECS with
PDU CRC.


 .
.
 .
John L. Hufferd
Senior Technical Staff Member (STSM)
IBM/SSG San Jose Ca
Main Office [phone], Tie: 276-0403,  eFax: [phone]
Home Office [phone], Cell: [phone]
Internet address: [e-mail]


Stephen Bailey <[e-mail]> on 02/09/2002 08:35:17 AM

To:    Julian Satran/Haifa/IBM@IBMIL
cc:    [e-mail], [e-mail]
Subject:    Re: [rdma] a proposal for a different No-Data-Touch framer for
       TCP



For a proper safety analysis, you can not assume that the the contents
of the the stream (or the PDU) are randomly distributed.  You have to
assume the stream has worst-case contents.  Defining `worst case' is
the hard part.

Steph

> The mathematics behind the proposal are simple. You have two random
> numbers "against" a finite-length PDU.
> In you original proposal you have single random number (the marker)
> against a quasi infinite stream. The chance to miss is 1.
> With any decent digest (e.g. a CRC) you have a small (2**-64) chance to
> miss per PDU word (for every new PDU you have a new pattern).  All the
> tricks like alignment etc do not decrease the cardinality of stream -
> i.e., it is still infinite and then a constant framer is no good.
> The cost of the new scheme is also tolerable.

------------------------ Yahoo! Groups Sponsor ---------------------~-->
Sponsored by VeriSign - The Value of Trust
Pinpoint the right security solution for your company - FREE
Guide from industry leader VeriSign gives you all the facts.
http://us.click.yahoo.com/pCuuSA/WdiDAA/yigFAA/W6uqlB/TM
---------------------------------------------------------------------~->

To unsubscribe from this group, send an email to:
[e-mail]



Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/








_______________________________________________
tsvwg mailing list
[e-mail]
https://www1.ietf.org/mailman/listinfo/tsvwg