Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I'm building an open source SMSC from scratch; it's almost finished, The SRI and the forwardSM operations are working, but I still have few things to do for the receiving part. I've built the SS7 stack already, but I'm using DB for saving the TCAP transactions IDs to be updated later to get/generate responses. My approach is this: I created memory table (heap table), saved the TCAP TID in the database, then compared the received TCAP TID with the TIDs saved in the database and then decide whether to end the TCAP session or continue.

What is the best way to implement it? I'm thinking of doubly linked list that holds the TCAP TID. Am I going towards the right direction, or should I use another technique other than database or D-linked list? Should I leave it as it is, and let the database do the job for saving the TIDs?

Please note that I'm using SCTP implementation available on Linux (lsctp) as a transport protocol, the language I'm using is C and the DB is MYSQL.

share|improve this question
1  
Welcome to Programmers! You are using a lot of domain-specific terminology not everybody ma be familiar with in your question, but if I have deciphered it correctly, you are asking whether to store some message ID (TCAP ID) in a doubly-linked-list or a database to perform some look-up on when receiving another TCAP ID. Is that correct? If so, could you edit your question to be more generally applicable, because as it stands now, it is likely to be closed as too localized. –  PersonalNexus Dec 31 '11 at 17:36
    
Yes you're right, It's about storing message ID (TCAP ID) on a D-linked list or a DB(using heap table). TCAP-ID is used to maintain a session open between two SS7 entities. –  Ammar Hameed Dec 31 '11 at 18:11
add comment

1 Answer

Your question about appropriate choice of data structure doesn't provide quite enough detail about the problem you are trying to solve. Questions I would have asked in-person when trying to help you include:

  1. How many active sessions do you expect on average and maximum? That is, what's the N-value we need to worry about for the asymptotic complexity of operations?
  2. What are your response latency and memory consumption constraints?
  3. What is the relative mix of add/remove/query operations?
  4. Can you make a reasonably reliable estimate of which order TIDs will arrive in? (If yes, most operations on our data structure will be at the beginning or end, with little need for searching operations)
  5. Do you know for sure that all the TIDs you are holding will eventually receive an update? (Alternative: some items in your in-memory data structure correspond to TIDs you will never see again, because you're not always guaranteed to see an "end-session" event).

Not knowing these things (I'm not familiar with the application domain or the "size" if your planned system) I can only make what I think are reasonable guesses, but please forgive me if I guess wrong.

I'm going to guess:

  1. Many; allow the resulting data structure to fill memory if necessary.
  2. Latency requirements are in the 1ms-100ms range, meaning that we should ideally avoid disk accesses - in this case, avoidable database operations. Memory consumption requirements are much vaguer but let's assume we can't use a sparse data structure (for example a hash table). The rationale here is that if we have some amount of memory, there are probably other kinds of data it's more useful to keep in it than this information (again, if I knew more about your application domain this would help...)
  3. add:remove:query ratios are close to 1:1:1.
  4. Assume we can't predict the TID arrival order
  5. Assume that we can't be sure that we'll see all sessions neatly closed (so we need to adopt a data structure which allows some kind of separate housekeeper process to occasionally delete stale TIDs).

If these guesses are more or less right, I'd probably use a heap. Heaps are denser than linked lists and much denser than hash tables. Each heap entry would contain the TID as the key and whatever other payload data your have (you didn't say; but if there is no additional payload, that's fine too).

Using a heap means that all the operations (insert, delete, lookup) are O(log(N)). If queries are much more common than insert/delete, then we should consider paying memory to get speed (for example using a hash table; the operations are O(1) but more memory is used). Contrariwise, if your data structure might get very large, you should consider using a B-heap instead of a regulat binary heap, because it's kinder to the virtual-memory system. See You're Doing It Wrong by Poul-Henning Kamp, which describes a cache system with some (rather small) degree of similarity to what you're doing.

If your heap is represented as an array, you may have trouble growing it beyond the initial size of the array. Using the traditional scheme of doubling the size of the array when it fills will amortize the overhead of the copying operation so that we can maintain logarithmic performance. But it would mean that occasionally, one of the insert operations will take much, much longer than others. The other property of a heap is that most implementations are designed for single-threaded use. If either of these two issues are going to be a problem for you, consider using a balanced tree instead of a heap.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.