CS402: Computer Communications and Networks

• when there are no losses
• when the third and seventh segments are lost
• when the second, fourth, sixth, eighth,... acknowledgments are lost
• when the third and fourth data segments are reordered (i.e., the fourth arrives before the third)

18. Same question when using selective repeat instead of go-back-n. Note that the answer is not necessarily the same.

19. Consider two high-end servers connected back-to-back by using a 10 Gbps interface. If the delay between the two servers is one millisecond, what is the throughput that can be achieved by a transport protocol that is using 10,000 bits segments and a window of

• one segment
• ten segments
• hundred segments

20. Consider two servers are directly connected by using a b bits per second link with a round-trip-time of r seconds. The two servers are using a transport protocol that sends segments containing s bytes and acknowledgments composed of a bytes. Can you derive a formula that computes the smallest window (measured in segments) that is required to ensure that the servers will be able to completely utilise the link?

21. Same question as above if the two servers are connected through an asymmetrical link that transmits bu bits per second in the direction used to send data segments and bd bits per second in the direction used to send acknowledgments.

22. The Trivial File Transfer Protocol is a very simple file transfer protocol that is often used by disk-less hosts when booting from a server. Read the TFTP specification in RFC 1350 and explain how TFTP recovers from transmission errors and losses.

23. Is it possible for a go-back-n receiver to inter-operate with a selective-repeat sender? Justify your answer.

24. Is it possible for a selective-repeat receiver to inter-operate with a go-back-n sender? Justify your answer.

25. The go-back-n and selective repeat mechanisms that are described in the book exclusively rely on cumulative acknowledgments. This implies that a receiver always returns to the sender information about the last segment that was received in-sequence. If there are frequent losses or reordering, a selective repeat receiver could return several times the same cumulative acknowledgment. Can you think of other types of acknowledgments that could be used by a selective repeat receiver to provide additional information about the out-of-sequence segments that it has received. Design such acknowledgments and explain how the sender should react upon reception of this information.

26. The goodput achieved by a transport protocol is usually defined as the number of application layer bytes that are exchanged per unit of time. What are the factors that can influence the goodput achieved by a given transport protocol?

27. When used with IPv4, Transmission Control Protocol (TCP) attaches 40 bytes of control information to each segment sent. Assuming an infinite window and no losses nor transmission errors, derive a formula that computes the maximum TCP goodput in function of the size of the segments that are sent.

28. A go-back-n sender uses a window size encoded in a n bits field. How many segments can it send without receiving an acknowledgment?

29. Consider the following situation. A go-back-n receiver has sent a full window of data segments. All the segments have been received correctly and in-order by the receiver, but all the returned acknowledgments have been lost. Show by using a time sequence diagram (e.g. by considering a window of four segments) what happens in this case. Can you fix the problem on the go-back-n sender?

30. Same question as above, but assume now that both the sender and the receiver implement selective repeat. Note the the answer will be different from the above question.

31. Consider a transport that supports window of one hundred 1250 Bytes segments. What is the maximum bandwidth that this protocol can achieve if the round-trip-time is set to one second? What happens if, instead of advertising a window of one hundred segments, the receiver decides to advertise a window of 10 segments?

32. Explain under which circumstances a transport entity could advertise a window of 0 segments?

33. To understand the operation of the TCP congestion control mechanism, it is useful to draw some time sequence diagrams. Let us consider a simple scenario of a web client connected to the Internet that wishes to retrieve a simple web page from a remote web server. For simplicity, we will assume that the delay between the client and the server is 0.5 seconds and that the packet transmission times on the client and the servers are negligible (e.g., they are both connected to a 1 Gbps network). We will also assume that the client and the server use 1 KBytes segments.

34. Several MBytes have been sent on a TCP connection and it becomes idle for several minutes. Discuss which values should be used for the congestion window, slow start threshold and retransmission timers.

35. To operate reliably, a transport protocol that uses Go-back-n (resp. selective repeat) cannot use a window that is larger than 2ⁿ− 1 (resp. 2ⁿ−1 ) segments. Does this limitation affects TCP? Explain your answer.

36. Consider the simple network shown in the figure below. In this network, the router between the client and the server can only store on each outgoing interface one packet in addition to the packet that it is currently transmitting. It discards all the packets that arrive while its buffer is full. Assuming that you can neglect the transmission time of acknowledgments and that the server uses an initial window of one segment and has a retransmission timer set to 500 milliseconds, what is the time required to transmit 10 segments from the client to the server. Does the performance increases if the server uses an initial window of 16 segments instead?

Figure 4.60: Simple network

37. The figure below describes the evolution of the congestion window of a TCP connection. Can you find the reasons for the three events that are marked in the figure?

38. The figure below describes the evolution of the congestion window of a TCP connection. Can you find the reasons for the three events that are marked in the figure?

Figure 4.61: Evolution of the congestion window

Figure 4.62: Evolution of the congestion window

39. A web server serves mainly HTML pages that fit inside 10 TCP segments. Assuming that the transmission time of each segment can be neglected, compute the total transfer time of such a page (in round-trip-times) assuming that:

• the TCP stack uses an initial window size of 1 segment
• the TCP stack uses an initial window size of three segments

40. RFC 3168 defines mechanism that allow routers to mark packets by setting one bit in the packet header when they are congested. When a TCP destination receives such a marking in a packet, it returns the congestion marking to the source that reacts by halving its congestion window and performs congestion avoidance. Consider a TCP connection where the fourth data segment experiences congestion. Compare the delay to transmit 8 segments in a network where routers discards packets during congestion and a network where routers mark packets during congestion.

4.5.2 Practice

1. The socket interface allows you to use the UDP protocol on a Unix host. UDP provides a connectionless, unreliable service that in theory allows you to send SDUs of up to 64 KBytes.

• Implement a small UDP client and a small UDP server (in Python, you can start from the example provided in http://docs.python.org/library/socket.html but you can also use C or Java)
• run the client and the servers on different workstations to determine experimentally the largest SDU that is supported by your language and OS. If possible, use different languages and Operating Systems in each group.

2. By using the socket interface, implement on top of the connectionless, unreliable service provided by UDP a simple client that sends the following message shown in the figure below.

In this message, the bit flags should be set to 01010011b, the value of the 16 bits field must be the square root of the value contained in the 32 bits field, the character string must be an ASCII representation (without any trailing 0) of the number contained in the 32 bits character field. The last 16 bits of the message contain an Internet checksum that has been computed over the entire message.

Upon reception of a message, the server verifies that:

• the flag has the correct value
• the 32 bits integer is the square of the 16 bits integer
• the character string is an ASCII representation of the 32 bits integer
• the Internet checksum is correct

If the verification succeeds, the server returns a SDU containing 11111111b. Otherwise it returns 01010101b

Your implementation must be able to run on both low endian and big endian machines. If you have access to different types of machines (e.g. x86 laptops and SPARC servers), try to run your implementation on both types of machines.

Figure 4.63: Simple SDU format

3. The socket library is also used to develop applications above the reliable bytestream service provided by TCP. We have installed on the cnp3.info.ucl.ac.be server a simple server that provides a simple client-server service. The service operates as follows:

• the server listens on port 62141 for a TCP connection
• upon the establishment of a TCP connection, the server sends an integer by using the following TLV format:
• the first two bits indicate the type of information (01 for ASCII, 10 for boolean)
• the next six bits indicate the length of the information (in bytes)
• An ASCII TLV has a variable length and the next bytes contain one ASCII character per byte. A boolean TLV has a length of one byte. The byte is set to 00000000b for true and 00000001b for false.
• the client replies by sending the received integer encoded as a 32 bits integer in network byte order
• the server returns a TLV containing true if the integer was correct and a TLV containing false otherwise and closes the TCP connection

Implement a client to interact with this server in C, Java or Python.

4. It is now time to implement a small transport protocol. The protocol uses a sliding window to transmit more than one segment without being forced to wait for an acknowledgment. Your implementation must support variable size sliding window as the other end of the flow can send its maximum window size. The window size is encoded as a three bits unsigned integer.

The protocol identifies the DATA segments by using sequence numbers. The sequence number of the first segment must be 0. It is incremented by one for each new segment. The receiver must acknowledge the delivered segments by sending an ACK segment. The sequence number field in the ACK segment always contains the sequence number of the next expected in-sequence segment at the receiver. The flow of data is unidirectional, meaning that the sender only sends DATA segments and the receiver only sends ACK segments.

To deal with segments losses, the protocol must implement a recovery technique such as go-back-n or selective repeat and use retransmission timers. You can select the technique that best suite your needs and start from a simple technique that you improve later.

Figure 4.64: Segment format

This segment format contains the following fields:

• Type: segment type
• 0x1 DATA segment.
• 0x2 ACK segment
• WIN: the size of the current window (an integer encoded as a 3 bits field). In DATA segments, this field indicates the size of the sending window of the sender. In ACK segments, this field indicates the current value of the receiving window.
• Sequence: Sequence number (8 bits unsigned integer), starts at 0. The sequence number is incremented by 1 for each new DATA segment sent by the sender. Inside an ACK segment, the sequence field carries the sequence number of the next in-sequence segment that is expected by the receiver.
• Length: length of the payload in multiple of one byte. All DATA segments contain a payload with 512 bytes of data, except the last DATA segment of a transfer that can be shorter. The reception of a DATA segment whose length is different than 512 indicates the end of the data transit.
• Payload: the data to send

The client and the server exchange UDP datagrams that contain the DATA and ACK segments. They must provide a command-line interface that allows to transmit one binary file and support the follow- ing parameters:

sender <destination_DNS_name> <destination_port_number> <window_size> <input_file>
receiver <listening_port_number> <window_size> <output_file>

In order to test the reactions of your protocol against errors and losses, you you can use a random number generator to probabilistically drop received segments and introduce random delays upon the arrival of a segment.

Packet trace analysis

When debugging networking problems or analyzing performance problems, it is sometimes useful to capture the segments that are exchanged between two hosts and to analyze them.

Several packet trace analysis tools are available, either as commercial or open-source tools. These tools are able to capture all the packets exchanged on a link. Of course, capturing packets require administrator privileges. They can also analyze the content of the captured packets and display information about them. The captured packets can be stored in a file for offline analysis.

tcpdump is probably one of the most well known packet capture software. It is able to both capture packets and display their content. tcpdump is a text-based tool that can display the value of the most important fields of the captured packets. Additional information about tcpdump may be found in tcpdump(1). The text below is an example of the output of tcpdump for the first TCP segments exchanged on an scp transfer between two hosts.

21:05:56.230737 IP 192.168.1.101.54150 > 130.104.78.8.22: S 1385328972:1385328972(0) win 65535 <m
21:05:56.251468 IP 130.104.78.8.22 > 192.168.1.101.54150: S 3627767479:3627767479(0) ack 13853289
21:05:56.251560 IP 192.168.1.101.54150 > 130.104.78.8.22:. ack 1 win 65535 <nop,nop,timestamp 27
21:05:56.279137 IP 130.104.78.8.22 > 192.168.1.101.54150: P 1:21(20) ack 1 win 49248 <nop,nop,tim
21:05:56.279241 IP 192.168.1.101.54150 > 130.104.78.8.22: . ack 21 win 65535 <nop,nop,timestamp 2
21:05:56.279534 IP 192.168.1.101.54150 > 130.104.78.8.22: P 1:22(21) ack 21 win 65535 <nop,nop,t
21:05:56.303527 IP 130.104.78.8.22 > 192.168.1.101.54150:. ack 22 win 49248 <nop,nop,timestamp 1
21:05:56.303623 IP 192.168.1.101.54150 > 130.104.78.8.22: P 22:814(792) ack 21 win 65535 <nop,nop

You can easily recognize in the output above the SYN segment containing the MSS, window scale, timestamp and sackOK options, the SYN+ACK segment whose wscale option indicates that the server uses window scaling for this connection and then the first few segments exchanged on the connection.

wireshark is more recent than tcpdump. It evolved from the ethereal packet trace analysis software. It can be used as a text tool like tcpdump. For a TCP connection, wireshark would provide almost the same output as tcpdump. The main advantage of Wireshark is that it also includes a graphical user interface that allows to perform various types of analysis on a packet trace.

Figure 4.65: Wireshark: default window

The wireshark window is divided in three parts. The top part of the window is a summary of the first packets from the trace. By clicking on one of the lines, you can show the detailed content of this packet in the middle part of the window. The middle of the window allows you to inspect all the fields of the captured packet. The bottom part of the window is the hexadecimal representation of the packet, with the field selected in the middle window being highlighted.

wireshark is very good at displaying packets, but it also contains several analysis tools that can be very useful. The first tool is Follow TCP stream. It is part of the Analyze menu and allows you to reassemble and display all the payload exchanged during a TCP connection. This tool can be useful if you need to analyse for example the commands exchanged during a SMTP session.

The second tool is the flow graph that is part of the Statistics menu. It provides a time sequence diagram of the packets exchanged with some comments about the packet contents. See blow for an example.

Figure 4.66: Wireshark: flow graph

The third set of tools are the TCP stream graph tools that are part of the Statistics menu. These tools allow you to plot various types of information extracted from the segments exchanged during a TCP connection. A first interesting graph is the sequence number graph that shows the evolution of the sequence number field of the captured segments with time. This graph can be used to detect graphically retransmissions.

Figure 4.67: Wireshark: sequence number graph

A second interesting graph is the round-trip-time graph that shows the evolution of the round-trip-time in function of time. This graph can be used to check whether the round-trip-time remains stable or not. Note that from a packet trace, Wireshark can plot two round-trip-time graphs, One for the flow from the client to the server and the other one. wireshark will plot the round-trip-time graph that corresponds to the selected packet in the top wireshark window.

Figure 4.68: Wireshark: round-trip-time graph

Emulating a network with netkit

Netkit is network emulator based on User Mode Linux. It allows to easily set up an emulated network of Linux machines, that can act as end-host or routers.

Note: Where can I find Netkit?

Netkit is available at http://www.netkit.org. Files can be downloaded from http://wiki.netkit.org/index.php/Download_Official, and instructions for the installations are available here: http://wiki.netkit.org/download/netkit/INSTALL .

There are two ways to use Netkit: The manual way, and by using pre-configured labs. In the first case, you boot and control each machine individually, using the commands starting with a “v” (for virtual machine). In the second case, you can start a whole network in a single operation. The commands for controlling the lab start with a “l”. The man pages of those commands is available from http://wiki.netkit.org/man/man7/netkit.7.html

You must be careful not to forgot to stop your virtual machines and labs, using either vhalt or lhalt.

A netkit lab is simply a directory containing at least a configuration file called lab.conf, and one directory for each virtual machine. In the case the lab available on iCampus, the network is composed of two pcs, pc1 and pc2, both of them being connected to a router r1. The lab.conf file contains the following lines:

pc1[0]=A
pc2[0]=B
r1[0]=A
r1[1]=B

This means that pc1 and r1 are connected to a “virtual LAN” named A via their interface eth0, while pc2 and r1 are connected to the “virtual LAN” B via respectively their interfaces eth0 and eth1.

The directory of each device is initially empty, but will be used by Netkit to store their filesystem.

The lab directory can contain optional files. In the lab provided to you, the “pc1.startup” file contains the shell instructions to be executed on startup of the virtual machine. In this specific case, the script configures the interface eth0 to allow traffic exchanges between pc1 and r1, as well as the routing table entry to join pc2.

Starting a lab consists thus simply in unpacking the provided archive, going into the lab directory and typing lstart to start the network.

Note: File sharing between virtual machines and host

Virtual machines can access to the directory of the lab they belong to. This repertory is mounted in their filesystem at the path /hostlab.

In the netkit lab (exercises/netkit/netkit_lab_2hosts_1rtr_ipv4.tar.tar.gz, you can find a simple Python client/server application that establishes TCP connections. Feel free to re-use this code to perform your analysis.

Note: netkit tools

As the virtual machines run Linux, standard networking tools such as hping, tcpdump, netstat etc. are available as usual.

Note that capturing network traces can be facilitated by using the uml_dump extension available at http://kartoch.msi.unilim.fr/blog/?p=19 . This extension is already installed in the Netkit installation on the stu- dent lab. In order to capture the traffic exchanged on a given ‘virtual LAN’, you simply need to issue the command vdump <LAN name> on the host. If you want to pipe the trace to wireshark, you can use vdump A | wireshark -i - -k

1. A TCP/IP stack receives a SYN segment with the sequence number set to 1234. What will be the value of the acknowledgment number in the returned SYN+ACK segment?

2. Is it possible for a TCP/IP stack to return a SYN+ACK segment with the acknowledgment number set to 0? If no, explain why. If yes, what was the content of the received SYN segment.

3. Open the tcpdump packet trace exercises/traces/trace.5connections_opening_closing.pcap and identify the number of different TCP connections that are established and closed. For each connection, explain by which mechanism they are closed. Analyze the initial sequence numbers that are used in the SYN and SYN+ACK segments. How do these initial sequence numbers evolve? Are they increased every 4 microseconds?

4. The tcpdump packet trace exercises/traces/trace.5connections.pcap contains several connection attempts. Can you explain what is happening with these connection attempts?

5. The tcpdump packet trace exercises/traces/trace.ipv6.google.com.pcap was collected from a popular website that is accessible by using IPv6. Explain the TCP options that are supported by the client and the server.

6. The tcpdump packet trace exercises/traces/trace.sirius.info.ucl.ac.be.pcap Was collected on the departmental server. What are the TCP options supported by this server?

7. A TCP implementation maintains a Transmission Control Block (TCB) for each TCP connection. This TCB is a data structure that contains the complete “state” of each TCP connection. The TCB is described in RFC 793. It contains first the identification of the TCP connection:

• localip: the IP address of the local host
• remoteip: the IP address of the remote host
• remoteport: the TCP port used for this connection on the remote host
• localport: the TCP port used for this connection on the local host. Note that when a client opens a TCP connection, the local port will often be chosen in the ephemeral port range ( 49152 <= localport <= 65535 ).
• sndnxt: the sequence number of the next byte in the byte stream (the first byte of a new data segment that you send will use this sequence number)
• snduna: the earliest sequence number that has been sent but has not yet been acknowledged
• rcvnxt: the sequence number of the next byte that your implementation expects to receive from the remote host. For this exercise, you do not need to maintain a receive buffer and your implementation can discard the out-of-sequence segments that it receives
• sndwnd: the current sending window
• rcvwnd: the current window advertised by the receiver

Using the exercises/traces/trace.sirius.info.ucl.ac.be.pcap packet trace, what is the TCB of the connection on host 130.104.78.8 when it sends the third segment of the trace?

8. The tcpdump packet trace exercises/traces/trace.maps.google.com was collected by con- taining a popular web site that provides mapping information. How many TCP connections were used to retrieve the information from this server?

9. Some network monitoring tools such as ntop collect all the TCP segments sent and received by a host or a group of hosts and provide interesting statistics such as the number of TCP connections, the number of bytes exchanged over each TCP connection,... Assuming that you can capture all the TCP segments sent by a host, propose the pseudo-code of an application that would list all the TCP connections established and accepted by this host and the number of bytes exchanged over each connection. Do you need to count the number of bytes contained inside each segment to report the number of bytes exchanged over each TCP connection?

10. There are two types of firewalls 30: special devices that are placed at the border of campus or enterprise networks and software that runs on endhosts. Software firewalls typically analyze all the packets that are received by a host and decide based on the packet’s header and contents whether it can be processed by the host’s network stack or must be discarded. System administrators often configure firewalls on laptop or student machines to prevent students from installing servers on their machines. How would you design a simple firewall that blocks all incoming TCP connections but still allows the host to establish TCP connections to any remote server?

11. Using the netkit lab explained above, perform some tests by using hping3(8). hping3(8) is a command line tool that allows anyone (having system administrator privileges) to send special IP packets and TCP segments. hping3(8) can be used to verify the configuration of firewalls 33 or diagnose problems. We will use it to test the operation of the Linux TCP stack running inside netkit.

12. The Linux TCP/IP stack can be easily configured by using sysctl(8) to change kernel configuration variables. See http://fasterdata.es.net/TCP-tuning/ip-sysctl-2.6.txt for a recent list of the sysctl variables on the Linux TCP/IP stack. Try to disable the selective acknowledgments and the RFC1323 timestamp and large window options and open a TCP connection on port 7 on the server by using:manpage:telnet‘(1)‘. Check by using tcpdump(1) the effect of these kernel variables on the segments sent by the Linux stack in netkit.

13. Network administrators sometimes need to verify which networking daemons are active on a server. When logged on the server, several tools can be used to verify this. A first solution is to use the netstat(8) command. This command allows you to extract various statistics from the networking stack on the Linux kernel. For TCP, netstat can list all the active TCP connections with the state of their FSM. netstat supports the following options that could be useful during this exercises:

• -t requests information about the TCP connections
• -n requests numeric output (by default, netstat sends DNS queries to resolve IP addresses in hosts and uses /etc/services to convert port number in service names, -n is recommended on netkit machines)
• -e provides more information about the state of the TCP connections
• -o provides information about the timers
• -a provides information about all TCP connections, not only those in the Established state

On the netkit lab, launch a daemon and start a TCP connection by using telnet(1) and use netstat(8) to verify the state of these connections.

A second solution to determine which network daemons are running on a server is to use a tool like nmap(1). nmap(1) can be run remotely and thus can provide information about a host on which the system administrator cannot login. Use tcpdump(1) to collect the segments sent by nmap(1) running on the client and explain how nmap(1) operates.

14. Long lived TCP connections are susceptible to the so-called RST attacks. Try to find additional information about this attack and explain how a TCP stack could mitigate such attacks.

15. For the exercises below, we have performed measurements in an emulated 31 network similar to the one shown below.

Figure 4.69: Emulated network

The emulated network is composed of three UML machines 32: a client, a server and a router. The client and the server are connected via the router. The client sends data to the server. The link between the router and the client is controlled by using the netem Linux kernel module. This module allows us to insert additional delays, reduce the link bandwidth and insert random packet losses.

We used netem to collect several traces:

exercises/traces/trace0.pcap
exercises/traces/trace1.pcap
exercises/traces/trace2.pcap
exercises/traces/trace3.pcap