주뇽's 저장소
Dealing with Changes: Resilient Routing via Graph Neural Networks and Multi-Agent Deep Reinforcement Learning 논문 리뷰 본문
Dealing with Changes: Resilient Routing via Graph Neural Networks and Multi-Agent Deep Reinforcement Learning 논문 리뷰
뎁쭌 2023. 10. 17. 21:17• Bhavanasi S S, Pappone L, Esposito F. Dealing with Changes: Resilient Routing via Graph Neural Networks and Multi-Agent Deep Reinforcement Learning[J]. IEEE Transactions on Network and Service Management, 2023. Link Code
변화에 대처하기: 그래프 신경망 및 다중 에이전트 심층 강화 학습을 통한 탄력적 라우팅
Dealing with Changes: Resilient Routing via Graph Neural Networks and Multi-Agent Deep Reinforcement Learning
Abstract
I. INTRODUCTION
강화 학습(RL)을 포함한 머신 러닝 기술은 네트워크 트래픽 예측 및 리소스 관리와 같은 작업을 개선하기 위해 컴퓨터 네트워킹에 널리 적용되어 왔다. 심층 신경망을 훈련시켜 Q-함수에 근사치를 구하는 RL은 게임에서 인간을 이기고 자율 주행 자동차를 구현하는 등 다양한 응용 분야에서 성공을 거두면서 각광을 받고 있다. 컴퓨터 네트워크의 경우 단일 에이전트를 통해 환경을 학습하고 기존 라우팅 프로토콜의 한계를 해결하기 위해 RL을 사용해 왔다. 그러나 단일 에이전트가 네트워크 토폴로지를 암묵적으로 학습해야 하는 경우 문제가 발생하므로, 제안된 접근 방식에서는 이러한 한계를 극복하기 위해 그래프 컨볼루션 네트워크(GCN)와 다중 에이전트 RL과 같은 분산 학습 방법을 사용할 것을 제안한다.
다중 에이전트 강화 학습(RL)에서는 에이전트가 공통의 목표를 향해 함께 작업하므로 단일 RL 에이전트에 비해 더 빠른 학습, 개인 정보 보호, 더 강력한 알고리즘을 구현할 수 있다. 그래프 컨볼루션 네트워크(GCN)와 다중 에이전트 RL은 글로벌 및 동적 네트워크 조건을 인식하면서 효율적인 경로를 선택하기 위해 로컬 관찰을 고려함으로써 분산 라우팅 학습 전략 수립의 복잡성을 해결하는 데 도움이 된다. 이 접근 방식은 컴퓨터 네트워크에서 라우팅 알고리즘의 효율성과 적응성을 개선하는 것을 목표로 한다.
이 논문에서 저자는 복원력 있는 RL 기반 라우팅 문제를 다루는데, 이는 RL 모델을 재교육하지 않고도 컴퓨터 네트워크의 변화에 적응할 수 있는 기능을 말한다. 제안된 접근 방식은 광역 네트워크, 도메인 내 및 도메인 간 라우팅, 소프트웨어 정의 네트워크에 적용할 수 있다. 네트워크 에지 또는 트래픽 엔지니어링 정책과 같은 특정 시나리오에 따라 다른 라우팅 규칙을 고려해야 할 수 있으며 분산 접근 방식이 필요할 수 있다.
저자는 서로 다른 학습 알고리즘을 활용하는 두 가지 복원력 있는 RL 기반 라우팅 체계, 즉 단일 에이전트 접근 방식과 다중 에이전트 솔루션을 소개한다. 두 접근 방식 모두 네트워크 토폴로지의 중대한 변화를 처리하는 데 있어 이점을 보여준다. 단일 에이전트 RL 라우팅 알고리즘은 그래프 신경망을 활용하여 재학습의 필요성을 줄이고, 다중 에이전트 RL 솔루션은 딥 큐 네트워크를 기반으로 연합된 라우팅 에이전트 간의 협력 최적화를 가능하게 한다.
단일 에이전트 그래프 컨볼루션 네트워크(SA-GCN) 알고리즘은 그래프 형식으로 인코딩된 네트워크 트래픽 데이터 세트에서 직접 작동하므로 컴퓨터 네트워크 인접 행렬로 표시되는 모든 네트워크 토폴로지에서 강화 학습(RL) 라우팅 시스템을 훈련할 수 있다. 이 접근 방식을 사용하면 신경망을 재학습할 필요 없이 라우팅 및 혼잡 이벤트의 변경에 따라 RL 정책을 조정할 수 있다. 이와는 대조적으로 MA-DQN(Multi-Agent routing with Deep Q-Network) 알고리즘은 각 에이전트가 로컬에서 라우팅 결정을 내린다.
이 연구에 따르면 네트워크 토폴로지를 강화 학습(RL) 에이전트의 상태 공간에 명시적으로 통합하면 학습 시간이 크게 개선되는 것으로 나타났다. 이는 머신러닝 모델이 지연 시간과 대역폭의 변화를 효과적으로 처리할 수 있기 때문이다. 또한 연구진은 네트워크 크기, 경쟁 흐름, 혼잡한 링크, 링크 및 노드 장애와 같은 요소를 고려하면서 다양한 RL 모델을 평가하고 지연 시간 및 대역폭과 같은 컴퓨터 네트워크의 서비스 품질(QoS) 메트릭을 최적화하는 능력을 테스트했다.
이 연구의 저자들은 RL 기반 알고리즘이 기존 라우팅 알고리즘보다 성능이 뛰어나며 다양한 지표를 기준으로 전반적인 개선이 이루어졌다는 사실을 발견했다. 두 솔루션을 비교한 결과, MA-DQN 라우팅 알고리즘이 SA-GCN 모델보다 더 빠르게 최적의 정책을 달성한다는 것을 입증했다. 그러나 신경망 모델 자체에 토폴로지가 인코딩되어 있기 때문에 다른 네트워크 토폴로지에 쉽게 적용하기 어렵다는 단점이 있는 반면, SA-GCN 알고리즘은 토폴로지 변경을 처리하는 데 더 유연한 솔루션을 제공한다.
II. RELATED WORK
컴퓨터 네트워크의 라우팅 프로토콜은 복잡하고 동적인 네트워크 토폴로지 처리, 선택된 경로와 서비스 품질(QoS) 간의 상관관계 학습, 라우팅 결정의 영향 예측 등 머신 러닝 모델에 어려운 과제를 제시한다. 기존의 강화 학습(RL) 알고리즘, 특히 Q-러닝은 변화하는 환경에 적응할 수 있기 때문에 트래픽 라우팅 문제를 해결하는 데 사용되어 왔다. 특정 네트워크 토폴로지 및 유틸리티 요구 사항에 따라 학습자 간의 학습 능력 분배 및 협업에 변화를 주면서 트래픽 라우팅에 RL을 적용하기 위해 다양한 기술이 제안되었다.
Single-Agent Deep Q-learning for Traffic Engineering.
단일 에이전트 딥 큐 러닝은 강화 학습의 일종인 딥 큐 러닝을 활용하여 트래픽 엔지니어링 문제를 해결하는 최근의 접근 방식이다. 네트워크의 실시간 라우팅 최적화, 혼잡 제어, 리소스 관리 등에 적용되고 있다. 연구에 따르면 딥 큐 러닝은 서비스 가용성 측면에서 다른 딥 강화 학습 알고리즘보다 성능이 뛰어나 네트워크 성능을 개선하는 데 유망한 기술이라고 한다.
[16]의 연구에서는 소프트웨어 정의 네트워크(SDN)에서 다양한 서비스 품질(QoS) 지표를 개선하는 탐욕적인 온라인 라우팅 알고리즘을 개발하기 위해 딥 Q-러닝 접근 방식을 사용했다. 이 알고리즘은 경험 재생을 우선시하는 결투 심층 Q-네트워크를 구현함으로써 네트워크 토폴로지를 성공적으로 학습하고 기존 학습 기반 방식에 비해 대역폭을 최대화하면서 지연, 비용, 손실을 줄이는 측면에서 더 나은 성능을 달성했다. 하지만 이번 연구는 QoS 라우팅 최적화를 위한 딥 Q-러닝에 그래프 컨볼루션 네트워크(GCN)를 적용하여 기존 솔루션과는 다른 접근 방식을 연구하는 데 초점을 맞추고 있다.
Routing with Multi-Agent Reinforcement Learning.
다중 에이전트 강화 학습을 사용한 라우팅은 동적 네트워크에서 라우팅 프로토콜을 최적화하기 위해 다중 에이전트 강화 학습(MARL)이라는 기술을 적용하는 것을 말한다. 이전 연구에서 MARL이 라우팅 구성을 자율적으로 배포할 수 있다는 사실이 밝혀졌지만, 일부 연구자들은 중앙 집중식 컨트롤러 접근 방식이 광범위하게 분산된 소스에서 실시간 네트워크 상태를 수집하기 어렵기 때문에 대규모 네트워크에서 어려움을 겪을 수 있다고 주장한다.
다중 에이전트 강화 학습(MARL)은 통신 네트워크에서 라우팅 프로토콜을 최적화하는 데 중점을 둔 연구 분야이다. MARL은 실시간 Q-러닝과 액터-크리틱 방법을 결합하여 적응형 라우팅 프레임워크를 만든다. 이 접근 방식은 강화 학습 기법을 활용하여 라우팅 결정의 효율성과 성능을 개선하는 것을 목표로 한다.
Pinyoanuntapong 등은 다중 에이전트 마르코프 의사 결정 프로세스(MA-MDP) 프레임워크를 사용하여 통신 네트워크에서 트래픽 엔지니어링 의사 결정 문제를 해결하는 방법을 제안했다. 트래픽 인식 라우팅을 위해 Q 라우팅 기법을 활용했지만, 이 접근 방식은 완전히 분산된 다중 에이전트 심층 Q 학습 강화 학습 알고리즘을 사용하여 서비스 품질(QoS) 요구 사항과 네트워크 토폴로지의 변화를 처리했다. 이를 통해 QoS와 동적 네트워크 조건을 모두 고려하는 적응형 라우팅이 가능했다.
III. MODEL AND BACKGROUND ON GCN AND MA-DQN
GCN 및 MA-DQN의 모델 및 배경
이 섹션에서는 저자들이 단일 에이전트 및 다중 에이전트 라우팅 접근 방식에 대해 설명한다. 또한 사용된 강화 학습(RL) 모델을 설명하고 상태 및 행동 공간과 GCN 기반 알고리즘과 DQN 모두에 대해 선택한 보상 함수를 정의한다. 이 정보는 전체 연구의 맥락에서 라우팅 방법의 설계와 구성 요소를 이해하는 데 도움이 된다.
A. Single Agent GCN Policy Background and Settings
단일 에이전트 GCN 정책 배경 및 설정
컨볼루션 신경망(CNN)은 구조화된 데이터에는 효과적이지만 그래프와 같은 비정형 데이터에는 적합하지 않다. 이러한 경우에는 컨볼루션 연산을 사용하여 그래프의 노드와 가장자리에서 특징을 추출하는 그래프 합성곱 신경망(GCN)이 사용된다. GCN은 인접 노드의 정보를 전파하여 각 노드의 표현을 업데이트함으로써 로컬 패턴을 포착하고 현재 상태를 입력으로 받아 가능한 동작에 대한 확률 분포를 출력하는 심층 강화 학습(DRL) 알고리즘에서 정책 네트워크 역할을 한다.
RL 기반 라우팅 접근법의 적용은 재교육 없이 다양한 네트워크 토폴로지에 적응하는 데 한계가 있다는 비판을 받아왔다. 하지만 GCN(그래프 컨볼루션 네트워크)을 정책 네트워크에 통합하면 이전에 볼 수 없었던 네트워크 토폴로지에서 작동할 때도 RL 기반 라우팅의 성능을 유지할 수 있다. 이 연구에서 저자들은 모델이 훈련 단계에서 경험하지 못한 새로운 네트워크 토폴로지에 대해 RL 알고리즘의 각 에피소드를 훈련하여 더 나은 일반화를 가능하게 한다.
통신 네트워크의 경우, 여러 흐름 세트가 동일한 경로에서 일치할 때 혼잡이 발생할 수 있다. 이 문제를 완화하기 위해 제안된 접근 방식은 대체 경로를 식별하여 흐름 세트의 공존을 최소화하는 것을 목표로 한다. '플로우 공존'이란 가상 라우터나 스위치와 같이 동일한 포워딩 애플리케이션 프로세스 내에 두 개 이상의 플로우 세트가 동시에 존재하는 상황을 말한다.
통신 네트워크에서 적응형 라우팅의 맥락에서 이 문제는 순차적 의사 결정 문제(SDP)로 모델링되며, RL 에이전트가 선택한 행동이 후속 행동에 영향을 미친다. 이 문제는 유한 상태 집합(S), 유한 행동 집합(A), 즉각적인 보상(R), 할인 계수(γ)로 구성된 튜플이 특징이다. 정책 네트워크 출력을 최적화하기 위해 안정적인 학습을 보장하고 편차를 방지하는 근사 정책 최적화(PPO) 알고리즘을 사용하는 '온-정책 접근법'이 사용된다.
State Space
통신 네트워크에서 적응형 라우팅의 맥락에서 상태 공간은 환경에서 허용 가능한 상태의 집합을 의미한다. 임의 상태는 네트워크의 인접성 행렬, 라우팅할 플로우 집합의 소스 및 대상 노드를 인코딩하는 2열 행렬, 네트워크에서 경쟁하는 플로우 집합을 나타내는 행렬의 세 부분으로 구성된다. 상태에는 다른 흐름 집합의 경로가 포함되지 않고 소스 및 싱크 노드만 포함된다는 점에 유의해야 한다. 가능한 상태의 수는 노드 수와 경쟁하는 흐름의 최대 수에 따라 달라진다.
Action Space
통신 네트워크에서 적응형 라우팅을 위한 강화 학습 프레임워크의 맥락에서 작업 공간은 에이전트가 수행할 수 있는 작업의 집합을 의미한다. 이 경우 액션 공간은 원핫 벡터로 구성되며, 그래프에서 가장 높은 차수의 노드에 의해 크기가 결정된다. 이 접근 방식은 작업 공간을 압축하여 관리하기 쉽게 만들며, 에이전트가 특정 노드에 있을 때 정책에 따라 작업을 선택할 때 벡터의 처음 몇 개의 인덱스만 고려한다.
RL Reward Functions
통신 네트워크에서 라우팅의 맥락에서 RL 보상 함수는 라우팅 정책의 성능을 평가하는 데 사용된다. R(s, a)로 표시되는 즉각적인 보상은 주어진 상태 s에서 라우팅 결정 a를 선택했을 때 예상되는 보상을 나타낸다. 이 글에서 고려하는 첫 번째 보상 함수는 목적지에 도달할 수 없는 경우 -1, 목적지에 도달하면 1, 라우팅이 아직 진행 중이면 0의 값을 할당하는 이산형 희소 함수이다. 이 보상 함수는 단순하지만 링크 용량과 지연을 고려하지 않고 최소 홉으로 목적지에 도달하는 데에만 초점을 맞추기 때문에 최적의 라우팅 결정이 이루어지지 않을 수 있다.
B. Multi Agent DQN Background and Settings
고차원 입력으로부터 딥러닝을 학습하는 선구적인 접근법 중 하나는 [1]에 설명되어 있습니다. 저자들은 Q 학습의 변형으로 훈련된 컨볼루션 신경망(CNN)을 개발했으며, 이는 Atari 2006 게임에서 이전 방법에 비해 우수한 성능을 달성했다. 이를 바탕으로 또 다른 연구[23]에서는 강화 학습과 심층 신경망을 결합하여 심층 Q 네트워크(DQN)를 생성함으로써 접근 방식을 확장했다.
강화 학습의 표 형식 방법은 수렴을 보장하고 작은 상태-행동 공간에 효과적이지만, 더 크고 복잡한 문제에 대해 보다 적응력 있고 확장 가능한 접근 방식을 만들기 위해 신경망과 심층 강화 학습(RL)을 선택했다. 심층 강화 학습은 기본 알고리즘을 크게 변경하지 않고도 까다로운 미래 시나리오를 처리할 수 있는 프레임워크를 제공한다.
강화 학습(RL)에 신경망을 사용할 때는 일련의 관찰로 인한 상관관계, 정책을 변경할 수 있는 신경망의 사소한 변경, 행동과 목표 값 간의 상관관계로 인해 불안정성이 발생할 수 있다. 이러한 요인들은 학습 과정에 영향을 미쳐 RL 에이전트를 효과적으로 학습시키는 것을 어렵게 만들 수 있다. 이러한 문제를 해결하기 위해 리플레이 버퍼 및 반복 업데이트와 같은 기술을 사용하여 학습을 안정화하고 이러한 문제를 완화한다.
심층 강화 학습의 훈련 중 불안정성을 해결하기 위해 이 책의 저자들은 딥 큐 네트워크(DQN)에 두 가지 기술을 사용한다. 첫째, 리플레이 버퍼를 사용하여 상태-행동-보상-다음 상태 쌍의 튜플을 저장하고 무작위로 샘플링하여 데이터 상관관계를 방지한다. 둘째, DQN은 반복 업데이트 프로세스를 사용하여 주기적으로 동작 값을 목표 값으로 조정하여 동작과 목표 값 간의 상관관계를 완화한다. 이러한 기법은 학습 프로세스를 안정화하고 DQN 알고리즘의 성능을 개선하는 데 기여한다.
MA-DQN 모델의 맥락에서 컴퓨터 네트워크의 각 노드는 독립적인 에이전트로 기능하다. 이러한 에이전트는 자체 신경망을 가지고 있으며 로컬에서 라우팅 결정을 내린다. 각 에이전트의 상태 공간에는 네트워크의 라우터 수와 동일한 크기의 원핫 벡터로 표시되는 목적지가 포함되며, 이 상태 공간은 각 에피소드에 걸쳐 모든 에이전트에서 일관되게 유지된다.
State Space
상태 공간은 다중 에이전트 심층 Q 네트워크(MA-DQN) 모델에서 각 에이전트가 사용할 수 있는 정보를 의미한다. 구체적으로 상태 공간은 네트워크의 라우터 수와 동일한 크기의 목적지를 나타내는 원핫 벡터로 구성된다. 이 정보는 학습 과정의 각 에피소드에 걸쳐 모든 에이전트에 대해 동일하게 유지된다.
Action Space
작업 공간은 다중 상담원 라우팅 시나리오에서 상담원이 수행할 수 있는 가능한 작업의 집합을 의미한다. 작업 공간은 원핫 벡터로 표시되며 각 요소는 에이전트의 이웃에 해당한다. 각 시간 단계에서 에이전트는 상태 공간을 검사하고 하나의 이웃을 작업으로 선택한다. 이를 통해 에이전트는 네트워크의 현재 상태를 기반으로 정보에 입각한 라우팅 결정을 내릴 수 있다.
RL Reward Functions
대규모 네트워크에서의 라우팅에서는 각 라우팅 결정에 대해 에이전트에게 피드백을 제공하기 위해 고밀도 보상 함수가 사용된다. 에이전트는 방정식에 따라 양수 또는 음수 보상을 받게 되며, 이는 모델의 수렴 속도를 크게 향상시킨다. 긍정적 보상과 부정적 보상의 상대적 부호와 크기 차이는 모델의 성능에 큰 영향을 미치며, 부정적 보상의 크기가 긍정적 보상의 크기를 초과하면 모델이 더 강력하게 강화되어 특정 판단을 회피하게 된다.
**
결론
저자는 패킷 라우팅에 강화 학습을 사용하는 방법과 재학습 없이 네트워크 토폴로지 및 트래픽 변화에 적응할 수 있는 기능을 조사했다. 단일 도메인 및 다중 도메인 라우팅 시나리오에 초점을 맞춰 단일 도메인 라우팅을 위한 그래프 컨볼루션 네트워크(GCN) 기반의 단일 에이전트 RL 모델과 다중 도메인 라우팅을 위한 다중 에이전트 딥 Q-Learning 네트워크 모델을 제안했다. 실험 결과, GCN 기반 모델은 네트워크 토폴로지가 변경될 때 높은 서비스 품질(QoS) 지표를 더 잘 달성하는 것으로 나타났으며, 멀티 에이전트 모델은 대규모 네트워크에서 OSPF 및 ECMP와 같은 업계 표준 알고리즘을 능가하는 성능을 보였다.