queue.cc
上传用户:sdhqmy
上传日期:2015-12-07
资源大小:63k
文件大小:7k
源码类别:

3G开发

开发平台:

C/C++

  1. /* -*- Mode:C++; c-basic-offset:8; tab-width:8; indent-tabs-mode:t -*- */
  2. /*
  3.  * Copyright (c) 1996-1997 The Regents of the University of California.
  4.  * All rights reserved.
  5.  * 
  6.  * Redistribution and use in source and binary forms, with or without
  7.  * modification, are permitted provided that the following conditions
  8.  * are met:
  9.  * 1. Redistributions of source code must retain the above copyright
  10.  *    notice, this list of conditions and the following disclaimer.
  11.  * 2. Redistributions in binary form must reproduce the above copyright
  12.  *    notice, this list of conditions and the following disclaimer in the
  13.  *    documentation and/or other materials provided with the distribution.
  14.  * 3. All advertising materials mentioning features or use of this software
  15.  *    must display the following acknowledgement:
  16.  *  This product includes software developed by the Network Research
  17.  *  Group at Lawrence Berkeley National Laboratory.
  18.  * 4. Neither the name of the University nor of the Laboratory may be used
  19.  *    to endorse or promote products derived from this software without
  20.  *    specific prior written permission.
  21.  * 
  22.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  23.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  24.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  25.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  26.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  27.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  28.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  29.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  30.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  31.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  32.  * SUCH DAMAGE.
  33.  */
  34. #ifndef lint
  35. static const char rcsid[] =
  36.     "@(#) $Header: /nfs/jade/vint/CVSROOT/ns-2/queue/queue.cc,v 1.25 2002/01/01 00:04:53 sfloyd Exp $ (LBL)";
  37. #endif
  38. #include "queue.h"
  39. #include <stdio.h>
  40. //JUNGMIN
  41. #include "mac-802_11.h"
  42. //end of JUNGMIN
  43. //#define MAXIMUM_NEIGHBOR 64
  44. void PacketQueue::remove(Packet* target)
  45. {
  46. for (Packet *pp= 0, *p= head_; p; pp= p, p= p->next_) {
  47. if (p == target) {
  48. if (!pp) deque();
  49. else {
  50. if (p == tail_) 
  51. tail_= pp;
  52. pp->next_= p->next_;
  53. --len_;
  54. bytes_ -= hdr_cmn::access(p)->size();
  55. }
  56. return;
  57. }
  58. }
  59. fprintf(stderr, "PacketQueue:: remove() couldn't find targetn");
  60. abort();
  61. }
  62. /*
  63.  * Remove packet pkt located after packet prev on the queue.  Either p or prev
  64.  * could be NULL.  If prev is NULL then pkt must be the head of the queue.
  65.  */
  66. void PacketQueue::remove(Packet* pkt, Packet *prev) //XXX: screwy
  67. {
  68. if (pkt) {
  69. if (head_ == pkt)
  70. PacketQueue::deque(); /* decrements len_ internally */
  71. else {
  72. prev->next_ = pkt->next_;
  73. if (tail_ == pkt)
  74. tail_ = prev;
  75. --len_;
  76. bytes_ -= hdr_cmn::access(pkt)->size();
  77. }
  78. }
  79. return;
  80. }
  81. //JUNGMIN
  82. int PacketQueue::BuildQState(int* q_array, int size)
  83. {
  84. //printf("PacketQueue::BuildQState called len_: %dn", len_);
  85. int i;
  86. Packet* tp;
  87. struct hdr_mac802_11* dh;
  88. int dst;
  89. int nodecount = 0;
  90. //First reset the array
  91. for(i=0; i < size; i++) {
  92. q_array[i] = 0;
  93. }
  94. for(i=0; i < len_; i++) {
  95. tp = lookup(i);
  96. dh = HDR_MAC802_11(tp);
  97. dst = ETHER_ADDR(dh->dh_da);
  98. if(dst == -1) continue;
  99. //update the q state!
  100. if(q_array[dst] == 0) nodecount++;
  101. q_array[dst]++;
  102. }
  103. return nodecount;
  104. }
  105. //end of JUNGMIN
  106. void QueueHandler::handle(Event*)
  107. {
  108. queue_.resume();
  109. }
  110. //JUNGMIN
  111. Queue::Queue() : Connector(), blocked_(0), unblock_on_resume_(1), qh_(*this), 
  112. pq_(0), atim_window_(0), wmac_(0), pre_atim_max_(0), pre_atim_iter_(0), pre_atim_(0)
  113. /* temporarily NULL */
  114. //end of JUNGMIN
  115. {
  116. bind("limit_", &qlim_);
  117. bind_bool("blocked_", &blocked_);
  118. bind_bool("unblock_on_resume_", &unblock_on_resume_);
  119. //JUNGMIN
  120. ResetQInfo();
  121. //end of JUNGMIN
  122. }
  123. void Queue::recv(Packet* p, Handler*)
  124. {
  125. int dest;
  126. struct hdr_mac802_11* dh = HDR_MAC802_11(p);
  127. enque(p);
  128. //JUNGMIN
  129. if (atim_window_ == 1) {
  130. if(!blocked_) {
  131. //must block the queue since already one packet is
  132. //waiting to be sent. It's just blocked by the
  133. //ATIM window.
  134. blocked_ = 1;
  135. }
  136. return;
  137. }
  138. if (!blocked_) {
  139. /*
  140.  * We're not blocked.  Get a packet and send it on.
  141.  * We perform an extra check because the queue
  142.  * might drop the packet even if it was
  143.  * previously empty!  (e.g., RED can do this.)
  144.  */
  145. p = deque();
  146. if (p != 0) {
  147. //if it is near the beacon, don't send the packet
  148. if(wmac_->NearBeacon(p, 0)) {
  149. ReturnPacket(p);
  150. return;
  151. }
  152. //end of implementation
  153. blocked_ = 1;
  154. target_->recv(p, &qh_);
  155. }
  156. }
  157. //end of JUNGMIN
  158. }
  159. void Queue::updateStats(int queuesize)
  160. {
  161.         double now = Scheduler::instance().clock();
  162.         double newtime = now - total_time_;
  163.         if (newtime > 0.0) {
  164.                 double oldave = true_ave_;
  165.                 double oldtime = total_time_;
  166.                 double newtime = now - total_time_;
  167.                 true_ave_ = (oldtime * oldave + newtime * queuesize) /now;
  168.                 total_time_ = now;
  169.         }
  170. }
  171. //JUNGMIN
  172. void Queue::ResetQInfo()
  173. {
  174. for(int i=0; i<MAX_NODES; i++) {
  175. q_state_[i] = 0;
  176. }
  177. }
  178. int Queue::ExtractMaximum(int *q_array)
  179. {
  180. int maximum_node = -1;
  181. int maximum_node_var = 0;
  182. int q_empty = 0;
  183. int i;
  184. for(i=0; i<MAX_NODES; i++) {
  185. if(q_array[i] > maximum_node_var) {
  186. maximum_node = i;
  187. q_empty = 1;
  188. }
  189. }
  190. if(q_empty == 0) return -1;
  191. //danger of seg fault
  192. q_array[i] = 0;
  193. return maximum_node;
  194. }
  195. void Queue::SetATIMWindow()
  196. {
  197. atim_window_ = 1;
  198. return;
  199. }
  200. void Queue::StartSendingATIM()
  201. {
  202. pre_atim_ = 1;
  203. //Build the Queue State and start sending ATIM
  204. pre_atim_max_ = BuildQState(q_state_, MAX_NODES); 
  205. pre_atim_iter_ = 0;
  206. if(pre_atim_iter_ < pre_atim_max_) {
  207. int dest = ExtractMaximum(q_state_);
  208. if(dest == -1) { 
  209. printf("dest = -1! Something's wrong!n");
  210. return;
  211. } else {
  212. wmac_->sendATIM(dest, &qh_);
  213. }
  214. pre_atim_iter_++;
  215. } else {
  216. pre_atim_ = 0;
  217. }
  218. }
  219. void Queue::ContinueSendingATIM()
  220. {
  221. //Build the Queue State and start sending ATIM
  222. if(pre_atim_iter_ < pre_atim_max_) {
  223. int dest = ExtractMaximum(q_state_);
  224. if(dest == -1) { 
  225. printf("dest = -1! Something's wrong!n");
  226. return;
  227. } else {
  228. wmac_->sendATIM(dest, &qh_);
  229. }
  230. pre_atim_iter_++;
  231. } else {
  232. pre_atim_ = 0;
  233. }
  234. }
  235. void Queue::ResetATIMWindow(int status)
  236. {
  237. atim_window_ = 0;
  238. if(status == 1) resume();
  239. }
  240. void Queue::resume()
  241. {
  242. //If the queue is backlogged, send the packet immediately.
  243. if (atim_window_ == 1) {
  244. //status: pre_atim_ (only)
  245. if(pre_atim_ == 1) {
  246. ContinueSendingATIM();
  247. return;
  248. }
  249. Packet* p = deque();
  250. if (p != 0) {
  251. //if it is near beacon, don't send the packet
  252. if(wmac_->NearBeacon(p, 1)) {
  253. //printf("[%d] %lf: Returning PACKET TO QUEUE DOWN from resume, queue size: %dn", wmac_->addr(), NOW, length());
  254. ReturnPacket(p);
  255. return;
  256. }
  257. //end of implementation
  258. target_->recv(p, &qh_);
  259. } else {
  260. if (unblock_on_resume_)
  261. blocked_ = 0;
  262. else
  263. blocked_ = 1;
  264. }
  265. }
  266. void Queue::reset()
  267. {
  268. Packet* p;
  269. total_time_ = 0.0;
  270. true_ave_ = 0.0;
  271. while ((p = deque()) != 0)
  272. drop(p);
  273. }
  274. void Queue::set_wmac(Mac802_11* m)
  275. {
  276. wmac_ = m;
  277. }
  278. //end of JUNGMIN