Algorithms for variable length subnet address assignment

In a computer network that consists of M subnetworks, the L-bit address of a machine consists of two parts: A prefix s/sub i/ that contains the address of the subnetwork to which the machine belongs, and a suffix (of length L-Is/sub i/I) containing the address of that particular machine within its subnetwork. In fixed-length subnetwork addressing, Is/sub i/I is independent of I, whereas, in variable length subnetwork addressing, Is/sub i/I varies from one subnetwork to another. To avoid ambiguity when decoding addresses, there is a requirement that no s/sub i/ be a prefix of another s/sub i/. The practical problem is how to find a suitable set of s/sub i/s in order to maximize the total number of addressable machines, when the ith subnetwork contains n/sub i/ machines. Not all of the n/sub i/ machines of a subnetwork i need be addressable in a solution: If n/sub i/>2(L-|s/sub i/|), then only 2(L-|s/sub j/|) machines of that subnetwork are addressable (none is addressable s/sub i/ the solution assigns no address s/sub i/ to that subnetwork). The abstract problem implied by this formulation is: Given an integer L, and given M (not necessarily distinct) positive integers n/sub 1/,...,n/sub M/, find M binary strings s/sub 1/,...,s/sub M/ (some of which may be empty) such that (1) no nonempty string s/sub i/ is prefix of another string s/sub j/, (2) no s/sub i/ is more than L bits long, and (3) the quantity /spl Sigma/(|s/sub k/|/spl ne/0) min{n/sub k/,2(L-|s/sub k/|)} is maximized. We generalize the algorithm to the case where each n/sub i/ also has a priority p/sub i/ 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 /spl gamma/ for the number of addressable machines, and the goal is to find the smallest L whose corresponding optimal solution results in at least /spl gamma/ addressable machines.