00001 /* -*- Mode:C++; c-basic-offset:8; tab-width:8; indent-tabs-mode:t -*- */ 00002 /* 00003 * Copyright (c) 1997 Regents of the University of California. 00004 * All rights reserved. 00005 * 00006 * Redistribution and use in source and binary forms, with or without 00007 * modification, are permitted provided that the following conditions 00008 * are met: 00009 * 1. Redistributions of source code must retain the above copyright 00010 * notice, this list of conditions and the following disclaimer. 00011 * 2. Redistributions in binary form must reproduce the above copyright 00012 * notice, this list of conditions and the following disclaimer in the 00013 * documentation and/or other materials provided with the distribution. 00014 * 3. All advertising materials mentioning features or use of this software 00015 * must display the following acknowledgement: 00016 * This product includes software developed by the Daedalus Research 00017 * Group at the University of California Berkeley. 00018 * 4. Neither the name of the University nor of the Laboratory may be used 00019 * to endorse or promote products derived from this software without 00020 * specific prior written permission. 00021 * 00022 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 00023 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 00024 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 00025 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 00026 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 00027 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 00028 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 00029 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 00030 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 00031 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 00032 * SUCH DAMAGE. 00033 * 00034 * Contributed by the Daedalus Research Group, http://daedalus.cs.berkeley.edu 00035 * 00036 */ 00037 00038 /* 00039 This is an implementation of the ARQ feature used in HDLC working in ABM (Asynchronous Balanced Mode) which provides a reliable mode of link transfer using acknowledgements. 00040 First cut implementation; 00041 */ 00042 00043 #ifndef ns_hdlc_h 00044 #define ns_hdlc_h 00045 00046 #include <satlink.h> 00047 #include <timer-handler.h> 00048 #include <drop-tail.h> 00049 00050 00051 00052 //#define HDLC_MWS 1024 00053 //#define HDLC_MWS 8 00054 #define HDLC_MWS 65536 00055 #define HDLC_MWM (HDLC_MWS-1) 00056 #define HDLC_HDR_LEN sizeof(struct hdr_hdlc); 00057 #define DELAY_ACK_VAL 0.5 // arbitrarily chosen val for which acks are delayed 00058 00059 enum SS_t {RR=0, REJ=1, RNR=2, SREJ=3}; 00060 enum COMMAND_t {SNRM, SNRME, SARM, SARME, SABM, SABME, DISC, UA, DM}; 00061 enum HDLCFrameType { HDLC_I_frame, HDLC_S_frame, HDLC_U_frame }; 00062 00063 class HDLC; 00064 class HdlcTimer; 00065 00066 struct ARQstate { 00067 00068 int nh_; // next-hop 00069 int t_seqno_; // tx'ing seq no 00070 int seqno_; // counter for seq'ing incoming data pkts 00071 int maxseq_; // highest seq no sent so far 00072 int highest_ack_; // highest ack recvd so far 00073 int recv_seqno_; // seq no of data pkts recvd by recvr 00074 00075 int nrexmit_; // num of retransmits 00076 int ntimeouts_; // num of retx timeouts 00077 bool closed_; // whether this connection is closed 00078 int disconnect_; 00079 bool sentDISC_; 00080 00081 int SABME_req_; // whether a SABME request has been sent or not 00082 bool sentREJ_; // to prevent sending dup REJ 00083 00084 Packet *save_; // packet saved for delayed ack to allow piggybacking 00085 // at receiving side hold pkts until they are all recvd in order 00086 // and can be fwded to layers above LL 00087 Packet** seen_; // array of pkts seen 00088 int nextpkt_; // next packet expected 00089 int maxseen_; // max pkt number seen 00090 00091 HdlcTimer *rtx_timer_; 00092 HdlcTimer *reset_timer_; 00093 HdlcTimer *delay_timer_; 00094 00095 // buffer to hold outgoing the pkts until they are ack'ed 00096 PacketQueue sendBuf_; 00097 00098 ARQstate *next_; 00099 00100 }; 00101 00102 class HdlcTimer : public TimerHandler { 00103 public: 00104 HdlcTimer(HDLC *agent, ARQstate *a, void (HDLC::*callback)(ARQstate *a)) 00105 : agent_(agent), a_(a), callback_(callback) {}; 00106 00107 protected: 00108 virtual void expire(Event *e); 00109 HDLC *agent_; 00110 ARQstate *a_; 00111 void (HDLC::*callback_)(ARQstate *a); 00112 }; 00113 00114 struct HDLCControlFrame { 00115 int recv_seq; 00116 int send_seq; 00117 char frame_command; 00118 }; 00119 00120 struct I_frame { 00121 int recv_seqno; 00122 bool poll_final_bit; 00123 int send_seqno; 00124 }; 00125 00126 struct S_frame { 00127 int recv_seqno; 00128 bool poll_final_bit; 00129 SS_t stype; 00130 }; 00131 00132 struct U_frame { 00133 bool poll_final_bit; 00134 COMMAND_t utype; 00135 }; 00136 00137 00138 00139 // The hdlc hdr share the same hdr space with hdr_ll 00140 struct hdr_hdlc { 00141 int saddr_; // src mac id 00142 int daddr_; // destination mac id 00143 HDLCControlFrame hdlc_fc_; 00144 HDLCFrameType fc_type_; 00145 int padding_; 00146 00147 // static int offset_; 00148 // inline int& offset() { return offset_; } 00149 // static hdr_hdlc* access(const Packet* p) { 00150 // return (hdr_hdlc*) p->access(offset_); 00151 // } 00152 00153 inline int saddr() {return saddr_;} 00154 inline int daddr() {return daddr_;} 00155 00156 }; 00157 00158 // XXXXXXXXX 00159 // Currently, we assume the link layer shall have one p-2-p connection 00160 // at any given time 00161 00162 // If this needs to change the ARQstate defined below should be used 00163 // to support multiple p-2-p connections, each state for a src-dst pair. 00164 00165 00166 00167 00168 00169 // Brief description of HDLC model used : 00170 // Type of station: 00171 // combined station capable of issuing both commands and responses, 00172 00173 // Link configurations: 00174 // Consists of combined stations and supports both full-duplex and half-duplex transmission. HAlf-duplex for now; will be extended to full-duplex in the future. 00175 00176 // Data transfer mode: asynchronous balanced mode extended (ABME). Either station may initiate transmission without receiving permission from the other combined station. In this mode the frames are numbered and are acknowledged by the receiver. HDLC defines the extended mode to support 7 bits (128bit modulo numbering) for sequence numbers. For our simulation we use 31 bits. 00177 00178 // Initialization: consists of the sender sending a U frame issuing the SABME command (set asynchronous balanced mode/extended); the receiver sends back an UA (unnumbered ackowledged) or can send a DM (disconnected mode) to reject connection setup. 00179 00180 // Data sending: done using I frames by sender. receiver sends back RR S frames indicating the next I frame it expects. S frames are used for both error control as well as flow control. It sends a REJ for any missing frame asking receiver to go-back-N. It can send RNR asking recvr not to send any frames until it again sends RR. It also sends SREJ asking retx of a specific missing pkt. 00181 00182 // Disconnect: 00183 // Either HDLC entity can initiate a disconnect using a disconnect (DISC) frame. The remote entity must accept the disconnect by replying with a UA and informing its layer 3 user that the connection has been terminated. Any outstanding unacknowledged frames may be recovered by higher layers. 00184 00185 00186 class HDLC : public SatLL { 00187 friend class HdlcTimer; 00188 friend class ARQstate; 00189 00190 public: 00191 HDLC(); 00192 virtual void recv(Packet* p, Handler* h); 00193 inline virtual void hdr_dst(Packet *p, int macDA) { HDR_HDLC(p)->daddr_ = macDA;} 00194 virtual void timeout(ARQstate *s); 00195 00196 protected: 00197 // main sending and recving routines 00198 void recvIncoming(Packet* p); 00199 void recvOutgoing(Packet* p); 00200 00201 // misc routines 00202 void inSendBuffer(Packet *p, ARQstate *a); 00203 int resolveAddr(Packet *p); 00204 void reset(ARQstate *a); 00205 00206 // queue 00207 Packet *getPkt(PacketQueue buf, int seq); 00208 00209 // rtx timer 00210 void reset_rtx_timer(ARQstate *a, int backoff); 00211 void set_rtx_timer(ARQstate *a); 00212 void cancel_rtx_timer(ARQstate *a) { (a->rtx_timer_)->force_cancel(); } 00213 void rtt_backoff(); 00214 double rtt_timeout(); 00215 void delayTimeout(ARQstate *s); 00216 void cancel_delay_timer(ARQstate *a) { (a->delay_timer_)->force_cancel();} 00217 double reset_timeout(); 00218 void set_reset_timer(ARQstate *a); 00219 void cancel_reset_timer(ARQstate *a) { (a->reset_timer_)->force_cancel(); } 00220 00221 // sending routines 00222 void sendDown(Packet *p); 00223 void sendMuch(ARQstate *a); 00224 void output(Packet *p, ARQstate *a, int seqno); 00225 //Packet *dataToSend(Packet *p); 00226 void ack(Packet *p); 00227 Packet *dataToSend(ARQstate *a); 00228 //void ack(); 00229 void sendUA(Packet *p, COMMAND_t cmd); 00230 void sendRR(Packet *p, ARQstate *a); 00231 void sendRNR(Packet *p); 00232 void sendREJ(Packet *p, ARQstate *a); 00233 void sendSREJ(Packet *p, int seq); 00234 void sendDISC(Packet *p); 00235 00236 // receive routines 00237 void recvIframe(Packet *p); 00238 void recvSframe(Packet *p); 00239 void recvUframe(Packet *p); 00240 void handleSABMErequest(Packet *p); 00241 void handleUA(Packet *p); 00242 void handleDISC(Packet *p); 00243 void handleRR(Packet *p); 00244 void handleRNR(Packet *p); 00245 void handleREJ(Packet *p); 00246 void handleSREJ(Packet *p); 00247 void handlePiggyAck(Packet *p, ARQstate *a); 00248 00249 // go back N error recovery 00250 void goBackNMode(Packet *p); 00251 00252 // selective repeat mode 00253 void selectiveRepeatMode(Packet *p); 00254 00255 // per src-dst connection state 00256 ARQstate *newEntry(int next_hop); 00257 ARQstate *createState(int next_hop); 00258 ARQstate *checkState(int next_hop); // get state, if no state, create 00259 void removeState(int nh_); // remove from list of states 00260 00261 // event-tracing 00262 //virtual void trace_event(char *eventtype); 00263 //EventTrace *et_; 00264 00265 // variables 00266 static int uidcnt_; 00267 int wndmask_ ; // window mask 00268 int wnd_; // size of window; set from tcl 00269 int queueSize_; 00270 double timeout_; // value of timeout 00271 int maxTimeouts_; // max num of timeouts before connection closed 00272 int selRepeat_; // if this is set then selective repeat mode is used // otherwise Go Back N mode is used by default 00273 int delAckVal_; // time for which ack is delayed 00274 int delAck_; // flag for delayed ack 00275 00276 ARQstate *list_head_; 00277 00278 00279 }; 00280 00281 #endif