November 1996 Programmer's Challenge

ROUTER RULES

Mail solutions to: progchallenge@mactech.com

Due Date: 1 November 1996

This month's Challenge is based on a suggestion by Peter Lewis and is motivated by a real-world problem. A certain university has a B-class IP subnet, let's call it 199.232.*.* (with apologies to the real-world owner of that subnet). The subnet is broken down into 256 networks for the various faculties and departments, each one having 256 IP numbers. So, for example, the computer club might have 199.232.101.*. Our hypothetical university is charged for communications based on volume, so some of these networks are allowed to talk to the outside world, and others are not. Outside access is controlled by programming a router with a sequence of rules, each of which allows or denies access to some subset of IP numbers. A rule consists of a (mask, value, allow) triplet. For example, say the networks (in hex) 01, 03, 41, 43 are allowed out, and all the rest are barred. The rules could be simply:

FF, 01, allow

FF, 03, allow

FF, 41, allow

FF, 43, allow

00, 00, deny

But this could be simplified to:

BD, 01, allow

00, 00, den

Your objective for this Challenge is to quickly generate a small sequence of rules that allows outside network access to only a specified set of networks. The prototype for the code you should write is:

enum {kDeny=0, kAllow=1};

typedef struct Rule {

long mask;

long value;

long allow; /* 0 == deny, 1== allow */

} Rule;

long RouterRules(

long allowedValues[],

long numAllowedValues,

long numBits,

Rule rulesArray[],

long maxRules

);

The array allowedValues is the set of numAllowedValues networks that are to be given outside network access. All other networks should be denied access. Instead of being limited to 8 bits as in the example above, network values have numBits bits. Your code should generate a sequence of rules that provides access to these networks, and no others. The rule sequence should be as short as possible and stored in rulesArray, which is allocated by the caller and is of size maxRules. Your code should return the number of rules generated, or return -1 if it cannot find a solution no longer than maxRules.

Rules will be triggered by the router in the order provided by your solution, and the first rule to fire for a given network will apply. At least one rule must fire for any possible network value. For example, if numBits==3, and we want to allow access to networks 0, 2, 3, 6, and 7, you could use the following rules:

3, 1, deny

6, 4, deny

7, 7, allow

To encourage code that generates both fast and short solutions, the ranking will be based on minimizing the following function of execution time on my 8500/150 and the number of rules generated:

score = (number of rules generated) + (execution time in seconds) / 2

This will be a native PowerPC Challenge, using the latest CodeWarrior environment. Solutions may be coded in C, C++, or Pascal.