Implementing a Reliable Data Transfer Protocol

Report
Reliable Data Transfer Protocol
IMPLEMENTATION TIPS
Recall
socket
door
application
writes data
application
reads data
TCP
send buffer
TCP
receive buffer
socket
door
Packet ->
 Reliable Data Transfer Mechanisms:
 Checksum
 Timer
- Verification of integrity of packet
- Signals necessary re-transmission is required
 Sequence
number
- Keeps track of which packet has been sent and received
 ACK
- Indicates receipt of packet in good or bad form
 NAK
 Window,
pipelining
- Allows for the sending of multiple yet-to-be-acknowledged
packets
Transport Layer
– TCP
2
B
Client - Server
Rclient_UDP.cpp
Rserver_UDP.cpp
CLIENT
SERVER
File1_Windows.txt
File1_Saved.txt
0 ABCDEF
1 ABCDEF
2 ABCDEF
3 ABCDEF
...
Empty
.
.
.
socket
UDP (User Datagram Protocol)
– has no connection establishment
- No connection state at servers
- less packet overhead than TCP
- light error-checking (checksum)
- server doesn’t use the listen() function
- server doesn’t use the accept() function
socket
UDP Basics
• See Lecture-2012-6-Socket Programming-Part2
(Slide #4)
Client - Server
Rclient_UDP.cpp
Rserver_UDP.cpp
CLIENT
SERVER
File1_Windows.txt
File1_Saved.txt
0 ABCDEF
1 ABCDEF
2 ABCDEF
3 ABCDEF
...
Empty
.
.
.
socket
socket
Port: 1235
Sample run:
Rclient 127.0.0.1 1235 0 0
Bits can be corrupted
Rserver 1235 0 0
Packets can be lost
You should run the server first, before running the client. You can
test your client and server using the same machine by using the
example run above.
Client - Server
Rclient_UDP.cpp
Rserver_UDP.cpp
CLIENT
SERVER
File1_Windows.txt
File1_Saved.txt
0 ABCDEF
1 ABCDEF
2 ABCDEF
3 ABCDEF
...
Empty
.
.
.
socket
Rclient 127.0.0.1 1235 0 0
socket
Rserver 1235 0 0
The client is the sender, while the server is the receiver.
The filenames used for sending and saving have been fixed in the
start-up codes (i.e. File1_Windows.txt, File1_Saved.txt).
Client - Server
Rclient_UDP.cpp
Rserver_UDP.cpp
CLIENT
SERVER
File1_Windows.txt
File1_Saved.txt
0 ABCDEF
1 ABCDEF
2 ABCDEF
3 ABCDEF
...
Empty
.
.
.
socket
Rclient 127.0.0.1 1235 0 0
socket
Rserver 1235 0 0
The client sends the contents of the file line by line. One packet
contains exactly one line. In order to implement reliable data
transfer, you will have to modify the packet header to add more
details.
Client - Server
Rclient_UDP.cpp
Rserver_UDP.cpp
CLIENT
SERVER
File1_Windows.txt
File1_Saved.txt
0 ABCDEF
1 ABCDEF
2 ABCDEF
3 ABCDEF
...
Empty
.
.
.
socket
Rclient 127.0.0.1 1235 0 0
socket
Rserver 1235 0 0
The objective is for you to implement a reliable data transfer
protocol. You can choose to implement a simple stop-and-wait
protocol or any of the pipe-lining protocols (i.e. Go Back-N,
Selective Repeat).
Client - Server
Rclient_UDP.cpp
CLIENT
Rserver_UDP.cpp
APPLICATION LAYER
File1_Windows.txt
SERVER
File1_Saved.txt
0 ABCDEF
1 ABCDEF
2 ABCDEF
3 ABCDEF
...
0 ABCDEF
1 ABCDEF
2 ABCDEF
3 ABCDEF
...
socket
socket
Reads file, then sends the contents
1 line at a time
Receives file contents
line-by-line, then stores everything
into a file
TRANSPORT LAYER
UNRELIABLE CHANNEL
NETWORK LAYER
Client - Server
Rclient_UDP.cpp
CLIENT
Rserver_UDP.cpp
APPLICATION LAYER
File1_Windows.txt
SERVER
File1_Saved.txt
0 ABCDEF
1 ABCDEF
2 ABCDEF
3 ABCDEF
...
0 ABCDEF
1 ABCDEF
2 ABCDEF
3 ABCDEF
...
socket
socket
Reads file, then sends the contents
1 line at a time
Receives file contents
line-by-line, then stores everything
into a file
TRANSPORT LAYER
Simulated by a
function named
send_unreliably()
UNRELIABLE CHANNEL
NETWORK LAYER
Unreliable Channel Simulation
int send_unreliably( int s, char * send_buffer,
struct sockaddr_in remoteaddress) {
int fate=packets_fate(); //random number generator: 0, 1, 2
if (fate==0){ //no problem will be introduced
bytes = sendto(s, send_buffer, ...)
printf("<-- SEND: %s \n",send_buffer);
} else if (fate== 1){ // introduce corrupted bits
send_buffer[damage_bit()]=random_char();
send_buffer[damage_bit()]=random_char();
bytes = sendto(s, send_buffer, ...)
printf("<-- DAMAGED %s \n",send_buffer);
…
You are not allowed to modify
} else if(fate==2){ // lose the packet
this function in the
printf("X-- LOST %s \n",send_buffer);
assignment.
}
}
UDP segment structure
Optional in IPv4
• The optional parameters are not even included in
the sendto() function.
int sendto(
SOCKET s,
char *buf,
int msglen,
int flags,
struct sockaddr *to,
int tolen
• The O/S will automatically
provide the IP address of
the sender of the
segment.
);
sendto()
•Send data through a socket:
sendto(SOCKET s, char *msg, int msglen, int flags,
struct sockaddr *to, int *tolen);
PARAMETERS
s = socket (inside the socket descriptor: port and IP address...)
msg = a pointer to a buffer (could be a string)
msglen = the length of the buffer
flags = 0 (forget about them for this exercise...)
to=structure of address with the IP / port #
tolen=length of the structure
Example:
sendto(s, sbuffer, strlen(sbuffer),0,(struct sockaddr*) to, &len);
recvfrom()
 Receive data
int recvfrom(SOCKET s, char *msg, int msglen,
int flags, struct sockaddr *from, int *fromlen)
PARAMETERS
s = socket (inside the socket descriptor: port and IP address...)
msg = a pointer to a buffer
msglen = the length of the buffer
flags = 0
from =structure of address with the IP / port #
fromlen=length of the structure
Example:
recvfrom(s, rbuffer, 1, 0,(struct sockaddr *) &from, &len);
14
Client - Server
Rclient_UDP.cpp
Rserver_UDP.cpp
CLIENT
SERVER
File1_Windows.txt
File1_Saved.txt
0 ABCDEF
1 ABCDEF
2 ABCDEF
3 ABCDEF
...
0 ABCDEF
1 ABCDEF
2 ABCDEF
3 ABCDEF
...
socket
socket
Reads file, then sends the contents
1 line at a time
Receives file contents
line-by-line, then stores into a file
UDP SEGMENT
Destination Port: 1235 checksum Length of segment DATA
Client - Server
Rclient_UDP.cpp
Rserver_UDP.cpp
CLIENT
SERVER
File1_Windows.txt
File1_Saved.txt
0 ABCDEF
1 ABCDEF
2 ABCDEF
3 ABCDEF
...
0 ABCDEF
1 ABCDEF
2 ABCDEF
3 ABCDEF
...
socket
Reads file, then sends the contents
1 line at a time
socket
Receives file contents
line-by-line, then stores into a file
Destination Port: 1235 checksum Length of segment DATA
CRC_NUM PACKET 0 0 ABCDEF ‘\r’ ‘\n’
User-defined
CRC
Let’s have a look at the CRC function
provided as part of the start-up codes
and the CRC test program.
Socket (in non-blocking mode)
//*******************************************************************
// CREATE CLIENT'S SOCKET
//*******************************************************************
s = socket(AF_INET, SOCK_DGRAM, 0);
if (s < 0) {
printf("socket failed\n");
WSACleanup();
exit(1);
}
//nonblocking option
u_long iMode=1;
ioctlsocket(s, FIONBIO, &iMode);
• We need to set our socket in non-blocking mode of operation.
• This prevents the recvfrom() function from stopping and waiting for a packet.
• Remember, packets could be lost in our simulation of the unreliable channel.
Start-up Codes (Client – Server)
Rclient_UDP.cpp
Rserver_UDP.cpp
CLIENT
SERVER
File1_Windows.txt
File1_Saved.txt
0 ABCDEF
1 ABCDEF
2 ABCDEF
3 ABCDEF
...
0 ABCDEF
1 ABCDEF
2 ABCDEF
3 ABCDEF
...
socket
Reads file using fgets(), then sends the
contents 1 line at a time
fopen(“file1_Windows.txt”, r)
Loop:
send_unreliably(data)
recvfrom()
socket
Receives file contents
line-by-line, then stores into a file
fopen(“file1_Saved”, w)
Loop:
recvfrom()
send_unreliably(ACK)
Reading the file contents
The client reads the file contents line by line using fgets()
CLIENT
fgets(send_buffer, SEGMENT_SIZE, fin)
• stops reading the file when it encounters either:
• a new line character (copied into send_buffer)
• EOF (End-Of-File) character
• a NULL-termination character (‘\0’) is automatically appended
• this is counted as one of the characters
strlen() – counts the number of characters excluding the NULL-character
strlen()=4
A
0
A
0
B
1
B
1
C
2
C
2
‘\n’
3
4
‘\0’
3
4
‘\0’
send_buffer
strlen()-1
‘\0’
send_buffer
Data Format
CLIENT
Destination Port: 1235 checksum Length of segment DATA
CRC_NUM PACKET 0 ABC ‘\r’ ‘\n’
User-defined
Remove the line feed character from the row of data read from the file
strlen()=4
A
0
A
0
B
1
B
1
C
2
C
2
‘\n’
3
4
‘\0’
3
4
‘\0’
send_buffer
strlen()-1
‘\0’
send_buffer
Start-up Codes (Client – Server)
Rclient_UDP.cpp
Rserver_UDP.cpp
CLIENT
SERVER
File1_Windows.txt
File1_Saved.txt
0 ABCDEF
1 ABCDEF
2 ABCDEF
3 ABCDEF
...
0 ABCDEF
1 ABCDEF
2 ABCDEF
3 ABCDEF
...
socket
fopen(“file1_Windows.txt”, r)
Loop:
send_unreliably(data)
recvfrom()
send_unreliably(”CLOSE”)
closesocket()
socket
fopen(“file1_Saved”, w)
Loop:
recvfrom()
send_unreliably(ACK)
Write everything into file1_Saved.txt
fclose()
closesocket()
Start-up Codes (Client – Server)
CLIENT
fopen(“file1_Windows.txt”, r)
0 ABCDEF
1 ABCDEF
2 ABCDEF
3 ABCDEF
...
Loop:
read one line from file
if(not EOF){
create packet with header fields
store packet into send_buffer
send_unreliably(send_buffer)
Sleep(1);
recvfrom(receive_buffer)
trim ‘\r’, ‘\n’ from receive_buffer
} else {
fclose()
send_unreliably(”CLOSE”)
}
closesocket()
SERVER
fopen(“file1_Saved”, w)
0 ABCDEF
1 ABCDEF
2 ABCDEF
3 ABCDEF
...
Loop:
recvfrom(receive_buffer)
trim ‘\r’, ‘\n’ from receive_buffer
process receive_buffer
if(receive_buffer contains DATA){
create ACK packet
send_unreliably(ACK)
save_line_without_header
} else {
fclose()
}
closesocket()
Start-up Codes
Let’s have a look at the Start-up Codes
(downloadable from our website)
Parameters Settings
Parameters (Client – Server)
Rclient_UDP.cpp
Bits can be corrupted
Rserver_UDP.cpp
CLIENT
SERVER
Packets can be lost
Sample run:
Rclient 127.0.0.1 1235 0 0
Rserver 1235 0 0
CLIENT
SERVER
COMMENTS
00
00
Packets can never be corrupted nor lost
01
00
Client may lose packets
00
01
Server may lose ACK packets
01
01
Both client and server may lose packets
10
00
Client may have corrupt bits
00
10
Server may have corrupt bits
10
10
Both client and server may have corrupted bits
11
11
Both client and server may have corrupted bits and may
lose packets
Ultimate Test
Rclient_UDP.cpp
Rserver_UDP.cpp
CLIENT
SERVER
Bits can be corrupted
Ultimate Test:
Packets can be lost
Rclient 127.0.0.1 1235 1 1
Rserver 1235 1 1
You can simply inspect the contents of File1_Windows.txt and
File1_Saved.txt, to check to see if they are exactly the same.
File1_Windows.txt
0 ABCDEF
1 ABCDEF
2 ABCDEF
3 ABCDEF
...
File1_Saved.txt
0 ABCDEF
1 ABCDEF
2 ABCDEF
3 ABCDEF
...
Extending the codes
Go-Back N
Let’s have a look at the Go-Back N Protocol
Specifications…
See Lecture-2012-7-Transport Layer-Part-1
(Slide #37)
Pipelining Protocol (Go Back-N)
CLIENT
(sender)
CRC_NUM
PACKET 0
Send a Window’s worth of packets
ABC
‘\r’
‘\n’
CRC_NUM
PACKET 1
ABC
‘\r’
‘\n’
CRC_NUM
N=Window size = 4
base
base + (N-1)
Sequence Number Space
PACKET 2
ABC
‘\r’
‘\n’
Pipelining Protocol (Go Back-N)
CLIENT
(sender)
CRC_NUM
PACKET 0
Send a Window’s worth of packets
ABC
‘\r’
‘\n’
CRC_NUM
PACKET 1
ABC
‘\r’
‘\n’
CRC_NUM
N = Window size = 4
base + (N-1)
base
nextSequenceNum
Packets sent but
not yet ACKed
nextSequenceNum-1
PACKET 2
ABC
‘\r’
‘\n’
...
Pipelining Protocol (Go Back-N)
CLIENT
(sender)
Packets sent but
not yet ACKed
N = Window size = 4
base + (N-1)
nextSequenceNum
base
nextSequenceNum-1
baseMax
base
ACKnum
We need to keep
track of the ACK
number received
Pipelining Protocol (Go Back-N)
CLIENT
(sender)
N = Window size = 4
0
1
2
3
time=0
base=0
Upon receipt of an
ACK, slide the
window forward
baseMax=3
ACKnum=1
0
1
2
3
4
5
time=1
base=ACKnum+1
baseMax=base+(N-1)
Pipelining Protocol (Go Back-N)
CLIENT
(sender)
N = Window size = 4
0
1
2
3
time=0
base=0
Transmit more packets
(up to baseMax)
baseMax=3
ACKnum=1
0
1
2
3
4
5
time=2
base=ACKnum+1
baseMax=base+(N-1)
WARNING: The following pseudo codes are not
complete. They are meant just to give you an idea
of how to implement a sliding Window protocol.
The statements highlighted in red corresponds to
the suggested routines that need to be incorporated.
Calculating the Elapsed Time
clock()
void wait ( int seconds )
{
clock_t endwait;
endwait = clock () + seconds * CLOCKS_PER_SEC ;
while (clock() < endwait) {}
}
clock_t startTime, elapsedTime;
startTime = clock();
…
...
elapsedTime = (clock() - startTime) / CLOCKS_PER_SEC;
38
Extending the codes
CLIENT
fopen(“file1_Windows.txt”, r)
Loop:
0 ABCDEF
1 ABCDEF
2 ABCDEF
3 ABCDEF
...
read one line from file
if(not EOF){
create packet with header fields
store packet into send_buffer
send_unreliably(send_buffer)
Sleep(1);
recvfrom(receive_buffer)
trim ‘\r’, ‘\n’ from receive_buffer
extract ACK number
update base, baseMax
} else {
fclose()
send_unreliably(”CLOSE”)
}
SERVER
fopen(“file1_Saved”, w)
Loop:
0 ABCDEF
1 ABCDEF
2 ABCDEF
3 ABCDEF
...
recvfrom(receive_buffer)
trim ‘\r’, ‘\n’ from receive_buffer
extract CRC1 from receive_buffer
extract data from receive_buffer
calc CRC2 using data
if(CRC1 == CRC2){
extract Packet Num
if(PacketNum is in-order){
if(receive_buffer contains DATA){
create ACK packet
send_unreliably(ACK)
save_line_without_header
update expectedSeqNum, base
}
else if(receive_buffer contains CLOSE) {
fclose(); closesocket();
closesocket()
}
}
}
Other Helpful Functions
strchr
• <cstring>
• const char * strchr ( const char * str, int character );
char * strchr ( char * str, int character );
• Locate first occurrence of character in string
• Returns a pointer to the first occurrence of character
in the C string str.
The terminating null-character is considered part of
the C string. Therefore, it can also be located to
retrieve a pointer to the end of a string.

similar documents