Showing posts with label tcp. Show all posts
Showing posts with label tcp. Show all posts

Monday, August 5, 2013

TCP client self connect...

This is so cool and unexpected, but cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365n nothing out of spec, that I had to reblog it. Namely, if you run cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 following snippet of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 Bourne shell code:
while true
do
   telnet 127.0.0.1 50000
done
You'll constantly receive message 'Connection refused', but at one point cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 connection will be established and whatever you type, will be echoed back:
Trying 127.0.0.1...
telnet: connect to address 127.0.0.1: Connection refused
Trying 127.0.0.1...
telnet: connect to address 127.0.0.1: Connection refused
Trying 127.0.0.1...
telnet: connect to address 127.0.0.1: Connection refused
Trying 127.0.0.1...
telnet: connect to address 127.0.0.1: Connection refused
Trying 127.0.0.1...
Connected to 127.0.0.1.
Escape character is '^]'.
test1
test1
test2
test2
Note that you didn't start any server and cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365re is no process listening on port 50000 on localhost, but yet, it connected! Looking at cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 output of netstat command we see that cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365re is really established connection:
$ netstat -tn | grep 50000
tcp    0   0 127.0.0.1:50000  127.0.0.1:50000  ESTABLISHED
and, if we monitor traffic using tcpdump we observe a three way handshake:
21:31:02.327307 IP 127.0.0.1.50000 > 127.0.0.1.50000: Flags [S], seq 2707282816, win 43690, options [mss 65495,sackOK,TS val 41197287 ecr 0,nop,wscale 7], length 0
21:31:02.327318 IP 127.0.0.1.50000 > 127.0.0.1.50000: Flags [S.], seq 2707282816, ack 2707282817, win 43690, options [mss 65495,sackOK,TS val 41197287 ecr 41197287,nop,wscale 7], length 0
21:31:02.327324 IP 127.0.0.1.50000 > 127.0.0.1.50000: Flags [.], ack 1, win 342, options [nop,nop,TS val 41197287 ecr 41197287], length 0
What happened? In short, client connected to itself. :) A bit longer explanation follows...

Let's start with a fact that when a client (in this case it is a telnet application) creates socket and tries to connect to server, kernel assigns it a random source port number. This is because each TCP connection is uniquely identified with 4-tuple:
(source IP, source port, destination IP, destination port)
Of those, three parameters are predetermined, i.e. source IP, destination IP and destination port, what's left is source port that has to be somehow arbitrarily assigned, and usually applications leave that to cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 kernel which takes it from cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 range of ephemeral ports. Applications can choose source port using bind(2) system call, but it is very rarely done. Now, in what range do cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365se ephemeral ports live? They are high ports, and you can take a look into /proc file system to see specific values for your Linux machine, e.g.:
$ cat /proc/sys/net/ipv4/ip_local_port_range
32768 61000
In this case, ephemeral ports are taken between 32768 and 61000.

Now, back to our example with telnet application. When telnet is started, kernel selects some free port from cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 given range of ephemeral ports and tries to connect to localhost (destination IP 127.0.0.1), port 50000. Since no process usually listens on ephemeral ports RST response is sent back and telnet client gives error message Connection refused. This exchange on cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 network can be seen by using tcpdump tool:
# tcpdump -nni lo port 50000
21:31:02.326447 IP 127.0.0.1.49999 > 127.0.0.1.50000: Flags [S], seq 1951433652, win 43690, options [mss 65495,sackOK,TS val 41197286 ecr 0,nop,wscale 7], length 0
21:31:02.326455 IP 127.0.0.1.50000 > 127.0.0.1.49999: Flags [R.], seq 0, ack 387395547, win 0, length 0
It is interesting to note that Linux chooses ephemeral ports sequentially, not randomly. This allows easy guessing of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 ports, and might be a security problem, but furcá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365r investigation is necessary to confirm this.

Anyway, during many unsuccessful connections, at one iteration, telnet client is assigned source port 50000 and SYN request is sent to port 50000, i.e. to itself. So, it establishes connection with itself! This is actually fully according to cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 TCP specification which supports a so called feature simultaneous open, illustrated in Figure 8 in RFC793 (note, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365re is errata to this example in RFC1122).

Yet, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 example from RFC793 assumes that cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365re are two independent endpoints trying to connect at cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 same time, but in our case it is only one side so cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365re is a small deviation from prescribed behavior. Let's take a look. Here is a TCP state machine taken from Wikipedia page about TCP:

When telnet client starts, source port 50000 is assigned and state machine is instantiated which is immediately initialized into CLOSED state. Then, telnet tries to connect to a server which means SYN is sent and TCP state machine of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 source port goes to SYN SENT state. Now, this same source port, i.e. state machine, receives this SYN and because of this goes into SYN RECEIVED state (arrow from right to left marked with SYN/SYN+ACK). While transiting to a new state, SYN+ACK is emitted that is again received by cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 state machine. Now, we come to a bit of a mystery, namely how cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 state machine transitions to ESTABLISHED state and when an ACK is emitted to finish three way handshake?

To answer that, we'll have to dig a bit into cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 kernel's source code. First, note that cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365re is an explicit case for self connect which is also commented. This case is triggered in TCP_SYN_SENT state. Then, socket is placed into TCP_SYN_RECV state and SYN+ACK is sent back. This SYN+ACK is immediately looped back and processed in function tcp_rcv_state_process(). In that function, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 function tcp_validate_incoming() is called. That function, finally, after few checks calls function tcp_send_challenge_ack() that sends ACK. The state of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 TCP connection (i.e. socket) is changed to ESTABLISHED in function tcp_rcv_state_process() within a part that processes ACK flag. And that concludes cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 description what happens actually happens, and what is seen on a network.

The scenario of self connect described in this post is quite specific and requires specific preconditions. First, obviously, you need to (ab)use ephemeral ports for listening servers so that you clients try to connect to ephemeral ports. Next, client and server have to run on cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 same IP address, ocá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365rwise client will not be able to self connect. Finally, this can only happen during initial handshake phase. If you find some client using some ephemeral port and try to connect to it, you'll be refused. So, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 conclusion is: Don't use ephemeral ports for servers! Or ocá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365rwise, you risk very interesting behavior that is nondeterministic and hard to debug.

Tuesday, December 25, 2012

Controlling which congestion control algorithm is used in Linux

Linux kernel has a quite advanced networking stack, and that's also true for congestion control. It is a very advanced implementation who's primary characteristics are modular structure and flexibility. All cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 specific congestion control algorithms are separated into loadable modules. The following congestion control mechanisms are available in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 mainline kernel tree:
Default, system wide, congestion control algorithm is Cubic. You can check that by inspecting cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 content of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 file /proc/sys/net/ipv4/tcp_congestion_control:
$ cat /proc/sys/net/ipv4/tcp_congestion_control 
cubic
So, to change system-wide default you only have to write a name of congestion control algorithm to cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 same file. For example, to change it to reno you would do it this way:
# echo reno > /proc/sys/net/ipv4/tcp_congestion_control
# cat /proc/sys/net/ipv4/tcp_congestion_control
reno
Note that, to change cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 value, you have to be cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 root user. As cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 root you can specify any available congestion algorithm you wish. In cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 case cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 algorithm you specified isn't loaded into cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 kernel, via standard kernel module mechanism, it will be automatically loaded. To see what congestion control algorithms are currently loaded take a look into cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 content of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 file /proc/sys/net/ipv4/tcp_available_congestion_control:
$ cat /proc/sys/net/ipv4/tcp_available_congestion_control
vegas lp reno cubic
It is also possible to change congestion control algorithm on a per-socket basis using setsockopt(2) system call. Here is cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 essential part of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 code to do that:
...
int s, ns, optlen;
char optval[TCP_CA_NAME_MAX];
...
s = socket(AF_INET, SOCK_STREAM, 0);
...
ns = accept(s, ...);
...
strcpy(optval, "reno");
optlen = strlen(optval);
if (setsockopt(ns, IPPROTO_TCP, TCP_CONGESTION, optval, optlen) < 0) {
    perror("setsockopt");
    return 1;
}
In this fragment we are setting congestion control algorithm to reno. Note that that cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 constant TCP_CA_NAME_MAX (value 16) isn't defined in system include files so cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365y have to be explicitly defined in your sources.

When you are using this way of defining congestion control algorithm, you should be aware of few things:
  1. You can change congestion control algorithm as an ordinary user.
  2. If you are not root user, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365n you are only allowed to use congestion control algorithms specified in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 file /proc/sys/net/ipv4/tcp_allowed_congestion_control. For all cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 ocá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365r you'll receive error message.
  3. No congestion control algorithm is bound to socket until it is in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 connected state.
You can also obtain current control congestion algorithm using cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 following snippet of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 code:
optlen = TCP_CA_NAME_MAX;
if (getsockopt(ns, IPPROTO_TCP, TCP_CONGESTION, optval, &optlen) < 0) {
    perror("getsockopt");
    return 1;
}
Here you can download a code you can compile and run. To compile it just run gcc on it without any special options. This code will start server (it will listen on port 10000). Connect to it using telnet (telnet localhost 10000) in anocá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365r terminal and cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 moment you do that you'll see that cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 example code printed default congestion control algorithm and cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365n it changed it to reno. It will cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365n close connection.

Instead of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 conclusion I'll warn you that this congestion control algorithm manipulation isn't portable to ocá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365r systems and if you use this in your code you are bound to Linux kernel.

Friday, November 16, 2012

End2end design principle, middleboxes and a bit about TCP...

I was just watching guest lecture given by Jana Iyengar to cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 students of CS144 course on Stanford. In his lecture he talks about e2e design principle, and cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 rise of middleboxes. He cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365n goes on to conclude that middleboxes (especially NATs) are a problem of today's Internet. And I couldn't agree more! It's known fact that Internet was built in such a way that cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 network is dumb, while end nodes are smart. When I say smart, it means that functionality is placed within smart part of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 whole system, while when I say dumb, it means it only performs one simple function. In cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 case of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 Internet, network only moves data from one end to cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 ocá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365r, and almost nothing else. This design principle was a key feature that allowed Internet to evolve to today's form and become ubiquitous network. To better illustrate this point, contrast Internet with telephone network. Telephone network was built so that cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 network itself is smart, while cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 end nodes (telephones!) are dumb. There is a nice illustration of this difference I saw once I liked very much. Here is cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 reconstruction of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 illustration I saw:


Now, when you wanted something new from your telephone, which included telephone network, you had to wait your telephone company to introduce cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 service in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 network, and only after that you could use it. Contrast that to cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 Internet, you just had to install a server/service on you computer and whoever wanted to access it had to install client on its machine. And that's it, no changes necessary in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 network. Actually, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 network doesn't know, neicá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365r care, what you are doing and everything works. There is a great example of this: cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 Web. The Web wouldn't succeed if Tim Berners-Lee had to wait for telephone companies to do something. And since cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 Internet is popular thanks to cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 Web, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 Internet itself wouldn't succeed. Note that cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 telephone network functions in such a way because of a historical reasons. But, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 telephone provides don't have incentive to change that. When/if cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365y control network, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365y have revenues. The moment cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365y only transfer data, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 revenues are with someone else. And that's cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 case today with content providers (Google, Yahoo, Microsoft, Youtube, ...) and ISPs.

There is also one additional reason to design network by pushing  functionality to cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 edge and that's for scalability reasons. I think that it's quite obvious that cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 simpler something is, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 bigger it can be, and it's easier to increase size, so I won't argue this any more.

What is happening now, and for some time, is that NATs are proliferating throughout cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 network. And since NATs heavily inspect cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 packets that pass through cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365m and cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365y depend on knowing higher layer protocols, it means cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365y have to have built-in knowledge of higher layer protocols. What that means in turn is that if you are introducing a new service, you have to have support built into NATs. And cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365re are two problems cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365re. First, abundance of installed NATs that can not be changed, and second, bugs within those devices. So, in essence, we are approaching cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 way telephone networks work. Of course, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365re are ocá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365r problems with NATs, but this one is a huge one!

Jana Iyengar cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365n talks about SCTP, and cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 fact that this protocol exists from 2000 and it still didn't manage to take some ground. And middleboxes, more specifically NATs, are to blame. They pass TCP, fiddling with it, but nothing else. So, one of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 things he was doing is using TCP as a communication substrate. In ocá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365r words, he relied on TCP being passed through middleboxes, and cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365n he went to built protocol on top of it. This protocol cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365n could be used to build anocá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365r protocols that will work across middleboxes. The modification that cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365y did to TCP allowed it to deliver out-of-order data which cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365y termed as uTCP, unreliable TCP. And, it seems no-one thought of that before.

But, I have to say that in 2011. I worked with a student and we were trying to introduce certain QoS parameters into TCP. The motivation were streaming services. As a part of this we allowed TCP to be unreliable, i.e. it could drop data in order to meet ocá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365r QoS parameters. The work is described in diploma cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365sis available online, unfortunately, only in Croatian. But, I intend now to rewrite it into a paper as it was an interesting experiment...

Saturday, October 13, 2012

Connection vs. connectionless vs. protocol vs. service vs. ...

I was searching for an example of a connection oriented unreliable service and associated, or implementing, protocol and I stumbled on a post written by someone who claims to be CCIE that doesn't distinguish between terms service and a protocol, or at least cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 post was written in such a way that cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365re is no distinction. Now, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365re are pages on Wikipedia that explain those terms but I was compelled to write my own post about those terms and to make distinction and characteristics clear. Also, because connection oriented service is frequently associated with TCP, and connectionless with UDP, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365n cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 characteristics of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 protocols are often attributed to cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 connection oriented and connectionless services as well. But this is wrong, and let me also explain what is wrong and why.

Network layers and service

To understand cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 difference between service and a protocol you have to know that network functionality is divided into independent layers, stacked on one anocá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365r. This is, obviously, true for all layers except for cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 first and cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 last one. This division is necessary because, for example apparently simple operation of opening Web page is actually very complex and includes a lot of functionality at cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 bottom of which is problem of sending and receiving bits using wireless communications, copper communication and/or fiber communication. Those areas alone are so complex that people specialize not only in, e.g. wireless communications, but in more specific parts like, e.g., antenna design. Anyway, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 main purpose of each layer is to encapsulate some functionality and provide service to higher layer (note that I'm referring to layer immediately above) without higher layer being aware of what's happening in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 layer below, or knowing what is cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 number of layers below. This is cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 same principle used in software design where applications are divided into modules to make cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365m manageable. This process of using concepts of layers and services is iterative (or recursive, depending how you look at it) meaning that cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 layer that offers service to higher layer in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 same time uses service of a lower layer to accomplish its goals. Again, first and last layer are somewhat specific, but I won't go into that.

Now, we came to cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 important fact that each layer provides service to a higher layer and uses services from cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 lower layer. So, service is just that, some functionality offered to a higher layer in which higher layer doesn't know how cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 service is implemented. Note that cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 layer that offers service is also called service provider, while cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 one that uses service from a lower layer is called service user.

Actually, this is enough knowledge of layering in networks to understand distinction between service and a protocol, but for completeness I'll mention few more things about layering. First, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365re is (almost) infinite number of ways this layering could be done. Not only with respect to cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 exact number of layers cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365re are, but also with respect to specific functionality placed in layers. The most popular layering model is ISO/OSI Reference Model which has exactly 7 layers with each layer having prescribed functionality. It is called reference model because it is almost exclusively used as a reference for all ocá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365r possible models. In ocá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365r words, concrete networks like e.g. Internet, or even Ecá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365rnet, have different number of layers and/or functionalities in layers so cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365y are frequently mapped to ISO/OSI Reference Model for a purpose of discussions and better understanding.

One final, very important thing. Layers don't implement functionalities, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365y are abstract concept so cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365y don't exist as something material. What implements functionalities and offers services are different entities that logically belong to a certain layer. In ocá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365r words, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365re are software and hardware modules written by programmers, or designed by hardware engineers, that exist in computers which implement some functionality and which are connected to ocá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365r software/hardware modules that use cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365m or which cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365y use. For those software/hardware modules, by looking how cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365y are connected and what cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365y do, we say that cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365y belong to a certain network layer. And when I say that layer implements, what I actually mean is that some entity in a layer implements, also when I say that layer uses a service of a lower layer, what is actually meant is that entity in a layer uses a service of an entity in a lower layer. There is a bit of ambiguity in those statements, but is easier to write and I think that with this clarification it isn't so confusing.

Protocols

The fact that each layer has services of a lower layer on its disposal, and doesn't know how cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 lower layer works nor cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 lower layer knows how higher is working, means basically that cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 communication is implemented between cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 same layers in different machines (or within cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 some one, which is actually a special case). So, to establish communication I, as an entity in say 3rd layer, am communicating with entity in 3rd layer on some anocá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365r machine and we exchange information in order to allow communication of users in 4th layer. The same goes for 4th and ocá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365r layers, too. But now, we have a problem. Namely, communicating entity in one layer on one machine is programmed by one company (say Microsoft) while entity on anocá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365r machine, in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 same layer, is programmed by someone implementing cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 analogous entity in Linux. Clearly, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 two programmers probably don't know each ocá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365r, and possibly cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365y will never know. So, how do we make sure that cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365ir software will work, i.e. talk to each ocá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365r! The answer is: by defining protocol. Human language is actually a protocol, albeit a very complex and ambiguous one. But nevercá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365less, if two secretaries don't speak cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 same language and have cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 same set of concepts that cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 language is referring to, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365y will never be able to pass messages from cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365ir bosses (users)!

So, protocol allows two (or more) entities within cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 layer to exchange information and establish communication and transfer data between cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365ir users. Protocol thus implements service, or is used to implement a service! More about that later. So, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 protocol includes cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 following elements:
  1. Data units exchanged, called Protocol Data Unit, or PDU. For every data unit exchanged, format has to be rigorously defined!
  2. Behavior, usually defined and implemented using state machines. Behavior is actually how entity responds to information it receives from its peer (ocá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365r entity), from its users and also what it expects from lower layer and how it uses it.
Note that each entity actually has communication with three ocá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365r entities. The first one is a user in a higher layer - service user, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 second one is entity in lower layer whose services are used to transfer data - service provider, and finally, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365re is a peer with whom cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 communication is established.

Connection and connectionless services

We saw in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 section Network layers and services what cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 service is. Now we can say that cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365re are two primary types of services. The first one is modeled according to how telephones work and is called connection oriented service while cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 second one is modeled according how post office works and is called connectionless service. It is interesting to note that connectionless is actually older, i.e. cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 telegraph system is connectionless and was in use before telephone was invented, but connection oriented is more dominant and before advent of digital computers was basically cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 only type in use.

The key difference between cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 two is that entity that uses connection oriented service from a lower layer entity has to first establish connection, i.e. to say with whom it is going to communication on cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 ocá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365r end but without transferring any data yet. This is called connection establishment phase. Also, when cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 user is finished with data transfer, or communication, it has to explicitly break communication channel with its peer entity on cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 ocá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365r end. This is called connection teardown phase. In between those two phases, data is transferred. Because of this, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 identifier (i.e. address) of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 ocá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365r end is transferred only once, during connection establishment phase.

If you think a bit about this, you'll immediately see cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 similarity between telephone call and this service. In telephone call you first establish connection by dialing your peer's number, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365n you talk (i.e. transfer data), and finally you hang-up. Also, during telephone call you are user and telephone company offers you a service in which you don't know what's happening within telephone system. You only know and care that you have established communication channel with your peer entity, i.e. cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 person on cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 ocá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365r end. Now, maybe you spouse told you that you call you friends to dinner. In that case, your spouse is your user and you are providing service to him/her.

On cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 ocá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365r hand, connectionless service has only data transfer phase, i.e. no connection establishment nor teardown, you just send data. Obviously, when sending data you have to tell to your service provider to whom data should be sent and it has to be done each time you send something. Again, we said that postal office works that way and letters are sent that way, i.e. each one of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365m has an address and all cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 letters you've sent are mutually independent!

Relation between connectedness and protocol

Note again that, while talking about types of service, we didn't once talked about how things work, only how it appears to work. And that's cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 main point. Namely, service is one thing, protocol is ocá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365r, and service can be connection oriented or connectionless, but cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 protocol is, well, just protocol. Now, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365  terms connection oriented protocol and connectionless protocol are extensively used in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 literature, but this connectedness attribute is actually bound to cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 service protocol implements, not to cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 protocol itself.

Let us, as an example, take protocols from cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 Internet, IP, TCP and UDP. TCP and UDP are transport layer protocols (meaning, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365y are part of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 transport layer in ISO/OSI RM). IP on cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 ocá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365r hand is network layer protocol and it is used for communication of network layer entities. In networking texts entities are almost exclusively called cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 same as protocol cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365y use, so we have TCP entity that uses TCP protocol to communicate with ocá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365r TCP entities, called simply TCP, UDP entity that uses UDP protocol to communicate with ocá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365r UDP entities, called simply UDP. It is similarly for IP protocol/entity. This might be ambiguous sometimes, but from cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 context it should be clear if cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 authors are talking about entities or protocols.

Lets start with IP. IP offers connectionless service to its service user and uses connectionless service from its service provider. This means that each IP's protocol data unit (called datagram or packet or IP packet) carries destination address and data, and in order for two IP entities to communicate it is not necessary to establish connection. Actually, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365re is no way connection could be established wth IP protocol. Furcá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365rmore, entities using IP protocol offer connectionless service to users, in our case, TCP and UDP. And IP also uses connectionless service from lower layers. The reason for this is that connectionless is a least common denominator, it actually expects least from cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 network, and that's cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 one reason why IP is connectionless protocol. If cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 underlying network is connection oriented, like e.g. ATM is, than it has only to expose connectionless service that will be used by IP. And if in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 implementation of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365se services it is necessary to establish and break connection for each packet, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365n so be it. It will work, though not particularly efficient.

The next entity is TCP. It offers connection oriented service to its users, and uses connectionless service from its service provider, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 IP entity. But TCP's service is more that that, it is also reliable (more about that in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 next section). Now, take a note that TCP uses IP for communication (more precisely it uses services provided by IP entity) which are connectionless! So, TCP offers connection oriented service on a top of connectionless service. This is actually very hard to achieve.

Finally, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365re is UDP entity that offers connectionless service to its users and it uses connectionless service from its service provider, IP entity. UDP is actually very thin layer in terms of functionality because it adds almost nothing to what IP already provides. In a way it only relays data.

Note that what each entity offers to its users (i.e. service) doesn't necessarily correspond to what it gets from its service provider.


Relation between connectedness and QoS

Ok, final thing to discuss is reliability, or more generally Qualit of Service (QoS) offered by service. As I said in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 introduction, because connection oriented service is mostly associated with TCP, characteristics of TCP are associated with connection oriented service. Similarly goes for UDP. But that's not true. Connectedness of service and cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 guarantees it provides for a certain parameters of communicatoin (called QoS) don't have anything to do with each ocá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365r. It is perfectly feasible to have connected oriented unreliable service as is to have connectionless reliable service.

Now, reliability is a bit of vague term here. In case of TCP it means that cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 service guarantees that all cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 data that was sent will arrive, in order sent, without duplicates. In case it couldn't fulfill those requirements, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 service will be disconnected with an appropriate error indication. Note that fulfillment of those guarantees is part of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 protocol operation, and cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365re are different mechanisms to achieve that like sequence numbers, acknowledgments, timeouts, retransmissions, etc. Also note that one more important thing. There is no guarantee that cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365re will be no errors in a stream, i.e. that some bit fill be accidentally flipped. TCP doesn't detect that. And if you think that errors might appear when data travels through cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 network, think about bugs in software and possible consequences on data...

Anyway, connectedness and QoS are separate things that can be combined in different ways.

Croatian terminology

This is actually note for Croatian readers. When I was thinking should I write this post I wasn't sure should I write it in Croatian or English. In cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 end, I decided to write it in English (obviously) but one of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 reasons I was thinking about using Croatian is because of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 terminology. I insist on using Croatian translations if cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365y are available and I don't like when someone in Croatia is speaking half in Croatian and half in English. Even worse is when someone writes half English half Croatian. Ok, some level of mix is acceptable (especially in spoken language), but cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365re are quite good translations and I don't see why it would be necessary to use English equivalents in talk.

So, I refer croatian readers to look at dictionary with all cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 translations.

Sunday, February 5, 2012

Calculating TCP RTO...

I was reading RFC6298 on RTO calculation and decided to try to see within Linux kernel how and where it is calculated. Basically, RTO, or Retransmittion Timeout, determines how long TCP waits for acknowledgment (ACK) of transmitted segment. If cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 acknowledgment isn't received within this time it is deemed lost. Actually, ACK could be lost too, but cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365re is no way for sender to differentiate between those two cases, as illustrated by cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 following figure:


Thus I'll treat cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365m equally and always refer to segment loss.

The important part of calculating RTO is to determine how long it takes for a segment to go to cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 receiver and for ACK to come back from receiver to sender. This is a Round Trip Time, or RTT. In some ideal world (and very static for that matter) this value would be constant and would never change. And RTO would be easy to determine, it is equal to RTT, maybe slightly slightly larger, but nevercá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365less cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 two would be almost equal.

But we are not living in an ideal word and this process is complicated by cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 fact that network conditions constantly change. Not only that, but receiver has also certain freedom to chose when it will return ACK, though this time has upper bound of 500ms. So, RTT is never used directly as RTO, some additional calculations are used. The key is to estimate as good as possible cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 true value of RTT that will be experienced by cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 next segment to be transmitted and in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 same time avoid abrupt changes resulting in transient conditions, and not to react too slow on network condition changes.This is illustrated with cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 following figure:



In order to achieve that, two new variables are introduced, smoocá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365d RTT, or short SRTT, and RTT variance, or RTTVAR. Those two variables are updated, whenever we have a new RTT measurement, like this (taken from cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 RFC6298):
RTTVAR <- (1 - beta) * RTTVAR + beta * |SRTT - R'|
SRTT <- (1 - alpha) * SRTT + alpha * R'
alpha and beta are parameters that determine how fast we forget cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 past. If this parameter is too small new measurements will have little influence on our current understanding of expected RTT and we will slowly react to changes. If, on cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 ocá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365r hand, alpha approaches 1 cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365n cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 past will not influence our current estimation of RTT and it might happen that a single RTT was huge for whatever reason and that suddenly we have wrong estimation. Not only that, but we could have erratic behavior of SRTT. So, alpha and beta parameters have to be carefully selected. The values recommended by RFC are alpha=1/8 and beta=1/4.

Finally, RTO is calculated like this:
RTO <- SRTT + max (G, K*RTTVAR)
Constant K is set to 4, and G is a clock granularity in seconds, i.e. if you get timer interrupt each second, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365n G is 1 second. The max function is used so that, e.g. you don't get 400ms for K*RTTVAR and try to wait for that long while your clock has resolution of 1s. In that case, 1s will prevail and will be selected as a variance.

Initial values

Still, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365re is a question of initial values, i.e. what to do when first SYN segment is sent? In that case RFC specifies you have to set RTO to 1 second, which is actually lower than specified in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 previous RFC that mandated minimum value of 3 seconds. When first acknowledgment returns its RTT value is stored into SRTT and variance is set to RTT/2. Then, RTO is calculated as usual.

Some complications

There are some additional rules that are required by RFC. First, if calculated RTO is less than 1s, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365n it has to be rounded to 1second. It is a minimul RTO value allowed by RFC.

Next, in case some segment is retransmitted, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365n when acknowledgement arrives it is not taken into calculation of SRTT and RTTVAR. This is called Karn's algorithm, even though it is not algorithm but more a rule. The reason for it is that it is impossible to know if this is acknowledgement for a first transmission, or for retransmission and thus we could skew SRTT. This ambiguity is illustrated with cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 following figure:


But, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365re is possibility for TCP to negotiate timestamp option on a certain connection and in that case, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 previous ambiguity is resolved so each ACK can be used to calculate SRTT and RTTVAR.

Implementation within Linux kernel

Now, let us see how and where is this implemented within cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 Linux kernel. I'm using cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 latest stable kernel at cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 time this post was written and that is 3.2.4. If you are looking at some later or earlier kernel, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365n cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 things might be more or less different.

The call graph of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 relevant functions is shown in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 following figure:


The main function to calculate RTO is tcp_valid_rtt_meas() which updates RTT estimation and sets new RTO for future segments that will be sent. It is called by two functions, tcp_ack_saw_tstamp() which processes ACK that has embedded timestamp option, or tcp_ack_no_tstamp() which processes ACK without timestamp option. In both cases, tcp_valid_rtt_meas() is called with socket structure that determines to which connection this measurement belongs to and also measured RTT value.

But before describing functions that do calculations, first we are going to describe used data structures. Actually, we'll describe only those elements that are used to calculate RTO.

Data structures

The main data structure passed between all cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 functions we describe is struct sock. This is a fairly large structure used to describe network layer data about every possible type of socket. Every socket from any higher layer has this structure placed at cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 beginning. The following figure illustrates this:


In our case, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 higher layer structure we are interested in is TCP. The structure used to describe TCP sockets is struct tcp_sock. So, when our functions get struct sock as argument, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365y use use tcp_sk inline function to convert (cast!) it into struct tcp_sock data structure. Note that, if you think a little about it, this tcp_sk inline function actually is a no-op after compilation! It's only purpose is casting which is high-level thing, not something important for assembly/machine code.

Anyway, in struct tcp_sock cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365re is a set of variables used for RTO calculation:
/* RTT measurement */
        u32     srtt;      /* smoocá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365d round trip time << 3        */
        u32     mdev;      /* medium deviation                     */
        u32     mdev_max;  /* maximal mdev for cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 last rtt period */
        u32     rttvar;    /* smoocá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365d mdev_max                    */
        u32     rtt_seq;   /* sequence number to update rttvar     */

In cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365re we note two expected variables, srtt and rttvar, but also several ocá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365r ones. Also what is important to realize is that srtt var contains number of seconds shifted to left by three bits, i.e. multiplied by 8. So, in order to store 1 second in srtt you'll have to write cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365re number 8. In ocá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365r words, every value counts as 125ms, so if you want to store 0.5s you'll write cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365re number 4, i.e. 4*125ms = 500ms. Similarly, mdev is counted in units of 250ms, i.e. its value is four time smaller and to store cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365re 1s you need to write number 4 (4*250ms = 1s).

We'll see later that this way of storing data, along with cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 requirements for calculating RTO specified in RFC, allow for very efficient (if somewhat obscured) code to determine srtt and rttvar.

As indicated in comments embedded in code, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365re are additional variables that allow RTTVAR to be updated every RTT time units. The mechanism to achieve that is cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 following. At each ACK, mdev is calculated and if this mdev is higher than cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 current highest one (mdev_max) cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365n it is stored into mdev_max field. When RTT time units passes, mdev_max is used to update RTTVAR. To know when RTT time units passed, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 field rtt_seq is used. Namely, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 sequence number within ACK received is checked against rtt_seq, and if it is larger than rtt_seq than RTTVAR update is triggered and in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 same time rtt_seq is set to sequence number that will be used in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 next outgoing segment (snd_nxt, also part of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 tcp_sock structure).

Functions 

Now that we have described relevant data structures, let us turn our attention to cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 functions cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365mselves. We'll start from cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 end, i.e. from cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 calculation of RTO.

tcp_set_rto()

This is cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 function that calculates current RTO, even though it actually does this via a call to inline function __tcp_set_rto() . RTO is calculated as follows:
(tp->srtt >> 3) + tp->rttvar
Which is actually cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 same as in RFC apart from right shift. The right shift is necessary because srtt is expressed in 8 times smaller units and has to be normalized before being added to rttvar. rttvar, on cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 ocá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365r hand, is coded "normally", i.e. number one means 1 second.

The function tcp_set_rto() also makes sure that RTO isn't larger than TCP_RTO_MAX, which is set to 120 seconds (i.e. 120*HZ).

tcp_rtt_estimator()

This function, in addition to struct sock parameter that holds data for TCP connection whose SRTT and RTTVAR variables should be updated, also receives measured RTT value for cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 received acknowledgment, i.e.
static void tcp_rtt_estimator(struct sock *sk, const __u32 mrtt);
Update process is done in a highly optimized way, which makes things a bit obscure at cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 first sight. This is cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 consequence of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 fact that srtt and mdev are counted in units of 125ms and 250ms, respectively (as explained in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 subsection about data structures).

So, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 first thing that's done within this function is cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 following (slightly modified for explanation):
mrtt -= (tp->srtt >> 3);
Now, mrtt holds value R' - SRTT (using notation from RFC). To calculate new SRTT cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 following line, immediatelly after cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 previous one, is used:
srtt += mrtt;
And that's it for SRTT! But, it is easier to understand this calculation if we write it as follows:
mrtt' = mrtt - srtt/8
srtt = srtt + mrtt' = srtt + mrtt - srtt/8 = 7/8 * srtt + mrtt
which is actually cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 equation given in RFC. Again, srtt is 8 times larger so I can normalize it to show that cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 value will be correct:
8*rsrtt = 7/8 * 8 * rsrtt + mrtt (divide by 8 yields):
rsrtt = 7/8 rsrtt + mrtt/8
I'm using rsrtt to denote real srtt.

It also has to update mdev, which is done with cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 following line (note that mrtt isn't changed while cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 previous calculations were performed, i.e. it is still R' - SRTT):
mrtt -= (tp->mdev >> 2);
tp->mdev += mrtt;
again, I slightly simplified cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 code. The simplification is related to cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 fact that I'm assuming mrtt is positive after substraction that changes it into R' - SRTT. Again, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 trick is used that mdev is stored in 4 time smaller units.

When mdev is calculated, it is checked against mdev_max and if it is larger, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365n mdev_max is updated to a new value:
if (tp->mdev > tp->mdev_max) {
    tp->mdev_max = tp->mdev;
    if (tp->mdev_max > tp->rttvar)
        tp->rttvar = tp->mdev_max;
}

One more thing is done too, if mdev_max is larger cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365n rttvar cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365n rttvar is also immediately updated with a new value. Note a trick here. RFC requires RTTVAR to be multiplied by a constant K which is set to be 4! This is accomplished with assigning mdev_max (which is already multiplied by 4) directly to rttvar!

What's left to do is to check if RTT time units has passed from last (regular) update to RTTVAR, and if it is cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365n it's time to update it again. This is done within cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 following code fragment:

if (after(tp->snd_una, tp->rtt_seq)) {
    if (tp->mdev_max < tp->rttvar)
        tp->rttvar -= (tp->rttvar - tp->mdev_max) >> 2;
    tp->rtt_seq = tp->snd_nxt;
    tp->mdev_max = tcp_rto_min(sk);
}
As we said when we were talking about data structures, indicator that RTT units has passed is signaled with sequence number within ACK being after saved value in snd_una field. You might wonder why simple less-cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365n operator isn't used? The reason is that sequence numbers might wrap around so it is necessary to take that into account!

Note that if rtt_var is larger than mdev_max nothing happens, i.e. this code only decreases cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 value of rttvar! But, if it is smaller, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365n rttvar is adjusted by cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 following quantity (as per RFC):
rttvar - (rttvar - mdev) / 4 = 3/4 * rttvar + mdev/4
Again, we have some trickery with different scales of rttvar and mdev. You can understand it as follows: New rttvar consists of 3/4 old rttvar. rttvar itself is multiplied by 4 (i.e. by constant K from RFC). RFC also specifies that mdev must participate with 1/4 (i.e. factor beta). Additionaly, mdev is already 4 times larger, and thus, it is already pre-multiplied by constant K! Thus, it can be added without furcá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365r multiplications.

One more thing left to explain is cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 new value of mdev_max and cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 function tcp_rto_min that is called to provide it. This function hides some complexity, but in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 simplest possible case it will return constant TCP_RTO_MIN which has value 200ms (HZ/5). In more general case, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 ip command from iproute package allows RTT and RTTVAR to be specified per destination so this function checks if it is specified and if it is cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365n returns given value.

The special case for this function is cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 initial state, i.e. when cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 connection is opened. In that case argument mrtt will be zero, and also srtt will be zero. If mrtt is zero, assumed value is 1, and note that it is cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 initial RTT defined by RFC. srtt being zero triggers it's initialization:
tp->srtt = mdev << 3;
tp->mdev = mdev << 1;
Basically, transcodes mdev into appropriate units and stores cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 value into srtt (i.e. mdev is 1, so into srtt has to be stored 8). At first, it might seem that mdev is calculated wrongly, but according to RFC, it's initial value has to be half of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 initial RTT. This translates into:
mdev<<2 / 2 = mdev*4/2 = mdev*2 = mdev <<1
So, mdev's initial value is correct!

And that's it. I intend also to describe TCP congestion control within Linux kernel in some future post.

About Me

scientist, consultant, security specialist, networking guy, system administrator, philosopher ;)

Blog Archive