Канальный уровень

Сервисы, подуровни

TODO

Протоколы

На канальном уровне нужно передавать данные с сетевого уровня. При этом требуется, чтобы кадры не дублировались, и сохранялся порядок. Ниже представлены протоколы с различными допущениями о канале от самого простого случая (с идеальным каналом) к более сложным. Сначала даётся краткое словесное описание, затем сишный псевдокод, из которого всё понятно.

Общие объявления

#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. */
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: Increment k circularly. */
#define inc(k) if (k < MAX_SEQ) k = k + 1; else k = 0

Неограниченный симлексный протокол

Данные передаются в одном направлении. Время обработки равно нулю, буфер бесконечен, канал идеальный. Отправитель просто постоянно шлёт данные, получатель постоянно читает.

/* Protocol 1 (utopia) provides for data transmission in one direction only, from
   sender to receiver.  The communication channel is assumed to be error free,
   and the receiver is assumed to be able to process all the input infinitely fast.
   Consequently, the sender just sits in a loop pumping data out onto the line as
   fast as it can. */

typedef enum {frame_arrival} event_type;
#include "protocol.h"

void sender1(void)
{
  frame s;	/* buffer for an outbound frame */
  packet buffer;	/* buffer for an outbound packet */

  while (true) {
        from_network_layer(&buffer);	/* go get something to send */
        s.info = buffer;	/* copy it into s for transmission */
        to_physical_layer(&s);	/* send it on its way */
  }	/* tomorrow, and tomorrow, and tomorrow,
 	   Creeps in this petty pace from day to day
	   To the last syllable of recorded time;
	        - Macbeth, V, v */
}

void receiver1(void)
{
  frame r;
  event_type event;	/* filled in by wait, but not used here */

  while (true) {
        wait_for_event(&event);	/* only possibility is frame_arrival */
        from_physical_layer(&r);	/* go get the inbound frame */
        to_network_layer(&r.info);	/* pass the data to the network layer */
  }
}

Симлексный протокол с ожиданием

Всё то же самое, только теперь считаем, что получатель обрабатывает данные не моментально, поэтому посылающий не может постоянно слать данные. Для этого получатель будет слать подтверждение, а отправитель будет его дожидаться, прежде чем послать следующий пакет. Канал считаем идеальным.

/* Protocol 2 (stop-and-wait) also provides for a one-directional flow of data from
   sender to receiver. The communication channel is once again assumed to be error
   free, as in protocol 1. However, this time, the receiver has only a finite buffer
   capacity and a finite procesing speed, so the protocol must explicitly prevent 
   the sender from flooding the receiver with data faster than it can be handled. */

typedef enum {frame_arrival} event_type;
#include "protocol.h"

void sender2(void)
{
  frame s;	/* buffer for an outbound frame */
  packet buffer;	/* buffer for an outbound packet */
  event_type event;	/* frame_arrival is the only possibility */

  while (true) {
        from_network_layer(&buffer);	/* go get something to send */
        s.info = buffer;	/* copy it into s for transmission */
        to_physical_layer(&s);	/* bye bye little frame */
        wait_for_event(&event);	/* do not proceed until given the go ahead */
  }
}

void receiver2(void)
{
  frame r, s;	/* buffers for frames */
  event_type event;	/* frame_arrival is the only possibility */
  while (true) {
        wait_for_event(&event);	/* only possibility is frame_arrival */
        from_physical_layer(&r);	/* go get the inbound frame */
        to_network_layer(&r.info);	/* pass the data to the network layer */
        to_physical_layer(&s);	/* send a dummy frame to awaken sender */
  }
}

Симплексный протокол для замушлённых каналов

Теперь перестаём верить в идеальный канал, кадры могут теряться и искажаться (в том числе служебные). Проверку искажения кадра будем проводить уровнем ниже (сверять checksum). Чтобы обнаружить потерю кадра, запустим таймер и будем ждать подтверждение. Если подтверждения нет, а наступил таймаут, то кадр считаем потраченным и посылаем заново. Есть проблема: может потеряться подтверждение, в таком случае произойдёт дублирование кадра. Для этого добавим порядковый номер кадра и подтверждения. В этом случае принимающий будет знать, какой порядковый номер он ждёт, и игнорировать кадры с неправильным номером. Нетрудно понять, что для порядкового номера хватит одного бита.

/* Protocol 3 (par) allows unidirectional data flow over an unreliable channel. */

#define MAX_SEQ 1	/* must be 1 for protocol 3 */
typedef enum  {frame_arrival, cksum_err, timeout} event_type;
#include "protocol.h"

void sender3(void)
{
  seq_nr next_frame_to_send;	/* seq number of next outgoing frame */
  frame s;	/* scratch variable */
  packet buffer;	/* buffer for an outbound packet */
  event_type event;

  next_frame_to_send = 0;	/* initialize outbound sequence numbers */
  from_network_layer(&buffer);	/* fetch first packet */
  while (true) {
        s.info = buffer;	/* construct a frame for transmission */
        s.seq = next_frame_to_send;	/* insert sequence number in frame */
        to_physical_layer(&s);	/* send it on its way */
        start_timer(s.seq);	/* if answer takes too long, time out */
        wait_for_event(&event);	/* frame_arrival, cksum_err, timeout */
        if (event == frame_arrival) {
                from_physical_layer(&s);	/* get the acknowledgement */
                if (s.ack == next_frame_to_send) {
                        from_network_layer(&buffer);	/* get the next one to send */
                        inc(next_frame_to_send);	/* invert next_frame_to_send */
                }
        }
  }
}

void receiver3(void)
{
  seq_nr frame_expected;
  frame r, s;
  event_type event;

  frame_expected = 0;
  while (true) {
        wait_for_event(&event);	/* possibilities: frame_arrival, cksum_err */
        if (event == frame_arrival) {
                /* A valid frame has arrived. */
                from_physical_layer(&r);	/* go get the newly arrived frame */
                if (r.seq == frame_expected) {
                       /* This is what we have been waiting for. */
                        to_network_layer(&r.info);	/* pass the data to the network layer */
                        inc(frame_expected);	/* next time expect the other sequence nr */
                }
                s.ack = 1 - frame_expected;	/* tell which frame is being acked */
                to_physical_layer(&s);	/* only the ack field is use */
        }
  }
}

Протоколы скользящего окна

Симплексные протоколы — это плохо, потому что данные хотим посылать в обе стороны, а если сделать два отдельных канала, то получится дороже. В случае с дуплексными протоколами в обе стороны могут ходить и обычные кадры, и служебные (ACK). В заголовке кадра будем хранить kind, чтобы различать типы кадров. Есть техника piggybacking: если мы хотим послать подтверждение и обычный кадр, то пошлём их вместе (подтверждение положим в поле ACK в заголовке кадра). В таком варианте нужно заводить отдельный таймер на тот случай, когда от нас ждут подтверждение, а мы не хотим посылать обычный кадр (в этом случае мы просто пошлём кадр с подтверждением). То есть, если нам пришло сообщение, то мы либо довольно скоро захотим сами что-то послать и приложим подтверждение, либо просто пошлём подтверждение по тику таймера.

Следующие три протокола относятся к протоколам скользящего окна. Суть в том, чтобы хранить два окна (диапазона порядковых номеров кадров) — посылающее и принимающее. Окно хранит номера кадров, которые мы можем послать/принять. Когда сетевой уровень просит что-то послать, мы даём очередному кадру номер, равный верхней границе посылающего окна, и увеличиваем эту границу. При получении подтверждения увеличиваем нижнюю границу. При получении пакета из принимающего окна оно сдвигается на единицу. При получении пакета не из принимающего окна такой пакет игнорируется.

Это всё общая идея, перейдём к конкретным реализациям.

Однобитовое окно

Простейший вариант, когда размер окна равен единице. В этом случае после отправки одного пакета мы не будем отправлять следующий, пока не получим подтверждения о доставке первого.

/* Protocol 4 (sliding window) is bidirectional and is more robust than protocol 3. */

#define MAX_SEQ 1	/* must be 1 for protocol 4 */
typedef enum {frame_arrival, cksum_err, timeout} event_type;
#include "protocol.h"

void protocol4 (void)
{
  seq_nr next_frame_to_send;	/* 0 or 1 only */
  seq_nr frame_expected;	/* 0 or 1 only */
  frame r, s;	/* scratch variables */
  packet buffer;	/* current packet being sent */
  event_type event;

  next_frame_to_send = 0;	/* next frame on the outbound stream */
  frame_expected = 0;	/* number of frame arriving frame expected */
  from_network_layer(&buffer);	/* fetch a packet from the network layer */
  s.info = buffer;	/* prepare to send the initial frame */
  s.seq = next_frame_to_send;	/* insert sequence number into frame */
  s.ack = 1 - frame_expected;	/* piggybacked ack */
  to_physical_layer(&s);	/* transmit the frame */
  start_timer(s.seq);	/* start the timer running */

  while (true) {
        wait_for_event(&event);	/* could be: frame_arrival, cksum_err, timeout */
        if (event == frame_arrival) { /* a frame has arrived undamaged. */
                from_physical_layer(&r);	/* go get it */

                if (r.seq == frame_expected) {
                        /* Handle inbound frame stream. */
                        to_network_layer(&r.info);	/* pass packet to network layer */
                        inc(frame_expected);	/* invert sequence number expected next */
                }

                if (r.ack == next_frame_to_send) { /* handle outbound frame stream. */
                        from_network_layer(&buffer);	/* fetch new packet from network layer */
                        inc(next_frame_to_send);	/* invert sender's sequence number */
                }
        }
             
        s.info = buffer;	/* construct outbound frame */
        s.seq = next_frame_to_send;	/* insert sequence number into it */
        s.ack = 1 - frame_expected;	/* seq number of last received frame */
        to_physical_layer(&s);	/* transmit a frame */
        start_timer(s.seq);	/* start the timer running */
  }
}

Протоколы с возвратом на N

Если у нас есть большая пропускная способность, небольшие кадры и большое время прохождения сигнала, то пропускная способность будет использоваться очень слабо, так как большую часть времени мы будем ждать подтверждение, прежде чем посылать очередной кадр. Поэтому будем посылать сразу много кадров не дожидаясь доставки/потери предыдущего. Размер посылающего окна больше единицы (но ограничен какой-нибудь константой).

Есть два подхода к обработке ошибок. Первый называется возвратом на N. Если с каким-то из посланных кадров случилась беда, то все остальные посланные кадры игнорируются, что соответствует единичному размеру входящего окна. Через какое-то время проигнорированные кадры будут перепосланы отправителем. Это плохо в ситуации, когда возможно большое количество ошибок.

В реализации есть ещё одно нововведение: у сетевого уровня не всегда есть данные для передачи, поэтому он будет генерить событие, когда хочет что-то передавать. Также его можно выключить, чтобы он ничего не генерил, если у нас заполнено всё окно.

/* Protocol 5 (pipelining) allows multiple outstanding frames. 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. */

#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. */
  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. */
  frame s;	/* scratch variable */

  s.info = 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 */

  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:	/* 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.  Check for this. */
                while (between(ack_expected, r.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();
  }
}

Протоколы с выборочным повтором

Второй вариант обработки ошибок называется выборочным повтором. Если потерялся/повредился кадр, то все следующие за ним получатель не игнорирует, а буферизует и шлёт на них подтверждения. Сломанный кадр будет перепослан, после чего получатель сможет восстановить нужную последовательность. Доставленные кадры перепосылать не потребуется.

Также можно посылать отрицательное подтверждение (NAK), в этом случае отправитель перепошлёт потерянный кадр до истечения таймаута.

/* 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[frame_nr % NR_BUFS];
  s.seq = 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 */
  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;

        case frame_arrival:	/* a data or control frame has arrived */
                from_physical_layer(&r);	/* fetch incoming frame from physical layer */
                if (r.kind == data) {
                        /* An undamaged frame has arrived. */
                        if ((r.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[r.seq % NR_BUFS] = r.info;	/* insert data into buffer */
                                while (arrived[frame_expected % NR_BUFS]) {
                                        /* Pass frames and advance window. */
                                        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 */
                                }
                        }
                }
                if((r.kind==nak) && between(ack_expected,(r.ack+1)%(MAX_SEQ+1),next_frame_to_send))
                        send_frame(data, (r.ack+1) % (MAX_SEQ + 1), frame_expected, out_buf);

                while (between(ack_expected, r.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();
  }
}

Верификация протоколов

Нам про это очень мало рассказывали.

Конечные автоматы

Состояние процесса будет хранить в себе значения всех переменных в программе. Также будет состояние канала (какой кадр передаётся и передаётся ли). Множество переходов — все возможные переходы между состояниями вследствие каких-либо событий. Также пометим начальные состояния. Получим автомат, в котором можно анализировать достижимость различных состояний. Возможны следующие ошибки:

• состояние, в котором нельзя определить, куда переходить (неполнота протокола)
• состояние, из которого нет выхода (тупик)
• состояние с переходом по событию, которое никогда не может произойти (лишний переход).

Анализ достижимости позволяет обнаружить такие проблемы.

Сети Петри

Нам про это два слова сказали, так что вряд ли понадобится. Есть в Таненбауме, если очень нужно.