allocated addresses should be aggregatable, the address utilization
should be reasonably high, and the allocation latency to the MAASs
should be shorter than [WAITING_PERIOD] whenever possible.
17.1.1. Prefix Expansion
For ease of implementation and troubleshooting, MASC should use
contiguous masks to specify the address ranges, i.e. prefixes.
(Research indicates that sufficiently good results can be achieved
using contiguous masks only.) The chosen prefixes should be as
expandable as possible. The method used to choose the children sub-
prefixes from the parent's prefix is the so called Reverse Bit
Ordering (idea by Dave Thaler; inspired by Kampai [KAMPAI]). For
example, if the parent's prefix width is four bits, the addresses of
the sub-prefixes are chosen in the following order:
Parent: xxxx
Child A: 0000
Child B: 1000
Child C: 0100
Child D: 1100
If some of the children need to expand their sub-prefix, they try to
double the corresponding sub-prefix starting from the right:
Child A: 000x
Child A: 00xx
Child D: 110x
Child D: 11xx
and so on.
However, because the address ordering is very strict, to reduce the
probability for collision, when a new sub-prefix has to be chosen,
the choice should be random among all candidates with the same
potential for expandability. For example, if the free sub-prefixes
are 01xx, 10xx, 110x, then the new prefix to claim should be chosen
with probability of 50% for 01xx and 50% for 10xx for example.
17.1.2. Reducing Allocation Latency
To reduce the allocation latency, a MASC node uses pre-allocation.
It constantly monitors the demand for addresses from its children (or
MAASs), and predicts what would be the address usage after
[WAITING_PERIOD]. Only if the available addresses will be used up
within [WAITING_PERIOD], a MASC node claims more addresses in
advance.
17.1.3. Address Space Utilization
Because every prefix size is a power of two, if a node tries to
allocate just a single prefix, the utilization at that node (i.e. at
that node's domain) can be as low as 50%. To improve the
utilization, a MASC node can have more than one prefix allocated at a
time (typically, each of them with different size). By using a pre-
allocation and allocating several prefixes of different size (see
below), a MASC node should try to keep its address utilization in the
range 70-90%.
17.1.4. Prefix Selection After Increase of Demand
To additionally reduce the allocation latency by reducing the
probability for collision, and to improve the aggregability of the
allocated addresses, a MASC node carefully chooses the prefixes to
claim. The first prefix is chosen at random among all reasonably
expandable candidates. If a node chooses to allocate another,
smaller prefix, then, instead of doubling the size of the first one
which might reduce significantly the address utilization, a second
"neighbor" prefix is chosen. For example, if prefix 224.0/16 was
already allocated, and the MASC domain needs 256 more addresses, the
second prefix to claim will be 224.1.0/24. If the domain needs more
addresses, the second prefix will eventually grow to 224.1/16, and
then both prefixes can be automatically aggregated into 224.0/15.
Only if 224.0.1/24 could not be allocated, a MASC node will choose
another prefix (eventually random among the unused prefixes).
If the number of allocated prefixes increases above some threshold,
and none of them can be extended when more addresses are needed,
then, to reduce the amount of state, a MASC node should claim a new
larger prefix and should stop re-claiming the older non-expandable
prefixes. Research results show that up to three prefixes per MASC
domain is a reasonable threshold, such that the address utilization
can be in the range 70-90%, and at the same time the prefix flux will
be reasonably low.
17.1.5. Prefix Selection After Decrease of Demand
If the demand for addresses decreases, such that its address space is
under-utilized, a MASC node implicitly returns the unused prefixes
after their lifetimes expire, or re-claims some smaller sub-prefixes.
For example, if prefix 224.0/15 is 50% used by the MAASs and/or
children MASC domains, and the overall utilization is such that
approximately 2^16 (64K) addresses should be returned, a MASC node
should stop reclaiming 224.0/15 and should start reclaiming either
224.0/16 or 224.1/16 (whichever sub-prefix utilization is higher).
17.1.6. Lifetime Extension Algorithm
If the demand for addresses did not decrease, then a MASC node re-
claims the prefixes it has allocated before their lifetime expires.
Each prefix (or sub-prefix if the demand has decreased) should be
re-claimed every 48 hours.
18. APPENDIX B: Strawman Deployment
At the moment of writing, 225.0.0.0-225.255.255.255 is temporarily
allocated to MALLOC. Presumably this block of addresses will be used
for experimental deployment and testing.
If MASC were widely deployed on the Internet, we might expect numbers
similar to the following:
o Initially will have approximately 128 Top-Level Domains
o Assume initially approximately 8192 level-2 MASC domains; on
average, a TLD will have approximately 64 children domains.
o MASC managed global addresses:
The following (large) ranges are not allocated yet (2^N represents
the size of the contiguous mask prefixes):
225.0.0.0 - 231.255.255.255 = 2^26 + 2^25 + 2^24
234.0.0.0 - 238.255.255.255 = 2^25 + 2^25 + 2^24
---------------------------
Total: 12*2^24 addresses
Initially, the range 228.0.0.0 - 231.255.255.255 (4*2^24 = 2^26 =
64M) could be used by MASC as the global addresses pool. The rest
(8*2^24) should be reserved. Part of it could be added later to
MASC, or can be used to enlarge the pool of administratively
scoped addresses (currently 239.X.X.X), or the pool for static
allocation (233.X.X.X).
o If the multicast addresses are evenly distributed, each TLD would
have a maximum of 2^19 (512K) addresses, while each level-2 MASC
domain would have 8192 addresses.
o Initial claim size: 256 addresses/MASC domain
o Could use soft and hard thresholds to specify the maximum amount
of claimed+allocated addresses per domain. For example, trigger a
warning message if claimed+allocated addresses by a domain is >=
1.0*average_assumed_per_domain (a strawman default soft
threshold):
* if a TLD claim+allocation >= 512K
* if a second level MASC domain claim+allocation >= 8K
The hard threshold (for example, 2.0*average_assumed_per_domain)
can be enforced by sending an explicit DENIED message.
The TLDs thresholds (with regard to the claims by the second level
MASC domains) is a private matter and is a part of the particular
TLD policy: the thresholds could be per customer, and the warnings
to the administrators could be a signal that it is time to change
the policy.
o Initial claim lifetime is of the order of 30 days. Prefix
lifetime is periodically (every 48 hours) reclaimed/extended,
unless the prefix is under-utilized (see APPENDIX A). Because the
allocation is demand-driven, the allocated prefix lifetime will be
automatically extended if the MAASs need longer prefix lifetime
(e.g. 3-6 months).
o A level-2 MASC domain could have children (i.e. level-3) MASC
domains.
o If a level-2 or level-3 MASC domain uses less than 128 addresses,
a Layer 2 protocol/mechanism (e.g. AAP) should be run among that
domain and its parent MASC domain.
19. Authors' Addresses
Pavlin Radoslavov
Computer Science Department
University of Southern California/ISI
Los Angeles, CA 90089
USA
EMail: pavlin@catarina.usc.edu
Deborah Estrin
Computer Science Department
University of Southern California/ISI
Los Angeles, CA 90089
USA
EMail: estrin@isi.edu
Ramesh Govindan
University of Southern California/ISI
4676 Admiralty Way
Marina Del Rey, CA 90292
USA
EMail: govindan@isi.edu
Mark Handley
AT&T Center for Internet Research at ISCI (ACIRI)
1947 Center St., Suite 600
Berkeley, CA 94704
USA
EMail: mjh@aciri.org
Satish Kumar
Computer Science Department
University of Southern California/ISI
Los Angeles, CA 90089
USA
EMail: kkumar@usc.edu
David Thaler
Microsoft
One Microsoft Way
Redmond, WA 98052
USA
EMail: dthaler@microsoft.com
20. References
[AAP] Handley, M. and S. Hanna, "Multicast Address
Allocation Protocol (AAP)", Work in Progress.
[API] Finlayson, R., "An Abstract API for Multicast
Address Allocation", RFC2771, February 2000.
[BGMP] Thaler, D., Estrin, D. and D. Meyer, "Border
Gateway Multicast Protocol (BGMP): Protocol
Specification", Work in Progress.
[BGP] Rekhter, Y. and T. Li, "A Border Gateway
Protocol 4 (BGP-4)", RFC1771, March 1995.
[CIDR] Rekhter, Y. and C. Topolcic, "Exchanging
Routing Information Across Provider Boundaries
in the CIDR Environment", RFC1520, September
1993.
[IANA] Reynolds, J. and J. Postel, "Assigned Numbers",
STD 2, RFC1700, October 1994.
[IANA-CONSIDERATIONS] Alvestrand, H. and T. Narten, "Guidelines for
Writing an IANA Considerations Section in
RFCs", BCP 26, RFC2434, October 1998.
[IPSEC] Kent, S. and R. Atkinson, "Security
Architecture for the Internet Protocol", RFC
2401, November 1998.
[KAMPAI] Tsuchiya, P., "Efficient and Flexible
Hierarchical Address Assignment", INET92, June
1992, pp. 441--450.
[MADCAP] Hanna, S., Patel, B. and M. Shah, "Multicast
Address Dynamic Client Allocation Protocol
(MADCAP)", RFC2730, December 1999.
[MALLOC] Thaler, D., Handley, M. and D. Estrin, "The
Internet Multicast Address Allocation
Architecture", RFC2908, September 2000.
[MBGP] Bates, T., Chandra, R., Katz, D. and Y.
Rekhter, "Multiprotocol Extensions for BGP-4",
RFC2283, September 1997.
[MTRACE] Fenner, W., and S. Casner, "A `traceroute'
facility for IP Multicast", Work in Progress.
[MZAP] Handley, M, Thaler, D. and R. Kermode
"Multicast-Scope Zone Announcement Protocol
(MZAP)", RFC2776, February 2000.
[RFC1112] Deering, S., "Host Extensions for IP
Multicasting", STD 5, RFC1112, August 1989.
[RFC2119] Bradner, S., "Key words for use in RFCs to
Indicate Requirement Levels", BCP 14, RFC2119,
March 1997.
[RFC2373] Hinden, R. and S. Deering, "IP Version 6
Addressing Architecture", RFC2373, July 1998.
[RFC2460] Deering, S. and R. Hinden, "Internet Protocol,
Version 6 (IPv6) Specification", RFC2460,
December 1998.
[SCOPE] Meyer, D., "Administratively Scoped IP
Multicast", RFC2365, July 1998.
21. Full Copyright Statement
Copyright (C) The Internet Society (2000). All Rights Reserved.
This document and translations of it may be copied and furnished to
others, and derivative works that comment on or otherwise explain it
or assist in its implementation may be prepared, copied, published
and distributed, in whole or in part, without restriction of any
kind, provided that the above copyright notice and this paragraph are
included on all such copies and derivative works. However, this
document itself may not be modified in any way, such as by removing
the copyright notice or references to the Internet Society or other
Internet organizations, except as needed for the purpose of
developing Internet standards in which case the procedures for
copyrights defined in the Internet Standards process must be
followed, or as required to translate it into languages other than
English.
The limited permissions granted above are perpetual and will not be
revoked by the Internet Society or its successors or assigns.
This document and the information contained herein is provided on an
"AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING
BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION
HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF
MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Acknowledgement
Funding for the RFCEditor function is currently provided by the
Internet Society.