1632
правки
Изменения
м
TODO: хорошо бы эти картиночки заменить на текст=== Общие объявления ===<code> #define MAX_PKT 4 /* determines packet size in bytes */ typedef enum {false, но мне пока как-то не хочется этим заниматьсяtrue} boolean; /* boolean type */ typedef unsigned int seq_nr; /* sequence or ack numbers */ typedef struct {unsigned char data[MAX_PKT];} packet; /* packet definition */ typedef enum {data, ack, nak} frame_kind; /* frame_kind definition */ typedef struct { /* frames are transported in this layer */ frame_kind kind; /* what kind of a frame is it? */ seq_nr seq; /* sequence number */ seq_nr ack; /* acknowledgement number */ packet info; /* the network layer packet */ } frame; /* Wait for an event to happen; return its type in event. */ void wait_for_event(event_type *event); /* Fetch a packet from the network layer for transmission on the channel. */ void from_network_layer(packet *p); /* Deliver information from an inbound frame to the network layer. */ void to_network_layer(packet *p); /* Go get an inbound frame from the physical layer and copy it to r. */ void from_physical_layer(frame *r); /* Pass the frame to the physical layer for transmission. */ void to_physical_layer(frame *s); /* Start the clock running and enable the timeout event. */ void start_timer(seq_nr k); /* Stop the clock and disable the timeout event.*/ void stop_timer(seq_nr k);
=== Общие объявления === /* Start an auxiliary timer and enable the ack_timeout event. */[[Файл: Networks Link Layer Protocols Definitions.png]] void start_ack_timer(void);
[[Файл /* Stop the auxiliary timer and disable the ack_timeout event. */ void stop_ack_timer(void); /* Allow the network layer to cause a network_layer_ready event. */ void enable_network_layer(void); /* Forbid the network layer from causing a network_layer_ready event. */ void disable_network_layer(void); /* Macro inc is expanded in-line: Networks Increment k circularly. */ #define inc(k) if (k < MAX_SEQ) k = k + 1.5 Definitions.png]]; else k = 0</code>
[[Файл: Networks 1.5 Protocol5.1.png]]
[[Файл: 2015-04-02-14-00-07_selection<code> /* Protocol 5 (pipelining) allows multiple outstanding frames.png]]The sender may transmit up to MAX_SEQ frames without waiting for an ack. In addition, unlike the previous protocols, the network layer is not assumed to have a new packet all the time. Instead, the network layer causes a network_layer_ready event when there is a packet to send. */
[[Файл: Networks #define MAX_SEQ 7 /* should be 2^n - 1*/ typedef enum {frame_arrival, cksum_err, timeout, network_layer_ready} event_type; #include "protocol.h" static boolean between(seq_nr a, seq_nr b, seq_nr c) { /* Return true if (a <=b < c circularly; false otherwise.5 Protocol5*/ if (((a <= b) && (b < c)) || ((c < a) && (a <= b)) || ((b < c) && (c < a))) return(true); else return(false); } static void send_data(seq_nr frame_nr, seq_nr frame_expected, packet buffer[]) { /* Construct and send a data frame.3*/ frame s; /* scratch variable */ s.pnginfo = buffer[frame_nr]; /* insert packet into frame */ s.seq = frame_nr; /* insert sequence number into frame */ s.ack = (frame_expected + MAX_SEQ) % (MAX_SEQ + 1); /* piggyback ack */ to_physical_layer(&s); /* transmit the frame */ start_timer(frame_nr); /* start the timer running */ } void protocol5(void) { seq_nr next_frame_to_send; /* MAX_SEQ > 1; used for outbound stream */ seq_nr ack_expected; /* oldest frame as yet unacknowledged */ seq_nr frame_expected; /* next frame expected on inbound stream */ frame r; /* scratch variable */ packet buffer[MAX_SEQ+1]; /* buffers for the outbound stream */ seq_nr nbuffered; /* # output buffers currently in use */ seq_nr i; /* used to index into the buffer array */ event_type event; enable_network_layer(); /* allow network_layer_ready events */ ack_expected = 0; /* next ack expected inbound */ next_frame_to_send = 0; /* next frame going out */ frame_expected = 0; /* number of frame expected inbound */ nbuffered = 0; /* initially no packets are buffered */
[[Файл case frame_arrival: Networks 1/* a data or control frame has arrived */ from_physical_layer(&r); /* fetch incoming frame from physical layer */ if (r.5 Protocol6kind == data) { /* An undamaged frame has arrived.2*/ if ((r.png]seq != frame_expected) && no_nak) send_frame(nak, 0, frame_expected, out_buf); else start_ack_timer(); if (between(frame_expected, r.seq, too_far) && (arrived[r.seq%NR_BUFS]== false)) { /* Frames may be accepted in any order. */ arrived[r.seq % NR_BUFS] = true; /* mark buffer as full */ in_buf[Файл: Networks 1r.5 Protocol6seq % NR_BUFS] = r.3info; /* insert data into buffer */ while (arrived[frame_expected % NR_BUFS]) { /* Pass frames and advance window.png*/ to_network_layer(&in_buf[frame_expected % NR_BUFS]); no_nak = true; arrived[frame_expected % NR_BUFS]= false; inc(frame_expected); /* advance lower edge of receiver's window */ inc(too_far); /* advance upper edge of receiver's window */ start_ack_timer(); /* to see if (a separate ack is needed */ } }[[Файл: Networks } if((r.kind==nak) && between(ack_expected,(r.ack+1)%(MAX_SEQ+1),next_frame_to_send)) send_frame(data, (r.5 Protocol6ack+1) % (MAX_SEQ + 1), frame_expected, out_buf); while (between(ack_expected, r.4.png]]ack, next_frame_to_send)) { nbuffered = nbuffered - 1; /* handle piggybacked ack */ stop_timer(ack_expected % NR_BUFS); /* frame arrived intact */ inc(ack_expected); /* advance lower edge of sender's window */ } break; case cksum_err: if (no_nak) send_frame(nak, 0, frame_expected, out_buf); break; /* damaged frame */ case timeout: send_frame(data, oldest_frame, frame_expected, out_buf); break; /* we timed out */ case ack_timeout: send_frame(ack,0,frame_expected, out_buf); /* ack timer expired; send ack */ } if (nbuffered < NR_BUFS) enable_network_layer(); else disable_network_layer(); } }</code>
rollbackEdits.php mass rollback
На канальном уровне нужно передавать данные с сетевого уровня. При этом требуется, чтобы кадры не дублировались, и сохранялся порядок. Ниже представлены протоколы с различными допущениями о канале от самого простого случая (с идеальным каналом) к более сложным. Сначала даётся краткое словесное описание, затем сишный псевдокод, из которого всё понятно.
=== Неограниченный симлексный протокол ===
В реализации есть ещё одно нововведение: у сетевого уровня не всегда есть данные для передачи, поэтому он будет генерить событие, когда хочет что-то передавать. Также его можно выключить, чтобы он ничего не генерил, если у нас заполнено всё окно.
while (true) { wait_for_event(&event); /* four possibilities: see event_type above */ switch(event) { case network_layer_ready: /* the network layer has a packet to send */ /* Accept, save, and transmit a new frame. */ from_network_layer(&buffer[[Файлnext_frame_to_send]); /* fetch new packet */ nbuffered = nbuffered + 1; /* expand the sender's window */ send_data(next_frame_to_send, frame_expected, buffer); /* transmit the frame */ inc(next_frame_to_send); /* advance sender's upper window edge */ break; case frame_arrival: Networks /* a data or control frame has arrived */ from_physical_layer(&r); /* get incoming frame from physical layer */ if (r.seq == frame_expected) { /* Frames are accepted only in order. */ to_network_layer(&r.info); /* pass packet to network layer */ inc(frame_expected); /* advance lower edge of receiver's window */ } /* Ack n implies n - 1, n - 2, etc.5 Protocol5 Check for this.4*/ while (between(ack_expected, r.png]]ack, next_frame_to_send)) { /* Handle piggybacked ack. */ nbuffered = nbuffered - 1; /* one frame fewer buffered */ stop_timer(ack_expected); /* frame arrived intact; stop timer */ inc(ack_expected); /* contract sender's window */ } break; case cksum_err: ; /* just ignore bad frames */ break; case timeout: /* trouble; retransmit all outstanding frames */ next_frame_to_send = ack_expected; /* start retransmitting here */ for (i = 1; i <= nbuffered; i++) { send_data(next_frame_to_send, frame_expected, buffer); /* resend 1 frame */ inc(next_frame_to_send); /* prepare to send the next one */ } } if (nbuffered < MAX_SEQ) enable_network_layer(); else disable_network_layer(); } }</code>
==== Протоколы с выборочным повтором ====
Также можно посылать отрицательное подтверждение (NAK), в этом случае отправитель перепошлёт потерянный кадр до истечения таймаута.
<code> /* Protocol 6 (nonsequential receive) accepts frames out of order, but passes packets to the network layer in order. Associated with each outstanding frame is a timer. When the timer goes off, only that frame is retransmitted, not all the outstanding frames, as in protocol 5. */ #define MAX_SEQ 7 /* should be 2^n - 1 */ #define NR_BUFS ((MAX_SEQ + 1)/2) typedef enum {frame_arrival, cksum_err, timeout, network_layer_ready, ack_timeout} event_type; #include "protocol.h" boolean no_nak = true; /* no nak has been sent yet */ seq_nr oldest_frame = MAX_SEQ+1; /* init value is for the simulator */ static boolean between(seq_nr a, seq_nr b, seq_nr c) { /* Same as between in protocol5, but shorter and more obscure. */ return ((a <= b) && (b < c)) || ((c < a) && (a <= b)) || ((b < c) && (c < a)); } static void send_frame(frame_kind fk, seq_nr frame_nr, seq_nr frame_expected, packet buffer[]) { /* Construct and send a data, ack, or nak frame. */ frame s; /* scratch variable */ s.kind = fk; /* kind == data, ack, or nak */ if (fk == data) s.info = buffer[Файл: Networks 1frame_nr % NR_BUFS]; s.5 Protocol6seq = frame_nr; /* only meaningful for data frames */ s.ack = (frame_expected + MAX_SEQ) % (MAX_SEQ + 1); if (fk == nak) no_nak = false; /* one nak per frame, please */ to_physical_layer(&s); /* transmit the frame */ if (fk == data) start_timer(frame_nr % NR_BUFS); stop_ack_timer(); /* no need for separate ack frame */ } void protocol6(void) { seq_nr ack_expected; /* lower edge of sender's window */ seq_nr next_frame_to_send; /* upper edge of sender's window + 1 */ seq_nr frame_expected; /* lower edge of receiver's window */ seq_nr too_far; /* upper edge of receiver's window + 1 */ int i; /* index into buffer pool */ frame r; /* scratch variable */ packet out_buf[NR_BUFS]; /* buffers for the outbound stream */ packet in_buf[NR_BUFS]; /* buffers for the inbound stream */ boolean arrived[NR_BUFS]; /* inbound bit map */ seq_nr nbuffered; /* how many output buffers currently used */ event_type event; enable_network_layer(); /* initialize */ ack_expected = 0; /* next ack expected on the inbound stream */ next_frame_to_send = 0; /* number of next outgoing frame */ frame_expected = 0; /* frame number expected */ too_far = NR_BUFS; /* receiver's upper window + 1.png*/ nbuffered = 0; /* initially no packets are buffered */ for (i = 0; i < NR_BUFS; i++) arrived[i]= false; while (true) { wait_for_event(&event); /* five possibilities: see event_type above */ switch(event) { case network_layer_ready: /* accept, save, and transmit a new frame */ nbuffered = nbuffered + 1; /* expand the window */ from_network_layer(&out_buf[next_frame_to_send % NR_BUFS]); /* fetch new packet */ send_frame(data, next_frame_to_send, frame_expected, out_buf); /* transmit the frame */ inc(next_frame_to_send); /* advance upper window edge */ break;
=== Верификация протоколов ===
