흐릿하게 보이는 링크 상태 라우팅 프로토콜

Hazy Sighted Link State Routing Protocol

Hlugy-View Link State Routing Protocol(HSLS)은 CUWiN Foundation에 의해 개발되고 있는 무선 메쉬 네트워크 라우팅 프로토콜입니다.이는 메시 네트워크 내의 디지털무선을 통해 통신하는 컴퓨터가 직접 무선접촉이 닿지 않는 컴퓨터에 메시지를 전송할 수 있도록 하는 알고리즘입니다.네트워크 오버헤드는 이론적으로 [1]최적입니다.액티브 및 리액티브링크 스테이트 루팅을 모두 사용하여 네트워크 갱신을 공간과 시간으로 제한합니다.그 발명가들은 그것이 유선 네트워크를 연결하는 더 효율적인 프로토콜이라고 믿고 있다.HSLS는 BBN Technologies의 연구자들에 의해 발명되었다.

효율성.

HSLS는 1,000개 이상의 노드로 구성된 네트워크로 잘 확장되었으며, 대규모 네트워크에서는 다른 라우팅 알고리즘의 효율성을 초과하기 시작합니다.이는 링크 상태 정보를 최적으로 전파하기 위해 신중하게 설계된 업데이트 빈도와 업데이트 익스텐트의 균형을 사용하여 이루어집니다.기존 방식과는 달리 HSLS는 네트워크의 나머지 부분과의 접속을 변경하는 이동 노드에 대응하기 위해 네트워크에 링크 스테이트 정보를 플래딩하지 않습니다.또한 HSLS에서는 각 노드가 같은 네트워크 뷰를 가질 필요가 없습니다.

왜 링크스테이트 프로토콜일까요?

링크 스테이트 알고리즘은 최적의 경로를 찾아 전송 용량의 낭비를 줄이기 때문에 이론적으로 매력적입니다.HSLS의[citation needed] 발명자들은 라우팅 프로토콜이 기본적으로 세 가지 다른 방식으로 분류된다고 주장합니다. 프로 액티브(OLSR 등), 리액티브(AODV 등), 그리고 차선의 루팅을 받아들이는 알고리즘입니다.그래프로 나타내면, 그것들은 단순한 단일 전략이기 때문에 효율이 저하해, 네트워크의 규모가 커집니다.가장 좋은 알고리즘은 중간에 있는 것 같다.

라우팅 정보는 "링크 상태 업데이트"라고 불립니다.링크 스테이트가 복사되는 거리는 "존속 가능 시간"이며, 어떤 노드에서 다음 노드로 복사될 수 있는 횟수 카운트입니다.

HSLS는 프로 액티브, 리액티브 및 차선의 라우팅 어프로치의 기능의 균형을 최적으로 유지하는 것으로 알려져 있습니다.이러한 전략은 링크스테이트 갱신을 시간과 공간에서 제한함으로써 조합됩니다.수명시간을 제한함으로써 전송용량을 줄일 수 있다.프로 액티브한 라우팅 갱신이 송신되는 시간을 제한함으로써, 복수의 갱신을 동시에 수집해 송신할 수 있어 송신 용량을 절약할 수 있습니다.

  • 정의상 링크 스테이트알고리즘은 사용 가능한 정보를 사용하여 최적의 루트를 생성하기 때문에 사용 가능한 정보를 바탕으로 라우팅이 최대한 최적화됩니다.
  • 원거리 노드가 정보를 얻는 빈도가 낮기 때문에 최적의 라우팅이 자연스럽게 이루어집니다.
  • 프로 액티브한 갱신을 최소한으로 억제하는 것이 어려운 부분입니다.이 방식은 2개의 제한된 링크 스테이트라우팅 알고리즘에서 채택되었습니다.첫 번째 '근시안 링크스테이트 라우팅'은 라우팅 정보를 전송할 수 있는 노드홉 수에 제한이 있습니다다른 라우팅 알고리즘인 "Discretized Link-State Routing"은 라우팅 정보가 전송될 수 있는 시간을 제한합니다.공간과 시간 양쪽에서 최적의 업데이트 감쇠는 약 2이므로, 그 결과 데이터에 대한 프랙탈2 노드 홉 거리(1, 2, 4, 1, 1, 8... 등)의 프랙탈 파워 오브 2 노드홉 거리(1, 2, 1, 8...)가 프로 액티브한 업데이트가 됩니다.
  • 리액티브 라우팅은 인접 링크를 사용하려고 하면 다음 타이머가 만료되어 대체 루트를 찾기 위한 정보가 그려지기 때문에 발생합니다.연속적으로 장애가 발생할 때마다 재시도를 통해 메시 노드의 대상 범위가 넓어집니다.

구조

설계자는 글로벌 네트워크 낭비의 척도를 정의함으로써 이러한 항목의 조정을 시작했습니다.여기에는 루트 업데이트 전송으로 인한 낭비와 비효율적인 전송 경로로 인한 낭비도 포함됩니다.정확한 정의는 "총 오버헤드는 노드에 순간적인 완전한 토폴로지 정보가 있다고 가정함으로써 최단거리(홉 수)에 걸쳐 패킷을 전송하기 위해 필요한 최소 대역폭을 초과하는 대역폭 양으로 정의됩니다."

그런 다음 몇 가지 합리적인 가정을 하고 수학적 최적화를 사용하여 링크 상태 업데이트를 전송하는 시간 및 링크 상태 업데이트가 커버해야 하는 노드의 폭을 찾아냈습니다.

기본적으로 둘 다 시간이 지날수록 2의 제곱으로 커져야 합니다.이론적으로 최적의 숫자는 2에 매우 가깝고 오차는 0.7%에 불과합니다.이는 가정에서의 오류보다 상당히 작기 때문에 2가 완전히 타당한 수치입니다.

연결이 끊어질 때마다 로컬라우팅 업데이트가 강제됩니다.이것은 알고리즘의 반응적인 부분입니다.로컬 라우팅 업데이트는 타이머 만료와 동일하게 동작합니다.

그렇지 않으면 마지막 업데이트 이후의 지연이 2배로 증가할 때마다 노드는 고려 중인 네트워크 홉의 수를 2배로 늘리는 라우팅 정보를 전송합니다.이것은 상한까지 계속됩니다.상한은 네트워크에 글로벌사이즈를 부여하고 이동노드가 없는 네트워크의 최대 응답시간을 고정합니다.

이 알고리즘에는 단일 방향 링크나 오래된 라우팅 테이블로 인해 발생하는 루프 전송 등 무선 네트워크에서 일반적인 경우에 대처하기 위한 몇 가지 특별한 기능이 있습니다.특히 인접 노드에 대한 링크가 손실될 때마다 모든 전송을 인근 노드로 재루팅합니다.또, 이 경우는 인접 관계도 재발송신합니다.이것은 가장 가치 있는 장거리 링크도 무선 네트워크에서 가장 신뢰성이 낮기 때문에 정확하게 유용합니다.

이점

네트워크는 실시간으로 매우 좋은 경로를 확립하고 네트워크를 연결하기 위해 전송되는 메시지의 수와 크기를 다른 많은 프로토콜에 비해 크게 줄입니다.단순한 메시 라우팅 프로토콜의 대부분은 링크가 변경될 때마다 라우팅 정보로 네트워크 전체에 플래딩됩니다.

실제 알고리즘은 매우 간단합니다.

라우팅 정보와 데이터 전송은 분산되므로 로컬핫스팟이 없는 뛰어난 신뢰성과 퍼포먼스를 얻을 수 있습니다.

시스템에서는 라우팅 테이블을 유지하기 위해 대용량의 메모리를 갖춘 유능한 노드가 필요합니다.다행히도, 이것들은 항상 저렴해지고 있다.

모든 노드에는 오래된 완전한 라우팅 정보가 존재하기 때문에 네트워크 내에 노드가 있는지 여부를 매우 빠르고 비교적 정확하게 추측할 수 있습니다.단, 이는 노드가 네트워크에 존재하는지 여부를 확인하는 것과는 다릅니다.이 추측은 전화와 같은 대부분의 요금 네트워크 사용에는 적합할 수 있지만 안전 관련 군사 또는 항전 장치에는 적합하지 않을 수 있습니다.

HSLS는 뛰어난 scalability 속성을 가지고 있습니다.총 오버헤드의 점근적 스케일러빌리티는 O 1.5 O와 O2(N로 스케일링되는 표준 링크스테이트에 비해 O( 1.5)\displaystyle O(N^{2})입니다.

크리틱

HSLS는 원거리 갱신을 송신하는 일이 드물기 때문에 노드에는 원거리 노드가 아직 존재하는지 여부에 대한 최신 정보가 없습니다.링크 스테이트 데이터베이스에 장애가 발생한 노드로부터의 알림이 포함되어 있을 가능성이 있기 때문에 이 문제는 모든 링크 스테이트 프로토콜에서 어느 정도 존재합니다.그러나 OSPF와 같은 프로토콜은 장애가 발생한 노드 인접 라우터에서 링크 상태 업데이트를 전파하므로 모든 노드가 장애가 발생한 노드의 소멸(또는 연결 해제)을 빠르게 학습합니다.HSLS에서는 이전 네이버가 장거리 방송을 송신할 때까지 10홉 거리에 있는 노드와 장애가 발생한 노드를 명확히 할 수 없습니다.따라서 HSLS는 높은 보증이 필요한 상황에서 실패할 수 있습니다.

HSLS에 대해 설명하는 문서에서는 보안에 중점을 두지 않지만 라우팅 업데이트에 관한 디지털 서명 등의 기술은 HSLS에서 사용할 수 있습니다(디지털 서명이 있는 OSPF와 유사합니다).BBN은 네이버디스커버리 메시지 및 링크스테이트 업데이트에 대해 디지털 서명이 있는 HSLS를 실장하고 있습니다.애드혹 환경에서는 공개 키 인프라스트럭처 서버의 도달 가능성을 보증할 수 없기 때문에 이러한 스킴은 실제로는 어렵습니다.거의 모든 라우팅 프로토콜과 마찬가지로 HSLS에는 데이터 트래픽을 보호하는 메커니즘이 포함되어 있지 않습니다(IPSec 및 TLS 참조).

「 」를 참조해 주세요.

레퍼런스

  1. ^ "Hazy Sighted Link State (HSLS) Routing: A Scalable Link State Algorithm" (PDF). BBN Technologies. Archived from the original (PDF) on 2008-07-06. Retrieved 2008-02-20. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)

외부 링크

  • OLSR fisheye - olsr.org의 OLSR은 HSLS와 동등한 "fisherheye" 알고리즘을 구현했다.
  • NRLOLSR 프로토타입 - 옵션의 HSLS 기능을 제공하는 확장 OLSR