coding

Published on December 22nd, 2012 | by Luke Queenan

0

Reliable UDP – Research Proposal

This is a research proposal I wrote for one of my classes at BCIT. UDP, while extremely fast, is not a reliable program in the sense that the sender has no way of knowing if a packet has been received. This proposal examines various other attempts at making UDP reliable and then suggests a new technique.

Problem Statement

UDP is not a reliable protocol due to the absence of acknowledgments, retransmissions, or timeouts and ordering of received datagrams.

Sub-Problems

1. The UDP protocol (User Datagram Protocol) could be made reliable by implementing, at the very least, a packet acknowledgement system
2. Making the protocol reliable must not cause an overly adverse effect on the speed of the protocol.
3. The protocol will need to actively take advantage of the available throughput on the communication line.

The Hypotheses

It is hypothesized that UDP can be made reliable while maintaining its overall speed and making use of a given network line’s maximum throughput.

Delimitations

The proposal will not go into the details of congestion and flow control design and existing algorithms.

The proposal will not go into the details of constructing the actual protocol.

The study will not discuss the actual coding implementations of the protocol.

Definition of Terms

Reliability: Reliability means that the protocol would make a “best effort” to deliver the data being transferred using acknowledgments of received packets, retransmissions of un-acknowledged packets, timeouts for lost connections and retransmission timings, ordering of datagrams, and congestion / flow control.

Throughput: Throughput is number of successfully delivered packets over a given time on a network line.

MD5 Checksum: The Message Digest Algorithm checksum is used to verify the validity of downloaded file. After running the algorithm on the file, the output should match the result of running the algorithm on the original file. If it does not, the file is corrupted in some way.

Assumptions

The first assumption is that the reader has some basic knowledge regarding the TCP and UDP protocols and their uses.

The second assumption is that the reader knows terms related to the internetworking field.

Importance of the Study

TCP is plagued by congestion and flow control issues on network lines where the length and delay is long and on lines where there is packet loss. Thus, TCP does not always make efficient use of the line’s maximum throughput. Building on the speed of the User Datagram Protocol by implementing reliability would increase the average throughput

Existing Literature

The following five literature reviews support and demonstrate various aspects of the hypothesis.

The research article entitled “A Reliable UDP for Ubiquitous Communication Environments” outlines the creation of a reliable UDP, or RUDP. The goal was to construct a fast and reliable communication protocol in comparison to an ordinary TCP connection for communication between terminal devices and their servers. In this environment, the terminal devices initiate the communication to the server and maintain this session for a short duration in comparison to TCP. In this sense the communication is event driven, so the maximum number of simultaneous connections to the server should not exceed the number of connected devices. Note that the RUDP protocol does not implement any form of data flow management, which means that it does not attempt to deal with congestion issues it may encounter. In order to achieve reliable delivery of packets, the RUDP protocol uses the following:

• A three way handshake similar to TCP where a sessionID is created.
• The sessionID is then used for further communication.
• A timeout if no ACK is received to recover from packet loss.

After developing the RUDP protocol with these requirements, a comparison test was done between TCP and RUDP. The first test consisted of a client creating up to 12500 threads, each creating packets and connecting to the server. This was done for both TCP and RUDP. The results show that even with the addition of a connection setup and packet retransmission on top of UDP, the protocol is much faster than TCP, usually between a factor of three to twelve times. There was some noted packet loss under heavier traffic, but this never resulted in performance degradation even with the retransmission of lost packets. The TCP connection was also unable to process more than 4000 packets at a time due to the large number of sessions, but the RUDP protocol was not impacted by this and could handle 12500 simultaneous packets. The second test showed that even in-creasing packet sizes maintained the RUDP protocol’s four times speed in-crease over TCP. Once packet sizes reached 16384 bytes, both protocols reached their limitation due to saturating the network bandwidth. The article concludes that a reliable UDP protocol can be made while still maintaining speed. They found that under test conditions, the protocol was at least four times faster than that of TCP. The results of this article show promise for a UDP protocol that implements reliability through ACKs and retransmissions along with data flow management for increased reliability and robustness.

In the article “Performance Analysis of Reliable Dynamic Buffer UDP over Wireless Networks”, the authors pro-pose a more sophisticated method of ensuring UDP reliability. This method is aimed at maintaining the raw speed of UDP by implementing a Reliable Dynamic Buffer instead of the standard ACK and retransmission schemes. The article states that the existing reliable protocols, TCP and SCTP, do not meet the speed requirements needed for complex wireless networks. Given the higher error rate, wireless link costs, host mobility, longer delay, and lower bandwidth on wireless networks, a reliable protocol is needed. Therefore, they propose making the aforementioned improvement to UDP to meet this requirement. The Reliable Dynamic Buffer UDP entails adding an additional header to the data portion of the standard UDP header. This new header contains the following four fields.

• Sequence Number, similar to TCP’s sequence number where the initial value is randomized when the connection is opened.
• ACK Number, again similar to TCP’s ACK number where the last received packet is acknowledged.
• Buffer Size, indicates to the receiver the number of bytes to reserve for out of order packets before the expected packet arrives.
• A Checksum, which uses the same algorithm, used on UDP and TCP headers.

The article then goes on to make a comparison between the Reliable Dynamic Buffer UDP and Reliable UDP in terms of network throughput and delay in wireless networks. The test consisted of one wireless sending node and one wireless receiving node. The results of the test showed that the RDBUDP protocol outperformed the RUDP protocol in both aspects. The throughput test demonstrates the weakness of using ACKs, as the throughput is not smooth and jumps around quite a bit. It is also worth noting that neither of the protocols can actually reach the total throughput of the link. In terms of delay time, the RDBUDP protocol just barely outperforms the RUDP protocol. The article concludes that in terms of network throughput and delay in wireless networks, the Reliable Dynamic Buffer UDP outperforms the Reliable UDP. Unfortunately they do not provide any data on pure transfer rates. Further research would have to be done to determine if the RDBUDP outperforms the RUDP in other aspects as well. Given the complexity of implementing the RDUDP, using the buffer method may not provide enough benefits over straight RUDP.

The research article “SABUL: A High Performance Data Transfer Protocol” describes a protocol that uses both TCP and UDP to transfer control messages and data respectively. The article begins by outlining the issues with data transfers over TCP, especially with high bandwidth, long delay networks. In order to overcome these challenges, the research team designed a new protocol called SABUL, or Simple Available Bandwidth Utilization Library. It has the following seven objectives.

• Reliable data transfer
• Application level implementation
• Minimal impact on computing re-sources
• Maximum utilization of available bandwidth
• Respond to network changes
• Share bandwidth with other connections
• Memory copy avoidance

The protocol is unidirectional in terms of the following; data flow is one way from the sender to the receiver over UDP, while control information is sent one way from the receiver to the sender over TCP. The protocol’s functionality is relatively simple. The only modification made to the UDP packet is the addition of a 32 bit sequence number used for packet ordering and acknowledgements. The control connection responds to the sender throughout the data transfer with one of three types of packets.

• ACK: This packet acknowledges that all the packets up to the provided sequence number have been received.
• ERR: This packet is used as a negative acknowledgment for the provided sequence number.
• SYN: This packet is used to control sending rates and flow control.

Since the purpose of the SABUL protocol was to transfer data over high bandwidth and long delay networks, the performance testing done by the re-searches is all over these types of net-works. The results show that on half of the networks the protocol was tested on, it outperformed TCP and UDP in terms of throughput. On the other two net-works, it underperformed in comparison to standard TCP and UDP. However, the researchers believe that this was due to the CPU limits on the machines since the SABUL protocol requires more overhead. The hybrid approach of combining UDP and TCP to create a reliable network is an interesting approach. Building on the inherent reliability of TCP to ensure that control information is received allows for a simpler and smaller UDP packet allowing for more data to be transferred. This also scales well with a multithreaded approach to sending data since there are two independent connections. Further tests could be done with this protocol over normal networks to compare its speed with that of RUDP.

In the next literary review, entitled “Reliable Blast UDP: Predictable High Performance Bulk Data Transfer”, the researchers propose a protocol for transferring bulk amounts of data. This protocol, similar to the SABUL protocol, is designed to operate on long distance, high speed, high latency connections and not the general internet. However, like with the SABUL protocol, some interesting ideas are brought forward that further develop the idea of a reliable general use UDP protocol. The Reliable Blast UDP protocol discussed in the article uses a dual protocol approach. Essentially, a file is transmitted over the UDP connection in full while the receiver keeps track of which packets it has received. Upon finishing the file transfer, the sender sends a “done” command to the receiver over a TCP control connection. The receiver responds with an “acknowledgment” along with a bitmap tally of the received packets. The sender resends the missing packets and this process repeats until all the packets have been received. To minimize the loss of UDP packets, the send rate must not exceed the lowest bandwidth on the link and a relatively fast machine is required to receive the UDP packets in a timely fashion. The tests performed by the researchers show that packet loss can be as low as 2-7% when the available bandwidth is calculated correctly. There were three different RBUDP protocols designed, each having a different focus for storing and ordering the received packets. The three versions are broken down as follows:

1. RBUDP with Scatter/Gather Optimization: this version assumes that most packets will be received in the correct order and that few packets will be lost due to the bandwidth calculations. Packets are first stored in memory assuming this, then checked and only moved if they are out of position.
2. RBUDP without Scatter/Gather Optimization: this version checks each packet as it comes in and stores it in the correct location.
3. Fake RBUDP: this version does not move packets and is just used to measure the overhead of RBUDP in comparison to standard UDP.

The researchers concluded that RBUDP, when used with Scatter/Gather Optimization, functioned the best under most circumstances and will scale with faster networks. They also found that the protocol obtained the best results when used with large bulk transfers. This is due to the fact that receiving an acknowledgment through the TCP channel takes almost as long as the actual file transfers when using smaller files. The results of this study show that the performance of a dual protocol approach, using UDP for data and TCP for control signals, is tied to the speed at which acknowledgments can be returned to the sender over the TCP channel. Further research will have to be done to determine where the optimal balance is, and whether this technique would be a viable solution in creating a reliable UDP protocol for the general internet.

The final research article in this re-view, “A Class of Reliable UDP-based Transport Protocols Based on Stochastic Approximation”, the researchers pro-pose a different and more in-depth solution to the reliable UDP problem. The paper begins by describing the problems associated with the current TCP and UDP setup. TCP is not performing well due to low throughputs as a result of AIMD, or Additive in-crease/Multiplicative decrease. This is the algorithm used to control the flow of packets during a TCP connection. The outstanding issues with this design is that it does not stop reducing its throughput as long as there are packet loses, even if there are only a few. Thus, throughput is usually below its optimal value with TCP, more so over lines with high bandwidth and long delay. With UDP the problem is reliability, as discussed in the beginning of this proposal. The researchers also address some of the other reliable UDP protocols created, such as SABUL and RBUDP, both discussed previously. While both these protocols utilize available bandwidth far better than standard TCP, the nature in which they do this does usually starves other TCP traffic of bandwidth. There-fore, the researchers propose a new protocol, Reliable UDP-based Network Adaptive Transport, or RUNAT, based on UDP that has a TCP friendly flow control while still maintaining the fast speeds of UDP. In order to achieve this, the protocol implements a floating window-based transport model and uses a rate control strategy that is broken into three zones, outlined below.

1. Packet loss rate is low; transmission speed should be increased.
2. Maximum throughput with a non-zero loss rate.
3. Packet loss rate is high; trans-mission speed should be decreased.

The optimal zone is the center zone (two), with the edge zones (one and three) each attempting to push the throughput into the center zone. Once in the center zone, traffic is kept there using the dynamic Kiefer-Wolfowitz Stochastic Approximation method to control transmission speed. This method takes into account the randomness of network traffic and adjusts for it. The mathematics behind it is out of the scope of this proposal. The researchers went on to perform some tests using RUNAT on various different links. All the tests concluded that the protocol was easily able to adjust and make the most use of the available bandwidth on each link. The results show that RUNAT uses 2-5 times the throughput in comparison to TCP without negatively affecting concurrent traffic on the line. This study brings up some interesting points in regards to the congestion and flow control required in a reliable UDP protocol. If this new protocol is required to share the line with existing traffic, then it needs to take this into account and not obliterate other traffic due to its burst speed.

Data Collection

The data collection must obtain data on the protocol’s reliability in delivering packets, speed in comparison to UDP and TCP, along with the protocol’s ability to take advantage of the available throughput on the line. This will consist of an Observational study, where the protocols are observed systematically while maintaining objectivity. There will be two different test beds in order to test the protocol over two different types of network lines.

1. This test bed will consist of two machines, a server and a client, separated by an intercontinental link. This will test the protocol over a link that has a high bandwidth and long delay.
2. This second test bed will consist of two machines, a server and a client, connected on an isolated network using a switch. This will provide a setting more often found in most local area networks.

Data will be obtained from these test beds as objectively as possible. To ensure this, the following limits will be put in place.

• Reliability will be measured by performing a MD5 sum on the completed file transfer.
• The maximum available throughput for TCP and UDP on a network line will be measured using Iperf.
• The throughput of the new protocol will be measured using the complete transfer time and a tally of successfully received packets.

Methodology

This study is intended to develop a reliable UDP protocol that takes full advantage of a network line’s available throughput while maintaining the overall speed of UDP. An observational research methodology will be followed in testing this newly designed protocol against the requirements put forward in this proposal.

Once the new protocol has been developed, it will be tested for reliability. This will entail transferring a file between the two systems on each test bed. The file will then be checked for validity via a MD5 sum.

After the reliability of the protocol has been established, it will be tested for speed. This will entail transferring a file between the two systems on each test bed using UDP, TCP, and the proposed reliable UDP. The file transfer time will be recorded for each protocol and then compared.

Finally, the protocol’s ability to take advantage of the available throughput on the communication line will be tested. First, the maximum available throughput will be measured using Iperf. Then the protocol will be used in a file transfer, with the packets received and transfer time used to calculate the attained throughput.

Data Analysis

For each of the sub-problems discussed at the beginning of this proposal, specific data needs to be collected and interpreted. The required data and how it is to be interpreted will now be discussed.

The first sup-problem is making the UDP protocol reliable. The data to prove that the protocol is reliable will be obtained from an observational study where the protocol is used to transfer data between two machines over a local area network and an intercontinental link. The collected data will consist of a file that has been transferred using the protocol and a tally of the number of retransmitted packets. The tally of retransmitted packets will be used to determine if the protocol can still ultimately deliver a complete file. If there are dropped packets, and therefore hopefully retransmissions, the next part of the data is interpreted. The file portion of data will be interpreted by running a MD5 Checksum on the file. If the result of this checksum matches the result of the checksum on the original file even with dropped packets, then the protocol has reliably transmitted a file.

The second sub-problem is maintaining the overall speed of the underlying UDP protocol while implementing reliability. The data required for interpretation is the elapsed time of the file transfer from start to finish using the new protocol, along with the same statistic for ordinary TCP and UDP. With these values in hand, a comparison can be made between the three values. A successful time for the new protocol will appear between the UDP and TCP values, but leaning towards the UDP time. This is to be expected since the addition of reliability to the UDP protocol will increase its transmission time.

The third sub-problem is creating a protocol that will actively take advantage of the available throughput on the communication line. The data to be collected here consists of the maximum throughput of the line and then the achieved throughput of the new protocol. The available throughput will be measured using the tool Iperf. The throughput of the new protocol will be measured during the file transfer by taking the transfer time and successfully delivered packet value. A successful result here should be close to the available throughput calculated by the Iperf tool.

These tests will be run on both the test beds to determine if the protocol is useful for the general internet. Should the protocol fail to perform adequately on one test bed but perform well on another, then further research should be done to determine the cause of this. If the protocol performs well on both the test beds and successfully passes all tests then it can be deemed ready for the general internet.

Qualifications

The qualifications of the researcher include a Diploma in Computer Systems Technology, specializing in Data Communication and a Bachelor of Technology, specializing in Network Security Administration.

Study Outline

The study outline details the four overall steps required in designing and then testing the proposed protocol according to the requirements presented in this proposal. An outline of the proposed study with the steps that are required to complete follows.

1. Protocol needs to be designed according to the requirements outlined in this proposal.
2. After the design work has been completed, the protocol can be coded according to the specifications.
3. Once the protocol has been created, it needs to be tested against the requirements outlined in the first step. This is to ensure that it meets the requirements and specifications.
4. The data collected from the tests in step three can be analyzed to determine the viability of implementing this protocol in the general internet.

References

Wu, Q., & Rao, N. (2005). A class of reliable UDP-based transport protocols based on stochastic approximation. (pp. 1013-1024).

He, E., Leigh, J., Yu, O., & DeFanti, T. (2002). Reliable blast udp : Predictable high performance bulk data transfer.

Tran, D. T., & Choi, E. (2007). A reliable udp for ubiquitous communication environments.

Long, W., & Zhenkai, (2010). Performance analysis of reliable dynamic buffer udp over wireless networks. (pp. 114-117).

Gu, Y., Hong, X., Mazzucco, M., & Grossman, R. (2002). Sabul: A high performance data transfer protocol.

Tags: proposal, protocol, reliable, research, tcp, udp

About the Author

Luke Queenan Software developer specializing in network security applications and administration, Windows/Unix client-server models using IPC and TCP/IP, keeping fit in the gym.