Subject: Re: AAP: Chattiness of protocol

From: Steve Hanna <[email-masked]>
Date: Wed, 20 Sep 2000 14:20:36 -0400

Thomas Narten wrote:
> This protocol seems fairly "chatty" to me, and I wonder how well it
> will scale in practice.

AAP is a soft-state protocol and a particularly chatty one, as you note.

The primary reason to provide such frequent state updates was to allow
new MAASs to quickly learn the state of the network. With AIU messages
sent every 30 seconds [REPEAT-INTERVAL], a new MAAS is required to wait
at least 150 seconds [STARTUP-WAIT] before allocating or preallocating
addresses. This ensures that a few dropped packets won't cause the
server to allocate addresses that are already in use. Increasing
[REPEAT-INTERVAL] would require a corresponding increase in
[STARTUP-WAIT], increasing startup time for MAASs.

I wrote a scaling analysis for draft-ietf-malloc-aap-03.txt, which I
have attached. The conclusion of this analysis was that because of the
chatty nature of AAP, each allocation scope should have no more than 10
or 20 MAASs (to keep bandwidth usage to 50-110Kbps). Also, AAP should
not be used over expensive or bandwidth-constrained links. In such a
case, it is better to subdivide the allocation domain and use an
interdomain protocol such as MASC (or manual allocation) across the
expensive link.

We were not able to reach working group consensus on this scaling
analysis, so it was removed from draft-ietf-malloc-aap-04.txt. However,
we did include a statement in section 3.1 saying:

   Any host that does not support a client-server protocol such as
   MADCAP SHOULD NOT operate as a MAAS for a given scope if a MADCAP
   server is available serving that scope. For scopes larger than
   Local scope, a host that does not support a client-server protocol
   such as MADCAP SHOULD NOT operate as a MAAS even if there is no
   MADCAP server available serving that scope. These behaviors may be
   overridden by configuration.

As for encouraging preallocation, section 2.2 says you SHOULD
preallocate enough addresses to span a network partition.

Perhaps we need to add a section highlighting the scaling issues related
to AAP. And beef up the SHOULDs listed above to be MUSTs. Alternative
suggestions are certainly welcome.

Thanks,

Steve

> 
> Things to note:
> 
> 0) All MAAS messages are multicast to a multicast group, so they are
>    transmitted throughout a administrative network.
> 
> 1) All MAASes send periodic multicast AIU messages every 30
>    seconds. This is to cover the entire state of the Allocation
>    Record (I believe).
> 
> 2) Whenever a MAAS allocates an address (e.g., from its preallocated
>    set), it immediately sends out an AIU for those addresses,
>    following up with retransmissions for reliability.
> 
> 3) For non-preallocated addresses, a MAAS sends sequence of ACLM
>    messages (including retransmissions for reliability) when a request
>    to allocate an address is made.
> 
> Result: for a moderately large site, it seems like the protocol could
> generate quite a lot of traffic. This especially true if a large
> number of addresses are allocated. I have concerns as to how large an
> environment this will scale to.
> 
> Given the time scales involved (shouldn't addresses be allocated for
> relatively long periods of time?), it seems like the protocol could
> relax some of its timing constraints, especially with regards to
> periodic multicast. Or to delay sending out AIU for pre-allocated
> addresses in order to batch them up.
> 
> It also seems like the model could do more to encourage
> pre-allocation, so that becomes the normal way to assign
> addresses. Right now, I don't read the spec as suggesting this is
> required.
> 
> Finally, what size of environment is this protocol expected to scale
> to? Is their consensus that the protocol will do so?
> 
> Thomas

---

From: Steve Hanna <[email-masked]>
Date: Wed, 20 Sep 2000 14:32:55 -0400

I forgot to include the scaling analysis from
draft-ietf-malloc-aap-03.txt. Here it is:

6 Scaling Analysis

   Because AAP is a peer-to-peer multicast protocol, it is especially
   important to analyze its behavior with a large number of
   participants.  Normally, only one Prefix Coordinator is active. So
   the primary concern is large numbers of MAAS's.

   Unless otherwise specified, calculations in this section will assume
   that there are m MAAS's, communicating across a network with a
   typical round-trip time of 200ms. We will also assume that each AAP
   packet is 100 bytes long. These are pessimistic assumptions, but not
   outrageously so.

   This analysis only examines traffic for a single scope. Results for
   multiple scopes should scale in a linear fashion. However, it should
   be noted that if several scopes share an allocation domain, all AAP
   traffic for those scopes will be sent on a single scope-relative
   multicast address (the AAP address for that domain). This may cause
   some MAAS's to receive traffic that they are not interested in, if
   they are not interested in all scopes sharing that domain. These
   packets will be dropped, but may have a performance impact.

6.1 Steady-State Traffic

   First, let's look at steady-state traffic. A MAAS that has not
   allocated or preallocated any addresses does not normally send any
   packets (except for defending the claims of others and ANA and ASRP
   packets, all of which are rare). However, let's make a worst-case
   assumption that all MAAS's have allocated and preallocated some
   addresses. In that case, the traffic caused by steady-state AIU and
   AITU messages will be:

             2*m
       ----------------- packets per second
       [REPEAT-INTERVAL]

Handley and Hanna                                              [Page 31]

Internet Draft        draft-ietf-malloc-aap-03.txt            March 2000

       and

           2*m*8*100
       ----------------- bits per second
       [REPEAT-INTERVAL]

   With m=10 and the recommended value for [REPEAT-INTERVAL], this is
   about m=1000, it is 67 packets per second and 56000 bits per second.

6.2 Peak Traffic

   Peak traffic depends on many variables. However, we might assume a
   worst-case scenario where all MAAS's begin to allocate addresses
   simultaneously. This might be caused by some externally synchronized
   special event, such as a news event or an advertising campaign.  It
   should not be caused by a power failure and subsequent synchronized
   power restoration, since the MAAS's must all have stable storage that
   maintains their allocations across power losses. In addition, it
   should be noted that the MAAS's should have some addresses
   preallocated to handle surges in demand. So this is a somewhat
   unlikely scenario. But let's look at the worst case.

   All MAAS's will begin with an initial delay between [STARTUP-WAIT]
   and [STARTUP-WAIT]*1.3. After this delay, the MAAS's will select the
   addresses that they want to allocate (or preallocate) and each MAAS
   will send an ACLM message, resending this message after [RESEND-
   WAIT], then [RESEND-WAIT]*2, and so on until the Claim Timer expires,
   [ANNOUNCE-WAIT] after the initial message was sent (unless a
   collision occurs).

   With recommended values for the timers (assuming no collisions
   occur), the total traffic sent during this burst of announcements
   will be 4*m packets composed of 4*m*8*100 bits. This traffic will be
   probably be spread out over an interval of [STARTUP-WAIT]*.3,
   providing an average bit rate of:

             4*m
       ----------------- packets per second
       [STARTUP-WAIT]*.3

       and

          4*m*8*100
       ----------------- bits per second
       [STARTUP-WAIT]*.3

   With m=10 and the recommended value for [STARTUP-WAIT], this is about
   m=1000, it is 80 packets per second and 64,000 bits per second.

Handley and Hanna                                              [Page 32]

Internet Draft        draft-ietf-malloc-aap-03.txt            March 2000

   Of course, this is just the average rate. There is a reasonable
   probability that several MAAS's will choose similar values for their
   Startup Timers and end up sending their ACLM messages very close
   together.  And it could even happen that all MAAS's would send their
   ACLM messages simultaneously. But that is exceedingly unlikely.

6.3 Probability of Collision

   One interesting statistic to examine is the probability of collision
   (two MAAS's allocating the same address). Unless MAAS's are unstable,
   the network is partitioned for a significant period of time, or the
   recommendations of section 2.2 are not followed, the only chance for
   a collision should be excessive packet loss.

   When allocating an address with the recommended timers, a MAAS will
   send out four (4) ACLM messages over an interval of ten (10) seconds
   before it considers the address allocated. If another MAAS chooses
   the same address at the same time, it should receive one of these
   ACLM messages before its Claim Timer expires. If the probability of
   packet loss is p, the probability of losing all four of these
   messages is p^4. With 10% packet loss, this indicates only one
   collision in 10,000 instances of simultaneously allocating the same
   address.

   Of course, a higher rate of packet loss would cause a higher
   probability of collision. But the chances of two MAAS's
   simultaneously allocating the same address should be slim unless
   there are very few free addresses.

6.4 Claim Defense Traffic

   When a MAAS sends an ACLM or AITU message with an address that has
   already beeen allocated by someone else, this causes other MAAS's to
   set an Allocation Defense timer.

   If the MAAS that allocated the address is present, it will set its
   timer to 0 and immediately send an AIU message to defend its
   allocation and it will follow this up with several more AIU messages
   at increasing intervals.  The other MAAS's will observe these AIU
   messages and reset their Allocation Defense timers to higher values.
   This avoids storms of packets defending the address.

   However, if the MAAS that allocated the address is not present, the
   MAAS's that have set timers are at substantial risk of causing a
   storm. This is why the Allocation Defense timer is randomized. MAAS's
   that choose a large timer value will see AIU messages from others
   first and suppress their own AIU messages.

Handley and Hanna                                              [Page 33]

Internet Draft        draft-ietf-malloc-aap-03.txt            March 2000

   However, if several MAAS's choose similar small timer values,
   multiple AIU messages will be sent. The probability that a MAAS will
   choose a timer less than 1/2 RTT after the lowest timer value chosen
   is:

                            RTT/2
        p1 = 1 - (1 - (---------------))^(m-2)
                       [RESEND-WAIT]*6

   With m=10, RTT=200ms, and [RESEND-WAIT] = 1 second (the recommended
   value), p1 is .13. With m=100, p1 is .81. And with m=1000, p1 is very
   close to 1.  In fact, with m=100 there is a 10% chance that 12 AIU
   messages will be sent before they are suppressed (all during a 100ms
   period). There is even a 1% chance that 23 AIU messages will be sent
   during this period. This storm could overwhelm network resources or
   hosts listening to the AAP group.

   One way to solve this problem would be to use an exponential
   distribution for the random timers. But even this will not provide a
   complete solution and it adds complexity to AAP implementations. A
   simpler solution is to adopt recommendations to ensure that no more
   than 10 or at most 20 MAAS's participate in AAP protocol exchanges
   for a given scope. With m=20, there is less than a .5% chance that 5
   or more AIU messages will be sent before suppression kicks in and a 1
   in 200,000 chance that 10 or more messages will be sent. And under no
   circumstances would more than 19 messages be sent!

6.5 Conclusion

   Clearly, it is important to minimize the number of MAAS's speaking
   AAP within an allocation domain. A limit of ten servers is reasonable
   in most cases. That is why section 3.1 requires that only MADCAP
   servers can operate as a MAAS if a MADCAP server is available and
   also requires that only MADCAP servers operate as MAAS's for scopes
   larger than Local scope.

   Since AAP is a somewhat "chatty" protocol, it is not recommended for
   use across when the network connecting the MAAS's is expensive or
   bandwidth-constrained. In such scenarios, it may be better to
   subdivide the allocation domain, using an interdomain protocol or
   mechanism to communicate between the domains.