Recently, a wide range of multimedia services including peer-to-peer services are becoming increasingly popular in the Internet. It explosively increases the volume of traffic on the Internet, making it difficult to measure or predict the characteristics of traffic. Moreover, the traffic may severely change as a result of special events including failures internal or external to the networks. Together with the dynamic nature of traffic, current heterogeneous networks will be integrated into a general unified network (i.e., Next Generation Networks). In this network, unexpected network events such as the network failures may frequently occur.
These phenomenons enforce the researches to develop new traffic management schemes to be capable of handling the dynamic nature of traffic and the unexpected network failures. That is, the traffic management scheme can promptly adapt to the changing network environment and re-configure itself to be best-fitted for the adapting environments, named as self-organizing traffic management schemes. For the purpose, this dissertation proposes a novel bio-inspired self-organizing traffic management schemes by making use of the swarm intelligence of artificial individual ants.
This dissertation firstly builds the basic framework called the swarm intelligence based self-organizing network (S2ON). The main objective of the S2ON framework is to develop a network in which a number of artificial ants measure the status of the network in real-time, deposit the pheromone trails on the basis of the measured status, and re-configure the management scheme according to the deposited pheromone trails, without the intervention of network operators. In the S2ON framework, a virtual colony named as sub-colony is newly introduced. The sub-colony is composed of the information statistic
and the pheromone table, and efficiently manages or controls the network. For the management of sub-colonies, we mathematically design the following methods: how to 1) choose the sub colony to be managed, 2) update the information statistic and the pheromone table in the chosen colony, 3) make a new sub colony, and 4) delete the unused sub colonies. Additionally, for usages of organized sub colonies, we mathematically design the following methods: how to 1) conduct the admission control of
incoming flows, 2) choose the sub colony best-fitted for the accepted flows, and 3) forward the flows. The S2ON framework exhibits a higher self-organized capabilities in terms of networking capabilities: it 1) autonomously re-distributes the congested traffic on all links, 2) promptly adapts to the changing network environments, 3) resists the unexpected network failures, and 4) extends for large-scale networks. The numerical comparisons with representative routing protocols such as the link state and distance vector algorithms indicate that the S2ON framework has its competitiveness in terms of the space complexity, protocol overhead, computational complexity, and path convergence time. The S2ON framework bases on the basic framework for the self-organizing traffic management schemes and can be applied to various traffic management areas. In this dissertation, we apply the developed S2ON framework to quality of services (QoS) framework, delay constrained least cost (DCLC) routing, energy saving routing and load
balancing routing.
First, this dissertation proposes ant-based self-organizing QoS framework named as AntQoS. In general, the network QoS provided by the previous QoS-enabled framework is explicitly controlled by network operators. On the other hand, the network QoS in the AntQoS framework autonomously reconfigures itself by promptly adapting to the changing network environments (such as sudden arrivals of highly bursty traffic and unexpected network failures). For the purpose, AntQoS organizes and maintains a small number of sub colonies named QoS colonies which can search sub-optimal paths for given quality demands; they enable the AntQoS framework to efficiently and reliably support a wide range of multimedia services, without any supervised control. Simulation results demonstrate that AntQoS successfully guarantees diverse delay requirements of multimedia services while increasing the network throughput compared with other frameworks. Simulation results also show that AntQoS redistributes the congested traffic and resists the unexpected network failures.
Second, this dissertation proposes ant colony optimization (ACO)-based DCLC routing called ADCLC. Current existing DCLC algorithms find the DCLC paths for incoming flows under the assumptions that the network states were temporarily static and the information about the states was accurately maintained at each node. However, these assumptions are seriously tackled by the dynamic nature of traffic and the frequent occurs of network failures. In addition, existing DCLC algorithms require considerable amount of time to compute the DCLC paths, making impractical to future high speed Internet. Compared with them, the A-DCLC algorithm finds the DCLC paths in a negligible time under the highly dynamic network environments. The operation principle is very simple: when an incoming
flow arrives, a node chooses the proper QoS colony and then transmits the flow to the neighbor referred to by the highest pheromone trail. Then the taken path by the flow is close to the DCLC path for the flow. Simulation results show that the performance of the A-DCLC algorithm is comparable to the one of the optimal constrained bellman-ford (CBF) algorithm.
Third, this dissertation proposes ACO-based energy saving routing called A-ESR. The A-ESR algorithm newly defines the traffic centrality which is a boundary to describes how incoming traffic is densely aggregated on specific links. Then the A-ESR algorithm re-formulate the original energy minimized network problem by making use of the defined traffic centrality. A-ESR can solve the re-formulated problem by transmitting incoming flows to the neighbor link which has the largest traffic centrality. The promising capability is that because A-ESR considers both the traffic centrality and the accumulated pheromone trails, it efficiently reduces the energy consumption while considering the delay performance in a degree. Simulation results show that the A-ESR algorithm greatly reduces the amount of energy consumption while sustains the network delay performance.
Fourth, this dissertation proposes ant-based load balancing routing called AntLBR. The AntLBR algorithm provides following promising capabilities: it can 1) guarantee the delay requirements of incoming flows, 2) evenly distribute the congested traffic on networks, and 3) increases the network utilization. Simulation results show that the AntLBR algorithm not only increase the network utilization but also efficiently resolves the congested traffic.
Consequently, this dissertation firstly designs the S2ON framework to be capable of efficiently handling the dynamic pattern of traffic and the unexpected network failures. The S2ON framework is the basic architecture to not only provide autonomous controls but also exhibit a higher self-organizing networking capabilities by using the swarm intelligence of artificial ant colony. On the basis of the S2ON framework, this dissertation proposes four specific algorithms in the QoS framework, DCLC routing, energy saving routing, and load balancing routing fields and shows their superiority compared than related works through simulations.
최근 P2P 서비스 및 다양한 멀티미디어 서비스가 폭발적으로 증가함에 따라, 인터넷 망에 부가
되는 트래픽의 량이 급격하게 증가되고 있다. 이러한 트래픽의 급증은 트래픽의 동적인 특징을 더욱 더 가속화 시켜, 서비스의 품질 보장을 어렵게 만들 뿐만 아니라 망의 전체 사용 효율 또한 급격히 떨어뜨리게 한다는 특징이 있다. 이와 더불어 다양한 망이 공존하는 현재의 망 구조를 탈피하고 하나의 단일 망으로 통합 운영하고자 하는 NGN망으로의 진화를 꾀하는 움직임이 전세계적으로 활발히 보이고 있다. 이러한 NGN 망 환경하에서는, 현재 망 환경에서는 빈번하게 발생되지 않는 망의 끊김이나 오작동 문제 등이 큰 이슈로 자리잡게 될 것이다.
트래픽의 급증과 NGN망으로의 진화는 미래 인터넷 망 환경에서의 트래픽 관리 기술의 근본적인
변화를 요구하고 있다. 즉, 현존하는 망 운영자 중심의 제어가 아닌, 망 스스로 상태 변화를 인지하고 그에 맞게 망을 다시 재구성할 수 있는 자율 구성형 기반의 트래픽 관리 기술을 절실히 필요로 하고 있다. 이를 위해, 본 논문은 개미들의 집단 지성을 활용하여 망 전체를 자율적으로 관리할 수 있는 획기적인 방법을 제안한다.
본 논문은 먼저 자율 구성형 트래픽 관리 기술의 가장 기반이 되는 S2ON 프레임워크를 개발하였다. 이 프레임워크의 기본적인 목적은 망 운영자의 개입 없이, 인공 개미를 사용하여 실시간으로 망 상태를 측정하고 그에 맞게 망 스스로 자율적으로 제어되는 망을 개발하는데 있다. S2ON 프레임워크는 ”subcolony”라는 가상의 colony 개념을 정의, 이를 활용하여 효과적으로 망을 제어하게 된다. Sub-colony는 정보 통계 모델과 페로몬 테이블을 갖는 구조로 구성되며, 인공 개미가 들어올 때마다 업데이트 되는 방식으로 운영된다. 이러한 sub-colony를 효율적으로 관리하기 위해 1)sub colony를 어떻게 선택하고, 2) 선택된 sub colony를 어떻게 업데이트하며, 3) 새로운 sub colony의 생성 및 4) 사용되지 않는 sub colony를 삭제하는 방법들을 수학적으로 분석하였다. 또한, 관리되어진 sub-colony를 사용하여 1) 인입된 호의 수락 제어 방법, 2) 호의 요구사항에 맞는 sub-colony 선택 방법 등을 수학적으로 분석하였다. 이러한 sub-colony 구조는 자율 적응형이며, 자율 학습형의 특성을 가짐으로써 로드 발랜싱 효과가 있으며, 망 유연성, 망 견고성, 망 확장성에서 탁월한 성능을 보인다. 이렇게 제안된 S2ON의 우수성을 검증하기 위해 공간 복잡성, 프로토콜 오버헤드, 계산의 복잡성, 경로 수렴 시간에 대해 기존의 대표적인 라우팅 기술인 Link state 알고리즘과 Distance vector 알고리즘과 성능 비교를 하였다. 이를 통해 공간 복잡성은 다른 알고리즘에 비해 조금 높지만 프로토콜 오버헤드, 계산의 복잡성에서는 뛰어난 성능을 보임을 수학적으로 입증하였다. S2ON 프레임워크는 자율 구성형 트래픽 관리 기술의 가장 기반이 되는 구조로, 여러가지 라우팅 방법에 사용될 수 있다. 본 논문에서는 개발된 S2ON 프레임워크를 QoS 프레임워크, DCLC 라우팅, 에너지 절감 라우팅, 로드 밸런싱 라우팅 각각에 적용하여 새로운 알고리즘을 개발하였으며, 성능 분석을 통해 제안된 알고리즘들의 우월성을 입증하였다.
첫번째로, S2ON 프레임워크의 응용 알고리즘으로 지연과 대역폭을 보장할 수 있는 AntQoS라는
프레임워크를 제안하였다. 일반적으로, 망에 의해 제공되는 QoS는 망 운영자에 의해 수동적으로 제어된다는 특징이 있다. 이와 달리, AntQoS에서의 QoS는 급변하는 망 상황에 맞게 동적으로 스스로 변형되어 플로우를 서비스한다는 특징이 있다. AntQoS에서는 S2ON 프레임워크는 sub-colony 개념이 QoS colony 개념으로 바뀌게 된다. 그 구조 또한 지연 통계 모델, 대역폭 통계 모델, 페로몬 데이블을 갖는 구조로 확장된다. AntQoS는 QoS colony를 활용하여 인입된 플로우의 지연 및 대역폭을 보장할 수 있음은 물론 변화하는 망 상태에 따라 QoS colony 수를 조절함으로써 더욱 효율적으로 QoS를 제공해 줄 수 있게 된다. 시뮬레이션을 통한 성능 측정 결과, AntQoS는 서비스가 요구하는 지연을 효과적으로 만족시킬 수 있을 뿐만 아니라, 망의 사용 효율 또한 기존의 QoS 프레임워크보다 월등히 뛰어남을 보임을 확인할 수 있다.
두번째로, 짧은 시간안에 Delay Constrained Least Cost (DCLC) 패스를 찾는 A-DCLC 알고리즘을 제안하였다. 현존하는 DCLC 알고리즘들은 변화가 없는 망 환경 하에서 망 상태의 모든 정보를 모든 라우터가 정확히 알고 있다는 가정하에 동작하는 알고리즘으로 미래 망의 다양한 변화와 트래픽의 동적인 특성을 수용함에 있어서 큰 한계점을 가진다. 이와 달리, 제안된 A-DCLC는 인공 개미를 통해 망의 변화를 실시간으로 획득하며, 획득된 정보에 망이 스스로 적응해간다는 특징이 있다. 또한 상당히 긴 계산 시간을 소모하여 DCLC 패스를 찾는 기존의 알고리즘과는 달리, A-DCLC는 단순히 QoS colony를 찾고, 그 colony안의 가장 높은 페로몬이 할당된 이웃노드로 플로우를 전송하는 방식으로 DCLC 패스를 찾는 알고리즘으로 계산 시간이 거의 없다는 장점이 있다. 성능 측정 결과, A-DCLC는 최적으로 DCLC 패스를 찾는 CBF 알고리즘에 비해서 DCLC 패스를 찾을 확률은 다소 떨어지지만, 평균 비용이나 지연 등에서 최적값과 유사한 값을 가짐을 보인다.
세번째로, 지연을어느정도유지하면서망에서소모되는에너지를줄일수있는A-ESR알고리즘을
제안하였다. A-ESR 알고리즘 제안에 앞서, 트래픽 집중도란 개념을 새롭게 정의한 후, 트래픽 집중도를 이용하여 망의 에너지 소모 문제를 정의하였다. 트래픽 집중도는 한 라우터에 인입된 트래픽이 특정 이웃 링크에 얼마나 몰려 있냐는 정도를 측정하기 위한 척도로, A-ESR 알고리즘은 트래픽 집중도가 큰 이웃 링크로 인입된 트래픽을 전송하되, 망에서 겪는 지연을 어느 정도 유지하기 위해 인공 개미에 의해 할당된 페로몬 값을 참조하여 트래픽을 전송하게 된다. 재정의된 에너지 소모 문제는 제안된 A-ESR의 트래픽 전송 방법에 의해서 경험적으로 해결되어 질 수 있음을 보인 후, 기존의 에너지 절감 라우팅 기법들과의 계산 복잡도를 분석하였다. 성능 측정 결과, A-ESR은 타 에너지 절감 라우팅 기법에 비해 계산 복잡도를 현저히 낮춤은 물론, 망의 지연을 어느 정도 유지하면서 더욱 더 많은 에너지를 절감할 수 있음을 보였다.
네번째로, 지연을 보장하면서 망에 인가된 트래픽 로드를 균등하게 분할하는 AntLBR 알고리즘을 제안하였다. AntLBR 알고리즘은 플로우가 요구하는 서비스 품질을 보장한다는 점에서, 인가된 트래픽을 망 전체의 링크에 어느 정도 균등하게 분배한다는 점에서, 그리고 망의 사용 효율을 타 로드 밸런싱 라우팅 보다 높게 한다는 점에서 큰 장점을 갖는다. AntLBR은 먼저, 트래픽 분산도란 개념을 정의한 후, 트래픽 분산도를 이용하여 망에 인가된 트래픽 로드를 균등하게 분할하게 된다. 성능 측정 결과, 타 알고리즘에 비해 인가된 트래픽 로드를 균등하게 분할할 수 있음을 보였다.
본 논문에 의해 개발된 S2ON 프레임워크 기반의 알고리즘들은 인공 개미들의 집단 지성을 활용
한 방법으로, 기본적으로 트래픽의 동적인 특성 및 망의 다양한 변화에 효과적으로 적응할 수 있다는 장점이 있다. 즉, 망의 특정 링크에 많은 부하가 걸려 congestion이 발생했을 때 망 스스로 트래픽을 분산하여 congestion을 해결하게 되며, 링크나 라우터의 오동작 환경 하에서도 자율적으로 문제를 판별해내고 해결해 낼 수 있다는 특징이 있다. 이러한 특징은 미래 인터넷 망의 트래픽 관리 기술에 가장 핵심이 되는 기술 요소로, 향후 미래 인터넷 망 등장시 큰 기여를 할 수 있을 것으로 사료된다.
