Public speaking course notes Read "Dynamo, Amazon’s Highly Available Key-value Store" Read "Bigtable, A Distributed Storage System for Structured Data" Read "Streaming Systems" 3, Watermarks Read "Streaming Systems" 1&2, Streaming 101 Read "F1, a distributed SQL database that scales" Read "Zanzibar, Google’s Consistent, Global Authorization System" Read "Spanner, Google's Globally-Distributed Database" Read "Designing Data-intensive applications" 12, The Future of Data Systems IOS development with Swift Read "Designing Data-intensive applications" 10&11, Batch and Stream Processing Read "Designing Data-intensive applications" 9, Consistency and Consensus Read "Designing Data-intensive applications" 8, Distributed System Troubles Read "Designing Data-intensive applications" 7, Transactions Read "Designing Data-intensive applications" 6, Partitioning Read "Designing Data-intensive applications" 5, Replication Read "Designing Data-intensive applications" 3&4, Storage, Retrieval, Encoding Read "Designing Data-intensive applications" 1&2, Foundation of Data Systems Three cases of binary search TAMU Operating System 2 Memory Management TAMU Operating System 1 Introduction Overview in cloud computing 2 TAMU Operating System 7 Virtualization TAMU Operating System 6 File System TAMU Operating System 5 I/O and Disk Management TAMU Operating System 4 Synchronization TAMU Operating System 3 Concurrency and Threading TAMU Computer Networks 5 Data Link Layer TAMU Computer Networks 4 Network Layer TAMU Computer Networks 3 Transport Layer TAMU Computer Networks 2 Application Layer TAMU Computer Networks 1 Introduction Overview in distributed systems and cloud computing 1 A well-optimized Union-Find implementation, in Java A heap implementation supporting deletion TAMU Advanced Algorithms 3, Maximum Bandwidth Path (Dijkstra, MST, Linear) TAMU Advanced Algorithms 2, B+ tree and Segment Intersection TAMU Advanced Algorithms 1, BST, 2-3 Tree and Heap TAMU AI, Searching problems Factorization Machine and Field-aware Factorization Machine for CTR prediction TAMU Neural Network 10 Information-Theoretic Models TAMU Neural Network 9 Principal Component Analysis TAMU Neural Network 8 Neurodynamics TAMU Neural Network 7 Self-Organizing Maps TAMU Neural Network 6 Deep Learning Overview TAMU Neural Network 5 Radial-Basis Function Networks TAMU Neural Network 4 Multi-Layer Perceptrons TAMU Neural Network 3 Single-Layer Perceptrons Princeton Algorithms P1W6 Hash Tables & Symbol Table Applications Stanford ML 11 Application Example Photo OCR Stanford ML 10 Large Scale Machine Learning Stanford ML 9 Anomaly Detection and Recommender Systems Stanford ML 8 Clustering & Principal Component Analysis Princeton Algorithms P1W5 Balanced Search Trees TAMU Neural Network 2 Learning Processes TAMU Neural Network 1 Introduction Stanford ML 7 Support Vector Machine Stanford ML 6 Evaluate Algorithms Princeton Algorithms P1W4 Priority Queues and Symbol Tables Stanford ML 5 Neural Networks Learning Princeton Algorithms P1W3 Mergesort and Quicksort Stanford ML 4 Neural Networks Basics Princeton Algorithms P1W2 Stack and Queue, Basic Sorts Stanford ML 3 Classification Problems Stanford ML 2 Multivariate Regression and Normal Equation Princeton Algorithms P1W1 Union and Find Stanford ML 1 Introduction and Parameter Learning

AI 2

Algorithm 17

Amazon 1

Authorization 1

Blog 3

Bootstrap 1

C++ 1

CCpp 5

CSS 2

Cloud 3

Code 1

Crawler 1

DNS 1

Database 17

DeepLearning 1

Design 16

Development 1

Docker 1

Express 1

GDB 1

Go 3

Google 4

HTML 3

IOS 1

Java 17

Javascript 4

Jekyll 1

Linux 4

MacOS 2

MachineLearning 16

Markdown 4

Mobile 1

MongoDB 2

Multi-threading 3

NAS 1

Network 11

NeuralNetwork 10

Node 1

OS 8

Public-speaking 1

Python 15

RESTful 1

Rails 9

React 1

Redis 1

Ruby 6

Shell 2

Spring 2

System 16

TCP 1

TDD 1

Thread 2

Vim 1

awk 1

git 1

jQuery 1

media 1

network 1

php 1


A TCP-like reliable data transfer protocol built on UDP

2018-04-23

Introduction

Check out the source code on github.

This TCP-like reliable data transfer project is developed with two layers. The basic layer is UDP. MyUDPSocket class is created as a wrapper of UDP transfer. For the other layer, SenderSocket class is built on top of UDP and implements pipelined transfer, retransmit, timeout, flow control, etc in order to make the transfer reliable and efficient.

This project implements following properties of TCP.

  1. Send a window of packets. The transfer can be pipelined to improve efficiency.
  2. Flow control. The sender never overwhelms receiver.
  3. Timeout and retransmit.
  4. Fast retransmit. Packet is retransmitted upon receiving 3 duplicate ACKs.
  5. Timeout intervals are calculated accumulatively according to TCP formula.

Implementation

UDP layer

MyUDPSocket is relatively simple. It implements SendTo() and RecvFrom() methods to do the job literally. Note the data transfer on both methods are unreliable and anything can happen.

reliable layer

SenderSocket has Open() method to initialize connection with the receiver side and Close() method to close that connection. SYN, FIN and ACKs packets are used for this purpose.

For the actual data transfer, SenderSocket owns three threads; one for sending packets, one for receiving ACKs, the last for Statistics. So that receiving doesn’t block sending.

Semaphores and events are used to ensure only one thread can access some critical sections.

Usage

The program takes 7 arguments as below.

transfer.exe target_host data_array_length_power window_size round_trip_time forward_loss reverse_loss link_rate

Sample trace

In the trace,

  • B: the base of sender window
  • N: next to send
  • T: number of timeouts
  • F: number of fast retransmissions
  • W: effective window
  • S: send speed
  • RTT: measured round trip time

Trace with no loss:

Main:   sender W = 3000, RTT 0.010 sec, loss 0 / 0, link 10000 Mbps
Main:   initializing DWORD array with 2^30 elements... done in 1566 ms
Main:   connected to localhost in 0.011 sec, pkt size 1472 bytes
[  2] B 163852 (228.8 MB) N 166852 T  0 F  0 W 3000 S 959.517 Mbps RTT 0.033
[  4] B 344321 (480.7 MB) N 347320 T  0 F  0 W 3000 S 1056.826 Mbps RTT 0.033
[  6] B 524254 (732.0 MB) N 527254 T  0 F  0 W 3000 S 1053.688 Mbps RTT 0.033
[  8] B 704543 (983.7 MB) N 707543 T  0 F  0 W 3000 S 1055.772 Mbps RTT 0.033
[ 10] B 885070 (1235.7 MB) N 888070 T  0 F  0 W 3000 S 1057.166 Mbps RTT 0.034
[ 12] B 1064803 (1486.7 MB) N 1067803 T  0 F  0 W 3000 S 1052.516 Mbps RTT 0.035
[ 14] B 1244188 (1737.1 MB) N 1247188 T  0 F  0 W 3000 S 1050.479 Mbps RTT 0.034
[ 16] B 1424665 (1989.1 MB) N 1427665 T  0 F  0 W 3000 S 1056.873 Mbps RTT 0.032
[ 18] B 1608966 (2246.4 MB) N 1611965 T  0 F  0 W 3000 S 1079.267 Mbps RTT 0.032
[ 20] B 1792467 (2502.6 MB) N 1795467 T  0 F  0 W 3000 S 1074.582 Mbps RTT 0.034
[ 22] B 1976910 (2760.1 MB) N 1979910 T  0 F  0 W 3000 S 1080.098 Mbps RTT 0.032
[ 24] B 2161746 (3018.2 MB) N 2164746 T  0 F  0 W 3000 S 1082.400 Mbps RTT 0.032
[ 26] B 2345969 (3275.4 MB) N 2348969 T  0 F  0 W 3000 S 1078.810 Mbps RTT 0.034
[ 28] B 2531027 (3533.8 MB) N 2534027 T  0 F  0 W 3000 S 1083.700 Mbps RTT 0.032
[ 30] B 2714903 (3790.5 MB) N 2717902 T  0 F  0 W 3000 S 1076.778 Mbps RTT 0.032
[ 32] B 2896752 (4044.4 MB) N 2899751 T  0 F  0 W 3000 S 1064.908 Mbps RTT 0.035
[32.492] <-- FIN-ACK 2933721 window 39F2A0E6
Main:   transfer finished in 32.404 sec, 1060354.84 Kbps, checksum 39F2A0E6
Main:   estRTT 0.025, ideal rate 1424901.86 Kbps

Trace with small loss:

...\x64\Release> .\p3-reliable-data-transfer.exe localhost 20 50 0.01 0.1 0.0001 1000
Main:   sender W = 50, RTT 0.010 sec, loss 0.1 / 0.0001, link 1000 Mbps
Main:   initializing DWORD array with 2^20 elements... done in 2 ms
Main:   connected to localhost in 0.011 sec, pkt size 1472 bytes
[  2] B    626 (  0.9 MB) N    676 T 16 F 43 W 50 S  3.666 Mbps RTT 0.011
[  4] B   1208 (  1.7 MB) N   1258 T 32 F 85 W 50 S  3.408 Mbps RTT 0.011
[  6] B   1574 (  2.2 MB) N   1624 T 53 F 112 W 50 S  2.143 Mbps RTT 0.011
[  8] B   2148 (  3.0 MB) N   2198 T 68 F 159 W 50 S  3.361 Mbps RTT 0.011
[ 10] B   2673 (  3.7 MB) N   2723 T 83 F 201 W 50 S  3.074 Mbps RTT 0.011
[11.029] <-- FIN-ACK 2865 window 5B0360D
Main:   transfer finished in 10.955 sec, 3062.93 Kbps, checksum 5B0360D
Main:   estRTT 0.011, ideal rate 54531.69 Kbps

Copyright claim: A TCP-like reliable data transfer protocol built on UDP is created by melonskin on 2018/04/23. Its copyright belongs to the author. Commercial usage must be authorized by the author. The source should be included for non-commercial purposes.
Link to the article: https://amelon.org/2018/04/23/reliable-data-transfer.html

Creative Commons License
Melon blog is created by melonskin. This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
© 2016-2024. All rights reserved by melonskin. Powered by Jekyll.