Abstract
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 sufix (of length L - |s(sub i)| ) containing the address of that particular machine within its subnetwork. In fixed-length subnetwork addressing, |s(sub 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 j). 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 to be addressable in a solution: If n(sub i) > 2^(L - |s(sub i)|) then only 2^(L - |s(sub m machines of that subnetwork are addressable (none is addressable if 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 n1,....n(sub m) find M binary stings s1, ... s(sub m) (some of which may be empty) such that (i) no nonempty string s(sub i) is prefix of another string s(sub j), (ii) no s(sub i) is more than L bits long, and (iii) the quantity (sumation |s(sub k)| is not equal to 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 gama for the number of addressable machines, and the goal is to find the smallest L whose corresponding optimal solution results in at least gama addressable machines.
