6장

6.1 Introduction, services

호스트와 라우터는 노드: 네트워크에 연결된 모든 디바이스

통신 경로를 따라 인접한 노드를 연결하는 통신 채널은 링크(무선 or 유선)

• wired links
• wireless links
• LANs

2-PDU는 프레임

• 데이터그램을 캡슐화

링크 계층은 링크를 통해 한 노드에서 물리적으로 인접한 노드로 프레임을 전송할 책임이 있다.

데이터그램은 다양한 링크 상으로 다양한 링크 프로토콜에 의해 전송됨

• 즉, 첫번째 링크는 Ethernet, 중간 링크는 frame relay, 마지막 링크는 802.11

각 링크 프로토콜은 다른 서비스를 제공

• 즉, 링크에서 rdt를 제공할수도, 하지 않을수도 있음

Link Layer Services: 인접한 두 노드의 통신

Framing, link access

• 데이터그램을 프레임으로 캡슐화, header와 trailer 추가
• 링크 액세스: 단대단 링크, 공유 브로드캐스트 링크, MAC(Media Access Control) 프로토콜
• 소스와 목적지 식별을 위해 프레임에서는 MAC address(또는 physical address)가 사용됨
  • different from IP address

인접 노드 사이의 신뢰성 있는 전달

• 낮은 비트 오류율을 가지는 링크에서는 거의 사용하지 않음
• 무선 링크: 높은 오류율
  • 트랜스포트 계층 프로토콜에서의 재전송 대신 링크에서 오류 정정(속도 느려서 재전송은 효율 낮음)

flow control, error detection, error correction, half-duplex and full-duplex 제공

어디에 링크계층이 내장?

각각의 모든 호스트에게 adaptor(aka network interface card NIC)나 칩으로 내장되어 있음

Adaptors communicating

전송측

• 데이터그램을 프레임으로 캡슐화
• 오류 검사 비트, rdt, 흐름 제어 등 추가

수신측

• 오류, rdt, 흐름 제어 등을 검사
• 데이터그램을 추출하여 수신 노드에게 전달

6.3 multiple access protocols

두가지 종류의 링크

• point-to-point
  • PPP for dial-up access
• broadcast (shared wire or medium)
  • traditional Ethernet
  • upstream HFC
  • 802.11 wireless LAN

Multiple Access protocols

하나의 공유된 브로드캐스트 채널

두개 이상의 노드들에 의한 동시 전송: 충돌, 간섭

• 한번에 하나의 노드만이 성공적으로 전송 가능

다중 액세스 프로토콜(multiple access protocol)

• 노드들이 어떻게 채널을 공유하는지를 결정하는 분산 알고리즘, 즉, 노드가 언제 전송할 수 있는지를 결정
• 채널 공유에 관한 통신 자체도 채널을 사용해야함.

이상적인 multiple access protocol

Broadcast channel of rate R bps

1. 한 노드가 전송하기를 원할 때, rate R로 전송가능
2. M 노드들이 전송하기 원하면, 각 노드는 평균적으로 rate R/M로 전송
3. 완전 분산
   1. 전송을 조정하기 위한 특수한 노드가 없음
   2. 클럭, 슬롯의 동기화가 없음
4. 단순하고 간단

MAC protocols: 분류

3가지

채널분할

• 채널을 더 작은 조각으로 분할(time slots, frequency, code)
• 노드에게 독점적 사용을 위한 조각을 할당

랜덤 액세스

• 채널은 분할되지 않고, 충돌을 허용
• 충돌로부터 복구

순번

• 충돌을 피하기 위해 고유 액세스를 강하게 조정

Mac protocols: TDMA

각 노드는 각 라운드에서 고정된 길이의 슬롯을 획득

사용되지 않는 슬롯은 낭비됨

장단점: 충돌 제거, 공정, 전송 노드가 하나일때에도 노드 전송률은 평균 R/N으로 제한. 전송 노드는 항상 자신의 차례를 기다려야함.

Mac protocols: FDMA

각 노드는 고정된 주파수 밴드 할당

주파수 밴드에서 사용되지 않는 전송 시간은 idle

장단점: 충돌을 피하고, N개의 노드에게 대역폭을 균등하게 할당, 하나의 노드만이 전송할 때에도 R/N 대역폭으로 한정

Random Access Protocols

노드가 전송할 패킷이 있을 때

• full channel data rate R로 전송
• 노드들간에 사전 조정이 없음

두개 이상의 노드가 전송 → 충돌

random access Mac protocol은 다음을 명시

• 충돌을 어떻게 검출하는가
• 충돌로부터 어떻게 복구하는가 (즉, 지연된 재전송을 통해)

CSMA (Carrier Sense Multiple Access)

CSMA: 전송전에 들음

• 채널이 idle이면, 전체 프레임을 전송
• 채널이 busy이면, 전송을 연기

충돌은 여전히 발생 가능

• propagation delay(전파 지연)은 두 노드가 상대방의 전송을 감지할 수 없는 경우가 발생한다는 것을 의미
• collison: 전체 패킷 전송 시간이 낭비됨
• note: 충돌 확률 결정에서 거리와 전파 지연의 역할

CSMA/CD (Collision Detection)

짧은 시간 내에 충돌 감지 → 전송을 취소 시켜서 채널 낭비를 줄임

충돌 감지

• 유선 LAN에서는 쉬움: 신호 세기를 감지하고 전송측과 수신측의 신호를 비교하면 됨
• 무선 LAN에서는 어려움: 전송중에 receiver그냥 닫아버림

Taking Turns MAC protocols

채널 분할 MAC protocls

• 높은 부하에서 채널을 효율적으로 공유
• 낮은 부하에서 비효율적: 1개의 노드를 위해서 대역폭을 1/N로 나누어야하기 떄문

랜덤 액세스 MAC protocls

• 낮은 부하에서 효율적
• 높은 부하: collision overhead

taking turns protocols

• 두개의 장점을 합침

Taking Turns MAC protocols

• 폴링
  • 마스터 노드가 슬래이브 노드를 차례로 전송하도록 invites
  • concerns
    • 폴링 오버헤드와 지연(물어볼 떄 발생)
    • single point of failure (master)
• 토큰 전달
  • 한 노드에서 다음 노드로 순차적으로 토큰을 전달
  • concerns
    • 토큰 오버헤드
    • 토큰 전달지연
    • single point of failure (token)
      • token이 오류 발생하면 문제

6.4 LANs

MAC Addresses and ARP

MAC address

• 프레임을 한 인터페이스에서 다른 물리적으로 연결된 인터페이스로 전달하기 위해 사용됨
• 48 bit MAC address (for most LANs) burned in the adapter ROM

LAN Address

LAN에서 각 어댑터는 유일한 LAN 주소를 가짐

MAC address 할당은 IEEE에 의해 관리됨

제조업자는 MAC address 공간의 일부를 구입

MAC 주소는 계층 구조가 아닌 평면 구조

• LAN 카드는 다른 LAN으로 이동 가능 (portable)

IP 계층적 주소는 portable이 아님

• 노드가 연결된 IP 네트워크에 의존

ARP: Address Resolution Protocol

LAN에서 각 IP 노드는 ARP table을 가짐

ARP Table: LAN 노드에 대한 IP/MAC address 매핑 (TTL 20분)

ARP protocol

MAC 주소가 없으면 해당하는 IP주소를 포함한 ARP query 패킷을 브로드캐스트 (목적지 MAC address = FF-FF-FF-FF-FF-FF(broadcast 주소)) → 모든 노드는 ARP Query를 수신 → 송신측에 MAC address를 응답(프레임이 유니캐스트로 전송)

ARP는 네트워크 관리자의 개입없이 자신의 ARP table을 생성 (plug-and-play)

Ethernet

가장 흔한 LAN: 싸고 단순하고 처음으로 널리 사용됨, 10 Mbps - 400 Gbps

버스형: 90년대 중반에 인기많음

• 모든 노드는 똑같은 충돌 도메인에 있음

스타형: 오늘날 사용

• 중앙에 스위치가 있음
• 분리되어서 충돌 없음

Ethernet Frame Structure

전송 어댑터는 IP datagram (또는 다른 네트워크 계층 프로토콜 패킷)을 Ethernet frame에 캡슐화

preamble

• 7 바이트의 10101010 패턴과 1 바이트의 10101011 패턴
• 수신측과 전송측의 클럭 속도를 동기화시키기 위해 사용됨

Addresses: 6 byte source, destination MAC addresses

• 어댑터가 일치하는 목적지 주소를 가지거나 브로드캐스트 주소를 가진 프레임을 수신하면, 프레임에서 데이터를 네트워크 계층 프로토콜로 전달 아니면 폐기

Type: 상위 계층 프로토콜을 지시. 대부분의 경우 IP

CRC: 오류검사

Unreliable, connectionless service

connectionless: 전송, 수신 어댑터 사이에 handshaking 과정 없음

unreliable: 수신 어댑터는 전송 어댑터에게 acks 또는 nacks을 전송하지 않음

• 네트워크 계층에 전달된 데이터그램 스트림은 손실된 패킷으로 인한 gap을 가질 수 있는데 TCP를 사용하면 재전송을 통해 채워짐

Ethernet uses CSMA/CD

어댑터가 전송 도중에 다른 전송을 감지하면 전송을 취소하고 jam signal을 전송 → 취소 후, 어댑터는 충돌확률을 줄이기 위해 랜덤한 시간동안 대기 ⇒ m번째 충돌 후, 어댑터는 {0,1,2,…,2^m-1}에서 랜덤하게 K를 선택. 어댑터는 K*512bit times을 대기한 후 재전송

Jam Signal: 모든 다른 전송자들이 충돌을 인식하도록 함: 48bits

Bit time: 0.1 microsec for 10 Mbps Ethernet; for K = 1023, wait time is about 50 msec

switches

Hubs (1 계층 디바이스, 신호 증폭시키는 장치)

허브는 본질적으로 물리계층 리피터

• 한 링크에서 수신 비트는 모든 다른 링크로 출력

상호연결된 허브

백본 허브는 LAN segments를 상호 연결

노드 사이의 최대 거리를 확장

그러나 개별 세그먼트 충돌 영역들이 하나의 큰 충돌 영역이 됨

• cs에서 노드와 EE에서 노드가 동시에 전송한다면, 충돌

10BaseT와 100BaseT를 상호연결할 수 없음

Switch

링크 계층 디바이스

• 이더넷 프레임을 저장하고 전달
• 프레임 헤더를 조사하고 MAC 목적지 주소에 기반하여 프레임을 선택적으로 전달
• 프레임이 세그먼트로 전달될 때, 세그먼트 액세스를 위해 CSMA/CD를 사용

transparent

• 호스트는 스위치의 존재를 인식하지 않음

plug-and-play, self-learning

• 스위치는 구성될 필요가 없음

동시전달

• 스위치는 버퍼를 가짐
• 목적지가 다를때는 동시 전달 가능 A to A’ B to B’ 하지만 목적지가 같으면 동시전달 불가능 A to A’ B to A’

스위치가 어느 인터페이스를 통해 목적지에 도달하는지 어떻게 알 수 있을까?

• 각각의 스위치는 switch table을 가지고 있음
• 스위치 테이블에는 호스트의 MAC address, 호스트에 도달하는 인터페이스 쌍으로 구성 ⇒ 라우팅 테이블과 닮음
• 어떻게 테이블을 만들고 유지할까? → self-learning

Switch: self-learning

스위치는 어느 호스트가 어느 인터페이스를 사용하여 도달될 수 있는지를 학습(learn)

• 프레임이 수신되면, 스위치는 전송자의 위치를 알게됨
• 스위치 테이블에 전송자/위치쌍을 기록

스위치에 프레임이 수신되면 수신측의 주소를 알게됨 → 목적지로 보내야하는데 목적지를 모르면 flooding(다 보냄) → 해당하는 목적지가 프레임을 수신하면 주소를 알게됨 → 주소를 알면 그 링크만 이용해서 보냄

상호연결된 스위치

single-switch와 같은 방식으로 self-learning 함

Switch: traffic isolation

스위치는 LAN을 LAN 세그먼트로 분리

스위치는 패킷을 필터

• 같은 LAN 세그먼트 프레임은 다른 세그먼트로 전달되지 않음
• 세그먼트는 충돌 도메인을 분리시킴(↔ 그냥 막 보내는 허브와는 다름)

Switches vs routers

router: 네트워크 계층 디바이스, 포워딩 테이블을 라우팅 알고리즘, IP 주소를 통해 계산

switch: 링크 계층 디바이스, 포워딩 테이블을 flooding, learning, MAC address를 이용하여 학습