Topic: Defining Reliable / Unreliable and Ordered / Unordered

[contingencyplan]

Here is my current understanding of Reliable vs. Unreliable and Ordered vs Unordered. I'm hoping whitelynx can correct any misunderstandings I have on the subject.

Reliable vs. Unreliable: This refers to whether the packet must arrive at the destination. If a packet marked as "reliable" fails to arrive at the destination, then we must request that the packet be resent.

Ordered vs. Unordered: This refers to whether the packets must arrive (or at least be interpreted) in a specific order.

TCP is an ordered, reliable protocol, to the point that it will outright block (i.e., stop receiving data and just keep sending resend requests) if it misses something. RUDP is ordered reliable as well (I think), but it won't block if it misses a packet. Rather, it collects the numbers that it didn't receive in the past N time units and send a resend request all at once (in the EAK segment).

So assuming the above info is right (I honestly expect it to be wrong, personally, but whatever), how would an ordered, unreliable or unordered, reliable packet behave? Can we have such a thing as an unordered, reliable packet, since we have to know which packets actually made it to the destination?

These are the kinds of questions that keep me up at night...  :-\


TCP is a reliable protocol, and will outright block (or at least wait) until it has received the packet it is missing. It seems to me that RUDP will not block if it fails to receive a packet; rather, it will continue receiving packets but will still request the packet from the sender.

[Morgul]

From what I remember in my networking class, here's how the others would work.

Let's assume the following:

Packets sent: 1, 2, 3, 4, 5.
Packets Received: 1, 2, 4.

Unordered Reliable:

A request would be sent for packet 3 and 5. When these arrived, the data would be: 1, 2, 4, 3, 5. (No order, but we make sure we get all of them.)

Unordered Unreliable:

Simply do nothing. We have 1, 2, 4.

Ordered Unreliable:

Now, I'm not sure this exists. However, if it did, it would look like Unordered Unreliable, in all cases but one. Let's say we sent 1, 2, 3, 4, 5. however packets 3 and 5 are lost, and 2 is delayed. We would then have 1, 4, 2. No resend requests are sent, and the packets are out of order.

Make any sense now?

--Chris

[contingencyplan]

Okay, so for unordered, unreliable, we'd use straight UDP, and for ordered reliable, we'd use TCP?

[Morgul]

yup.

[whitelynx]

Here is my current understanding of Reliable vs. Unreliable and Ordered vs Unordered. I'm hoping whitelynx can correct any misunderstandings I have on the subject.

Reliable vs. Unreliable: This refers to whether the packet must arrive at the destination. If a packet marked as "reliable" fails to arrive at the destination, then we must request that the packet be resent.

Almost... It just means that we have to try to provide a guarantee that it will get there. (with reasonable limits) There are two ways of doing this: requesting resends of missing packets, (perfect for ordered reliable packets because you know that one's missing when a sequence number is skipped) or resending any packet after a given timeout, unless an ACK for that packet has been received. (which could be useful for unordered reliable sending, but which may need to be discussed first.)

Ordered vs. Unordered: This refers to whether the packets must arrive (or at least be interpreted) in a specific order.

Exactly.

TCP is an ordered, reliable protocol, to the point that it will outright block (i.e., stop receiving data and just keep sending resend requests) if it misses something. RUDP is ordered reliable as well (I think), but it won't block if it misses a packet. Rather, it collects the numbers that it didn't receive in the past N time units and send a resend request all at once (in the EAK segment).

Actually, from my understanding, they both work the way that you described RUDP. TCP will queue up out-of-order packets until the previous packets arrive, and then pass them all to the application once they do. The biggest difference between TCP and RUDP is that RUDP cuts out a lot of the unused "features" of TCP.

So assuming the above info is right (I honestly expect it to be wrong, personally, but whatever), how would an ordered, unreliable or unordered, reliable packet behave? Can we have such a thing as an unordered, reliable packet, since we have to know which packets actually made it to the destination?

Yes, we can, using the second technique for making reliable packets that I described above. We could also rely on sequence numbers, but simply pass all packets up to the application when they come in instead of waiting for older packets when an out-of-order one arrives. I'm not sure which approach would be best for us.

Okay, so for unordered, unreliable, we'd use straight UDP, and for ordered reliable, we'd use TCP?

Actually, no, on both counts. We wouldn't use straight UDP because we need some sort of header in there so we can figure out what type of packet it's supposed to be. (since we can have multiple packet types on each socket... take a look at the channel/socket thoughts in the IRC log on that page) For the same reason, we can't use TCP at all for this; we'd have to create a new Socket to be able to do that. Instead, I'd like all 4 of these sub-protocols to be usable on the same socket at the same time, by opening a channel for each.

[Jove]

An important difference I have not seen mentioned is that UDP is packet based and TCP stream based. For the upper layers, in TCP there is no such thing as a packet. You data will arrive as one continuous stream of bytes. From the headers i've seen in your spec, you are not prepared to handle that (since there is no way to see how long the data segment of a packet is, only the header). Also, there is no guarantee that if you receive data it will be a complete packet.

Another feature I haven't seen mentioned either is the difference between delay sensitive and not-delay sensitive data. For a game, I think that might be important. Especially if you consider mixing TCP and UDP as a transport layer. TCP can introduce extra delays because it will queue sending data in an attempt to compose larger packets (Naggle).

[contingencyplan]

So what you're saying is that RaptorNL, which (for now) will sit on top of the sockets, will not have to worry about the individual TCP packets; rather, the socket library will deliver them as a stream? Can you point me to some specific sources for this information?

The delay and non-delay sensitive data is definitely a good point. I'm not sure whether we'd want to add those in or not (and if so, how we'd go about doing it - perhaps as a flag). I'm assuming that "immediate" packets (those that cannot be delayed) would only be sent over a reliable channel (either TCP or RUDP), so we could just have a flag on the reliable channels to say whether to delay packets sent over them, or have a flag in the individual message to that effect. Any further thoughts on this?

Also, what is "Naggle"?

[Jove]

My references are my experience and the linux man page socket (7), first paragraph:

       This  is  an  implementation  of  the  TCP protocol defined in RFC 793,
       RFC 1122 and RFC 2001 with the NewReno and SACK  extensions.   It  pro-
       vides  a  reliable, stream-oriented, full-duplex connection between two
       sockets on top of ip(7), for both v4 and v6 versions.   TCP  guarantees
       that the data arrives in order and retransmits lost packets.  It gener-
       ates and checks a per-packet checksum  to  catch  transmission  errors.
       TCP does not preserve record boundaries.

It explicitly states that record boundries are not respected. The RFCs (the protocol specifications) will tell you the same.

Nagle (I spelled it wrong the first time) is an algorithm that delays outgoing TCP packets in an attempt to join them into 1 larger packet. This is done to improve bandwidth efficiency for interactive traffic. It is turned on or off with the TCP_NODELAY flag. Even if you do not use Nagle, records can get joined or split by network delays, MTU limitations, retransmissions, cpu load and so on. (if you write out 2 x 1000 bytes in rapid sequence, it will most likely arrive as 1 packet with 1460 and 1 with 540 bytes. This may or may not be presented to you as 1 read of 2000 bytes or 2 seperate reads).

About the delay sensitive, I would definatly NOT send them over the reliable channel. An example of delay sensitive data could be trajectory data of objects in your world. Retransmission would only make the delay worse. For a retransmission, the game would pause, then it would jump, in the second case, there will be a jump too, but it will be smaller. The jumps can be made smaller by sending more updates, but that would increase the chance for packet loss...

PS: As a side issue, it is the kernel that does the TCP handling, it is not the socket library itself.

[Morgul]

Regarding 'Delay' vs 'Imminent' that's basically the same as reliable vs unreliable. In the first networking layer we wrote, we used unreliable transmissions for the 'Imminent' stuff, and reliable for the important 'Delay' stuff. With the construction of the game, we're doing everything locally, and updating as we get information from the server. That means that we can stand to miss information all together for up to a second or more without issues.

--chris