Study & Project repository

Link layer

• 지금까지 고려하지 않은 것들을 고려
• 에러 찾기, 고치기 가능
• 렌카드를 허브에 연결 -> 여러 선을 연결하여 broadcast media -> 같은 서브넷 안에 있는 디바이스들이 사용하는 허브로 연결한 네트워크는 전부 1홉
• IP address : 인터넷 상에 한 호스트로 가기 위해 필요한 주소 -> Link layer에서 사용하는 address가 따로 존재(MAC)
• 인스턴스화, 다양한 링크 계층 기술 구현
• 모바일망 -> 기관(같은 서브넷을 사용) -> link layer가 공유
• 호스트와 라우터들을 노드라고 칭함
• 통신 경로를 따라 인접 노드들을 연결 하는 통신 채널들을 link라고 함
• 유선 링크
• 무선 링크
• LANs
• 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가 필요
• ex) 편지를 쓸때, 받는 사람의 주소와 우체국의 주소는 다름 -> 받는 사람의 주소 : host, 우체국의 위치 : router
• 프리스턴에서 로잔까지의 여행으로 비유해보면
• 프리스턴에서 JFK까지는 리무진을 타고
• JFK에서 제네바까지는 비행기를
• 제네바에서 로잔까지 기차를 타고 감
• 관광객 = 데이터 그램
• 교통편 = 커뮤니케이션 링크
• 운송 방식 = 링크 계층 프로토콜
• 여행사 = 라우팅 프로토콜

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 = 오류 검사로 보호되는 데이터, 헤더 필드가 포함될 수 있음
• 과정
1. Data D에 오류 검출 및 정정 비트들(EDC)를 첨가
2. D에는 링크 프레임 헤더에 있는 링크 수준의 주소 정보와 순서번호 및 기타 필드들을 포함
3. D와 EDC는 링크 수준 프레임에 포함되어 수신 노드로 전송
4. 수신 노드에서 비트열 D'과 EDC'을 수신
5. 수신자는 D'과 EDC'만으로 원래의 D가 D'과 동일한지 결정
6. 수신자는 오류 검출과 정정 기술을 사용하여 항상은 아니지만 거의 모든 비트 오류를 검출할 수 있음 -> 여전히 미검출된 비트 오류가 있을 수 있음
• 100% 신뢰할 수 없는 오류 감지
• 프로토콜이 일부 오류를 가끔씩 놓침
• EDC가 커지면 검출 및 수정이 향상

Parity checking

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

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

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

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

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

multiple access protocols

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

• point-to-point link : 한쪽 끝에 한 송신자와 링크의 다른 쪽 끝에 한 수신자가 있음
• broadcast link : 동일한 하나의 공유된 브로드캐스트 채널에 다수의 송신 노드 및 수신 노드들이 연결 -> 브로드캐스트는 임의의 한 노드가 프레임을 전송하면 채널이 그 프레임을 방송(broadcast)해서 다른 모든 노드들이 그 프레임의 복사본을 수신하기 때문에 사용된 것
• 단일 공유 브로드 캐스트 채널의 경우 2개 이상의 정보를 수신하면 충돌과 간섭이 일어나는 문제가 있음
• 다중 접속 프로토콜을 개발 : 노드가 채널을 공유하는 방식을 결정하는 분산 알고리즘, 즉 노드가 언제 전송할 수 있는지 결정
1. 하나의 노드가 전송하기를 원할 때, 그것은 레이트 R로 전송할 수있다.
2. M 개의 노드가 전송하기를 원할 때, 각각은 평균 비율로 전송할 수있다. R / M
3. 전송 조정을위한 특별한 노드가 없다 -> 클록, 슬롯의 동기화 없음
4. 단순하다

• TDMA : time division multiple access
• 시간을 시간 프레임으로 나누고 각 시간 프레임을 N개의 시간 슬롯으로 나눈다.

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

• FDMA : frequency division multiple access
•  Rbps의 채널을 다른 주파수로 나눠서 각 주파수를 N개 노드 중 하나에게 할당

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

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

• 전송노드는 항상 채널의 최대 전송률인 Rbps로 전송
• 충돌이 생기면 충돌과 관련된 각 노드는 프레임이 충돌없이 전송될 때까지 자신의 프레임을 계속해서 재전송
• Slotted ALOHA
• 모든 프레임은 정확히 L 비트로 구성
• 시간은 L/R초의 슬롯들로 나뉜다 -> 한 슬롯은 한 프레임 전송에 걸리는 시간과 같다
• 노드는 슬롯의 시작점에서만 프레임을 전송하기 시작
• 각 노드는 언제 슬롯이 시작하는지 알 수 있게끔 동기화되어 있다
• 한 슬롯에서 2개 이상의 프레임이 충돌하면, 모든 노드는 그 슬롯이 끝나기 전에 충돌 발생을 알게된다
• 노드가 새로운 프레임을 획득 할 때, 다음 슬롯이 시작할 때까지 기다렸다가 그 슬롯에 전체 프레임을 전송
• 만약 충돌하지 않으면, 노드는 성공적으로 자신의 프레임을 전송한 것
• 만약 충돌하면, 노드는 그 슬롯이 끝나기 전에 충돌을 검출
• 노드는 그 프레임이 충돌없이 전송될 때까지 확률 p로 해당 프레임을 다음 슬롯들에게 재전송
• 재전송을 할지말지 랜덤으로 결정하며 재전송을 하더라도 또 다시 충돌할 가능성이 많다

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

• 슬롯 알로하 프로토콜은 모든 노드가 슬롯의 시작점에서 전송을 시작할 수 있도록 동기화되어 있기를 요구
• 처음의 알로하 프로토콜은 슬롯이 없고 완전히 분산된 프로토콜이었다
• 프레임이 도착하면(네트워크 계층 데이터그램이 송신 노드의 네트워크 계층으로부터 아래로 전달되면) 노드는 즉시 그 프레임 전체를 브로드캐스트 채널로 전송
• 만일 전송된 프레임이 하나 이상의 다른 전송과 충돌하면, 노드는 확률 p로 그 프레임을 즉시 재전송(충돌된 프레임이 완전히 전송된 후에)
• 즉시 재전송하지 않는 경우, 노드는 프레임 전송 시간동안 기다림
• 기다리고 나서 그 프레임을 확률 p로 전송하거나 아니면 확률(1-p)로 또 다른 프레임 시간 동안 기다림

• 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)

• 위의 두 알로하에서 노드가 전송 여부를 결정하는 것은 브로드캐스트 채널에 접속되어 있는 다른 노드의 활성 여부와 무관
• 노드는 전송 시작 시 다른 노드의 전송 여부에 대해서는 주의하지 않을 뿐만 아니라, 만일 다른 노드가 자신의 전송을 간섭하는 경우에도 자신의 전송을 중지하지 않는다
• 그러므로 CSMA에서는 이러한 문제점을 없애기 위해 두 가지 규칙을 정함
1. 말하기 전에 듣는다 : 만일 다른 사람이 전송하고 있으면, 전송이 끝날 때까지 기다려라. 네트워크에서는 이것을 캐리어 감지(carrier sensing)라고 한다 -> 노드는 전송하기 전에 채널을 듣는다
2. 전송 중단을 감지하면 대기하고 있던 노드는 전송을 시작함
3. 다른 사람이 동시에 말하기 시작하면 말을 중단한다 : 네트워크에서는 이것을 충돌 검출(collision detection)이라 한다 -> 송신 노드는 전송하면서 동시에 채널을 듣는다
4. 만일 다른 노드가 방해 프레임을 전송하고 있음을 검출하면, 자신의 전송을 중단하고 랜덤 시간 동안 기다린 후 감지 및 전송 과정을 반복

• 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에게 노드 1이 최대로 보낼 수 있는 프레임 수에 대한 정보를 지닌 메시지를 전송
• 노드 1이 프레임들을 보낸 다음에 노드 2에게 노드 2가 최대로 보낼 수 있는 프레임 수를 알려줌
• 마스터 노드는 순환적으로 각 노드를 폴링하는 방식으로 이 과정을 반복

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을 통해 데이터 그램 보내기

1. A가 B의 IP 주소를 알고 있다고 가정
2. A가 첫 번째 홉 라우터의 IP 주소를 알고 있다고 가정
3. R의 MAC 주소를 알고 있다고 가정
4. A는 IP 소스 A, 목적지 B로 IP 데이터 그램을 생성
5. A는 목적지 주소로 R의 MAC 주소를 갖는 링크 계층 프레임을 생성하고, 프레임은 A-to-B IP 데이터 그램을 포함
6. A에서 R로 보낸 프레임
7. R에서 수신 된 프레임, 제거 된 데이터 그램, IP에 전달 된 프레임
8. R은 IP 소스 A, 목적지 B로 데이터 그램을 전달
9. R은 목적지 주소로 B의 MAC 주소를 갖는 링크 계층 프레임을 생성하고, 프레임은 A-to-B IP 데이터 그램을 포함
10. B로 도착