MENTO 라우팅 알고리즘

MENTOR routing algorithm

MENTO 라우팅 알고리즘은 메시 네트워크의 라우팅, 특히 초기 토폴로지에 관한 알고리즘입니다.그것은 1991년에 Aaron Kershenbaum, Parviz Kermani, 그리고 George A에 의해 개발되었다.Grove 및 IEEE에 의해 발행되었습니다.

복잡성

경험적 관찰 결과 이 알고리즘의 복잡도 클래스는 O(N²) 또는 2차인 것으로 나타났습니다.이는 "현재 사용되고 있는 알고리즘에 비해 상당히 개선된 것이며, (아직도) 훨씬 느린 다른 절차와 경쟁적인 품질의 솔루션을 생산하고 있다"는 것을 의미한다.

방법론

알고리즘에서는 3가지 요소가 저비용 토폴로지에 도움이 된다고 가정하고 있습니다.즉, 이 경로는 회선이 아닌 직접적이고, 링크의 사용률이 높은 경향이 있습니다.즉, 이 경로는 거의 최대 동작 용량에 가깝습니다.또, 「긴, 고용량 링크」가 됩니다.이용될 수 있습니다.

전체적인 계획은 요건의 크기가 충분히 클 때마다 소스와 수신처 사이의 직접 경로를 통해 트래픽을 전송하고, 그 외의 모든 경우에는 트리 내의 경로를 통해 트래픽을 전송하는 것입니다.전자의 경우, 우리는 높은 활용률과 대용량의 직접적인 경로를 사용하고 있는 세 가지 목표를 모두 충족하고 있습니다.후자의 경우 트래픽을 가능한 한 집약하고 있기 때문에 적어도 마지막 두 가지 목표를 달성하고 있습니다.

후자의 경우 트래픽이 흐르는 최소 스패닝 트리는 Dijkstra 알고리즘과 Prim 알고리즘에 의해 경험적으로 정의됩니다.

레퍼런스