컴퓨터 네트워크 정리 -13주차- <링크 레이어/5.1 - 5.3>

Chapter 5 Link Layer

-      목표 : 링크 레이어의 원칙을 이해한다.

• 에러 검출 및 정정
• 브로드캐스트 채널 공유 : multiple access (ex:와이파이)
• Link layer addressing (MAC 주소 사용=6byte)
• Local area networks : Ethernet, VLANs

-      링크 레이어를 생성 및 구성하는 다양한 기술에 대한 이해

Link Layer : introduction

-      Terminology(용어)

• Hosts, Routers : nodes
• Links : 중간 소통 통로
  • Wired links
  • Wireless links
  • LANs
• Layer-2 packet : frame (APP:MSG, TRANSFER:SEG, NET:PACKET, LINK:FRAME)

Link Layer : context

-      데이터그램은 다양한 링크에 따른 다양한 프로토콜을 따라 전송된다.

Ex) 시작은 Ethernet 링크를 따라서 진행되어 마지막엔 802.11 와이파이로 전송가능

Link Layer services

-      Framing, link access:

• Framing : Datagram에 해더와 꼬리를 붙여 frame화 시킨다.
• Link Access : 만약 shared medium이면 채널에 접근한다.
• 프레임 해더에 소스 구분을 위해 ‘MAC’ 사용

-      이웃 노드간 RDT (reliable data transfer), 하지만 여기선 CRC를 통해 구현됨

• CRC => wireless links : high error rates <= 요걸 검출해냄

-      Flow control : 송신 rate를 제한해서 수신 rate를 초과하게 하지 않는다. => 수신자는 현재 적재가능 용량을 ack header에 담아 보낸다. 이를 수신자가 확인하고 송신 빈도 결정
But link layer에선 조금 다르게 접근한다?

-      Error detection : CRC

-      Error correction : We don’t do, 대신 link layer에선 resending으로 극복한다.

-      Half-duplex and full-duplex

• 802.11 와이파이 모듈은 half-duplex, 왜냐면 동시에 송수신은 못하고 한번에 한 역할만 가능하기 떄문.

Link layer implement (NIC)

-      링크 레이어는 adaptor (Network Interface Card) 또는 마더 보드 칩에서 생성(on chip)

Adaptors Communicating

-      Sending side :

• 데이터그램을 프레임으로 캡슐화
• 에러확인비트 추가, rdt, flow control 수행

-      Receiving side :

• 에러를 확인하고, rdt, flow control 수행
• 데이터그램 추출, 상위 레이어로 넘김 

Error Detection

EDC = Error Detection and Correction bits (redundancy:중복성)
D = Data (collapse or not)

-      에러검출은 100% 확실하진 않다. 이유는 Parity checking에서 나옴

 

Parity checking

 

-      Single bit parity

• 홀/짝 방법이 있으며, 짝수 방법을 쓰는 경우, D data내 1의 개수가 홀수면 parity bit에 1을 추가해 짝수를 만든다.
• 하지만 2개 이상의 오류가 발생해, 짝수인 경우 확인할 수 없다.

-      Two-dimensional bit parity

• 2차원으로 패리티확인, 2개의 에러 검출
• 그러나 한 행/열에 복수 에러 검출 X
• 이것이 100프로 에러 검출 할 수 없는 이유다.

Internet checksum (또 다른 에러 검출 법)

-      목표 : transport layer에서만 사용 가능하며, 전송된 패킷에서 ‘여러 에러’를 검출하는 것

-      Sender

• Segment contents를 16비트 정수의 연속체로 다룬다.
• Segment contents의 합의 1의 보수 값을 checksum으로 둔다.
• Sender는 이 checksum 값을 ‘UDP’의 checksum field에 기입한다.

-      Receiver

• Checksum을 포함한 수신 데이터의 합(모두 1이어야 함)의 1의 보수(모두 0 이어야 함)를 취한 값이 모두 1으로 되어있는지 계산, 만약 한 비트라도 0이면 오류

 

 

Cyclic Redundancy Check (CRC) Error detection

-      D 비트로 이뤄진 데이터 D를 송신노드가 수신노드로 전송한다 가정

-      송신자와 수신자는 G로 표기되는 생성자를 통해 r+1비트 패턴에 대해 합의

-      G의 최상위(가장 왼쪽) 비트는 1이다.

-      주어진 데이터 D에 송신자는 r개의 추가 비트 R을 선택해, D에 덧붙인다.

-      d + r비트 패턴은 mod 2 연산시 G로 명확히 나뉜다. =>D*(2^r) XOR R = nG

-      이제 수신자는 d+r개의 수신비트를 G로 나눠, 나머지가 0인지 아닌지를 통해 오류 판별을 한다.
여기서 r = g 비트의 개수 – 1 이다.

 

Multiple access links, protocols

-      링크는 2종류가 있다.

• Point-to-point : 링크 끝에 송수신자 존재
• Broadcast (shared wire or medium) : 공유 브로드캐스트 채널에 다수의 송수신 노드

Multiple Access Protocols

-      충돌 : 수신자 측에서 발생하며, 두개 이상의 signals이 동시에 도착하면 발생

-      이 충돌을 최소화하는게 MAP의 목표다.

-      분산알고리즘을 통해 얼마나 많은 노드들이 채널을 공유하는가를 결정짓는다.

-      out-of-band를 사용하지 않고 in-band를 사용해, 컨트롤과 데이터 전달을 한 채널에서 진행하도록 해야 한다.

An ideal multiple access protocol

-      given : 브로드캐스트 채널의 rate = R bps

-      희망사항 : 한 노드의 송신주기 = R, M개의 노드가 송신 희망 => R/M rate, 이를 보장하기 위해선, 탈중앙화해야 함, 이 과정이 모두 심플했으면 함.

 

 

MAC protocols: taxonomy(분류)

-      채널 분리 (channel partitioning) : 채널을 ‘pices’로 나눠, 노드에게 할당 = TDMA

-      랜덤 접근 (random access) : 충돌 허용, 하나의 채널 사용, 충돌시 회복작업

-      Taking turns : 노드에게 turn이라는 토큰을 쥐어준다.

Channel Partitioning MAC protocols: TDMA

-      TDMA : time division multiple access

• 시간을 ‘시간 프레임’으로 나누고 각 프레임을 n개의 ‘time slot’으로 나눈다.
• n개의 노드는 1/n개의 슬롯을 할당 받고, 전송할 때, 할당된 시간 슬롯 동안 패킷 비트들을 전송한다.
• 아주 공정하고 바람직하지만, 전송할 패킷이 없을 때도 슬롯이 할당되어 시간 최적화되진 않는다.

Channel Partitioning MAC protocols: FDMA

-      FDMA : frequency division multiple access

• R bps의 채널을 주파수별로 나눠, 각 주파수 영역에 N개의 노드 중 하나를 할당
• 모든 노드가 갖는 주파수 대역폭이 같아지는데, 이는 전송 패킷 양과 상관없이 할당된다는 단점이 있다.

Random Access Protocol

-      각 노드가 항상 채널의 최대 전송률인 R bps로 전송

-      충돌시 재전송, 랜덤 지연시간 동안 기다렸다가 전송

-      여기에 CDMA, slotted ALOHA 등등이 포함된다.

Slotted ALOHA

-      가정

• 모든 프레임이 같은 크기를 갖는다.
• 시간은 L/R초의 슬롯들로 나뉜다.
• 각 노드는 언제 슬롯이 시작하는지 알 수 있게 동기화 돼있다.
• 한 슬롯에서 2개 이상의 프레임충돌 발생, 모든 노드는 충돌 발생을 알게 된다.

-      동작

• 충돌 없을 때 => 다음 프레임 준비
• 충돌 발생 => 슬롯이 끝나기 전에 충돌 검출, 해당 프레임이 충돌 없이 전송될 때 까지의 일정 확률을 가진 slot 뒤에 다시 보낸다.

-      장점 : 각 노드가 충돌 감지, 전송 시점을 결정함으로 분산되어 있다.

-      단점 : 활성 노드가 여럿일 때, 일부 슬롯이 충돌로 인해 낭비될 위험이 있다.

-      효율성 연산

• 한 노드가 슬롯안에 프레임을 전송시킬 확률 prob = p(1-p)^(N-1)
• 어떤 노드가 성공할 확률 : Np(1-p)^(N-1)
• Max efficiency = 해당 수식을 p에 대해 미분해서 최대값 찾기
• N이 무한대로 가면 => 해당 식은 1/e와 같다. =>.37 => 37%다.

Pure(unslotted) ALOHA

-      슬롯이 없고 동기화도 없다.

-      프레임이 도착하면 즉시 전송한다.

-      충돌 지점이 두곳이나 생김(2배가됨).

-      효율성 연산

• 성공 확률 = p * (1-p) ^ (N-1) * (1-p) ^ (N-1) = p * (1-p)^2(N-1)
• 이걸 또 미분떄리고 N을 최대화 => 1/(2e) = .18 = 슬롯에 비해 절반효율

CSMA (carrier sense multiple access)

-      Carrier Sense(캐리어 감지) : 다른 노드의 활성상태를 감지하고 활성화 여부를 결정한다.

-      여전히 충돌 확률 존재

 

• 노란점에서 propagate, 붉은점이 케리어 센싱을 못 하고 또 propagate, 두개의 신호가 섞인 영역이 발생하고 이 부분이 충돌되는 영역이다.
• 위 예시가 다른 노드의 행동을 파악하지 못해 발생하는 propagation delay 예시다.
• 이런 충돌 발생시 해당 패킷의 전송 시간은 버려지게 된다.

CSMA/CD (collision detection), CA (collision avoidance)

-      다른 노드가 동시에 활성화되면, 활성화를 중지한다. 그 후 랜덤 시간 동안 기다린 후 재전송을 한다. 이는 media의 전위차를 통해 이뤄진다.

-      CD는 이제 full duplex에서 사용하고 CA는 half duplex(802.11)에서 사용한다.

-      알고리즘

• NIC가 network layer에서 datagram을 받아 frame 생성
• NIC가 channel이 idle임을 감지하면, frame을 송신, 만약 busy면 idle 될 때까지 기다렸다 송신한다
• NIC가 다른 전송사항을 감지하지 못한 채, 모든 frame을 송신하면 끝난다.
• 만약 감지되면, 현재 전송 시그널을 중지시킨다.
• NIC가 중지하는 시간은, m번의 충돌이면, 2^m-1 * 512 bit times만큼 대기후 2번으로

“Taking turns” MAC protocols

-      Channel partitioning mac protocols은 high load 상태에선 공평하고 효율적, low load에선 비효율적

-      Random access mac protocols은 low load에선 효율적, high load에선 다수의 충돌발생

-      그래서 두 부분의 장점만 모아서 써보자!

-      Bluetooth, FDDI, token ring

Polling

-      노드 중 하나가 마스터 노드, 나머지는 노예

-      마스터는 중재자 역할을 하며, 어떤 노드가 사용될지 지정한다.

-      고려사항

• Polling overhead : master-slave-master의 traverse overhead 발생
• Latency : 마스터가 다른 slave랑 통신하며 기다리는 노예등장
• 중앙 집중형으로, 마스터가 죽으면 망한다.
  (single point of failure)

Token Passing

-      마스터 노드 X

-      토큰이라는 특수 목적형 프레임을 정해진 순서대로 노드 간에 전달

-      토큰을 가진 노드는 data를 보낼 수 있으며, 전송할 프레임이 있을 때만 토큰을 붙잡는다.

-      하지만 토큰을 가진 노드가 죽으면 망한다. (single point of failure)

-      또한 한 노드가 data를 계속 보내면 다른 노드들은 latency를 갖게 된다.

-      이를 개선하기 위해, 시계방향, 반시계방향의 두 토큰을 쓰기도 하지만 여전히 문제는 있다.