Anonymous Monk has asked for the wisdom of the Perl Monks concerning the following question:

Hi,

I am trying to take two pieces of unique information and encode them into a 9 digit number with a static seed. I also need the ability to decode it given the proper seed. The two pieces of information are..

1) An IP addresss
2) A 9 digit session id

I thought about first base 10 encoding the IP address using the following code... 
unpack "N", pack "C4", split /\./, "64.58.79.230"

[download]
and then just appending the 9 digit session id.

However, due to project restrictions, I need the final number to be a unique result, no more than 9 digits, and it must be a non-floating point positive integer. Is there some cipher or mathematical function that I could use to get this result? Speed is also an issue so the fastest algorithm would be preferred.

An example function would be... 
$uniq_result = encode("static_seed","64.58.79.230","542158235");
($IP,$sessionid) = decode("static_seed",$uniq_result);

[download]
Security is not an issue really, so a seed might not even be necessary. Also, the ability to encode is much more important than the ability to decode. So if encoding without the ability to decode is all I can get, than I'll make do. As long as no unique combination of IP address and sessionid will produce the same 9 digit number, I'm ok.

Any help would be greatly appreciated. I've been racking my brain trying to come up with a solution.

Thanks

-scrill

Replies are listed 'Best First'.
Re: integer encoder/decoder
by dga (Hermit) on Mar 13, 2003 at 18:57 UTC

    You cannot guarantee no collisions since one of your input spaces is the 9 digit number and your output space is the same size. You can probably code to reduce the possibility. If you could use another base like 64 then your output space is larger than your input space.

    Specifically your input space is basically a 30 bit quantity + a 32 bit quantity which you want to store uniquely in a 30 bit space. For each value in the output, there are 2**32 inputs which will give you that output.

    If you could use base64 then you could get a 62 bit quantity SID.IP into 9 character places.

    If you used for example Digest::MD5 you can get an almost certainly unique quantity base16 in 32 bytes or base64 in 22 bytes. This uses an existing module implementing a strong digest algorithm which is the math problem you are wanting to solve.

    In summary you can make up a program to map the ip address into the existing session id and you can work to avoid collisions but ultimately the space is too small to never have a collision

    If you can throw the unique ids away after a time then by using time generated as a small factor you could probably get a system which would not be likely to collide for the lifetime of the session id. This is the only solution that seems to not have a collision hazard but the larger the time interval the more likely a collision.

[reply]
      Thats an interesting idea. You certainly have more of a grasp on it than I do. Unfortunately, my knowledge of base64 and even base10 encoding is extremely limited. The unmap call in my original post was used from an example in another node.

      I looked into Digest::MD5, but found that the smallest result that could be produced from any of the digest functions was 16 bytes from binary digest. The other prduced too many characters.

      What I really need is an example of exactly how to do this, if it's possible. My experience with map/unmap is sparse.

      Could you post an example? Don't get me wrong, I'm not looking for a handout, but an example with an explanation would help me learn.

      Thanks
[reply]
Re: integer encoder/decoder
by jasonk (Parson) on Mar 13, 2003 at 18:31 UTC

    You want to encode a nine digit number and an ip address into a nine digit number in such a way that you can recreate the original data on demand? And something makes you belive this is possible? If your requirement was to get it down to nine characters and didn't require them to be numeric, then you could do it, but if you want to encode 9+ digits of numbers into 9 digits of numbers, it is going to be an irreversible procedure.

    We're not surrounded, we're in a target-rich environment!
[reply]
      I realized that might be the case, which is why I stated that I could live without the ability to decode the number, as long as the resulting number is unique and 9 digits or less.

      For example...

      I dont want "IP1" and "Sessionid1" to ever produce a 9 digit number that can be produced by any other "IP" and "Sessionid" combination. The encoding is really the vital part.

      Any ideas?
[reply]
        I dont want "IP1" and "Sessionid1" to ever produce a 9 digit number that can be produced by any other "IP" and "Sessionid" combination. The encoding is really the vital part.
        This is not possible. You want a 9-digit session-ID number (about 30 bits of information) to be added to an IP address (about 14 or 15 bits of info, depending on how you throw out invalid network numbers), resulting in only a 9-digit number (about 30 bits of info again).

        You can't do it. You can't fit 45 bits of info into 30 bits of output, without some of them overlapping.

        You'll need to think of a different strategy. You can't even fit it into 9 hex characters (36 bits of info). If you insist on nine output symbols, you'll need to use some larger base, something with at least 5 bits of info per symbol, like base 36 encoding with 0-9 and a-z.

        -- Randal L. Schwartz, Perl hacker
        Be sure to read my standard disclaimer if this is a reply.

[reply]
Re: integer encoder/decoder
by bart (Canon) on Mar 13, 2003 at 22:24 UTC
    The way you can do it, is by storing the data in a database, with an auto-increment index, and use that index as the reference. You can get the original data back by looking it up in the same database.
[reply]
      Hehe,

      Nice idea. Unfortunately it won't work in my situation.

      Here are the specifics of my project. I have many NASes throughout my network. Each NAS has users online identified by a 9 digit session id. I access relevant user info via SNMP. Every specified interval a user dump is taken from each NAS and populated into a database. The application I am writing is a snmpd fronted to the database. So a client can walk my snmpd and get a list of their users. However, for simplicity and for certain functions to work, they need to be able to referrence a uniqe session id. Since the session id's on the NASes can be the same, I need to generate a new sessionid based on the NAS ip and sessionid.

      I can't use an auto-incrementing id from a database table since the users are dumped every 5 min or so and I can't guarantee that the same id with be associated with the same user after each dump, and I'd also have to worry about users connecting and disconnecting. That is why I need to be able to generate a new sessionid. The 9 digit limitation is due to net-snmp. The maximum number of an oid level is 2147483647.

      The idea is for the 9 digit sessionid to be part of the oid, so they can easily reference their users, instead of an auto-incrementing number. 
      enterprises.10000.10182.398820668
enterprises.10000.10182.548131831
enterprises.10000.10182.872131658

      [download]
      If it was an auto-incrementing number, that number would change when users connect/disconnect and unless they walk the tree again, they might access the wrong users info. It's more complicated than I am explaining it, but I think you get the basic idea of what I need.

      I realize that encoding the IP and sessionid into a 9 digit number is not possible now, due to the reply's above. All I really want now is a way to take the IP and sessionid, do whatever to it, and get a 9 digit number that I is unique to that specific IP and sessionid. I don't care if I can't go backwards. Understand?
[reply]
[d/l]

        yes, i think i understand. but i don't see the reason to limit yourself to a 9 digit sessionid. just use more than one OID slot and give the client people a sessionid with a dots in it.

        enterprise.10000.10182.192.168.254.12.3888206
 for NAS 192.168.254.12 session 3888206

or take IP and convert to two 16bit numbers and do

...10182.49128.64782.3888206 
 ( give person 49128.64782.3888206 as sessionid )

        [download]

        i've seen both. another really cool thing i came across recently is to use a timestamp as part of the OID, like ...1.3.1.$time.$id = $value. then you can keep a history of values in your MIB and the user can walk your table from ...1.3.1 and get all of the history or walk the table from ...1.3.1.$last and get all of the updates that have happend since they last walked the table.

        Update: if all of your NAS IPs are in the same subnet (/16 or less) you could just forget about the first two octets. give them: 64782.3888206 as the session id if all your NAS are in 192.168.0.0/16.

[reply]
[d/l]

Back to Seekers of Perl Wisdom