Multiple POSIX Timers with handlers: how to?

[premudriy]

Hello everyone,



I'm working on a course project. I need to implement a "pseudo TCP" on top of UDP protocol. I've already implemented sequence and error handling concepts of TCP. Now I need to deal with timers and retransmission of packets, i.e. when acknowledgement for a sent packet doesn't arrive after X seconds, then retransmit that given packet.

My plan for timers is as following:

1. Create many posix timers (one per packet)
2. When timer runs out, call a handling function with a parameter that specifies which packet number to retransmit.


The problem is that I can't find a definitive explanation anywhere about how to do it. Some guides talk about "timer_connect(handlerFunction, ...)", but "man timer_connect" doesn't exist in Fedora 11.


Can anyone shed some light on how do I create an arbitrary number of timers with handling function? Or maybe there's another way to implement TCP timeout/retransmission concept?


Thank you beforehand!

[JN4OldSchool]

Yes, I could shed some light on the TCP timeout concept but...I am not a guru, so...

[lewis41]

I'm not Linus Tornvalds, alias a guru, and so more superficially and with poor knowledge of the subject, I would create a list of objects, with the appropriate functions to manage it (insert, delete, read, write objects, timer, ecc.) and one/more global functions to manage the list.
Or if I would have much free time, I would hack some good code written by others.

[RupertPupkin]

This is fairly simple to do, but since I'm not a guru then premudriy doesn't want my help.

[premudriy]

LOL. Ok. I see what's wrong - the title says for gurus only. I didn't think it's going to be so touchy.



Ok. The title means: If you will answer this question, then you're officially a guru. Will this work?




But seriously, I didn't mean the title to be accepted as it is by some people. I just wanted a concrete help and not just "Look in the man pages!" answers.

[scottro]

I'll change the title, as folks seem to be, as you say, overly touchy. Maybe that will help.

[premudriy]

Ok, Scottro, thank you. Next time I'll try make more politically correct titles :-) I'm sorry for it's touchiness. I didn't mean to.

[stevea]

This is probably all you should need
man timer_create
Creating a timer per packet is a profligate use of resources. OK for a "toy" example but totally unrealistic.

Let me expand on Lewis41 suggestion.

Create linked list method so you can keep the packet handles in ordrer of expiration time.
You need to be able to insert packets in expiration time order,
remove packet by ID when you get an ACK,
there is one timer needed and it is always set to expire in the "soonest" packet expiration time - the EX-time of the list head. Whenever the list head changes, then the timer TO-time is set to the new value.
If the timer times out (typically it will be reset to a later time then the head is ACKed) then you take the head packet ,resend it, update the resend count, perform any OOB messaging and re-enter it on the queue with a new expiration time.
If you are SunMS compliant you may want to resend forever awaiting an ACK, otherwise you probably want to use a less idealistic approach and signal an out of band error after some resource limit (total time or number of retries for example) That feature should be user definable on a per-socket bases (think about why).

[premudriy]

Stevea, thanks for replying.

This sounds like a very good way to do it and with only one timer.

[stevea]

Oops - use man 3p setitimer since you most certainly want signal notification when the timeout occurs.
You'll need to think about how to partition the work between the signal handler and the main process, perhaps using a semaphore from sighandler to the main ...

Another thought - if your main process/thread is normally waiting on input/output, you can use the timeout parameter of the select syscall man 3p select to represent the 'next' packet timeout time.

[jpollard]

I also suggest that there be a maximum number of outstanding packets....

You wouldn't want to be sending a 3GB file to a system that goes down... and end up with 80% of your memory
with nothing but timeouts and packets to send...

[premudriy]

Thanks, guys! I'm implementing "go-back-N" concept of TCP and my Window Size is set to a specific number. I won't read more than Window Size packets into a memory from file.

[stevea]

Originally Posted by jpollard

I also suggest that there be a maximum number of outstanding packets....

You wouldn't want to be sending a 3GB file to a system that goes down... and end up with 80% of your memory with nothing but timeouts and packets to send...

The number of packets awaiting ack must be limited, but NOT by a asserting a maximum count. There are only 2^16 ports, each with a finite window. Any attempt to send can and will cause the process to block until resources are available. Whether you can "stall the sender" for this toy example isn't clear, that might be too much work, but having a maximum count isn't a solution unless you say EXACTLY how you handle the "out of resources" case.

TCP is for RELIABLE comm, so you are required to either have 100% assurance that the data got through - or else error/fail. It is NOT the "mostly reliable" layer. You cannot choose to ignore some packets - that is unacceptable.

The Nagle algorithm is relevant here. It prevents the next pack send until the previous receives an ACK. It's more complicated than that, it may cause packet data mergers or it may block, but .... read the book.

Interestingly when I worked on router technology with some real network gurus a few years ago, in a router or switch, it is acceptable to drop TCP packets as a means of creating "backpressure". If you drop a packet the resend will eventually occur. So in an oversubscribesd situation that router would preferentially drop TCP packets (observing QoS if present). You can't do that as a host.

[jpollard]

Yup - the application specified is using UDP, which doesn't block. That calls for
something external to invoke the stall. In this case, I'd suggest a NAK when the
count reaches the limit, and drop the data.

[stevea]

Originally Posted by jpollard

Yup - the application specified is using UDP, which doesn't block. That calls for
something external to invoke the stall. In this case, I'd suggest a NAK when the
count reaches the limit, and drop the data.

So much misinformation in such few lines ....

/UDP certainly does block, tho' for a smaller set of reasons. This "toy" case is presumable implemented in userspace making the forced sleep on write of sending 'processes' (if they even exist in this toy example) more difficult than with a syscall to the kernel. There is a world of difference between brocking the sender process which his reasonable to avoid congesiton, and blocking the network traffic which makes congestion worse ((think of the backed-up traffic and all the resends)).

/There is no such thing as a NACK in TCP. There is an ACK flag and count in every header.

/The host (that the OP is implementing) is forbidden from dropping outbound packets, otherwise the link is not RELIABLE. A *ROUTER* can do this for traffic congestion since the host must resend. A host can drop received packets, but these don't occupy space in the queue - so they don't solve the queue resource problem - they are just delivered to the reader processes.

/Setting a hard limit on outbound packets is a foolish approach as already mentioned. Instead you create a resource pool and arrange to never exhaust it by applying backpressure and congestion control. Especially the use of sliding-windows for the transmit. Yes there is a real resource limit, but hitting it means at least connection failure if not system failure. You need to manage the resource to avoid the limits.

You clearly don't understand TCP. You don't get to re-design it by the seat of your pants - the standard is the rule ...

Read Stevens TCP/IP illustrated or
http://tools.ietf.org/html/rfc793
http://tools.ietf.org/html/rfc1122
http://tools.ietf.org/html/rfc3168
http://tools.ietf.org/html/rfc896

http://tools.ietf.org/html/rfc813

There are a great many RFCs a full implementation would need. It's very likely this class projects doesn't handle packet fragmentation & reassembly, and probably not windowing and traffic congestoin and QoS. OO-Order recontrstuction and the ack/timeout scheme is quite aq bit.