Data Link Control Protocols

이태곤·2022년 11월 30일

Data Communication

목록 보기

11/15

1. Data Link Control Protocols

Physical Layer : 신호를 송, 수신
DataLink Layer : Frame 단위를 송, 수신
- Frame Synchronization : 송신측, 수신측 동일한 데이터를 주고받을 수 있도록 동기화되어야 한다.
- Flow Control : 송신측에서는 수신측에서 수용 가능한 Buffer사이즈에 알맞게 데이터를 전송할 수 있도록 관찰, 흐름제어가 되어야한다.
  -> Overflow 방지
- Error Control : Error Detection + Error Correction
  - Error Correction : Retransmission OR Forward Error Correction
    -> Retransmission은 시간효율, 신뢰도가 낮음 (특히, Multimedia)
- Addressing : 주소 부여 (물리적 주소 의미)
  - IP : 논리적 주소 -> Network Id + Host Id
  - Network Interface Card (ROM) : 물리적 주소 (MAC Address)
- Control and data
- Link management : Link alive or dead

2. Flow Control

송신측에서 수신측 상황을 고려해서 (Buffer size) transmitting entity가 Overwhelm되지 않도록 하는 기술이다.
-> 필요한 양만큼만 보내야한다! (프로토콜로 정의되어 있어야함)
-> Flow Control이 없다면, 수신측 buffer가 꽉차게 되면서 old data를 처리하는 동안 overflow 일어나게 될 것이다.
Frame 구성
- A -----> B
  -> B는 목적지 주소를 보고 수신
  -> C,D도 수신되지만 목적지 주소를 보고 수신받지 않음
Error 또는 Buffer Overflow 경우 어떻게 흐름제어?
-> (a)는 정상적인 송, 수신
-> (b)는 Frame2 : Overflow, Frame4 : Error
1. Stop and wait Flow Control
- 송신측에서 프레임을 전송한다.
- 수신측에서 data를 정상적으로 수신한 경우 ACK(일종의 frame)을 전송한다.
- 송신측은 수신측의 ACK를 수신한 경우에만 다음 frame을 전송한다.
- 수신측은 ACK를 보내지않음으로써 흐름제어를 할 수 있다.
- Utilization : 긴 Data를 여러개의 frame으로 나누어 전송한다.
  - Tp : Propagation delay로 frame이 송신측에서 수신측에 도착할때까지 걸리는 시간
    -> 거리에 따라 달라진다.
  - Tx : Transmission delay로 모든 frame을 링크로 밀어내기까지 걸리는 시간
    
    -> Tp안에 몇 개의 frame (Tx)을 보낼 수 있는지를 의미한다.
    -> 2a+1 시간동안 1개의 frame을 전송하므로 Utilization이 좋지않다.
    -> 해결방법? frame을 연속으로 여러개 보내기 (Sliding windows Flow Control)
1. Sliding windows Flow Control
- 각 frame마다 번호를 붙여 연속으로 보내는 방식으로 utilization이 증가하게 된다.
  - 수신측 : W 크기의 buffer를 가지고 있다.
  - 송신측 : ACK 사인없이 W개 까지의 frame을 전송할 수 있다.
  - 수신측이 전송하는 ACK는 수신이 기대되는 프레임의 번호를 전송한다.
    -> 송신측이 전송한 마지막 frame의 번호 + 1
    -> n번까지 정상적으로 수신, n+1번 frame 요청
  - Frame : Modulo 2^k (0~7, where k is 3)
  - Max Window Size : 2^k - 1, where k is field size
- Example
  - Maximum window size = 7, where Sequence number is 3bit
  - A의 window size는 수신측 buffer에 의존
    -> RR3 이후 Window size가 7로 증가
  - B에서 ACK 전송까지 마친 frame들을 buffer에서 지우고 상위로 전달하며 window size 증가
    -> RR3 이후 Window size가 7로 증가

3. Error Control Techniques

Error detection → Positive Acknowledgment 또는 Negative Acknowledgment (Lost frames OR Damaged frames)
-> Lost frames : frames fail to arrive
-> Damaged frames : frames arrive but some of bits are in error

Retransmission after timeout
-> Acknowledgment 정보 또한 Lost, Damaged 될 수 있음!

Automatic Repeat Request (ARQ) : 재전송 요청을 통한 Error control 방법
- Stop-and-wait (IDLE RQ) : 한 번에 1개의 frame을 전송하는 방식
- Continuous RQ : 연속적으로 여러개의 frame들을 전송하는 방식
  - Go-back-N
  - Selective-reject
Stop-and-wait (IDEL RQ)
1. 송신측에서 frame 1개를 전송하고 ACK을 기다린다.
  -> 송신측에서 받은 ACK에 error가 있는 경우 discard
2. 수신측에서 수신한 frame에 error가 있는 경우 discard
  -> 정상적으로 수신한 경우 Acknowledgment 전송
3. Discard된 경우에 송신측은 Round-trip기준으로 설정된 timeout 시간을 통해 재전송
  -> Sequence number를 사용하여 전송/재전송 프레임을 구별함 (ACK0, ACK1)
  -> 재전송 프레임 경우 수신측은 이미 받은 frame이기 때문에 저장하지 않고 ACK만 전송
Go-back-N
- 2번에 대한 ACK을 받지 못하면 Round-trip 시간 기준으로 설정된 time-out에 의해서 2번데이터부터 모두 다시 보내게된다.
  -> 수신측은 Damaged, Lost 된 프레임을 받게 되면 해당 frame을 포함한 이후로 buffering하지 않는다.
  -> 전송측은 해당 N번째 frame으로 돌아가 해당 frame부터 모든 frame들을 재전송해야 한다.
- sliding-window
  -> 연속으로 프레임을 보내기때문에 flow control이 필요하다.
  -> Window size 설정을 통해 ACK을 수신하지 못한 상황에서 나머지 frame들에 대한 제어가 필요하다.
- RR : receive ready (ACK) -> 에러 없을시에
- REJ = reject (Negative ACK) -> 에러 발생시에
- piggybacking: 수신측에서도 보낼 데이터가 있다면 데이터와 함께 ACK or Negative ACK 을 전송하는 방법
  -> Type의 한 종류 (Control의 종류들)
The limitation to Maximum Window Size
- EX) 3-bit sequence number : frame 0 ~ 7, Window Size : 8
  1. 송신측이 0을 전송하고 수신측에서 0을 잘 전달 받았을 때, RR1을 전송하게 된다.
    -> RR1 : 수신측에서는 Sequence number 0까지 잘 받았으므로 1번 보내길 기대
  2. 송신측은 계속해서 frame 1, 2, 3, 4, 5, 6, 7, 0을 보내고 RR1을 수신받을 것이다.
    -> 수신측에서 frame1 ~ frame 0까지 정상적으로 수신하고 Sequence number 1을 요청하는 상황 Cumulative ack
    -> 수신측에서 frame1 ~ frame 0까지 damaged or lost 되어서 다시 RR1 요청

<결론>

반대되는 경우이지만 송신측에서는 재전송 / 전송 여부를 구별할 수 없음
-> Solution : Maximum Window Size를 2^k - 1
Selective-Reject (ARQ)
- A.K.A "Selective repeat"
- Error가 발생한(Rejected) frame들만 재전송 <-> Go-back-N 방법은 Rejected된 frame부터 모든 frame들을 전송
  -> 정상 수신 된 frame들은 수신측에 의해서 buffring
  -> 재전송이 되어 정상적으로 수신 후 buffer에 채워지면 상위로 전달
- 재전송을 최소화
- 수신측은 충분한 buffer를 유지해야 함
- 상대적으로 긴 propagation delays를 가지는 위성과같은 경우에 유용
  -> 재전송을 최소화함으로써!
- Maximum Window Size for Selective-Reject ARQ : 2^(k-1)
- Dilemma
  - EX) 2-bit sequence number : frame 0 ~ 3, Window Size : 3
    
    -> 문제 되지 않음!
    
    -> 송신측에서 송신한 frame에 대한 모든 ACK를 받지 않고 timeout으로 인해 이전 data frame 0에 대해 재전송을 수행
    -> 수신 측의 window 안에 0이 들어 있으며 송신측의 상황을 모르기 때문에 이번에 들어온 패킷0가 올바른 패킷으로 판단하고 패킷 0을 버퍼에 넣기
    -> 하지만 이번에 들어온 패킷 0는 이미 예전에 받은 패킷0와 똑같은, 즉 중복된 패킷을 받게 되는 문제가 발생
  - Solution : Maximum Window Size를 2^(k - 1)
    
    -> Window size가 sequence number의 개수의 절반보다 이하여야한다.

4. High Level Data Link Control (HDLC)

Station types
- Primary : link operation을 제어
- Secondary: primary station에 의해 제어
- Combined : primary & secondary 모두 가능
Link configurations
- Unbalanced: 1 primary, multiple secondary
- Balanced: 2 combined stations
HDLC Data Transfer Modes
- Normal Response Mode(NRM)
  - unbalanced configuration 사용
  - Primary부터 전송 시작
  - Multipoint의 경우 frame을 받기 위해서 주소가 명시되어야 한다.
- Asynchronous Balanced Mode(ABM)
  - balanced configuration 사용
  - 각각의 station이 전송 시작 → Polling overhead가 없음
    -> polling : primary가 secondary한테 전송할 data가 있는지 물어보는 행위
- Asynchronous Response Mode(ARM)
  - unbalanced configuration 사용
  - primary의 허가 없이 secondary가 전송
HDLC Frame Structure
- Flag : Frame의 시작과 끝을 알림
  -> 01111110
- Address : 주소 명시
  - frame을 수신할 secondary station 주소를 명시
  - 11111111은 primary가 모든 secondaries에게 frame을 broadcast할 때 사용
- Control (8 bit, 16 bit)
  - Information (I) : 실제 data 전송을 의미 (piggybacking 사용)
    -> N(S): Send seq #
    -> N(R): Receive seq #
    -> P/F: Poll/Final bit
    Command frames (P) bit=1
    -> 상대로부터 response를 요구하는 frames (Polling)
    
    Response frames (F) bit=1
    -> response를 알리는 frame (final)
  - Supervisory (S) : piggybacking을 사용하지 않고 RR, RNR, REJ, SREJ 사용를 의미
    -> RR : ACK
    -> RNR : Receive Not Ready
    -> REJ : Reject
    -> SREJ : Selective Reject
  - Unnumbered (U) : 통신 모드를 setting하기 위해서 사용
    -> SNRM : Set Normal Response mode
    -> SARM : Set Asynchronous response mode
    -> DISC : Disconnect
    -> UA : Unnumbered Acknowledgment
- Information : 전달하고자하는 데이터 자체를 의미
  - flag 비트와 동일한 bit sequence가 나타나면?
    -> 수신측에서 정상적인 해석이 불가능
    -> 송신측은 1이 연속으로 5번 나타나는 sequence에 0을 추가 (Bit insertion, Bit stuffing)
    -> 수신측은 5번 연속으로 나타나는 1을 감지하고 그 다음 bit를 확인
    -> 0인 경우 : destuffing(0 삭제)
    -> 10인 경우 : flag로 해석
    -> 11인 경우 : error로 감지하고 abort
    Possible error
    
    -> (b) : 하나의 프레임이 두 개로 나뉘는 경우
    -> (c) : 여러개의 프레임이 하나의 프레임으로 합쳐지는 경우
HDLC Operation
- Involves three phases
1. Initialization : Specifies three modes (NRM, ABM, ARM) and sequence numbers
2. Data Transfer : through I-frame, S-frame
3. Disconnect : Sends DISC and replies UA from remote entity
- Example
  - (a)
  1. Set Asynchronous balanced mode
  2. timeout으로 인한 재전송
  3. UA
  4. Data transfer
  5. DISC
  6. UA
  - (b)
  1. I, 0, 0 : 0번 보내고 0번 이전 프레임 잘 받았으니 0번 요구
  2. I, 0, 1 : 요구한 0번 보내고 0번 프레임 잘 받았으니 1번 요구
  3. I, 1, 1 : 요구한 1번 보내고 0번 프레임 잘 받았으니 1번 요구
  4. I, 2, 1 : 2번 보내고 0번 프레임 잘 받았으니 1번 요구
  5. I, 1, 3 : 요구한 1번 보내고 2번 프레임 잘 받았으니 3번 요구
    -> Cumulative ack
  - (c)
  1. I, 3, 0 : 3번 보내고 0번 이전 프레임 잘 받았으니 0 번 요구
  2. RNR, 4 : 4번 받으면 되는데 버퍼가 가득차 받을 준비가 되지 않았고 3번 프레임 잘받았다
  3. RR, 0, P : 0번 이전 프레임 잘 받았으니 0번 요구하고 Polling (p = 1)
  4. RNR, 4, F : 4번 받으면 되는데 버퍼가 가득차 받을 준비가 되지 않았고 3번 프레임 잘받았다 (f = 1)
  5. RR, 0, P : 0번 이전 프레임 잘 받았으니 0번 요구하고 Polling (p = 1)
  6. RR, 4, F : 받을 준비가 됬고 3번 프레임 받았으니 4번 요구 (f = 1)
  7. I, 4, 0 : 4번 보내고 0번 이전 프레임 잘 받았으니 0번 요구
  - (d)
  1. I, 3, 0 : 3번 보내고 0번 이전 프레임 잘 받았으니 0번 요구
  2. I, 4, 0 : 4번 보내고 0번 이전 프레임 잘 받았으니 0번 요구
  3. I, 5, 0 : 5번 보내고 0번 이전 프레임 잘 받았으니 0번 요구
  4. REJ, 4 : 4번 프레임 받지 못함
    -> Go-back-N 형태로 4번 프레임부터 모두 재전송
  - (e)
  1. I, 2, 0 : 2번 보내고 0번 이전 프레임 잘 받았으니 0번 요구
  2. I, 3, 0 : 3번 보내고 0번 이전 프레임 잘 받았으니 0번 요구
  3. RR, 3 : 3번 이전 프레임 잘 받았으니 3번 요구
  4. RR, 0, P : timeout으로 polling, 0번 이전 프레임 잘 받았으니 0번 요구 (p = 1)
  5. RR, 3, F : 3번 이전 프레임 잘 받았으니 3번 요구 (f = 1)
  6. I, 3, 0 : 3번 보내고 0번 이전 프레임 잘 받았으니 0번 요구