As per Relevance of the word position, we have this rfc below:
Network Working Group P.
Request for Comments: 1219
April 1991
On the Assignment of Subnet
Status Of This
This memo suggests a new procedure for assigning subnet numbers.
of this assignment technique within a network would be a purely
matter, and would not effect other networks. Therefore, the use
these procedures is entirely discretionary
This memo provides information for the Internet community. It
not specify an Internet standard. Distribution of this memo
unlimited
RFC-950 [2] specifies a procedure for subnetting Internet
using a bit-mask. While RFC-950 allows the "ones" in the subnet
to be non-contiguous, RFC-950 recommends that 1) they be contiguous
and 2) that they occupy the most significant bits of the "host"
of the internet address
RFC-950 did not specify whether different subnets of the same
may have different masks. This ambiguity was unfortunate, as
resulted in development of routing protocols that do not
different masks; see e.g., RIP [6]. The Gateway Requirements RFC [7]
settled the issue in favor of allowing different masks, and
future routing protocols may be expected to support this feature
OSPF [3] is an example
The network administrator must of course determine the mask for
subnet. This involves making an estimate of how many hosts
subnet is expected to have. As it is often impossible to predict
large each subnet will grow, inefficient choices are often made,
some subnets under-utilized, and others possibly
renumbering because of exceeded capacity
This memo specifies a procedure for assigning subnet numbers
eliminates the need to estimate subnet size. Essentially, host
(mask = 0) are assigned from the least significant bit
towards the most, and subnet bits (mask = 1) are assigned from
most significant bit working towards the least. As subnets grow
more host bits are assigned. As the number of subnets grows,
subnet bits are assigned. While this process does sometimes
Tsuchiya [Page 1]
RFC 1219 On the Assignment of Subnet Numbers April 1991
in new subnet masks, no host ever need change addresses
This technique is not new, but it is also not widely known, and
less widely implemented. With the development of new
protocols such as OSPF, it is possible to take full advantage of
technique. The purpose of this memo, then, is to make this
widely known, and to specify it exactly
This memo requires no changes to existing Internet standards.
does, however, require that the intra-domain routing protocol
multiple different subnet masks
The author would like to thank Phil Karn, Charles Lynn, Jeff Mogul
and Charles Wolverton for their helpful suggestions. Special
go to Joel Halpern for his painstaking debugging of the
specification and the examples
1.
The Subnetting standard, RFC-950, specifies that the Host part of
formally 2-level Internet address can be divided into two fields
Subnet and Host. This gives the Internet address a third level
hierarchy, and the concomitant firewalls and savings in
overhead. It also introduces increased inefficiency in
allocation of addresses
This inefficiency arises from the fact that the network
typically over-estimates the size (number of hosts) of any
subnetwork, in order to prevent future re-addressing of subnets.
may also occur if the routing protocol being used does not
different length subnets, and the administrator must therefore
every subnet an amount of space equivalent to that received by
largest subnet. (This RFC does not help in the latter case, as
technique herein requires different length subnets.)
The administrative hassle associated with changing the
structure of a network can be considerable. For instance,
the following case. A network has three subnets A, B, and C.
that the lowest significant byte is the host part, and the next
is the subnet part (that is, the mask is 255.255.255.0).
further that A has subnet 1.0, B has subnet 2.0, and C has
3.0.
Now, assume that B grows beyond its allocation of 254 hosts
Ideally, we would like to simply change B's mask without changing
of the host addresses in B. However, the subnets numerically
Tsuchiya [Page 2]
RFC 1219 On the Assignment of Subnet Numbers April 1991
and below B are already taken by A and C. (If say 3.0 was not
by C, B's mask could be changed from 255.0 (ff00) to 254.0 (fe00).
In this case, all of B's existing addresses would still match the
subnet. Indeed, if non-contiguous masks were in use, it might
possible for B to find some other mask bit to change to 0. However
non-contiguous masks are generally not in favor, as they
limitations on certain forwarding table lookup algorithms. Indeed
RFC-950 discourages their use.)
So, the choices available to the network administrator are to 1)
two subnets out of the existing one, or 2) renumber the subnet
that the subnet ends up with a smaller (fewer 1's) mask. Choice 1
can either be accomplished physically or logically.
forming two subnets requires partitioning the subnet and inserting
gateway between the two partitions. For obvious reasons, this is
a desirable course of action. Logically forming two subnets can
done by simply assigning another subnet number (say 4.0) to the
subnet, and assigning host addresses under the new subnet.
result of this logical partition is that the hosts with
subnet numbers will not recognize that the others are on the
subnet, and will send packets to the default gateway rather
directly to the host. In fact, this is not such a bad solution
because assuming that the gateway is capable of recognizing
subnet numbers on the same subnet, the gateway will simply send
host an ICMP Redirect [4], and subsequent packets will go directly
the host [1] (this may not work correctly on all hosts).
If, however, neither choice is acceptable or possible, then
network administrator must assign a new subnet number to B,
renumbering the existing hosts, modifying the Domain Name
entries, and changing any other configuration files that
hardwired addresses for hosts in subnet B
2. A More Flexible and Efficient Technique for Assigning Subnet
In order to help explain the new technique, we shall show what
wrong with what is currently done now. Currently, most subnets
assigned by splitting the host part of the address in two fields;
subnet field and the host field. Mask bits are one for subnet
bits, and 0 for host field bits. (In all of our addresses, the
significant bit (LSB) is on the right, the most significant bit (MSB
is on the left.)
MSB
--------------------------------------
| subnet field | host field |
--------------------------------------
Tsuchiya [Page 3]
RFC 1219 On the Assignment of Subnet Numbers April 1991
The subnet field could be different lengths for different
subnets. For instance, say a network had two large subnets and
rest small subnets (by large subnet we mean a large number of hosts).
Then the network administrator might assign two types of addresses
--------------------------------------
| subnet | host | large
--------------------------------------
--------------------------------------
| subnet | host | small
--------------------------------------
In this case, the full range of subnet numbers would not be
to the small subnets, as the bits in the small subnet that
to those in the large subnet could not have the same values as
in the large subnets. For instance, say that the large subnets
4-bit subnet numbers, and the small subnets had 8-bit subnet numbers
If the large subnets had values 0001 and 0010, then subnet numbers
the range 00010000 to 00101111 could not be assigned to the
subnets, otherwise there will be addresses that would match
subnets
In any event, a network administrator will typically assign values
the two fields in numerical order. For example, within a
subnet, hosts will be numbered 1, 2, 3, etc. Within a given network
subnets will be numbered 1, 2, 3, etc. The result is that
number of bits on the right side of the subnet and host fields
be ones for some hosts and zeros for others, and some number of
on the left side of the subnet and host fields will be zeros for
subnets and hosts. The "all zeros" bits represent room for growth
and the "ones and zeros" bits represent bits already consumed
growth
--------------------------------------
| subnet field | host field |
|-----+-----------+-------+------------|
| | | | |
| 0's | 1's & 0's | 0's | 1's & 0's |
/\ /\
|| ||
subnets can hosts can grow
grow
Now, let's assume that the number of hosts in a certain subnet
to the maximum allowed, but that there is still room in the
field to assign more addresses. We then have the following
Tsuchiya [Page 4]
RFC 1219 On the Assignment of Subnet Numbers April 1991
--------------------------------------
| subnet field | host field |
|-----+-----------+--------------------|
| | | |
| 0's | 1's & 0's | 1's & 0's |
While the host field can no longer grow, there is still room in
address for growth. The problem is that because of where the
areas are situated, the remaining growth has been
reserved for subnets only
What should be done instead is to assign subnet numbers so that
ones start from the left of the subnet field and work right. In
case we get the following
--------------------------------------
| subnet field | host field |
|-----------+-------------+------------|
| | | |
| 1's & 0's | 0's | 1's & 0's |
/\
||
Both hosts and subnets
grow
Now, both hosts and subnets individually have considerably
growing space than before, although the combined growing space is
same. Since one can rarely predict how many hosts might end up in
subnet, or how many subnets there might eventually be,
arrangement allows for the maximum flexibility in growth
Actually, the previous figure is misleading. The boundary
the host and subnet fields is being shown in the middle of the
area. However, the boundary could exist anywhere within the
area. Note that it is the mask itself that determines where
boundary is. Ones in the mask indicate subnet bits, and
indicate host bits. We will show later that in fact the
should lie somewhere in the middle. Putting it there minimizes
number of times that the masks must be changed in hosts
2.1 Specification of the New
Having given the appropriate explanatory material, we can now
the procedure for subnet number assignment. We need the
definitions
Host-assigned Bits (h-bits): These are the bits, contiguous
Tsuchiya [Page 5]
RFC 1219 On the Assignment of Subnet Numbers April 1991
the right, for which host values, within a given subnet,
both ones and zeros. Different subnets may have different h-bits
Subnet-assigned Bits (s-bits): These are the bits, contiguous
the left, which 1) are not h-bits, AND 2) are required
distinguish one subnet from another, AND 3) include all
to the left of and including the right-most one. Notice
different subnets may have different s-bits
Growth Bits (g-bits): These are the "all zeros" bits in
the h-bits and s-bits
s-mask: For a given subnet, the mask whereby all s-bits are one
and all g-bits and h-bits are zero
g-mask: For a given subnet, the mask whereby all s-bits and g-
are one, and all h-bits are zero
Subnet Field: These are the one bits in the subnet mask (
defined in RFC-950). These bits are on the left. The
field must at least include all of the s-bits, and
additionally include some or all of the g-bits
Host Field: These are the zero bits in the subnet mask
These bits are on the right. The host field must at
include all of the h-bits, and may additionally include
or all of the g-bits
Mirror-image Counting: Normal counting, in binary, causes
bits to start at the right and work left. This is how
values are assigned. However, for subnet assignment, we
the one bits to start at the left and work right. This
is the mirror image of normal counting, where the MSB is
with the LSB, the second MSB is swapped with the second LSB,
so on. So, where normal counting is
0 (reserved to mean "this host")
01
10
011
100
101
:
:
11...1110
11...1111 (reserved to mean "all hosts")
and so on, Mirror-image, or MI counting, is
Tsuchiya [Page 6]
RFC 1219 On the Assignment of Subnet Numbers April 1991
0 (reserved to mean "this subnet")
10
01
110
001
101
:
:
011...11
111...11 (reserved to mean "all subnets")
and so on. If the current MI counting value is, say, 001,
the "next" MI value is 101, and the "previous" MI value is 11.
Now we can specify the algorithm. We have the following functions
Initialize(), AddSubnet(), RemoveSubnet(subnet#), AddHost(subnet#),
and RemoveHost(subnet#,host#).
Notice that the algorithm is described as though one state machine
executing it. In reality, there may be a root Address
(RootAA) that assigns subnet numbers (Initialize, AddSubnet,
RemoveSubnet), and subnet AA, that assign host numbers within
subnet (AddHost and RemoveHost). While in general the AAs can
independently, there are two cases where "coordination" is
between the rootAA and a subnetAA. These are the cases where
the rootAA or the subnetAA "grabs" the last growth bit (in the
case because another subnet has been added, and in the latter
another host has been added). Since it is impossible for the
and a subnetAA to simultaneously grab the last growth bit, either
or the other must do it
Finally, note that the following C language style notation is used
& bit-wise AND
== is equal
!= is not equal
x-mask(X) the x-mask of X (where x is s or g
Initialize():
Assign the first subnet value to be 0 (the value reserved to
"this subnet"). This is not assigned to any real subnet
AddSubnet():
1. Find the lowest non-zero (in MI counting) non-assigned
number S such that (S & g-mask(Y)) != (Y & g-mask(Y)) for
existing subnet numbers Y, (Y != S).
2. If all bits in S from the rightmost one bit left are ones
then label all bits to the left of and including one
position to the right of the rightmost one bit in S to
Tsuchiya [Page 7]
RFC 1219 On the Assignment of Subnet Numbers April 1991
s-bits. Else, label all bits to the left of and including
rightmost one bit in S to be s-bits. This prevents the "
ones" value (which is the "all subnets" broadcast address
from being assigned to a subnet. (Since no hosts have
added, the rightmost one bit is a subnet bit.)
3. Label all other bits in the address to be g-bits. (
address, we mean that part of the IP address not
the network number.)
4. Set the subnet mask to include at least all s-bits,
optionally some g-bits. The subnet mask must be contiguous
(Section 2.2 discusses the pros and cons of choosing a mask.)
5. For all existing subnet numbers Y (Y != S):
51. If (S & s-mask(Y)) == (Y & s-mask(Y)), then
511. Change the leftmost g-bit of Y to an s-bit.
the rootAA and YAA (the address authority for Y)
separate AAs, then the YAA must be informed of
change of bit status. If this is the last g-bit
then this change must be coordinated with YAA
512. Expand the subnet mask for all hosts in Y
necessary (that is, if the subnet mask no
includes all s-bits).
RemoveSubnet(S):
1. Consider B to be the bit position of the rightmost s-bit in S
2. Remove S
3. For all existing subnet numbers Y
31. If the bit in position B is not an s-bit, or if the
in bit position B is a one, or if the bit in bit
B is a zero and all bits to the left of bit position
are ones, then do nothing (skip steps 32 and 33).
32. Change the s-bit in position B to a g-bit
33. If for any other existing subnet numbers
(X & s-mask(Y)) == (Y & s-mask(Y)), then change
g-bit in position B back into an s-bit for Y. Else
inform YAA that of the change of bit status
AddHost(S):
1. Create an address A consisting of subnet number S
with zeros
2. Assign to A the same h-bits, g-bits, and s-bits as
other host addresses
3. Find the lowest non-zero (using normal counting) non-
host number H
4. If all bits from the leftmost one bit to bit position 0
ones, then execute steps 5 and 6 using bit position B
one bit position to the left of the leftmost one bit in H
Else, execute steps 5 and 6 with bit position B
the leftmost one bit in H. This prevents the "all ones"
Tsuchiya [Page 8]
RFC 1219 On the Assignment of Subnet Numbers April 1991
(which is the "all hosts" broadcast address) from
assigned to a host
5. If bit position B is an s-bit, then the host cannot be added
Skip the remaining steps
6. If bit position B is a g-bit
61. Change the g-bit to an h-bit for all hosts in S.
that if this is the last g-bit, this change must
coordinated with the address authority assigning
numbers (see section 2.2).
62. Modify the subnet mask in all hosts if necessary
7. Create a new address A consisting of S concatenated with
8. Assign A to the host
RemoveHost(S,H):
1. Remove H
2. If for all remaining host numbers in S, the value of the
position of the leftmost h-bit is zero, and there is a zero
at least one of the bit positions to the right of the
h-bit, then for all hosts change the leftmost h-bit into
g-bit
It is worth noting here that this technique is a 2-level subset
the more general n-level kampai addressing [5]. The
difference here is that n-level kampai results in non-
masks, while 2-level does not. In the description of
addressing in [5], g-bits are called a-bits, h-bits are
g-bits, and s-bits are called i-bits
2.2 An
For this example, we assume a class C network, so we will only
to work with 8 bits. We start with 3 subnets, A, B, and C.
nomenclature is h for h-bit and g for g-bit. Note that h-bits can
one or zero, but g-bits are all zero. The remaining bits are s-bits
but are shown as 1's and 0's according to the subnet
assignment. The space is just to make the addresses and masks
to read. Finally, we number our bits 0 to 7 from right to left
shown below
Subnet Address
A 10gg ghhh 1111 0000
B 01gg ghhh 1111 0000
C 110g ghhh 1111 0000
bit 7 bit 0
We see that each subnet has at most 6 hosts (because of the three h
bits). Notice that we have chosen the masks so that there is
for growth in both hosts and subnets without requiring a mask change
Tsuchiya [Page 9]
RFC 1219 On the Assignment of Subnet Numbers April 1991
However, we have generally allowed for more growth in subnets than
hosts because adding new subnets can cause mask changes in
subnets, while adding new hosts in a subnet only causes that subnet'
mask to change
Further, if a subnet's mask must change, but not all hosts
reconfigured at the same time, then it is less damaging if the
yet reconfigured hosts have too large a mask (too many ones) than
they have too small a mask. This is because with too large a mask,
host may think that another host which is in fact on the subnet is
another subnet. In this case, the host will send packets to
gateway, and will be redirected to the host
However, with too small a mask, a host may think that another
which is in fact not on the subnet is on the subnet, and will ARP
that host but receive no reply. (Note that broadcasts may fail
all masks do not match.)
Finally, notice that subnet C requires three s-bits instead of
two. This is because with just two, the subnet address of C could
"11" (rather than "110"), which is a broadcast value. Step 2
AddSubnet checks for this case
Now, a fourth subnet, D, also with 6 hosts, is added. We get
Subnet Addr
A 10gg ghhh 1111 0000
B 01gg ghhh 1111 0000
C 110g ghhh 1111 0000
D 001g ghhh 1111 0000
Notice that none of the original subnets required a change in any
their status bits. This is because, when D compared its
number with the others (step 5 of AddSubnet(), using the s-mask),
they were all different. In other words, a router would be able
distinguish an address in D from addresses in A, B, and C
Next, a fifth subnet, E, is added. We get
Subnet Addr
A 100g ghhh 1111 0000
B 01gg ghhh 1111 0000
C 110g ghhh 1111 0000
D 001g ghhh 1111 0000
E 101g ghhh 1111 0000
Notice that this time, A was forced to change its leftmost g-bit (
5) into an s-bit, because bit 5 is needed to distinguish subnet
Tsuchiya [Page 10]
RFC 1219 On the Assignment of Subnet Numbers April 1991
from subnet E (step 511 of AddSubnet()). Changing bit 5 into an s
bit prevents hosts from being added to A to the point where bit 5
would be changed into a one (that is, step 5 of AddHost()
fail).
Notice also that if the masks in A, B, and C were originally set
1100.0000, then the addition of E would have caused A's mask
change to 1110.0000 (Step 512 of AddSubnet()).
Next, 8 hosts each are added to subnets A and C, thus causing
right-most g-bit in each to change to an h-bit
Subnet Addr
A 100g hhhh 1111 0000
B 01gg ghhh 1111 0000
C 110g hhhh 1111 0000
D 001g ghhh 1111 0000
E 101g ghhh 1111 0000
Notice again that no masks have changed. If the masks for A, B,
C were originally set to 1111 1000, then they would have
changing (step 62 of AddHost()).
Next, enough hosts are added to subnet B that all of its
g-bits become h-bits
Subnet Addr
A 100g hhhh 1111 0000
B 01hh hhhh 1100 0000
C 110g hhhh 1111 0000
D 001g ghhh 1111 0000
E 101g ghhh 1111 0000
Notice here that the masks in B's subnet had to be changed
accommodate the new h-bits (step 62 of AddHost()). Notice also
if the person assigning host addresses for B (B Address Authority,
BAA) is different than the person assigning network numbers (RootAA),
then BAA must coordinate the change of its last g-bit to an h-
with the RootAA. This allows the RootAA to properly
additional subnet numbers, as in the next step, where we add
subnet F
Subnet Addr
A 100g hhhh 1111 0000
B 01hh hhhh 1100 0000
C 110g hhhh 1111 0000
D 001g ghhh 1111 0000
E 101g ghhh 1111 0000
Tsuchiya [Page 11]
RFC 1219 On the Assignment of Subnet Numbers April 1991
F 1110 ghhh 1111 0000
Notice that F received subnet number 1110 rather than subnet
011 (which is what comes after 101 in MI counting). The reason
that 1) 011 is not distinguishable from B's subnet address using B'
mask, and 2) we can't increase B's mask to make it
because B has already assigned hosts at bit position 5. In
words, when the comparison of step 1 in AddSubnet() was tried
number 011, the two values were equal, and so the next number
tried. In fact, no subnet numbers with 01 in bit positions 7 and 6
can be assigned (unless B loses hosts).
Next, subnet E is removed
Subnet Addr
A 10gg hhhh 1111 0000
B 01hh hhhh 1100 0000
C 110g hhhh 1111 0000
D 001g ghhh 1111 0000
F 1110 ghhh 1111 0000
Notice that this caused subnet A to change an s-bit back into a g
bit. This is because the equality of step 33 of RemoveSubnet()
not hold true for subnet A with respect to the remaining subnets
[1] Braden, R., "Requirements for Internet Hosts --
Layers", RFC 1122, USC/Information Sciences Institute,
1989.
[2] Mogul, J., and J. Postel, "Internet Standard
Procedure", RFC 950, USC/Information Sciences Institute,
1985.
[3] Moy, J., "OSPF Specification", RFC 1131, Proteon, October 1989.
[4] Postel, J., "Internet Control Message Protocol", RFC 792,
USC/Information Sciences Institute, September 1981.
[5] Tsuchiya, P., "Efficient and Flexible Hierarchical
Assignment", TM-ARH-018495, Bellcore, February 1991.
[6] Hedrick, C., "Routing Information Protocol" RFC 1058,
University, June 1988.
[7] Braden, R., and J. Postel, "Requirements for Internet Gateways",
RFC 1009, USC/Information Sciences Institute, June 1987.
Tsuchiya [Page 12]
RFC 1219 On the Assignment of Subnet Numbers April 1991
Security
Security issues are not discussed in this memo
Author's
Paul F.
435 South St.5 South St
MRE 2L-281
Morristown, NJ 07960
Phone: 201 829-4484
EMail: tsuchiya@thumper.bellcore.
Tsuchiya [Page 13]
if you see any problems within the linking, don't worry be happy,
this is version 0.1 of the Relevance System and you gotta expect some crappy subroutines sometimes,
just be content we did not write this in Java, which would have made this "bigger and better" HAHAHHA.
RFC documents can be found at I.E.T.F.
Relevance System Copyright © 2002 Spectrum WorldResearch
other technical nosh by ServerMasters Corporation
collaboration of BobX
