Introduction

This article explains several possible algorithms for hub implementations to allocate and assign Session IDs (or SIDs) to ADC clients.

Background

In ADC the Session ID (or SID) uniquely identifies a user while connected to a hub, and the user will be assigned a SID at the time of login. Once assigned, the SID cannot be changed without a reconnect.

The SID is a 4 byte sequence of Base32 characters consisting of 32 possible characters, A-Z and 2-7. This means there can be 32^4 different SIDs (slightly over 1 million).

Suggestion: The first SID, 0 which is encoded as 'AAAA' is reserved for the hub (although not used in the protocol currently). A regular expression that matches a SID is: "[A-Z2-7]{4}".

There is no reserved SID for hub in the protocol in 1.0 that option was removed in previous draft version.

Algorithms

Random SID allocation

This algorithm is implemented in ADCH++.

1. When client logs in: SID = random number between 1 and 1048576.
2. if (SID in use) go to 1.
3. Assign SID to user

Advantages:

• Very simple to implement.

Disadvantages:

• Theoretically, if a hub has close to the maximum allowed users (1 Million), the algorithm of generating a unique SID becomes very costly. On a hub consiting of a few thousand users this is negligible if looking up users based on SID is fast.
• In order to make this algorithm efficient: looking up users based on the SID must be cheap.

Incremental SID allocation

This algorithm is implemented in uHub.

1. When hub starts, set: counter = 0
2. When client logs in: SID = ((++counter) % 1048576)
3. if (counter > 1048576) and (SID == 0 or in use) go to 2.
4. Assign SID to user

Advantages:

• Simple to implement.
• For the first 1048576 allocated SIDs one does not need to check for SID collisions.

Disadvantages:

• Information leak: Assuming less than 1M login attempts have been made, one can easily figure out how many users have logged in before.
• In order to make this algorithm efficient after 1M connections: looking up users based on the SID must be cheap.

Pre-allocated recyclable SIDs

This idea came from Pietry and darkKlor ^[1]. Implemented in NetfractionHub.

• Allocate a queue large enough to contain SIDs for the maximum users allowed (or dynamically, regarding the user count and the maximum allowed)
• Pre-initialize the queue with unique SIDs (for example in ascending order)
• When client logs in: Assign the first SID from the end of the queue
• When client logs out: push the SID to the beginning of the queue

Advantages:

• No need to check for duplicate SIDs when users log in.

Disadvantages:

• If max_users is too large, a lot of memory is allocated but not used (one can allocate as users come in, the maximum user count would be just a reference)
• If the queue is kept as a linked list of SIDs, even more memory is allocated.
• If the queue is kept as an array, a lot of memory moving needs to be performed when users log out.
• Changing the max_users limit while the hub is running is slightly more complicated (see below)
• Negligible: While starting up, the hub needs to allocate and fill the queues.

Changing the max_users limit:

• if max_users is increased, another set of unique SIDs needs to be added to the front of the queue
• if max_users is decreased, no change is needed, it just means the queue will still have unused elements in it if the hub becomes full (or remove some elements from the not used end of the queue)

Incremental recyclable SID allocation

This is planned for Luadch.

1. When hub starts, set counter = 0
2. When client logs in: take last element of SID array if exist and delete it or SID = something like ((++counter) % 1048576)
3. Assign SID to user
4. When client logs out: store client SID as last element in SID array

Advantages:

• Simple to implement (at least in Lua).
• You never need to check collisons.

Disadvantages:

• Information leak: you can find out the max user peak of the hub in a session.
• The SID array grows when more clients logout then login; in worst case, the hub is empty and the array contains all created SIDs of the session.

See a Lua implemetation using coroutines.

References

See also