v6ops B. Dickson Internet-Draft Afilias Canada, Inc Expires: August 9, 2008 February 6, 2008 A Survey and Analysis of Address Allocation Strategies for IPv4 and IPv6 draft-dickson-v6ops-assignment-00 Status of this Memo By submitting this Internet-Draft, each author represents that any applicable patent or other IPR claims of which he or she is aware have been or will be disclosed, and any of which he or she becomes aware will be disclosed, in accordance with Section 6 of BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet- Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt. The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. This Internet-Draft will expire on August 9, 2008. Copyright Notice Copyright (C) The IETF Trust (2008). Dickson Expires August 9, 2008 [Page 1] Internet-Draft IP address assignment strategies February 2008 Abstract This Internet Draft describes, analyzes, and compares different strategies for allocating addresses, in a way that can be generalized for any power-of-two sized, binary address space. One such strategy is proposed as being "optimal", when viewed from the perspective of space-packing efficiency. This Draft recommends use of this technique as a "Best Current Practice", for both IPv4 and IPv6 address allocations. Dickson Expires August 9, 2008 [Page 2] Internet-Draft IP address assignment strategies February 2008 Author's Note This Internet Draft is intended to result in this draft or a related draft(s) being placed on the Informational Track for v6ops. The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [2] Table of Contents 1. Background . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2. Scaling problem examples . . . . . . . . . . . . . . . . . . . 5 3. Address structures . . . . . . . . . . . . . . . . . . . . . . 6 4. Assignment Techniques . . . . . . . . . . . . . . . . . . . . 7 5. Best Fit - Details and Example . . . . . . . . . . . . . . . . 8 6. Security Considerations . . . . . . . . . . . . . . . . . . . 9 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 10 8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 11 9. Informative References . . . . . . . . . . . . . . . . . . . . 12 Appendix A. Appendix of FIXME references . . . . . . . . . . . . 13 Appendix B. Allocation Technique Examples . . . . . . . . . . . . 14 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 17 Intellectual Property and Copyright Statements . . . . . . . . . . 18 Dickson Expires August 9, 2008 [Page 3] Internet-Draft IP address assignment strategies February 2008 1. Background In the early days of the Internet, IP addresses were "classful", meaning the size of the prefix was determined by its location in the address space. Subnetting these classful blocks was frequently done, mostly in an ad-hoc manner. When Classless Inter-Domain Routing (CIDR) replaced classful, the Regional Internet Registries - who were given the task of allocating address space - started to track usage. Additional address space was allocated only if a reasonable level of efficiency in assignments was achieved. However, the process of assignments was still piece-meal and largely ad-hoc or occassionally automated with simple tools. With the dawn of widespread and large- scale deployment of IPv6, there is a new opportunity to improve on the internal assignment techiques used by ISPs. Dickson Expires August 9, 2008 [Page 4] Internet-Draft IP address assignment strategies February 2008 2. Scaling problem examples The problem space for address assignments is a classical triangle: Efficiency (the packing problem): Efficiency is measured in terms of availability of unused space. Inefficient use is characterized by fragmentation of unused space. Optimal efficiency is achieved if none of the unused block sizes could be merged, regardless of location in the binary tree. Expansion (the reservation problem): Expansion is the reservation of unused space adjacent to used space. A block expands when it gets merged with unused space adjacent to it. Example: Used block FEC0::2:0/112 merges with unused block FEC0::3:0/112 to become used block FEC0::2:0/111. Existence (the renumbering problem) As soon as space is assigned, the recipient becomes a ticking time bomb. It must be presumed that their network is growing, and at some point will need more space. The recipient will not want to renumber an existing assignment, in order to receive a new assignment. The more room is reserved for growth, the less is available for new assignments, and the lower the apparent global efficiency. This is a zero-sum game, in a finite space. However, the risk-reward, or rather cost-pain, equation pits the assignee against the assigner: any improvement in efficiency which requires a recipient to renumber will face vociferous opposition. Dickson Expires August 9, 2008 [Page 5] Internet-Draft IP address assignment strategies February 2008 3. Address structures Both IPv4 and IPv6 address space have the same properties. They are binary addressing schemes. Their respective routing tables use a binary tree (at least conceptually), and walk this tree comparing an address against the routing table until the longest match is found. This means that routes need to be sized to exactly a power of two in size, and assignments (which are the prerequisites of routes) also are powers-of-two in size. Since these properties are the same, we can consider just the generalized problem, involving powers-of-two hierarchies, when comparing methods of assigning address space. Dickson Expires August 9, 2008 [Page 6] Internet-Draft IP address assignment strategies February 2008 4. Assignment Techniques There are a number of general techniques for assignment of address space. Each have pros and cons, related to efficiency, expansion, and renumbering. Variants on each can achieve some compromise in the secondary areas, in addition to the primary benefit of the technique. Sequential Block This technique breaks a large block into smaller blocks, and assigns prefixes of a given size all out of one sub- block, in a sequential fashion. Variants make assignments paired with reserverations ajacent in the same block, by effectively increasing the size of assignment itself. While simple to implement, this technique is neither terribly efficient, nor very flexible for growth. Bisection This technique initially reserves the whole space for the first recipient. Thereafter, each new recipient is assigned space by splitting, or bisecting, the space reserved for one recipient, reserving half for the original recipient and the other half for the new recipient. Growth occurs within a recipient's reserved space. This technique achieves expansion at the cost of efficiency. Under bisection, unused space is *maximally* fragmented. Variants may make allowances in bisection algorithm based on size of initial assignment. Another problem with bisection is, it is non-deterministic, in that it is sensitive to the sequence in which requests are recieved - particularly when balancing new assignment requests against assignment increases due to growth. Best Fit It uses the smallest unused block big enough to hold the requested assignment. It then repeatedly bisects that block until the exact fit for the new assignment is achieved. If the smallest is the right size, no bisection is necessary. This technique guarantees no aggregation of unused space is possible after an assignment (if it wasn't possible to aggregate before assignment). It starts with a completely aggregated empty block. Thus, it will always achieve optimal efficiency. It also exhibits the characteristic of not being order-sensitive. Regardless of the sequence of assignments, the same set of empty blocks will result - meaning the measure of efficiency does not depend on order. In an apples-to-apples comparision, "Best Fit" will have the best efficiency. Other techniques may equal its efficiency, but it is not possible to improve on it. Dickson Expires August 9, 2008 [Page 7] Internet-Draft IP address assignment strategies February 2008 5. Best Fit - Details and Example The strategy "Best Fit", works by minimizing the sizes of unused blocks. When possible, exact matches are used, meaning the unused block is the same size as the requested block. When no exact match is found, the smallest block larger than the request, is the block used for splitting into smaller blocks. Each time the larger block is split, only one of the two halves are subsequently re-split. This is repeated until the match is exact. For example, consider a single empty block of size /N, and a request for size M (M > N). /N is split, producing empty blocks /N+1, /N+2, /N+3,... /M, and a second /M. The second /M is assigned in response to the request. If a subsequent request is made for /R, there are three possiblities: R == M In this case, there is an exact match, of size /M, and no splitting occurs. The result does not differ depending on the order of the requests (since the requested sizes are identical.) N < R < M In this case, there is an exact match, of size /R, and no splitting occurs. The set of empty blocks, sorted by size, is /N+1 through /R-1, /R+1 through /M. R > M In this case, there is no exact match. The smallest empty block is /M, which is then split. The set of empty blocks, sorted by size, is /N+1 through /M-1, /M+1 through /R. The results for the cases "R < M" and "R > M", are symmetric. If we swap which is done first, the resulting sets of empty blocks are the same. By the mathematical proof method of induction, we can see that in all cases, there will never be a case where two members of the set of empty blocks will be the same size, and that the results are not order dependent. This means that "Best Fit" is indeed completely optimal when space efficiency is considered. Dickson Expires August 9, 2008 [Page 8] Internet-Draft IP address assignment strategies February 2008 6. Security Considerations Owing to the abstract nature of this document, there are no security considerations. Dickson Expires August 9, 2008 [Page 9] Internet-Draft IP address assignment strategies February 2008 7. IANA Considerations This document has no actions for IANA. Dickson Expires August 9, 2008 [Page 10] Internet-Draft IP address assignment strategies February 2008 8. Acknowledgements The author wishes to acknowledge the helpful guidance of Joe Abley, Brian Haberman, and Jari Arrko. The author also thanks Marla Azinger, Scott Leibrand, Bob Hinden, and Iljitsch van Beijnum. Dickson Expires August 9, 2008 [Page 11] Internet-Draft IP address assignment strategies February 2008 9. Informative References [1] Postel, J., "Internet Protocol", STD 5, RFC 791, September 1981. [2] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. [3] Fuller, V., Li, T., Yu, J., and K. Varadhan, "Classless Inter- Domain Routing (CIDR): an Address Assignment and Aggregation Strategy", RFC 1519, September 1993. [4] Hinden, R. and S. Deering, "IP Version 6 Addressing Architecture", RFC 4291, February 2006. Dickson Expires August 9, 2008 [Page 12] Internet-Draft IP address assignment strategies February 2008 Appendix A. Appendix of FIXME references FIXME - change "FRONT" components of references above to real values - ask WG chair, AD, or RFC Editor for help Dickson Expires August 9, 2008 [Page 13] Internet-Draft IP address assignment strategies February 2008 Appendix B. Allocation Technique Examples Using tools which do allocations according to either the "best fit" or "bisection" method, and given an empty block of a specific size, and a sequence of requests for allocations, we can observe the results readily. In the following, the allocations are kept in a file, whose structure is described in the comments block. Comments are preserved at the top. The transaction file is a list of address size requests, and the name to associate to the request. We illustrate several scenarios, using the same set of allocation requests in different sequence. The resulting allocation files are shown at various steps, so the differences between methods and the sensitivity to sequence of transactions is clearer. The resulting allocation block file, shows allocations (and optionally reservations, in the case of the bisection method). Each block has the name assigned to the allocated block, or the empty string indicating unallocated space. (Bisection uses reserved space, and does not have "unallocated" space, per se.) Input Files: Empty allocation file (start from scratch): # File for storing tree of allocations and free blocks # default base is 10 # default arrangement is flat (vs dotted or colon separated hierarchy) # # format of each line is: # network/[reservation-]length[,customer] # # if no [,customer] label exists, the block is available # if [reservation-] is specified, the following are true: # network/length is allocated to customer # network/reservation is tentatively reserved for customer, # but can be bisected universe=/6 0/0 Transaction file containing sequential requests for new allocations: # Set of requests (for batch processing of requests for allocations) # name /size c1 /5 c2 /6 c3 /3 c4 /6 c5 /4 c6 /3 Results for allocation strategy "Bisection": Dickson Expires August 9, 2008 [Page 14] Internet-Draft IP address assignment strategies February 2008 universe=/6 0/3-5,c1 8/3-4,c5 16/3-3,c3 24/3-3,c6 32/2-6,c2 48/2-6,c4 Results for allocation strategy "Best": universe=/6 0/5,c1 2/6,c2 3/6,c4 4/4,c5 8/3,c3 16/3,c6 24/3 32/1 Additional allocations: c7 /2 c8 /3 c9 /3 c10 /3 Results for allocation strategy "Bisection": Unable to allocate prefix size /2 for c7 Unable to allocate prefix size /3 for c10 universe=/6 0/3-5,c1 8/3-4,c5 16/3-3,c3 24/3-3,c6 32/3-6,c2 40/3-3,c8 48/3-6,c4 56/3-3,c9 Results for allocation strategy "Best": universe=/6 0/5,c1 2/6,c2 3/6,c4 4/4,c5 8/3,c3 16/3,c6 24/3,c8 32/2,c7 Dickson Expires August 9, 2008 [Page 15] Internet-Draft IP address assignment strategies February 2008 48/3,c9 56/3,c10 We can see that the requests used up all of the available space, exactly. The strategy "Best" succeeded in using up all the space. The strategy "Bisect" did leave some room for growth for some allocations, but not for others. "Bisect" ultimately fragmented the space too much for allocations that would otherwise have been able to fit. Dickson Expires August 9, 2008 [Page 16] Internet-Draft IP address assignment strategies February 2008 Author's Address Brian Dickson Afilias Canada, Inc 4141 Yonge St, Suite 204 North York, ON M2P 2A8 Canada Email: briand@ca.afilias.info URI: www.afilias.info Dickson Expires August 9, 2008 [Page 17] Internet-Draft IP address assignment strategies February 2008 Full Copyright Statement Copyright (C) The IETF Trust (2008). This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights. This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM 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. Intellectual Property The IETF takes no position regarding the validity or scope of any Intellectual Property Rights or other rights that might be claimed to pertain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; nor does it represent that it has made any independent effort to identify any such rights. Information on the procedures with respect to rights in RFC documents can be found in BCP 78 and BCP 79. Copies of IPR disclosures made to the IETF Secretariat and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementers or users of this specification can be obtained from the IETF on-line IPR repository at http://www.ietf.org/ipr. The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement this standard. Please address the information to the IETF at ietf-ipr@ietf.org. Acknowledgment Funding for the RFC Editor function is provided by the IETF Administrative Support Activity (IASA). Dickson Expires August 9, 2008 [Page 18]