Optimizing an IP generation method

Question

I have designed a proxy server which has the feature to manage miniature separate networks. Each network has space to have up to 500 nodes or 500 IPs. The code for getting a new virtual IP is based on a bit flag based approach. I have used an array of DWORD (Blocks) so as to skip entire 32 IP chunks, if the block is fully set. I have also divided the DWORD further into byte based checking. so as to forgo checking of all 32 bits as much as possible. The code also skips any addresses with the lower octet being 0 or 1. The code only gets the lower two octets while the higher two octets are fixed to 10.0.

I know the problem with this approach is that the higher the IP, the slower it gets found. So how can I diminish the slow down? Should I go higher towards LongWORD for one block? Should I check the Block byte by byte or in smaller/bigger chunks? Or just abandon this and find some other algorithm?

The limit to be 500 is more of a marketing move than a technical one. We currently have to manage 1800 such networks. These networks are academic in nature and have very anomalous behavior patterns, as such that we are seeing almost 10000 requests per second in peak times.

---
var
 fIPPool : array [0..15] of DWORD;
---
constructor xxxx;
begin
 fIPPool [0] := 00000003ドル; // Skips 0.0 and 0.1
 fIPPool [7] := 80000000ドル; // Skips 0.255
 fIPPool [8] := 00000003ドル; // Skips 1.0 and 1.1
 fIPPool [15] := $FE000000; // Skips 1.249-1.255
end;
---
function GetIP: DWORD;
var
 Block, Cell : Byte;
 Mask : DWORD
 function GetCell ( const ABlock: DWORD; var AMask: DWORD; const ACell : Byte )
 : Byte; inline;
 begin
 Result := ACell;
 while ( ABlock and AMask ) <> 0 do
 begin
 Result := Result + 1;
 AMask := AMask shl 1;
 end;
 end;
begin
 Result := 0;
 for Block := 0 to 15 do
 begin
 if fIPPool [Block] <> $FFFFFFFF then
 begin
 if ( fIPPool [Block] and 000000ドルFF ) < 000000ドルFF then
 begin
 Mask := 00000001ドル;
 Cell := GetCell ( fIPPool [Block], Mask, 0 )
 end
 else if ( fIPPool [Block] and 0000ドルFFFF ) < 0000ドルFFFF then
 begin
 Mask := 00000100ドル;
 Cell := GetCell ( fIPPool [Block], Mask, 8 )
 end
 else if ( fIPPool [Block] and 00ドルFFFFFF ) < 00ドルFFFFFF then
 begin
 Mask := 00010000ドル;
 Cell := GetCell ( fIPPool [Block], Mask, 16 );
 end
 else
 begin
 Mask := 01000000ドル;
 Cell := GetCell ( fIPPool [Block], Mask, 24 );
 end;
 Result := ( Block * 32 ) + Cell;
 fIPPool [Block] := fIPPool [Block] or Mask;
 break;
 end;
 end;
end;
// one can use the following line to get the IPs if run in a for-loop for 500 times
Memo1.Lines.Add
( IntToStr ( ( IP and $FF00 ) shr 8 ) +'.'+ IntToStr ( IP and 00ドルFF ));

• rolfl: Can you add some detail about why you have 500 and not 512 addresses in each block?
• rolfl: Also, how many of these networks do you have?

Answer 1

I have performed some benchmarks to get the optimum combination of block and slice sizes using 32-bit and 64-bit compiler. 64-bit because we are also developing an optimized 64-bit implementation on the sidelines. Here are the results for generating 320000 IPs on our server with all the server applications also running, the values are in Milli-seconds and floored over 5 runs;

Block-Slice 32-bit 64-bit
32-0 3479 3120
32-16 3464 5912
64-0 2059 2980
64-16 2028 1606
64-32 2013 1622

The algorithm gave the worst results with 8-bit slices. So the best bets are 64-32 for 32-bit and 64-16 for 64-bit for this algorithm.