//#include <ip

Size: px

Start display at page:

Download "//#include <ip"

抵欧阳
6 years ago
Views:

1 NS-2 中 AODV 的 RREQ 與 RREP 訊息傳送過程程榮祥. 郭俐君簡介移動性 Ad hoc network (MANET) 是由一群配備無線設備而且可以任意移動的主機所構成的網路由於在 MANET 中並沒有無集中式的網路管理設備 ( 例如基地台等 ) 且由於受限於電波傳輸範圍的限制, 因此若欲將一個封包 (Packet) 由來源端主機 (Source) 傳送到目的端主機 (Destination) 時, 可能必須藉由鄰近的行動式主機負責幫忙轉送, 但由於在 MANET 中的主機可以隨意移動, 因此為了確保應用程式的資料能在 MANET 上順利傳送,MANET 的路由協定 (Routing Protocol) 在設計時, 就必須考量到網路拓樸隨時會改變的情形 Ad hoc On Demand Distance Vector (AODV) protocol 是一個專門為 Ad hoc 移動網路所設計的通訊協定 AODV 是一個無迴路, 由來源主機開始啟動, 且能擴展到大量移動節點的一種通訊協定 ; 和 DSDV 不同的地方在於,AODV 是一種在需要時才啟用的路由協定, 意即當有來源端主機想傳送資料時, 才開始建立由來源主機至目的主機的路由 (Route) AODV 的路由方式 AODV 透過發出請求 (Route Request,RREQ) 與回覆 (Route Reply,RREP) 的機制來取得路由首先, 若來源點主機想傳輸到目的主機的路由資訊未建立, 則 AODV 的來源主機會廣播 RREQ 訊息至整個網路, 收到此訊息的相鄰節點會更新收到來源點發出的資訊, 並建立向後端來源點的路由表 RREQ 中的訊息如下 : <source_addr,source_sequence#, broadcast_id, dest_addr, dest_sequence_#, hop_cnt> 這些訊息分別為 : 來源主機的 IP 位址來源端的序列號碼廣播 ID 目的主機的 IP 位址目的端的序列號碼, 最後是經過的 hop 數 RREP 則會包含如下的訊息 : <source_addr, dest_addr, dest_sequence _#, hop_cnt, lifetime> 這些訊息分別為 : 來源主機的 IP 位址目的主機的 IP 位址, 目的端的序列號碼, 經過的 hop 數以及連線的有效存活時間有關 AODV 的運作過程, 簡單地介紹如下 : (1) 每個 Node 藉由 Hello_message 來確保相鄰的節點 (2) Source node 想傳資料時, 啟動 Route discovery 程序找出其它 Node 位置藉由廣播 RREQ 給它相鄰的 Node, 接到此封包的 Node 再轉送給相鄰的 Node, 直到此封包到達目的主機為止 (3) 其中 <source_addr, broadcast_id> 唯一決定一個 RREQ 收到重覆 RREQ, 則丟棄或不理會後來抵達者 (4) 轉送 RREQ 過程中, 每個 node 會自動設定反向的路徑 (reverse path), 而收到 RREQ 的中間節點 (intermediate node) 會查看是從哪一個相鄰節點送來此封包, 接著把相鄰節點的 IP 紀錄在自己的路由表中 ( 建立反向路徑 ), 再把 hop_count 加 1, 轉送給下一個 Node (5) 在傳送過程中, 若某一個節點已含有到達目的的路徑資訊, 則會直接回覆 RREP 給 Source node ADOV 程式說明在這個例子中, 我們希望能觀察 AODV 的 RREQ 訊息在 NS-2 中是如何被 Source Node 送出, 網路上的 Node 在收到這個 RREQ 訊息時, 又是如何去產生 RREP 訊息的首先我們先來看在 aodv.h 這個檔案 ( 相關函式如下 ) 中, 有關傳送及接收處理函式的定義在 NS-2 中,AODV 封包的傳送及接收分別是由 sendrequest() 以及 recvrequest() 這兩個函式來處理 ; 至於 AODV 的 Reply 訊息, 則分別由 sendreply() 以及 recvreply() 這兩個函式來負責 // Packet TX Routines forward(aodv_rt_entry *rt, Packet *p, double delay); sendhello(); sendrequest(nsaddr_t dst);

2 sendreply(nsaddr_t ipdst, u_int32_t hop_count, nsaddr_t rpdst, u_int32_t rpseq, u_int32_t lifetime, double timestamp); senderror(packet *p, bool jitter = true); // Packet RX Routines recvaodv(packet *p); recvhello(packet *p); recvrequest(packet *p); recvreply(packet *p); recverror(packet *p); 接下來我們來看 aodv.cc 的部份, 為了簡單起見, 我們只列出 sendrequest() sendreply() recvrequest() 以及 recvreply() 這四個函式 ; 另外這些函式在執行的過程中, 會將傳送及接收訊息的時間以及 Hop count Latency 的資訊記錄在一個名為 out.aodv 的 trace 檔中 #include <aodv/aodv.h> #include <aodv/aodv_packet.h> #include <random.h> #include <cmu-trace.h> #include <stdio.h> #define max(a,b) ( (a) > (b)? (a) : (b) ) #define CURRENT_TIME Scheduler::instance().clock() //#define DEBUG //#define ERROR #define DUMP // 這是我自行增加的一個參數, 這個參數是一個開關, 在進行除錯的過程中時, 可用來開啟 // 或是關閉除錯訊息 AODV::recvRequest(Packet *p) { struct hdr_ip *ih = HDR_IP(p); struct hdr_aodv_request *rq = HDR_AODV_REQUEST(p); aodv_rt_entry *rt; if(rq->rq_src == index) { // 檢查這個 request 是不是自己送出來的 fprintf(stderr, "%s: got my own REQUEST\n", FUNCTION ); Packet::free(p); // 若是的話就將此封包丟棄 return; if (id_lookup(rq->rq_src, rq->rq_bcast_id)) { fprintf(stderr, "%s: discarding request\n", FUNCTION ); Packet::free(p); return; // Cache the broadcast ID id_insert(rq->rq_src, rq->rq_bcast_id); // We are either going to forward the REQUEST or generate a // REPLY. Before we do anything, we make sure that the REVERSE // route is in the route table. aodv_rt_entry *rt0; // rt0 is the reverse route rt0 = rtable.rt_lookup(rq->rq_src); if(rt0 == 0) { // if not in the route table // create an entry for the reverse route. rt0 = rtable.rt_add(rq->rq_src);

3 rt0->rt_expire = max(rt0->rt_expire, (CURRENT_TIME + REV_ROUTE_LIFE)); if ( (rq->rq_src_seqno > rt0->rt_seqno ) ((rq->rq_src_seqno == rt0->rt_seqno) && (rq->rq_hop_count < rt0->rt_hops)) ) { // If we have a fresher seq no. or lesser #hops for the // same seq no., update the rt entry. Else don't bother. rt_update(rt0, rq->rq_src_seqno, rq->rq_hop_count, ih->saddr(), max(rt0->rt_expire, (CURRENT_TIME + REV_ROUTE_LIFE)) ); if (rt0->rt_req_timeout > 0.0) { // Reset the soft state and // Set expiry time to CURRENT_TIME + ACTIVE_ROUTE_TIMEOUT // This is because route is used in the forward direction, // but only sources get benefited by this change rt0->rt_req_cnt = 0; rt0->rt_req_timeout = 0.0; rt0->rt_req_last_ttl = rq->rq_hop_count; rt0->rt_expire = CURRENT_TIME + ACTIVE_ROUTE_TIMEOUT; // Find out whether any buffered packet can benefit from the reverse route. // May need some change in the following code - Mahesh 09/11/99 assert (rt0->rt_flags == RTF_UP); Packet *buffered_pkt; while ((buffered_pkt = rqueue.deque(rt0->rt_dst))) { if (rt0&&(rt0->rt_flags == RTF_UP)) { assert(rt0->rt_hops!= INFINITY2); forward(rt0, buffered_pkt, NO_DELAY); // End for putting reverse route in rt table // We have taken care of the reverse route stuff. // Now see whether we can send a route reply. rt = rtable.rt_lookup(rq->rq_dst); // 若 Node 本身就是 Qequest 的 destination.. if(rq->rq_dst == index) { fprintf(stderr, "%d - %s: destination sending reply\n", index, FUNCTION ); #ifdef DUMP FILE *fp; if ((fp = fopen("out.aodv", "a"))!= NULL) { fprintf(fp, "%f %d -%s from %d\n", CURRENT_TIME, index, FUNCTION, rq->rq_src); fclose(fp); // 將收到 Request 的時間接收節點 ID Action 發送節點 ID 等訊息記錄到 out.aodv 這個檔案中 // Just to be safe, I use the max. Somebody may have incremented the dst seqno. seqno = max(seqno, rq->rq_dst_seqno)+1; if (seqno%2) seqno++; sendreply(rq->rq_src, // IP Destination 1, // Hop Count index, // Dest IP Address seqno, // Dest Sequence Num MY_ROUTE_TIMEOUT, // Lifetime rq->rq_timestamp); // timestamp Packet::free(p);

4 // 若 Node 本身並不是 destination, 但是有 fresh enough route else if (rt && (rt->rt_hops!= INFINITY2) && (rt->rt_seqno >= rq->rq_dst_seqno) ) { #ifdef DUMP FILE *fp; if ((fp = fopen("out.aodv", "a"))!= NULL) { fprintf(fp, "%f %d -%s from %d (I may have flash enough route)\n", CURRENT_TIME, index, FUNCTION, rq->rq_src); fclose(fp); // 將收到 Request 的時間接收節點 ID Action 發送節點 ID 等訊息記錄到 out.aodv 這個檔案 assert(rq->rq_dst == rt->rt_dst); sendreply(rq->rq_src, rt->rt_hops + 1, rq->rq_dst, rt->rt_seqno, (u_int32_t) (rt->rt_expire - CURRENT_TIME), rq->rq_timestamp); // Insert nexthops to RREQ source and RREQ destination in the // precursor lists of destination and source respectively rt->pc_insert(rt0->rt_nexthop); // nexthop to RREQ source rt0->pc_insert(rt->rt_nexthop); // nexthop to RREQ destination #ifdef RREQ_GRAT_RREP sendreply(rq->rq_dst, rq->rq_hop_count, rq->rq_src, rq->rq_src_seqno, (u_int32_t) (rt->rt_expire - CURRENT_TIME), rq->rq_timestamp); // TODO: send grat RREP to dst if G flag set in RREQ using rq->rq_src_seqno, rq->rq_hop_count // DONE: Included gratuitous replies to be sent as per IETF aodv draft specification. As of now, G flag // has not been dynamically used and is always set or reset in aodv-packet.h --- Anant Utgikar, // 09/16/02. Packet::free(p); // Can't reply. So forward the Route Request else { ih->saddr() = index; ih->daddr() = IP_BROADCAST; rq->rq_hop_count += 1; // Maximum sequence number seen en route if (rt) rq->rq_dst_seqno = max(rt->rt_seqno, rq->rq_dst_seqno); forward((aodv_rt_entry*) 0, p, DELAY); // 將這個封包繼續 forward 出去 AODV::recvReply(Packet *p) { struct hdr_ip *ih = HDR_IP(p); struct hdr_aodv_reply *rp = HDR_AODV_REPLY(p); aodv_rt_entry *rt; char suppress_reply = 0; double delay = 0.0; fprintf(stderr, "%d - %s: received a REPLY\n", index, FUNCTION ); #ifdef DUMP FILE *fp;

5 if ((fp = fopen("out.aodv", "a"))!= NULL) { fprintf(fp, "%f %d -%s from %d hop=%d latency=%f\n", CURRENT_TIME, index, FUNCTION, rp->rp_src, rp->rp_hop_count, (CURRENT_TIME - rp->rp_timestamp)); fclose(fp); // 將時間 Node ID 函式的功能 Source Node 的 ID Hop count 以及 Latency 等資料記錄在 out.aodv // 這個檔案中 /* * Got a reply. So reset the "soft state" maintained for * route requests in the request table. We don't really have * have a separate request table. It is just a part of the * routing table itself. */ // Note that rp_dst is the dest of the data packets, not the // the dest of the reply, which is the src of the data packets. rt = rtable.rt_lookup(rp->rp_dst); // If I don't have a rt entry to this host... adding if(rt == 0) { rt = rtable.rt_add(rp->rp_dst); // Add a forward route table entry... here I am following Perkins-Royer AODV paper almost literally - SRD // 5/99 if ( (rt->rt_seqno < rp->rp_dst_seqno) // newer route ((rt->rt_seqno == rp->rp_dst_seqno) && (rt->rt_hops > rp->rp_hop_count)) ) { // shorter or better route // Update the rt entry rt_update(rt, rp->rp_dst_seqno, rp->rp_hop_count, rp->rp_src, CURRENT_TIME + rp->rp_lifetime); // reset the soft state rt->rt_req_cnt = 0; rt->rt_req_timeout = 0.0; rt->rt_req_last_ttl = rp->rp_hop_count; if (ih->daddr() == index) { // If I am the original source // Update the route discovery latency statistics, rp->rp_timestamp is the time of request // origination rt->rt_disc_latency[(unsigned char)rt->hist_indx] = (CURRENT_TIME - rp->rp_timestamp) / (double) rp->rp_hop_count; // increment indx for next time rt->hist_indx = (rt->hist_indx + 1) % MAX_HISTORY; /* * Send all packets queued in the sendbuffer destined for * this destination. * XXX - observe the "second" use of p. */ Packet *buf_pkt; while((buf_pkt = rqueue.deque(rt->rt_dst))) { if(rt->rt_hops!= INFINITY2) { assert (rt->rt_flags == RTF_UP); // Delay them a little to help ARP. Otherwise ARP // may drop packets. -SRD 5/23/99 forward(rt, buf_pkt, delay); delay += ARP_DELAY; else {

6 suppress_reply = 1; /* If reply is for me, discard it. */ if(ih->daddr() == index suppress_reply) { Packet::free(p); else { /* Otherwise, forward the Route Reply. */ // Find the rt entry aodv_rt_entry *rt0 = rtable.rt_lookup(ih->daddr()); // If the rt is up, forward if(rt0 && (rt0->rt_hops!= INFINITY2)) { assert (rt0->rt_flags == RTF_UP); rp->rp_hop_count += 1; rp->rp_src = index; forward(rt0, p, NO_DELAY); // Insert the nexthop towards the RREQ source to // the precursor list of the RREQ destination rt->pc_insert(rt0->rt_nexthop); // nexthop to RREQ source else { fprintf(stderr, "%s: dropping Route Reply\n", FUNCTION ); drop(p, DROP_RTR_NO_ROUTE); AODV::sendRequest(nsaddr_t dst) { // Allocate a RREQ packet Packet *p = Packet::alloc(); struct hdr_cmn *ch = HDR_CMN(p); struct hdr_ip *ih = HDR_IP(p); struct hdr_aodv_request *rq = HDR_AODV_REQUEST(p); aodv_rt_entry *rt = rtable.rt_lookup(dst); assert(rt); /* * Rate limit sending of Route Requests. We are very conservative * about sending out route requests. */ if (rt->rt_flags == RTF_UP) { assert(rt->rt_hops!= INFINITY2); Packet::free((Packet *)p); return; if (rt->rt_req_timeout > CURRENT_TIME) { Packet::free((Packet *)p); return; // rt_req_cnt is the no. of times we did network-wide broadcast // RREQ_RETRIES is the maximum number we will allow before // going to a long timeout. if (rt->rt_req_cnt > RREQ_RETRIES) { rt->rt_req_timeout = CURRENT_TIME + MAX_RREQ_TIMEOUT; rt->rt_req_cnt = 0; Packet *buf_pkt; while ((buf_pkt = rqueue.deque(rt->rt_dst))) { drop(buf_pkt, DROP_RTR_NO_ROUTE); Packet::free((Packet *)p); return;

7 fprintf(stderr, "(%2d) - %2d sending Route Request, dst: %d\n", ++route_request, index, rt->rt_dst); #ifdef DUMP FILE *fp; if ((fp = fopen("out.aodv", "a"))!= NULL) { fprintf(fp, "%f %d -%s to %d\n", CURRENT_TIME, index, FUNCTION, rt->rt_dst); fclose(fp); // 將時間 Node ID 函式功能以及 Request 的 Destination 記錄至 out.aodv 這個檔案中 // Determine the TTL to be used this time. // Dynamic TTL evaluation - SRD rt->rt_req_last_ttl = max(rt->rt_req_last_ttl,rt->rt_last_hop_count); if (0 == rt->rt_req_last_ttl) { // first time query broadcast ih->ttl_ = TTL_START; else { // Expanding ring search. if (rt->rt_req_last_ttl < TTL_THRESHOLD) ih->ttl_ = rt->rt_req_last_ttl + TTL_INCREMENT; else { // network-wide broadcast ih->ttl_ = NETWORK_DIAMETER; rt->rt_req_cnt += 1; // remember the TTL used for the next time rt->rt_req_last_ttl = ih->ttl_; // PerHopTime is the roundtrip time per hop for route requests. // The factor 2.0 is just to be safe.. SRD 5/22/99 // Also note that we are making timeouts to be larger if we have // done network wide broadcast before. rt->rt_req_timeout = 2.0 * (double) ih->ttl_ * PerHopTime(rt); if (rt->rt_req_cnt > 0) rt->rt_req_timeout *= rt->rt_req_cnt; rt->rt_req_timeout += CURRENT_TIME; // Don't let the timeout to be too large, however.. SRD 6/8/99 if (rt->rt_req_timeout > CURRENT_TIME + MAX_RREQ_TIMEOUT) rt->rt_req_timeout = CURRENT_TIME + MAX_RREQ_TIMEOUT; rt->rt_expire = 0; fprintf(stderr, "(%2d) - %2d sending Route Request, dst: %d, tout %f ms\n", ++route_request, index, rt->rt_dst, rt->rt_req_timeout - CURRENT_TIME); // Fill out the RREQ packet // ch->uid() = 0; ch->ptype() = PT_AODV; ch->size() = IP_HDR_LEN + rq->size(); ch->iface() = -2; ch->error() = 0; ch->addr_type() = NS_AF_NONE; ch->prev_hop_ = index; // AODV hack

8 ih->saddr() = index; ih->daddr() = IP_BROADCAST; ih->sport() = RT_PORT; ih->dport() = RT_PORT; // index 就是 Source Node 自己本身的 Node ID // Fill up some more fields. rq->rq_type = AODVTYPE_RREQ; // AODV RREQ rq->rq_hop_count = 1; rq->rq_bcast_id = bid++; rq->rq_dst = dst; rq->rq_dst_seqno = (rt? rt->rt_seqno : 0); rq->rq_src = index; seqno += 2; assert ((seqno%2) == 0); rq->rq_src_seqno = seqno; rq->rq_timestamp = CURRENT_TIME; Scheduler::instance().schedule(target_, p, 0.); AODV::sendReply(nsaddr_t ipdst, u_int32_t hop_count, nsaddr_t rpdst, u_int32_t rpseq, u_int32_t lifetime, double timestamp) { Packet *p = Packet::alloc(); struct hdr_cmn *ch = HDR_CMN(p); struct hdr_ip *ih = HDR_IP(p); struct hdr_aodv_reply *rp = HDR_AODV_REPLY(p); aodv_rt_entry *rt = rtable.rt_lookup(ipdst); fprintf(stderr, "sending Reply from %d at %.2f\n", index, Scheduler::instance().clock()); #ifdef DUMP FILE *fp; if ((fp = fopen("out.aodv", "a"))!= NULL) { fprintf(fp, "%f %d -%s to %d\n", CURRENT_TIME, index, FUNCTION, ipdst); fclose(fp); // 將時間 Node ID 函式功能以及 Reply 的 Destination 記錄至 out.aodv 這個檔案中 assert(rt); rp->rp_type = AODVTYPE_RREP; //rp->rp_flags = 0x00; rp->rp_hop_count = hop_count; rp->rp_dst = rpdst; rp->rp_dst_seqno = rpseq; rp->rp_src = index; rp->rp_lifetime = lifetime; rp->rp_timestamp = timestamp; // ch->uid() = 0; ch->ptype() = PT_AODV; ch->size() = IP_HDR_LEN + rp->size(); ch->iface() = -2; ch->error() = 0; ch->addr_type() = NS_AF_INET; ch->next_hop_ = rt->rt_nexthop; ch->prev_hop_ = index; // AODV hack ch->direction() = hdr_cmn::down; ih->saddr() = index; ih->daddr() = ipdst; ih->sport() = RT_PORT;

9 ih->dport() = RT_PORT; ih->ttl_ = NETWORK_DIAMETER; Scheduler::instance().schedule(target_, p, 0.); 模擬結果首先我們先將 TCL Script 的執行過程列出來給大家看一下 ($ 為 Linux 的命令列提示符號 ) 這個 TCP Script 在執行的過程中會產生 10 個 Node,Node 的位置 ( 在 X Y 軸上的位置 ) 都是以亂數的方式產生的另外, 包括應用程式啟動的時也都是亂數產生的, 其中,ftp 3 在秒時開始傳資料,ftp 7 則是在開始傳資料, 最後一個傳資料的是 ftp 8, 流量產生的時間是在秒開始 $ ns random_pos_delay.tcl 10 random Starting Simulation... node(0): x= y= node(1): x= y= node(2): x= y= node(3): x= y= node(4): x= y= node(5): x= y= node(6): x= y= node(7): x= y= node(8): x= y= node(9): x= y= ftp 0 ON ftp 1 ON ftp 2 ON ftp 3 ON ftp 4 ON ftp 5 ON ftp 6 ON ftp 7 ON ftp 8 ON num_nodes is set 10 channel.cc:sendup - Calc highestantennaz_ and distcst_ highestantennaz_ = 1.5, distcst_ = 接下來我們就透過我們自行產生的 out.aodv 這個 Trace 檔的來觀察到 AODV 的訊息是如何在網路上的 Node 之間運作的 : sendrequest to 4 // 註 :ftp 3 準備開始傳資料 recvrequest from sendreply to recvreply from 4 hop=1 latency= sendrequest to 8 // 註 :ftp 7 準備開始傳資料 recvrequest from sendreply to recvreply from 8 hop=1 latency= sendrequest to recvrequest from sendreply to recvreply from 5 hop=1 latency= sendrequest to recvrequest from sendreply to recvreply from 6 hop=1 latency= recvreply from 3 hop=2 latency= sendrequest to recvrequest from sendreply to 0

10 recvreply from 1 hop=1 latency= sendrequest to recvrequest from sendreply to recvreply from 2 hop=1 latency= recvreply from 7 hop=2 latency= sendrequest to recvrequest from 1 (I may have a fresh enough route) sendreply to recvrequest from 1 (I may have a fresh enough route) sendreply to recvreply from 3 hop=3 latency= recvreply from 0 hop=4 latency= recvreply from 7 hop=2 latency= sendrequest to recvrequest from 2 (I may have a fresh enough route) sendreply to recvreply from 7 hop=3 latency= recvreply from 0 hop=3 latency= sendrequest to recvrequest from sendreply to recvreply from 7 hop=1 latency= recvreply from 0 hop=2 latency= sendrequest to 9 // 註 :ftp 8 準備開始傳資料 recvrequest from sendreply to recvreply from 9 hop=1 latency= recvreply from 3 hop=2 latency= recvreply from 0 hop=3 latency= 由於 AODV 是一種 On deman 的 Protocl, 也就是只有在需要時,AODV 才會去尋找一個由 Source 至 Destination 之間的 Route 所以在 Application 有資料要準備開始傳時,AODV 才去把傳送這個資料所需要的找出來 Reference:

穨control.PDF

穨control.PDF TCP congestion control yhmiu Outline Congestion control algorithms Purpose of RFC2581 Purpose of RFC2582 TCP SS-DR 1998 TCP Extensions RFC1072 1988 SACK RFC2018 1996 FACK 1996 Rate-Halving 1997 OldTahoe