6. Link layer

Link layer

• 지금까지 고려하지 않은 것들을 고려
• 에러 찾기, 고치기 가능
• 렌카드를 허브에 연결 -> 여러 선을 연결하여 broadcast media -> 같은 서브넷 안에 있는 디바이스들이 사용하는 허브로 연결한 네트워크는 전부 1홉
• IP address : 인터넷 상에 한 호스트로 가기 위해 필요한 주소 -> Link layer에서 사용하는 address가 따로 존재(MAC)
• 인스턴스화, 다양한 링크 계층 기술 구현
• 모바일망 -> 기관(같은 서브넷을 사용) -> link layer가 공유
• 호스트와 라우터들을 노드라고 칭함
• 통신 경로를 따라 인접 노드들을 연결 하는 통신 채널들을 link라고 함
• Link layer에서는 데이터 패킷을 frame이라고 부름 -> 네트워크 레이어의 데이터그램을 캡슐화
• data-link layer에서는 물리적으로 붙어있는 서브넷들에게 어떻게 잘 전달할 수 있을지가 가장 중요

link layer 종류

• LANs
• wifi
• 이러한 것들을 모두 처리할 수 있어야함 -> 어떤것으로 받아도 처리하여 상위계층에서 동일한 형식으로 사용할 수 있어야 함
• logical : frame form은 비슷
• 각 링크 프로토콜은 서로 다른 서비스들을 제공 - ex)rdt를 제공하는 링크도 있지만 제공하지 않는 링크도 존재

transportation analogy(교통에 비유)

• 라우터까지 host가 직접 전송해야하기 때문에 Link layer는 모든 host에 존재
• 라우터까지 데이터를 보낼 때 IP address를 사용할 수 없음 -> MAC address가 필요
• 프리스턴에서 로잔까지의 여행으로 비유해보면

---

Link layer services

• framing - 데이터그램을 프레임에 캡슐화하고 헤더와 trailer를 추가
• link access - 매체 접속 제어(medium access control, MAC) 프로토콜은 링크상으로 프레임을 전송하는 규칙에 대해서 명시, 하나의 브로드캐스트 링크를 여러 노드가 공유하는 경우(다중 접속), MAC 프로토콜은 여러 노드로부터의 프레임 전송을 조정
• 신뢰적 전달 - 인접한 노드 사이의 안정적인 전달, 트랜스포트 계층의 신뢰적 전달 서비스와 마찬가지로, 링크 계층의 신뢰적 전달 서비스도 확인응답(ACKnowledgment)과 재전송을 통해 가능해짐
• 오류 검출과 정정 - 신호의 약화나 전자기 잡음 때문에 생기는 오류(0을 1로, 1을 0으로 오인)를 검출하는 방법을 제공 -> 수신기는 재전송에 의지하지 않고 비트오류를 식별하고 수정
• 흐름제어 : 인접한 송신 노드와 수신 노드 사이의 페이스를 맞춤
• half-duplex(보내거나 받거나 할 수 있지만 보낼때는 보내기만, 받을때는 받기만 가능)와 full-duplex(보내기와 받기 동시에 가능)

---

Where is the link layer implemented?

• 대부분의 경우 링크 계층은 네트워크 인터페이스 카드(Network Interface Card, NIC)로 알려진 네트워크 어뎁터(network adapter)에 구현
• 링크, 물리계층 구현
• 호스트의 시스템 버스에 연결
• 하드웨어, 소프트웨어, 펌웨어의 조합

 

Adaptors communicating

 

• sending side : 프레임에 데이터그램 캡슐화 + 오류 검사 비트, rdt, flow control 등을 추가
• receiver side : 오류, rdt, flow control 등을 확인, 데이터그램 추출, 수신 측 상위 계층 통과

---

Error detection

• EDC = Error Detection and Correction bits(redundancy) - 오류 감지 및 수정 비트(중복성)
• D = 오류 검사로 보호되는 데이터, 헤더 필드가 포함될 수 있음
• 과정
• 100% 신뢰할 수 없는 오류 감지

Parity checking

• single bit parity : 한 비트의 에러를 검출

• 짝수 패리티 : d+1개의 비트들 중에서 1의 총개수가 짝수가 되도록 선택
• 홀수 패리티 : 1의 개수가 홀수 개가 되도록 선택
• 수신자는 수신된 d+1개의 비트들에서 1의 개수를 계산
• 만약 짝수 패리티 기법에서 1의 개수가 홀수 개라면 최소한 하나의 비트 오류가 있음을 알게됨 -> 임의의 홀수개의 비트 오류

• two-dimensional bit parity : 2차원 패리티 기법

 

• 반전된 비트를 포함하는 열과 행에 대한 패리티에 오류가 생김
• 따라서 단일 비트 오류의 발생을 검출할 수 있을 뿐만 아니라, 패리티 오류가 있는 열과 행의 인덱스값을 사용해 잘못된 비트를 실제로 식별해서 오류를 정정할 수도 있음
• 임의의 2개의 오류도 검출할 수 있으나 정정은 하지 못함

• checksum도 사용 -> 이전 강의에서 다루었던 내용

---

multiple access protocols

• 다중 접속 링크와 프로토콜

• TDMA : time division multiple access

1. 각 슬롯에 해당하는 사용자만 전송을 할 수 있으므로 충돌이 발생하지 않게 된다
2. 하지만 슬롯을 배정받은 한 사용자가 전송을 모두 마친 상태에서도 여전히 그 슬롯은 비어있기 때문에 시간적인 낭비가 생길 수 있다.

• FDMA : frequency division multiple access

1. 슬롯을 기다리는 시간은 없어지겠지만 여전히 R/Nbps로 고정된 대역폭을 가진다.

Random access protocols : 랜덤 접속 프로토콜

• 전송노드는 항상 채널의 최대 전송률인 Rbps로 전송
• 충돌이 생기면 충돌과 관련된 각 노드는 프레임이 충돌없이 전송될 때까지 자신의 프레임을 계속해서 재전송
• Slotted ALOHA

1. 단일 노드인 경우에는 단순하고 채널의 최대 속도로 연속적으로 전송할 수 있음
2. 그러나 다중 노드일 경우에는 위의 그림처럼 충돌이 많이 발생하고 대기하는 빈 슬롯들도 발생한다는 단점이 있다
3. Slotted ALOHA의 최대 효율 유도

모든 노드들이 항상 p의 확률로 재전송 된다고 가정했을 떄, (1-p)의 확률로 대기하게 됨

1. 우선 N개의 노드가 있다고 가정
2. 그렇다면 주어진 슬롯이 성공적인 슬롯일 확률은 1개만 전송되고 나머지 N-1개의 노드는 전송되지 않을 확률
3. 주어진 노드가 전송될 확률은 p, 나머지 노드가 전송되지 않을 확률은 (1-p)^(N-1)이고 N개의 노드가 있으므로

   4.   이 확률이 최대가 되기 위해서 E(p)값을 미분하여 그 값이 0이 될 때의 p값을 구해보자

   5.   그러면 p = 1/N이 나온다 -> 1도 함께 나오는데 이는 무조건 충돌없이 모두 성공했을 경우

   6.   활성 노드가 매우 많을 경우의 최대 효율을 구하고 싶은 것이므로 N의 값(노드의 개수)을 무한대로 보내면 공식에 의해 1/e = 0.37이라는 값이 도출(37%)

• Pure (unslotted) ALOHA

• t0라는 시간에 한 프레임을 전송한다고 가정해보자 이 프레임이 성공적으로 저송되기 위해서는 다른 노드들이 [t0-1,t0]동안 전송을 시작해서는 안된다
• 먼저 전송하지 않을 확률이 (1-p)^(N-1), 그리고 전송중에 다른 전송을 할 확률이 (1-p)^(N-1)이다
• 따라서 N개의 노드들이 모두 성공적인 전송을 할 확률은 p(1-p)^2(N-1)이다
• 효율 E(p) = Np(1-p)^2(N-1)이고
• 위의 최대효율 공식을 적용시킨 pure ALOHA의 최대 효율은 1/2e = 0.18 밖에 되지 않는다

• CSMA(carrier sense multiple access)

 

• t0에서 채널이 비어있음을 감지하고 전송을 시작
• 전송한 비트들이 브로드캐스트 매체를 따라 양방향으로 전파
• 시간이 경과하면서 비트들이 아래쪽으로 전파되는 것은 실제로 전파할 때 완전히 전파되기 위해서 약간의 시간이 걸림을 의미
• t1일때 아직 처음 전송한 비트가 도달하지 않은 노드에서 비어있는 것으로 감지하고 전송을 시도할 수 있음
• 이렇게 되면 두 전송이 서로 간섭을 일으키게 됨
• 그러므로 채널의 한 쪽 끝에서 다른 쪽 끝으로 전파되는데 걸리는 시간(채널 전파 지연 - channel propagation delay)을 짧게 해야만 이미 시작된 전송을 빠르게 감지할 수 있음

• CSMA/CD : collision detection)

1. 어댑터(NIC)는 네트워크 계층으로부터 데이터그램을 받아서 링크 계층 프레임을 만든 후에 그 프레임을 어댑터의 버퍼에 저장
2. 어댑터는 채널이 유휴(idle)한 것을 감지하면 프레임 전송 시작 -> 만약 어댑터가 채널이 바쁜 것을 감지하면 어떤 신호 에너지도 감지되지 않을 때까지 더 기다렸다가 프레임을 전송
3. 전송하는 동안 어댑터는 브로드캐스트 채널을 사용하는 다른 어댑터로부터의 신호 에너지가 있는지 감시
4. 프레임 전체를 전송하는 동안 다른 어댑터로부터의 신호 에너지가 감지되지 않으면, 프레임 전송을 완료
5. 그러나 전송 도중에 다른 어댑터로부터의 신호 에너지를 감지하면, 자신의 프레임 전송을 취소
6. 어댑터는 전송을 취소한 후 임의의 랜덤 시간만큼 기다린 후 단계 2로 돌아감
7. 효율

---

"Taking turns" MAC protocols

• polling : 노드 중 하나를 마스터 노드로 지정

 

1. 충돌 뿐만이나라 빈 슬롯의 문제도 없애주어 훨씬 높은 효율을 제공
2. 폴링 지연(노드가 전송할 수 있음을 알리는 데 걸리는 시간) - ex)한 노드만 활성이면 활성 노드가 프레임을 최대 개수만큼 보낼 때마다 마스터 노드는 비활성 노드들을 차례로 폴링해야 하므로, 활성 노드는 Rbps보다 작은 전송률로 전송하게 된다
3. 마스터 노드가 고장나면 전체 채널이 동작하지 못하게 됨

• token passing

 

1. 예를들어 노드 1은 항상 노드 2에게 토큰을 전송하며, 노드 2는 항상 노드 3에게 토큰을 전송하고, 노드 N은 항상 노드 1에게 토큰을 전송
2. 노드가 토큰을 수신하면, 전송할 프레임이 있을 때만 토큰을 붙잡는다
3. 전송할 프레임이 없다면 토큰을 즉시 다음 노드로 전달
4. 전송할 프레임이 있다면 프레임을 최대 개수까지 전송한 뒤 토큰을 다음 노드로 전달
5. 분산 방식이며 매우 효율이 높다
6. 그러나 노드 하나가 실패하면 전체 채널이 동작하지 않는 문제가 있다
7. 노드가 잘못해서 토큰을 놓아주지 않으면 토큰이 다시 돌 수 있도록 하는 회복 절차가 실행

---

MAC addresses and ARP

• 48bit의 MAC address는 링크 계층 주소를 의미한다 -> 2^48만큼의 사용 가능한 랜 주소
• 16진수로 표시된다 -> 1A-2F-BB-76-09-AD
• 각 어댑터에는 고유한 주소를 가지고 있음

 

• IEEE가 MAC주소 공간을 관리하기 때문에 각각 다른 회사에서 만들어낸 것들의 주소들 까지 겹치지 않고 고유한 주소를 가지게 되는 것
• LAN카드를 한 LAN에서 다른 LAN으로 이식할 수 있음
• ARP 테이블 : LAN의 각 IP 노드 (호스트, 라우터)에 테이블이 있다
• 예시

1. A가 B에 데이터 그램을 보내려고 한다
2. B의 MAC 주소가 A의 ARP 테이블에 없다
3. A는 B의 IP 주소를 포함하는 ARP 쿼리 패킷을 브로드 캐스트
4. 목적지 MAC 주소 = FF-FF-FF-FF-FF-FF를 알려줌
5. LAN상의 모든 노드는 ARP 쿼리를 수신
6. B는 ARP 패킷을 수신하고 A에게 B의 MAC 주소로 응답
7. 프레임이 A의 MAC 주소로 전송
8. A는 정보가 오래 될 때까지 ARP 테이블에 IP-MAC 주소 쌍을 캐시

• 다시 위의 그림을 가지고 연습 : A에서 B로 R을 통해 데이터 그램 보내기