Full Echo Q-Routing.. 개념 정리

                                                                                                                                                         

                                                                                                                                                                                                                   

                                                                                                                                                         

                                                                                                                                                                                                             

                                                                                                                                                                                                          

모바일 환경, 차량으로 이동하는 등의 그런 동적으로 네트워크가 바뀌는 상황(즉 네트워크 토폴로지가 계속해서 바뀌는 동적인 상황)에서도 통신은 효율적으로 이루어져야 한다. 이 논문에서는 이 목적을 달성하기 위하여 기존의 Full echo Q-Routing 알고리즘을 개선해서 Adaptive Full echo Q-Routing 알고리즘을 제안한다.

기존의 Full echo Q-Routing 알고리즘도 어느 정도 이 목적을 이루기 위해서 제안된 알고리즘이지만, high load상황에서는 계속해서 oscillation이 발생하는 한계가 있다. 이 oscillation은 Q-value에 의해 계속 ‘이 라우터가 적합하다’라는 판단이 왔다갔다 하는 것이다. 즉 벤치마크로 제안된 그리드 네트워크(Fig 2.)에서 High load인 환경일 때 2-3번의 1번쌍과 14-15번의 2번쌍이 번갈아서 선택되는 진동 상황인 것이다.

(위의 벤치마크는 routing algorithms 분야에서는 딥러닝의 mnist같은 존재다. 즉 성능 평가의 기준이 되기 때문에 다른 알고리즘들과의 성능 평가 비교가 가능하게 된다.)

Full echo Q-routing algorithms을 사용할 시엔 위의 그리드 네트워크에서 부하가 심하게 걸리는 2-3번, 14-15번 노드 중에서 Q값이 작은 값으로 계속 바뀌는 현상이 발생한다. Q값을 주기적으로 주고받기 때문이다. (패킷 로드가 큰 상황에서 즉각적으로 경로가 바뀐다.) 즉 Full echo 방식은 기존의 Q-routing 방식에 비해 exploration을 더 열심히 한다는 것을 의미한다.(Q-routing에서는 값이 한 번 정해지면 바뀌지 않는다.) 

이 때 Q-routing algorithms에 비해 full echo q-routing algorithms방식은 추가적인 msg가 필요하다. 즉 계속해서 Q값을 얻어내기 위해 주기적으로 request를 수행하는 것과 return을 요구한다.(반면 adaptive full echo~방식은 full echo에 비해 추가적인 msg가 필요하지 않아서 full echo에 비해서는 상대적으로 실용적이지만 기존의 Q-routing에 비해서는 여전히 실용적이지 않다.)

 

그 결과 다음의 그래프의 simulation time이 30000을 넘어가는 시점에서부터 Average Delivery time에 진동이 나타나는 것을 관찰할 수 있다.

 

 

네트워크 토폴로지에서 노드들은 결국 agent다. agent라는 것은 결국 강화학습에 의해 학습을 하여 가장 적합한 action을 취하겠다는 것이 목적인데, 여기서는 어떤 이웃노드로 내가 가진 패킷을 보내야 목적지까지 빠른 시간에 보낼 수 있을까가 목적이 된다.

 

따라서 각각의 노드들은 자기들만의 큐 테이블과 큐 값을 가지고 있게 된다. 이 때 큐 값은 큐 테이블에서 가장 작은 값이다.

 

각 노드들이 갖고 있는 큐 테이블에는 자기들의 주변 노드들까지 가는 데 걸리는 시간을 갖고 있고, 이 시간 정보는 이웃노드들에게 request한 결과 받은 return값으로서 이 값 역시 시간에 해당하며 Q-value다.

 

즉 t값은 노드 x의 주변 노드들인 y들 각각의 노드들이 자기들이 갖고 있는 Q값중 가장 작은 값을 의미하며, 주변 노드들로부터 받는 값인 것이다.

 

이 때 Q값을 업데이트하는 핵심적인 공식은 다음과 같다.

 

q, s, t 그리고 Q값까지 모두 time이다. 따라서 산술연산이 가능하다.

 

 

위의 수식이 제대로 작동하기 위해서는 자기 주변의 노드들 뿐만 아니라, 자기 주변의 노드들이 또 자기들의 이웃노드들의 return값을 알고 있어야 한다. 즉 탐험-개발 전략(exploration-exploitation)을 사용하기 위해 추가적인 learning rate을 사용하여 adaptive하게(상황에 따라 적절하게 값이 바뀌는) 해당 learning rate이 바뀌도록 만들어주고자 한다. 

따라서 두 개의 learning rate이 필요하게 된다.

 

 

 주변의 이웃들로부터 받아들이는 return값의 평균을 내고, 이 평균값은 지속적으로 바뀌게 된다. 어쨌든 계속해서 바뀌는 이 값들 중에서 가장 큰 값을 Tmax로 두어, learning rate의 기준으로 삼는다. 결국 Test값이 계속 바뀌되, 낮은 값으로 바뀌게 되면 업데이트가 조금 일어나게 되는 상황이 되어 adaptive하게 된다. 즉 해당 노드의 oscillation이 덜 일어나게 된다.

Test값이 계속 바뀌게 되는데, Tmax값과 유사할수록 eta2값이 커져서 업데이트가 크게 일어나게 되고, Test값이 작아질수록 eta2값이 작아져서 업데이트가 덜 일어나게 된다.

이상적인 상황은 Test값이 작아지는 상황 즉 delivery가 빨리 되서 delivert time값이 작은 상황을 말한다. 이 때 delivery time이라는 것은 global deliverty time이 아니라 local delivery time으로서 자기 주변의 이웃 노드들까지의 delivery time만을 의미한다. global delivery time은 전지적인 시점이 필요한데 현실적으로 불가능하다.(시뮬레이션을 위한 제한된 환경이라면 모를까...)

 

그 결과 다음과 같이 개선된 결과를 얻게 된다.

 

 

즉, oscillation이 감소되었다는 것은 over time(시간이 지남에 따라) 네트워크 topology가 바뀌는 등의 동적인 상황(이 상황까지는 기존의 Full echo Q-routing algorithms도 커버함) & high load상황(기존의 알고리즘이 한계를 보이는 상황)에서도 안정적으로 라우팅 환경이 보장된다는 것을 의미한다.

 

---

토폴로지라는 것은 일반적인 의미로는 물리적인(우리 눈에 보이고 만질 수 있는) 배치(어떤 물체들의 각각의 위치)의 형태(구성)로 이루어진 어떤 현장의 종류를 말한다.

그러나 네트워크 분야에서의 토폴로지는 노드들(라우터들이나 컴퓨터들)과 이에 연결된 회선들을 포함한 네트워크들의 배열이나 구성을 개념적인(만질 수 없으나 이해할 수 있는) 그림으로 표현한 것이다.

 

성형 토폴로지(star topology)

망형 토폴로지(mesh topology)

버스형 토폴로지(bus topology)

환형 토폴로지(ring topology)

나무형 토폴로지(tree topology)