[Networks] Delay in Packet-Switched Networks

 패킷들은 하나의 호스트(Source) 로부터 출발하여 여러 개의 라우터를 거치며, 마지막에는 또다른 호스트(Destination) 에서 멈춥니다. 이런 과정에서, 패킷은 이동하며 거치는 노드들에서 여러 종류의 지연을 경험할 것입니다. 발생하는 지연들 중 대표적인 것은 아래와 같습니다.

• Nodal processing delay
• Queuing delay
• Transmission delay
• Propagation delay

이러한 지연들이 누적되어 Total Nodal Delay가 발생합니다. 검색, 웹 브라우징, 이메일, 지도, 네트워크를 이용하는 메시지, VOIP 등과 같은 많은 인터넷 애플리케이션들의 성능은 이런 네트워크 지연에 굉장히 많은 영향을 받습니다. 

 

Types of Delay

  위 그림에서, 패킷은 업스트림 노드에서 라우터 A를 통해 라우터 B로 이동합니다. 라우터 A는 라우터 B로 가는 Outbound link가 존재하며, 이 링크의 앞에는 큐(또는 버퍼)가 위치하게 됩니다. 패킷이 업스트림 노드로부터 라우터 A에 도착했을 때, 라우터 A는 패킷의 헤더를 읽어 가장 적합한 Outbound link를 결정하고, 그 링크로 패킷을 전송하게 됩니다. 이 예에서, 이 패킷이 가야할 Outbound Link 는 라우터 B로 향하는 링크 하나 뿐입니다. 현재 해당 링크에 전송되고 있는 다른 패킷이 없고, 큐에도 전송을 기다리는 패킷이 없는 경우에만 패킷은 해당 링크를 타고 이동할 수 있습니다. 만약, 해당 링크가 이미 다른 패킷을 전송하고 있거나, 다른 패킷들이 큐에서 기다리고 있다면, 새로 도착한 패킷은 큐에서 자기 순서를 기다려야만 합니다.

 

Processing Delay

 라우터에서, 패킷의 헤더를 읽고 어느 Outbound Link로 내보낼지 결정하는 과정에 소요되는 시간이 바로 Processing Delay의 일부분입니다. 또한 Processing Delay 는 업스트림 노드로부터 라우터 A 까지 전송되는 과정에서 발생하는 Bit-level 에러가 발생했는지에 대한 여부를 확인하는 데에 드는 시간도 포함하고 있습니다. 
 빠른 속도를 가진 라우터의 Processing Delay 는 1 마이크로 초 이하로 발생합니다. 이런 노드 처리 후에, 라우터는 해당 패킷을 라우터 B와 이어진 링크로 전송합니다.

Queuing Delay

 패킷이 큐에 위치할 때, 패킷은 Queuing Delay를 겪게 됩니다. Queuing Delay 시간은 큐 앞에 위치하고 있는 먼저 온 패킷들의 수에 비례하게 됩니다. 큐에 기다리고 있는 패킷이 없고, 현재 링크에 전송되고 있는 패킷이 없다면 Queuing Delay는 0이 됩니다. 반면에 트래픽이 굉장히 많고 큐에 기다리고 있는 패킷의 수가 많다면, Queuing Delay는 굉장히 늘어날 것입니다.  Queuing Delay는 실제로 마이크로초~밀리초 정도로 발생합니다.

Transmission Delay

 패킷 스위칭 라우터처럼 라우터에 먼저 들어온 패킷이 먼저 나갈 때(first-come-first-served manner), 앞에 먼저 도착한 패킷들이 모두 전송되고 난 후에야 해당 패킷을 보낼 수 있습니다. 패킷의 길이를 L bits, 라우터 A 로부터 라우터 B로 가는 링크의 전송 속도(transmission rate)가 R bits/sec 라고 가정해보겠습니다. 이때 Transmission Delay 는 L/R 입니다.  이 지연 시간은 패킷의 모든 비트를 링크로 Push(Transmit) 하는 데에 필요한 시간입니다. 실제로 Transmission Delay는 보통 마이크로초~밀리초 정도로 발생합니다.

Propagation Delay

 패킷이 링크에 들어갔을 때, 패킷은 라우터 B로 이동합니다. 라우터 A와 라우터 B 사이에 이어진 링크에 딱 들어왔을 때부터 라우터 B에 도착할 때까지 걸리는 시간을 Propagation Delay 라고 합니다. 패킷의 비트들은 Propagation Speed 의 속도로 링크를 이동합니다. Propagation Speed 는 링크의 물리적인 수단에 의해서 결정됩니다. 이 수단에는 Fiber Optics, Twisted-pair Copper Wire 등이 있습니다. 이 속도는 아래의 범위 안에 포함됩니다.

$$ 2*10^8\, meters/sec\, \sim \,3* 10^8\,meters/sec $$

이 속도는 광속과 같거나 조금 느린 수준입니다. Propagation Delay는 두 라우터 사이 거리 나누기 Propagation Delay로 정의됩니다. 즉 두 라우터 사이의 거리를 d, 링크의 Propagation Speed를 s 라고 하였을 때, Propagation Delay는 d/s 입니다. 패킷의 마지막 비트가 라우터 B에 도착하면, 그 앞의 비트들은 이미 라우터 B에 도착하여 저장되어있습니다. 그리고 라우터 B는 다시 포워딩을 시작합니다. Wide-area Networks 에서는, Propagation Delay가 수 밀리세컨드 정도입니다.

Transmission Delay 와 Propagation Delay 비교

 Transmission Delay 와 Propagation Delay 의 차이가 무엇인지 쉽게 깨닫지 못할 수 있습니다. 이 둘의 차이는 눈에 확 보이지는 않지만 아주 중요한 부분입니다. Transmission Delay는 라우터가 패킷을 링크로 보내기까지에 걸리는 시간입니다. 이 시간은 패킷의 길이와 링크의 전송 속도에 영향을 받지만, 두 라우터 간의 거리에는 영향을 받지 않습니다. 이와 다르게 Propagation Delay는 하나의 라우터로부터 다음 라우터까지 이동하는 데에 걸리는 시간을 의미합니다. 이 시간은 두 라우터 사이의 거리에 영향을 받지만, 패킷의 길이나 링크의 전송 속도에는 영향을 받지 않습니다.

 고속도로에 100 Km 마다 톨게이트가 있다고 가정해보겠습니다. 톨게이트와 톨게이트 사이의 고속도로를 링크, 톨게이트를 라우터라고 생각할 수 있습니다. 쭉 100 Km/hour 로 주행(Propagation)하는 차량이 있다고 할 때, 이 차량은 한 톨게이트로부터 다음 톨게이트까지 1시간이 걸리게 됩니다. 고속도로에 이런 차량 10대만 있으며 이 차량들은 서로 추월하거나 하지 않고 순서를 지키며 주행합니다. 이 차량을 Bit, 이 10대의 차량을 묶어 Packet 으로 생각할 수 있습니다. 톨게이트에서는 한 차량의 비용 처리에 12초가 소요됩니다(1분에 5대 처리). 마지막으로, 10번째 차량까지 톨게이트에서 비용처리를 완료할 때까지 앞 차량들은 모두 톨게이트에서 대기합니다. 그리고 마지막 차량이 비용 처리를 완료하면 다시 차량들은 그들의 순서를 지키며 출발합니다. 

 톨게이트가 차량들을 다시 고속도로 위로 보내는데에 소요되는 시간은 2분({10대의 차량 / 차마다 12초})입니다. 이 시간은 네트워크 상에서 Transmission Delay에 해당합니다. 한 톨게이트로부터 다음 톨게이트까지 차량이 이동하는데에 드는 시간은 앞서 서술했듯 1시간입니다. 이 시간은 네트워크 상에서 Propagation Delay에 해당합니다. 그러므로, 톨게이트 앞에서 대기하던 10대의 차량들이 다음 톨게이트의 앞에 대기할 때까지 소요되는 시간은 Transmission Delay + Propagation Delay 가 됩니다. 이 예시에서는 62분입니다.

 만약 톨게이트에서 차량 10대의 비용을 처리하는 데에 소요되는 시간이 차량 1대가 톨게이트로부터 다음 톨게이트까지 이동하는 시간보다 길게 걸리게 된다면 어떤 일이 일어날까요?  예를 들어, 차량이 이동하는 속도가 기존 100km/h 에서 1,000km/h 로 빨라졌다고 해보겠습니다. 그럼 톨게이트로부터 다음 톨게이트까지 6분이 소요됩니다. 이러한 상황은 Packet-Switched Networks 에서도 발생합니다. 앞서 위치한 라우터에서 패킷의 모든 비트를 전송 처리하기 전에, 패킷의 첫번째 비트가 다음 라우터에 도착해버리는 상황입니다. 

 

$$ d_{nodal}\,=\,d_{processing}\,+\,d_{queuing}\,+\,d_{transmission}\,+\,d_{propagation} $$

 지연시간 총합은 위 식과 같이 정의됩니다. 이러한 지연시간에 대한 지연시간 구성요소들의 기여도는 크게 달라질 수 있습니다. 예를 들어, 같은 대학 캠퍼스 내에 위치한 두 라우터 사이의 링크의 경우 Propagation Delay는 몇 마이크로초 정도로 무시할 수 있을 정도입니다. 그러나, 정지 궤도 위성 링크에 의해 연결된 두 라우터의 경우 Propagation Delay는 수백 밀리초이며, 이때는 지연시간의 총합에 엄청난 영향을 끼치게 됩니다. 이와 비슷하게 Transmission Delay는 LAN 과 같이 빠른 속도를 가진 링크의 경우(10Mbps 이상)에 무시할 수 있을 정도로 작아집니다. 그러나 낮은 속도를 가진 Dial-up 모뎀 링크의 경우에는 수백 밀리초로 늘어나게 되며, 이는 지연시간의 총합에 큰 영향을 끼칩니다. Processing Delay의 경우에는, 라우터의 Maximum Throughput 에 영향을 끼치며, 이는 무시할 만큼 작지 않습니다.

 

Queuing Delay

 지연시간의 구성요소 중에 가장 복잡하고 흥미로운 요소는 Queuing Delay 입니다. 다른 딜레이들과 다르게, Queuing Delay 는 패킷마다 다를 수 있습니다. 예를 들어, 10개의 패킷이 동시에 빈 큐에 도착했다고 하면, 첫번째 패킷은 Queuing Delay 를 겪지 않고 바로 전송될 것입니다. 이에 반해, 가장 마지막 패킷은 앞 패킷들이 전송되는 동안에 비교적 긴 Queuing Delay 를 경험해야 하죠. 그러므로 Queuing Delay 를 설명할 때, 대부분 Queuing Delay 들의 평균이나 분산과 같이 통계적으로 접근합니다. 

 Queuing Delay가 클 때와 작을 때는 언제일까요? 트래픽이 대기열에 도착하는 속도, 링크의 전송 속도, 그리고 트래픽이 정기적으로 도착하는지 아니면 갑자기 한 번에 몰리는지와 같은 도착하는 트래픽들의 특성에 따라 달라집니다. 패킷이 큐에 도착하는 평균 속도를 a, Transmission Rate 를 R, 모든 패킷은 L bits, Queue는 용량 제한이 없다라고 가정하겠습니다. 그러면 큐에 도착하는 비트들의 평균 속도는 La bits/sec 로 계산할 수 있습니다. La/R 로 계산되는 Traffic Intensity 는 Queuing Delay 의 범위를 측정하는데 중요한 역할을 합니다. 먼역 이 Traffic Intensity가 1보다 크다면, 큐에 도착하는 비트의 평균 속도는 큐에서 비트를 처리할 수 있는 속도를 뛰어넘게 됩니다. 이런 상황에서, Queue에서 기다리는 비트들은 가파르게 증가할 것이고, Queuing Delay 또한 끝도 없이 증가하게 됩니다. 즉! Traffic Engineering 에서 가장 중요한 점 하나는, Traffic Intensity 가 1이 넘지 않도록 설계하는 것입니다.

이번에는 Traffic Intensity(La/R) 가 1 이하일 때를 알아보겠습니다. 도착하는 트래픽들의 특성이 Queuing Delay 에 영향을 끼치게 되는데, 예를 들어 패킷들이 L/R 초마다 도착하는 것과 같이 주기적으로 도착한다면 모든 패킷은 Queue 에 도착했을 때 Empty Queue 상태일 것이고, 그에 따라 Queuing Delay 또한 없습니다. 반면, 만약 패킷이 한 번에 여러개 몰리면서 주기적으로 도착하는 경우, 평균 Queuing Delay 는 상당할 수 있습니다. 예를 들어, (L/R)N 초마다 N 개의 패킷이 동시에 도착한다고 가정해보겠습니다. 첫번째 패킷은 Queuing Delay 없이 바로 전송이 진행됩니다. 두번째 패킷은 N/R 초의 Queuing Delay 를 겪고 전송됩니다. 이를 일반식으로 표현해보면 아래와 같습니다.

$$ nth\,packet's\,queuing_delay\,=\,(n\,-\,1)L/R\,seconds $$

위 예시는 가정한 상황이고, 일반적으로 Queue 에 패킷이 도착하는 과정은 모두 랜덤입니다. 즉, 도착은 어떤 규칙도 따르지 않고, 패킷들끼리는 불규칙한 텀을 가집니다. 실제 네트워크 환경에서는, La/R 은 Queuing Delay 를 표현하기에는 부족한 식입니다. 하지만, 직관적으로 Queuing Delay를 이해하는 데에는 충분합니다. 특히 Traffic Intensity 가 0에 가까울 때면, 도착하는 패킷의 수는 적고 서로 멀리 떨어져있으며, 도착한 패킷이 Queue 에서 앞서 도착한 패킷을 발견할 가능성 또한 낮습니다. 따라서 이때 평균 Queuing Delay 는 0에 가깝습니다.  반면 Traffic Intensity 가 1에 가까울 때에는, 패킷이 도착하는 속도가 전송 용량(Transmission Capacity)을 초과하는 시간 간격이 있을 것이고, 이때에는 Queue 가 형성됩니다. 

 위 그래프는 Traffic Intensity 가 증가함에 따라 바뀌는 평균 Queuing Delay 를 표현하고 있습니다. 그래프와 같이 Intensity 의 작은 상승에 평균 Queuing Delay 는 급격하게 상승합니다.  

 

 Packet Loss

  Packet Loss 란 패킷이 이미 앞서 도착한 패킷들로 꽉 찬 Queue에 도착했을 때, 해당 패킷은 저장될 공간이 없어 라우터가 해당 패킷을 Drop 하는 것을 의미합니다. 그렇게 Drop 된 패킷은 사라지게 됩니다. 종단 시스템의 관점에서 보았을 때, Packet Loss 는 "패킷이 네트워크로 전송되기는 했는데,, 도착지에 도착하지는 않았네..?" 와 같이 느껴질 수 있습니다. 트래픽 혼잡도가 증가할수록, 이런 사라지는 패킷의 비율도 증가하게 됩니다. 그러므로, 이러한 Packet Loss의 발생률 또한 지연 시간과 함께 노드의 성능 평가의 기준이 됩니다. 

 

End-to-End Delay

 지금까지는 하나의 라우터에서 발생하는 지연, 즉 Nodal Delay 에 대해서만 알아보았습니다. 이번에는 Source 로부터 Destination 까지의 Total Delay 에 대하여 알아보겠습니다. Source 와 Destination 사이에 N-1 개의 라우터가 있습니다. 네트워크의 혼잡도는 낮아서 Queuing Delay 를 무시할 수 있습니다. 마지막으로 Transmission Rate 는 R bits/sec 입니다. 이때 End-to-End Delay 는 아래의 식과 같이 표현할 수 있습니다.

$$ d_{end-end}\,=\,N(d_{processing\,delay}\,+\,d_{transmission\,delay}\,+\,d_{propagation\,delay} $$ 

Traceroute 을 사용하면, End-to-End Delay 를 직접 확인해볼 수 있습니다. 사용자가 Destination 의 호스트 네임만 입력하면, Source Host 에서 작동되고 있는 Traceroute 는 여러개의 특수 패킷을 Destination 에게 전송합니다. 이 과정에서 해당 패킷들은 여러 라우터를 거치면서 여러 지연시간을 겪게 됩니다. 이동하는 과정에서 만나는 라우터들은, 해당 패킷이 라우터에 도착하면 Source(우리들의 컴퓨터)에게 라우터의 이름과 주소가 담긴 짧은 메시지를 전송합니다. 윈도우 환경에서는 명령어가 tracert 입니다.

 연구실 컴퓨터 환경에서 진행했습니다. 랜선으로 직접 이어져있는, 즉 Source 와 Destination 사이에 라우터가 없는 연구실 서버 IP 를 입력했을 때, 중간에 라우터가 없기에 곧바로 도착했음을 알 수 있습니다. 

Github 로 실행해본 결과입니다. 여러개의 라우터를 거쳐가는 것과 그에 따른 지연시간을 알 수 있습니다.