스케일러블 소스 라우팅
Scalable Source RoutingScalable Source Routing(SSR; 스케일러블소스 라우팅)은 모바일애드혹 네트워크, 메시 네트워크, 센서네트워크 등의 비구조화 네트워크용 라우팅 프로토콜입니다.소스 라우팅과 가상 링을 통한 루팅을 결합하여 "화음을 언더레이에 푸시"[1]하는 아이디어를 기반으로 합니다.
개념
가상 링
SSR는 가상 링으로 구성된 플랫 주소 공간에서 작동합니다.이것은 코드와 같은 피어 투 피어 오버레이 네트워크에서 인기 있는 개념입니다.링 구조에 대한 일반적인 지식을 통해 노드는 기반이 되는 물리 네트워크의 토폴로지를 인식하지 않고 패킷을 라우팅할 수 있습니다.물리 네트워크는 매우 역동적일 수 있지만 가상 링의 구조는 다소 정적인 상태로 유지됩니다.따라서 물리 네트워크의 플래딩을 회피할 수 있습니다.
패킷은, 행선지까지의 가상 거리(즉, 주소의 절대 차이)를 줄이기 위해서, 링을 따라서 이동합니다.각 노드가 가상 링 내의 올바른 이전 노드와 후속 노드를 인식하면 올바른 수신 노드에 대한 전달이 보증됩니다.링은 일정하다고 합니다.
대부분의 경우 라우팅은 링 내에서 정의된 방향을 갖는 것으로 간주되지만, 이는 이론을 단순화하는 데 도움이 될 뿐입니다.실제로 이는 필요하지 않으며 심지어 성능에도 해가 됩니다.
가상 링 내의 숏컷을 제공하는 코드 내의 핑거 테이블은 루트캐시로 대체됩니다.
소스 라우팅
실제 네트워크에서 SSR는 원본 라우팅을 사용합니다.릴레이 노드는, 소정의 패킷의 송신원루트의 횡단 부분을 기회론적으로 캐시 합니다.이것에 의해, 라우팅 정보의 수집이 용이하게 되어, 노드의 루트 캐시가 낡은 정보로 오염되는 것을 방지할 수 있습니다.
루트 집약
노드는 캐시 라인을 사용하기 위해 루트 캐시 내에 수신처에 대한 완전한 경로를 가질 필요가 없습니다.대신 메시지는 가상 링에서 진행 중인 가장 가까운 물리 노드에 라우팅됩니다.메시지가 이 중간 노드에 도착하면 해당 노드는 루트 캐시에서 발신기지 루트로 정보를 추가합니다.필요에 따라 이 단계를 반복합니다.메시지가 최종 수신처에 도착하면 경로 최적화 후(Dijkstra 알고리즘을 사용하여) 루트 업데이트메시지가 발신자 노드로 송신되어 발신자 루트캐시가 갱신됩니다.이 기술을 사용하면 고정 크기의 루트 캐시를 쉽게 사용할 수 있으므로 노드별 상태를 제한하고 SSR를 메모리 부족 [2]환경에서 사용할 수 있는 옵션이 됩니다.
분산 해시 테이블(DHT) 기능
SSR는 완전한 라우팅 프로토콜입니다(cf).OSI 모델의 네트워크 계층)은 분산 해시 테이블의 의미도 제공합니다.이를 통해 기존 라우팅 프로토콜 위에 오버레이 프로토콜을 설치하는 데 따른 오버헤드를 줄이고 애플리케이션이 키 기반 라우팅을 지원(또는 지원하도록 수정)하는 경우 [3][4]플래딩에 의존할 수 있는 MANET에서 검색 작업을 크게 가속화할 수 있습니다.제공된 DHT 기능을 사용하여 서버가 없는 경우에도 확장 가능한 네트워크 서비스를 구현할 수 있습니다.
알고리즘의 개요
부트스트랩(네트워크 부팅)
모든 노드는 정기적으로 물리 네이버에 "hello" 메시지를 브로드캐스트하여 네이버에 존재를 알립니다."Hello" 메시지에는 각 노드의 물리 네이버 목록이 포함됩니다.노드가 다른 노드의 "hello" 메시지에 포함된 것을 발견하면 노드는 양방향 연결을 가정하고 다른 노드를 물리 피어 목록에 추가합니다(나중에 라우팅에 사용).
또한 노드는 가상 링에 가입하기 위해 가정된 후계자에게 "네이버 알림" 메시지를 보냅니다.접속된 노드가 올바른 후계 노드가 아닌 것을 검출했을 경우, 문의 노드의 후계 노드에 대한 최선의 추측을 포함한 메시지로 응답합니다.올바른 가상 네이버를 찾을 때까지 이 과정을 반복합니다(ISPRP라고 하는 이 프로세스에 대한 자세한 내용은 [5]를 참조하십시오.부트스트래핑의 또 다른 방법은 선형화입니다.)[6]
라우팅
노드가 메시지를 라우트할 때
- 루트 캐시를 검색합니다.행선지에의 루트가 존재하는 경우는, 그 루트가 사용됩니다.
- 행선지에의 루트가 불명확한 경우, 노드는 메시지를 행선지의 거의 가까운 이전 노드로 라우팅 합니다.이 중간 노드는 라우팅 프로세스를 반복합니다.
- 노드 루트 캐시에는 아직 일치하는 루트가 포함되어 있지 않습니다.폴백으로 노드는 메시지를 가상 링 내의 후계자에게 전달합니다.가상 후계자는 물리적으로 노드에 근접하지 않을 수 있지만 부트스트래핑 프로세스에서 노드에 대한 루트가 확립되어 있어야 합니다.이 폴백스텝이 반복되면 메시지는 링을 따라 전송되고 최종적으로 수신처에 도달하거나 타임아웃됩니다.
분류
SSR에는 사후 대응적 구성 요소와 사전 예방적 구성 요소가 있으므로 하이브리드 라우팅 프로토콜이 됩니다.Virtual Ring Routing은 개념적으로 비슷합니다.가장 큰 차이는 VRR에서 노드별 상태(라우팅 테이블)를 구축하는 것과 비교하여 SSR에서 소스 루팅을 사용하는 것입니다.
이점
- 메시지 효율:로컬 브로드캐스트만 글로벌플래딩 없음
- 메모리 부족.노드당 상태가 작고 제한적입니다.
- DHT 기능은 검색을 고속화하거나 서버리스 인프라스트럭처를 구축하는 데 사용할 수 있습니다.
단점들
- 발견된 경로가 필요 이상으로 길어질 수 있습니다.
- 송신원루트는 메시지의 헤더사이즈에 추가됩니다.따라서 payload에 남아 있는 공간이 줄어듭니다.
「 」를 참조해 주세요.
레퍼런스
- ^ a b Fuhrmann, Thomas; Pengfei Di; Kendy Kutzner; Curt Cramer (June 2006). "Pushing Chord into the Underlay: Scalable Routing for Hybrid MANETs" (PDF). System Architecture Group, Technical University of Karlsruhe (TH), Germany. Retrieved 15 April 2010.
{{cite journal}}:Cite 저널 요구 사항journal=(도움말) - ^ Fuhrmann, Thomas (May 2005). "A Self-organizing Routing Scheme for Random Networks". NETWORKING 2005 (PDF). Lecture Notes in Computer Science. Vol. 3462/2005. Springer Berlin / Heidelberg. pp. 1366–1370. doi:10.1007/11422778_116. Retrieved 15 April 2010.
- ^ Castro, Marcel C.; Andreas J. Kassler; Carla-Fabiana Chiasserini (March 2010). "Peer-to-Peer Overlay in Mobile Ad-Hoc Networks". Handbook of Peer-to-Peer Networking. Springer Verlag. pp. 1045–1080. doi:10.1007/978-0-387-09751-0_37. ISBN 978-0-387-09750-3.
- ^ Zahn, Thomas; Greg O'Shea; Antony Rowstron (2009). "An empirical study of flooding in mesh networks" (PDF). SIGMETRICS Perform. Eval. Rev. ACM. 37 (2): 57–58. doi:10.1145/1639562.1639584. Retrieved 16 April 2010.
- ^ Cramer, Curt & Fuhrmann, Thomas (31 January 2005). "Self-stabilizing ring networks on connected graphs" (PDF). Retrieved 26 April 2010.
{{cite journal}}:Cite 저널 요구 사항journal=(도움말) - ^ Kendy Kutzner & Thomas Fuhrmann (March 2007). "Using Linearization for Global Consistency in SSR" (PDF). Proceedings of the 4th Int. IEEE Workshop on Hot Topics in P2P Systems. Retrieved 20 April 2010.
