计算机网络复习(自顶向下)知识点总结(一天一夜超8000字,详细知识点总结,带重点标注目录)

复习目录

在这里插入图片描述

一、计算机网络基本概念

在这里插入图片描述

  • 本章节组织结构:基本概念、组件-网络边缘-网络核心-重点概念(时延-丢包-吞吐量)-协议概念

1.1 认识英特网

概括:由通信链路和分组交换机连接巨大数量的端系统构成的巨大转发网络

构成:

  • 主机(host)=端系统(end system):接入计算机网络的智能设备,个人电脑、智能家电等;又根据功能大致分为客户(client)、服务器(server)
  • 通信链路(communication link):连接网络的线路—实体到实体的一条链路构成路径(path/route)
  • 分组交换机(packet switch):路由器(router)(圆形X表示)和链路交换机(switch)(方块X表示)
  • 服务提供商(Internet Service Provider,ISP):提供接入网络的服务,比如三大运营商等
  • 因特网工程任务组(Internet Engineering Task Force,IETF):负责因特网协议和规范的制订,制订文件统一为RFC(Request For Comment)+编号
  • 分组概念(packet):发送端将长信息截断打包
  • 传输速率(Transmission Rate):特指将数据搬移到链路的转化速度(bps),注意与传播速率(Propagation rate)区分

服务:

  • 分布式应用程序(distributed application):基于计算机网络构建的应用,面向网络中的多个对象提供数据交换的应用,如:Web应用,联网的app等
  • API支持:计算机网络包含对应用接入接口的支持,这部分应该被实现在端系统中
  • 各种计算机网络—协议(protocol):定义在两个或多个通信实体之间交换的报文格式和次序,以及发送和接收以及其他事件应该执行的操作——控制网络信息接收和发送,比如TCP(Transmission Control Protocol)传输控制协议、IP(Internet Protocol)网际协议等

1.2 网络边缘

  • 边缘路由(edge router):负责将端系统接入网络的第一个路由器
  • 边缘组:由主机/端系统+接入网构成(家庭组、企业组等)
  • 接入技术、物理媒介:略

1.3 网络核心

核心:互联因特网端系统的分组交换机和通信链路构成的网状结构

需要了解分组转发网络相关概念

  • 分组交换机的输出缓存/队列(output buffer/queue):收到信息先保存在缓存中,等转发端口有空在依次发送
  • 存储-转发传输(store-and-forward transmission):分组交换机先全部接收一组信息,存储,然后在发送端空闲时转发搬移到下一段链路上(产生传输延迟(transmission delay)下面讲)
  • 排队时延(queuing delay):由于节点存储有限,如果不能及时转发出去,会导致收到的信息等一段时间才能转发出去
  • 丢包(packet loss):大概率由于缓存满,导致新接收的包被丢弃
  • 转发表(forwarding table):收到的信息中含由目的地信息,通过查询转发表获取应该转发到的目的链路转发出去。通过路由选择协议(routing protocol)自动更新转发表

电路交换网络方式:通过频分复用/时分复用技术共享链路,固定分配

1.4 ⭐时延、丢包和吞吐量

端到端时延(dend-end):从一个主机发送信息到另一个主机消耗的时间,由以下4部分组成:

  • 节点处理延时(node processing delay)

  • 排对延时(queuing delay)

  • 传输延时(transmission delay):从节点把信息搬移到链路的时间dtransmission=N*L/R(N是节点个数,L信息长度、R是传输率)

  • 传播延时(propagation delay):从链路一端到另一端的时间(Lenght/C)

  • [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-qpQtmqdN-1641366431459)(C:Users86191AppDataRoamingTyporatypora-user-imagesimage-20220105143313582.png)]

  • 瓶颈链路(bottleneck link)和瓶颈传输速率:传输速率应该小于节点中最小的传输速率,为了避免缓存堆积(不确定)

丢包(packet loss):一次信息传输时中途丢失

  • 丢包(packet loss):大概率由于缓存满,导致新接收的包被丢弃

吞吐量(throughput):接收到的信息长度/时间—bps

  • 瞬时吞吐量
  • 平均吞吐量

1.5 协议层次和服务模型

协议层次(5层因特网协议栈)

层次 相关协议 封装的包
应用层(application layer) HTTP、SMTP、DNS等 报文(message)
传输层(transmission layer) TCP、UDP 报文段(segment)
网络层(network layer) IP 数据报文(datagram)
链路层(linked layer) DOSIS 帧(fame)
物理层(physical layer)

一个层的所以协议称为一个协议栈(protocol stack)

  • 交换机(switch)只需要下两层协议,不需要寻址
  • 路由器(router)需要下面三层协议,需要根据解析IP找到转发链路目标
  • 封装:上层协议的数据被下层附加信息打包的过程
  • 有效载荷字段(payload field):除了附加的包头,即指包体内容

1.6 安全和历史(略)

二、应用层

在这里插入图片描述

2.1 应用层协议原理

相关概念:

  • 应用层体系架构(application architecture):客户-服务器架构(B/S)、点对点架构(P2P)
  • 进程通信:进程作为通信主体,发起通信的作为客户端,等待连接的作为服务器,通过套接字(socket)这个软件接口从网络中收发信息(由4个方面:传输率、吞吐量、定时、安全…)
  • 寻址:主机地址(IP标识)+进程端口号(port number)
  • 容忍丢失应用(loss-tolerant application):允许一部分丢包
  • 带宽敏感应用(bandwidth-sensitive application):要求高带宽,不然无法工作
  • 应用层的应用基本上都以TCP作为传输层支持(不确定)

应用层协议内容:

  • 定义了报文类型(请求/响应)
  • 定义了报文语法(每个字段含有什么)
  • 定义了报文的含义(字段内容如何解读)
  • 报文的响应规则(合适发送,如何发送)

Web是一种B/S应用=HTML标准+浏览器+服务器+HTTP协议+…(协议只是应用的一部分)

2.2 ⭐Web和HTTP协议

超文本传输协议(Hypertext Transfer Protocol,HTTP):定义了Web服务器返回/Web客户端请求 内容的方式,以及请求/响应报文的格式,它是一种无状态协议(stateless protocol),每次收发都不记录请求者状态(RFC 1945、RFC 2616)

  • 词汇:web page、web browser、web server、URL、base HTML file
  • 请注意:非持续性连接(non-persistent connection)、持续性连接(persistent connection)、并发连接、流水线模式和HTTP版本
  • (待添加)

HTTP报文:

  • 请求报文头部
实体内容 具体解读
GET xxx/xxx/index.html HTTP/1.1 GET请求方式、URL、HTTP版本
Host:www.someschool.edu 请求主机对象
Connection:close 使用非持续性连接
User-agent:Mozilla/5.0 代理/版本(浏览器)
  • 响应报文头部
实体内容 具体解读
HTTP/1.1 200 OK HTTP版本、状态码、状态信息
Connection:close 使用非持续性连接
Date:True,09 Aug 2011 15… 时间信息
Server:Apache/2.2.3(Centos) 服务器软件信息
Lost-Modified:Tue,09,Aug… 最后一次更新时间
Content-Type : text/html 返回内容的类型
  • 报文主体和头部之间用两个换行隔开

Web缓存器(Web cache)/代理服务器(proxy server):在靠近客户端建立一个缓存服务器,短期内已经访问过的页面可以直接从缓存服务器获取,流程如下

  1. 建立到缓存服务器的TCP连接,发送请求
  2. 缓存查找有无请求的资源,若有直接响应,节约时间
  3. 没有找到,通过缓存服务器(这时叫代理服务器更为恰当)向请求的目标建立TCP连接,转发请求,获得目标响应
  4. 先在缓存中保存一份,然后响应发送到客户

优点:

  • 减少了客户请求响应时间(特别是对于频繁请求的热门资源)
  • 降低了带宽压力-》内容分发网络(Content Distribution Network,CDN)

流量计算?(不确定)

2.3 FTP和SMTP

  • FTP是关于终端间文件传输的协议,服务器用21端口;SMTP是邮件发送的协议,用25端口;SMTP属于推送协议(push protocol)、HTTP属于拉取协议(pull protocol)一般服务器采用80端口…

2.4 DNS目录服务

域名系统(Domain Name System ,DNS):进行主机名到IP地址的转化的目录结构(RFC 1034/RFC 1035)

  • 一个由分层的DNS服务器(DNS Server)实现的分布式数据库
  • 使得主机能够查询分布式数据库的应用协议

查询过程:

  1. 对于一个网络应用,需要将主机转化成IP时,打开DNS客户端(浏览器自动完成)
  2. 从URL(这里一Web应用为例)读取主机名,传给DNS客户端
  3. 向DNS服务器发送一个包含主机名的查询请求
  4. 收到服务器回复的IP
  5. 网络应用向该IP地址+相应端口(Web默认80)发起TCP连接请求

小Tips:

  • DSN提供主机别名服务、负载分布服务等

  • 它使用的是UDP协议,服务器端口为53

DNS服务器结构

等级 具体内容
根级别(root) 全球13台
顶级域(Top-Level Domain,TLD) .com、.org、.edu等
权威级别(企业级) amazom.org、scu.edu

本地DNS服务器(Local DNS Server):为本地一定范围内的主机提供查询范围——相当于Web缓存——即DNS缓存机制(DNS caching)

  • 主要查询方式有两种:递归查询(recursive query)、迭代查询(iterative query)
  • [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-iHTtnzTF-1641366431459)(C:Users86191AppDataRoamingTyporatypora-user-imagesimage-20220105150605856.png)]

DNS服务器资源记录(Resource Record,RR)

  • 具体为四元组形式(Name,Value,Type,TTL)
  • 根据Type=A(Name标识主机名)、CNAME(主机别名)、NS(域名)、MX(邮件主机名)
  • [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-C3Z0iiar-1641366431460)(C:Users86191AppDataRoamingTyporatypora-user-imagesimage-20220105150618263.png)]

2.5 P2P(略)

三、⭐传输层(全重点)

在这里插入图片描述

3.1 概述和传输层服务

传输层为不同主机上的进程提供了逻辑通信(logic communication);而应用层负责为不同主机之间通信

传输层服务:

  • 传输层的下层网络层中的IP协议尽力而为的交互服务(best-effort delivery service)不能保证数据到达的顺序、完整性、设置无法保证送达
  • UDP仅能确保数据交付和差错校验,不保证数据完好
  • TCP提供可靠的数据传输(reliable data transfer),并且还有流量控制、序号确认、定时器等机制,TCP确保数据准确有序到达,并且提供拥塞控制服务

3.2 多路复用/分解

  • 多路分解(demultiplexing):传输层解析报文字段定向到指定进程套接字的过程
  • 多路复用(multiplexing):传输层从不同套接字接收message报文,封装向网络层转发的过程
  • 端口(port):0~1023固定用法,周知端口号(well-know port);1024~65535供客户进程使用

3.3 无连接的UDP

应用UDP的优点:

  • 通过应用层实现对数据发送更有效的控制
  • 无需建立连接,更快
  • 无连接状态
  • 分组首部开销小——UDP首部8字节,TCP首部20字节?(不确定)

UDP报文结构:

  • 8Byte x 8 = 64bits
  • 2Byte 源接口+2Byte 目标接口
  • 2Byte 长度+2Byte 检验和

校验和:全部内容求和(注意反卷),然后取反

接收方检验时:全部带校验和求和结果为全1

3.4 可靠数据传输原理(rdt+GBN+SR)

可靠数据传输协议(reliable transfer protocol,rdt):TCP作为其一种实现

接下来通过层层升级解释可靠数据传输协议的实现技术:

  • rdt1.0:假设底层通信信道可靠,直接发送和接收数据即可(rdt_send(data):packet=make_pak(data);udt_send(packet)/rdt_rcv(packet):extract(packet,data);deliver_date(data)😉
  • rdt2.0:假设为有bit差错的信道,使用——差错校验+接收方发送ACK/NAK+重传机制(每次发送完需要等接收方发送回ACKorNAK后才能继续发送,这种模式叫做停等模式(stop-and-wait))
  • rdt2.1:考虑发送回的确认包有可能错误,导致重传时不能确定是新发送的包还是重传包,因此引入组序号机制
  • rdt2.2:取消NAK,改为发送上一次成功的ACK和序号
  • rdt3.0:添加了丢包的考虑,为防止确认包丢失长时间等待,发送方发送时启动倒计数定时器(countdown timer)——启动定时器,中断响应定时器或者接收成功取消定时器

尽管到rdt3.0已经大致实现了可靠数据传输,但是停等模式的性能堪忧,于是进一步探究流水线模式(pipelining)

  • 回退N步(Go-Back N,GBN):N为发送方窗口长度(window-size),因此也叫滑动窗口协议(sliding window protocol)
  • 选择重传机制(Selective Repeat,SR):有选择性的重新传输超时的组

GBN:

  • 发送方:上层调用时,判断发送窗口是否满,满了一般加入发送缓存/或者满了就不允许上层调用;收到ACK采用累计确认机制(comulative acknowledgement),该ACK前面的组也确认收到;超时时重发所有没有被确认的包,每收到一个ACK更新一次定时器;
  • 接收方:只维护一个接收口,一次只接收顺序到达的一个包;其他情况(乱序,包错误)返回上一次接收成功的包序号ACK,不缓存乱序包
  • 问题:不适用于开始就出差错的情况,会导致大量重传;适用于返回包有问题情况

SR:

  • 发送方:上层调用同理;收到ACK将该包标记为确认,不在重发;为每个发送的包设置定时器,超时只重复一个包;
  • 接收方:缓存乱序包,等到前面的空缺包到达一起递交;正确收到一个包返回对应序号的ACK
  • 问题:不适用于返回包有问题情况和乱序较多情况(不确定)

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-oILA5id1-1641395557887)(C:Users86191AppDataRoamingTyporatypora-user-imagesimage-20220105223813345.png)]

3.5 面向连接的TCP

TCP集以上多种技术于一身:差错校验、重传、累计确认、首部字段确认号/序号…面向连接——在传输信息前需要建立连接,而且它还属于

  • 全双工传输(full-duplex service)
  • 点对点传输(point-to-point)
  • 需要三路握手(three-ways-handshake)

一些概念:

  • 最长报文长度(Maximum Sagement Size,MSS)=最大传输单元(Maximum Transmission Unit,MTU)- 40字节(TCP/IP报文首部)(一般等于1460)
  • 序列号(sequence number):基于发送报文段的第一个字节在发送缓存中的位置
  • 捎带(piggybacked):在服务器对客户的请求确认包中捎带服务器返回给客户的数据报文

TCP报文解读:

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Pzck91Ek-1641395557888)(C:Users86191AppDataRoamingTyporatypora-user-imagesimage-20220105223836295.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-jBA5Gwy1-1641395557888)(C:Users86191AppDataRoamingTyporatypora-user-imagesimage-20220105223859489.png)]

三路握手过程:

  • Send:SYN=1,seq=client_isn
  • Receive:SYN=1,seq=server_isn,ack=client_isn+1
  • Send:SYN=0,seq=client_isn,ack=server_isn+1

定时器设置——往返时间估计(不确定,待添加)

特殊功能:

  • 超时间隔加倍:当定时器超时,重发包定时器设置为两倍
  • 快速重传机制:当重复收到3个冗余ACK时,立刻重发该ACK下一个包
  • 流量控制(flow control service):由于接收方缓存有限,用以控制发送方流量(更改发送方发送窗口大小)以消除接收方缓存溢出的方法
  • 拥塞控制(congestion control):由于IP网络的拥塞而遏制了发送方发送窗口的大小,TCP自动调节发送流量

流量控制具体解析

  • 发送方维护一个标识接收方剩余缓存的变量为接收窗口(receive window,rwnd)
  • 每次接收方返回ACK时都携带自身剩余缓存信息(rwnd=RevBuffer[总缓存大小]-(LastByteRevd[最新接收到的数据位置]-LastByteRead[最新被上层读取的数据位置])
  • 发送方确保发送窗口小于rwnd,即LastByteSent[最新待发送的位置]-LastByteAcked[最新确认的位置]<=rwnd
  • 特别的,当rwnd为0时,发送方仍需要发送一个长度为1字节的报文,目的为了使得接收方返回ACK说明自己缓存是否被清空(部分清空)

3.6 TCP拥塞控制

拥塞控制(congestion control)具体解析:

  • 又发送方维护一个变量——拥塞窗口(congestion window,cwnd),对TCP发送方向网络中的发送流量的速率作出限制,和流量控制一起约束,有发送方swnd<=min{rwnd,cwnd}
  • TCP确认丢包(一般通过超时、三次冗余ACK)以认为网络拥塞,然后限制速度(降低拥塞窗口大小),相反收到ACK表示网络良好,增长窗口大小——这种特性称为自计时(self-clocking)
  • 拥塞控制三原则:丢包降速、ACK增速、从当前cwnd开始降速,然后逐步试探拥塞情况(不确定)

TCP拥塞控制具体算法(TCP congestion control algorithm):

  1. 慢启动:从一个MSS开始,每个ACK增加一个MSS(第一轮一个,第二轮两个,第三轮四个…每次都会多收到一倍的ACK);直达丢包发生;记录此时慢启动阈值ssthresh=cwnd/2;然后有两种应对方法——当超时丢包:将cwnd重新设置为1然后重新慢启动,到达阈值时采用拥塞避免算法(2);冗余ACK采用快速恢复方法(3)(这里按题目来)
  2. 拥塞避免:丢包后,又一次慢启动到达阈值时,采用线性增长方法,每个RTT都受到ACK后+1MSS,直到丢包发生,更新阈值重新慢启动(1)/采用快速恢复(3)
  3. 快速恢复:三个冗余ACK后,不重新到1个MSS,而是直接设置为当前cwnd/2+3(记录的冗余ACK数量),然后开始线性变化同(2),丢包同上

该拥塞控制特性为线性增-乘性减(Additive-Increase,Multiplicative-decrease,AIMD)

四、⭐网络层(全重点)

在这里插入图片描述

4.1 概述

本章节线路——

网络层服务-构造网络层分组交付的两种方法-路由器工作原理和网际协议-转发和路由选择-路由选择算法和协议-广播和多播

  • 转发:当一个分组到达路由器一个输入时,将其移到另一个输出链路上的过程
  • 路由选择(routing):当分组从发送方流向接收方,网络层(所有路由器)决定的该分组应该经过的路径(最短路选择,详情看路由选择算法(routing algorithm)
  • 转发表(forwarding table):由路由器维护的,通过检索分组目的地首字段决定输出链路的对照表
  • 链路交换机(link-layer switch):实现到链路层的交换机,只根据链路层信息转发,详见下一章
  • 路由器(router):基于网络层地址实现转发的设备

网络层服务模型(network service model):定义了分组在发送与接收端之间的网络层特性

  • 确保交付、有交付时延上限、有序分组交付、确保最小带宽、保证最大延时抖动、安全性等
  • 但是很遗憾,最常用的IP协议只能保证尽力而为(best-effort-service)的服务
  • 除此之外还有:恒定比特率(Constant Bit Rate,CBR)ATM网络服务,可用比特率(Available Bit Rate,ABR)ATM网络服务这些有保证的服务

网络层和传输层差别

  • 传输层面向不同主机进程通信,而网络层只负责把数据送到对应主机
  • 网络层不同时提供有连接和无连接的服务,而传输层可以TCP、UDP都能用
  • 网络层在核心网络(路由器)中和端系统都有实现,传输层只在端系统(主机)

4.2 虚电路和数据报网络

虚电路(Virtual-Circuit,VC)网络(VCN):有链接的网络服务,在发送方和接收发之间维护一条链路

  • 源主机和目标主机之间的路径(一系列路由器和链路)
  • VC号(标识不同路径不同链路)
  • 转发表(记录一条路径入VC和出VC号,跨过该路由的每条路径都需要一组VC对应)

数据报网络(datagram network):无连接状态的网络,发送发只负责将含有目标IP地址的datagram包发送给下层输送到网络中即可,不需要先建立维护一条路径,会有路由器自动根据转发表转发到目标地址

  • 转发表前缀(prefix)匹配-最长前缀匹配原则(loggest prefix matching rule):将目标地址和转发表中最长匹配到的前缀做为转发目标,把分组转发到对应的链路

4.3 路由器工作原理

转发功能(forwarding function):组成——输入/输出端口(指接收/发送数据的物理接口)、交换结构(将输入与输出相连的内部结构)、路由选择处理器(维护路由选择表以及连接链路状态和更新路由表的处理器)、以及相应的执行路由选择协议,响应输入转发的软件——又可分为路由器转发平面(router forward plane)和路由器控制平面(router control plane)

输入端口、输出端口(略)

交换结构

  • 经内存交换
  • 经总线交换
  • 经网状结构交换

一些名词(不重要):负责调度(packet schedule)、服务质量保证(quality-of-service guarante)、弃尾(drop tail)策略、主动队列管理(Active Queue Managerment,AQM)、随机早期检测(Random Early Detection,RED)

4.4 网际协议

因特网网络层三大部件:

  • IP协议(使用无连接的IP协议提供服务,尽力而为的服务,啥都不保证,需要在传输层TCP保证)
  • 路由选择部分
  • 网络层差错控制和信息报协议,互联网控制报文协议(ICMP)

IP协议数据报格式

- [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-knvk6ZGM-1641466958705)(C:Users86191AppDataRoamingTyporatypora-user-imagesimage-20220106181023011.png)]

- [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-87y83pmn-1641466958705)(C:Users86191AppDataRoamingTyporatypora-user-imagesimage-20220106181217099.png)]

- [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0utUxHwY-1641466958706)(C:Users86191AppDataRoamingTyporatypora-user-imagesimage-20220106181240492.png)]

相关概念

  • 接口(interface):实体节点与物理链路之间的边界,IP地址与接口相关联,而不是和主机相关联
  • 子网(subnet):具有相同前缀IP的多个相互连接的接口构成一个子网,比如223.1.1.0/24,表示前24为前缀相同的接口组成了223.1.1.0这个网段的子网,后8位全零标识子网,全1表示广播地址
  • 子网掩码(network mask):定义子网前缀范围,如前24为全1,取得一个IP求与运算可得子网前缀,方便匹配
  • 无类别域间路由选择(classless Inter Domain Routing,CIDR):将子网划分为如下形式:a.b.c.d/x
  • 之前使用的分类编制(classfull addressing):子网的前缀只能为1,2,3个字节

网络层接入:

  • ⭐️地址块分配方法
  • 动态主机配置
  • 网络地址转换

地址块分配方法(由大到小逐个分配,详见书)

动态主机配置协议(Dynamic Host Configuration Protocol,DHCP):通过一台DHCP服务器为接入的主机动态分配IP地址的方法(接入的主机可获得不同的随机分配的IP或固定IP),使得接入的新主机获取到IP地址、第一跳路由器、本地DNS服务器地址等,也叫即插即用(plug-and-paly)的协议

  1. DHCP服务器发现:由接入主机启动DHCP客户端发送DHCP发现报文(DHCP discover message)广播到目的地址全1地址,源地址标识为全0,通过链路交换机/子网路由器广播
  2. DHCP服务器提供:服务器收到发现报文,用一个DHCP提供报文(DHCP offer message)响应,同样广播全1地址
  3. DHCP请求:客户选择一个提供报文,向该服务器发送DHCP请求报文(DHCP request message)
  4. DHCP ACK:被选中的服务器用DHCP ACK报文(DHCP ACK message)进行响应,证实其参数

网络地址转换(Network Address Translation,NAT):应对IP不够分配的情况,允许本地子网地址转换为统一唯一的IP地址共用一个公网IP

  • 通过NAT路由器维护一张NAT转换表(NAT translation table)
  • 转换对应如:10.0.0.1:3445(本地IP:进程端口)《——》138.76.29.7:5001(共用公网IP:随机绑定端口),可随机分配216个端口

ICMP因特网控制报文协议(不重要)、IPv6兼容IPv4

4.5 路由选择算法

  • 默认路由器(default router):主机连接的路由器,第一跳路由器(first-loop router)

  • 源路由器(source router):发送方的默认路由器

  • 目的路由器(destination router):接收方的默认路由器

路由选择问题->最低费用路径(least-cost path)问题->最短路径(shortest path)问题

路由选择问题分类:

  • 全局/分散式路由选择算法(global/decentralized routing algorithm)-链路状态(Link-State,LS)算法(全局)/距离向量(Distance-Vector,DV)算法(分散式)
  • 静态/动态路由选择算法(static/dynamic routing algorithm)
  • 负载敏感/负载迟钝(load-sensitive/load-insensitive)

LS算法和DV算法详情见书(内容实在是太多了,比较复杂,有考的概率)

LS算法对应OSPF(开放最短路经优先协议)(Open Shortest Path First)

DV算法对应RIP(路由选择信息协议)(Routing Information Protocol)

五、链路层

在这里插入图片描述

5.1 链路层概述

链路层概念和技术-差错检测和纠正-多路访问链路和协议-交换局域网

  • 节点(node):能运行链路层协议的任何设备(如主机、路由器、交换机、WiFi接入点)
  • 链路(link):沿通信路径连接两个节点的通信信道
  • 链路层帧(frame):在链路层封装的包

链路层提供的服务:

  • 成帧(framing):提供将上层数据添加相关标准封装的功能
  • 链路接入:媒体访问控制协议(Medium Access Control,MAC)协议:规定帧在链路上的传输规则
  • 可靠交付
  • 差错检验和纠正技术

链路层主体在网络适配器(network adapter)也叫网络接口(network Interface Card NIC)上实现,其核心是链路层控制器,实现了许多链路层服务(成帧、链路层接入、差错检测)的专用芯片

5.2 差错检测和纠正技术

  • 比特级差错检测和纠正(bit-level error detection and correction)
  • 差错检测和纠正比特(Error-Dection and Correction,EDC):保护比特免受差错的技术

相关技术

  • 奇偶校验位(parity bit):奇校验加上校验位使得有奇数个1,偶校验则加上校验位有偶数个1

  • 二维奇偶校验(two-dimensioned parity):

  • [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-8N7Dw1Zk-1641478224215)(C:Users86191AppDataRoamingTyporatypora-user-imagesimage-20220106212559251.png)]

  • 校验和:因特网校验和(Internet checksum):将k比特整数加起来得到的和作为差错检测位(TCP和UDP使用16bit一组反卷求和结果取反作为校验和,对所有字段求和(首部和数据段))

  • 循环校验冗余(Cyclic Redundancy Check,CRC):也叫多项式编码(polynomial code)

循环冗余校验码计算方法:

  1. 双方约定一个生成多项式(generaor)——r+1位比特,称为G(首位一定为1)
  2. 发送的数据D后添加r个0
  3. 使用D添加0后除以G,使用XOR除法
  4. 求得余数R作为CRC比特,和附加在原D后
  5. 接收方用收到的D连接R,除以G得0判断为正确
    在这里插入图片描述

5.3 多路访问链路和协议

点对点链路(point-to-point):由单个发送方和单个接收方组成的通信链路(如PPP协议,高级数据链路控制(high-level data link control,HDLC)

广播链路(broadcast link):多个发送方和接收方都连接到相同单一的共享链路(涉及多路访问问题(multiple access problem),相关的多路访问协议(multiple access protocol)分三类如下

  • 信道划分协议(channel partioning protocol)——时分多路复用(TDM)、频分多路复用(FDM)、码分多路复用(CDMA)等
  • 随机接入协议(random access protocol)——ALOHA协议、载波侦听多路访问协议(CSMA)
  • 轮流协议(taking-turns protocol)——轮询协议(polling)、令牌传递协议(token-pass)

协议共有特点:

  • 只有一个使用者,独占带宽
  • 多个平分
  • 分散,不会因为一个节点损害而不能使用
  • 简单,实现简单

5.4 交换局域网(MAC、交换机)

通过链路层寻址和地址解析服务(ARP,将IP地址转换成链路层地址)实现交换局域网

  • MAC地址:又叫LAN地址、物理地址(physical address)、长度为6个字节

  • 地址解析服务(Address Resolution Protocol,ARP):通过输入目标IP查找在子网中的节点MAC地址,只查询子网中的MAC地址;主机中维护一张ARP对照表(ARP Table)(IP地址,MAC地址,TTL)

  • 通过ARP服务查找MAC过程(通过发送和返回ARP分组):

    1. 网络层传输到链路层获取到IP,链路层通过该目标IP+广播MAC地址(全1),广播到子网所有接口
    2. 目标IP的节点获取到该请求返回自身MAC地址,发送一个响应ARP分组
    3. 查询主机获取响应得到目标MAC地址,更新ARP表,发送IP数据报
    4. 链路层获取到IP数据报,添加刚刚获取到的MAC地址封装发送

    MAC目标地址只会在同一子网中,不同子网的目标IP会查询到边缘出口路由器的MAC地址

交换机的转发和过滤:

  • 过滤器(filtering):决定一个帧应该转发到某个接口还是应该丢弃的功能

  • 转发(forwarding):决定一个帧应该被导向到哪个接口

  • 交换机表(switch table)(MAC地址、接口、时间)基于MAC地址的转发,三者情况

    1. 从x接口输入的包MAC地址查找不到,广播到所有接口
    2. 查找到为x接口,直接丢弃
    3. 查找到输入MAC的对应接口为y,从y接口输出

交换机自学习特性,过程:

1. 表初始为空
2. 对于每个输入帧,记录其源MAC地址和接口号,以及输入时间
3. 一段时间后若没有该MAC地址消息,删除该MAC对照

优点:

  • 消除了碰撞
  • 异质的通信链路
  • 能够管理

结尾

作者长期更新,如果觉得本文还算不错的话,请给我一个大大的赞!!!
如果非常赞同这篇文章,请关注我,持续了解更多精彩博文!!!

祝大家期末必胜呀!!!没有学计算机网络的小伙伴也可以先收藏,说不定以后就学到了,作为知识点手册也可以的!!!

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇
下一篇>>