애드 혹 네트워크에서 트래픽을 라우팅하는 방법 및 시스템 document_id A220623042426

이동 사용자들 사이의 무선 통신은 장치 및 기술이 개발됨에 따라 점점 더 대중적이 되었다. 기반구조 롤 아웃(infrastructure roll out)은 전기통신 시스템 및 데이터 네트워크 시스템 둘 모두에서 확장하고 있다. 또한, 요즘 전기통신 시스템은 점점 더 패킷 교환 네트워크를 사용하고 있고, 추세가 이러한 패킷 기반 라우팅 방식을 행해 진행되고 있다. 이 시스템은 데이터 네트워크 기반 시스템에서 다년간 사용되었으므로, 이 용도를 위한 많은 표준화된 라우팅 프로토콜이 존재한다. 그러나, 이것들은 예를 들어, 소위 애드 혹 네트워크와 같이 네트워크 토포그래피(network topography)를 고속으로 변화시키는 것이 준비되지 않았다. 무선 애드 혹 네트워크는 통상적인 유선 네트워크 기반구조와 동일한 고정 특성을 갖는 것이 아니라, 제어가 집중되지 않고, 종종 자발적인 방식으로 생성되는 것을 특징으로 한다. 이것은 분산된 개념을 통하여 제어를 유지한다. 노드는 표준 고정 네트워크 구조에 비하여 제어되지 않는 방식으로 접속되거나 분리될 수 있고, 상기 노드는 고속으로 왕복할 수 있는데, 이는 네트워크 토폴로지를 극적으로 변화시키도록 한다. 일부 경우에, 이와 같은 애드-혹 네트워크는 기반구조 컴포넌트로서 사용자/클라이언트 장치 자신에 의해 형성된다. 그 후, 이러한 컴포넌트는 사용자가 네트워크 셀 주위, 상기 셀 내 및 상기 셀로부터 이동하므로, 기반구조가 이에 따라 이동한다는 의미에서 실제로 이동국이다. 이것은 기반구조를 형성하는 직접적인 방법이지만, 라우팅 프로토콜 상에 매우 높은 요구를 설정한다. 무선 기반구조 환경에서의 다른 문제점은 네트워크 흐름의 성능 및 효율을 저하시키는 무선에 특정된 문제에 기인한다. 무선 환경에서 물체의 이동 또는 기반구조 노드의 이동으로 인하여 페이딩 문제가 존재할 수 있고, 범위 내의 다른 무선 소스로부터의 간섭으로 인한 문제점이 존재할 수 있다. 이러한 종류의 네트워크 토포그래프는 군사 환경에서 사용되었지만, 지금은 또한 민간인 에어리어로 이동하고 있다. 무선 시스템은 이제 예를 들어, 주거 지역 또는 상업 지역에서의 무선 광대역 액세스를 위한 기반구조 에어리어를 고속으로 구성하는데 사용된다. 이것은 예를 들어, 비상 사태, 재해 지역, 또는 군사용 전쟁터에서 일시적 기반구조 구성을 위하여 사용될 수 있다. 이것은 또한 예를 들어, 콘서트, 회의, 미팅, 또는 계절적 관광 지역과 같은 이벤트 동안 일시적 액세스 커버리지 에어리어(coverage area)를 구성하는데 사용될 수 있다. 이러한 종류의 에어리어에서, 1년 내내 커버리지를 가지는 것이 필요로 되지는 않고, 단지 특정 기간 동안에만 커버리지를 갖는 것이 필요로 된다. 요즘, 몇 개의 인터넷 서비스 제공자(ISP)는 고정된 무선 기반 구조 시스템을 사용하여 공항, 식당, 커피 숍, 및 호텔과 같은 공공 또는 반-공공 지역에서 무선 액세스를 제공한다. 이러한 시스템을 종종 소위 핫 스폿(hotspot)이라 칭한다. 액세스하고자 하는 사용자로부터의 요구가 커버리지 및 대역폭에 비하여 증가함에 따라, 무선 커버리지 또는 대역폭의 에어리어를 확장하는 하나의 방법은 더 많은 기반구조 컴포넌트를 설치하는 것이지만, 통상적인 고정된 무선 컴포넌트로 이것을 행하는 것은 고가이므로, 무선 라우터를 사용하여 네트워크를 구성하는 개념이 출현하였다. 이 경우에, 설치 절차가 간소화되도록 하기 위하여 애드 혹 라우팅 프로토콜이 사용될 수 있다. 애드 혹 네트워크를 논의할 때, 기본적으로 두 종류의 네트워크 용도가 존재하는데, 제 1 용도는 외부 네트워크, 예를 들어, 인터넷으로의 액세스를 제공하는 임의의 외부 게이트웨이 없이 근거리 네트워크를 구성하는 것이다. 이 방식은 재해 지역에 관한 시설 또는 전쟁터에서의 군사 시설에서 발견될 수 있다. 다른 그리고 더 통상적인 용도는 하나 또는 몇 개의 게이트웨이가 예를 들어, IP 기반 네트워크(사설 또는 공중, 예를 들어, 인터넷)로의 외부 접속을 네트워크에 제공하는 경우이다. 이와 같은 네트워크 구성에서, 데이터 패킷은 예를 들어, 데이터 트래픽 유형, 혼잡도, 라우팅 비용에 따라서 상이한 루트(route)를 취하고/하거나, 상이한 게이트웨이를 사용할 수 있다. 패킷 기반 라우팅 방식은 종종 계층화된 모델을 중심으로 한 통신 네트워크 시스템, 예를 들어, OSI 기준 모델(개방 시스템 상호접속)을 구성한다. 통신 소프트웨어 및 하드웨어는 여러 개의 더 작은 서브 유닛으로 분할되고, 계층적인 방식으로 동작한다. 정보 및 통신 제어 파라미터는 송신 및 수신 단 사이의 동일한 층들 사이에서 그리고 상하로 국부적으로 통과된다. 각각의 이와 같은 층은 통신 명령에서 상이한 태스크에 대한 책임이 있다. 라우팅과 관련하여, OSI 기준 모델에 따른 제 1의 세 층이 가장 중요하다. 층 1은 데이터 비트의 물리적인 송신에 대한 책임이 있다, 물리적인 수단의 예는 예를 들어, 무선 근거리 네트워크(WLAN)에서의 무선 링크 또는 이더넷 기반 네트워크일 수 있다. 층 2는 종종 링크 층 또는 MAC 층이라 칭해지며, 데이터의 청크, 에러 검출, 및 네트워크 자원 조정을 송신하는 것에 대한 책임이 있다. 층 3은 종종 네트워크 층이라 칭해지며, 네트워크 내의 임의의 쌍의 노드들 간의 통신을 인에이블하는 것에 대한 책임이 있다. 이 층은 예를 들어, 라우팅 계산 및 혼잡도 제어를 책임진다. 이 목적을 위하여, 네트워크의 유형에 따라 상이한 라우팅 프로토콜이 개발되었다. IP-기반 네트워크에서의 패킷 라우팅 프로토콜은 일반적으로 거리 벡터 또는 링크 상태 정보를 사용한 라우팅 알고리즘을 토대로 하여, 네트워크에서 소스 및 목적지 노드의 각 쌍에 대한 루트를 탐색하여 유지하도록 한다. 원칙적으로, 거리 벡터 라우팅 알고리즘에서, 각 라우터는 모든 호스트에 대한 거리를 자신의 이웃 라우터에 브로드캐스팅하며, 그 정보를 수신하는 각 라우터는 네트워크 내의 호스트 각각에 대한 최단 루트를 계산한다. 링크 상태 라우팅 알고리즘에서, 각각의 라우터는 자신의 인접 네트워크 링크 각각의 상태 정보를 자신의 이웃 라우터에 브로드캐스팅하고, 그 정보를 수신하는 각각의 라우터는 링크 상태 정보로부터 네트워크의 전체 픽처(picture)의 데이터베이스를 유지하고, 데이터베이스에서 링크 비용을 토대로 하여 각 호스트로의 최대 루트를 계산한다. 이러한 라우팅 알고리즘은 비교적 고정된 네트워크를 위해 디자인되므로, 새로운 라우팅 알고리즘이 토폴리지가 자주 변화하는 애드 혹 네트워크를 위해 디자인되어야 한다. 애드 혹 네트워크를 위한 기존 라우팅 프로토콜의 기본적으로 두 개의 카테고리가 존재한다. 이것은 "프로액티브(proactive)"(테이블 구동된) 및 "리액티브(reactive)"(온-디멘드(on-demand)) 라우팅 프로토콜이다. 이러한 프로토콜의 조합을 갖는 프로토콜이 또한 가능하다. 프로액티브 라우팅 프로토콜은 애드 혹 네트워크에서 모든 호스트로의 루트를 자주 그리고 주기적으로 계산하므로, 패킷이 특정 목적지 호스트로 송신될 필요가 있을 때, 루트가 항상 이용 가능하다. 그 결과는 모든 노드에서 라우팅 테이블에 유지된다. 각 호스트로의 루트를 유지하기 위하여, 제어 메시지는 라우터들 사이에서 교환되어, 네트워크 구성 및 링크 상태의 변화를 통지한다. 거리 벡터 및 링크 상태 라우팅 프로토콜 둘 모두는 프로액티브 프로토콜로서 분류된다. 제어 메시지가 오버헤드를 초래하고, 네트워크 효율을 감소시킬 수 있다는 것이 주의되어야 한다. 또한, 프로액티브 프로토콜은 네트워크 토폴로지가 자주 변화할 때, 유효한 루트를 유지하는데 있어서 어려움을 가질 수 있다. DSDV(목적지-순서화된 거리 벡터 라우팅)는 라우팅 정보 프로토콜(RIP)을 애드 혹 네트워크에 적응시키는, 거리 벡터 알고리즘을 토대로 한 프로액티브 라우팅 프로토콜이다. 각 노드는 상기 노드가 모든 도달 가능한 목적지 호스트 각각으로의 홉 노드(hop node) 및 홉 카운트(hop count)를 저장하는 라우팅 테이블을 유지한다. DSDV에서, 각 노드는 주기적으로, 또는 자신이 네트워크 토폴로지의 변화를 검출할 때, 라우팅 갱신을 브로드캐스팅하거나 멀티캐스팅한다. 최종 갱신 이후의 변화에 관한 정보만을 갱신하는 증분 갱신이 또한 제어 트래픽을 감소시키기 위하여 사용된다. 리액티브 프로토콜은 송신될 데이터 패킷이 존재할 때, 루트를 탐색/갱신하기 위하여 제어 메시지 교환만을 수행한다. 소스 노드는 데이터 패킷을 송신하고자 할 때, 제어 프로토콜을 개시하여, 자신의 이웃 노드로 루트 요청 메시지를 송신함으로써 루트를 탐색한다. 이 원리에 의하여, 리액티브 방법은 송신될 패킷이 존재하지 않을 때, 네트워크 자원이 낭비되지 않는다는 점에서 양호하다. 그러나, 루트가 제 1 시간 동안 형성되어야 할 때, 패킷을 송신하는 것은 시간이 많이 든다. AODV 및 DSR은 대표적인 리액티브 프로토콜이다. AODV(애드혹 온-디멘드 거리 벡터 라우팅) 프로토콜은 DSDV 알고리즘을 사용하며, 온-디멘트를 토대로 하여, 즉, 단지 소스 노드가 데이터 패킷을 송신하고자 하는 경우에만, 루트를 생성하고/갱신한다. 이로 인해, 루트를 탐색/갱신하기 위해 필요로 되는 브로드캐스트의 수가 감소된다. AODV에서, 각 노드는 검출된 이웃 노드의 리스트를 유지한다. 이웃 리스트는 다음의 세 가지 방법, a) 패킷이 이웃 노드로부터 수신되는 경우, b) 이웃 노드로부터 로컬 어드버타이즈먼트(local advertisement), 즉, 헬로 메시지(hello message)를 수신하는 것, 또는 c) 링크 층으로부터의 피드백 중 하나에서 갱신된다. 헬로 메시지는 각 노드로부터 이의 이웃하는 노드로 주기적으로 브로드캐스팅되어, 자신의 존재에 관해 이웃하는 노드에 통지한다. AODV에서, 각 노드는 상기 노드가 통신하거나 다른 노드를 대신하여 데이터 패킷을 전달하는 모든 목적지에 대한 라우팅 테이블을 유지한다. 각각의 목적지에서, IP 어드레스, 목적지 노드에 대한 시퀀스 번호, 목적지로의 홉 카운트, 목적지로의 다음 홉 노드, 및 루트에 대한 수명과 같은 목적지에 관한 정보를 포함하는 라우팅 테이블 내에 엔트리(entry)가 존재한다. 노드가 목적지 노드와 통신하고자 할 때, 즉, 데이터 패킷을 목적지로 송신하고자 할 때, 소스 노드는 루트 발견 메커니즘을 개시하는데, 여기서 소스 노드는 루트 요청(RREQ)을 모든 검출된 이웃 노드로 브로드캐스팅한다. 이웃 노드가 RREQ 메시지를 수신하고 자신의 라우팅 테이블에서 그 목적지로의 충분히 새로운 루트에 대한 엔트리를 가지는 경우, 상기 이웃 노드는 소스 노드에 루트 응답(RREP) 메시지를 역송신한다. 이웃 노드가 그 목적지에 대한 루트 엔트리를 탐색하지 못하는 경우, 상기 이웃 노드는 RREQ 메시지를 자신의 검출된 이웃 노드로 전달한다. 목적지 노드가 RREQ를 수신하는 경우, 상기 목적지 노드는 소스 노드에 RREQ 메시지를 리턴시킨다. RREQ 패킷을 전달하는 프로세스에서, 각각의 중간 노드는 브로드캐스트 RREQ의 제 1 카피(copy)가 수신되고, 반대 루트가 설정되는 이웃 노드의 IP 어드레스를 기록한다. 이후에 수신된 동일한 RREQ 메시지의 카피는 모두 폐기된다. 중간 노드는 목적지에 대한 자신의 라우팅 테이블로 엔트리를 부가하는데, 여기서 RREP가 수신되는 이웃 노드는 그 목적지로의 다음 홉 노드로서 기록된다. 목적지 시퀀스 번호 및 루트의 수명이 RREP로부터 복사되고, 엔트리에 기록된다. RREP 메시지가 최종적으로 소스 노드로 리턴될 때, 소스로부터 목적지로의 순방향 루트가 형성된다. 루트가 상기 루트 상의 인시던트 링크(incident link)의 고장에 의하여 이용 불가능하다는 것을 노드가 검출할 때, 노드는 그 루트를 사용하는 모든 이웃 노드에 루트 에러(RERR) 메시지를 송신한다. RERR 메시지는 소스 노드에 도달할 때까지, 이들의 이웃 노드 등으로 송신된다. 그 후, 소스 노드는 데이터 패킷 송신을 중단하는 것 또는 새로운 루트 발견을 개시하는 것 중 하나를 결정할 수 있다. DSR(동적 소스 라우팅) 프로토콜은 소스 노드가 온-디멘트를 토대로 하여 루트에 따라 노드의 완전한 시퀀스를 결정하고, 패킷 헤더 내의 중간 노드의 리스트를 설정하여, 루트에 대한 노드의 시퀀스를 나타내는 소스 라우팅 메커니즘을 사용한다. 이 방법으로, 각 패킷은 패킷 라우팅을 위한 오버헤드를 지녀야 한다. 그러나, 중간 노드는 루트에 관한 임의의 정보를 유지할 필요가 없고, 데이터 패킷을 전달할 때, 루트를 습득할 수 있다. DSR에서, 각 노드는 자신이 습득하였던 루트를 저장한다(캐싱(cashing)한다). 소스 노드가 목적지 노드에 데이터 패킷을 송신하고자 하고, 그 목적지에 대한 엔트리를 캐시에서 갖지 않는 경우, 상기 소스 노드는 자신의 링크-층 상에서 RREQ 메시지를 브로드캐스팅함으로써 루트 발견 메커니즘을 개시한다. RREQ 메시지를 수신하는 각 노드 자신의 IP 어드레스를 RREQ에 부가하고 나서, 이를 또한 전달한다. 이 프로세스는 목적지로의 루트가 탐색되거나 다른 노드가 목적지로의 루트를 제공할 수 있을 때까지 행해진다. 그 후, 목적지 로드로의 네트워크 홉의 시퀀스를 포함하는 루트 응답(RREP) 메시지가 소스 로드로 리턴된다. DSR에서, 링크 고장이 노드에서 검출되는 경우(즉, 패킷이 최대 횟수로 재송신되었을 경우), 그 노드는 그 링크를 자신의 루트 캐시로부터 제거하고, 확인이 최종적으로 수신되었던 이후에 그 링크를 사용하였던 노드들 각각에 루트 에러(RERR) 메시지를 송신한다. 그러한 노드는 그 링크를 포함하는 루트를 제거해야 한다. 그 후, 소스 노드로부터의 데이터 패킷의 재송신은 송신 제어 프로토콜(TCP)과 같은 상위층에 의해 핸들링된다. 링크 만료 시간 및 노드의 트래픽 로드를 사용하는 애드 혹 라우팅 프로토콜에서, 링크 만료 시간은 두 개의 특정 노드의 거리가 무선 유효 거리보다 짧거나 무선 유효 거리와 동일하게 유지되는 시간 간격으로서 규정된다. 이 라우팅 프로토콜에서, 메트릭(metric)은 각 링크의 비용으로서 사용되고, 노드는 이와 같은 루트의 수명이 더 길어지므로, 이것이 제어 트래픽으로 인한 오버헤드 및 루트 갱신 빈도를 감소시키고, 데이터 패킷 송신의 전체 처리량을 증가시키는 것이 예상되는, 최소 비용 루트를 탐색하려고 시도한다. 이 프로토콜에서, 노드의 트래픽 로드는 소정의 시간 기간 동안 노드의 비지 레이트(busy rate)로 표현된다. 노드의 최소 트래픽 로드를 갖는 루트가 루트 선택 알고리즘에서 선택된다. 상기 알고리즘이 네트워크에서 로드 밸런싱을 더 양호하게 하는데, 즉, 상기 알고리즘이 네트워크에서 특정 노드로 트래픽이 집중되지 않도록 한다는 것이 예상된다. 통상적인 애드 혹 네트워크 라우팅 방법이 이동 무선 통신 네트워크에서 사용되는 경우, 일부 문제점이 발생할 수 있다. 하나의 문제점은 사용자가 이동국이기 때문에, 사용자들이 돌아다녀서, 시스템이 예를 들어, 페이딩, 전파-손실, 및 섀도잉(shadowing)으로 인한 무선 품질의 변화를 겪게 된다는 것이다. 이것은 또한, 기반구조 시스템이 이동 요소로 이루어진 경우, 예를 들어, 클라이언트 장비가 기반구조의 부분인 경우에 그러하다. 고정된 무선 기반구조 구성요소를 갖는 시스템에서도, 예를 들어, 무선 링크 품질의 변화를 초래하는 두 개의 기반구조 구성요소 사이의 신호 경로를 일시적으로 차단하는 차량 또는 다른 물체로 인하여, 이와 같은 문제점이 발생할 수 있다. 이러한 유형의 문제점에 대한 주요 관심은 이것들이 라우팅 경로 변화 또는 라우팅 테이블의 갱신 빈도보다 빠르게 변화할 때 발생한다. 라우팅 정보의 갱신 빈도를 증가시킴으로써 상술된 문제점을 해결하고자 시도하는 경우, 라우팅 정보의 갱신이 매체에서 가능한 데이터 송신 볼륨의 상당한 부분을 차지하기 때문에, 어느 포인트에서 송신 효율을 저하시키기 시작할 것이다. 미국 특허 출원 제 2003/0120809호에서, 사용 주파수 대역, 이 경우에, 2.4GHz ISM 대역에서 인증되지 않은 신호에 대해 청취함으로써 네트워크에서 간섭 소스를 검출하는 시스템에 설명되어 있다. 이 문서에서, 네트워크 층 상에서 발생하는 문제점이 주로 포커싱되고, 무선 층 상에서 발생하는 문제점은 더 적게 포커싱된다. 상기 문서는 단지 현재 상태에 대한 적응만을 공개하며, 링크 상태의 가능한 다음 특성에 대한 관련이 이루어지지 않는다. 상기 시스템은 이에 따라 패킷 루트를 적응시키도록 시도하여, 간섭의 영향을 감소시킨다. 상기 해결책은 단지 간섭을 검출하는 것만을 포커싱하고 있고, 상기 문제점은 간섭 소스를 향한 무선 커버리지를 감소시키기 위하여 간섭자(interferer)에 가까운 노드의 안테나 위치 및 방향을 조정함으로써 해결된다. 미국 특허 제 5,537,394호에서, 고정된 네트워크 해결책을 위하여 상태 예측 기능이 도입된다. 상기 해결책은 상태 모니터링 기능으로부터 정보의 큰 통계적인 계산을 수반한다. 상기 통계적인 계산은 전체 네트워크 시스템의 내포된 의미의 해석을 위해서 행해지며, 애드 혹 네트워크에 대해 용이하게 조정될 수 없고, 특히 무선 애드 혹 네트워크에 대해 조정될 수 없다.