C++ STL 컨테이너의 성격

Study 2011.04.12 16:35 Posted by 몽백작

연속 메모리(continuous-memory) 컨테이너(배열 기반 컨테이너 - array-based container - 라고도 합니다)는 동적 할당된 하나 이상 - 대개 하나 - 의 메모리 단위(chunk)에다가 데이터 요소를 저장해 두는 컨테이너입니다. 각 메모리 단위는 하나 이상의 요소를 담고 있지요. 새 요소가 삽입되거나 이미 있던 요소가 지워지면(erase), 같은 메모리 단위에 있던 다른 요소들은 앞 혹은 뒤로 밀려나면서 새 요소가 삽입될 공간을 만들든지, 지워진 공간을 메웁니다. 이러한 "밀어내기"때문에 수행 성능의 발목을 잡을 수 있고, 예외 안전성(exception safety)에도 영향을 미칩니다. 표준 연속 메모리 컨테이너는 vector, string, deque입니다. 비표준 컨테이너인 rope 역시 연속 메모리 컨테이너입니다.

노드 기반(node-based) 컨테이너는 동적 할당된 하나의 메모리 단위에다가 하나의 요소만을 저장합니다. 컨테이너 요소를 삽입 혹은 삭제했을 때 노드의 포인터만이 영향을 받지, 노드의 내용은 그대로입니다. 따라서, 삭제나 삽입이 일어났다고 해도 나머지 요소들이 밀려난다든지 하는 일이 없습니다(해당 노드가 없어지고 생기고 하는 것이니까요). 연결 리스트를 나타내는 컨테이너, 즉 list나 slist가 노드 기반이고, 표준 연관 컨테이너 모두가 노드 기반입니다(이것들은 전형적으로 균형 트리(balanced tree)로 구현되어 있습니다). 비표준인 해쉬 컨테이너도 노드 기반으로 구현되어 있습니다.

출처: Scott Meyer 저, 곽용재 편역, "이펙티브 STL(Effective STL)", 정보문화사
저작자 표시 비영리 변경 금지
신고

'Study' 카테고리의 다른 글

C++ STL 컨테이너의 성격  (0) 2011.04.12
Review of "MP, NLP, DLP"  (0) 2009.10.14
Review of "Single Path Flooding Chain"  (0) 2009.10.14
Review of "Geocasting (multicast)"  (0) 2009.10.13
ns-2 tutorial 발표자료  (0) 2009.10.13
Review of "IGF"  (0) 2009.10.06

Review of "MP, NLP, DLP"

Study 2009.10.14 17:09 Posted by 몽백작

The Effect of Mobility-Induced Location Errors on Geographic Routing in Mobile Ad Hoc and Sensor Networks: Analysis and Improvement Using Mobility Prediction


논문: http://nile.cise.ufl.edu/wb/media/publication/2004/Son_the%20effect%20of%20mobility-induced%20location%20errors%20on%20geographic%20routing.pdf

Introduction

위치기반 라우팅에서는 노드의 이동 및 하드웨어, 거친 환경 문제 등으로 인해 위치 정보가 부정확할 수 있고, 성능에 영향을 미친다.
성능에 영향을 미치는 3가지 주요 요소
  • The freshness of location information
  • The speed of mobile nodes
  • The mobility patterns

발생하는 문제
  • The Lost Link problem (LLNK): 이웃 노드와 연결이 문제
  • The loop in packet delivery problem (LOOP): 부정확한 목적지 노드 위치 정보가 문제

Identified Problems (caused by mobility)

Lost Link (LLNK) Problem

  • Node mobility: 노드가 이동함. sender가 stale한 위치 정보를 가지고 있을 경우 발생
  • Asymmetry in a communication link: 환경 문제 혹은 노드 특성상 tx range가 다를 수 있음

LOOP Problem

목적지 노드가 원래 위치에서 이동하고 다른 노드가 원래 목적지 위치에서 가장 가까운 곳에 위치할 경우, 인접 노드들의 완벽한 위치정보가 없어 불필요하게 perimeter가 반복되는 현상

MP: Improvement on Geographic Routing

Neighbor Location Prediction (NLP)

각 노드들의 neighbor list 항목
  • last beacon time (LBT)
  • node speed in the direction of the x-axis (S_x)
  • node speed in the direction of the y-axis (S_y)

가장 최근의 2개의 정보 ((x_1,y_1,text{PBT}), (x_2,y_2,text{LBT}))를 통해 평균 속도를 예측
S_x=(x_2-x_1)/(text{LBT}-text{PBT})
S_y=(y_2-y_1)/(text{LBT}-text{PBT})

평균 속도로 가장 최근의 beacon 시간으로부터 현재 시간까지 이동했다고 가정했을 경우의 위치를 예측
x_{est}=x_2+S_xtimes(text{Current Time}-text{LBT})
y_{est}=t_2+S_ytimes(text{Current Time}-text{LBT})

Destination Location Prediction (DLP)

각 노드들이 neighbor list에서 목적지 노드가 있는지 먼저 확인하고 전달하도록 함.

신고

'Study' 카테고리의 다른 글

C++ STL 컨테이너의 성격  (0) 2011.04.12
Review of "MP, NLP, DLP"  (0) 2009.10.14
Review of "Single Path Flooding Chain"  (0) 2009.10.14
Review of "Geocasting (multicast)"  (0) 2009.10.13
ns-2 tutorial 발표자료  (0) 2009.10.13
Review of "IGF"  (0) 2009.10.06

Review of "Single Path Flooding Chain"

Study 2009.10.14 12:54 Posted by 몽백작

Single Path Flooding Chain Routing in Ad hoc Networks




DREAM은 end-to-end restricted flooding 인데 반해, single path flooding chain routing은 매 홉마다 restricted flooding을 수행한다. 가장 최신의 경로상의 이웃노드의 위치 및 속도 정보를 바탕으로 expected region을 결정한다. 따라서 DREAM에 비해 네트워크 대역폭 사용을 줄이고, 통신 복잡도를 낮추는 효과가 있다. 하지만 시뮬레이션 결과 delivery ratio는 DREAM에 비해 더 낮다.

신고

'Study' 카테고리의 다른 글

C++ STL 컨테이너의 성격  (0) 2011.04.12
Review of "MP, NLP, DLP"  (0) 2009.10.14
Review of "Single Path Flooding Chain"  (0) 2009.10.14
Review of "Geocasting (multicast)"  (0) 2009.10.13
ns-2 tutorial 발표자료  (0) 2009.10.13
Review of "IGF"  (0) 2009.10.06

Review of "Geocasting (multicast)"

Study 2009.10.13 11:48 Posted by 몽백작

Review of "Geocasting (multicast)"


Basic Idea

MANET에서 가장 간단한 멀티캐스트 방법은 flooding 이다. 하지만, cost가 매우 크다. (높은 충돌 확률, 네트워크 대역폭 낭비 등) 특정 지역에 속한 노드들이 멀티캐스트 그룹이 되는 geocast를 사용하고, 특정 지역까지 메시지를 전달하기 위한 노드들을 제한하기 위해 forwarding zone을 사용한다면 이런 문제를 최소화할 수 있다.



위와 같이 forwarding zone을 제한시켜서 중간 노드들의 전달 여부를 결정하게 하는 것이 기본 개념. forwarding zone이 커지면 커질수록 delivery ratio는 높아진다.

Determining Membership of the Forwarding Zone

Location-Based Multicast Scheme 1

  • 단순하게 S와 multicast region간에 사각형을 그리고 forwarding zone을 정의.
  • forwarding zone은 multicast region을 포함함.
  • 만약 S의 위치가 multicast region안에 있다면 multicast region=forwarding zone.

Location-Based Multicast Scheme 2

  • 3가지 사전 정보를 활용한다.
    • multicast region specification
    • multicast region의 중앙 좌표.
    • S의 좌표
  • 이웃 노드가 패킷을 수신하면, 패킷을 전송한 이전 노드와 MR(multicast region) 중앙의 거리와 자신과 MR 중앙의 거리를 비교한다.
  • 자신이 더 MR과 가까우면 전달하고, 그렇지 않으면 무시한다. 단, 이미 MR 내에 위치하면 전달한다.


Evaluation

Scheme1은 flooding에 비해서 오버헤드는 적으나, accuracy가 떨어짐.
Scheme2는 flooding만큼 accuracy가 나오면서 오버헤드를 줄임.

신고

'Study' 카테고리의 다른 글

Review of "MP, NLP, DLP"  (0) 2009.10.14
Review of "Single Path Flooding Chain"  (0) 2009.10.14
Review of "Geocasting (multicast)"  (0) 2009.10.13
ns-2 tutorial 발표자료  (0) 2009.10.13
Review of "IGF"  (0) 2009.10.06
Review of "DSR"  (0) 2009.10.06

ns-2 tutorial 발표자료

Study 2009.10.13 09:14 Posted by 몽백작



아무래도 ns-3는 지원되는 라이브러리에 한계가 있다. 물론 수많은 개발자들의 참여를 부탁 / 촉구하고 있지만, 어디 그게 쉬운 일인가;;;
내 능력이 된다면 참여해보고 싶기도 하지만, 개인적으로 천년만년 네트워크 연구할 것도 아니고, 석사만 졸업하면 되므로 그냥 ns-2를 하기로 했다. 이런 결심 덕분에 다시 세미나 자료를 새로 준비하였다. ;;;

첫 페이지에 나와 있는데로 Marc Greis의 튜토리얼과 홍릉과학출판사에서 나온 ns-2 네트워크 시뮬레이터의 이해를 참고하였다.
저작자 표시 비영리 동일 조건 변경 허락
신고

'Study' 카테고리의 다른 글

Review of "Single Path Flooding Chain"  (0) 2009.10.14
Review of "Geocasting (multicast)"  (0) 2009.10.13
ns-2 tutorial 발표자료  (0) 2009.10.13
Review of "IGF"  (0) 2009.10.06
Review of "DSR"  (0) 2009.10.06
Review of "GPSR"  (0) 2009.10.06

TAG NS-2

Review of "IGF"

Study 2009.10.06 15:45 Posted by 몽백작

Robust and timely communication over highly dynamic sensor networks


Introduction

Lazy binding
  • deferring mapping the system physics (e.g., the network topologies) into the volatile states (e.g., the route state), required by a certain operation, to the last possible moment allowed by the operations
  • 가능한 상태 바인딩을 늦춰서, 네트워크 토폴로지의 실시간 변화를 잘 처리할 수 있게 한다.

IGF
  • Implicit Geographic Forwarding
  • combining lazy-binding and location-address semantics


The motivation for lazy-binding


고정 네트워크에서는 네트워크가 생성될 때 네트워크 상태를 바인딩했고, proactive 라우팅(DSDV, GPSR)에서는 주기적인 네트워크 관리를 통해 계속해서 네트워크 상태를 바인딩했으며, on-demand 라우팅(AODV, DSR)에서는 데이터 전송의 요구가 있을 때에만 네트워크 상태를 바인딩했음.

이 논문에서는 실제 네트워크 토폴로지가 라우팅 상태에 매핑되는 시간라우팅 상태가 패킷 전달에 사용되는 시간의 차이가 상태 비일치와 라우팅 실패의 주요 원인으로 봄.

IGF는 패킷 전달 동작을 수행할 때 위치정보를 바탕으로 실시간으로 라우팅하므로 라우팅 상태가 필요가 없음 (stateless)

목표
  • 상태를 proactively 하게 관리하기 위한 통신 오버헤드를 없애버림
  • 토폴로지 변화를 실시간으로 감지


IGF Protocol design

System model and assumptions

  • 네트워크: GPS나 위치추적기법 등을 통해 위치를 파악할 수 있는 센서노드들로 이루어진 high-end 센서 네트워크
  • location-address semantic
  • 패킷 크기가 크다.
    • Hidden / exposed terminal 문제를 해결하기 위한 RTS-CTS handshaking
    • 아니면, small packet delivery

IGF details


  • ORTS: Open RTS의 약자로 source, destination의 위치(주소)를 broadcast
  • CTS-WAIT: candidate nodes 들만 T_{text{ctsunder{ }wait}} 만큼 기다린다. T_{text{ctsunder{ }wait}} 는 각각의 위치에 따라 다르며, 목적지와의 거리가 가까우면 가까울수록 짧다. candidate nodes 가 아닌 노드들은 NAV를 설정하고 통신하지 않는다.
  • CTS: T_{text{ctsunder{ }wait}}가 가장 짧은 노드가 CTS를 응답한다. 이를 엿들은 다른 후보 노드들은 NAV를 설정하고 통신하지 않는다. 이를 엿듣지 못해서 (uni-directional link 때문에) 발생하는 이후의 CTS들은 source에 의해서 무시된다.
  • DATA: source가 데이터 패킷을 전송
  • ACK: 데이터 패킷을 성공적으로 수신시 source에게 ACK 전송

More on forwarding candidates

Source-destination 에서 ±30도 내에 위치한 노드가 candidate nodes
candidate nodes 끼리 CTS 경쟁

Optimizations for sparse networks

만약에 candidate nodes가 없다면 history-based forwarding area shift
forwarding area를 돌리면서 void area를 피한다.

Design issues

Radio irregularity

symmetric radio range를 가정했지만, asymmetric link 에서도 잘 동작한다.
  • ORTS-CTS-DATA-ACK 를 통한 symmetric 통신 보장
  • 중복된 CTS에 대해서는 sender가 무시
즉, 원하는 데이터 패킷 전달은 symmetric link 에서만 전송.

Localization error impact

최대 50% 무선 영역 에러가 발생해도 100% delivery ratio

Energy implications

overhearing으로 인한 에너지 소비 증가. 하지만 negligible

Alternative MAC implementation

다양한 MAC에 적용할 수 있다.

신고

'Study' 카테고리의 다른 글

Review of "Geocasting (multicast)"  (0) 2009.10.13
ns-2 tutorial 발표자료  (0) 2009.10.13
Review of "IGF"  (0) 2009.10.06
Review of "DSR"  (0) 2009.10.06
Review of "GPSR"  (0) 2009.10.06
ns-3 tutorial로 세미나 시작  (1) 2009.10.04

Review of "DSR"

Study 2009.10.06 00:30 Posted by 몽백작

Dynamic Source Routing Protocol for Multi-Hop Wireless Ad Hoc Networks


Assumption

  1. ad hoc network 내에 있는 다른 노드들과 통신하기를 원하는 모든 노드들은 프로토콜에 전적으로 참여한다.
  2. 네트워크의 최소 반경은 작을 것. 그래도 1hop보다는 클 것.
  3. 노드들의 이동 속도는 보통. flooding 밖에 전송 방법이 없을 정도로 노드들이 심하게 움직이는 상황은 제외.
  4. overhearing (promiscuous mode) 사용. CPU 처리 오버헤드가 네트워크 오버헤드보다 작다는 가정. 물론 이것 마저도 부담된다면 주기적으로 promiscuous mode를 on/off switching.
  5. 링크가 항상 bidirectional 하지 않다. uni-directional 한 asymmetric link도 지원한다.
  6. 하나의 IP 주소를 사용한다. (e.g., home address of Mobile IP)


DSR Protocol Description

Overview and Important Properties of the Protocol

  • Route Discovery: source S가 경로를 모르는 destination D로 패킷을 보내기 위한 source route를 얻는 과정.
  • Route Maintenance: S와 D 사이에 경로가 끊어졌을 때 D를 알고 있는 다른 경로를 사용하거나 다시 Route Discovery를 수행하는 등 경로를 유지하기 위한 과정

위 두가지 동작은 모두 on demand. DSR은 데이터를 전송하기 전에 경로를 형성 / 유지하기 위한 어떠한 종류의 주기적인 패킷을 사용하지 않는다.
하나의 Route Discovery에 대한 응답을 통해 노드는 어떤 목적지에 대한 다양한 경로들을 학습하고, cache한다.
DSR은 unidirectional link들도 필요에 따라 지원한다. 따라서 connectivity를 더욱 높일 수 있다.
다양한 종류의 무선 네트워크 간의 internetworking을 지원한다.

Basic DSR Route Discovery

패킷의 헤더에 경로상의 중간 노드들의 주소들을 차례로 명시.
Route Cache에 경로를 보관하고 있다면 이를 그대로 source routing에 사용하지만, 경로를 보관하고 있지 않다면 Route Discovery를 통해 새로운 경로를 찾는다.
여기서 source는 initiator, destination은 target 이라 표현한다.


위 그림은 노드 A가 노드 E로 패킷을 전송하기 위한 Route Discovery 과정. A는 transmission range 내의 모든 노드들에게 ROUTE REQUEST 메시지를 broadcast한다. 각 ROUTE REQUEST 메시지에는 initiator, target, (initiator에 의해 결정되는) request id를 담고 있다. ROUTE REQUEST가 전달될 때는 매 홉마다 전달하는 노드의 주소를 기록한다. 따라서 initiator에 의해 최초로 전송될 때의 route record는 empty list.

ROUTE REQUEST를 target이 수신한 경우, ROUTE REPLY로 응답한다. ROUTE REPLY에는 ROUTE REQUEST에 차곡차곡 쌓인 route record를 복사한다. 이러한 ROUTE REPLY가 initiator에 도착하면, initiator의 route cache를 route record로 갱신한다. target이 아닌 노드가 ROUTE REQUEST를 수신했는데, 이전에 본 ROUTE REQUEST 메시지이거나 (같은 initiator id, request id), route record에 자신의 주소가 존재한다면 그 REQUEST는 무시한다 (loop 방지). 그렇지 않으면 route record에 자신의 주소를 추가한 후, broadcast로 전달한다.

노드 E가 노드 A로 ROUTE REPLY를 보내는 과정은 다시 E→A로 경로를 찾는 과정과 같다. 노드 E에서 자신의 route cache를 검색하여 A를 향하는 경로가 있으면 그 경로를 패킷의 헤더에 적어서 보낸다. route cache에 A에 대한 경로가 존재하지 않는다면, 다시 Route Discovery 과정을 수행하여 A에 대한 경로를 찾는다. Route Discovery의 무한 반복을 피하기 위해서 ROUTE REPLY를 아예 ROUTE REQUEST에 실어 (piggyback) 보낸다.

※ 이 부분이 이해가 안갔었는데, 이렇게 생각해보면 이해가 간다. A는 ROUTE REQUEST를 보낸 상태고, E로부터 ROUTE REPLY를 수신하기 전까지는 E에 대한 경로를 알 수 없다. E가 ROUTE REPLY를 보내기 위해 A로 ROUTE REQUEST를 보내면 역시 A로 부터의 ROUTE REPLY를 기다리게 될 것이고, A는 여전히 E에 대한 경로를 모르기 때문에 또 ROUTE REQUEST를 보내야 하는, Route Discovery가 무한히 recursion되는 현상이 발생한다. 이를 방지하기 위해서 DSR에서는 ROUTE REPLY를 ROUTE REQUEST에 실어 보내는 것이다.

[Postel 1981b]에서는 TCP SYN 같은 작은 패킷을 ROUTE REQUEST에 piggyback 해서 보내는 제안을 했다.

TCP에서 연결을 설정(establish)하기 위해서는 보통 three way handshaking (SYN, SYN+ACK, ACK)이 일어난다. 따라서, A가 ROUTE REQUEST를 전송할 때 TCP SYN를 같이 보내고, E가 ROUTE REPLY를 응답할 때 TCP SYN+ACK를 같이 보내고, A가 E에 대한 source routing을 최초로 수행할 때 TCP ACK를 전송하면서 실질적인 데이터를 전송하면 오버헤드도 적고 빠른 시간안에 연결을 맺을 수 있다.

노드 E에서 ROUTE REPLY를 보낼 때 ROUTE REQUEST에 있는 route record를 사용하여 그대로 역방향으로 ROUTE REPLY를 보낼 수도 있다. IEEE 802.11 같은 bi-directional exchange를 바탕으로 하는 MAC에서 동작할 때에는 이런 것이 가능하다. 하지만 uni-directional link를 지원하지 않는다. 무선 환경에서는 uni-directional link가 더 좋은 경로이거나 유일한 경로일 수도 있다.

아래 그림을 보면 이해가 쉬울 듯. 첫번째 그림은 bi-directional link이고, 두번째 그림은 uni-directional link이다. IEEE 802.11, MACA 같은 MAC에서는 RTS-CTS를 통한 사전 패킷 전송을 통해 양쪽이 서로 패킷을 주고 받는 것을 기본으로 가정한다. 하지만 무선 환경에서는 장애물, 간섭, 지향성 안테나 등의 방사 패턴에 따라 uni-directional link (두번째 그림)가 발생할 수 있다.



Route Discovery를 시작할 때, 전송하려는 실제 패킷은 Send Buffer라는 곳에 임시 저장한다. Send Buffer에는 source route 정보가 없어서 당장 전송이 불가능한 패킷들이 저장되어 있고, 각각 버퍼에 처음 들어온 timestamp가 찍혀있다. 일정 시간 후에도 route 정보를 알아낼 수 없다면 버퍼 overflow를 막기 위해 패킷을 버린다. 패킷들이 Send Buffer에 남아있는 동안에는 새로운 Route Discovery를 계속해서 수행한다. 하지만 현재 닿을 수 없는 목적지이거나 알 수 없는 목적지 일 수도 있기 때문에 무조건 계속해서 수행하지 않고 일정 rate 정도로 제한해서 수행한다.

Send Buffer에 있는 각각의 패킷들이 같은 target을 향할 경우, 각각의 패킷들이 ROUTE REQUEST를 전송한다면 매우 비생산적이다. 이런 Route Discoveries의 오버헤드를 줄이기 위해서, 같은 목적지를 향하는 새로운 Route Discoveries들의 rate를 제한하기 위한 exponential back-off를 사용한다. 이 limited rate 보다 더 자주 데이터 패킷을 전송하려고 해도 Send Buffer에 저장해 놓고 ROUTE REPLY가 들어올 때까지 기다린다. 그리고 최소의 허용가능한 Route Discoveries의 interval 동안 기다린 후, Route Discovery를 시도한다. (ARP Request와 유사)

Basic DSR Route Maintenance


패킷을 발신 / 전달하는 각 노드들은 그 패킷들이 source route에 따라 next hop이 수신하였는지 확인해야 할 의무가 있다. 따라서 확인 응답을 수신하기 전까지는 일정 횟수만큼 재전송을 시도한다. Figure 2에서는 A는 B로부터, B는 C로부터, C는 D로부터, D는 E로부터 패킷 수신여부를 확인해야 한다. 이러한 확인은 IEEE 802.11 MAC에서의 link-level ACK, 또는 C가 D에게 전달하는 것을 B가 엿듣는 (overhear) 과정을 통해 전송여부를 확인하는 passive ack 등을 통해 DSR에 별다른 구현 없이도 이뤄질 수 있다. 이런 메카니즘들이 가능하지 않을 때에도, DSR 헤더에 비트를 set 함으로써 software acknowledge를 할 수도 있지만, uni-directional link 에서는 multi-hop을 통해서 ack가 전송될 수도 있다. C-D 처럼 연결이 끊어지면 source A에게 링크가 깨졌음을 알리고, A는 route cache에서 그 경로를 삭제하고 상위계층 프로토콜에게 그 사실을 알린다. 만약 route cache에 그 목적지로 향하는 다른 경로가 있거나 다른 패킷들을 overhear하여 다른 경로를 알고 있다면 경로를 복구할 수 있다. 그렇지 않으면 다시 Route Discovery를 수행한다.


Additional Route Discovery Features

Caching Overheard Routing Information

모든 노드들은 데이터 패킷의 source route 정보, ROUTE REQUEST / REPLY 에 누적된 route record 정보를 엿듣고, 자신의 route cache를 갱신한다. (물론 엿듣기 위해서 MAC address를 broadcast address로 하거나, promiscuous mode를 사용하거나 방법에 제한은 없음)


하지만, 이런 overhearing이 uni-directional link에서는 문제가 된다. A-B-C-D-E 의 순방향 경로를 생각해보자. Route Discovery 과정에서 C는 B로부터 ROUTE REQUEST 패킷을 수신한다. 이를 보고 C는 B에게 패킷을 보낼 수 있다고 생각한다. 하지만 B-C 경로가 uni-directional link 라면, C는 B에게 패킷을 전송할 수 없다. 따라서 bi-directional link를 가정하는 MAC을 사용하지 않는다면 이러한 overhearing을 사용하면 안된다. 마찬가지로 V-W-X-Y-Z 의 순방향 경로에서 X에서 Y로 전송되는 ROUTE REQUEST 패킷을 C가 수신한다면 C는 uni-directional link 여부를 생각하지 않고, C-X 링크 뿐만 아니라, V~Z까지 모든 노드들로 패킷을 전송할 수 있다고 믿게 된다.

Replying to ROUTE REQUESTs using Cached Routes

ROUTE REQUEST를 수신한 노드들은 자신이 target이 아니라면 자신의 route cache에 해당 target이 있는지 확인한다. 해당 target이 있으면 ROUTE REQUEST에 누적된 route record에 자신이 가지고 있는 route를 덧붙여 ROUTE REPLY를 전송한다.

단, 위와 같은 경우에 단순하게 concatenation 하면 중복되는 구간이 발생한다. 따라서 F는 A-B-C-D-E라는 경로로 ROUTE REPLY를 응답할 수 있지만, F는 그 경로에 속하지 않는다. DSR에서는 F가 ROUTE REPLY를 보내는 것을 금지한다.
  1. This limitation increases the probability that the resulting route is valid, since F in this case should have received a ROUTE ERROR if the route had previously stopped working.
  2. This limitation means that a ROUTE ERROR traversing the route is very likely to pass through any node that sent the ROUTE REPLY for the route (including F), which helps to ensure that stale data is removed from caches (such as at F) in a timely manner.

※ 사실 잘 이해가 가지 않는다. 하지만 만약 C-D-E 경로가 동작중이라면 C의 cache에 그 경로가 존재할테고, C가 바로 ROUTE REPLY를 보내면 된다. 만약 cache에 없어도 F의 입장에서는 자신이 ROUTE REPLY를 응답하지 않아도, D가 C의 tx range에 존재하기 때문에 D가 응답할 것으로 생각해도 된다. 즉, 오지랖 넓게 관여하지 않아도 정상적으로 동작할 것 같다. ;;;;


Preventing ROUTE REPLY Storms

A가 Route Discovery를 하는데, 인접한 B, C, D, E, F가 경로를 모두 알고 있다면 동시에 ROUTE REPLY를 전송하여 패킷 충돌의 위험이 있다. 게다가 최적의 경로도 찾기 힘들다. 따라서 DSR에서는 다음과 같이 해당 목적지에 대한 홉 수에 차등적으로 ROUTE REPLY를 지연시키도록 하여 ROUTE REPLY storms를 방지한다.
d=H times (h - 1 + r)
d는 ROUTE REPLY를 지연시키는 시간, H는 작은 지연 시간, h는 목적지까지의 홉 수, r은 랜덤 넘버.
즉, 홉 수에 따라 가까운 노드가 빨리 응답하도록 하는 메카니즘.


ROUTE REQUEST Hop Limits

ROUTE REQUEST를 보낼 때 hop limit을 정해서 보내고, 매 홉마다 hop limit을 하나씩 줄인다. 이를 통해 nonpropagating ROUTE REQUEST를 사용할 수도 있고, expanding ring search 를 사용할 수도 있다.
expanding ring search는 hop limit을 지수적으로 증가시키면서 Route Discovery를 해 나가는 방법으로 불필요한 ROUTE REQUEST의 범람을 막을 수 있지만, 지연이 발생하는 단점이 있다.


Additional Route Maintenance Features

Packet Salvaging

ROUTE ERROR를 전송한 후, 그 패킷을 버리기 보다는 살려보려고 (salvaging) 노력함. ROUTE ERROR 전송 후, route cache에 대체 경로를 찾고 대체 경로가 있으면 그 경로로 전송(패킷 헤더의 source route 부분의 뒷부분(suffix)를 새로운 경로로 바꿈). 전송할 때는 salvaged packet 임을 mark 하고 전송하여 여러번 salvage 하는 현상을 방지함.

Automatic Route Shortening


A가 B에게 전달한 메시지가 C가 들을 수 있음 → B는 불필요한 경로
C가 메시지를 전달한 후, 경로를 줄여서 (B를 빼고) gratuitous ROUTE REPLY 를 A에게 전송.
A는 gratuitous ROUTE REPLY를 바탕으로 다음 패킷부터는 줄어든 경로로 source routing

Increased Spreading of ROUTE ERROR Messages

ROUTE ERROR를 source가 수신하였을 경우, ROUTE REQUEST에 그 ROUTE ERROR를 piggyback해서 전송하여 ROUTE REQUEST를 수신하는 노드들 중 그 경로를 사용하는 노드들은 해당 route cache를 삭제하도록 함.

Caching Negative Information

ROUTE ERROR를 수신한 노드는 해당 경로가 끊어졌다는 사실을 (그냥 지우지 않고) 일정 시간동안 caching.
링크가 빈번에게 연결되고 끊어지는 현상이 반복될때, route cache oscillation 현상을 방지함



References
  1. Wikipedia
  2. RFC4728
  3. http://www.cs.jhu.edu/~cs647/dsr.pdf


신고

'Study' 카테고리의 다른 글

ns-2 tutorial 발표자료  (0) 2009.10.13
Review of "IGF"  (0) 2009.10.06
Review of "DSR"  (0) 2009.10.06
Review of "GPSR"  (0) 2009.10.06
ns-3 tutorial로 세미나 시작  (1) 2009.10.04
석사과정 6개월.. 네트워크 시뮬레이션 분야에 손을 대다.  (0) 2009.10.04

Review of "GPSR"

Study 2009.10.06 00:18 Posted by 몽백작

GPSR: Greedy Perimeter Stateless Routing for Wireless Networks


원문: http://www.cse.psu.edu/~gcao/teach/598-03/locaion_harvard.pdf

Introduction

기존 라우팅 프로토콜(Distance Vector, Link State)의 scalability에 영향을 끼치는 두가지 요인
  • The rate of change of the topology
  • The number of routers in the routing domain

Hierarchy
  • Autonomous System 내에서는 intra-domain routing, AS간에는 inter-domain routing
  • 인터넷처럼 잘 정의되고 토폴로지가 잘 변하지 않는 네트워크에서는 잘 동작하지만, ad-hoc에서는 어울리지 않음.

Caching
  • DSR, AODV, ZRP 등
  • ad-hoc 에서 scaling에 대한 전략으로 나타남.
  • on-demand fashion
  • routing message에 대한 부담을 줄여줌
    • It avoids pushing topological information where the forwarding load does not require it.
    • It often reduces the number of hops between the router that has the needed topological information and the router requires it
      • 상태가 변한 링크와 더 가까운 노드가 이미 링크정보를 캐시했을 수 있음.
      • 즉, 문제가 있는 링크까지 가지 않아도 그 링크의 상태를 알수 있으므로 라우터간 홉 수를 줄여줌.

Proposal: the aggressive use of geography to achieve scalability in wireless routing protocol

Scalability의 증가: 노드 수 증가, 노드 이동 증가
Scalability의 측정
  • routing protocol message cost: How many packets does a RT send?
  • application packet delivery success rate
  • per-node state: How much storage does a RT require at each node?

geographic routing: nearly stateless
  • Single hop 내의 이웃 노드들의 정보들만 관리
  • Source, destination, 그리고 이웃 노드들의 위치정보가 있다면 correct forwarding decisions를 내리기에 충분함.

Assumptions
  • 위치를 파악할 수 있는 장치: GPS or ultrasonic
  • bidirectional radio reachability
  • 평면
  • 주소와 위치를 매핑시켜주는 위치 등록 / 찾기 서비스가 있음 (out of scope)


Algorithms and Examples

Greedy Forwarding


패킷에 목적지의 위치를 명시함. 목적지와 가장 가까운 이웃 노드에게로 전달.

이웃노드의 위치 파악은 간단한 beaconing algorithm을 통해서
  • 2개의 4byte 부동소수점 타입
  • synchronization을 피하기 위해서 beacon의 전송을 beacon간 인터벌 B의 50%로 jitter (?)
    • To avoid synchronization of neighbors' beacons. as observed by Floyd and Jacobson [8], we jitter each beacon's transmission by 50% of the interval B between beacons, such that the mean inter-beacon transmission interval is B, uniformly distributed in [0.5B, 1.5B]
  • beacon이 일정 시간(T=4.5B, 최대 jittered beacon 간격의 3배) 동안 오지 않으면 노드 fail 또는 범위 밖으로 사라졌다고 가정하고, 테이블에서 삭제
  • 이웃만 알면 되므로 전체 네트워크 노드 밀도를 몰라도 믿을 수 있음. 이웃 파악에 대한 오버헤드는 negligible
  • 이웃에 대한 정보의 정확도는 beaconing interval에 달려있음. beaconing interval은 네트워크의 이동성 정도와 노드들의 무선 범위에 의존적.
  • beaconing 에 대한 비용을 줄이기 위해 모든 data packets를 전달할 때 전달하는 노드의 위치 정보를 piggyback. 그리고 promiscuous mode 활용.
  • reactive beacon



temporarily farther in geometric distance from the destination
  • 오직 이웃정보에만 의지해서 발생하는 약점
  • Perimeter에 의해 해결

The Right-Hand Rule: Perimeters


right-hand rule: 삼각형 내부에서 봤을 때 오른손 방향 (시계반대방향) 으로 전달.
perimeter: right-hand rule을 통해 연결되는 엣지들
  • Fig. 3에서 보면 x->w->v->D->z->y->x 로 연결되는 엣지들

이렇게 하면 목적지에 가장 가까운 perimeter를 찾을 수 있다.
그러나 no-crossing heuristic을 요구한다. 항상 찾는 것은 아니다. (잘 이해가 안감)

Planarized Graphs

no-crossing heuristic이 경험적으로 대부분의 경로를 찾아낸다 해도 static, unchanging 네트워크 토폴로지에서 영원히 못찾는 경우가 있다.

planar: a graph in which no two edges cross

To be continued...

신고

ns-3 tutorial로 세미나 시작

Study 2009.10.04 22:12 Posted by 몽백작

사실 가장 먼저 ns-3를 접하기로는 공식 사이트에서 제공하는 튜토리얼만큼 좋은 자료가 없다고 생각한다. 우선 튜토리얼로 ns-3 세미나 첫번째 시간 자료를 만들어보았다.


그나저나 세상 참 편하네...ㅋㅋ 구글 문서도구로 이런 식으로 게시할 수 있다니...
저작자 표시 비영리 변경 금지
신고

TAG ns-3

사실 석사과정 들어올 때부터 손을 대야 했을까?
나름 애써서 쓴 논문이 리젝되고 나서 곰곰히 생각해보았다.

"무엇이 문제일까?"

나름 리뷰어들이 꼼꼼하게 지적해준 부분은 다음과 같다.

1. lack of evaluations

내가 생각해낸 프로토콜이 "왜 다른 프로토콜보다 좋은지" 잘 표현해내지 못했다는 것이다. 사실 네트워크 분야에서 ns-2 같은 시뮬레이터는 부가적인 부분이라고 생각했다. 따라서, 실제 테스트베드에 구현하고 테스트 하면 더 좋을 줄 알았다. 물론 맞는 말이긴 하다. 하지만, 다른 프로토콜들과의 비교가 어렵다. 또한 환경을 다양하게 하여 테스트하기도 힘들다. 최근에는 많은 이들이 ns-2 같은 네트워크 시뮬레이터만으로 논문 쓰는 시대는 끝났다고 이야기하지만, 시뮬레이터로 어느 정도 다른 프로토콜과의 비교 과정을 통해서 "성능상 더 우수하다"라는 점을 보여줘야 하고, 시뮬레이터로 다양한 시나리오로 테스트하여 "어느 환경에서든 잘 동작한다"라는 점을 보여줘야 할 것이다. 실제 테스트베드는 그 다음에 해보면 될 것이다.


2. non new research area

연구 주제가 전혀 새롭지 못하다는 것이다. 이 부분은 석사과정이라면, 그리고 UST 같은 선배가 극도로 부족한 환경에서는 어쩔 수 없는 문제일 것이다. 그 누구의 귀뜸도 없이 내 스스로 "state of the art"를 파악해야 하니까, 어떻게 보면 석사과정 두어달만에 제대로된 사전 지식없이 논문을 쓰기 시작했으니 당연한 결과가 아닐까 싶다. 이 부분은 어쩔 수 없다. 리젝당한 후 한동안은 "아이고 내 팔자야"라며 신세한탄을 하며 심적으로 방황을 했지만, 이제는 긍정적으로 생각하기로 했다. 아무도 "state of the art"를 알려주지 않는다면, 내가 "state of the art"를 파악해 나가면 된다.


어찌 되었든, 위의 2가지 이유로 인해 야심차게 (?) 쓴 첫번째 논문이 리젝 당했으므로, 두번 다시 이런 일이 발생하지 않도록 최선을 다해야 겠다. 두번째 이유야 내가 열심히 논문연구하면 되는 문제고, 첫번째 이유는 시뮬레이터를 사용하면 해결될 것이다. 어떻게 보면 네트워크 분야에 관심있는 석사생이라면 입학하자마자 시뮬레이션 툴 사용법을 익혀야 하지 않았을까? 만약, 그렇다면 어떤 툴로 시작해봐야 할까?

우선은 동기들끼리 ns-3 세미나를 시작해보기로 했다. 사실 가장 많이 쓰는 네트워크 시뮬레이터는 ns-2이고, 무선 네트워크라면 GloMoSim 같은 특화된 네트워크 시뮬레이터도 있지만, ns-3가 처음 배우는 입장에서는 유리하다고 생각된다. 내 생각에 ns-2 유저들이 ns-3로 옮겨오지 못하는 이유는 그동안 ns-2로 작업을 해왔기 때문이고, 수많은 라이브러리들이 아직 ns-3 용으로 만들어지지 않았기 때문일 것이다. 나는 어차피 처음이다. 겁날 것이 무엇이겠는가.
저작자 표시 비영리 동일 조건 변경 허락
신고



 

티스토리 툴바