Principles of Reliable Data Transfer
- With a reliable channel, no transferred data bits are corrupted or lost, and all are delivered in the order in which they were sent.
- It is the responsibility of a reliable data transfer protocol to implement this service abstraction.
- For example, TCP is a reliable data transfer protocol that is implemented on top of an unreliable(IP) end-to-end network layer.
Reliable Data Transfer over a Perfectly Reliable Channel : rdt 1.0
- Considering the simplest case, in which the underlying channel is completely reliable.
- There are separate FSMs for the sender and the receiver.
- In this simple protocol, there is no difference between a unit of data and a packet.
- Also, all packet flow is from the sender to receiver, with a perfectly reliable channel there is no need for the receiver side to provide any feedback to the sender since nothing can go wrong.
Reliable Data Transfer over a Channel with Bit Errors : rdt 2.0
- A more realistic model of the underlying channel is one in which bits in a packet may be corrupted.
- Such bit errors typically occur in the physical components of a network as a packet is trnasitted, propagates, or is buffered.
- Positive acknowledgements("OK") and negative acknowledgements("Please repeat that") can be used to indicate whether the message was corrupted or not by the receiver to the sender.
- Reliable data transfer protocols based on such retransmission are known as ARQ(Automatic Repeat request) protocols.
- Three additional protocol capabilities are required in ARQ protocols; Error detection, Receiver feedback, and Retransmission.
- It is important to note that when the sender is in the wait-for-ACK-or-NAK state, it cannot get more data from the upper layer.
- Because of this behavior, protocols such as rdt2.0 are known as stop-and-wait protocols.
- The receiver-side FSM for rdt2.0 still has a single state.
- Protocol rdt2.0 may look as if it works but, unfortunately, it has a fatal flaw. It hasn't accounted for the possibility that the ACK or NAK packet could be corrupted.
Reliable Data Transfer over a Channel with Bit Errors : rdt 2.1
- A simple solution to the problem stated above in which the ACK and NAK packet could be corrupted, is to add a new field to the data packet and have the sender number its data packets by putting a sequence number into this field.
- Protocol rdt2.1 uses both positive and negative acknowledgements from the receiver to the sender. When an out-of-order packet is received, the receiver sends a positive acknowledgement for the packet it has received.
- For the receiver, instead of sending a NAK, we can send an ACK for the last correctly received packet.
- A sender that receives two ACKs for the same packet knows that the receiver did not correctly receive the packet following the packet that is being ACKed twice.
- In rdt2.2, instead of using NAK, use ACK only.
- Receiver sends ACK for last packet received OK, and must explicitly include seq # of packet being ACKed.
- Duplicate packets at sender acts as NAK.
Reliable Data Transfer over a Channel with Bit Errors : rdt 3.0
- In addition to corrupting bits, the underlying channel can lose packets as well.
- Two additional concerns must now be addressed by protocol, how to detect packet loss and what to do when packet loss occurs.
- An approach to solve this problem is to wait for an reasonable amount of time for ACK, and if no ACK is received in this time, retransmit.
- The problem is that it is very difficult to estimate this worst-case maximum delay when deciding the time for the sender to wait for the ACK sent by the receiver to arrive back.
- Waiting for a worst-case delay could mean a long wait until error recovery is initiated.
- Also, the sender may retransmmit the packet even though neither the data packet nor its ACK have been lost, which introduces the possibility of duplicate data packets.
- Implementing a time-based retransmission mechanism requires a countdown timer that can interrupt the sender after given amount of time has expired.
- Because packet sequence numbers alternate beween 0 and 1, protocol rdt3.0 is sometimes known as alternating-bit protocol.
Pipelined Reliable Data Transfer Protocols
- Protocol rdt3.0 is a functionally correct protocol, but it is unlikely that anyone would be happy with its performance.
- At the heart of rdt 3.0's performance problem is the fact that it is a stop-and-wait protocol.
- As a result, network protocol limits use of physical resources.
- If we define the utilization of the sender as the fraction of time the sender is actually busy sending bits into the channel, it turns out that the sender was busy only 2.7 hundredths of one percent of the time.
- Rather than operate in a stop-and-wait manner, the solution is to let the sender to send multiple packets without waiting for acknowledgements.
- Since the many in-transit sender-to-receiver packets can be visualized as filling a pipeline, this technique is known as piplining.
- Buffering requirements will depend on the manner in which a data transfer protocol responds to lost, corrupted, and overly delayed packets.
- Two basic approaches toward pipelined error recovery can be identified : Go-Back-N and selective-repeat.
Go-Back-N (GBN)
- Sender is allowed to transmit multiple packets without waiting for an acknowledgement, but is constrained to have no more than some maximum allowable number N of unacknowledged packets in the pipeline.
- Receiver only sends cumulative ACK, and doesn't ACK if there is gap.
- We define base to be the sequence number of the oldest unacknowledged packet and nextseqnum to be the smallest unused sequence number, then four intervals in the range of sequence numbers can be identified.
- As the protocol operates, this window slides forward over the sequence number space.
- For this reason, N is often referred to as the window size and the GBN protocol itself as a sliding-window protocol.
- While the sender must maintain the upper and lower bounds of its window and the position of nextseqnum within the window, the only piece of information the receiver need maintain is the sequence number of the next in-order packet.
- For the receiver, it doesn't have to maintain a buffer, but discard out-of-order packets.
- Instead, the sender maintains a timer for oldest unacked packet.
- There are scenarios in which GBN itself suffers from performance problems.
- A single packet error can cause GBN to retransmit a large number of packets, many unnecessarily, and the pipeline can become filled with these unnecessary retransmissions.
Selective Repeat (SR)
- Selective Repeat Protocols avoid unnecessary retransmissions by having the sender retransmit only those packets that it suspects were in error at the receiver.
- Unlike GBN, the receiver will acknowledge a correctly received packet whether or not it is in order, and sender will have already r ceived ACKs for some of the packets in the window.
- If the received packet falls within the receiver's window and a selective ACK packet is returned to the sender.
- If the packet was not previously received, it is buffered.
- If the packet has a sequence number equal to the base of the receive window(rcv_base) , the packets are delivered to the upper layer.
- The lack of synchronization between sender and receiver windows has important consequences when we are faced with the reality of a finite range of sequence numbers.
- In order to avoid the problem in the figure above, we should carefully decide the relation between seq# size and window size.
- The window size must be less than or equal to half the size of the sequence number space for SR protocols.
Connection Oriented Transport (TCP)
- TCP is defined in RFC 793, RFC 1122, RFC 1323, RFC 2018, and RFC 2581.
- TCP is said to be connection-oriented because before one application process can begin to send data to another, the two processes must first handshake with each other.
- TCP connection is not an end-to-end TDM or FDM circuit as in a circuit-switched network, but instead connection is a logical one. The intermediate network elements do not maintain TCP connection state.
- TCP connection provides a full-duplex service, both from Process A on one host to Process B on another host and at the same time from Process B to Process A. It is bi-directional data flow in same connection.
- TCP connection is also always point-to-point, transfer of data from one sender to many receivers in a single send operation is not possible with TCP.
Three-way handshake
- Because three segments are sent between the two hosts to establish a TCP connection, this connection-establishment procedure is often referred to as a three-way handshake.
- Once a TCP connection is established, the two application processes can send data to each other.
- TCP directs data to the connection's send buffer, which is one of the buffers that is set aside during the initial three-way handshake.
Maximum Segment Size
- The maximum amount of data that can be grabbed and placed in a segment is limited by the maximum segment size(MSS).
- MSS is typically set by first determining the length of the largest link-layer frame that can be sent by the local sending host(so called maximum trasmission unit, MTU).
- Both Ethernet and PPP link-layer protocols have an MTU of 1,500 bytes, thus a typical value of MSS is 1460 bytes, excluding the TCP/IP header length which is 40 bytes.
- Thus MSS is the maximum amount of application-layer data in the segment, not the maxium size of the TCP segment including headewrs.
TCP Segment Structure
- TCP segment consists of header fields and a data field.
- MSS limits the maximum size of a segment's data field.
- When TCP sends a large file, it typically breaks the file into chunks of size MSS.
- As with UDP, the header includes source and destination port numbers and checksum field.
- TCP segment header contains 32-bit sequence number field, 32-bit acknowledgement number field, 16-bit receive window for flow control, 4-bit header length field specifing length of TCP header in 32-bit words, optional and variable-length options field used when a sender and receiver negotiate the maximum segment size(MSS) or a window scaling factor, and flag field which is consisted of 6 bit(ACK bit, RST, SYN, FIN, CWR, ECE), PSH bit, and URG bit.
- The two most important fields in TCP segment header are the sequence number field and the acknowledgement number field.
- These fields are a critical part of TCP's reliable data transfer service.
- Sequence number for a segment is the byte-stream number of the first byte in the segment.
- Acknowledgement number that Host A puts in its segment is the sequence number of the next byte Host A is expecting from Host B.
- Because TCP only acknowledges bytes up to the first missing byte in the stream, TCP is said to provide cumulative acknowledgements.
- When a host receives out-of-order segment in a TCP connection, it is up to the programmer implementing a TCP implementation becuase TCP RFCs do not impose any rules here.
- The two choices programmers can make are to make the receiver immediately discard out-of-order segment or keep the out-of-order bytes and wait for the missing bytes to fill in the gaps.
- Also, in truth, both sides of a TCP connection ramdonly choose an initial sequence number to minimize the possibility that a segment that is still present in the network from an earlier, already-terminated connection between two hosts.
- The acknowledgement for client-to-server data is carried in a segment carrying server-to-client data; this acknowledgment is said to be piggybanked on the server-to-client data segment.
Round-Trip Time Estimation and Timeout
- TCP, like our rdt protocol described above, uses a timeout/retransmit mechanism to recover from lost segments.
- The SampleRTT for a segment is the amount of time between when the segment is ent and when an acknowledgment for the segment is received.
- Instead of measureing SampleRTT for every transmitted segment, most TCP implementations take only one SampleRTT measurement at a time.
- It is natural to take some sort of average of the SampleRTT values, which is EstimatedRTT.
- Using exponential weighted moving average, EstimatedRTT is a weighted average of the SampleRTT values, putting moreweight on recent samples than old samples.
- In addition to having an estimate of RTT, it is also valuable to have a measure of the variability of RTT, called DevRTT.
- Given values of EstimatedRTT and DevRTT, we could decide the TCP's timeout interval.
- The interval should be greater or equal to EstimatedRTT, or unnecessary retransmissions would be sent.
- The timeout interval should not be too much larger than EstimatedRTT, otherwise when a segment is lost, TCP would not quickly retransmit the segment, leading to large data transfer delays.
Reliable Data Transfer
- With IP service, datagrams can overflow router buffers and never reach their destination, datagrams can arrive out of order, and bits in the datagram can get corrupted.
- TCP creates a reliable data transfer service on top of IP's unreliable best-effort service.
- Recommended TCP timer managment procedures use only a single retransmission timer, even if there are multiple transmitted but not yet acknowledged segments.
- There are three major events related to data transmission and retransmission in the TCP sender; data received from application above; timer timeout; and ACK receipt.
- Whenever timeout event occurs, TCP retransmits the not-yet-acknowledged segment with the smallest sequence number.
- But each time TCP retransmits, it sets the next timeout interval to twice the previous value.
- This modification provides a limited form of congestion control.
- The timer expiration is most likely caused by congestion in the network, that is, too many packets arriving at one router queues in the path between the source and destination, causing packets to be dropped and/or long queuing delays.
- If a segment is lost, there will likely be many duplicate ACKs.
- If sender receives 3 ACKs for same data, fast retransmit unacked segment with smallest sequence.
Flow Control
- TCP provides a flow-control service to its applications to eliminate the possibility of the sender overflowing the receiver's buffer.
- Flow control is thus a speed matching service, matching the rate at which the sender is sending against the rate at which the receiving application is reading.
- TCP provides flow control by having the sender maintain a variable called the receive window.
- Receive Window is used to give the sender an idea of how much free buffer space is available at the receiver.
- Receiver advertises free bufferspace by including rwnd value in TCP header of receiver-to-sender segments.
- Sender limits amount of unacked("in-flight") data to receiver's rwnd value, which guarantees receive buffer will not overflow.
TCP Connection Management
- TCP connection establishment is very important because it can significantly add to perceived delays.
1)
- The client side TCP first sends a special TCP segment to the server-side TCP, with SYN bit is set to 1.
- In addition, the client randomly chooses an initial sequence number(client_isn) and puts this number in the sequence number field.
2)
- Once the IP datagram containing the TCP SYN segment arrives at the server host, the server extracts the TCP SYN segment from the datagram, allocates the TCP buffers and variables to the connection, and sends a connection-granted segment to the client TCP.
- The acknowledgement field of the TCP segment header is set to client_isn+1.
- The server chooses its own inital sequence number(server_isn) and puts this value in the sequence number field of the TCP segment header.
- This connection-granted segment is referred to as SYNACK segment.
3)
- Upon receiving the SYNACK segment, the client also allocates buffers and vairables to the connection.
- The client host then sends the server yet another segment that acknowledges the server's connection-granted segment.
- It puts the value server_isn+1 in the acknowledgement field of the TCP segment header.
- The SYN bit is set to zero, since the connection is established.
- Once these three steps have been completed, the client and server hosts can send segments containing data to each other.
- In each of these future segments, the SYN bit will be set to zero.
- This connection-establishment procedure is often referred to as a three-way handshake.
- When closing a connection, client and server each close their side of connection by sending TCP segment with FIN bit = 1.
- Each side should respond to received FIN with ACK.
'Network' 카테고리의 다른 글
| Network Layer (1/4) - Data Plane (0) | 2021.10.31 |
|---|---|
| Transport Layer (3/3) (0) | 2021.10.12 |
| Transport Layer (1/3) (0) | 2021.10.11 |
| Application Layer (3/3) (0) | 2021.10.11 |
| Application Layer (2/3) (0) | 2021.09.27 |
