CSMA와 이더넷 스위치

CSMA(carrier sense multiple access)

앞서 aloha 모델에 대해 공부해보았는데 전송 효율을 극대화하기 위해 요즘은 CSMA/CD 방식을 주로 사용한다.

CSMA 방식은 그냥 노드들이 현재 전송중인지에 대한 여부를 채널을 통해 주고받는거다. 만약 채널이 비어있다면 전송을 시도할 것이고 채널을 사용중이라면 전송을 미룰 것이다. 뒤에 붙어 있는 CD는 collision detection의 약자인데 짧은 시간동안 충돌을 감지하여 감지 즉시 전송을 중단하여 시간을 보존하는 것이다. 이 CD는 유선은 쉽지만 무선은 어렵다.

CSMA 방식에는 총 세 가지가 있다.

Nonpersistent CSMA

채널이 비어있으면 즉시 전송을 시도한다.

채널이 사용중이라면 random-backoff 방식으로 기다린다. 이 대기시간이 길면 효율이 줄어든다.

1-persistent CSMA

채널이 비어있으면 마찬가지로 즉시 전송을 시도한다.

채널이 사용중이라면 채널이 idle 상태가 될 때까지 기다리다가 idle 상태가 되면 즉시 전송한다.

만약 두개 이상의 노드가 전송을 시도한다면 항상 충돌이 일어날 것이다.

p-persistant CSMA

채널이 비어있으면 p의 확률로 전송을 시도하고 (1-p)의 확률로 한 타임 슬롯만큼 전송을 지연시킨다. 

채널이 사용중이면 idle 상태가 될 때까지 기다리다가 step 1으로 돌아간다.

전송이 지연되었다면 다시 p의 확률로 전송을 시도하고 (1-p)의 확률로 한 타임 슬롯만큼 전송을 지연시킨다.(step 1)

-Non과 1의 짬뽕 느낌이다.

-N개의 노드가 있을 때 Np<1이 되도록 p 값을 정해야만 충돌을 피할 수 있다. 타임 슬롯이 매우 짧으므로 p값을 줄일수록 충돌을 피하기에 유리하다.

CSMA:collisions

하지만 실제 전송 상에서는 propagation delay가 존재하기 때문에 CS를 하더라도 충돌을 완벽히 피할 수는 없다. 이 전파 지연 때문에 각 노드는 서로가 전송을 시작했는지의 여부를 주고받지 못할 수도 있기 때문이다. 따라서 충돌 발생을 감지하면 그 즉시 전송을 중단하는 것이 시간 낭비를 줄일 수 있다.

전송을 즉시 중단하여 가능한 한 시간 낭비를 줄인다.

Ethernet CSMA/CD algorithm

앞서 ethernet에서 통신을 하게 해주는 NIC(network internet chip)을 배웠다. 이 NIC가 채널의 idle 상태를 감지하여 프레임의 전송 여부를 결정한다. 만약 충돌이 발생하면 마찬가지로 전송을 즉시 중단하고 jam 신호를 보낸다. 이후 NIC는 binary backoff를 한다. binary backoff란 충돌이 있을 때마다 전송확률 p의 값을 0.5씩 줄인다. 정확히는 random slot의 범위를 두 배씩 늘려 전송확률 p를 선택한다. 한계에 도달하면 전송 실패로 간주하고 전송을 포기한다.

taking turns

MAC 프로토콜의 마지막, taking turns이다. 노드들끼리 돌아가면서 turn을 확보하는 방법인데 전송을 더 많이 해야 하는 노드에게는 총 전송시간이 너무 길어질 수 있다. 채널 분할 프로토콜은 많은 노드들이 동시에 전송할 때에는 효율이 높지만 적은 노드, 심지어 단 한 노드만 전송하더라도 1/N bps로 전송해야한다는 단점이 있고, 랜덤 access 방식은 반대로 많은 노드들이 동시에 전송할 때에 효율이 낮아진다. 이래서 등장한 것이 taking turns 프로토콜이다.

polling

한 master 노드가 다른 노드들을 초대하여 돌아가면서 각 노드에게 데이터를 보낼 의사가 있는지 물어보는 것이다.

이 master 노드가 다운되면 전체 네트워크에 문제가 생기는 치명적인 단점이 있다.

polling

token passing

토큰을 서로 돌리면서 토큰을 갖고 있는 노드가 전송할 수 있는 방식이다. 토큰이 오버헤드가 날 수도 있고 특정 노드가 오래동안 토큰을 소지하면 다른 노드들의 전송 시간이 오래 지연될 수 있는 문제가 있다.

token passing

Cable access network

multiple downstream: ISP > 사용자로 갈 때에는 상시 공평히 많은 load로 분배하므로 FDM channel을 이용한다.

multiple upstream: 사용자 > ISP로 갈 때에는 일부 슬롯은 일부 정해진 사용자들에게 할당되고 나머지 슬롯은 나머지 사용자들이 서로 경쟁하여 얻는다. (FDM과 TDM을 같이 사용한다.)

DOCSIS

인터넷 제공 표준 규격이다. FDM에서 업스트림과 다운스트림의 채널들을 관리하고 TDM에서는 사용자에게 슬롯을 할당을 관리한다. 업스트림 슬롯을 얻기 위해 요청하면 binary backoff 방식으로 슬롯을 선택하여 할당해준다.

MAC address

앞서 잠깐 얘기했지만 MAC 주소는 ip 주소와 달리 실제 물리적인 주소이다. 물리적으로 연결된 interface끼리 통신할 때 사용하는 것으로 동일 서브넷 내에서 사용된다. MAC 주소는 48비트로 구성되어 있으며 2자리 * 6의 총 12 자리의 16진수로 주로 표현한다.

ip는 가변적이지만 MAC 주소는 IEEE로부터 할당받은 물리적 식별을 위해 사용되는 주소로 불변한다. 비유하자면 MAC 주소는 주민번호, ip 주소는 집주소가 적절하겠다. 또한 ip 주소는 계층적인 구조이지만 MAC는 계층적이지 않다.

ARP(address resolution protocol)

LAN 상에서 호스트 A가 호스트 B에게 데이타그램을 어떻게 전송할까? LAN 상에 각 노드들은 arp table을 갖고 있다.

arp table에는 ip주소와 mac 주소 그리고 ttl이 적혀 있다. A가 B의 MAC 주소를 찾기 위해 A는 broadcast 방식으로 B의 ip 주소를 보낸다. (B의 ip주소는 미리 알고 있다.) 이 때 도착지의 MAC 주소는 FF-FF-FF-FF-FF-FF로 보낸다.

B는 A에게 MAC 주소를 포함한 ARP 응답을 보낸다.

A는 응답을 받아 local ARP table에 기록한다.

만약 LAN이 아닌 다른 서브넷으로 첫번째 홉 R을 거쳐 데이터그램을 보낸다면 어떨까?

A는 출발지 A 도착지 B인 ip 데이터그램을 만들고 첫번째 홉 라우터(R)의 MAC 주소를 도착지로 한 프레임으로 캡슐화하여 보낸다. 이 때 소스의 MAC과 ip주소는 A의, 도착지의 MAC 주소는 R, ip 주소는 B이다.

A to R

다음으로 R에서 데이터그램으로 추출하여 나갈 인터페이스를 찾은 뒤 소스의 MAC addr에는 자기의 주소를, source ip addr에는 A의 ip 주소를 넣고 도착지의 MAC와 ip 주소는 B에 대한 정보를 넣어 다시 프레임으로 캡슐화한다.

이후 B에게 도착하여 전송이 완료된다.

R to B

Ethernet

이더넷은 많이들 익숙할거다. 전부 이더넷을 사용하기 때문이다. topology(모양)는 크게 두 가지가 있는데 switched 형태와 bus 형태가 있다. bus는 옛날 형태이고 오늘날엔 거의 switched 형태로 되어있다.

Ethernet frame structure

이더넷 프레임으로 캡슐화하며 데이터그램을 전송하면 다음과 같은 형태로 된다.

preamle: 송수신자의 동기화를 맞추는데 7바이트가 사용된다. 프레임의 본격적인 시작을 알리는 1바이트를 추가하여 7+1로 8바이트의 크기를 갖는다.

address: 데이터의 송수신 장치의 MAC 주소가 들어가는 곳으로 6바이트 씩 총 12바이트가 들어간다. (48비트씩 두개)

type: 2바이트가 할당된다.

data + CRC부분은 생략한다. 보통 data 46~1500 바이트 CRC 4바이트가 할당된다고 한다.

 

이더넷에는 다음과 같은 속성이 있다.

connectionless: 송수신자 사이에 핸드쉐이킹 과정이 필요없다.

unreliable: NIC는 ACK이나 NAK을 보내지 않으므로 신뢰를 보장하지 않는다. (TCP 등의 방식으로만 신뢰성 보장이 가능하다)

unslotted CSMA/CD 방식으로 전송이 가능한 시간에는 언제든지 데이터를 전송하여 충돌 시 binary backoff로 확률을 줄인다.

Ethernet switch

스위치는 능동적인 역할을 수행하는 링크 계층 디바이스이다. store forward 방식이 저렴하여 이 방식을 사용하고 선택적으로 프레임을 포워딩한다. 또한 self-learning으로 관리자 조작이 불필요하다는 특징이 있다.

호스트 입장에서 보았을 때 스위치는 여러 호스트들이 동시에 서로 충돌이 일어나지 않고 통신할 수 있게 해주지만 한 호스트가 동시에 두 호스트와 연결하는 것은 불가능하다.

switch forwarding table

스위치는 어떻게 포워딩 테이블을 만들까? 아래와 같은 알고리즘을 통해 작동한다.

switch forwarding 알고리즘

1. 들어오는 링크와 MAC 주소를 기록한다.

2. 도착지 MAC 주소를 테이블에서 조회한다.

3. 만약 찾는다면, 포트가 같다면 프레임을 보내고 / 포트가 다르다면 해당하는 포트로 포워딩한다.

4. 찾지 못한다면 flood 한다. (broadcast 방식으로 프레임이 온 포트를 제외한 모든 포트로 MAC 주소를 찾는다.)

스위치는 스위치들 끼리도 interconnect가 가능하다. 이 때도 self learning을 통해 forwarding table을 형성한다.

Switch vs Router

스위치와 라우터는 얼핏 보면 비슷한 점이 많다. 그렇다면 뭐가 같고 뭐가 다를까?

둘 모두 store-forward 방식을 사용한다. 하지만 스위치는 링크 계층 디바이스로 링크 계층의 header를 갖고 있고 라우터는 네트워크 계층의 디바이스로 네트워크 계층의 header를 갖고 있다.

또한 둘 다 포워딩 테이블을 갖고 있다. 하지만 스위치는 self learning을 통해 flood하고 MAC 주소를 알아내고 라우터는 라우팅 알고리즘을 통해 ip 주소 테이블을 만든다.

스위치는 프레임을, 라우터는 데이터그램을 다룬다는 것 또한 차이라고 할 수 있다.

Virtual LAN(VLAN)

LAN이란 local area network의 약자로 서로 직접 연결이 가능한 컴퓨터 집합을 뜻한다. VLAN이란 반대로 이를 다시 세분화해 분리하는 것이다. 이는 스위치를 라우터처럼 보이게 하는 효과가 있다. 동일 LAN이지만 마치 다른 LAN인것처럼 보이게 할 수 있다.

Datacenter networks

우리가 아는 데이터센터이다. 매우 큰데, 맨 위에 보더 라우터부터 아래 블레이드 서버라고 불리우는 부분까지 있다.

Datacenter

이 데이터센터로부터 우리의 일상생활에서 인터넷에 접속할 때를 상상해보면 다음과 같은 순서일 것이다.

먼저 노트북에서 DHCP를 통해 사용할 ip주소와 첫 홉의 주소, DNS 서버의 주소를 받아온다.

DHCP는 UDP로 세그먼트 캡슐화되고, ip로 데이터그램 캡슐화되며 802.3 이더넷의 프레임으로 캡슐화될 것이다.

다음으로 이더넷 프레임을 LAN 상에서 브로드캐스트하여 DHCP 서버에서 받으면 세 차례의 demux로 DHCP에게 도착할 것이다.

DHCP는 같은 과정으로 요청자의 ip주소와 첫 홉의 ip 주소, 그리고 DNS 서버의 이름과 ip 주소를 ACK과 함께 응답할 것이다.

이렇게 인터넷에 연결이 완료되면 HTTP 요청을 하기 전에 구글의 주소가 필요하니 DNS가 필요할 것이고 DNS 요청 전에 라우터의 MAC 주소가 필요하여 ARP가 필요할 것이고 이 ARP 응답을 통해 MAC 주소를 알아 구글의 주소를 DNS에 요청하게 된다. 

이 DNS 요청을 첫 홉 라우터에게 포워딩하면 DNS 서버까지 encapsulate/demux 과정을 통해 전송되면 응답을 받으면서 최종적으로 구글닷컴에 접속하게 된다.