데이터 통신과 네트워킹-TCP/IP프로토콜 기반: 3장 데이터 링크층
3.1 개요
3.1.1 노드와 링크
노드(node): 두 종단 호스트와 라우터를 노드로 표현
링크(link): 노드 사이의 네트워크를 링크로 표현
3.1.2 링크의 두 가지 유형
점-대-점(point-to-point link)
링크는 서로 연결된 2개의 장치가 전용으로 이용한다.
➡️ 일반 가정집 전화
브로드캐스트 링크(Broadcast link)
링크는 여러 장치의 쌍들이 공유된다.
➡️ 휴대폰
3.1.3 2개의 부계층
데이터 링크 제어(DLC, Data Link Control)
- 점-대-점, 브로드캐스트에 연관된 공통 사항 다룸
매체 접근 제어(MAC, Media Access Control)
- 브로드캐스트 링크에 관한 사항 다룸
3.2 데이터 링크 제어
- 데이터 링크 제어(DLC, Data Link Control)는 링크가 전용이거나 방송용이거나 상관없이 두 인접한 노드 사이의 통신을 위한 절차를 다룬다.
- 프레임짜기(framing), 오류 제어(error control)를 포함
3.2.1 프레임 짜기(framing)
- 데이터 링크층의 프레임 짜기는 송신자와 수신자의 주소를 추가하여 한 발신지에서 한 목적지로 가는 메시지를 구분한다.
- 목적지 주소: 패킷이 가야 할 곳
- 송신자 주소: 수신자가 수신에 대한 확인 응답하는 데 사용
- 메시지를 여러 개의 작은 프레임으로 나눠 넣음 ➡️ 오류에 대응하기 위해
프레임 크기
- 고정 길이 프레임 짜기(fixed-size framing): 사전 정의된 크기를 구분 기호로 사용
- 가변 길이 프레임 짜기(variable-size framing): 프레임이 끝나는 곳과 시작 되는 지점을 지정해야 한다.
문자 중심 프레임 짜기
- 데이터 및 제어 정보(헤더/트레일러)는 8비트 문자(예: ASCII)로 구성
- 플래그: 특수 8비트 문자는 프레임의 시작과 끝을 표시
- 데이터에 플래그가 표시되어 오해가 발생할 수 있다.
비트 중심 프레임 짜기
- 프레임의 데이터 부분은 상위 계층에서 해석하는 비트의 순서이다.
- 헤더를 포함하여 프레임들을 서로 분리하는 구분자가 있음
- 8비트 패턴(01111110)을 프레임 구분자로 사용
비트 채우기(Bit Stuffing)
- 플래그 패턴이 데이터 안에 나타나면 수신자로 하여금 이것이 프레임의 끝이 아니라는 것을 알리기 위해 사용
- 1개의 단일 비트를 채워 넣어서 크 패턴이 플래그처럼 보이지 않도록 만든다.
방법
- 0과 그 뒤로 연속하는 5개의 1을 만나게 되면 추가로 0을 더해 넣는다.
- 추가로 채워진 비트는 마지막 순간에 수신자가 데이터에서 제거하여 원본 데이터로 재구성
3.2.2 오류 제어
데이터 링크층에서 오류 제어는 주로 오류 검출과 재전송
오류의 유형
- 간섭(interference): 비트가 다른 지점으로 전달될 때 간섭으로 인해 변경이 생길 수 있음
- 단일 비트 오류(single-bit error): 주어진 데이터 단위 중 오직 하나만 0에서 1, 1에서 0으로 변경
- 폭주 오류(burst error): 데이터 단위에서 2개 이상의 연속적인 비트들이 0에서 1, 1에서 0으로 변경
중복(Redundancy)
- 오류를 검출하거나 정정하는 것의 중심 개념
- 송신자에 의해 오류 검출, 정정을 위해 데이터 이외에 추가 비트를 수신자에게 보냄
검출 대 정정(Detection versus Correction)
- 오류 검출(error detection): 단순히 오류가 생겼는지만
- 오류 정정(error correction): 정확히 몇 비트가 잘 못되었는지, 어디가 잘못되었는지 알아야 함
부호화(Coding)
- 송신자는 중복 비트와 실제 데이터를 관련 짓는 중복비트를 수신자에게 보낸다.
- 수신자는 이 두 종류의 비트들 사이에 관계를 확인하여 오류를 검출하거나 정정.
- 부호화 방법은 블록 부호화(block coding)와 컨볼루션(convolution) 부호화로 나눌 수 있다.
블록 부호화(block coding)
- 메시지를 데이터워드(dataword)라는 k비트의 블록으로 나눈다.
- 각 블록에 r개의 중복 비트들을 더하여 길이 n = k + r이 되도록 한다.
- n비트 블록을 코드워드(codeword)라 한다.
오류 검출
- 수신자는 유효 코드워드의 목록을 가지고 찾을 수 있다.
- 원래의 코드워드가 무효 코드워드로 바뀌었다.
예제
k = 2, n = 3이고 송신자가 데이터워드 01을 011로 부호화하여 수신자에게 보낸다.
- 수신자가 011을 수신 ➡️ 유효 코드 ➡️ 수신자는 데이터 워드 01을 추출
- 코드워드 손상으로 111 수신 ➡️ 유효 코드가 아니므로 버려진다.
- 코드워드 손상으로 000 수신 ➡️ 유효 코드 ➡️ 수신자는 00 추출 ➡️ 2개 비트가 손상되어 요류를 찾지 못함
※ 오류 검출 코드는 찾도록 설계된 오류만 찾아낼 수 잇다. 다른 유형의 오류는 검출 x
해밍 거리(Hamming distance)
- 2개의 워드(같은 길이) 사이의 해밍거리는 서로 다른 대응 비트의 개수
- 두 워드 x, y사이의 해밍 거리를 d(x, y)로 표시
- 수신된 코드워드와 발신된 코드워드 사이의 해밍 거리는 전송되는 동안에 오류가 생긴 비트의 수
- 해밍 거리는 두 워드에 XOR 연산을 한 결과에 1의 개수
오류 검출을 위한 최소 해밍 거리
- 모든 경우에 s개까지의 오류 검출을 보장하려면 블록 코드의 최소 해밍 거리는 d(min) = s + 1
선형 블록 코드(Linear Block Code)
- 2개의 유료 코드워드에 대해 XOR 연산을 하면 다른 유효 코드워드가 생성되는 코드
선형 블록 코드의 최소 거리
- 0이 아닌 가장 적은 수의 1을가지고 있는 코드워드의 1의 개수
패리티 검사 코드(Parity-check code)
- k비트 데이터워드를 n = k + 1이 되도록 n 비트 코드워드로 바꾸는 것
- 추가된 비트는 패리티 비트한다.(보통 짝수 패리티 비트 사용)
- 최소 해밍 거리 d(min) = 2 이다.
- 송신자가 전송한 워드를 수신자가 덧셈한 결과를 신드롬(Syndrome)라고 하는데 1비트 값이다.
- 수신된 워드의 1의 개수가 짝수이면 신드롬은 0이고 아니면 1이다.
- 신드롬이 0이면 오류가 없음
- 신드롬이 1이면 코드워드의 데이터 부분을 버린다.
순환 코드(Cyclic Code)
- 코드워드를 순환시키면 다른 코드워드를 얻는다.
- 1011000이 코드워드이면 1개의 비트를 왼쪽으로 이동시켜 얻은 코드워드 0110001도 코드워드이다.
순환 중복 검사(CRC, Cyclic Redundancy Check)
- 순환 코드의 한 범주
송신자 - encoder(부호기)
- 부호기(encoder)에서 데이터워드는 k비트이며, 코드워드는 n비트이다.
- 데이터워드의 크기는 n - k 개의 0을 워드의 오른편에 더해서 키워진다.
- n비트 결과 값이 생성기로 보내진다.
- 생성기는 미리 전해진 크기 n - k + 1의 나누기 장치를 사용한다.
- 생성기는 확장된 데이터 워드를 나누기 장치로 나눈다.
- 나눗셈 결과로 얻은 몫은 버려지고 나머지(r2r1r0)를 데이터워드에 덧붙여 코드워드를 만든다.
수신자 - decoder(복호기)
- 손상되었을지 모르는 코드워드를 수신
- 수신된 n비트의 사본이 검사기에 보내짐
- 검사기에 의해 만들어진 나머지가 n - k 비트의 신드롬이 되며 이 신드롬이 결정 논리 분석기에 보내짐
- 신드롬 비트가 모두 0이면 코드워드의 왼편 4개 비트를 데이터 워드로 받아드림
- 그렇지 않은 경우 4개 비트는 버려짐(오류 발생)
부호기(Encoder)
- 데이터워드를 받아 n - k 개의 0을 덧붙인다.
- XOR 연산을 사용한다.
복호기(Decoder)
- 복호기는 부호기와 동일한 나눗셈 연산 수행
- 나머지가 신드롬이 됨
- 신드롬이 000인 왼편은 오류가 없다.
- 오른편은 오류가 하나 있는 경우의 신드롬 값이다.
검사합(Checksum)
- 모든 길이의 메시지에 적용할 수 있는 오류 검출 기법.
- 네트워크층과 전송층에서 사용됨(여기는 링크층)
3.3 매체 접근 프로토콜(MAC, Media Access Control)
3.3.1 임의 접근(Random-Access)
- 어떤 지국이든 다른 지국보다 우월하지 않으며 다른 지국에 대해 제어할 수 없다.
- 전송은 지국 사이에서 임의로 벌어진다.
- 어느 지국이 다음번에 전송해야 하는지 아무 규칙이 없다.
- 지국들은 매체에 접근하기 위해 서로 경쟁한다.
- 2개 이상의 지국이 동시에 전송하려고 하면 접근에 대한 충돌(Collision)이 발생한다.
ALOHA
- 임의 매체 접근 방법
순수 ALOHA
- 프레임의 한 비트라도 다른 프레임의 한 비트하고 충돌이 생기면 두 프레임 모두 훼손될 수 있다.
- 순수 ALOHA 프로토콜은 수신자가 잘 받았다는 확인응답에 의존
- 타임아웃이 될 때까지 오지 않으면 지국은 프레임이 훼손된 것으로 간주하여 다시 전송
- 1, 3번 지국에서 보낸 프레임만 제대로 전송됨
- 충돌이 발생하면 각 지국은 임의 시간을 기다린 후 재전송
- 이 임의 대기 시간을 대기 시간(back-off time)이라고 한다.
취약 시간(vulnerable time)
- 충돌 위험이 있는 시간
- 지국 A와 B가 전송한 프레임 사이에 충돌 발생
- 지국 B와 C가 전송한 프레임 사이에 충돌 발생
처리율(Throughput)
- 성공적으로 전송되는 프레임의 개수
- G: 한 프레임 전송 시간 동안에 시스템 전체에서 생성되는 프레임의 평균 개수
- S: 성공적으로 전송되는 프레임의 평균 개수
틈새(slotted) ALOHA
- 틈새 ALOHA에서는 시간을 T(fr)의 틈새로 나누어 지국은 매 시간 틈새가 시작할 때에 전송하도록 규제한다.
- 지국은 오직 동기화된 시간 틈새가 시작될 때에만 프레임을 전송할 수 있음
- 2개의 지국이 동시에 같은 시간 틈새에 전송 시도시 충돌 발생
반송파 감지 다중 접근(CSMA, Carrier Sense Multiple Access)
- 각 지국이 전송하기 전에 먼저 매체의 상태를 확인할 것을 요구
- 충돌 가능성을 줄일 수는 있으나 완전히 없애는 것은 없음
- 전파 지연 때문에 충돌 위험 존재
- t(1)에서 지국 B가 매체를 감지하여 매체가 휴지 상태에 있다고 판단하여 프레임을 전송한다.
- 시간 t(2) 에서 지국 C가 매체를 감지하여 휴지 상태에 있다고 판단하는데, 이는 이 시각에 B가 보낸 프레임의 첫 번째 비트가 아직 C에게 도달하지 않았기 때문
- 지국 C 또한 프레임을 전송하면 두 신호는 충돌하여 두 프레임 모두 손상
취약 시간
- CSMA의 취약 시간은 전파 시간(propagation time) T(p)이다.
- 이 시간은 신호가 매체의 한 끝에서 다른 끝으로 전파되는 데 소요되는 시간이다
- 위 그림은 최악의 경우이다.
- 회색으로 표시된 부분이 시간과 공간상의 취약 지역이다.
지속 방식
- 채널이 사용 중, 휴지 상태이면 지국이 무엇을 할지
1 - 지속 방식(1 - Persistent)
- 이 방식에서는 지국이 회선이 휴지 상태인 것을 감지하게 되면 즉각 프레임을 전송한다.
- 2개 이상의 지국이 회선이 휴지 상태인 것을 감지하고 그 경우 즉각 프레임을 존송하기 때문에 가장 높은 충돌 위험을 유발
비지속 방식(Nonpersistent)
- 전송할 프레임이 있는 지국이 회선을 감지한다.
- 회선이 휴지상태에 있으면 즉각 프레임을 보낸다
- 휴지 상태에 있지 않으면 임의 시간을 대기하고 다기 회선을 감지한다.
- 전송할 프레임이 있는 지국이 있음에도 불구하고 회선이 휴지 상태에 있을 수 있기 때문에 회선의 효율이 낮아진다.
p - 지속 방식(p-Persistent)
- 채널이 최대 전파 지연 시간과 같거나 그보다 큰 시간 틈새를 사용하는 경우에 채택된다.
- p - 지속 방식은 위의 두 가지 방식의 장점을 합한 것이다
- 회선이 휴지 상태에 있는 것을 감지하면
- 학률 p를 가지고 프레임을 전송한다.
- 확률 q = 1 - p를 가지고 지국은 다음 틈새 시작까지 기다리다가 회선을 다시 감지한다.
- 만일 회선이 휴지 상태이면 1번 단계로 간다.
- 만일 회선이 사용 중이면 충돌이 생긴 것으로 간주하고 대기 절차에 들어간다.
반송파 감지 다중접근/충돌 검출 (CSMA/CD, with Collision Detec-tion)
- 이 방법에서 지국은 프레임을 전송한 뒤에 전송이 성공적인지 매체를 관찰한다.
- 실패면 충돌이 생긴 것이며, 프레임을 다시 전송한다.
- 지국 A와 C가 충돌
- t(1)에서 지국 A는 자신의 지속 절차에 따라 프레임의 비트들을 전송하기 시작
- t(2)에서 지국 C는 A가 보낸 프레임의 첫 번째 비트를 아직 감지하지 못한다.
- 지국 C는 지속 절차를 수행하여 자신의 프레임 비트들을 전송하는데 그 비트는 왼편과 오른편으로 전파된다.
- 충돌은 시각 t(2) 이후에 발생
- 지국 C는 시각 t(3)에 A가 보낸 프레임의 첫 번째 비트를 수신하게 되어 충돌을 감지한다.
- 지국 C는 즉각 전송하는 것을 멈춘다.
- 지국 A는 C의 프레임의 첫 번째 비트를 수신한 시각 t(4)에 충돌을 알게 되어 자신도 즉각 전송하던 것을 멈춘다.
예제
CSMA/CD를 사용하는 네트워크의 대역폭은 10Mbps다. 최대 전파 시간 (디바이스의 지연을 포함하며 방해 신호를 보내는 데 필요한 시간은 무시합니다. 나중에 참조)이 25.6μs인 경우 프레임의 최소 크기는 얼마인가?
➡️ 최소 프레임 전송 시간은 T(fr) = 2 × T(p) = 51.2μs
3.3.2 제어 접근(Controlled Access)
제어접근에서 지국들은 서로 상의하여 어느 지국이 전송할 권리를 갖는지 찾는다.
예약(Reservation)
- 예약 방식에서 지국은 데이터를 전송하기 전에 예약을 해야 한다.
- 시간은 구간들로 나눠 각 구간마다 예약 프레임이 그 구간에 전송되는 데이터 프레임의 앞에 놓인다.
- 모두 N개의 지국이 있다면 예약 프레임에는 N개의 예약 미니틈새(minislot)가 있다.
- 각 미니 틈새는 한 지국에 속한다.
- 어떤 지국이 데이터 프레임을 보내려고 하면 자신의 미니틈새에 예약한다.
- 위 그림은 5개의 미니틈새 예약 프레임을 보여준다.
- 첫 번째 구간에는 1, 3, 4 번 지국이 예약을 했다.
- 두 번째 구간에서는 1번 지국이 예약을 했다.
폴링(Polling)
- 폴링은 지국 중 하나가 주국(primary station)이 되고 다른 지국은 종국(secondary stations)이 되는 접속 형태에서 동작한다.
- 종국으로 가는 데이터도 모두 주국을 통해서 전달된다.
선택(Select)
- 선택 시능은 주국이 무엇을 보낼 것이 있을 때마다 수행된다.
- 데이터를 전송하기 이전에 주국은 선택(SEL)프레임을 만들어서 전송한다.
- 그 프레임의 필드 중 하나가 보내려고 의도하는 종국의 주소를 포함한다.
폴(Poll)
- 주국이 종국들로부터 전송을 요청할 때 이용한다.
- 주국이 데이터를 수신할 준비가 되어 있으면 각 장치에게 차례로 보낼 것이 있는지 물어봄(Polling)
- 주국은 부정 확인 응답(NAK)을 받으면 데이터를 보낼 종국을 찾을 때까지 다음 종국에게 동일하게 묻는다.
- 확인 응답이 긍정일 때 주국은 프레임을 읽어 들이고 확인응답(ACK)을 보내어 받은 것을 확인해 준다.
토큰 전달(Token Passing)
- 토큰 전달 방식에서 네트워크 안의 지국들은 논리 링 형태로 구성된다.
- 각 지국에는 선행자(Predecessor)와 후행자( Sucessor )가 있다.
- 선행자는 링 접속형태에서 논리적으로 앞에 있는 지국이며 후행자는 링의 바로 뒤에 있는 지국이다.
3.4 링크 계층 주소 지정
'데이터 통신과 네트워킹 TCP-IP프로토콜 기반' 카테고리의 다른 글
| [데이터 통신과 네트워킹-TCP/IP프로토콜 기반] 6장 연결 장치와 가상 LAN (0) | 2025.01.07 |
|---|---|
| [데이터 통신과 네트워킹-TCP/IP프로토콜 기반] 5장 광역 통신망: WAN (0) | 2024.12.19 |
| [데이터 통신과 네트워킹-TCP/IP프로토콜 기반] 4장 (0) | 2024.11.28 |
| [데이터 통신과 네트워킹-TCP/IP프로토콜 기반] 2장 물리층 (2) | 2024.11.14 |
| [데이터 통신과 네트워킹-TCP/IP프로토콜 기반] 1장 개요 (1) | 2024.11.10 |