3. Selective repeat
- receiver individually acknowledges all correctly received packets : 각각의 패킷에 대해 acknowledge
- buffers packets(out-of-order 패킷을 버퍼링해놓았다가 안들어온 것이 들어오면 그때 함께 application쪽으로 올려준다.), as needed, for eventual in-order delivery to upper layer
- sender only resends packets for which ACK not received : sender은 재전송하는 패킷은 ACK을 안받은 것에 대해서만 재전송하면 된다.
- sender timer for each unACKed packet : 타이머를 각자 가지고 있다.
- sender window
- N consecutive sequence numbers : 윈도우 사이즈가 N이면 ACK을 받기전에 한번에 보낼 수 있는 갯수
- limits sequence numbers of sent, unACKed packets : 최대 N개까지만 가능하도록 함
Selective repeat: sender, receiver windows
go-back-N과의 차이점은 초록색의 패킷이 중간중간 차있다.
만약에 데이터 윈도우 바깥쪽에 있는 패킷이 왔다면 그 데이터는 받아들여지지 않는다.
자주색은 패킷이 온 것이다.
회색인 부분은 패킷이 와야하는데 아직 안온상태이다.
지금 receiver 쪽은 10번 패킷이 아직 안와서 ACK를 보내지 않은 상태이다.
(요약)
여기에서는 ACK을 받지 못한 패킷과 ACK을 받은 패킷이 섞여있다.
Selective repeat
- sender : 다음 이벤트에 반응
- data from above : app에서 데이터를 내려보냄
- if next available sequence number in window, send packet : next sequence number가 window 안에 있다면 패킷을 보낸다.
- timeout(n) : n번의 timeout이 걸린경우
- resend packet n, restart timer
- ACK(n) in [sendbase, sendbase+N] : ACK이 winwow 안으로 온 경우
- mark packet n as received
- if n smallest unACKed packet, advanced window base to next unACKed sequence numbe : 만약 window의 최저 seq num이 왔다면 윈도우 이동
- data from above : app에서 데이터를 내려보냄
- receiver
- packet n in [rcvbase, rcvbase+N-1] : window 안에 se num으로 패킷이 들어온 경우
- send ACK(n) : n번 패킷에 대한 ACK 전송
- out-of-order: buffer : 중간께 오면 저장만 하고 있다.
- in-order: deliver (also deliver buffered, in-order packets) advance window to next not-yet-received packet : 정상적인 순서로 데이터가 오면 윈도우를 이동
- packet n in [rcvbase-N, rcvbase-1] : 윈도우의 rcvbase 이하까지는 모두 ACK를 보내주어야 한다.(재전송때문) 하지만 범위상 N보다 더 큰 범위에서 보내질 수 없음
- ACK(n)
- otherwise
- ignore
- packet n in [rcvbase, rcvbase+N-1] : window 안에 se num으로 패킷이 들어온 경우
(요약)
-
sender
ACK을 받았는데 보낸것중에 가장 작은 ACK 이였다면 윈도우 이동
보낸 ACK에 대한 ACK을 못 받았으면 time out이 되고 보내준다. -
receiver
정상적인 순서로 데이터가 오면 윈도우를 이동
받은 것은 그대로 ACK(n)을 돌려주는데 못받은 놈은 무시
이미 ACK을 보낸 패킷을 받은 경우 무시
Selective repeat: action
pkt3은 window 2 3 4 5에서 3을 채워준다.(Buffering)
그러면 sender 쪽에서도 window가 2 3 4 5에서 3만 채워준다.
이후 2번 패킷이 timeout된다.
Selective repeat: dilemma
윈도우 size는 얼마, seqnum은 몇 bit 쓸것인가.
window size가 너무 크면 패킷드랍과 충돌이 많이 생기어 적당한 사이즈를 결정해야 한다.
- example
- seq. nums: 0, 1, 2, 3
- window size = 3
- receiver sees no difference in two scenarios
- duplicate data accepted as new in (b)
- Relationship between sequence number size and window size to avoid problem in (b)
- window size must be less than or equal to half the size of sequence number space : sequence number은 window size보다는 크게. 즉 window size는 seq num의 절반이하로 잡아야 문제가 생기지 않는다.
그림 그림의 아래와 같이 ACK 모두 못받은 경우 timeout이 걸리게 된다. 그러면 seq num과 window size간의 간격이 너무 짧아서 receive쪽에서 문제가 생기게 된다.
- window size must be less than or equal to half the size of sequence number space : sequence number은 window size보다는 크게. 즉 window size는 seq num의 절반이하로 잡아야 문제가 생기지 않는다.
(요약)
32bit의 seq만 가지고 있음
만약에 윈도우가 너무 작으면 보낸 seq num이 같은 다른 패킷을 던지어진다. 그러면 먼저 보내진 에러가 난 패킷이 정상적으로 보내졌다고 생각할 수 있다.
그래서 window size는 이렇게 계산한다.
N : win size
S : seq number space(0, ... , s-1)
그럼
0 1 ... N-1 N ... S-1 0 1 2
[초기 윈도우][seq 끝]
이기때문에 못해도
2N-1 <= S-1 가 되기 때문에 정리하면
N <= S/2 크기면 정상이다.
=== connection-oriented transport: TCP ===
1. TCP: Overview [RFC 793, 1122, 1323, 2018, 2581]
- point-to-point
- one sender, one receiver : one sender to one receiver 프로토콜이다.
- reliable, in-order byte stream : reliable + sender가 보내는 byte 순서대로 받는다.
- no "message boundaries" : TCP(=Byte Stream), 한 Byte마다 Byte의 번호를 보낸다.
- pipelined : window 안의 패킷들은 ACK을 받지않고 한 번에 보낼 수 있다.
- TCP congestion and flow control set window size : window size를 얼마로 할것인가가 중요(congestion and flow control)
- full duplex data
- bi-directional data flow in same connection : 상호 데이터를 주고 받을 수 있다.
- MSS: maximum segment size : 헤더를 제외한 부분을 이야기
- connection-oriented : 연결을 맺고 끝는다.
- handshaking (exchange of control messages) inits sender, receiver state before data exchange
- flow controlled : sender가 receiver가 받을 수 있는 수준으로 데이터를 보내주는 것
- sender will not overwhelm receiver
TCP segment structure
options : 있을수도 없을수도 있음(option이 없으면 head가 20byte, 있으면 최대 60byte)
source port / dest port : 송/수신자의 포트번호
sequence number : sender가 데이터를 보낼때 맨 앞에 있는 seq number
acknowledgement number : 내가 보내는 패킷이 ACK일때 어떤 Byte를 받았는지 저장됨
head len : 어디까지가 TCP 헤더인지 알려줌(4bit * 4로 계산)
not used : 비는 부분 (나중에 CWR, ECE가 추가됨 지금은 몰라도 됨)
UAPRSF : Flag
- U (URG) : 긴급하게 처리해야하는 데이터가 있다. -> Urg data pointer을 사용
- A (ACK) : acknowledgement number 유효
- P (PSH) : 바로 application쪽으로 데이터를 보내줘라
- R (RST) : 비정상적으로 connection 끝을때 1
- S (SYN) : 처음 connection을 맺을때 1로 되어 있음
- F (FIN) : connection을 끝을때 1
receive window : flow control용, receiver가 앞으로 받을 수 있는 데이터 양
checksum : 오류 정정
Urg data pointer : Urgent data의 마지막 바이트 (application data의 urgent 부분이 또 나뉘어짐 그때 마지막 바이트 위치)
(요약)
head len : 어디까지가 TCP 헤더인지 알려줌(4bit * 4로 계산)
UAPRSF : Flag
- U (URG) : 긴급하게 처리해야하는 데이터가 있다. -> Urg data pointer을 사용
- A (ACK) : acknowledgement number 유효
- P (PSH) : 바로 application쪽으로 데이터를 보내줘라
- R (RST) : 비정상적으로 connection 끝을때 1
- S (SYN) : 처음 connection을 맺을때 1로 되어 있음
- F (FIN) : connection을 끝을때 1
이거 계산 문제나 FLAG별 특징을 물어볼 수 있음
TCP sequence numbers, ACKs
- sequence numbers
- byte stream "number" of first byte in segment's data : byte마다 숫자가 붙는다. 예를 들어 6000byte를 보낸다면 랜덤으로 seq number을 정한다. 그래서 이번에 0번 1000byte 보내면 그 다음 패킷은 1000부터 시작한다.
파란색 부분이 새롭게 시작한 seq num
- acknowledgements
- sequence number of next byte expected from other side : 이번에 받은거 바로 다음 번호를 보내준다.(0시작 1000byte받았다면 다음인 1001을 ack num에 넣는다.), A flag가 서있는다.
- cumulative ACK
1. C 데이터의 byte number가 42라서 seq num이 42인 것이다.(42번째 데이터) A가 데이터를 보낼떄 B의 데이터에 대한 ACK도 함꼐 보낸다. 이전에 B가 A에게 보낸 마지막 byte number가 78이기 때문에 보낼때 79를 달라고 보내주는 것이다.
-
B가 A로 보낼때 byte num이 79라서 79를 보낸다. 그리고 seq num 42를 받았으니 ACK를 43을 보낸다.
-
A에서 보낼데이터가 없어도 seq은 43으로 하고 ACK는 80으로 보낸다.
(요약)
seq num에는 몇번째 byte인지가 적힌다.(세그먼트는 byte의 묶음이다. 100 단위로 잘라서 0 -> 0, 100 -> 1 로 할 수 있다. 그래서 보내는 부분들의 가장 첫번째를 지칭한다.)
(반면 ACK는 바이트를 단위로 체크한다. 이번에 받은것에 대한 응답만 해주면 된다.)
=> 쉽게 생각하면 seq num 과 ack num 모두 저체 보내는 것을 바이트 단위로 쪼개서 숫자를 계산하되
seq는 보내는 것에 대한 번호가 적혀있다.
ack는 받아야 하는 것에 대한 응답이다. 그래서 문제가 없다면 윈도우의 첫번째 바이트가 올 수 있고 문제가 있다면 에러가 난 바이트의 번호가 올 수 있다.
ack field에는 어디까지 잘 받았으니 이번에는 몇번째 바이트를 기대한다는 값을 넣는다.(ACK flag 1이 된다.)
TCP round trip time, timeout
패킷 loss가 발생하면 timer을 설정해 놓고 재전송을 하게 된다. timeout을 얼마로 할 것인가?
- How to set TCP timeout value?
- longer than RTT(Round Trip Time 왔다갔다 하는데 걸리는 시간)
- but RTT varies
- too short: premature timeout, unnecessary retransmissions : 잘못 설정하면 쓸모없는 재전송을 할 수도 있다.
- too long: slow reaction to segment loss
- longer than RTT(Round Trip Time 왔다갔다 하는데 걸리는 시간)
- How to estimate RTT?
- SampleRTT: measured time from segment until ACK receipt : 패킷을 보내고 시간을 재는 방법
- ignore retransmissions
- SampleRTT will vary
- We want "smoother" estimated RTT : estimated RTT를 계산한다.
- average several recent measurements, not just current SampleRTT
- SampleRTT: measured time from segment until ACK receipt : 패킷을 보내고 시간을 재는 방법
(요약)
TCP의 타이머 계산
timeout이 너무 작으면 너무 자주 duplicate time이 전송됨
너무 크면 너무 늦게 반응함
TCP round trip time, timeout
- Exponential weighted moving average
데이터가 오고 갈때마다 시간을 계산한다. sampleRTT가 달라질때마다 새롭게 계산한다. - influence of past sample decreases exponentially fast
- typical value: α = 0.125
TCP round trip time, timeout
- timeout interval: EstimatedRTT + "safety margin"
- large variation in EstimatedRTT → larger safety margin
- estimate SampleRTT deviation from EstimatedRTT
DevRTT : safety margin을 더해준다. RTT의 변동폭을 알려주는 변수
(요약)
- typical value: α = 0.125
- SampleRTT : 세그먼트를 보내고 ACK을 받을때까지의 시간을 측정한다.(재전송 무시)
- EstimatedRTT : 최근 데이터의 평균
알파가 1에 가까우면 현재값을 많이 반영
알파가 0에 가까우면 스무딩을 많이 한것이다.
하지만 이것도 표준편차를 붙여서 사용한다.
DevRTT : safety margin을 더해준다. RTT의 변동폭을 알려주는 변수
그러면 실재 TimeoutInterval이 계산되어진다.
