Algorithms for Variable Length Subnet Address Assignment.
AbstractIn a computer network that consists of M subnetworks, the L-bit address of a machine consists of two parts: A prefix si that contains the address of the subnetwork to which the machine belongs, and a suffix (of length L$-$ |si|) containing the address of that particular machine within its subnetwork. In fixed-length subnetwork addressing, |si| is independent of i, whereas, in variable-length subnetwork addressing, |si| varies from one subnetwork to another. To avoid ambiguity when decoding addresses, there is a requirement that no si be a prefix of another sj. The practical problem is how to find a suitable set of sis in order to maximize the total number of addressable machines, when the ith subnetwork contains ni machines. Not all of the ni machines of a subnetwork i need be addressable in a solution: If $n_i > 2^{L-|s_i|},$ then only $2^{L-|s_i|}$ machines of that subnetwork are addressable (none is addressable if the solution assigns no address si to that subnetwork). The abstract problem implied by this formulation is: Given an integer L, and given M (not necessarily distinct) positive integers $n_1, \cdots, n_M,$ find M binary strings $s_1, \cdots, s_M$ (some of which may be empty) such that 1) no nonempty string si is prefix of another string sj, 2) no si is more than L bits long, and 3) the quantity $\sum \nolimits _{|s_k|\ne0} \min \left\{ n_k, 2^{L-|s_k|} \right\}$ is maximized. We generalize the algorithm to the case where each ni also has a priority pi associated with it and there is an additional constraint involving priorities: Some subnetworks are then more important than others and are treated preferentially when assigning addresses. The algorithms can be used to solve the case when L itself is a variable; that is, when the input no longer specifies L but, rather, gives a target integer  for the number of addressable machines, and the goal is to find the smallest L whose corresponding optimal solution results in at least  addressable machines.
Introduction
This introduction discusses the connection between computer networking and the abstract problems
for which algorithms are subsequently given. It also introduces some terminology.
In a computer network that consists of M subnetworks, the L-bit address of a machine consists
of two parts: A prefix that contains the address of the subnetwork to which the machine belongs,
and a suffix containing the address of that particular machine within its subnetwork. In the case
where the various subnetworks contain roughly the same number of machines, a fixed partition of
the L bits into a t-bit prefix, Me, and an (L \Gamma t)-bit suffix, works well in practice: Each
subnetwork can then contain up to 2 L\Gammat addressable machines; if it contains more, then only 2 L\Gammat
of them will have an address and the remaining ones will be unsatisfied, in the sense that they will
have no address. If, in a fixed length partition scheme, some machines are unsatisfied, then the only
way to satisfy them is to increase the value of L. However, a fixed length scheme can be wasteful
if the M subnetworks consist of (or will eventually consist of) different numbers of machines, say,
machines for the ith subnetwork. In such a case, the fixed scheme can leave many machines
unsatisfied (for that particular value of L) even though the variable length partition scheme that
we describe next could satisfy all of them without having to increase L.
In a variable partition scheme, the length of the prefix containing the subnetwork's address
varies from one subnetwork to another. In other words, if we let s i be the prefix that is the address
of the ith subnetwork, then we now can have js j. However, to avoid ambiguity (or having to
store and transmit js i j), there is a requirement that no s i be a prefix of another s j . Variable length
subnetwork addressing is easily shown to satisfy a larger total number of addressable machines than
the fixed length scheme: There are examples where fixed length subnetwork addressing cannot
satisfy all of the addressing
can. Furthermore, we are also interested in the cases where even variable length addressing cannot
satisfy all of the N machines: In such cases we want to use the L bits available as effectively as
possible, i.e., in order to satisfy as many machines as possible. Of course an optimal solution might
then leave unsatisfied all the machines of, say, the ith subnetwork; this translates into s i being the
empty string, i.e., js solution therefore consists of determining binary strings
that maximize the sum
A solution completely satisfies the ith subnetwork if it satisfies all of the machines of that
subnetwork, i.e., if js no machine of the ith subnetwork is
satisfied, and we then say that the ith network is completely unsatisfied. If the solution satisfies
some but not all the machines of the ith subnetwork, then that subnetwork is partially satisfied;
this happens when in which case only 2 L\Gammajs i j of the machines of that subnetwork
are satisfied. An optimal solution can leave some of the subnetworks completely satisfied, others
completely unsatisfied, and others partially satisfied.
The prioritized version of the problem models the situation where some subnetworks are more
important than others. We use the following priority policy.
Priority Policy: "The number of satisfied machines of a subnetwork is the same as if all lower-priority
subnetworks did not exist."
The next section proves some useful properties for a subset of the optimal solutions. We assume
the unprioritized case, and leave the prioritized case until the end of the paper.
Before proceeding with the technical details of our approach, we should stress that in the above
we have provided only enough background and motivation to make this paper self-contained. The
reader interested in more background than we provided can find, in references [11, 8, 9, 10, 6, 4, 12],
the specifications for standard subnet addressing, and other related topics. For a more general
discussion of hierarchical addressing, its benefits in large networks, and various lookup solution
methods (e.g., digital trees), see [7, 5]. Finally, what follows assumes the reader is familiar with
basic techniques and terminology from the text algorithms and data structures literature - we
refer the reader to, for example, the references [1, 2, 3].
Preliminaries
The following definitions and observations will be useful later on. We assume, without loss of
generality, that . Since the case when n admits a trivial solution (2 L machines
are satisfied, all from subnetwork 1), from now on we assume that
logarithms are to the base 2.
Lemma 1 Let S be any solution (not necessarily optimal). Then there exists a solution S 0 that
satisfies the same number of machines as S, uses the same set of subnetwork addresses as S, and
in which the completely unsatisfied subnetworks (if there are any) are those that have the k lowest
k. In other words, js
Proof: Among all such solutions that satisfy the same number of machines as S, consider one that
has the smallest number of offending pairs defined as pairs completely
unsatisfied, and j is not completely unsatisfied. We claim that the number of such pairs is zero:
Otherwise interchanging the roles of subnetworks i and j in that solution does not decrease the
total number of satisfied machines, a contradiction since the resulting solution has at least one
fewer offending pair. 2
On the other hand, there does not necessarily exist an S 0 of equal value to S and in which all
of the (say, completely satisfied subnetworks are those that have the k highest n i values. If,
in the optimal solution we seek, we go through the selected subnetworks by decreasing n i values,
then we initially encounter a mixture of completely satisfied and partially satisfied subnetworks,
but once we get to a completely unsatisfied one then (by the above lemma) all the remaining ones
are completely unsatisfied.
Lemma 2 Let S be any solution (not necessarily optimal). There exists a solution S 0 that satisfies
as many machines as S, uses the same set of subnetwork addresses as S, and is such that js
Proof: Among all such solutions that satisfy the same number of machines as S, consider one which
has the smallest number of offending pairs defined as pairs i; j such that js
We claim that the number of such pairs is zero: Otherwise interchanging the roles of
subnetworks i and j in that solution does not decrease the total number of satisfied machines, a
contradiction since the resulting solution has at least one fewer offending pair. 2
Let T be a full binary tree of height L, i.e., T has 2 L leaves and 2 nodes. For any
solution S, one can map each nonempty s i to a node of T in the obvious way: The node v i of T
corresponding to subnetwork i is obtained by starting at the root of T and going down as dictated
by the bits of the string s i (where a 0 means "go to the left child" and a 1 means "go to the right
child"). Note that the depth of v i in T (its distance from the root) is js i j, and that no v i is ancestor
of another v j in T (because of the requirement that no nonempty s i is a prefix of another s j ). For
any node w in T , we use parent(w) to denote the parent of w in T , and we use l(w) to denote the
number of leaves of T that are in the subtree of w; hence solution
completely satisfies subnetwork i iff which case we can extend our terminology by
saying that "node v i is completely satisfied by S" rather than the more accurate "the subnetwork
i corresponding to node v i is completely satisfied by S."
any solution that satisfies Lemmas 1 and 2. Then there is a
solution
i at the same depth as v i ,
and is such that implies that v 0
i has smaller preorder number in T than v 0
j (which is equivalent
to saying that s 0
i is lexicographically smaller than s 0
can be obtained from S by a sequence of "interchanges" of various subtrees of T , as
follows. initially a copy of T , and repeat the following until
1. Perform an "interchange" in T 0 of the subtree rooted at node v i with the subtree rooted at
the leftmost node of T 0 having same depth as
i is simply the new position occupied by
"interchange".
2. Delete from T 0 the subtree rooted at v 0
Performing in T the interchanges done on T 0 gives a new T where the v 0
's have the desired property.The "interchange" operations used to prove the above lemma will not be actually performed by
our algorithm - their only use is for the proof of the lemma.
Lemma 4 Let S be any solution (not necessarily optimal) that satisfies the properties of Lemmas 1-
3. There exists a solution S 0 that satisfies as many machines as S, that also satisfies the properties of
Lemmas 1-3, and is such that any v i that is not the root of T has l(parent(v i
the nonempty s i 's of such an S 0 are a subset of the nonempty s i 's of S.
Proof: Among all solutions that satisfy the same number of machines as S, let S
one that maximizes the integer i which all of v the lemma's property,
i.e., they have We claim that that such an S 0
already satisfies the lemma. Suppose to the contrary that i ! k, i.e., that l(parent(v i+1
cannot be completely satisfied since that would imply that l(v i+1
Hence v i+1 is only partially satisfied, i.e., l(v
z be the parent of v i+1 and y be the sibling of v i+1 in T ; y must be to the right of v i+1 since
otherwise v i is at y and v i too has l(parent(v i which contradicts the definition of i. Also
note that the fact that l(z) - n i+1 implies that n i.e., the number of unsatisfied
machines in subnetwork promoting v i+1 by "moving it to its parent",
one level up the tree T , thus (i) replacing the old s i+1 by a new (shorter) one obtained by dropping
the rightmost bit of the old s i+1 , and (ii) deleting from S 0 all of the s j that now have the new
s i+1 as a prefix. Note that, for each s j so removed, its corresponding v j was in the subtree of y,
hence the removal of these s j 's results in at most l(y) machines becoming unsatisfied, but that is
compensated for by l(y) machines of subnetwork that have become newly satisfied as a result
of v i+1 's promotion, implying that the new solution S 00 has value that is no less than that of S 0 .
However, a v j so deleted from the subtree of y can cause S 00 to no longer satisfy the property of
Lemma 1 because of a surviving v t to the right of z having an n t ! n j . We next describe how to
modify S 00 so it does satisfy Lemma 1. In the rest of the proof S 0 refers to the solution we started
with, before v i+1 was moved up by one level, and S 00 refers to the solution after v i+1 was moved.
Let (v denote the set of the deleted v j 's (who were in y's
subtree in the original S 0 but are not in S 00 ). If are in S 00 and are
to the right of z, hence we need to "repair" S 00 to restore the property of Lemma 1 (if on the other
then no such repair is needed). This is done as follows. Simultaneously for each
of the elements of the sequence (v do the following: In the tree T , place the element
considered (say, v j ) at the place previously (in the original S 0 ) occupied by v j+l+1 (if
then that v j cannot be placed and the new solution leaves completely unsatisfied). The S 00 so
modified satisfies the same number of machines as the original one, still satisfies Lemmas 1-3, but
has "moved" v i+1 one level up the tree T . This can be repeated until v i+1 is high enough that
but that is a contradiction to the definition of integer i. Hence it must be
the case that S 0 has
Lemma 5 There exists an optimal solution S that satisfies the properties of Lemma 4 and in which
every subnetwork i has an s i of length equal to either
Proof: Let S be an optimal solution satisfying Lemma 4. First, we claim that there is such an
S in which every s i satisfies js Suppose to the contrary that, in S, some s i has
length less than moving v i from its current position, say node y in T , to a
descendant of y whose depth equals e, would leave subnetwork i completely satisfied
without affecting the other subnetworks. Repeating this for all i gives a solution in which every
s i has length - course moving a v i down to (say) y's left subtree leaves a ``hole''
in y's right subtree in the sense that the right subtree of y is unulitilized in the new solution.
The resulting S might have many such unutilized subtrees of T : It is easy to "move them to the
right" so that they all lie to the right of the utilized subtrees of T (the details are easy and are
omitted). Hence we can assume that S is such that js (Note that the above does
not introduce any violation of the properties of Lemma 4.)
To complete the proof we must show that js implies that
Taking logarithms on both sides gives:
which completes the proof. 2
The observations we made so far are enough to easily solve in O(M log M) time the following
(easier) version of the problem: Either completely satisfy all M subnetworks, or report that it is
not possible to do so. It clearly suffices to find a v i in T for each subnetwork i (since the v i 's
uniquely determine the s i 's). This is done in O(M log M) time by the following greedy algorithm,
which operates on only that portion of T that is above the v i 's:
1. Sort the n i 's in decreasing order, say n log M) (the log M factor
goes away if the n i 's can be sorted in linear time, e.g., if they are integers smaller than M O(1) ).
2. For each n i , compute the depth d i of v i in T : d
3. Repeat the following for on the leftmost node of T that is at depth
d i and has none of v no such node exists then stop and output "No
Solution Exists"). Time: O(M) by implementing this step as a construction and (simultane-
ously) preorder traversal of the relevant portion of T - call it T we start at the root
and stop at the first preorder node of depth d 1 , label it v 1 and consider it a leaf of T 0 , then
resume until the preorder traversal reaches another node of depth d 2 , which is labeled v 2 and
considered to be another leaf of T 0 , etc. Note that in the end the leaves of T 0 are the v i 's in
left to right order.
Theorem 1 Algorithm greedy solves the problem of finding an assignment of addresses that completely
satisfies all subnetworks when such an assignment exists. Its time complexity is O(M) if the
are given in sorted order, O(M log M) if it has to sort the n i 's.
Proof: The time complexity was argued in the exposition of the algorithm. Correctness of the
algorithm follows immediately from Lemmas 1-5. 2
Theorem 2 An assignment that completely satisfies all subnetworks exists if and only if
Proof: Observe that algorithm greedy succeeds in satisfying all subnetworks if and only if the
inequality is satisfied. 2
Corollary 1 Whether there is an assignment that completely satisfies all subnetworks can be determined
in O(M) time, even if the n i 's are not given in sorted order.
Proof: The right-hand side of the inequality in the previous theorem can be computed in O(M)
time. 2
Would the greedy algorithm solve the problem of satisfying the largest number of machines
when it cannot satisfy all of them? That is, when it cannot assign a v i to a node (in Step 3),
instead of saying "No Solution Exists", can it accurately claim that the solution produced so far is
optimal? The answer is no, as can be seen from the simple example of
example the greedy algorithm satisfies 5 machines whereas it is possible to satisfy
7 machines). However, the following holds.
Observation 1 The solution returned by the greedy algorithm satisfies a number of machines that
is no less than half the number satisfied by an optimal solution.
be the number of subnetworks completely satisfied by greedy. Observe that
since if we had would have put v i at a greater depth than its
current position. Therefore an optimal solution could, compared to greedy, satisfy no more than
an additional
machines, which is less than
the number satisfied by greedy.However, we need not resort to approximating an optimal solution, since the next section will
give an algorithm for finding an optimal solution.
3 Algorithm for the Unprioritized Case
We assume throughout this section that the greedy algorithm described earlier has failed to satisfy
all the machines. The goal then is to satisfy as many machines as possible.
We call level ' the 2 ' nodes of T whose depth (distance from the root) is '. We number the
nodes of level ' as follows: ('; 1); ('; is the kth leftmost node of level '.
Lemma 5 says that v i is either at a depth of d i or of d limits
the number of choices for where to place v i to 2 d i choices at depth d i , and 2 d i +1 choices at depth
1. For every to be the maximum
number of machines of subnetworks that can be satisfied by using only the portion of T
having preorder numbers - the preorder number of (d i ; j), and subject to the constraint that v i
is placed at node (d defined analogously but with (d playing the role that
played in the definition of C(i; j). The C(i; j)'s and C 0 (i; j)'s will play an important role
in the algorithm: Clearly, if we had these quantities for all then we could easily obtain
the number of machines satisfied by an optimal solution, simply by choosing the maximum among
them:
Another notion used by the algorithm is that of the '-predecessor of a node v of T , where ' is
an integer no greater than v's depth: It is the node of T at level ' that is immediately to the left of
the ancestor of v at level ' (if no such node exists then v has no '-predecessor). In other words, if
w is the ancestor of v at level ' (possibly then the '-predecessor of v is the rightmost node
to the left of w at level '. The algorithms will implicitly make use of the fact that the '-predecessor
of a given node v can be obtained in constant time: If v is represented as a pair (a; b) where a is
v's depth and b is the left-to-right rank of b at that depth (i.e., v is the bth leftmost node at depth
a), then the '-predecessor of (a; b) is ('; c) where
The following algorithm preliminary will later be modified into a better algorithm. The input
to the algorithm is L and the n i 's. The output is a placement of the v i 's in T ; recall that this is
equivalent to computing the s i 's because the s i 's can easily obtained from the v i 's (in fact each s i can
be obtained from v i in constant time, as will be pointed out later). We assume that a preprocessing
step has already computed the d i 's. We use pred('; v) or pred('; a; b) interchangeably, to denote
the '-predecessor of a node v = (a; b), with the convention that pred('; a; b) is (\Gamma1; \Gamma1) when it is
undefined, i.e., when ' ? a or (a; b) has no '-predecessor.
1. For to M in turn, do the following:
(a) For
with the convention that are 0.
be the node of T that "gives C(i; b) its value" in the above maximization,
that is, f(i; b) is
pred(d
pred(d
(b) For
with the convention that are 0.
be the node of T that "gives C 0 (i; b) its value" in the above maximization,
that is, f
pred(d
pred(d
2. Find the largest, over all i and b, of the C(i; b)'s and C 0 (i; b)'s computed in the previous
step: Suppose it is C(k; b) (respectively, C 0 (k; b)). Then C(k; b) (respectively, C 0 (k; b)) is the
maximum possible number of machines that are satisfied by an optimal solution v
To generate a set of assignments that correspond to that optimal solution (rather than just its
value), we use the f and f 0 functions obtained in the previous step: Starting at node (d
(respectively, we "trace back" from there, and output the nodes of the optimal
solution as we go along (in the order v k ; v The details of this "tracing back" are
as follows:
(a) k. If the largest of the C(i; b)'s and C 0 (i; b)'s computed in the previous step was
Then repeat the following until
(b) Output "v equal to either f(i; fi) (in case or to f 0 (i; fi)
(in case
Note. To output the string s i corresponding to a v i node, rather than the (d
describing that v i , we modify the above Step 2(b) as follows: If v
(a; b) then s i is the binary string consisting of the rightmost a digits in the binary
representation of the integer 2 a is the breadth-first number
of the node (a; b), and that an empty string corresponds to the root since 2 0
This implies that s i can be computed from the pair (a; b) in constant time.
Correctness of the above algorithm preliminary follows from Lemmas 1 - 5.
The time complexity of preliminary is unsatisfactory because it can depend on the size of T as
well as M , making the worst case take O(M2 L ) time. However, the following simple modification
results in an O(M 2 In Steps 1(a) and (respectively) 1(b), replace "For
"For iteration
bounds for b remain unchanged, at 2 d i for 1(a) and 2 d i +1 for 1(b)). Before arguing the correctness
of this modified algorithm, we observe that its time complexity is O(M 2 ), since we now iterate
over only M 2 distinct note: The relevant C(i; b)'s need not be explicitly
initialized, they can implicitly be assumed to be zero initially; this works because of the particular
order in which Step 1 computes them.) Correctness follows from the claim (to be proved next) that
there is an optimal solution that, of the 2 a nodes of any level a, does not use any of the leftmost
nodes of that level. Let S be an optimal solution that has the smallest possible number
(call it t) of violations of the claim, i.e., the smallest number of nodes (a; b) where b ! 2 a \Gamma M and
some v i is at (a; b). We prove that by contradiction: Suppose that t ? 0, and let a be the
smallest depth at which the claim is violated. Let (a; b) be a node of level a that violates the claim,
is placed at (a; b) by optimal solution S. Since there are more than M
nodes to the right of v i at level a, the value of S would surely not decrease if we were to modify S
by re-positioning all of v in the subtrees of the rightmost nodes of level a
(without changing their depth). Such a modification, however, would decrease t, contradicting the
definition of S. Hence t must be zero, and the claim holds.
The following summarizes the result of this section.
Theorem 3 The unprioritized case can be solved in O(M 2 ) time.
4 Algorithm for the Prioritized Case
Let the priorities be is the priority of subnetwork k i . In the rest of
this section we assume that L is not large enough to completely satisfy all of the M subnetworks
(because in the other case, where L is large enough, the priorities do not play a role and Theorem
Use greedy (or, alternatively, Corollary 1) in a binary search for the largest i (call it - i) such
that the subnetworks k can be completely satisfied; each "comparison" in the binary search
corresponds to a call to greedy (or, alternatively, to Corollary 1) - of course it ignores the priorities
of the subnetworks k This takes total time O(M log M) even though we may use greedy
a logarithmic number of times, because we sort by decreasing n j 's only once, which makes each
subsequent execution of greedy cost O(M) time rather than O(M log M ). Let S be the solution,
returned by greedy, in which all of subnetworks are completely satisfied. By the definition
of - i, it is impossible to completely satisfy all of subnetworks Our task is to modify S
so as to satisfy as many of the machines of subnetworks k - as possible without violating
the priority policy (hence keeping subnetworks completely satisfied).
This is done as follows:
1. set the depth of each k i , 1, to be dlog n k i e.
2. Use greedy log log n k j times to binary search for the smallest depth (call it d) at which v k j
can be placed without resulting in the infeasibility (as tested by greedy) of (i) placing all
of subnetworks k at their previously fixed depths and (ii) placing k j at depth d
(there are log n k j possible values for d, which implies the log log n k j iterations of the binary
search). If no such d exists (i.e., if any placement of k j prevents the required placement of
proceed to Step 3. If the binary search finds such a d then fix the depth of
v j to be d (it stays d in all future iterations), set 2.
3. The solution is described by the current depths of k These fixed depths are then
used by a preorder traversal of (part of) T to position v k 1
in T .
That the above algorithm respects the priority policy follows from the way we fix the depth of
Subnetworks of lower priority do not interfere with it (because they are considered
later in the iteration). The time complexity is easily seen to be O(M 2 log L), since n k
The following summarizes the result of this section.
Theorem 4 The prioritized case can be solved in O(M 2 log L) time.
5 Further Remarks
What if L itself is a variable ? That is, consider the situation where instead of specifying L the
input specifies a target integer fl for the number of addressable machines; the goal is then to find
the smallest L that is capable of satisfying at least fl machines. The algorithms we gave earlier (and
that assume a fixed L) can be used as subroutines in a "forward" binary search for the optimal
(i.e., smallest) value of L (call it -
L) that satisfies at least fl machines: We can use them log -
times
in a "forward" binary search for -
L. So it looks like there is an extra multiplicative log -
if L is itself a variable that we seek to minimize, as opposed to the version of the problem that
fixes L ahead of time. However, Theorem 2 implies that there is no such log -
in the important case where we seek the smallest L that satisfies all
the machines: This version of the problem can be solved just as fast as the one where L is fixed
and we seek to check whether it can completely satisfy all M subnetworks.

Acknowledgement

. The authors are grateful to three anonymous referees for their helpful comments
on an earlier version of this paper.



--R

Combinatorial Algorithms on Words
Introduction to Algorithms
Algorithms
"Class A Subnet Experiment"
"Parallel searching techniques for routing table lookup,"
"Class A Subnet Experiment Results and Recommendations"
"Fast routing table lookup using CAMs,"
"Internet standard subnetting procedure"
"Broadcasting Internet datagrams in the presence of subnets"
"Internet subnets"
"Variable Length Subnet Table For IPv4"
"On the Assignment of Subnet Numbers"
--TR
prefix codes;addressing;algorithms;computer networks