Jamming transitions in traffic flow on complex queueing networks

Abstract

네트워크는 노드와 링크로 구성된 가상적인 대상이다. 일반적인 정의 덕분에, 네트워크는 자연과 사회에 존재하는, 구성요소와 상호작용 모두 다양한, 복잡계를 표현하는데 적합하다. 그러나 최근까지도 많은 네트워크들이, 소위 척도 없는 네트워크라고 불려지는 불균일한 구조를 가지고 있다는 것이 알려지지 않았다. 기반 네트워크의 이러한 불균일한 구조는 그 위에서 일어나는 다양한 동역학들, 확산, 아이징 동역학, 전염병학, 동기화, 그리고 교통 흐름 등등에 큰 영향을 미친다.

다양한 현상들 중에서도, 복잡계 네트워크 위에서의 수송 현상은 매우 중요한데, 그것은 많은 네트워크들이 상품이나 에너지, 정보 또는 사람 등의 물리적인 대상을 전송하는데 사용되는 기반 구조로써 기능하기 때문이다. 따라서 효율적인 수송을 위해서는 복잡계 네트워크 위에서의 수송 현상을 이해하는 것이 필요하다. 또한, 복잡계 네트워크 위에서의 수송 현상에서 가장 흥미로운 특징 중 하나가 전송 물질의 수가 어떤 임계값을 넘었을 때 정체 상전이가 발생한다는 것이다. 이는 창발하는 집단 현상의 좋은 예이고, 따라서 네트워크 위에서의 수송 현상을 연구하는 것은 이론적인 관점에서도 의미 있는 일이라고 할 수 있다.

본 논문에서, 우리는 인터넷과 같은 복잡한 대기열 네트워크 위의 교통 흐름에서 발생하는 정체 상전이에 대해서 연구 하였다. 인터넷에서 데이터는 패킷이라고 불리는 여러 개의 기본적인 정보 단위로 쪼개져서, 라우터와 케이블을 통해 전송된다. 패킷은 일종의 가상적인 입자라고 생각할 수 있다. 계에 유입되는 입자의 수가 계에서 나가는 입자의 수보다 많아지면, 교통 흐름에서 정체 상전이가 일어난다. 대기열 네트워크 위에서 교통 흐름의 정체 상전이에 영향을 주는 다양한 요소들이 존재한다. 네트워크의 위상 구조, 입자의 생성 과정, 길 안내 규약, 대기열 제어 규약, 라우터와 케이블의 대역폭, 유한한 버퍼 크기 효과 등등이 있다. 우리는 세포 자동자 모형을 이용하여 이런 요소들이 정체 상전이에 미치는 효과를 연구하였다.

첫 번째로, 우리는 대기열 제어 규약이 대기열 네트워크 위의 교통 흐름에서 일어나는 정체 상전이에 미치는 영향을 연구하였다. 우리는 우선순위 대기열 규약과 적응적 길 안내 규약이 동시에 사용되었을 때 정체 상전이의 특징과 교통의 상그림의 구조가 크게 바뀌는 것을 발견하였다. 우리는 우선순위 대기열 규약이 사용된 가장 단순한 교통 모형을 제안하였다. 이 모형에는 우선권이 있고 없고의 두 단계의 우선권만이 존재한다. 우선순위 대기열 규약은 다른 종류의 입자 사이에 비대칭적인 상호작용을 유발한다. 적응적 길 안내 규약과 결합되어서, 이런 비대칭적인 상호작용이 다른 대기열 규약들에 비해 풍부한 상그림 구조를 만든다. 게다가, 우선순위 대기열 규약과 적응적 길 안내 규약이 동시에 사용될 때, 전체적인 교통 정체는 입자의 밀도가 낮을 때에 더 악화되고, 반면에 입자의 밀도가 높을 때는 개선되었다.

다음으로, 우리는 대기열 네트워크 위의 교통 흐름에서 불연속적인 정체 상전이에 대해서 연구하였다. 불연속적인 정체 상전이가 일어나는 대부분의 경우에서, 어떤 노드로의 입자 전송 비율이 그 노드의 대기열 길이가 일정한 값을 넘어서 있으면 급격하게 감소하는 공통적인 현상을 보인다. 이것은 저장 버퍼의 크기가 유한한 것을 반영하기 위한 것이다. 이런 유한한 버퍼 효과를 가지는 계에서만 불연속적인 정체 상전이가 일어나는 것처럼 보이지만, 예외적인 경우가 있다.

우리는 유한한 버퍼 효과가 없는 대기열 네트워크 위의 교통 흐름에서, 불연속적인 정체 상전이가, 유한한 버퍼 대기열 네트워크의 경우와는 다르게, 대규모의 정체와 일치하는 것은 아님을 발견하였다. 또한 우리는 광역 질서 변수와 정체 노드의 비율에서 발생하는 불연속적인 도약이 시스템의 크기가 증가함에도 각각 증가하고 일정하게 유지됨을 발견 하 였다. 이것은 관찰된 급격한 정체 상전이가 정말로 불연속일 수 있음을 강력하게 시사한다. 부분적인 적응적 길 안내 규약 하에 정체 상전이가 일어나는 지점에서, 위상 정보는 무시되고 입자들은 가장 정체가 덜한 노드로만 움직인다. 이런 부분적인 적응적 길 안내 규약의 행동은 전체 네트워크를 상호 도달이 불가능한 여러 개의 부분 네트워크들로 쪼개 버린다.

우리는 정보 지평선을 가지는 일반화된 부분적인 적응적 길 안내 규약의 영향을 조사하였다. 이 길 안내 규약에서는, 정보 지평선 안에 있는 모든 노드들의 교통 정체 정도와 구조적인 정보를 얻어올 수 있다. 우리는 정체 상전이 지점에서 질서 변수의 불연속적인 도약의 높이가 정보 지평선이 확대 될수록 줄어들고 최종적으론, 정보 지평선의 크기가 네트워크의 지름과 같아졌을 때, 불연속적 도약이 완전히 사라짐을 발견 하였다. 또한 우리는 조절 변수를 가지는 일반적인 확률적인 동적 길 안내 규약에 대해서 살펴보았다. 우리는 조절 변수 값이 증가함에 따라서, 교통 흐름에 발생하는 정체 상전이가 연속 정체 상전이에서 불연속적인 정체 상전이로 바뀌는 것을 발견하였다. 이들로부터, 우리는 유한한 버퍼 효과가 없는 대기열 네트워크의 교통 흐름에서 일어나는 불연속적인 정체 상전이는, 길 안내 규약의 과도한 정체 회피 행동이 계의 분절화를 야기함으로써 발생함을 발견했다.

마지막으로, 우리는 무한한 버퍼를 가지는 대기열 네트워크 위의 교통 흐름에서 기본 그림을 연구하였다. 우리는 최대 전송 효율이, 자동차 교통이나 유한한 버퍼 대기열 네트워크에서의 경우와는 다르게, 정체 상전이가 일어나는 때와 일치하지 않음을 발견하였다. 우리는 최대 전송 효율이 대규모 정체가 발생하는 지점에서 얻어짐을 발견하였다. 이 결과는 광역 질서 변수만으론 무한한 버퍼 대기열 네트워크 위에서의 교통 흐름의 성질을 올바르게 알 수 없음을 말해준다

A network is an abstract object composing of nodes and links. Due to its generality, it is appropriate to represent the complex systems in nature and society, of which both elements and interactions are diverse. But until recently, it was not known that many networks have a very heterogeneous structure, called the scale-free network. This heterogeneous topology of underlying networks affects significantly various dynamic processes on them such as diffusion, Ising dynamics, epidemics, synchronization, and traffic flow and so on.

Among them, transportation on complex networks is important since many networks function as the substrate of transferring physical entities such as merchandise, energy, information and even people themselves. Thus, it is necessary to understand transportation on complex networks to improve the transport efficiency of the system. Also one of the most interesting fea- tures observed in transportation on networks is an emergence of the jamming transition when the number of entities exceeds a certain critical value. It is a good example of collective phenomena, hence studying transport process on networks is meaningful in theoretical point of view.

In this dissertation, we studied jamming transitions in traffic flow on complex queueing networks such as Internet. In the Internet, data are split into several number of basic information units called packet, which may be regarded as a sort of particle, and transmitted through routers and cables. When the number of incoming packets exceeds the number of removed packets, the traffic undergoes a jamming transition. There are various ingredients affecting the properties of jamming transition: network topology, packet creation process, routing policy, queueing discipline, bandwidth of routers and cables, finite buffer size, and so on. We studied effects of these ingredients on the jamming transition with cellular automaton models.

First, we investigated the effects of queueing disciplines on jamming transitions in traffic on queueing networks. We found when both the prior- ity queueing discipline and an adaptive routing strategy are used simultaneously, the properties of jamming transitions and structure of phase diagram of traffic are drastically changed. We introduced a minimal traffic model with priority queueing discipline in which there are only two types of particles, one is assigned priority and the other is not. Priority queueing discipline induces an asymmetric interaction between different species of particles. Combined with adaptive routing policy, this asymmetric interaction gives rich structure in phase diagram compared to those for other queueing disciplines. Moreover, with priority queueing discipline and an adaptive routing strategy, the overall congestion is worsened in the low particle density region, while is improved in high density region, compared to those for other queueing disciplines.

Next, we studied discontinuous jamming transitions in traffic on queueing networks. In most cases of occurring a discontinuous jamming transition, there is a common mechanism that the particle transmission rate to a certain node decreases significantly when the length of queue of that node exceeds a certain threshold, which mimics a limited size of buffer. It seems that discontinuous jamming transition occurs only in the system involving such finite buffer effect

however, there is an exception of this statement.

We found that in traffic on queueing networks of lacking finite buffer effect, discontinuous jamming transition does not coincide with large scale congestions, which is different from systems with finite buffer. We also found that discontinuous jumps in the global order parameter and the ratio of congested nodes increase and remain unchanged with increase of system size N, respectively. This indicates the abrupt jamming transition is probably discontinuous. At the jamming transition point under local adaptive routing policies, topological information is ignored and thus a particle moves strictly to the least congested node. Such behavior of a local adaptive routing policy at the critical point disintegrates the network into several mutually unreachable components.

We examined a generalized local adaptive routing policy with extended information horizon, i.e., a node can access information of congestion level of nodes and topological shortest path within the range of information horizon. We found that discontinuity in the order parameter at the jamming transition point decreases as the information horizon extends and finally disappears when the information horizon reaches the diameter of an underlying network. We also checked a generalized stochastic adaptive routing policy with control parameter β

a particle hops to a node i with probability proportional to (ni + 1)−β where ni is the length of queue of node i. We found that there is a crossover from continuous to discontinuous jamming transitions with increasing β . From these, we concluded that discontinuous jamming transition in traffic on queueing networks of lacking the finite buffer effect occurs generally due to excessive congestion-avoiding behavior of routing policies, which leads to fragmentation of the systems.

Finally, we studied the fundamental diagram of traffic flow on queueing networks with unlimited buffer. We found that maximum transport efficiency does not coincide generally with the jamming transition point, in contrast to usual cases such as vehicle traffic and traffic on queueing networks with finite buffer. We found that maximum transport efficiency is achieved at the onset of large scale congestions. It indicates the global order parameter is insufficient to correctly describe the properties of traffic flow on queueing networks with unlimited buffer.