네트워크 코어와 지연 — 패킷 교환, 인터넷 구조, 네 가지 지연

1. 코어는 라우터의 그물이고, 라우터는 패킷을 다 받은 뒤 보냅니다

앞 글에서 호스트가 접속망을 거쳐 엣지 라우터에 닿는 데까지 보았습니다. 그 안쪽이 네트워크 코어(network core)입니다. 코어는 서로 연결된 라우터들의 그물(mesh)입니다. 호스트가 메시지를 패킷으로 자르면, 라우터들이 패킷을 출발지에서 목적지까지 한 라우터에서 다음 라우터로 넘깁니다. 이렇게 넘기는 일을 전달(forward)이라고 합니다.

라우터를 한 줄로 이으면 선이 덜 듭니다. 그래도 그물로 짜는 이유는 둘입니다. 한 줄 구조에서는 라우터 하나가 고장 나면 그 뒤가 모두 끊기지만, 그물에서는 다른 경로로 돌아갈 수 있습니다. 또 목적지가 다른 트래픽이 서로 다른 경로를 타므로 부하가 여러 링크로 흩어집니다. 라우터가 갈 방향을 알 수 있는 이유는 패킷마다 목적지 주소가 들어 있기 때문입니다.

저장 후 전달

라우터는 패킷의 첫 비트가 도착했다고 바로 다음 링크로 내보내지 않습니다. 패킷 전체가 도착할 때까지 기다렸다가 내보냅니다. 이 방식을 저장 후 전달(store-and-forward)이라고 합니다. 목적지 주소 같은 정보는 패킷 앞쪽의 헤더에 한 번만 들어 있고, 오류가 없는지도 패킷을 다 받아야 확인할 수 있습니다. 앞부분만 먼저 보내면 뒷부분은 갈 곳을 모르는 조각이 됩니다.

그래서 전송 지연이 링크마다 더해집니다. 출발지와 목적지 사이에 링크가 N개 있고, 신호가 선을 따라 이동하는 시간을 0으로 두면 패킷 하나가 도착하는 데 이만큼 걸립니다.

d_end-end = N × L / R

예를 들어 8,000비트 패킷을 40 Mbps 링크로 보내면 한 링크에서 8,000 / (40 × 10⁶) = 0.2 ms가 걸립니다. 출발지에서 라우터 둘을 거쳐 목적지까지 가면 링크가 3개이므로 0.6 ms입니다.

문제 1

위와 같은 조건(L = 8,000비트, R = 40 Mbps, 링크 3개)에서 출발지가 패킷 3개를 연달아 보냅니다. 마지막 패킷이 목적지에 다 도착하는 시각은 언제입니까. 전파 지연과 큐잉 지연은 0으로 둡니다.

L / R = 0.2 ms를 한 칸으로 셉니다. 1번 패킷은 1칸째에 첫 링크를 마치고, 2칸째에 둘째 링크, 3칸째에 셋째 링크를 마칩니다. 출발지는 1번을 다 내보낸 직후 2번을 내보내기 시작하므로, 2번은 2칸째에 첫 링크를 마치고 한 칸씩 뒤따라 4칸째에 도착합니다. 3번은 5칸째에 도착합니다. 답은 5 × 0.2 = 1.0 ms입니다. 패킷들이 서로 다른 링크를 동시에 쓰기 때문에 3 × 0.6 = 1.8 ms까지 걸리지 않습니다. 일반적으로 링크 N개에 패킷 P개를 보내면 (N + P − 1) × L / R입니다. 여기서는 (3 + 3 − 1) × 0.2 = 1.0 ms로 같습니다.

2. 큐잉과 패킷 손실

라우터 하나에 여러 링크로 패킷이 들어와서 같은 출력 링크로 나가야 하는 상황을 생각합니다. 들어오는 쪽 링크가 각각 100 Mbps이고 나가는 링크가 10 Mbps라면, 들어오는 속도가 나가는 속도를 쉽게 넘습니다.

링크로 도착하는 비트의 속도가 한동안 링크의 전송률을 넘으면 두 가지 일이 일어납니다.

• 패킷이 출력 링크 앞에서 줄을 서서 차례를 기다립니다. 줄을 큐(queue)라고 하고, 기다리는 시간을 큐잉 지연(queueing delay)이라고 합니다.
• 라우터가 패킷을 쌓아 두는 메모리인 버퍼(buffer)는 크기가 정해져 있습니다. 버퍼가 가득 찬 뒤에 도착한 패킷은 버려집니다(dropped). 이것이 패킷 손실(packet loss)입니다.

전송 지연은 패킷 크기와 링크가 정해지면 정해지는 값입니다. 큐잉 지연과 손실은 그때그때 트래픽에 따라 달라집니다. 버려진 패킷은 바로 앞 라우터나 출발지 호스트가 다시 보낼 수도 있고, 아무도 다시 보내지 않을 수도 있습니다. 파일처럼 빠짐없이 와야 하는 데이터는 다시 보내고, 실시간 통화처럼 늦게 오면 쓸모없는 데이터는 손실을 감수하고 넘어갑니다.

3. 포워딩과 라우팅

라우터가 받은 패킷을 내보낼 출력 링크를 정하는 일은 두 기능으로 나뉩니다.

포워딩은 패킷 헤더에 적힌 목적지 주소 일부를 보고 표를 찾는 일입니다. 어떤 라우터의 포워딩 테이블이 다음과 같다고 합시다.

헤더 값이 1011인 패킷이 들어오면 라우터는 표를 찾아 출력 링크 2로 내보냅니다. 실제 인터넷에서 이 값은 IP 주소입니다.

이 표를 채우는 일이 라우팅입니다. 한 ISP가 자기 라우터들을 모두 관리한다면, 라우터 사이 링크마다 비용을 매기고 그래프의 최단 경로 알고리즘으로 각 목적지까지 가장 좋은 경로를 계산할 수 있습니다. 그 결과로 라우터마다 "이 목적지는 이 링크로"라는 표가 만들어집니다. 서로 다른 회사의 망을 건널 때는 비용 말고도 회사 사이의 계약과 정책이 경로를 정하는 데 끼어들어 훨씬 복잡해집니다. 자세한 알고리즘은 네트워크 계층에서 다룹니다.

자동차 여행에 빗대면, 출발 전에 지도를 펴고 전체 경로를 짜는 일이 라우팅이고, 가는 길에 갈림길을 만날 때마다 표지판을 보고 나갈 길을 고르는 일이 포워딩입니다.

4. 다른 방식 — 회선 교환

패킷 교환의 반대편에 회선 교환(circuit switching)이 있습니다. 데이터를 보내기 전에 출발지에서 목적지까지 경로 위의 자원을 그 통화 전용으로 예약하는 방식입니다. 전통적인 전화망이 이렇게 동작합니다. 전화가 연결되면 그 통화를 위한 몫이 링크마다 잡히고, 통화가 끝날 때까지 다른 사람은 그 몫을 쓰지 못합니다.

• 자원을 나눠 쓰지 않으므로 큐잉이 없고 성능이 보장됩니다.
• 통화 중에 아무 말도 하지 않아도 예약된 몫은 비어 있는 채로 남습니다(idle). 다른 사용자가 그 몫을 쓸 수 없으니 낭비입니다.

한 링크를 여러 통화에 나눠 주는 방법은 두 가지입니다.

5. 두 방식을 숫자로 비교하기

60 Mbps 링크 하나를 여러 사용자가 씁니다. 사용자는 활동할 때 10 Mbps를 쓰고, 전체 시간의 10%만 활동합니다. 나머지 90%는 아무것도 보내지 않습니다.

회선 교환이라면 사용자마다 10 Mbps를 예약해야 하므로 60 / 10 = 6명까지만 받을 수 있습니다. 그 6명은 시간의 90% 동안 예약한 몫을 쓰지 않습니다.

패킷 교환에는 예약이 없으니 정해진 한도가 없습니다. 20명을 받았다고 합시다. 링크가 모자라는 때는 동시에 활동하는 사람이 6명을 넘을 때뿐입니다. 사용자들이 서로 독립적으로 각자 확률 0.1로 활동한다면, 동시 활동자 수 X는 이항분포(binomial distribution)를 따릅니다.

P(X = k) = C(20, k) × 0.1^k × 0.9^20−k

P(X > 6) = ∑_k=7²⁰ C(20, k) × 0.1^k × 0.9^20−k ≈ 0.0024

링크가 모자라는 시간은 약 0.24%입니다. 나머지 99.76%의 시간에는 20명이 아무 문제 없이 씁니다. 같은 링크로 회선 교환보다 3배 넘게 많은 사람을 받습니다.

사용자 수나 활동 확률이 커지면 모자랄 확률이 빠르게 커집니다. 활동 확률이 0.2만 되어도 20명 중 7명 이상이 겹치는 시간이 9% 가까이 됩니다. 패킷 교환이 유리한 이유는 사람들이 링크를 늘 쓰지 않고 가끔 몰아서 쓰기 때문입니다. 이런 데이터를 버스티(bursty)하다고 합니다.

패킷 교환에도 대가가 있습니다. 많은 사람이 한꺼번에 보내면 혼잡(congestion)이 생기고, 버퍼가 넘쳐 지연과 손실이 생깁니다. 그래서 잃은 데이터를 다시 보내는 신뢰적 전송과, 망이 붐빌 때 보내는 속도를 줄이는 혼잡 제어가 따로 필요합니다. 영상 통화처럼 일정한 대역폭이 꼭 필요한 응용은 패킷 교환 위에서 대역폭을 보장하는 방법을 따로 찾아야 합니다.

6. 인터넷 구조 — 네트워크들의 네트워크

호스트는 접속 ISP(access ISP)를 통해 인터넷에 붙습니다. 어느 두 호스트든 서로 패킷을 주고받으려면 접속 ISP들끼리도 연결되어야 합니다. 실제 구조는 수십 년 동안 경제 사정과 국가 정책에 따라 자라 왔기 때문에 복잡합니다. 그래서 단계별로 쌓아 가며 이해합니다. 아래 단계는 이해를 돕기 위해 나눈 것이고 실제 역사의 순서와는 다릅니다.

1. 모두 직접 잇기 — 접속 ISP가 N개일 때 모든 쌍을 직접 이으면 연결이 N(N − 1) / 2개 필요합니다. N이 1,000만 되어도 499,500개입니다. 접속 ISP는 수백만 개이므로 불가능합니다.
2. 글로벌 중계 ISP 하나 — 가운데에 세계를 잇는 ISP 하나를 두고 모든 접속 ISP를 거기에 연결합니다. 연결은 N개로 줄어듭니다. 접속 ISP는 고객(customer)으로서 돈을 내고, 글로벌 ISP는 제공자(provider)로서 연결을 팝니다.
3. 경쟁하는 글로벌 ISP 여럿 — 돈이 되는 사업이면 경쟁자가 생깁니다. 이런 최상위 ISP를 티어 1 ISP(tier-1 ISP)라고 합니다. 이제 글로벌 ISP끼리도 이어져야 서로의 고객이 통신할 수 있습니다.
4. IXP와 피어링 — ISP들은 여러 ISP가 선을 끌어와 한곳에서 연결하는 시설인 IXP(Internet Exchange Point)에서 만나거나, 두 회사의 라우터를 직접 잇는 피어링 링크(peering link)로 트래픽을 주고받습니다.
5. 지역 ISP — 티어 1 ISP가 전 세계의 접속 ISP에 일일이 선을 대기는 어렵습니다. 그래서 중간의 지역 ISP(regional ISP)가 한 지역의 접속 ISP들을 모아 위로 잇습니다.
6. 콘텐츠 제공자 네트워크 — 구글, 마이크로소프트 같은 회사는 자기 사설망을 깔고 데이터센터를 지역 ISP나 접속 ISP에 직접 잇습니다. 트래픽이 늘수록 티어 1 ISP에 내는 돈도 늘어나므로, 상위 ISP를 거치지 않는 길을 직접 만드는 쪽이 싸다고 판단한 것입니다.

이렇게 쌓으면 오늘날 인터넷의 모습이 됩니다. 가운데에 소수의 잘 연결된 티어 1 ISP가 있고, 그 아래에 지역 ISP와 접속 ISP가 계층을 이루며, 옆에 콘텐츠 제공자의 사설망이 나란히 붙어 있습니다. 티어를 정하는 중앙 기관은 없습니다. 회사들 사이의 거래 관계에 따라 느슨하게 나눈 분류입니다.

7. 패킷 지연의 네 가지 원인

패킷이 라우터 하나를 지날 때마다 네 가지 지연이 더해집니다.

d_nodal = d_proc + d_queue + d_trans + d_prop

전파 지연의 d는 링크의 물리적 길이이고, s는 매체 안에서 신호가 이동하는 속도로 약 2 × 10⁸ m/s입니다. 전송 지연과 전파 지연은 이름이 비슷해 자주 헷갈립니다. 전송 지연은 패킷 크기와 링크 전송률로 정해지고 거리와 상관없습니다. 전파 지연은 거리와 매체로 정해지고 패킷 크기와 상관없습니다. 전파 속도는 빛의 속도를 넘을 수 없으므로 기술이 발전해도 줄일 수 없습니다.

두 지연의 크기를 비교해 봅니다. 12,000비트 패킷을 10 Mbps 링크로 보내면 전송 지연은 12,000 / 10⁷ = 1.2 ms입니다. 이 링크가 대략 9,600 km 떨어진 서울과 로스앤젤레스를 잇는다면 전파 지연은 9.6 × 10⁶ / (2 × 10⁸) = 48 ms로 전송 지연의 40배입니다. 같은 링크가 건물 안 50 m 구간이라면 전파 지연은 50 / (2 × 10⁸) = 0.25 μs로, 이번에는 전송 지연이 훨씬 큽니다. 어느 쪽이 큰지는 거리와 전송률이 정합니다. 중간에 중계국을 세워 구간을 나눠도 전체 거리는 그대로이므로 전파 지연은 줄지 않습니다. 중계국은 약해진 신호를 되살리려고 세웁니다.

8. 톨게이트 행렬로 두 지연 가르기

자동차 행렬이 톨게이트를 차례로 지나는 상황으로 두 지연을 나눠 볼 수 있습니다. 차 한 대가 비트 하나, 차 여러 대의 행렬이 패킷 하나, 톨게이트가 라우터입니다. 톨게이트가 차 한 대를 내보내는 데 드는 시간이 비트 하나의 전송 시간이고, 톨게이트 사이 도로를 달리는 시간이 전파 지연입니다. 차는 한 대씩 따로 달리지만, 다음 톨게이트는 행렬이 모두 모인 뒤에야 처리를 시작한다고 보면 저장 후 전달과 같습니다.

문제 2

차 6대가 행렬을 이룹니다. 두 톨게이트 사이는 60 km입니다. (가) 톨게이트가 차 한 대를 20초에 내보내고 차는 시속 120 km로 달립니다. 행렬 전체가 둘째 톨게이트 앞에 모이기까지 몇 분이 걸립니까. (나) 톨게이트가 차 한 대를 2분에 내보내고 차는 시속 600 km로 달립니다. 첫 차가 둘째 톨게이트에 닿는 순간, 첫 톨게이트에는 아직 몇 대가 남아 있습니까.

(가) 6대를 모두 내보내는 데 6 × 20초 = 120초, 곧 2분이 걸립니다. 이것이 전송 지연입니다. 마지막 차가 60 km를 시속 120 km로 달리는 데 30분이 걸립니다. 이것이 전파 지연입니다. 합하면 32분입니다.

(나) k번 차는 2k분에 첫 톨게이트를 떠나고, 60 km를 시속 600 km로 달리는 데 6분이 걸리므로 2k + 6분에 둘째 톨게이트에 닿습니다. 1번 차는 8분에 닿습니다. 그 순간 4번 차가 막 첫 톨게이트를 떠나고 있습니다(2 × 4 = 8). 5번은 처리 중이고 6번은 기다리는 중이므로 2대가 남아 있습니다. 첫 비트가 목적지에 닿았는데 마지막 비트는 아직 출발지를 떠나지 못한 상황입니다. 이번에는 전송 지연(12분)이 전파 지연(6분)보다 큽니다. 행렬 전체가 둘째 톨게이트에 모이는 시각은 12 + 6 = 18분입니다.

9. 큐잉 지연과 트래픽 강도, 그리고 traceroute

큐잉 지연은 패킷이 언제 몰려오느냐에 따라 달라지므로 식 하나로 정해지지 않습니다. 대신 평균적인 경향을 세 값으로 가늠합니다. R은 링크 전송률(bps), L은 패킷 길이(bits), a는 평균 패킷 도착률(packets/sec)입니다. La는 초당 들어오는 비트 수이고 R은 초당 내보낼 수 있는 비트 수입니다. 둘의 비를 트래픽 강도(traffic intensity)라고 합니다.

트래픽 강도 = La / R

예를 들어 1 Mbps 링크에 10,000비트 패킷이 들어옵니다. 초당 20개가 오면 10,000 × 20 / 10⁶ = 0.2이고 큐는 거의 비어 있습니다. 초당 95개가 오면 0.95입니다. 평균으로는 아직 처리할 수 있는 양이지만 지연은 크게 늘어납니다. 패킷이 고른 간격으로 오지 않고 몰려서 오기 때문입니다. 몰리는 순간에 쌓인 줄이 한가한 순간에 다 줄어들기 전에 다음 무리가 옵니다. 초당 120개가 오면 1.2가 되어 줄이 계속 늘어납니다. 그래서 시스템은 트래픽 강도가 1을 넘지 않게, 되도록 1에서 멀게 설계합니다. 지연을 줄이려면 R을 키우거나(더 빠른 링크) a를 줄입니다(트래픽을 다른 경로로 나누기). 버퍼를 키우면 손실은 줄지만 줄이 길어져 큐잉 지연은 늘어납니다.

traceroute로 실제 지연 재기

traceroute는 출발지에서 목적지까지 경로 위의 라우터마다 지연을 재는 프로그램입니다. 패킷 헤더에는 라우터를 하나 지날 때마다 1씩 줄고 0이 되면 버려지는 TTL(time to live) 값이 있습니다. traceroute는 이 값을 i로 둔 패킷을 3개 보냅니다. 패킷은 i번째 라우터에서 멈추고, 그 라우터가 출발지로 응답을 돌려줍니다. 보낸 시각과 응답을 받은 시각의 차가 왕복 시간(RTT, round trip time)입니다. i를 1부터 하나씩 늘려 목적지까지 반복하므로, 출력의 한 줄이 라우터 하나입니다.

서울에서 미국 서버로 traceroute를 돌리면 처음 몇 줄은 수 ms이다가, 태평양을 건너는 링크를 지나는 줄에서 갑자기 100 ms 넘게 뜁니다. 해저 케이블이 길어 전파 지연이 크기 때문입니다. 더 먼 라우터의 RTT가 바로 앞 라우터보다 작게 찍히기도 합니다. 두 줄의 측정은 서로 다른 시각에 보낸 패킷으로 하므로, 그사이 망이 한가해져 큐잉 지연이 줄었을 수 있습니다. 별표(*)가 찍힌 줄은 응답이 오지 않은 경우입니다. 패킷이 손실되었거나 라우터가 응답하지 않도록 설정되어 있습니다.

정리

네트워크 코어는 라우터의 그물이고, 라우터는 패킷 전체를 받은 뒤 포워딩 테이블을 보고 다음 링크로 넘깁니다. 표를 채우는 일은 라우팅 알고리즘이 합니다. 회선 교환은 자원을 미리 예약해 성능을 보장하고, 쓰지 않는 동안 그 자원은 놀게 됩니다. 패킷 교환은 링크를 그때그때 나눠 쓰므로 버스티한 사용자를 같은 링크에 훨씬 많이 받을 수 있고, 대신 큐잉과 손실을 감수해야 합니다. 인터넷은 티어 1 ISP, 지역 ISP, 접속 ISP가 계층을 이루고 IXP와 피어링, 콘텐츠 제공자 망이 그 사이를 잇는 구조입니다. 패킷은 라우터마다 처리, 큐잉, 전송(L / R), 전파(d / s) 지연을 겪고, 큐잉 지연은 La / R이 1에 다가갈수록 급격히 커집니다. 다음 글에서는 성능의 마지막 지표인 처리량을 보고, 복잡한 네트워크를 계층으로 나누는 방법과 응용 계층의 원리로 넘어갑니다.