On Thu, 9 Jan 1997, William Bulley wrote:
> According to Steven P. Crain:
> >
> > I'm of the opinion that RADIUS (auth&acct) should not use the dictionary
> > at all. Alot of time is wasted looking things up in the dictionaries and
> > parsing things. The users database should be preparsed into a machine
> > readable format very similar to the packets that will be sent to the
> > client. I bet the improvement in performance would be very dramatic.
>
> The Merit server reads the dictionary but once at startup.
>
> All subsequent "dictionary lookups" are done in memory at the
> fastest speed the machine can offer (traversing a linked list).
That is the same as Liv 1.16, Ascend, and I assume most implementations.
Consider:
Lookup username in users.dbm.
Get back (a sample from our database)
username Authentication-Type = Unix-PW
User-Service = Framed-User,
Framed-Address = testcrain.shore.net,
Framed-Netmask = 255.255.255.255,
Framed-Protocol = SLIP,
Framed-Compression = None,
Framed-MTU = 1006,
Ascend-Idle-Limit = 3600
Assume there are 'a' attributes assigned and 'v' values. (Livingston 1.16
stores all the values in a single linked list. I'm not sure if Merit does
that as well.)
For each attribute, you have to do an average of a/2 strcmp()s until you
find the correct one. (In Liv 1.16 --only used as an example because it
required the most hacking-- the linked list is in reverse order to the
order in dictionary file. Most dictionaries have the most used attributes
at the start, so they are actually found the slowest! Perhaps even 'a'
strcmp()s would be closer to the actual number.)
Then, if there is a VALUE as well (e.g. User-Service) you can through in
an average of v/2 strcmp()s as well. Each login then requires about 4a+2v
strcmp()s. Both a and v are about 150 with Merit's dictionary, i.e. an
average of 900 strcmp()s per login! (Really higher because 7 of the
attributes are right at the top, and so are found at the end of the list.
That pushes it over 1000.)
Compare this to a case where the lookup results in:
username [1027] [4] [1]
[6] [4] [2]
[8] [4] [ip #]
[9] [4] [0xffffffff]
[7] [4] [2]
[13] [4] [0]
[12] [4] [1006]
[244] [4] [3600]
Where each [] is stored in binary (4 bytes).
Advantages: 0 strcmps vs. 1000 strcmps per login.
The dictionary can be upgraded without worrying about upgrading
the users file.
The users file is much smaller. (about 100 bytes per user vs. 250
bytes)
Another alternative is modifying the dictionary, deleting everything that
is not being used. That would result in similar performance boost.
- ----------------------------------------------------------------------------
Steven P. Crain scrain@shore.net http://www.shore.net/~scrain
Shore.Net Unix Development and Administration
An ISP with Excellence in the Greater Boston Area.
-----BEGIN PGP SIGNATURE-----
Version: 2.6.2
Comment: Finger me for a public key.
iQB1AwUBMtVUXI0DAXSiDippAQFD/gL/fgrL9iXLt5w4lmtTNUbxlns/NbE7AFqR
C48zNsWgJzimY2j12Jlq4dSFmJJLDz0GaawLcNZYDv1xijG4LEw7gSn99iKor3ke
h4jgPG8AgMTWp+eAh64B/MsaYUma9jQs
=HjUO
-----END PGP SIGNATURE-----