1.4 Delay, Loss and Throughput in Packet-Switched Networks

1.4.1 Overview of Delay in Packet-Switched Network

 패킷 스위치로 된 네트워크에서는 패킷들은 일련의 라우터들을 거쳐서 호스트로 간다는 것을 봤다. 이때 발생할 수 있는 전체적인 딜레이는 

$$(nodal processing delay) + (queueing delay) + (transmission delay) + (propagation delay)$$

가 있다. 이 딜레이를 최소화 한다는 것은 네트워크 내의 전송을 최적화한다는 것과 같다.

 

Types of Delay

 delay 가 어느 부분에서 발생하는지 보자. 위의 그림에서는 A라우터가 B라우터로 가기 위한 outbound link를 지니고 있기 때문에 end system에서의 B로 패킷을 보냈을 때, 패킷이 source → upstream node(source 와 가장 가까운 router) → 라우터 B로 전송된다. 여기서 A 라우터에서는 자기 자신이 다른 라우터들과 연결되어 있기 때문에 이 패킷의 정보를 읽어서 어디로 보낼지를 정하는 table이 있다. 적절한 outbound link를 선택하여 해당 경로로, 즉 downstream node 쪽으로 보내게 된다.

 

Processing Delay

 여기서 A가 들어오는 패킷을 처리하는 과정에서 발생하는 지연시간이 있을 터인데, 해당 지연시간을 processing delay라고 한다. 보통 router의 장비 성능에 따라가고 우리가 어떻게 할 수가 없다(통신사나 자체적인 회사 기획에서 돈을 좀 더 들이면 될 수도?).

 Packet Switching Network에서의 Nodal Processing Delay:

1. 패킷의 헤더를 검사
2. 패킷을 적절한 하웃바운드 링크를 결정(해시테이블 이용)
3. 패킷을 해당 링크로 보냄

 이 링크는 큐(queue) 앞에 위치되어 있고, 이제 B로 이어지는 고속도로 들어가기 전의 톨게이트 바로 전의 국도로 진입하게 된 셈이다(queue를 톨게이트 바로 앞이라고 보면 이해하기 쉽다). 패킷은 링크가 현재 다른 패킷을 전송하고 있지 않으며 큐에 다른 패킷이 없을 ㄸ때만 링크로 전송될 수 있다. 링크가 현재 사용중이거나 큐에 이미 다른 패킷이 있는 경우에 새로 도착한 패킷은 큐(톨게이트 앞)에서 기다리게 된다.

 

Queueing Delay

 Queue로 들어간 패킷들은 출력 링크(고속도로)로 들어가기 위해 queue에서 대기를 해야 한다. 이때 대기하는 시간을 Queueing Delay라고 한다. 이 시간은 보통 라우터의 congestion level에 비례하여 증가하며, 일반적으로 수 밀리초 ~ 수 마이크로 초로 지연되게 된다. 만약에 queue에 어떤 패킷도 없는데 Inbonud로 들어오는 패킷이 있다면 해당 패킷의 queueing delay는 0초가 될 것이다.

 

Transmission Delay

 packet을 전송하는 router가 first-com-first-served 방식을 따른다고 하자(FIFO). 이때 패킷의 길이 L bits을 보내려고 할 때, 한 라우터에서 다른 라우터로의 전송하기 위해 링크로 밀어내는 시간을 transmission delay라고 한다. 계산식은 다음과 같다(거속시 계산과 같음).

$$(transmission delay) =  \frac{L (bits)}{R (bits/sec)(bps, kbps, mbps, ...)}$$

 

Propagation Delay

 드디어 A에서 B로 가는 라우터 사이의 링크(고속도로)를 탔다. 여기서 최대 속도 제한이 있는데, 보통 이는 전송 매체에 따라 다르다(광섬유냐, Twisted Pair 구리선을 쓰냐, ...). 보통 우리가 관여를 할 수 없다. 전파지연은 다음과 같이 계산된다.

$$(Propagation Delay) = \frac{d (km, m, ..)}{s( 2 \times 10^{8} ~ 3 \times 10^{8} m/sec)}

 

Nodal Delay

전체 노드 지연이라고 부르며, 계산식은 다음과 같다.

$$d_{nodal} = d_{proc} + d_{queue} + d_{trans} + d_{prop}$$

보통 거리가 엄청 크면 d_prop이 상대적으로 큰 비중을 차지하게 되어 이를 줄여야 하는게 관건일 것일 것이다. 하지만 그렇지 않다면 d_prop는 무시할 수 있을 정도로 작다(알고리즘에서 상수 시간이 걸린다의 느낌?). d_trans는 network의 traffic intensity에 따라 천차만별이기 때문에 엄청 작을수도 있고, 클 수도 있다. 또 d_proc도 무시할 수 있지만, 라우터가 좋은 장비인지 아닌지 따져봐야함.

 

1.4.2 Queueing Delay and Packet Loss

(queueing 지연에 대해서 high-level에 대해서만 다룬다.) queueing delay는 앞서 봤던 다른 전파 지연, 전송 지연, 처리 지연이랑 다른 양상을 띈다. 10개의 패킷이 동시에 빈 큐에 들어오는 것을 생각해보자. 첫번째 패킷은 queueing delay가 0이지만, 다른 패킷들은 줄을 기다려야 할 것이기 때문에 기다리는 시간을 a라고 두면 a*(a-1)/2 의 시간이 걸리게 될 것이다(첫째항이 0임). 그래서 각 패킷마다 다른 queueing delay가 걸리기 때문에 이를 '특성화'(특정 짓고자) 할때,

$$ E[Queueing Delay], Var[Queueing delay], (the probability that the queuing delay exceeds some specified value) $$

당을 사용한다고 한다(통계 잘하면 됨). 위의 수치들을 보면 queueing delay는 router에서 outbound 로 가는 대기하는 패킷들의 숫자에 따라 다른 것을 알 수 있다. 이 대기하는 패킷(톨게이트에서 많은 차들이 기다리는 교통혼잡, 추석을 생각하자)은 사용자들의 수, 혼잡한 시간대 에 따라 다르기 때문에, 이를 측정하는 척도가 필요하다. 패킷이 큐에 도착하는 평균 속도를 a(packet/sec) 라고 하고, 패킷의 길이를 L(bits), 전송 속도를 R (bit/sec) 라고 할 때, 비트가 큐에 도착하는 평균속도는 traffic intensity 는

$$ (traffic intensity) = \frac{La}{R} $$

라고 한다. 만약 traffic intensity가 1보다 크다면 비트가 큐에 도착하는 평균 속도가 비트가 큐에서 전송되는 속도를 초과하게 되며, 큐에서 기다리는 패킷들이 계속 쌓이게 될 것이다(따라서 네트워크 설계에서는 La/R 이 1을 넘지 않도록 설계해야 함).

 그러면 La/R ≤ 1일 때, E[Queueing Delay]를 계산해보면, N개의 패킷을 전송할 때 걸리는 지연시간은

$$ 1 \times \frac{L}{R} + 2 \times \frac{L}{R} + 3 \times \frac{L}{R} + \dots + (N-1) \times \frac{L}{R} = \frac{(N-1)N}{2} \times \frac{L}{R} $$

이 될 것이다. 만약 1에 근접하지만 1보다 크지는 않은 상황에서는 queueing delay 가 어떻게 될까? 아마 도착 속도가 queueing delay보다 큰 구간이 있을 수 있으며, 이 시간 동안 대기열이 형성될 수 있다.

위의 그림은 traffic intensity와 E[Queueing Delay]간의 관계를 그려놓은 것인데, 1에 가까워 질 때 무한대로 증가함을 볼 수 있다. 그래서 보통 티케팅에서 nodal delay 중 queueing delay 의 비중이 굉장이 커지기 때문에 느려지는 것이다.

 

Packet Loss

 우리의 라우터가 가지는 queue 라는 것은 수용력이 무한대가 아니다. 무한대 일때는 traffic intensity가 1보다 초과하는 경우, queue에 패킷들이 계속 대기할 공간이 있지만, 유한적일 때, router는 들어오는 패킷들을 버리게(drop) 된다. 이 drop 되는 상황을 packet loss라고 말하게 된다. 하지만 이런 packet loss 가 생긴다면 request 에 대한 데이터 신뢰성이 떨어지게 된다. 네트워크에서 이런 데이터 손실은 end system 에게 굉장히 치명적이고 정상적인 서비스를 제공하지 못할 수도 있다.

 

1.4.3 End-to-End Delay

 이제 전체적인 delay를 살펴보자. 위에서는 한 router가 다른 router로 전송될 때 부분만 본 것이다. 패킷은 두 라우터를 거치는게 아니라 다수의 라우터를 거치기 때문에 이를 공식화 해야 한다.

$$dend-end = N(d_{proc} + d_{trans} + d_{prop})$$