대기행렬 이론과 큐잉 지연

네트워크 지연

네트워크에서 한 패킷이 송신자에서 수신자까지 도착하는 데 걸리는 시간은 처리 지연processing delay, 큐잉 지연queueing delay, 전송 지연transmission delay, 전파 지연propagation delay의 네 가지 지연이 합쳐진 값입니다.

처리 지연은 노드가 수신한 패킷의 헤더를 검사하고 어디로 전달(forward)할지 결정하는 데 걸리는 시간입니다. 오늘날의 라우터에서는 마이크로초 단위의 매우 짧은 시간이 소요됩니다.

큐잉 지연은 라우터의 출력 링크로 전달되기 위해 출력 버퍼에 도착한 패킷이 자신의 차례를 기다리는 시간입니다. 동시에 같은 링크로 향하는 패킷이 많을수록 이 시간이 길어집니다.

전송 지연은 패킷의 모든 비트를 출력 링크로 밀어넣는 데 걸리는 시간입니다. 패킷의 크기를 L이라고 하고, 링크의 전송 속도를 R이라고 할 때 L/R의 시간이 소요됩니다.

전파 지연은 링크로 밀려나간 비트가 물리 매체를 통해 다음 노드까지 이동하는 데 걸리는 시간입니다. 링크의 길이와 매체의 전파 속도로 결정되며, 지리적 거리가 길수록 늘어납니다.

이 중 처리 지연, 전송 지연, 전파 지연은 패킷의 크기와 링크의 속성에 의해 거의 고정되어 예측 가능한 값을 갖습니다. 반면 큐잉 지연만은 같은 경로 위의 같은 패킷이라 하더라도 매 순간 다른 값을 갖습니다. 왜 유독 큐잉 지연만 이런 성질을 갖는지, 그리고 그 규모를 어떻게 가늠할 수 있는지를 다루는 것이 대기행렬 이론Queueing Theory입니다.

패킷 스위칭의 수학적 기반

인터넷은 패킷 스위칭packet switching 방식으로 동작합니다. 데이터를 여러 개의 패킷으로 쪼갠 뒤, 각 패킷을 독립적으로 목적지까지 전달하는 방식입니다. 과거의 전화망에서 쓰이던 회선 스위칭circuit switching과는 기본 철학이 다릅니다.

회선 스위칭에서는 통신을 시작하기 전에 두 종단 사이의 경로와 대역폭을 미리 확보해둡니다. 한 번 확보된 자원은 통신이 끝날 때까지 오직 그 두 종단만을 위해 사용되며, 그 덕분에 품질이 안정적으로 유지됩니다. 다만 통신이 없는 구간에서도 대역폭이 묶여있어 낭비가 발생한다는 단점이 있습니다. 사람의 통신은 대체로 짧은 시간 동안 몰아서 주고받다가 한동안 조용해지는, 이른바 버스티bursty한 특성을 띠기 때문에 이 낭비는 결코 무시할 만한 수준이 아닙니다.

패킷 스위칭은 이 문제를 정반대 방향에서 해결합니다. 경로와 대역폭을 미리 예약하지 않고, 여러 통신이 하나의 링크를 그때그때 나누어 쓰도록 합니다. 같은 링크로 패킷이 동시에 몰리면 일부는 버퍼에서 순서를 기다려야 하지만, 평균적인 관점에서 보면 훨씬 적은 자원으로 훨씬 많은 통신을 수용할 수 있습니다.

이 방식이 실제로 회선 스위칭보다 효율적인지에 대한 수학적인 근거는 1960년대 초 레너드 클라인록Leonard Kleinrock의 연구에서 제시되었습니다. 그는 대기행렬 이론을 도구로 삼아 버스티 트래픽 소스에 대해 패킷 스위칭이 회선 스위칭보다 훨씬 효율적이라는 사실을 증명했고, 이 결과는 이후 데이터 네트워크 설계의 이론적인 뼈대가 되었습니다.

수치로 보는 두 방식의 차이

클라인록의 결과가 어느 정도의 차이를 만드는지는 간단한 시나리오로 살펴볼 수 있습니다. 아래와 같은 링크를 가정해봅시다.

• 링크의 대역폭: 1 Mbps
• 유저 한 명이 활동 중일 때 필요한 대역폭: 100 kbps
• 유저 한 명이 실제로 활동하는 시간의 비율: 10%

회선 스위칭의 경우, 각 유저에게 100 kbps를 통신이 끝날 때까지 예약해두어야 하므로 이 링크가 수용할 수 있는 유저는 최대 10명으로 고정됩니다. 나머지 90%의 시간 동안 해당 유저가 아무것도 전송하지 않더라도, 그 대역폭은 다른 누구도 쓸 수 없습니다.

패킷 스위칭의 경우, 예약이 존재하지 않으므로 10명보다 훨씬 많은 유저를 동시에 수용할 수 있습니다. 대신 동시에 활동 중인 유저의 수가 10명을 초과하는 순간에는 링크의 용량을 넘기게 되어 큐잉 시간이 발생하게 되고, 손실로 이어질 수 있습니다. 따라서 "동시 활동 유저가 10명을 초과할 확률"을 허용 가능한 수준 이하로 유지하는 것이 수용 가능한 유저 수의 상한을 결정합니다.

각 유저가 독립적으로 10%의 확률로 활동한다고 가정하면, 전체 유저 수 N 일 때 동시에 활동 중인 유저의 수는 이항분포를 따르며 해당 확률을 아래와 같이 계산할 수 있습니다.

유저가 35명이 되어도 링크의 용량을 초과할 확률은 약 0.04%에 불과합니다. 즉 회선 스위칭으로는 10명밖에 수용하지 못하는 링크에서, 패킷 스위칭은 사실상 동일한 품질을 유지하면서 세 배 이상인 35명을 수용할 수 있다는 뜻입니다. 각 유저가 활동하는 시간의 비율이 낮을수록, 다시 말해 트래픽이 더 버스티할수록 이 격차는 더욱 크게 벌어집니다.

이것이 통계적 다중화statistical multiplexing라고 불리는 패킷 스위칭의 핵심 이점이며, 오늘날 인터넷이 상대적으로 적은 자원으로도 수많은 통신을 감당할 수 있는 이유이기도 합니다.

큐잉 지연은 왜 가변적인가

앞서 짧게 짚은 것처럼, 큐잉 지연은 같은 출력 링크를 여러 패킷이 동시에 두고 경쟁할 때 발생합니다. 라우터는 여러 입력 링크로부터 패킷을 수신하여 각자의 목적지에 맞는 출력 링크로 전달하는 역할을 수행하는데, 이 때 동시에 여러 패킷이 같은 출력 링크로 향하게 되면 뒤늦게 도착한 패킷들은 전송 순서를 기다리며 출력 버퍼output buffer에 쌓이게 됩니다.

큐잉 지연의 가장 큰 특징은 네트워크의 혼잡도에 따라 패킷마다 값이 달라진다는 점입니다. 처리 지연이나 전송 지연이 패킷의 크기와 링크의 속성에 따라 거의 고정된 값을 갖는 것과는 사뭇 다른 성질입니다. 어떤 패킷은 버퍼가 비어있는 순간에 도착하여 거의 기다리지 않고 바로 전송되지만, 다른 어떤 패킷은 앞에 수백 개의 패킷이 쌓여있는 혼잡한 순간에 도착하여 훨씬 오래 기다려야 할 수도 있습니다.

이러한 변동성 때문에 큐잉 지연을 분석할 때는 하나의 확정된 값을 이야기하는 것이 의미가 없습니다. 대신 아래와 같은 통계적 척도를 사용합니다.

• 평균 큐잉 지연 — 특정 기간 동안 패킷들이 겪는 지연의 평균값
• 큐잉 지연의 분산 — 지연이 얼마나 들쑥날쑥한지를 나타내는 값
• 특정 값을 초과할 확률 — 예를 들어 지연이 100ms를 넘을 확률 같은 꼬리 분포tail의 지표

실제 라우터의 버퍼는 유한합니다. 만약 큐가 가득 찬 상태에서 새로운 패킷이 도착한다면, 라우터는 해당 패킷을 수용할 공간이 없으므로 이를 폐기합니다. 이를 패킷 손실packet loss이라고 부르며, TCP와 같은 상위 계층 프로토콜은 이 손실을 혼잡의 신호로 해석하여 자신의 전송 속도를 조절합니다. 따라서 큐잉 지연을 논할 때 손실률 역시 함께 고려해야 할 품질 지표가 됩니다.

트래픽 강도

큐잉 지연의 규모를 추정할 때 가장 중요한 지표는 트래픽 강도traffic intensity입니다. 이는 링크에 얼마나 많은 트래픽이 몰리고 있는지를 하나의 값으로 요약해줍니다. 평균적으로 초당 a개의 패킷이 도착하고, 각 패킷의 크기가 L 비트이며, 링크의 전송 속도가 R bps라고 할 때, 트래픽 강도는 아래와 같이 정의됩니다.

분자 La는 큐에 쌓이는 비트의 평균 속도를 나타내며, 분모 R은 큐에서 빠져나가는 비트의 속도를 나타냅니다. 즉 이 값은 들어오는 속도와 나가는 속도의 비율로 해석할 수 있습니다.

La / R 이 1 이상인 경우

큐에 쌓이는 비트의 평균 속도가 큐에서 빠져나가는 속도를 따라잡거나 넘어서면, 큐의 길이는 시간이 흐를수록 끝없이 늘어나고 평균 큐잉 지연 역시 무한대로 발산합니다.

La/R > 1 인 경우 이러한 현상은 직관적으로 보여집니다. 단위 시간당 들어오는 비트의 양이 나가는 양보다 많으니, 그 차이만큼이 매 순간 큐에 그대로 쌓일 것입니다.

La/R 가 정확히 1인 경우는 들어오는 비트와 나가는 비트가 정확히 일치하니 문제가 없을 것 같기도 합니다. 하지만 이 경우에도 La/R이 1 이상인 경우와 동일한 현상이 발생합니다. 실제 트래픽은 규칙적으로 도착하지 않고 무작위로 들어오기 때문입니다. 어떤 순간에는 도착이 몰려 큐가 부풀고, 한산한 순간에는 큐가 빕니다. 이 때 La/R = 1 인 시스템은 한 번 부푼 큐를 평균 처리 속도로밖에 밀어낼 수 없기 때문에, 부풀음이 완전히 해소되기 전에 다음 버스트가 들어와 큐를 더 키웁니다. 이런 변동이 반복되면 큐의 평균 길이는 시간이 흐를수록 한없이 커집니다.

유한한 버퍼를 가진 실제 라우터에서는 두 경우 모두 큐가 금방 가득 차 손실률이 급등합니다. 트래픽 엔지니어링의 주요 원칙 중 하나가 바로 트래픽 강도가 1에 닿지 않도록 시스템을 설계하는 것인 이유가 여기에 있습니다.

La / R 이 1 미만인 경우

트래픽 강도가 1 미만이라면 시스템은 안정 상태에 도달할 수 있습니다. 다만 그 안쪽에서도 1에 얼마나 가까운지에 따라 체감되는 지연은 전혀 다른 수준으로 나타납니다.

트래픽 강도가 0에 가까우면 패킷이 도착할 때 이미 버퍼가 비어있을 가능성이 매우 높으므로 평균 큐잉 지연은 거의 0에 수렴합니다. 반면 트래픽 강도가 1에 가까워질수록 평균 큐 길이와 큐잉 지연은 기하급수적으로 치솟습니다. 예를 들어 트래픽 강도 0.5와 0.95는 둘 다 링크 용량 안쪽이라는 점에서는 동일하지만, 체감되는 지연의 규모로 보면 완전히 다른 상황입니다.

평균 트래픽 강도가 같더라도, 트래픽이 주기적인지 무작위적인지에 따라 지연은 크게 달라집니다. 주기적으로 도착하는 트래픽과 한 번에 몰렸다가 잠잠해지는 버스티한 트래픽은 큐잉 지연의 분산과 꼬리 분포의 양상이 완전히 다릅니다. "용량의 절반도 안 쓰는데 왜 이렇게 지연이 튀지?"라는 질문의 답은 대개 평균 부하가 아니라 트래픽의 버스티한 성격에서 찾게 됩니다.

아래 시뮬레이터는 지금까지 이야기한 다섯 가지 구간을 직접 눈으로 비교할 수 있도록 구성한 것입니다. 버튼을 눌러 시나리오를 전환하면, 같은 버퍼에 같은 서비스 속도를 가진 링크가 각 트래픽 강도에서 어떤 식으로 반응하는지 관찰할 수 있습니다. 특히 ρ = 1 인 두 경우를 번갈아 보면, 같은 평균 트래픽 강도에서도 도착 패턴에 따라 큐의 양상이 얼마나 달라지는지가 한눈에 들어옵니다.