제 4 장데이터링크제어 한기준경북대학교컴퓨터공학과 kjhan@knu.ac.kr 1
목차 회선구성 점대점링크 멀티포인트링크 오류제어 Stop-and-Wait ARQ Go-back-N N ARQ Selective-Repeat ARQ 흐름제어 X-ON/X-OFF OFF 방식 슬라이딩윈도우방식 데이터링크제어프로토콜 HDLC (High-level Data Link Control) 2
점대점 (point-to to-point) 링크회선 각스테이션이별도의회선을통해서접속 스테이션식별주소필요없다 회선구성이간단하고대용량전송에유리 설치비용이많이든다. 3
멀티포인트링크회선 멀티드롭 (multidrop) 링크라고도함 여러스테이션이하나의전송회선을공유 스테이션식별주소필요 링크접속제어를위한메카니즘이필요 불균형링크 : 모든데이터교환을주스테이션이통제 (polling and selection) 균형링크 : 스테이션간에경쟁이나예약에의한데이터송수신 4
오류제어 프레임오류의종류 비트에러 (bit error) : 순환중복검사등의오류검출기법사용 프레임손실 (loss) : 순서번호 (sequence number) 이용검출 순방향및역방향오류제어방법 순방향 오류정정코드사용으로수신측에서에러복구 역방향 재전송에의한에러복구 자동재전송요청 (Automatic Repeat Request: ARQ) 기법 : 수신측에서오류검출시송신측으로메시지의재전송을자동적으로요청함 정지대기 (Stop-and-Wait) ARQ Go-back-N N ARQ 선택적재전송 (Selective Repeat) ARQ 5
정지 -대기 (Stop-and and-wait) ARQ 데이터프레임의정확한수신을확인하고다음프레임을전송 (Idle RQ) 구현이간단 비효율적인링크사용 A 프레임손실 ; 재전송 Timeout ACK 0 손실 ; 재전송 Timeout Frame 0 ACK 1 Frame 1 ACK 0 Frame 0* Frame 0 ACK 1 Frame 1 ACK 0 * Frame 1 ACK 0 Frame 1 B 중복된프레임을버린다. 6
ARQ 에러제어 ( 에러없을경우 ) 7
ARQ 에러제어 ( 데이터프레임에러경우 ) 8
ARQ 에러제어 (ACK 프레임에러경우 ) 9
Example Layered Architecture with Idle RQ Protocol 10
Protocol Stacks 11
Idle RQ link utilization 12
전송시간및전파지연 X 지점에있는 100 명이 200m 떨어진 Y 지점으로초당 2명씩이동할경우모두이동하는데걸리는시간은? ( 단, 이동속도 =10m/s) 100/2 + 200/10 = 70s 2000 비트의프레임을 1Km 떨어진두지점간에 B=1Mbps 의전송속도로보낼경우소요되는총시간은? ( 전파속도 = 2*10 8 m/s) 2000/1000000 + 1000/(2*10 8 ) = 2005us 13
전송시간및전파지연 D = 전파거리 V = 전파속도 = 2*10 8 m/s L = 프레임길이 B = 전송속도 전송시간 = T x = L/B 전파지연 = T p = D/V (Km 당 5us) 전파거리 D를비트로환산하면 D = B(D/V) ( 비트 ) 14
예제 D = 1Km L = 1000 비트 B = 1 Mbps D = 5 비트 5 1 D = 1Km L = 1000 비트 B = 200 Mbps D = 1000 비트 1000 1 15
예제 D = 1Km L = 1000 비트 B = 1Gbps D = 5000 비트 (5 개의프레임 ) 프레임을연속적으로전송할경우첫번째프레임의 50 번째비트가수신측에도착할시점에송신측에서는몇번째프레임의몇번째비트가전송되는순간인가? 프레임을하나전송하고 10us 이후에그다음프레임을전송할경우에는어떻게되는가? 5 th th frame 1 st st frame 1000 1 1000 1 16
Effect of propagation delay 17
Effect of propagation delay 18
Effect of propagation delay 19
Pipelined ARQ (Continuous ARQ) Pipelining: sender allows multiple, in-flight,, yet-to to-be- acknowledged pkts Two generic forms of pipelined protocols: go-back Back-N, selective repeat 20
ARQ (Without Error) 21
Go-back back-n N ARQ 연속적으로데이터프레임전송 에러가발생한프레임이후에전송된모든데이터프레임을재전송 전송대역폭낭비 일반적으로컴퓨터통신에서널리사용 프레임 2,3,4 재전송 A Frame 0 Frame 1 Frame 2 Frame 3 Frame 4 Frame 2 Frame 3 Frame 4 Frame 5 B ACK 1 ACK 2 * Error NAK 2 폐기 ACK 3 ACK 4 ACK 5 22
Go-back-N : Corrupted I-frame 23
Example 24
Go-back-N : Corrupted ACK-frame 25
Go-Back Back-N Sender: k-bit seq # in pkt header window of up to N, consecutive unack ed pkts allowed timer for each in-flight pkt ACK(n): ACKs all pkts up to, including seq # n - cumulative ACK timeout(n): retransmit pkt n and all higher seq # pkts in window Receiver : ACK-only: always send ACK for correctly-received received pkt with highest in-order seq # may generate duplicate ACKs need only remember expectedseqnum out-of of-order order pkt: discard (don t t buffer) -> > no receiver buffering! 26
선택적재전송 (Selective-Repeat) ARQ 에러가발생한데이터프레임만을재전송한다. 링크를효율적으로사용 재순서화기능등으로구현이복잡 A Frame 0 Frame 1 Frame 2 Frame 3 Frame 2 Frame 4 프레임 2 재전송 Frame 5 Frame 6 Frame 7 Frame 0 B ACK 1 ACK 2 * Error NAK 2 수신측이보관 ACK 5 ACK 6 프레임 2 를수신 ACK 7 ACK 0 27
Selective Repeat: Corrupted I-frame 28
Selective Repeat: Corrupted ACK 29
Selective Repeat receiver individually acknowledges all correctly received pkts buffers pkts,, as needed, for eventual in- order delivery to upper layer sender only resends pkts for which ACK not received 30
Selective repeat: sender, receiver windows 31
Selective repeat sender data from higher layer : if next available seq # in window, send pkt timeout(n): resend pkt n, restart timer ACK(n) in [sendbase,sendbase+n]: mark pkt n as received if n smallest unacked pkt, advance window base to next unacked seq # receiver pkt n in [rcvbase[ rcvbase, rcvbase+n-1] send ACK(n) out-of of-order: order: buffer in-order: deliver (also deliver buffered, in-order pkts) ) to higher layer, and advance window to next not-yet yet-received pkt otherwise: ignore 32
Selective repeat in action 33
Selective repeat: dilemma Example: seq # s: 0, 1, 2, 3 window size=3 receiver sees no difference in two scenarios! incorrectly passes duplicate data as new in (a) Q: what relationship between seq # size and window size? 34
Send and Receive Window Limits 35
Sequence Numbers 36
피기백응답 (Piggybacked Ack) 양방향데이터교환시에별도의응답메시지를사용하지않고역방향정보프레임의헤더에 ACK 번호를실어서보냄으로써오버헤드를줄이는기술 I(N(S)) I(N(S),N(R)) RR(N(R)) I(N(S),N(R)) I: 정보프레임 RR: 긍정응답프레임 N(S) : 정보프레임의송신순서번호 N(R) : 정보프레임의수신순서번호 (a) 별도의메시지에의한응답 (b) 피기백응답 37
흐름제어 수신측의버퍼가넘치지않도록송신측의데이터전송을제어하는기술 흐름제어의기법 X-ON/X-OFF OFF 방식 슬라이딩윈도우 (sliding window) 방식 38
Flow Control flow control sender won t overrun receiver s buffers by transmitting too much, too fast RcvBuffer = size or Receive Buffer RcvWindow = amount of spare room in Buffer receiver: explicitly informs sender of (dynamically changing) amount of free buffer space sender: keeps the amount of transmitted, unacked data From lower layer Free space (receiver window) To higher layer 39
X-ON/X-OFF OFF 방식 일종의 Stop and Wait 방식 X-OFF (^S) 를전송하여전송중지를요구 X-ON (^Q) 을전송하여계속적인데이터전송을요구 유사한흐름제어가데이터링크프로토콜인 HDLC 에서도적용 : RR(Receive Ready) RNR(Receive Not Ready) 40
슬라이딩윈도우방식 송신윈도우크기만큼의데이터프레임을연속적으로전송 송신윈도우크기 : 전송할수있는데이터프레임의최대개수 송신윈도우의크기는수신측의버퍼상황에따라에서증 감됨 송신윈도우 : 데이터프레임을전송할때마다하나씩줄어들고응답을받을때마다하나씩열림 수신윈도우 : 데이터프레임을수신할때마다하나씩줄어들고응답을전송할때마다하나씩열림 41
슬라이딩윈도우동작원리 이미전송한프레임들 전송가능한프레임의윈도우 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 프레임순서번호 전송한마지막프레임 매프레임전송마다윈도우의후미부터하나씩줄어든다. 확인응답을받은수만큼윈도우의선두끝이확장된다. (a) 송신윈도우동작 이미수신한프레임들 수신가능한프레임의윈도우 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 확인응답한마지막프레임 매프레임수신마다윈도우의후미부터하나씩줄어든다. 확인응답을전송한수만큼윈도우의선두끝이확장된다. (b) 수신윈도우동작 42
Sliding Window Concept 43
슬라이딩윈도우방식동작예 Source System A 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 F0 F1 F2 Destination System B 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 ACK3 F3 F4 F5 F6 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 ACK7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 44
데이터링크제어프로토콜 송수신기간에연결된전송회선을통하여신뢰성있는데이터프레임교환을담당 데이터링크제어의기능 링크의설정, 관리및해제 (link management) 프레임동기화 (frame synchronization) 흐름제어 (flow control) 오류제어 (error control) 대표적인데이터링크제어프로토콜 HDLC - High Level Data Link Control PPP - Point-to to-point Protocol 45
HDLC ISO 에서표준화한대표적인데이터링크제어프로토콜 비트위주의동기식전송방법 비트삽입방식에의한투명한데이터전송 점대점및멀티포인트링크지원 흐름제어 : X-ON/XX ON/X-OFF OFF and Sliding Window 오류제어 : Go-Back Back-N, Selective Repeat ARQ 46
링크의구성 주스테이션 명령 응답 (a) 점대점불균형링크 부스테이션 주스테이션 명령 응답 응답 부스테이션 ---- 부스테이션 (b) 멀티포인트불균형링크 복합스테이션 명령 응답 응답 명령 복합스테이션 (c) 점대점균형링크 47
동작모드 정규응답모드 (NRM: Normal Response Mode) 점대점이나멀티포인트불균형링크구성에서사용 주스테이션이링크의제어를담당 부스테이션은주스테이션으로부터폴 (poll) 메시지를수신한경우만데이터전송가능비동기균형모드 (ABM: Asynchronous Balanced Mode) 점대점균형링크에서사용 두개의스테이션은동등한기능을가진복합스테이션으로구성 어느쪽에서나링크의설정과해제를요구할수있음 링크가설정되면상대편의허락없이도데이터전송가능비동기응답모드 (ARM: Asynchronous Response Mode) 점대점불균형링크에서사용 부스테이션은주스테이션의허락없이데이터전송가능 주스테이션은링크의설정이나해제, 오류복구등의제어담당 48
프레임구조 flag address control information FCS flag 8 8 8 or 16 Variable 16 or 32 8 Extendable 플래그 (01111110) : 프레임의시작과끝을식별 프레임내용물과플래그의혼동방지를위해비트삽입에의한데이터투명성보장주소필드 ( 확장가능 ) : 멀티포인트링크에서스테이션식별 일반적으로 8비트를사용하나확장가능 1111111 은모든스테이션에게프레임전달을위한방송용주소제어필드 : 프레임의유형을식별정보필드 : 사용자사이에교환되는데이터를싣는영역프레임검사순서 (FCS): 플래그를제외한프레임내용에대한오류검출을위해사용 16- or 32-bit CRC 49
프레임의종류 정보프레임 (I-frame: Information Frames): 사용자데이터전달 피기백응답 (Piggybacked ACKs) 감독프레임 (S-frame: Supervisory Frames): 흐름제어및오류제어 Receive Ready(RR), Receive Not Ready(RNR) Reject(REJ): Go-back back-n N ARQ 용 NAK Selective Reject(SREJ): Selective Repeat ARQ 용 NAK 무번호프레임 (U-frame: Unnumbered Frames): 링크초기화, 유지및해제 동작모드설정명령및응답 오류복원명령및응답 기타명령및응답 50
제어영역의형식 N(S) : Send sequence number N(R) : Receive sequence number S : Supervisory function bits M : Unnumbered function bits P/F : Poll/Final bits I : Information S : Supervisory U : Unnumbered 8 비트제어영역형식 0 N (S) P/F N (R) 1 0 S P/F N (R) 1 1 M P/F M 16 비트제어영역형식 Information 0 N (S) P/F N (R) Supervisory 1 0 S 0 0 0 0 P/F N (R) 51
HDLC 프레임의종류와기능 52
1. 3. 0 RNR. 4 RR. 0.P RNR. 4. F RR. 0. P RR. 4. F 1. 4. 0 HDLC 의동작예 (c) RNR 을이용한흐름제어 53 SABM 1. 0. 0 1. 0. 1 SABM 1. 1. 1 1. 2. 1 UA 1. 1. 3 1. 3. 2 DISC UA 1. 2. 4 1. 3. 4 RR. 4 Time out Link setup Link disconnect N(S) N(R) Time out (a) 링크설정과해제 (b) 양방향데이터교환
(d) REJ 를이용한오류제어 54 1. 2. 0 RR. 3 1. 3. 0 RR. 0. P RR. 3. F 1. 3. 0 RR. 4 Timeout (d) 타임아웃을이용한오류제어 1. 3. 0 1. 4. 0 1. 5. 0 REJ. 4 1. 4. 0 1. 5. 0 1. 6. 0
기타데이터링크제어프로토콜 LAPB (Link Access Procedure, Balanced) ITU-T 에서만든 X.25 패킷교환망을위한데이터링크제어프로토콜 HDLC 의비동기균형모드 (ABM) 의부분집합 LAPD (Link Access Procedure, D channel) ITU-T 에서만든 ISDN 의 D 채널을위한데이터링크제어프로토콜 LLC (Logical Link Control) IEEE 802 위원회에서만든 LAN 을위한데이터링크제어프로토콜 55