Subject: noninfinite peak data rates

From: "Michael W. Patrick" <[email-masked]>
Date: Fri, 16 May 1997 18:31:47 -0400

1)  Does a noninfinite "peak data rate" mean the same as the
    "maximum transmission rate" defined in RFC1363?  
    I read RFC1363 to require a "minimum packet spacing" where a
    leaky bucket gets only a single packet's worth of tokens that drain at
    the peak rate, and packet forwarding is delayed until the bucket empties.
    So a peak data rate of 10% of incoming link capacity means that
    after start of arrival of a packet of length L, 10*L byte
    times must pass before the next packet can start arrival.
    
2) Does a flow requesting guaranteed service with a non-infinite peak
    rate somehow have to manage its minimum packet spacing?

3) Does a network element accepting a GS flow with noninfinite peak rates
    somehow have to police minimum packet inter-arrival times?
        
-mike
------------------------------------------------------------------------
Michael W. Patrick  Motorola ISG/NSD               20 Cabot Rd, MS M4-30
[email-masked]  (508) 261-5707              Mansfield MA 02048

---

From: Roch Guerin <[email-masked]>
Date: Mon, 19 May 97 13:22:17 -0400

Michael,

Let me try to take a crack at addressing the points you raise in your note.
Scott, Raju, Vinod, and myself actually had a similar discussion a while back
on pretty much this topic.

>    times must pass before the next packet can start arrival.

There are some differences between the "maximum transmission rate"
of RFC1363 and the peak data rate.  One of the motivation of the
"maximum transmission rate" of RFC1363 was to limit the size of the
maximum burst that could be injected in the network (p. 7 of RFC1363):

      "The maximum transmission rate limits how fast packets may be sent
      back to back from the host.  Consider that if the token bucket is
      full, it is possible for the flow to send a series of back-to-back
      packets equal to the size of the token bucket.  If the token
      bucket size is large, this back-to-back run may be long enough to
      significantly inhibit multiplexing."

In order to avoid this problem, RFC1363 recommended (again, see p. 7):

      "To limit this effect, the maximum transmission rate bounds how
      fast successive packets may be placed on the network."

As you pointed out, this amounts to enforcing a minimum spacing between
consecutive packets.

The "peak data rate" of the Int-Serv specs is similar but slightly
different because of the use of the maximum datagram size (M) in 
identifying a conformant packet stream.  Specifically, a packet stream
is deemed conformant if (e.g., see p. 9 of GS draft):

   "the amount of data sent
   cannot exceed M+min[pT, rT+b-M], where r and b are the token bucket
   parameters, M is the maximum datagram size, and T is the length of
   the time period"

As you can see from the above, the spec states that you can only send
at the peak data rate an amount of data equal to at most M bits, a maximum size
datagram.  After that, the term (rT+b-M) kicks in and imposes that you
wait (to remain conformant) before sending more data.  The difference
with RFC1363 is in terms of what you MUST do to remain conformant, and in
particular what it implies for packet spacing (more on this below).

>    rate somehow have to manage its minimum packet spacing?

Answer is yes and no.  The only requirement (for conformance) is that the
amount of data injected into the network always be upper bounded by
M+min[pT, rT+b-M].  If you just sent a packet of size M, and your next
packet is of size L, this then means that you have to wait for L/p before you 
can send it, so here you are imposing a certain minimum spacing between packets.  
On the other hand, if you just sent a packet of size L1 and the next one is of 
size L2, where L1+L2<=M, then you can proceed with the transmission of the second 
packet without any delay, i.e., there is no requirement for a minimum gap
between the two packets are the resulting stream is conformant.

From an implementation point of view, the difference between the above
operation and what RFC1363 described is in how the "token bucket" used
to control the maximum/peak rate operates.  Specifically, RFC1363 states (p.7):

      "One can think of the maximum transmission rate control as being a
      form of a leaky bucket.  When a packet is sent, a number of
      credits equal to the size of the packet is placed into an empty
      bucket, which drains credits at the maximum transmission rate.  No
      more packets may be sent until the bucket has emptied again."

So, here you have a variable size bucket which must be empty for the
next packet transmission to proceed. 

On the other hand, in order to conform with the traffic envelope of the
Int-Serv specs, the following token bucket is used:

      "Peak data rate control is achieved using a token bucket of size
      M, the maximum datagram size, which is initialized to a full bucket.
      Before transmitting a packet of size L, at least L tokens/credits
      must be present in the token bucket, and these credits are removed
      from the bucket upon transmission of the packet.  Tokens/credits
      accumulate in the bucket at the peak data rate, up to a maximum
      number of M credits."

The difference is that you have a bucket of fixed size M, and there has 
to be enough tokens/credits in the bucket for you to be able to transmit
a packet.  

>    somehow have to police minimum packet inter-arrival times?
        
A network element *inside* the network must not do policing (see pp. 9-10
of the GS specs).  However, it can do *reshaping* of the packet stream 
as this wont affect the delay bound (as a matter of fact, you can even
reshape to a peak data rate equal to the requested service rate R as this
wont affect the bound either).

At the edge of the network, you only need to police according to the
above traffic conformance rule, i.e., don't need to enforce a minimum
packet inter-arrival time unless it is required to conform to the
traffic envelope M+min[pT, rT+b-M].

Hope this helps clarifies things.

Roch

---

From: Francesco Potorti` <[email-masked]>
Date: Thu, 3 Jul 97 13:03 MET

Well, sorry for the delay, I am going to comment on a message more
than two weeks old.

   [...] a packet stream is deemed conformant if (e.g., see p. 9 of GS
   draft): [in the new draft, it is on page 10]
   
      "the amount of data sent cannot exceed M+min[pT, rT+b-M], where
      r and b are the token bucket parameters, M is the maximum
      datagram size, and T is the length of the time period"
   
   As you can see from the above, the spec states that you can only
   send at the peak data rate an amount of data equal to at most M
   bits, a maximum size datagram.  After that, the term (rT+b-M) kicks
   in and imposes that you wait (to remain conformant) before sending
   more data.

Perhaps I am missing something here.  What I see is that you can send
at any rate up to M bits, then you can send at peak rate (p) until you
meet the rT+b constraint.  This happens where the two straight lines
M+pT and b+rT cross, that is at the instant (b-M)/(p-r).

So you can send up to M bits at any rate, then up to  p(b-M)/(p-r)
bits at rate p, then any number of bits at rate r.

Where am I wrong?

-- 
Francesco Potorti` (researcher)        Voice:    +39-50-593203
Computer Network Division              Operator: +39-50-593211
CNUCE-CNR, Via Santa Maria 36          Fax:      +39-50-904052
56126 Pisa - Italy                     Email:    [email-masked]

---

From: Roch Guerin <[email-masked]>
Date: Thu, 03 Jul 97 07:51:48 -0400

>Well, sorry for the delay, I am going to comment on a message more

Think it's more like 1.5 months, but that's ok ;-)

>M+pT and b+rT cross, that is at the instant (b-M)/(p-r).

Indeed, my explanation got mixed up there, although the details that
follow it in the original note are correct and clarify what was meant.

As you point out, what you have is something that lets you send up
to M bits (the max packet size) at any rate.  That's because it
should be legal to send a packet (all of its bits) at, say, OC-12
rate even if the flow has advertised a 10Mbps peak rate (it's attached
to an E/N).  As is mentioned in the original note, this can be viewed
as having another token bucket of size M that you fill with a token
rate equal to the peak rate.  So, in the case where you have just 
sent a packet of max size M, that bucket is empty, so that you *may*
need to wait to send the next packet.  How long you need to wait is
a function of the size of the packet and the *speed* at which you want
to send it, i.e., a function of the speed of the interface you are
attached to.  Specifically, if you are going to sent it at OC-12
speed because that's the speed of the wire you are attached to, then
you essentially have to wait for L/p where L is the size of the packet
(here I'm ignoring that you can start a tad earlier as you can get a
few more tokens within the time it takes to send the packet at OC-12
rate).  Now if your interface is running at the same speed as your
peak rate, then you can start sending the next packet immediately as 
you'll be getting tokens as fast as you are sending bits (I'm assuming 
you still have tokens in the other bucket).

>bits at rate p, then any number of bits at rate r.

Correct, but practically you have to factor in the speed of your
interface to determine when you can let packets go out.  If the
interface speed is p, then you can indeed send M+ p(b-M)/(p-r) bits
without interruption.  If the interface speed is much higher, you
need to make sure you have enough peak rate "tokens" before blasting
the next packet.

Hope this clarifies things and sorry for the confusion the earlier
note may have caused.  It was assuming that you had an interface 
running at a speed much faster than p, so that you could not keep
transmitting after sending the first M bits.

Roch