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

From: "John Hufferd" <[email-masked]>
Date: Sat, 9 Feb 2002 17:05:37 -0800

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 (408) 256-0403, Tie: 276-0403,  eFax: (408) 904-4688
Home Office (408) 997-6136, Cell: (408) 499-9702
Internet address: [email-masked]

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

To:    Julian Satran/Haifa/IBM@IBMIL
cc:    [email-masked], [email-masked]
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:
[email-masked]

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

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

---

From: Stephen Bailey <[email-masked]>
Date: Mon, 11 Feb 2002 17:41:26 -0500

John,

Thanks for the exhausting analysis.

As Paul points out, you do not want to scan the received segment to
recover synchronization with either of these techniques, since it's
too risky.  The TUF draft specifically makes this point.  Basically,
you get one event per segment.  However, if you want to be really
pessemistic you could say the stream IS segmented into tiny frames
that almost result in scanning.

The TUF draft also says that the use of a TUF-derived PDU containment
property should be discontinued after repeated failure of PDU
containment.  Given Julian's repeated statements that TUF should be
analyzed against an infinite stream, I can conclude that the draft
does not make this point strongly or clearly enough.

The TUF assumption is that there are two distinct, quasi-stable
scenarios: segmentation is preserved or it is not.  Obviously if
segmentation is not preserved, there's no point in trying to use the
PDU containment property because it will never hold.  If a receiver
detect that the PDU containment property does not hold for longer than
would represent a transient condition like PMTU change, it gives up
and stops using it.

Julian's argument that TUF needs to be analyzed against an infinite
stream is a straw man.  You can pick the threshold at which a TUF
receiver gives up to be any number that makes you comfortable (10e6
packets, 10e4, whatever).

I'm not clear on how your analysis incorporates worst case data
pattern distribution assumptions.  There is a ULP running inside the
framing protocol, and if we assume the ULP is efficient, MOST of the
data IT carries is actually controlled by the user of the ULP.  This
user data can just as well be a `search and destroy' sequence that
tries every `eye catcher' in a well-formed context.  This technique
boils down to a blind search for a 32-bit integer, and there's the
additional probability of hitting any particular element of the blind
search pattern (basically like your ex and ey).  Julian's extra 64
bits (salt & digest) are not doing anything for you in this case.
It's as simple as the probability of the resegmented stream hitting
the correct 32-bit number.

Thanks again for your work on this.

Steph

---

From: "Douglas Otis" <[email-masked]>
Date: Mon, 11 Feb 2002 16:15:12 -0800

Steph,

Schemes exclusively supporting layers prior to TCP, used in conjunction with
application designators for placement, are advocating a TCP/application
transport amalgam depreciating the TCP interface paradigms.  There is an
effort at adding a shim to SCTP as a generalization of placement
capabilities.  This TCP amalgam concept introduces a new transport and
interface that should attempt application consolidation if such changes are
allowed.  Would you see a benefit in combining generalized structures found
within the SCTP shim within these various introductions of a new layer for
framing and "out of sequence" synchronization for direct placement within
TCP?

Doug