Home

네트워크에서 패킷을 목적지까지 전송하기 위해서는 유니캐스트, 멀티캐스트, 브로드캐스트 등의 방법이 존재한다. 유니캐스트 라우팅 기법은 패킷을 전송해야 할 경우 목적지 수만큼 패킷을 출발지에서 생성해서 전송해야 한다. 반면에 멀티캐스트 라우팅 기법은 패킷 전송 시 네트워크의 라우터가 패킷을 복사하여 목적지로 패킷을 보내기 때문에 유니캐스트 라우팅 기법에 비해서 효율적으로 같은 데이터를 여러 목적지로 전달할 수 있다. 그러나 이러한 멀티캐스트 라우팅 기법은 라우팅 시에 멀티캐스트 라우팅 트리를 형성하게 되는데 각 라우터가 독립적으로 운영되는 기존의 분산 네트워크에서는 흩어진 네트워크 연결 정보로 인해 최적인 멀티캐스트 라우팅 트리를 형성하는 것이 쉽지 않다. 하지만 기존의 분산 네트워크 환경과 다르게 SDN 환경은 네트워크 제어 평면과 데이터 평면으로 분리하였기 때문에 SDN 제어기(Controller)가 제어 평면을 이용해 네트워크를 중앙집중적으로 제어하는 것이 가능하다. 이러한 장점으로 SDN 환경에서 멀티캐스트 라우팅 트리는 기존의 분산 네트워크 환경에서보다 효과적으로 형성할 수 있다. 따라서 SDN 환경에서 멀티캐스트 라우팅 트리를 보다 효율적으로 생성하는 연구들이 활발히 진행되고 있다[4]. 그런데 SDN 환경에서 멀티캐스트 라우팅 트리를 생성하는 문제는 대게 스타이너 트리(Steiner Tree)를 생성하는 문제로 귀결되고 이는 NP-Complete의 문제이다[5][6].

강화학습은 기본적으로 그림 1과 같은 구조를 가진다. 그림에서 에이전트(Agent)는 환경(Environment)과 상호작용하면서 환경에서 인식한 현재 상태에서 수집한 경험으로부터 가능한 행동(Action)을 선택한다. 또한 강화학습은 보상(Reward) 함수에 기반을 두고 있는데 보상은 환경으로부터 에이전트가 전달받는 것으로 현재 취한 행동에 대한 피드백을 받는 것으로 볼 수 있다. 전통적인 강화학습 방법에는 Q-learning[7], SARSA[8]와 같은 기법들이 존재하나 이 기법들은 여러 한계점을 가지고 있다. 그 중 하나는 모두 테이블 기반의 방법론으로서 에이전트와 환경이 상호작용하면서 이루어질 수 있는 모든 상태와 행동의 경우에 대해 사전에 기록하여 최대의 보상을 얻도록 하는 방식을 사용한다는 것에 있다. 이러한 테이블 기반의 방법론은 해결하고자 하는 문제가 복잡한 문제일 경우 무한히 많은 상태와 행동 쌍에 대한 경우를 저장할 수 없기 때문에 계산 복잡도 및 차원의 저주 같은 문제점이 있다. 따라서 이를 해결하기 위해 Deep-Q-Network(DQN)과 같이 인공신경망을 이용하는 방법이 제안되었다[9].

Fig. 1. 
Reinforcement learning model

따라서 DQN 기법을 여러 분야의 적용하는 연구들이 진행되었는데 [10]은 멀티캐스트 라우팅 트리 생성 문제에 DQN 기법을 적용한 연구이다. [10]에서는 학습과 테스트 모두 동일한 네트워크 토폴로지를 가정하고 멀티캐스트 노드 케이스에 대한 변화를 고려한 실험을 진행하였다. 그러나 네트워크 환경은 링크 연결 정보가 수정될 수 있는 가변적 특징을 가지고 있기 때문에 가변적 네트워크 링크 토폴로지에서는 적절한 성능을 나타내지 못한다.

따라서 본 논문에서는 멀티캐스트 노드 케이스 뿐만 아니라 다양한 링크 토폴로지 케이스를 사용하여 가변적인 네트워크 링크 토폴로지에서 유연하게 멀티캐스트 라우팅 트리를 생성하는 학습 방법을 제안한다.

SDN 환경에서 멀티캐스트 라우팅 트리 생성 문제는 다음과 같이 정의할 수 있다. SDN 환경에서 네트워크를 구성하는 노드들은 SDN 제어기에 의해서 완전하게 통제되고 관측 가능하다. 따라서 기존의 분산 네트워크와 다르게 전체 네트워크 관점에서 라우팅이 가능하다. 이때 전체 네트워크 관점에서의 라우팅은 출발 노드에서 모든 목적지 노드들까지 최소 비용으로 연결하는 문제이다. 이러한 문제는 스타이너 트리를 생성하는 문제로 알려져 있고 대게 NP-Complete의 문제로 귀결된다. 따라서 네트워크를 구성하는 노드의 수가 증가할수록 최적의 스타이너 트리를 찾는 것을 어렵다.

따라서 본 연구에서는 인공지능을 이용한 접근 방법으로서 강화학습을 이용하여 멀티캐스트 라우팅 트리 생성 문제를 다룬다. 또한 고정적 네트워크 토폴로지 환경을 가정하지 않고 가변적인 네트워크 토폴로지 환경을 가정하여 SDN에서 멀티캐스트 라우팅 트리를 생성하고자 한다. 다음은 강화학습 기법을 이용하기 위해서 SDN에서 멀티캐스트 라우팅 트리 생성 문제를 MDP(Markov Decision Process)로 나타낸 것이다. MDP M은 M {S, A, R, γ}의 집합으로 구성된다. S는 상태(State)를 나타내며 강화학습 에이전트가 환경으로부터 관측한 정보를 나타낸다. SDN에서는 제어기가 강화학습 에이전트의 역할을 하므로 SDN에서 발생하는 네트워크 지연, 대역폭, 링크 정보 등의 모든 정보를 상태로 관측하는 것이 가능하다. A는 행동(Action)으로 강화학습 에이전트가 관측한 상태로부터 행동 가능한 행동 집합을 나타낸다. 즉, 멀티캐스트 라우팅 트리를 생성하는 문제에서 행동은 다음으로 연결 가능한 링크들이 된다. R은 보상(Reward)을 나타낸다. 보상은 강화학습 에이전트가 현재 상태에서 어떤 행동을 했을 때 변화한 환경으로부터 주어지는 값이다. 따라서 멀티캐스트 라우팅 트리 생성 문제에서는 목적지 노드에 연결되면 보상이 발생한다. γ는 0~1 사이의 값을 가지며 미래의 보상에 대한 감가율을 나타낸다. 보상은 강화학습 에이전트가 적은 행동을 하면서 목표에 도달할수록 누적되어야 한다. 따라서 멀티캐스트 라우팅 트리 생성 시에 적은 링크 개수를 선택할수록 누적 보상이 증가된다.

그림 2는 학습된 DQN 에이전트를 통해 멀티캐스트 라우팅 트리를 생성하고 이를 바탕으로 플로우 규칙(Flow Rule)을 SDN 스위치들에게 전달하는 과정을 보여주고 있다. SDN 환경에서 SDN 제어기는 여러 SDN 스위치로부터 네트워크 상황을 측정한 여러 정보들을 전달 받는다.

Fig. 2. 
Process of forwarding the flow rule using multicast routing tree constructed based on DQN agent

SDN 제어기는 전달 받는 정보들 중에서 멀티캐스트 출발지, 목적지들에 대한 정보와 현재 네트워크 토폴로지의 링크 연결 정보를 DQN 에이전트에게 전달한다. 효율적인 멀티캐스트 라우팅 트리를 생성하도록 학습된 DQN 에이전트는 전달받은 정보를 이용하여 해당 네트워크 상황에 맞는 멀티캐스트 라우팅 트리를 생성하여 SDN 제어기에게 전달한다. SDN 제어기는 멀티캐스트 라우팅 트리에 따라 플로우 규칙을 생성하여 SDN 스위치들에게 전송한다. 그 후 출발지 노드의 멀티캐스트 패킷은 각 스위치에 존재하는 플로우 규칙에 따라 멀티캐스트 라우팅되어 목적지에 도착한다.

그림 3은 DQN 에이전트를 학습시키는 과정을 보여주고 있다. 그림에서 DQN 에이전트는 SDN 제어기로부터 네트워크 정보 즉, 상태 S를 전달받는데 여기에는 멀티캐스트 요청, 링크 연결 정보, 지연 등과 같이 스위치에서 제어기로 수집된 정보가 포함된다. DQN 에이전트는 이러한 상태 S에서 다음 연결할 노드를 e-greedy 방법을 이용하여 결정한다. e-greedy 방법을 이용할 때, 연결 가능한 다음 행동들 중에서 무작위로 선택하거나 신경망(Neural Network)에 입력으로 전달하여 나온 결과로부터 최대 Q-value를 가지는 행동을 선택한다. 이렇게 선택된 행동, 즉 노드가 목표로 하는 멀티캐스트 요청의 목적지 중 하나이면 보상 값을 환경으로부터 전달받는다. 이러한 과정에서 발생하는 경험들을 리플라이 버퍼에 저장하고 모든 목적지를 찾게 되면 한 번의 에피소드(Episode)가 종료된다.

Fig. 3. 
Proposed process of training DQN agent

이때 본 논문에서 제안하는 방법은 한 번의 에피소드가 종료될 때 마다 생성 가능한 네트워크 링크 토폴로지의 분포로부터 새로운 네트워크 링크 토폴로지 환경을 추출한다. 따라서 기존 연구와 달리 DQN 에이전트는 에피소드마다 새로운 네트워크 상황에서 학습하게 된다. 새로운 환경에서 DQN 에이전트가 일정한 수의 에피소드만큼 경험하게 되면 리플라이 버퍼에 저장되어 있던 경험들에서 미니배치 데이터를 무작위로 추출한다. 이 데이터를 이용해 학습 신경망을 학습 시킨다. 또한 일정 에피소드 마다 목적 신경망으로 학습 신경망의 가중치을 복사한다.

그림 4에서는 학습 후의 DQN 에이전트의 멀티캐스트 라우팅 트리 생성 과정을 도식화한 것이다. 앞서 언급한 그림 2의 과정과 같이 DQN 에이전트는 SDN 제어기로부터 네트워크 상황과 멀티캐스트 정보들을 받는다. DQN 에이전트가 멀티캐스트 라우팅 트리를 생성하는 첫 단계에서는 SDN 제어기로부터 주어진 정보들을 학습된 에이전트 신경망의 입력으로 사용하고 신경망의 결과 값으로부터 행동을 선택하며 트리 생성을 시작한다. 두 번째 단계에서는 에이전트 신경망에게 현재 연결된 링크 토폴로지와 멀티캐스트 정보를 입력으로 사용한다. 따라서 에이전트 신경망은 현재 연결된 링크 토폴로지 정보를 고려한 결과 값을 출력하고 모든 목적지를 연결할 때까지 반복한다. 모든 목적지를 연결하게 되면 멀티캐스트 라우팅 트리 구성이 완료된다. 이러한 생성 방법이 기존 연구와 다른 점은 에이전트가 학습 과정에서 멀티캐스트 라우팅 트리를 매번 생성할 때마다 새로운 환경에 노출 된다는 것이다.

Fig. 4. 
Process of constructing multicast routing tree for DQN agent

기존 연구에서는 학습 과정에서 항상 같은 환경에 대해서 멀티캐스트 라우팅 트리를 생성하므로 멀티캐스트 라우팅 트리를 생성하는 신경망의 대응 능력이 떨어지지만, 매번 새로운 환경에 처하게 되는 제안 방법은 새로운 환경에 대해 대응하여 학습하게 된다.

위와 같이 생성된 멀티캐스트 라우팅 트리의 성능을 평가하기 위해 다음 절인 실험에서는 본 논문에서 제안한 한 번의 에피소드가 종료되었을 때 새로운 환경을 추출하는 방식으로 학습한 DQN 에이전트가 일반적인 고정적 네트워크 토폴로지에서 학습한 DQN 에이전트에 비해 가변적인 네트워크 환경에서 얼마나 나은 성능을 내는지 정량적으로 평가해 본다.

본 논문에서 제안하는 가변적인 네트워크 링크 토폴로지를 고려한 DQN 에이전트 기반의 멀티캐스트 라우팅 트리 생성 방법을 구현하기 위해서 먼저 표 1과 표 2와 같이 데이터 집합을 생성하였다. 표 1은 고정적 네트워크 환경에서 학습을 진행하는 고정(Fixed) DQN 에이전트와 가변적 네트워크 환경에서 학습을 진행하는 범용(General) DQN 에이전트가 공통으로 사용하는 멀티캐스트 노드 집합을 나타낸다. 네트워크 구성 노드가 10개인 경우 학습에는 4,010개, 테스트에는 1,010개의 멀티캐스트 노드 집합을 사용하고 노드가 20개인 경우 학습에서는 80,000개, 테스트에는 20,000개의 노드 집합을 사용한다.

표 2는 범용(General) DQN 에이전트가 사용할 네트워크 링크 토폴로지의 수를 보여주고 있다. 이때 생성 가능한 모든 네트워크 링크 토폴로지를 사용하는 것은 현실적으로 어렵기 때문에 일부 링크 토폴로지만을 임의로 선택하여 학습에 사용한다. 그 수는 네트워크 구성 노드가 10개 일 때 50,000개, 구성 노드가 20개일 때, 100,000개이다.

또한 실험에 사용한 노드 개수는 관련 연구와 비슷한 노드 개수를 가정하였다. 관련 연구인 [11][12]에서는 sprint network[13]를 사용하였는데 노드 개수 25개, 링크 개수 56개로 이루어져 있다. 본 논문에서 실험한 노드 개수가 비교적 작지만 다양한 링크 토폴로지에 대해서 실험하므로 적절하게 실험을 구성했다고 할 수 있다.

본 논문에서 학습한 DQN 에이전트들을 테스트하기 위해 그림 5와 같은 방법을 사용하였다. 그림에서 알 수 있듯이 각각 3개의 밀집도를 가지는 고정적 네트워크 환경에서 학습한 3개의 고정 DQN 에이전트와 가변적 네트워크에서 학습한 1개의 범용 DQN 에이전트가 존재한다. 고정 DQN 에이전트는 학습하지 않았던 다른 밀집도를 가지는 네트워크 토폴로지를 포함하여 테스트를 진행한다. 따라서 하나의 고정 DQN 에이전트마다 총 3개의 네트워크 토폴로지(학습 토폴로지 1개, 학습하지 않은 토폴로지 2개)에서 테스트 된다. 또한 범용 DQN 에이전트는 고정 DQN 에이전트와의 비교를 위해 고정 DQN 에이전트가 테스트된 네트워크 토폴로지에서 테스트를 진행한다. 그러므로 범용 DQN 에이전트는 총 3개의 네트워크 토폴로지에서 테스트 된다. 이에 따라 고정 에이전트는 자신이 학습한 네트워크 토폴로지에서는 좋은 성능을 보일 수 있으나 그 외 네트워크 토폴로지에서는 나쁜 성능을 보인다. 이에 반해 범용 에이전트는 여러 밀집도를 가지는 다양한 네트워크 토폴로지에서 고른 성능을 보인다.

Fig. 5. 
Comparative experiment diagram

학습된 DQN 에이전트의 정량적인 성능을 측정하기 위해 식 (1)과 같은 성능 비율(Performance ratio)을 사용한다. 성능 비율은 DQN 에이전트가 생성한 멀티캐스트 라우팅 트리 길이를 최적 멀티캐스트 라우팅 트리 길이로 나눈 것이다. 성능 비율 값이 1에 가까워질수록 생성된 멀티캐스트 라우팅 트리가 최적 멀티캐스트 라우팅 트리 길이에 가깝다고 말할 수 있다.

학습된 DQN 에이전트들의 멀티캐스트 라우팅 트리 생성 실험 결과는 그림 6, 그림 7과 같다. 그림 5와 그림 6은 노드 개수가 각각 10개, 20개 일 때의 각 DQN 에이전트의 성능 비율을 나타낸 그래프이다. 그림에서 Fixed_30, Fixed_50, Fixed_70은 학습에 사용된 네트워크 링크 밀집도가 30%, 50%, 70%인 고정 DQN 에이전트들을 나타낸다. 결과에서 알 수 있듯이 고정 에이전트는 자신이 학습한 네트워크 링크 밀집도를 가지는 토폴로지에서는 최적 성능인 1에 근접한 성능을 보이지만 다른 밀집도를 가지는 토폴로지에서는 성능이 급격히 떨어진다. 반면에 범용 에이전트는 특정 밀집도에서는 해당 밀집도 네트워크 링크 토폴로지를 집중적으로 학습한 고정 에이전트보다는 성능이 떨어지지만 다른 링크 밀집도를 가지는 네트워크 환경에서 전반적으로 고정 에이전트보다 모두 나은 성능을 보인다.

Fig. 6. 
Performance ratio for each agents that the number of nodes is 10

Fig. 7. 
Performance ratio for each agents that the number of nodes is 20