[Dcplusplus-commit] SF.net SVN: adc:[111] trunk/ADC-Recommendation.txt

[<ul...@us...>]

Revision: 111
          http://sourceforge.net/p/adc/code/111
Author:   ullner
Date:     2013-06-30 14:34:06 +0000 (Sun, 30 Jun 2013)
Log Message:
-----------
Added SID allocation suggestions.

Modified Paths:
--------------
    trunk/ADC-Recommendation.txt

Modified: trunk/ADC-Recommendation.txt
===================================================================
--- trunk/ADC-Recommendation.txt	2013-06-30 13:54:31 UTC (rev 110)
+++ trunk/ADC-Recommendation.txt	2013-06-30 14:34:06 UTC (rev 111)
@@ -1,6 +1,5 @@
 = ADC Recommendations
-Fredrik Ullner <ul...@gm...>
-1.0.0, July 2010
+1.1.0
 
 == Abstract
 These are the official recommendations to ADC. This document is based on the information contained in the ADC documents, ADC wiki and ADC blog. Information is this document should be taken as guide lines to implementations.
@@ -12,9 +11,16 @@
 
 This version corresponds to $Revision: 1 $.
 
-=== Version 1.0.0
-* Initialize release
+=== Version 1.1.0, UNRELEASED
 
+* Added ZLIB recommendation
+* Added SID recommendations/considerations.
+
+=== Version 1.0.0, 2010-07-01
+Fredrik Ullner, <ul...@gm...>
+
+* Initial release
+
 == General recommentations
 
 Message length
@@ -26,37 +32,130 @@
 While STA messages require a severity to accompany the error code, the severity may not be of importance to some error codes or are simply implied by the actual error code. However, it is important that the severity is sent as appropriate and is accurate. STA messages with 0 (success) for severity can usually be regarded by implementations that the information require little or no counter-action.
 The following list include error codes that make no or little sense in one or many severities, and a description why they are best used in one or only some severities. The descriptive text for the error codes can be seen in the STA specification, but may be re-stated as part of the description why they can have severity restriction(s).
 
-11 | If the hub is full, it makes little sense in keeping the client in some "connected" state. The recommended severity is to use 2 (fatal) to force the client to reconnect at a later time.
-12 | Similar to error code 11.
-21 | While potentially fatal, the client may resend its INF with a new NI field. The recommended severity for hubs is to use 2 (fatal) but they can use 1 (recoverable).
-22 | Similar to error code 21.
-23 | An invalid password depend on whether the hub wish to allow the client to resend its password (say, if the transmission became garbled). However, the recommended severity is to use 2 (fatal) unless under special circumstances, for some clients or for some users.
-24 | The recommended severity is to use 2 (fatal).
-25 | Can be 1 (recoverable) or 2 (fatal) but generally not 0 (sucess).
-26 | If the user is not registered in the hub, it makes little sense to try to reconnect immediately. The recommended severity is to use 2 (fatal).
-27 | Similar to error code 24.
-30 | The recommended severity is to use 2 (fatal).
-31 | Must be 2 (fatal).
-32 | Must be 2 (fatal).
-43 | Information that is missing or is bad is generally grounds for a disconnect but may be recoverable under certain states. The recommended severity is to use 2 (fatal).
-44 | Similar to error code 43.
-45 | Similar to error code 43.
-46 | Similar to error code 43.
-47 | Must be 2 (fatal).
-50 | May be cause for a disconnect but is generally recoverable. The recommended severity is to use 1 (recoverable).
-51 | Similar to error code 50.
-52 | Similar to error code 50.
-53 | Similar to error code 11.
-54 | Must be 2 (fatal).
+[options="autowidth"]
+|=====
+|11 |If the hub is full, it makes little sense in keeping the client in some "connected" state. The recommended severity is to use 2 (fatal) to force the client to reconnect at a later time.
+|12 |Similar to error code 11.
+|21 |While potentially fatal, the client may resend its INF with a new NI field. The recommended severity for hubs is to use 2 (fatal) but they can use 1 (recoverable).
+|22 |Similar to error code 21.
+|23 |An invalid password depend on whether the hub wish to allow the client to resend its password (say, if the transmission became garbled). However, the recommended severity is to use 2 (fatal) unless under special circumstances, for some clients or for some users.
+|24 |The recommended severity is to use 2 (fatal).
+|25 |Can be 1 (recoverable) or 2 (fatal) but generally not 0 (sucess).
+|26 |If the user is not registered in the hub, it makes little sense to try to reconnect immediately. The recommended severity is to use 2 (fatal).
+|27 |Similar to error code 24.
+|30 |The recommended severity is to use 2 (fatal).
+|31 |Must be 2 (fatal).
+|32 |Must be 2 (fatal).
+|43 |Information that is missing or is bad is generally grounds for a disconnect but may be recoverable under certain states. The recommended severity is to use 2 (fatal).
+|44 |Similar to error code 43.
+|45 |Similar to error code 43.
+|46 |Similar to error code 43.
+|47 |Must be 2 (fatal).
+|50 |May be cause for a disconnect but is generally recoverable. The recommended severity is to use 1 (recoverable).
+|51 |Similar to error code 50.
+|52 |Similar to error code 50.
+|53 |Similar to error code 11.
+|54 |Must be 2 (fatal).
+|=====
 
 == ZLIB compression
 
 === Generic
 
 * Try to keep constant and almost constant named parameters together, that way there is a higher likelyhood for a longer parameter match.
-
 * When possible try to keep similar commands no more than a window size (usually 32 bits if highest rate is used) away, that ensures you will benefit from the redundancy provided by these (this may be particularly important when sending large strings like MOTDs or help and configuration values intertwined with other commands).
-
 * Syncing is important to keep the clients updated but when you sync some bytes are sent (the sync ones and the ones for the Huffman tree of the new packet if it is a type 2 packet) as such it may make sense to keep in different queues commands depending on how much latency matters for them, for example you may want to keep low latency for MSG commands and send them frequently but may prefer to send searches or passive results together each half second or so. Also latencies matter depending on the type of network, on a LAN users expect most things to happen almost inmediately (especially things like MSGs) whilst clients connecting over a classic DSL line may not care that much for higher latencies.
 
+== SID generation
+The following are different algorithms for hubs to allocate and assign session IDs (SIDs) to 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).
+
+=== Algorithms
+The following algorithms are ways one can manage the SIDs that are assigned.
+
+==== Random SID allocation
+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. 
+
+Notes: 
+
+* The algorithm requires that lookup of users must be as cheap as possible.
+
+==== Incremental SID allocation
+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 1 million login attempts have been made, one can easily figure out how many users have logged in before. 
+
+Notes:
+
+* The algorithm requires that lookup of users must be as cheap as possible.
+
+==== Pre-allocated recyclable SIDs
+1. Allocate a queue large enough to contain SIDs for the maximum users allowed (or dynamically, regarding the user count and the maximum allowed)
+2. Pre-initialize the queue with unique SIDs (for example in ascending order)
+3. When client logs in: Assign the first SID from the end of the queue
+4. 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 maximum 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.
+
+Notes:
+
+* Changing the maximum users limit: 
+** if maximum users is increased, another set of unique SIDs needs to be added to the front of the queue. 
+** if maximum 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
+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.
+* 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.
+
 // vim: set syntax=asciidoc:

This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.