IDRing

A major feature of the Romana Project is topology-aware IPAM, and an integral part of it is the ability to assign consecutive IP addresses in a block (and reuse freed up addresses, starting with the minimal).

Since IPv4 addresses are essentially 32-bit uint, the problem is basically that of maintaining a sequence of uints, while allowing reuse.

To that end, a data structure called IDRing was developed. I’ll describe it here. It is not yet factored out into a separate project, but as Romana is under Apache 2.0 license, it can still be reused.

  • The IDRing structure is constructed with a NewIDRing() method, that provides the lower and upper bound (inclusive) of the interval from which to give out IDs. For example, specifying 5 and 10 will allow one to generate IDs 5,6,7,8,9,10 and then return errors because the interval is exhausted. 

    Optionally, a locker can be provided to ensure that all operations on the structure are synchronized. If nil is specified, then synchronization is the responsibility of the user.

  • To get a new ID, call GetID() method. The new ID is guaranteed to be the smallest available.
  • When an ID is no longer needed (in our use case — when an IP is deallocated), call ReclaimID().
  • A useful method is Invert(): it returns an IDRing whose available IDs are the ones that are allocated in the current one, and whose allocated ones are the available ones in the current one. In other words, a reverse of an IDRing with min 1, max 10 and taken IDs from 4 to 8 inclusively is an IDRing with the following
    available ranges: [1,3], [9,10].
  • You can see examples of the usage in the test code and in actual IP allocation logic.
  • Persisting it is as easy as using the locker correctly and just encoding the structure to/decoding it from JSON.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s