《计算机网络》读书笔记（三）
数据链路层
数据链路层需要完成的功能包括三个方面：1.向网络层提供一个定义良好的服务接口；2.处理传输错误；3.调节数据流，确保接受方不会被淹没。
数据链路层提供三种服务：1.无确认的无连接的服务（绝大多数LAN使用）；2.有确认的无连接的服务（比如无线系统）；3.有确认的面向连接的服务。
数据链路层的几种成帧方法：1.字符记数法；2.含字节填充的分界符法；3.含位填充的分界标志法；4.物理层编码违例法。
流控制包括两种：1.基于反馈的流控制（数据链路层使用）；2.基于速率的流控制。
错误检测和纠正：1.纠错码，也叫做向前纠错；2.检错码。海明距离：为了检测d个错误，需要一个距离为d+1的编码方案；为了纠正d个错误，需要一个距离为2d+1的编码方案。 CRC（Cyclic Redundancy Check，循环冗余校检码）。。。。。。。更多等带以后添加基本数据链路协议，参照后面的1.c，是一个支持重传的肯定确认协议。
滑动窗口协议：所有滑动窗口协议的本质是，在任何时刻，发送方总是维持着一组序列号，分别对应准许它发送的帧，我们称这些帧在发送窗口之内，类似的，接收方也维护着一个接受窗口。三个例子：1.1位滑动窗口协议；2.使用回退N帧技术的协议；3.使用选择性重传的协议。详细参照后面的三个C程序。
协议验证：1.有限状态机模型：许多协议模型中用到的一个关键概念是有限状态机（finite state machine），每个协议机（即发送方或接受方）在任何一个时刻，总是处于一种特定的状态，它的状态是由所有变量的值组成的，其中也包括程序计数器；2.Petri网模型：一个Petri网有4个基本元素：库所（place），变迁（transition），弧（arc）和标记（token）。
HDLC（High-level Data Link Control，高级数据链路控制）：所有协议都是面向位的，并且为了确保数据的透明性，它们都使用了位填充。
PPP（Point-to-Point Protocol，点到点协议）：Internet中大量使用该协议，PPP提供了三类功能：1.一种支持错误检测的成帧方法；2.一个LCP链路控制协议，支持同步和异步线路，也支持面向字节的和面向位的编码方法；3.一种协商网络层选项的方法，并且协商方法与所使用的网络层协议独立，所选择的方法对于每一种支持的网络层都有一个不同的NCP（网络控制协议）。
//protocol.h typedef enum {false, true} boolean; /* boolean type */ typedef struct { /* frames are transported in this layer */ /* Wait for an event to happen; return its type in event. */ /* Fetch a packet from the network layer for transmission on the channel. */ /* Deliver information from an inbound frame to the network layer. */ /* Go get an inbound frame from the physical layer and copy it to r. */ /* Pass the frame to the physical layer for transmission. */ /* Start the clock running and enable the timeout event. */ /* Stop the clock and disable the timeout event. */ /* Start an auxiliary timer and enable the ack_timeout event. */ /* Stop the auxiliary timer and disable the ack_timeout event. */ /* Allow the network layer to cause a network_layer_ready event. */ /* Forbid the network layer from causing a network_layer_ready event. */ /* Macro inc is expanded in-line: Increment k circularly. */ //1.c void receiver3(void) #define MAX_SEQ 1 /* must be 1 for protocol 4 */ #define MAX_SEQ 7 /* should be 2^n - 1 */ static boolean between(seq_nr a, seq_nr b, seq_nr c) static void send_data(seq_nr frame_nr, seq_nr frame_expected, packet buffer[]) s.info = buffer[frame_nr]; /* insert packet into frame */ void protocol5(void) enable_network_layer(); /* allow network_layer_ready events */ switch(event) { case cksum_err: break; /* just ignore bad frames */ } #define MAX_SEQ 7 /* should be 2^n - 1 */ s.kind = fk; /* kind == data, ack, or nak */ enable_network_layer(); /* initialize */ case frame_arrival: /* a data or control frame has arrived */ while (between(ack_expected, r.ack, next_frame_to_send)) { case cksum_err: case timeout: case ack_timeout:
#define MAX_PKT 1024 /* determines packet size in bytes */
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 */
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;
void wait_for_event(event_type *event);
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);
#define inc(k) if (k < MAX_SEQ) k = k + 1; else k = 0
#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) {
stop_timer(s.ack); /* turn the timer off */
from_network_layer(&buffer); /* get the next one to send */
inc(next_frame_to_send); /* invert next_frame_to_send */
}
}
}
}
{
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); /* send acknowledgement */
}
}
}
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; /* frame expected next */
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); /* frame_arrival, cksum_err, or 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 seq number expected next */
}
if (r.ack == next_frame_to_send) { /* handle outbound frame stream. */
stop_timer(r.ack); /* turn the timer off */
from_network_layer(&buffer);/* fetch new pkt 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 */
}
}
typedef enum {frame_arrival, cksum_err, timeout, network_layer_ready} event_type;
#include "protocol.h"
{
/* 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);
}
{
/* Construct and send a data frame. */
frame s; /* scratch variable */
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 */
}
{
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;
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 */
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 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();
}
}
#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; /* initial value is only 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 */
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;
ack_expected = 0; /* next ack expected on the inbound stream */
next_frame_to_send = 0; /* number of next outgoing frame */
frame_expected = 0;
too_far = NR_BUFS;
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;
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);
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;
if (no_nak) send_frame(nak, 0, frame_expected, out_buf); /* damaged frame */
break;
send_frame(data, oldest_frame, frame_expected, out_buf); /* we timed out */
break;
send_frame(ack,0,frame_expected, out_buf); /* ack timer expired; send ack */
}
if (nbuffered < NR_BUFS) enable_network_layer(); else disable_network_layer();
}
}