数据链路层(ARQ)协议的实现，重点是p5(退回到N重传)和p6（选择性重传）

#include <sys/types.h> #include <sys/stat.h> #include <stdlib.h> #include <unistd.h> #include <stdio.h> #include "common.h" #define NR_TIMERS 8 /* number of timers */ #define MAX_QUEUE 100000 /* max number of buffered frames */ #define NO_EVENT -1 /* no event possible */ #define FRAME_SIZE (sizeof(frame)) #define BYTE 0377 /* byte mask */ #define UINT_MAX 0xFFFFFFFF /* maximum value of an unsigned 32-bit int */ #define INTERVAL 100000 /* interval for periodic printing */ #define AUX 2 /* aux timeout is main timeout/AUX */ /* DEBUG MASKS */ #define SENDS 0x0001 /* frames sent */ #define RECEIVES 0x0002 /* frames received */ #define TIMEOUTS 0x0004 /* timeouts */ #define PERIODIC 0x0008 /* periodic printout for use with long runs */ /* Status variables used by the workers, M0 and M1. */ bigint ack_timer[NR_TIMERS]; /* ack timers */ unsigned int seqs[NR_TIMERS]; /* last sequence number sent per timer */ bigint lowest_timer; /* lowest of the timers */ bigint aux_timer; /* value of the auxiliary timer */ int network_layer_status; /* 0 is disabled, 1 is enabled */ unsigned int next_net_pkt; /* seq of next network packet to fetch */ unsigned int last_pkt_given= 0xFFFFFFFF; /* seq of last pkt delivered*/ frame last_frame; /* arrive frames are kept here */ int offset; /* to prevent multiple timeouts on same tick*/ bigint tick; /* current time */ int retransmitting; /* flag that is set on a timeout */ int nseqs = -1; /* must be MAX_SEQ + 1 after startup */ extern unsigned int oldest_frame; /* tells protocol 6 which frame timed out */ char *badgood[] = {"bad ", "good"}; char *tag[] = {"Data", "Ack ", "Nak "}; /* Statistics */ int data_sent; /* number of data frames sent */ int data_retransmitted; /* number of data frames retransmitted */ int data_lost; /* number of data frames lost */ int data_not_lost; /* number of data frames not lost */ int good_data_recd; /* number of data frames received */ int cksum_data_recd; /* number of bad data frames received */ int acks_sent; /* number of ack frames sent */ int acks_lost; /* number of ack frames lost */ int acks_not_lost; /* number of ack frames not lost */ int good_acks_recd; /* number of ack frames received */ int cksum_acks_recd; /* number of bad ack frames received */ int payloads_accepted; /* number of pkts passed to network layer */ int timeouts; /* number of timeouts */ int ack_timeouts; /* number of ack timeouts */ /* Incoming frames are buffered here for later processing. */ frame queue[MAX_QUEUE]; /* buffered incoming frames */ frame *inp = &queue[0]; /* where to put the next frame */ frame *outp = &queue[0]; /* where to remove the next frame from */ int nframes; /* number of queued frames */ /* Prototypes. */ void wait_for_event(event_type *event); void queue_frames(void); int pick_event(void); event_type frametype(void); void from_network_layer(packet *p); void to_network_layer(packet *p); void from_physical_layer(frame *r); void to_physical_layer(frame *s); void start_timer(seq_nr k); void stop_timer(seq_nr k); void start_ack_timer(void); void stop_ack_timer(void); void enable_network_layer(void); void disable_network_layer(void); int check_timers(void); int check_ack_timer(void); unsigned int pktnum(packet *p); void fr(frame *f); void recalc_timers(void); void print_statistics(void); void sim_error(char *s); void wait_for_event(event_type *event) { /* Wait_for_event reads the pipe from main to get the time. Then it * fstat's the pipe from the other worker to see if any * frames are there. If so, if collects them all in the queue array. * Once the pipe is empty, it makes a decision about what to do next. */ bigint ct, word = OK; if (nseqs < 0) nseqs = oldest_frame; /* need MAX_SEQ+1 for protocol 6 */ offset = 0; /* prevents two timeouts at the same tick */ retransmitting = 0; /* counts retransmissions */ while (true) { queue_frames(); /* go get any newly arrived frames */ if (write(mwfd, &word, TICK_SIZE) != TICK_SIZE) print_statistics(); if (read(mrfd, &ct, TICK_SIZE) != TICK_SIZE) print_statistics(); if (ct == 0) print_statistics(); tick = ct; /* update time */ if ((debug_flags & PERIODIC) && (tick%INTERVAL == 0)) printf("Tick %u. Proc %d. Data sent=%d Payloads accepted=%d Timeouts=%d\n", tick/DELTA, id, data_sent, payloads_accepted, timeouts); /* Now pick event. */ *event = pick_event(); if (*event == NO_EVENT) { word = (lowest_timer == 0 ? NOTHING : OK); continue; } word = OK; if (*event == timeout) { timeouts++; retransmitting = 1; /* enter retransmission mode */ if (debug_flags & TIMEOUTS) printf("Tick %u. Proc %d got timeout for frame %d\n", tick/DELTA, id, oldest_frame); } if (*event == ack_timeout) { ack_timeouts++; if (debug_flags & TIMEOUTS) printf("Tick %u. Proc %d got ack timeout\n", tick/DELTA, id); } return; } } void queue_frames(void) { /* See if any frames from the peer have arrived; if so get and queue them. * Queue_frames() sucks frames out of the pipe into the circular buffer, * queue[]. It first fstats the pipe, to avoid reading from an empty pipe and * thus blocking. If inp is near the top of queue[], a single call here * may read a few frames into the top of queue[] and then some more starting * at queue[0]. This is done in two read operations. */ int prfd, frct, k; frame *top; struct stat statbuf; prfd = (id == 0 ? r2 : r1); /* which file descriptor is pipe on */ if (fstat(prfd, &statbuf) < 0) sim_error("Cannot fstat peer pipe"); frct = statbuf.st_size/FRAME_SIZE; /* number of arrived frames */ if (nframes + frct >= MAX_QUEUE) /* check for possible queue overflow*/ sim_error("Out of queue space. Increase MAX_QUEUE and re-make."); /* If frct is 0, the pipe is empty, so don't read from it. */ if (frct > 0) { /* How many frames can be read consecutively? */ top = (outp <= inp ? &queue[MAX_QUEUE] : outp);/* how far can we rd?*/ k = top - inp; /* number of frames that can be read consecutively */ if (k > frct) k = frct; /* how many frames to read from peer */ if (read(prfd, inp, k * FRAME_SIZE) != k * FRAME_SIZE) sim_error("Error reading frames from peer"); frct -= k; /* residual frames not yet read */ inp += k; if (inp == &queue[MAX_QUEUE]) inp = queue; nframes += k; /* If frct is still > 0, the queue has been filled to the upper * limit, but there is still space at the bottom. Continue reading * there. This mechanism makes queue a circular buffer. */ if (frct > 0) { if (read(prfd, queue, frct * FRAME_SIZE) != frct*FRAME_SIZE) sim_error("Error 2 reading frames from peer"); nframes += frct; inp = &queue[frct]; } } } int pick_event(void) { /* Pick a random event that is now possible for the process. * The set of legal events depends on the protocol number and system state. * A timeout is not possible, for example, if no frames are outstanding. * For each protocol, events from 0 to some protocol-dependent maximum * are potentially allowed. The maximum is given by highest_event. The * events that are theoretically possible are given below. * * # Event Protocols: 1 2 3 4 5 6 * 0 frame_arrival x x x x x x * 1 chksum_err x x x x * 2 timeout x x x x * 3 network_layer_ready x x * 4 ack_timeout x (e.g. only 6 gets ack_timeout) * * Note that the order in which the tests is made is critical, as it gives * priority to some events over others. For example, for protocols 3 and 4 * frames will be delivered before a timeout will be caused. This is probably * a reasonable strategy, and more closely models how a real line w