Subject: [Tsvwg] Re: draft-ietf-tsvwg-quickstart-00: Consideration of QS NONCE.

From: Sally Floyd <[email-masked]>
Date: Tue, 23 Aug 2005 15:52:21 -0700

Gorry -

...
>I think these issues are important, and that unless other methods are found,
>I would support this use of a NONCE. 

Great.

...
>I believe the method also lends itself
>to extension (see a proposal in (B) below).
>
>B) Thoughts on a more conservative NONCE operation.
>---------------------------------------------------

I think that having the sender retry the downgraded rate request
with a second QS request, to see if a valid nonce is returned, is
a great idea.

My inclination would be to say that the sender MAY decide to only
accept a QS response with a valid nonce (indicating the approval
by the routers of the original rate request), and that when a rate
request is downgraded in the network, the sender MAY send a new QS
request with the downgraded value to see if this is in fact approved
with a valid nonce returned in the response.  

My guess would be that one initial deployment scenario for QS would
be in Intranets, and in some of these environments the sender might
have sufficient trust of the environment to act on a downgraded QS
request the first time around.  

Just as an observation it also seems that if end nodes
frequently resend requests in order to get a request with a valid
nonce, this could somewhat complicate implementations at routers
(giving routers more of an incentive to keep per-flow state,
remembering that it saw a request from this sender recently,
so that this new request is essentially a repeat of the earlier
one (possibly with a smaller requested rate)).

About the second part of your email, my inclination is not to use
the zero nonce value for an "erased" nonce, for the reasons below.
But perhaps we need more feedback about how difficult it is (or is
not) for routers approving a downgraded rate request to set the
nonce to a random or vaguely unpredictable value.  The rest of the
email is an expansion on this paragraph.

...
>C) Zero NONCE value?
>--------------------
>One thing to be considered when using a QS NONCE, is the need for routers to
>assign a random number to an "erased" nonce. This sounds like it does not
>lend itself to a simple implementation (router hardware/software engineers
>may tell you different).  

Well, one thing that might make it less of a problem is that the
requirements for randomness are pretty lax - almost any vaguely
plausible randomization scheme should do just fine.  All that matters
is that a reduced Rate Request received at the receiver has a
reasonable chance of having a different QS nonce that the original
value sent by the sender, and that the receiver can't construct the
original nonce from the one that is received.  And that the receiver
can't tell if the rate request is the original one or a downgraded
one, as discussed below.

>If it is a problem, is it possible for a
>negotiating router to simply reset the nonce value to zero instead. There
>would be some implications:
>+ The sender would have to choose a non-zero nonce for the QS probes it
>sends (simple to implement).

Not a problem.

>+ A down-stream device would immediately know the nonce had been erased (is
>this an issue?).

I think this could be a problem.  If the receiver knows that the
received rate request is not the original rate request sent by
the sender, then this is one step in helping the receiver to 
learn the original rate request.  And if the sender and receiver
have a long relationship, with many QS requests going back
and forth over time, learning the original rate request helps
the receiver to lie about the value of the received rate request.
So, if senders are allowed, if they want, to use QS requests
where the rate is reduced in the network (which seems ok to me),
then I think it is better for the receiver not to be able to
tell if the received Rate Request is the original rate request
or a reduced value.

*If* we were going to have routers zero the nonce when downgrading
a rate request, because this was easier for routers, that would be
one more argument for senders not to rely on rate requests with a
downgraded value.  (Because the receiver has more information for
learning the original rate request, and therefore more freedom,
when the request is reduced in the network, to report a reduced
request that is just one step below the original rate request.) 
My inclination would be to leave this section how it is.

>+ The nonce properties become 1/15 rather than 1/16.

Again, this one wouldn't be a problem.

Many thanks for the feedback.  

- Sally

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

---

From: Gorry Fairhurst <[email-masked]>
Date: Wed, 24 Aug 2005 14:38:51 +0100

I agree with you. See some comments in-line.

Gorry

> with a valid nonce returned in the response.
- I like allowing this.
> request the first time around.
- Agreed, but would senders have a method to know this trust boundary?
> one (possibly with a smaller requested rate)).
- Seems reasonable, this is mitigated somewhat by the re-probe being smaller
and one path RTT later.
> email is an expansion on this paragraph.
- If the WG can find feedback on complexity this would be good.

> can't tell if the rate request is the original one or a downgraded

- Perhaps the I-D should try to capture the "randomness" requirement? - The
re-written nonce MUST NOT be easily determined from inspection of the packet
or by previous packets (e.g. it MUST NOT be directly implied by an algorithm
utilising only a combination of specific packet header fields). The nonce
therefore needs to include some information not accessible to the receiver
(i.e. Random, or changing unpredictable internal router/host state).

> I think this could be a problem.
I wondered too...

> If the receiver knows that the
> have a lon  g relationship, with many QS requests going back
Yes.
> My inclination would be to leave this section how it is.
OK - I agree the proposed method of using a replaced random value has
advantages over the zero option. If the router randomness function can be
implemented at reasonable cost, this seems a reasonable argument for using
the method as you say in -00.
> Many thanks for the feedback.

Gorry

---

From: Mark Allman <[email-masked]>
Date: Mon, 29 Aug 2005 10:00:57 -0400

> with a second QS request, to see if a valid nonce is returned, is

I'll disagree, because ...

> Just as an observation it also seems that if end nodes frequently
> resend requests in order to get a request with a valid nonce, this
> could somewhat complicate implementations at routers (giving routers
> more of an incentive to keep per-flow state, remembering that it saw a
> request from this sender recently, so that this new request is
> essentially a repeat of the earlier one (possibly with a smaller
> requested rate)).

I am not sure this scheme is really all that workable in practice.  Let
me walk through this to try to be clear...

  + Say a sender uses a request of R without the nonce.  The network
    changes this to R' (R' < R).  If the receiver knows the sender
    always requests R then the echo can be R and nobody is the wiser -
    thus, gaming the scheme.

  + So, we introduce a random nonce.  Now the rate request, R, gets sent
    with a random nonce, say X.  When some router in the path reduces R
    to R' then the nonce is set to some new random value, say X'.  The
    receiver echos both back and the sender can figure out
    (probabilistically, anyway) that the rate request was changed in the
    network.  So, if the receiver knows that the sender advertises R
    then it can game the echo to R-1 since it doesn't know the initial
    nonce.

    Sally noted in the last meeting that I am indifferent about the
    nonce and the above situation is precisely why.  It really doesn't
    protect things all that much and it's more complexity.  I don't
    think it necessarily really hurts all that much, but I could do
    without it.

  + So, then Gorry's scheme offers better protection.  In this case, we
    send rate request R and nonce X, as before.  A router that changes R
    to R' also changes X to some random X'.  However, the sender, in
    this case doesn't trust the answer because the rate request didn't
    make it through the network without being downgraded.  So, the
    sender replays R' with some new nonce Y.  The idea being that R'
    should now make it through the path and so, the receiver can bounce
    back R' and Y (the unchanged nonce).  This gives the sender a much
    stronger assurance that nobody is lying.

    The wondering here is if the second rate request (R') can make it
    through the network without being reduced *further*.  The first time
    through the router (that reduced the request to R') looked around
    and determined that it could only give out R' bytes/sec of capacity
    and marked the capacity as "allocated" from the QS point-of-view.
    That allocation lasts only so long, of course.

    However, without the added state of remembering who was given what
    rate the best the router can do is to just look around and assess
    the current situation and set the rate accordingly.  Since R' is
    already allocated then it could well be that there isn't R' left
    over to give out again.  So, the router may reduce the request to
    R'' and change the nonce and start the cycle all over again (i.e.,
    the sender won't accept it because the nonce has been changed).
    Even if the router has R' available then one flow is getting 2*R'
    worth of capacity -- of which it will only ever use R' bytes/sec.

    Also, the routers are going to have to be tuned to understand that
    the capacity they are handing out may not be used as quickly as
    assumed now because of this additional RTT that *could* be needed
    (clearly a router reducing the rate will know the extra RTT would be
    used, but a router not reducing the rate request would have no way
    to know whether the rate was going to be used within the RTT or
    whether there was to be another RTT of negotiation in there).

From my point of view, Gorry has shown us how to make the nonce quite a
bit better, but I think to make it really workable we'd have to involve
the routers to remember what they handed out recently to make this all
that practical at all.  I think this all boils down to a question of
whether we care enough about lying receivers to complicate the
router-side of quick start.  Thoughts?

> accept a QS response with a valid nonce (indicating the approval by
> the routers of the original rate request), and that when a rate

I am not sure this sort of loose approach is advisable.  (In other
words, with no change in the routers I am not sure this is a reasonable
path for senders to take.)

allman

-- 
Mark Allman -- ICIR -- http://www.icir.org/mallman/

---

From: Mark Allman <[email-masked]>
Date: Mon, 29 Aug 2005 10:03:12 -0400

> > more of an incentive to keep per-flow state, remembering that it saw
> > a request from this sender recently, so that this new request is
>   Seems reasonable, this is mitigated somewhat by the re-probe being
>   smaller and one path RTT later.

My quick comment is that I don't think the smaller request in the
re-probe mitigates this at all because at some point in the network the
re-probe is not, in fact, "smaller" but is really the same size.

allman

---

From: Gorry Fairhurst <[email-masked]>
Date: Mon, 29 Aug 2005 22:05:14 +0100

> re-probe is not, in fact, "smaller" but is really the same size.
Accepted - if you consider the "bottleneck" router, then it's certainly the 
case that at this router the resent request would have the same size.

> 
> 
> 
> ------------------------------------------------------------------------
> 

More on the later comments in the thread tomorrow,

Gorry