2015年12月17日 星期四

Cickd 註解

今天要來記錄一下clickd的語法
因為太難了...要做個紀錄
以下是我們可以看到clickd中的code
#!/bin/sh 

# Copyright (c) 2006, Roberto Riggio
#
# All rights reserved.
# 
# Redistribution and use in source and binary forms, with or without 
# modification, are permitted provided that the following conditions    
# are met:
# 
#   - Redistributions of source code must retain the above copyright 
#     notice, this list of conditions and the following disclaimer.
#   - Redistributions in binary form must reproduce the above copyright 
#     notice, this list of conditions and the following disclaimer in 
#     the documentation and/or other materials provided with the 
#     distribution.
#   - Neither the name of the CREATE-NET nor the names of its 
#     contributors may be used to endorse or promote products derived 
#     from this software without specific prior written permission.
# 
# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
# "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
# LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
# A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
# CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
# EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
# PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
# PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
# LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
# NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
# SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

PATH=/usr/local/sbin:/usr/local/bin:/sbin:/bin:/usr/sbin:/usr/bin:./
DAEMON=click => 可執行檔
HELPER=click_config =>由click_config產生腳本
NAME=clickd

MODE="11g"
CHANNEL="2412"
DEV="moni0"

PROFILE="bulk"
LS="fcfs"
METRIC="wcett" => 有hop-count與wcett,這是route機制
RC="minstrel" => 有static與minstrel,這是Rate Control機制

CLICK_FILE=/var/run/$NAME.click
PID_FILE=/var/run/$NAME.pid
LOG_FILE=/var/log/$NAME.log 

test -x "$(which $DAEMON)" || exit 0
test -x "$(which $HELPER)" || exit 0

case "$1" in
  start)

 echo "Starting $NAME"

 if which wlanconfig > /dev/null 2>&1; then  => > /dev/null 2>&1表示說不Print在螢幕上
  PHY="wifi0"
  WLANCONFIG=$(which wlanconfig)
  [ ! -f "$WLANCONFIG" ] && {
   echo "Couldn't find wlanconfig";
   exit 1; 
  }
  $WLANCONFIG $DEV destroy 2> /dev/null
  $WLANCONFIG $DEV create wlandev $PHY wlanmode monitor > /dev/null 2>&1 || {
   echo "Couldn't create monitor device on $PHY";
   exit 1; 
  }
  echo '803' >  /proc/sys/net/$DEV/dev_type
  /sbin/iwpriv $DEV mode $MODE
 elif which iw > /dev/null 2>&1; then
  PHY="phy0"
  IW=$(which iw)
  [ ! -f "$IW" ] && {
   echo "Couldn't find iw";
   exit 1; 
  }
  $IW dev $DEV del > /dev/null 2>&1
  $IW phy $PHY interface add $DEV type monitor > /dev/null 2>&1 || {
   echo "Couldn't create monitor device on $PHY";
   exit 1; 
  }
 else
  echo "Couldn't find neither iw or wlanconfig";
  exit 1
 fi

 /sbin/iwconfig $DEV channel ${CHANNEL}M
 /sbin/ifconfig $DEV mtu 1900
 /sbin/ifconfig $DEV txqueuelen 5
 /sbin/ifconfig $DEV up
 /sbin/modprobe tun > /dev/null 2>&1 =>載入Module (包製多NIC)

 # extract the bottom three octects to use as IP =>查網卡卡號,可直接設SUFFIX成0.0.0.1
 MAC=$(/sbin/ifconfig $DEV 2>&1 | sed -n 's/^.*HWaddr \([0-9A-Za-z\-]*\).*/\1/p' | sed -e 's/\-/:/g' | cut -c1-17)
 HI=$(echo $MAC | sed -n 's/.*:.*:.*:\([0-9A-Za-z:]*\):.*:.*.*/\1/p')
 MID=$(echo $MAC | sed -n 's/.*:.*:.*:.*:\([0-9A-Za-z:]*\):.*.*/\1/p')
 LOW=$(echo $MAC | sed -n 's/.*:.*:.*:.*:.*:\([0-9A-Za-z:]*\).*/\1/p')
 SUFFIX=$((0x$HI)).$((0x$MID)).$((0x$LOW))

 XR_IFNAME="wing-mesh"
 XR_IP="6.$SUFFIX"
 XR_NM="255.0.0.0"
 XR_PERIOD="36000"
 XR_TAU="360000"

 $HELPER -p $PROFILE -r $RC -s $LS -l $METRIC -m $MODE -c $CHANNEL -n $DEV -a $MAC -d \
  | sed -e "s/__XR_IFNAME__/$XR_IFNAME/g" \
  | sed -e "s/__XR_IP__/$XR_IP/g" \
  | sed -e "s/__XR_NM__/$XR_NM/g" \
  | sed -e "s/__XR_PERIOD__/$XR_PERIOD/g" \
  | sed -e "s/__XR_TAU__/$XR_TAU/g" > $CLICK_FILE

 $DAEMON $CLICK_FILE > $LOG_FILE 2>&1 &

 sleep 2
 if ! pidof $DAEMON > /dev/null 2>&1; then
  echo "Unable to start click. Check log for more information."
  exit 1
 fi

 pidof $DAEMON > $PID_FILE

 ;;
  stop)
 echo "Stopping $NAME"

 if which wlanconfig > /dev/null 2>&1; then
  WLANCONFIG=$(which wlanconfig)
  [ ! -f "$WLANCONFIG" ] && {
   echo "Couldn't find wlanconfig";
   exit 1; 
  }
  $WLANCONFIG $DEV destroy > /dev/null 2>&1
 elif which iw > /dev/null 2>&1; then
  IW=$(which iw)
  [ ! -f "$IW" ] && {
   echo "Couldn't find iw";
   exit 1; 
  }
  $IW dev $DEV del > /dev/null 2>&1
 else
  exit 1
 fi
 [ -f $PID_FILE ] && {
  kill -9 $(cat $PID_FILE)
  [ -f $PID_FILE ] && rm $PID_FILE
 }
 [ -f $CLICK_FILE ] && rm $CLICK_FILE
 [ -f $LOG_FILE ] && rm $LOG_FILE
 ;;
  restart|force-reload)
 $0 stop
 sleep 1
 $0 start
 ;;
  *)
 echo "Usage: $NAME {start|stop|restart}" >&2
 exit 1
 ;;
esac

exit 0

2015年12月14日 星期一

無線隨意網路路由協定 (Routing Protocols for MANET)---DSR&AODV&TORA

無線隨意網路路由協定 (Routing Protocols for MANET)

8.1 無線隨意網路簡介 

8.2 主動式路由策略 

8.3 回應式路由策略 

8.4 主動式與回應式路由之比較

8.5 位置輔助路由 (location-based routing)策略 

8.6 結語

8.3 回應式路由策略

回應式(reactive)路由又稱On-demand routing (經需求路由)
主動式(路由表) vs. 回應式 ->8.4
回應式路由只尋找與維護有需要的路由
主動式路由則不論需要與否所有路由均須維護
回應式路由
優點: 省去一些不必要的路由維護
             適合偶發訊務(traffic)且一但發生則有大量的訊務;通訊只涉及少 數節點
缺點: 首次尋找耗時較多時間做路徑尋找造成封包延遲

回應式路由例子:
            動態來源路由 (Dynamic Source Routing , DSR)
            隨意依需求距離向量路由(Ad hoc On-demand Distance Vector, AODV) 
            臨時排序路由演算法 (Temporally Ordered Routing Algorithm, TORA)

回應式路由協定 –DSR(Dynamic Source Routing)

來源路由(Source routing)的基本精神:
1.封包的整個路由在來源地(source)已決定並置放在該節點的路由快取貯存區 (route cache) 
2.路由路徑資訊在封包標頭中;中繼節點按此資訊傳送封包。 

(要到的目地地無路由時) 啟動路由探索程序(Route discovery procedure):
1.由節點送出路由請求(route request, RREQ)封包來啟動
2.中繼節點收到RREQ時,若收過此封包則丟棄,不然就更新封包內部資訊後繼續廣播此RREQ封包 

當此封包到達目的地或中繼節點的route cache中有目的地節點資訊時則回覆路由回應(Route Reply, RREP)封包
RREP封包利用來源路由(Source routing)的策略回傳至來源節點

當來源節點收到RREP封包後可開始傳輸資料封包 


路由錯誤(Route Error, RERR)封包 : 
1.在DSR協定中,當連結失敗 (即傳送封包給下一站時遇到 失敗)則會產生”路由錯誤(RERR)”封包送回並告知來源地
2.沿途的節點會把該路由資訊清除 
3.當來源地收到REER封包後會重新啟動路由探索程序找替代路徑 

DSR使用來源路由(Source routing)及路由快取貯存區 (route cache)策略有下列優點
1.避免路由迴圈的產生(Routing Loop free) 
2.RREQ與RREP皆有整個路由路徑資訊
3.各節點可記錄路由 路徑資訊於route cache 
4.加速封包傳輸  RREQ與RREP皆有路由路徑資訊
5.可以有多條路由路徑
6.增加可靠性 (reliability)

回應式路由協定 –AODV(Ad-hoc On-Demand Distance Vector Routing)

AODV:使用如同DSR的路由探索使用RREQ與RREP 廣播機制找尋路徑。
採用不同機制維護路由資訊: 使用傳統路由表 (目地、下一、跳躍數) 。
AODV捨棄 source routing而依靠著中繼節點機動地建立的路由表項 目(route table entries)。 

AODV 使用:
             1.DSDV的目的地序列編號演算法
                           距離向量 
                           序列編號 
             2.使用計時器(timer)保持路由新鮮。

回應式 (on-demand)產生路由:不在路由路徑(selected path)上的節點不需保有路由資訊與交換路由資訊。

目標:降低廣播經常費用(overhead)與傳輸延遲

對每一目的地路由表有一列資訊包含 :
<destination addr , next-hop addr , destination sequence number , life tine>
• 目的地 
• 下一節點 
• 量度 (metric) : 跳躍數 (hop count) 
• 目的地序號 (Sequence number) 
• 路由表項目過期時間[計時器]:被用過即重置,否則expire掉
• 來源節點廣播RREQ封包
• 中繼節點轉送至目的地節點
• 目的地節點以<broadcastID,src-address>來分辨RREQ 封包;且當收到第一個RREQ 封包時回應RREP封包



AODV-Route Discovery:

1.先檢查table->Yes 送
2.No->Source送RREQ
RREQ封包內容:<source IP addr , source current sequence number , destination IP addr , destination seq number>
封包也有Broadcast ID number(src 給)
所以當有Broadcast ID and Source IP addr就可以知道具唯一性。


Reverse Route Entry:

當node收到RREQ,會在route table建立一個reverse route entry
格式:<Source IP Address , Source seq. number , number of hops to source node , IP address of node from which RREQ was received>
使用這個reverse route entry去送RREP回Source,本身entry也具Life Time

RREP格式: <IP addr of source and destination>

If RREP sent by destination:
<current seq# of destination , hop-count= 0 , life-tine>


If sent by intermediate node
<destination seq number , hop-count=its distance to destination , its value of the life-tine>

When a node received a RREP means it can set up a forward path entry
<IP addr of destination , IP addr of node from which tje entry arrived , hop-count to destination , life-time>

When a node received multiple RREP 
- only forwards the first RREP
- May forward another RREP if that has greater destination seq number or a smaller hop-count
- Rest are discarded


NOTE:若Table中可以找到一個entry且Seq, number >= RREQ那可以直接送去destination
否則繼續轉送RREQ並增加hop-count

回應式路由協定 –TORA(:Temporally Ordered Routing Algorithm)

TORA : 為一回應式路由協定

路由探索程序:算出多條通往目的地之路徑->目的地導向的有向無迴圈圖(directed acyclic graph, DAG*) 
NOTE:*無線隨意網 路可被視為無方向的圖 (undirected graph) 但TORA將此圖的邊(edges)給與方向:朝向目的地節點。 

每個節點會記錄至任一目的地的距離又稱高度值。 封包送往目的地依其高度值遞減如水往下流。 

如何建立高度值:使用詢問(query) /更新(update) 機制 
當一節點嘗試送出封包時會發出詢問(Query)封包, 該封包廣播至整個網路直到目的地或有至目的地路 由的節點。接著此點會回覆更新(update)封包(包含自 己高度資訊)。
當其它結點收到更新(update)封包後…會更新其高度 值。
各節點的高度值建立成功,形成一以目的地導向的DAG 
當連結失敗時,節點發現它的高度值為局部最小時;則 會將其高度值提高並發出更新(update)封包


8.4 主動式與回應式路由之比較



定義:流量密度/差異(traffic diversity) ?[流量分布的情 形]
低流量密度:集中於網路的少數節點
高流量密度:平均分散於網路的每個節點

回應式路由能適應不同流量密度(較適合低流量密度); 路徑非最佳,主動式路由則不受流量密度所影響。
高流量密度:路由負擔相當但:回應式路由->次佳路徑; 主動式路由->最佳路徑 
低流量密度:回應式路由->表現較佳 
->混合式路由(ZRP)

ZRP為一混合式路由協定。
一節點的區域(Zone):半徑(= hop counts) 內的所有節點。
邊緣節點(Border node):半徑上的所有節點。
Zone內使用連結狀態(link state)的主動式路由協定
 Zone間使用回應式路由協定的路由探索程序,其路由 請求封包只送往邊緣節點直到目的地的邊緣節點後回 覆。 


回應式路由 在路由探索(route discovery)造成較 長的延遲  不適用於對延遲 敏感(delay sensitive)和極短暫的應用(如問答) 





無線隨意網路路由協定 (Routing Protocols for MANET)----DSDV

無線隨意網路路由協定 (Routing Protocols for MANET)

8.1 無線隨意網路簡介 
8.2 主動式路由策略 
8.3 回應式路由策略 
8.4 主動式與回應式路由之比較
8.5 位置輔助路由 (location-based routing)策略 
8.6 結語

8.1 無線隨意網路

特性:

1.移動性(影響路由)
2.多點跳躍(multi-hop)
3.自我組態(self-configuration):node可以決定自己的參數[IP、路由表、位置]
4.可延伸性
5.安全性

無線隨意網路可隨時隨地可建立,無固定基礎架構,不需事先規劃與佈置;由自我(self)組態而 自動(auto)組織而成,成員可隨時加入或離開,通訊方法:單播(uni-cast),群播 (multi-cast)。
大型的隨意(Ad-Hoc)網路封包傳輸須中繼站轉播 -->多點跳躍 (multi-hop) --> 路由(routing) ) 
[不同於(802.11)中定義的IBSS屬 單點跳躍(one-hop)可直接溝通無中繼站轉播,故無路由問題]
而單播(uni-cast)]路由策略又分以下四種:
1.主動式 (proactive):事先建立 (又稱 table-driven) [8.2] 
2.回應式 (reactive):只尋找與維護有需要的路由 [8.3] 
3.位置輔助 (Location-based):利用節點的位置資訊 [8.4] 
4.混合式 (Hybrid):主動式及回應式的混合[8.5]

8.2 主動式(proactive)路由策略


(無線隨意網路)主動式路由可分為:
距離向量 (Distance Vector, DV)法:記錄自己到網路中所 有節點的距離及要往該節點路由的下一個節點(向量)。 節點間交換距離向量(DV)資訊,從而計算出自己到各節 點的最佳路由。

連結狀態 (Link State)法:記錄自己的連結狀態。節點間 交換連結狀態,從而計算出自己到各節點的最佳路由。

距離向量(DV)不適用於隨意網路 (ad-hoc networks) ,因為網路連結失敗造成 路由迴圈 (Routing Loops)產生跳躍數無限 (Count to Infinity),所以須要另找協定避免上述問題 ,
ex:目的地序列距離向量 (Destination-Sequenced Distance-Vector, DSDV) 協定


距離向量(Distance-Vector)路由協定


DSDV 協定:

DSDV是基於傳統Bellman-Ford路由選擇演算法所 改良而發展出來的,是一個以路由表(routing table)為基礎的通訊協定。 故每一個行動節點必須儲存一張路由表。須紀錄所有與該節點可能進行連結節點的距離。除給自己節點一個序列編號外,路由表內的每筆紀錄 同時還包含了一個目的地序列編號(destination sequence number):用來判斷路徑的新舊,以避免迴路的產生。

當網路拓樸變動比較不頻繁時,並不需要將路由表的所有資料進行交換。DSDV在每個節點內再加了一個table,用來記錄其路由表從上次交換至今所更改的部分。如果更改很多[或定期地],就進行全部資料的交 換,稱為全路由更新 (full routing update);如果 改變很少,就只針對改變部分交換,稱為累加式路由更新 (incremental routing update)

特性:

保有距離向量 (Distance Vector)的簡易性 
1.保證無迴路 ->路由表內新增一表項目 (Table Entry):目的地序列編號 (Destination Sequence Number) 
3.對拓樸改變反應迅速??? 
       ->當路由表有顯著改變;立即做路由廣告(route advertisement)。 
       ->但對未穩定路由(unstable routes)採等待策略;而不立即做路由廣告 (damping             fluctuations) 

路由選取:


更新資訊與路由表比較: 
1. 選取目的地的序號 (destination sequence number) 較高的路由 (保證使用來自目 的地的最新資訊) 
2. 當目的地的序號一樣時,選取量度(Metric) [=至目的地的hop counts]較佳的路由

路由表範例





新節點加入:



無迴路,無跳躍數無限:






降低路由表的波動:

對每一個特殊目的地,保留關於最先到來的路由最佳路由的到來的時間長度的資料。
依據這資料,决定延遲廣告 (可能將很快改變的) 路由 ,因而降低路由表的波動 (damping (抑制/降低) fluctuations )。通常為了減少相同序號編號之路由廣告的重播的數量 會延遲可能不穩定之路由廣告 。

何謂路由表的波動 :

路由表A中的項目D:[D, Q, 14, D-100] 
D 廣播序列編號 D-102  A 由P 收到D 的更新廣播:(D, 15, D-102) 
路由表A中的項目D:[D, P, 15, D-102] A 必須立即散播(propagate)此路由。
A 由Q收到D 的更新廣播:(D, 14, D-102)
路由表A中的項目D:[D, Q, 14, D-102] A 必須立即散播(propagate)此路由。
若不立即散播由P 收到的D 之更新廣播而延遲一 段時間,也許只要散播由Q 收到的D 之更新廣播 這可能發生在每一次在點D或其他節點做它的 更新廣播後導致在網路 上多餘的路由廣告,即 所謂波動 (fluctuations)。

如何緩和路由表波動:

於個別的表格上記錄上一次的決定時 間(Settling Time)與決定時間的平均。 [ 一個序列编号的第一個路由到來與最 佳的路由到來的時間間隔叫做決定時 間 (Settling Time)。]
當一個較新的特定序列编号的第一個 路由到來時,節點A仍然必須更新它的 路由表;但是它會等待一段時間才將 它散播。建議的等待時間約為平均決 定時間的兩倍。
在大型網路中像這的波動可以被降低 以避免多餘的廣告,因而節省了頻寬。

連結狀態(link-state)路由協定:


多重傳遞點(Multipoint Relay, MPR)概念:

1.單點跳躍 (1-hop):節點A 與節點B能直接相互通訊時,我 們稱A與B為(直接) [單點跳躍 (1-hop)]鄰居;又稱A到B或 B到A為單點跳躍(1-hop) 。[單向通訊vs.雙向通訊???]

2.覆蓋:節點B與節點A為一單點跳躍的關係;我們可以說 節點B為節點A (或節點A為節點B)所覆蓋。 

3.兩點跳躍 (2-hop):節點A與節點B及節點B與節點C皆為單 點跳躍(1-hop)的關係;但節點A與節點C無單點跳躍(1- hop)的關係時->節點A與節點C為一兩點跳躍(2-hop)的關係。又稱節點A為節點C[或節點C為節點A]的兩點跳躍(2- hop)鄰居

4.在節點A的單點跳躍 (1-hop)鄰居內選出一組特殊節 點;稱這些節點集合為”多重傳遞點” (Multipoint Relay, MPR)。
這些特殊節點要愈少愈好且滿足:節點A選出的MPR集合要能覆蓋節點A的所有兩點跳躍(2- hop)鄰居。PS:此最佳化問題為一NP-hard的問題