计算机网络 复习提纲（完整版）

第一章 概述

计算机网络：利用通信线路和通信设备，将地理位置和功能不同的多台计算机互联起来，用完善的网络软件实现资源共享和信息传递的网络。
组成：计算机，网络操作系统，传输介质，网络软件（不可缺少）
通信子网，资源子网，通信协议。
p2p：对等网络，即是终端又是服务器。传统网络客户端只能从服务器下载数据，在p2p网络中终端平等，可以从其他任意设备来下载文件，每个节点都可以存储，传输和接收文件，属于分布式网络。
OSI参考模型：开放式系统互联模型，分为七层：
物理层，数据链路层，网络层，传输层，会话层，表示层，应用层。
在每一层中，用户实现该层功能的活动元素被称为实体，可以是软件实体也可以是硬件实体。同一层次，完成相同功能的实体为对等实体。
不同主机上的相同层次为对等层，对等层存在“协议”关系，被称为对等协议。对等层之间的通信是“虚拟通信”，实际上是通过使用他们的下一层提供的服务来实现的，但是看起来好像是各层平行独立地互相通信。
SAP：服务访问点，N层的服务访问点是N层为N+1层提供服务的地方，N+1层调用接口来获取N层的服务。每一层的SAP都有唯一标明的地址，且每一层可能有多个SAP。
物理层：最底层，主要定义系统的电气，机械，过程和功能标准，如电压等。物理层的功能是利用“传输介质”为“数据链路层”提供物理连接，负责数据流传输，基本单位是比特流，也就是01.
数据链路层：在“通信实体”建立数据链路连接，基本单位是“帧”（Frame），为网络层提供差错控制和流量控制。由介质访问控制子层（MAC）和逻辑链路控制子层（LLC）组成。MAC规定如何在物理线路上传输帧。LLC对在同一条网络链路上的设备之间的通信进行管理。
网络层：为数据在节点之间创建逻辑链路，通过“路由选择算法”为分组选择最佳路径，实现拥塞控制，网络互联等功能。换言之，网络层负责的主要是路由选择工作，使得多个网络之间的连接畅通，信息得以共享。网络层提供面向连接和无连接两种服务，面向连接服务主要通过虚电路实现，无连接则是通过数据报提供服务，无需预留资源且灵活多变，但是是一种不可靠的服务。由于数据报使用的较多，在更高层中可以通过协议来提供可靠的服务。IP协议属于该层。
传输层：传输层是网络体系结构中高低层之间的接口层，是整个体系结构的核心，提供端到端（End to end）服务，处理数据报错误，数据包次序等传输问题。他使得用户完全无需考虑物理层，链路层和网络层工作的详细情况。TCP与UDP协议均属于该层。
会话层：会话层用户维护两个节点直接的传输连接，确保传输不中断，以及管理数据交换等功能。
表示层：表示层为在应用过程之间传送信息提供表示方法的服务，他无需再考虑数据的可靠性等，而是关注数据的加密，解密，数据格式变化，数据压缩与解压等，与网络安全服务关系较近。
应用层：OSI的最高层，直接面对用户，为应用程序提供服务。Http和dns就是应用层的协议。
封装：每一层并不关心从高层传递来的信息的具体格式，而是将高层来的数据报看做整体，添加报头然后递交给低层，因此每一层都会添加自己的报头*数据链路层还要添加报尾，
形成最终的一帧数据。当该数据通过物理层到达目标主机后，物理层会将帧递交给高一层，最后逐层拆开数据报并进行校验，最终原始数据会被提交给具体的应用程序。
TCPIP的区别：TCP/IP参考模型划分为五层，对于OSI最高三层统一称为应用层，因而相对清晰简练。
TCP/IP参考模型各层数据实体名称：应用层——数据服务单元，传输层——报文，网络层——分组，传输层——帧。
网络协议：为数据交换建立的规则，标准或约定，由三个要素组成：语法（结构和格式），语义（需要发出何种控制信息，完成何种动作以及做出何种相应，即具体含义），同步（事件实现顺序的详细说明）。
交换技术：
电路交换：先建立物理链路，然后报文的比特流直接传输过去。电话网络。
分组交换：一个分组会传送到相邻节点，存储之后寻找转发表，发送到下一个节点。一个分组只是报文的一部分。
报文交换：整个报文先传送到相邻节点，全部存储之后查找转发表，转发到下一个节点。
计算机网络的性能指标：速率，带宽，时延，利用率。
码元速率：单位时间内信号波形变换次数，即码元的个数，单位为波特。
数据速率：即比特速率。比特率=码元速率*log2（n），n代表进制数。二进制传输中一个码元可以携带一个bit，而如果一个码元有八个状态值，在调制时就可携带三个比特的信息。
码元：实际上就是一个脉冲信号（波形），通过不同的调制方式可能携带不同的比特数量，携带数量越多，码元速率换算成比特速率也就越快了。
时延：发送时延，传播时延，处理时延，排队时延。

第二章 物理层

香农定理：在有随机热噪声的信道上传输数据信号时，信道容量Rmax与信道带宽W，信噪比S/N关系为： Rmax=W*log2(1+S/N) 单位bit per sec：bps。该定理用于求信道最大传输速率。注意这里的log2是以2为底的对数。因此信道容量由带宽和信噪比决定，增大贷款，提高信噪比可以增大信道容量。
带宽（bandwidth）：数据传输率，单位bps。严格来说带宽考量的是波特率而不是比特率，但是数字电路使用二进制传输，由在第一章提到的公式，波特率数值上等于比特率。因而在计网中比特率可以用来代表带宽。
有时会省略比特每秒，1M带宽实际上是指1Mbps。
信噪比：SNR或者S/N,指电子设备中信号与噪声的比例。单位是分贝dB。SNR=10lg(S/N)。例如S/N=1000，SNR=30.
尼奎斯特定理：在理想状态下最高码元传输速率C=2Wlog2K b/s 或者C=2W 波特/s, W是带宽（波特每秒为单位），一旦带宽确定，极限波特率也就确定了。但是比特率可以通过改善编码方式来提高。

传输介质：
双绞线，同轴电缆，光缆。
双绞线：由绝缘铜导线缠绕而成，一起包裹在绝缘电缆套管里，每一根导线辐射出来的电波会被另一根线上的电波抵消，有效降低信号干扰。还分为有屏蔽和无屏蔽的双绞线，屏蔽层可以减少辐射，防止信息被窃听。
五类双绞线：最高传输率100Mbps，最大网段长100米。超五类线可用于千兆以太网。
优势：便宜，有屏蔽效果。缺点：传输距离小，传输速度低。
同轴电缆：随着时代发展已经逐渐被淘汰。
光纤：利用光的全反射传播信息，速率极高，但是成本也高。
信道复用技术：通过共享信道，最大限度提高信道利用率。
频分FDM：将一条信道按照频带分配给不同客户。
时分TDM：将时间分成一段段登场的TDM帧，一人占用一块。
统计时分STDM：扫描正在使用信道的用户，动态分配时隙。
波分WDM（Wave）：按照波长将一条光纤划分成多个信道。优点是极大提升速率（信道更多了），缺点是价格昂贵。

宽带接入技术：xDSL和ADSL
xDSL，数字用户线路，在电话线（铜线）基础上改造，低频用于通话高频用于上网。
ASDL：xDSL的改进，非对称数字用户线路，采用DMT技术，将高频分段，少部分用于上行信道，大部分用于下行信道。采用频分复用技术(FDM)
优点：直接改造电话线，成本较低，不破坏原有结构。
使用物理方法滤波，维护成本低。
缺点：受用户线条件影响，无法保证固定的数据率（毕竟是电话线），现在基本淘汰。
FTTx（光纤）：使用光纤进行传输，为了有效利用光纤，数十个用户使用一个光配线网ODN（光分路器）分用一条光纤。采用波分复用WDM。
速度快，成本高。

公共交换电话网络：
三要素：本地环路，干线，交换局。以模拟技术为基础的电路交换网络，网络资源利用率较低。因为是电路交换，一条通路从建立到释放，所有的带宽只能被两端的设备使用，即使他们没有传输数据，因此造成了带宽的浪费。
电话-（本地环路）-端局-（干线）-长途局-（高带宽干线）-中间交换局
分类：按照覆盖的地理范围，分为本地电话网，国内长途电话网，国际长途电话网。
结构：星型网络，网状网络，环形网络（使用不多）
分层结构：适用于不同等级交换局的互联，用于长途网络。
Modem（调制器）的调制方式：调频和调幅。
三种交换方式的比较：
电路交换：建立线路，传输数据，拆除线路三个过程，具有独占性，实时性的特点，数据可靠迅速而且不会丢失，而且保持原有序列。然而因为需要分配和一直占用资源，电路空闲时资源浪费。
报文交换：将用户完整报文存储在交换机存储器中，当输出电路空闲时再发送给接受交换机或者用户终端。特点是不独占线路，线路利用率高，不需要实时传输因为网络可以暂存；一个报文可以发往多个目的地；能够实现差错控制和纠错处理等。缺点是中间节点需要很大的存储空间；由于报文需要排队，增加了传输延迟。
分组交换：类似报文交换，都是存储交换技术，但是规定了交换机处理和传输的数据长度，称为一个分组。不同用户的分组可以交织在网络中传输。目前应用最广。
如果一个报文过长，就会被分成多个报文分组发送。因为分组较短，一旦出错检错容易，重发代价小，有利于提高转发节点的存储空间利用率和传输效率。
分组流在网络中传输的方式：数据报和虚电路。
数据报：每个数据报独立处理，每个节点会根据路由选择算法选择一条路径，而他们的目的地相同。
虚电路：发送方和接收方先建立一条逻辑上的连接，每个节点无需再为每个数据包判断路径，就像双方有一条专用信道一样（但是不是物理的）。

总结：电路交换：需要建立物理通路，在释放之前被双方占有且完全透明。
报文交换：报文从发送方发送到接收方采用存储转发的方式。
分组交换：报文交换的改进，报文被分成报文分组，并规定了分组长度，提高节点存储空间利用率，但是到达目标之后需要重新将分组组装成报文。

第三章 链路层

链路：是一条无源的点到点的物理线路段，中间没有任何其他的交换节点。
数据链路：除了物理链路之外，还需要通信协议控制数据传输。硬件和软件加到链路上，就构成了数据链路。

成帧

帧是链路层的一个单元。
标志用来标识帧的开头和结尾，帧中有地址字段，控制字段，正文字段，校验字段。标志是成帧的重要标志，一旦链路层读到标志就知道帧开始了。
1.字符计数法：用一个帧的第一个字节说明帧的长度，总长度包括帧头。然而一旦帧头出错，后面将一直出错。
2.字符填充（字节填充）：在帧头前和尾后加一个特殊字符，只要读到说明帧开始，再读到说明帧结束。如果正文中也出现了特殊字符，就加入转义字符，如果读到转义字符就认为是普通数据。如果要输入转义字符，就在前面再来一个转义。
3.比特填充（位填充），规定flag是6个1，读到6个1就说明帧开始或者结束。那么一旦在字段中出现连续的5个1，发送方就要在后面添加一个0.如果接收方读到5个1，就从后面去掉一个0并继续往下读。如果没有0可去（下一位还是1）那显然就是帧结束了。

差错检测：
循环冗余校验CRC》可能会有计算
在数据位后面添加n位校验位，n为校验多项式最高次项的次数，然后讲校验多项式的项数提出来（空位补0），形成二进制生成除数序列。用补0后的源数据除以除数，得到余数即校验码。除的过程中，高位有1商1无1商0.
最后把校验码添加在源数据后面。接收端用完整数据（包含校验码）除以多项式生成的除数，如果余数为0说明正确。
神奇之处：实际上相当于将原数位扩大后加上余数，这样无论如何得到的新数据都可以被除尽。虽然可以纠错但是实际应用的时候出错了会直接抛弃，因为纠错代价太大不如重新传。

基本数据链路协议：
停等协议（stop-and-wait）（原单词多么简单明了非要简化成什么停等协议我真实服了。）
朴素的协议，发完一个分组就停止发送，等待对方确认，收到确认后再发下一个分组，如果一段时间收不到就再发一遍。
发送端发完数据帧后，需要将帧的副本暂存在缓存中，这样才能在出了差错时重传。
CRC检验通常是硬件完成的， 所以对上层软件或者用户来说通常感觉不到。
优点：很简单，缺点信道利用率太低，花很多时间在等待上。
滑动窗口协议：发送端和接收端设定发送窗口和接收窗口。在三次握手的时候会将自己的窗口大小发送给对方。
实际上停等协议就是窗口大小为1的滑动窗口。
主机按照滑动窗口发送数据，如果客户端的缓冲区已满就等待确认，收到确认ACK之后，发送窗口才能往前滑动一格。

回退n协议：
也叫退后n帧协议，发送一个帧后无需等待确认，可以继续连续发送多个帧。收到确认帧仍可发送数据，这样就不存在等待时间（无需等待确认就一直发）
每个帧都有一个确认时间，如果超出了超时间隔，就认为丢失或者损坏，需要重发出错帧和后面所有的帧，相当于退后了n帧。
然而这样可能把正确的数据帧也重传一遍，所以降低了效率。可能会浪费大量带宽用于重传，而且窗口较小时信道利用率也会受到限制（最差当然就是1比特滑动窗口，即停等协议。）

选择性重传协议:
NACK:非确认帧，相当于一定时间没收到某个帧的ack就回复NACK告诉你我没收到。
如果接收端一段时间没收到某个帧或者帧损坏，接收端只会抛弃该帧而不会抛弃后面的帧，并发送NAK，发送端重传的时候只发送出错的帧。
此外在数据包中需要有顺序字符帮助接收端排序。
选择重传可以避免重复发送正确的数据帧，但是接收端需要有缓存空间。

捎带确认：接收方在收到数据帧后不是立即返回一个确认帧，而是等待网络层传递给它下一个分组，然后确认信息会被附带在往外发送的数据帧帧头的ack域中，相当于ack信息搭了下一个外发数据帧的便车。

拥塞控制：防止过多数据注入网络，使得路由器或链路发生过载。涉及的是网络中所有的主机，路由器与其它和降低网络传输性能有关的因素。
流量控制：指对点对点通信量的控制，针对的是端到端的通信，要做的事抑制发送端发送的速率，使得接收端来得及接收。
顺带一提传输层的tcp也有滑动窗口，和链路层的基本原理类似，但是tcp的发送窗口除了由接收方的接收窗口决定之外，还需要考虑拥塞窗口。
发送窗口：发送方的一段缓存空间，在收到确认之前保留这些帧，这样当出错时才能重发。
接收窗口：接收方的一段缓存空间，在接收方处理速度比接收速度慢时暂时保存数据帧。

介质访问子层MAC（介于物理层和逻辑链路控制层之间）
静态分配信道：
FDM（Frequency频分），TDM（时分）
m/m/1
特点：信道分配不合理，资源没有按需分配，效率低。
动态分配：通过多路访问协议，动态分配信道资源；
分为两种：随机访问协议和受控访问协议（有中央控制模块）
随机访问协议：不进行控制，由发送方自行决定什么时候发送，相应地可能会出现冲突，需要进行冲突避免。
ALOHA：诞生于夏威夷大学的随机访问协议，为了解决无线通信问题。
纯ALOHA：任何信道在帧生成后立即发送，不考虑是否被占用的问题，但是可以通过检测信道来直到帧是否发送成功。如果失败，就随机延时一段时间，重新发送。
吞吐率S：在发送时间T内，发送成功的平均帧数。由于T是一个帧发送的时长，0<S<1.
网络负载G：时间T内所有站总共发送的平均值。G>=S,G=S时没有冲突发生，G>S时则表示发生了冲突。
p0 一帧发送成功（未冲突）的概率。p=S/G，如果G>1则说明冲突频繁。
冲突危险期：发送的帧容易和其它帧冲突的时间。
在ALOHA中，冲突危险期为2T（两倍帧时），相当于两倍端到端的时间，因为还需要收到一个ack才能确认。最高信道利用率18.6%。
时隙aloha：把时间划分为一个个时隙，规定无论何时帧产生，都要在一个时隙开始时发送。由于此时一旦某个时隙被占用其他站就不会发送，从而使得冲突只可能在时隙开始发生。效率提高了一倍。
CSMA：aloha的改进，特点是先听后发，边听边发。
先侦听，如果介质空闲就开始发送。
如果介质忙，则等待一段随机时间。
随机时间之后，重复侦听过程。
如果两个站点都检测到信道是空闲的，那么几乎会立刻导致冲突。此外就算监听到信道空闲也并不意味着真的空闲，也许其它站点的数据还在传输但是未到达监听的站点，从而使得监听站点没有意识到现在信道被占用。
改进：使得发送站点在传输过程中继续侦听，监测是否冲突，如果冲突就可以监听到超过本身发送载波信号的电磁波，从而发现冲突。一旦检测到冲突，立即停止发送并发送一串阻塞信号，通知对方站点，快速终止被破坏的帧，这就是CSMACD
CD表示Collision Detection即冲突检测。相比于CSMA，cd还在节点发送信息帧的同时监听介质，判断是否发生冲突。
先听后说：一段时间寂静无声，则开始传输。
有空就说：如果一直忙碌，就持续监听，直到出现IFG就开始发送数据。
边听边说：在传输过程中持续地监听信道，检测到冲突就停止。
冲突停止：如果一个节点在传输期间检测到冲突，就立即停止传输，同时发送一个阻塞信号，以确保所有节点都发现冲突，从而抛弃受损的数据包。
后退一段时间后，试图重新发送。后退时间采用二进制指数退避算法来决定等待的时间（随机延迟）
重复。

以太网：
二进制指数退避算法：
基本退避时间为2t，表示端到端往返的时间，称为争用期。
冲突发生后需要等待一定基本退避时间再重复发送。第i次冲突后在0-2^i-1之间选择一个等待的时隙数再重传。10次冲突后，时隙数固定在0-1023之间，16次冲突后宣告发送失败，报告上层。

最小帧长：首先电缆的延时特性为5us/km，在站点最大间隔2500m的情况下，往返共5000m，于是会产生25us的时延。现在标准以太网的速率为10Mbps，因此最小帧长在完美情况下是25bit，但是考虑其他的时延，最终确定为64bit。
最小帧长存在的意义实际上就是为了区分那些因为碰撞和破碎的帧和完整的帧，因为最小帧长大于64bit，在一个争用期内一个帧不可能被发完，就可以确认没有碰撞发生，且在发送完毕之前也不会再发生（所有的站点已经监听到信道被占用了，或者碰撞了），那么碰撞也只可能在争用期内发生。接收方可以自然地把那些小于64bit的帧都视为无效而抛弃掉。
！！！！之所以争用期是2T，第一个T是为了让信道被占用的消息能够通知到所有站点，第二个T是为了让碰撞的消息通知到所有站点，在这两种情况下，都可能出现未被通知的站点发送数据从而导致碰撞（或者新的碰撞）。因此争用期为2T。2T之后，所有站点都被通知到了，他们就不会再抢占信道导致冲突了。

电磁波在光纤中的速率为2*10^5km/s（三分之二光速），1s=10^6us,所以每us传输0.2km，相应每千米需要5us，因此是5us/km
算法：设总线长S，光速0.7C，传输率R，帧长L,tPHY为物理层时延
2T=2 (S/0.7C + tPHY)
Lmin=2T * R
那么R=Lmin/2T,如果要加快以太网速度到百兆或者千兆所以要调整。

曼彻斯特编码：首先要规定方向，从位中间电平到高电平跳变是0还是1，规定有所不同。在802.3中规定低到高1，高到底0.
差分曼彻斯特编码：是曼彻斯特编码的改进，在每一位周期中间都会改变波形，如果在周期交界处电平不变就是1，如果电平改变就是0.
另一种方法：如果波形和前一个相同，这个波形就是0，否则是1.

以太网帧格式：
前导码：用于接收方与发送方同步，7个0xAA
起始定界符：用于标识一个帧开始，为0xAB
DST，SRC：标识目标地址和原地址，6个字节长，如果目标地址第一位是1表示是普通地址，否则是组地址。
length，type：表示数据类型。通常一个以太网帧长在1518字节之内。
Data：数据主体，最小48字节，加上头12字节，CRC4字节刚好64字节。数据小于48字节会添加pad字段填充。数据段最长为1518-12-4=1502字节。
FCS，即CRC，循环冗余检测码，4字节。

网络层：

设计要点：虚电路子网和数据报子网

虚电路子网：虚电路是由分组交换通信所提供的面向连接的通信服务（分组交换对应的有电路交换，但是与虚电路原理上完全不同），所有分组会顺序到达，进行可靠的数据传输服务。
为了进行数据传输，两个节点之间需要建立一条逻辑通道，该通道会在会话结束时释放。两个节点之间可能有多个虚电路进行数据传输，每个节点上保存一张虚电路表，包含虚电路号，前一个结点，下一个节点等信息，这些信息在虚电路建立的过程中被确定。

数据报：数据报时通过网络传输数据的基本单元，报头描述了目的地以及它和其它数据报的关西。数据报是完备的，独立的数据实体。数据报提供无连接，不可靠的通信服务，每个路由器使用目的地址进行转发，对每个分组独立选择路由。

对比：数据报的每个分组需要包括完整的源地址和目的地址，但是路由器不需要存储任何连接状态信息，独立的为每个分组算则路由。此外由于分组不保证顺序到达，所以数据报头中还需要包括序列信息。实际上数据报服务不能保证服务质量，只能尽量保证交付。
虚电路需要建立电路，报文不必携带目的地址，源地址等辅助信息，只需要带有虚电路的编号即可。

路由算法
路由（routing）按照原意实际上就是寻路的意思。路由算法也就是发现代价最小路径的算法，是网络层软件的一部分，用于完成路由功能。
路由算法的原则：正确性（至少要使得分组正确到达目的站点），简单性（通过简单的算法降低算法延迟。）健壮性（能够灵活适应通信量和网络拓扑的变化），稳定性（路由不应摇摆），公平性（对每个站点都公平），最优性（对某个指标最优）

分类：静态路由算法：路由表是事先计算好的，不能适应网络拓扑的变化。动态路由算法：能自适应拓扑和通信量的变化。
汇集树：所有到目标站点的最优化路径组成的树叫做汇集树。
flooding：结点收到不是发给他的分组，就将该分组的副本发送给除了输入链路之外所有相连的链路，因为其中必然有一条是最优的。适合流量小以及健壮性要求很高的网络，否则会导致严重拥塞。
随即走动法：顾名思义，当分组到达节点时按照一定概率随机选择一条路进行转发。

自适应路由算法：
最短路径路由：迪杰斯特拉算法，不再赘述。实际上时单源最短路，等于每个站点根据拓扑结构和代价跑一次最短路。

距离矢量路由
朴素的动态路由思路，每个路由器会从邻居处获得路由信息，加上自己到这个邻居的距离矢量来形成自己的路由信息，从而更新整个网络。Bellman-ford算法。
count to infinite：由于是动态更新的一旦其中某个路由器下线，就可能无穷计数。例子：A-B-C，现在B到A成本为1，C到A成本为2.一旦A下线，B将不再能到达A，因而此时B到A的距离应该是无穷大。然而B却发现C声称自己能以2为成本到达A（尽管这是通过B，但是距离矢量路由不会考虑这个），因而B会将距离更新为通过C到达A的代价，即2+1=3.然而C发现了B的变化，他也进行检查发现现在到达A的最短距离是通过B，代价为3+1=4.C更新之后，B仍然要更新为5，如此会无限更新到无穷大。
解决方法：规定跳数上限，超过一定跳数为到达就抛弃。

链路状态路由协议：相比于距离矢量路由中的路由器只需要关注与它相邻的路由提供的路由项信息，链路状态路由则是要获知整个网络的路由信息，根据状态信息生成网络拓扑结构，每个路由器根据拓扑结构计算出路由。
LSP：链路状态数据包，包含与该路由器直连的每条链路的状态，通过记录每个邻居的所有相关信息来完成。建立了连接关系就创建LSP。通过泛洪的方式在整个网络中发送LSP，首先将自己的LSP发送给所有邻居，一旦从邻居处收到LSP则保存副本并立即转发给非该邻居的所有邻居。它需要在收到所有状态信息之后再计算路由，而不是链路状态路由一边计算一边发送。
最终，每个路由器都使用数据构建一个完整的拓扑图，自行计算通向各个网络的最佳路径，这个计算是相互独立的，但是他们用的拓扑图是一样的。

对比：1，链路状态路由的每个路由器都会拥有整个网络的拓扑图，并根据拓扑图来计算最短路径。而距离矢量路由仅保存开销和下一跳方向，不在乎整体。2，链路状态路由在LSP泛洪过程中不需要更新路由表和计算，因此收敛更快。3，在第一次LSP泛洪之后，只有拓扑发生改变才会发出LSP，然后所有的路由器会重新计算。距离矢量路由常常需要定期更新。4，然而链路状态路由一般占用更多内存和cpu，因为需要创建拓扑树还要维护链路状态数据库。此外LSP泛洪可能会影响带宽。

分级路由：路由器被划分为区域，每个路由器只需要知道如何将分组路由到自己所在区域的目标地址，但是对其他区域的结构毫不知情，也无需知道他们的拓扑结构，这样路由表就会大大减少，为了选择路由占用的内存也会减少。区域可能分成簇，簇又分成区，区又分成组。
分层路由也有缺点，就是路由未必是最优路由（因为不清楚其它组路由的情况）

广播路由：不同于点对点的路由，广播路由要提供一种从源节点到网络中所有其他节点交付分组的任务。
生成树广播：为了防止广播随着某个环无限制的泛洪，可以定义一个中心点建立生成树。

拥塞控制：RED Random nearly detection。是一种网络层的拥塞控制算法，该算法会维持一个最小门限min和最大门限max参数，当分组到达时RED会计算平均队列长度，如果长度小于min则正常将分组放入队列。如果在min和max之间则以一定概率p丢弃该分组。如果超过max则丢弃该分组。平均队列长度采用加权平均来计算。
该策略是路由器来实现，因此在网络层。

服务质量：
资源预留协议（RSVP），允许主机在网络上请求特殊服务质量用于特殊应用程序数据流的传输。路径消息：从发送方主机沿着数据路径发送，并记录路径上节点的路径状态。预留消息：由接收方沿着反向路径到达发送方，在过程中确定流需要的资源。相当于为一个数据流同志经过的所有路由器，与他们协商为该数据流提供质量保证。

网络抖动：是网络性能的参数之一，用于描述包在网络中的传输延时变化。通过缓冲技术可以优化。
PS 计算机网络的性能参数指标：时延，丢包率，带宽和抖动。
漏桶算法（leaky bucket）：强制一个输出速率而不管数据流的突发性，过多的数据流会被承载在缓冲桶中。突发流量将会被整形而提供一个稳定流量。如果数据流填满了桶，多余的将会被丢弃。然而如果有一些突发传输超出了桶的大小，这些传输可能会被抛弃。
令牌桶算法（Token bucket）：桶内放的不再是数据而是令牌，算法会按照恒定速度在桶内放置令牌，如果满则溢出，这就保证最大令牌数不会超过桶的大小。传送到令牌桶的数据包要消耗令牌发送，不同大小消耗数量不同。如果没有令牌可用则不允许发送，可能被丢弃或者等到有足够的令牌。他能够允许一定程度的突发传输。

隧道技术：一类网络协议，实际上是一种数据包封装技术，将原始ip包封装在另一个ip包的数据载荷中传输。通过隧道技术可以将两个独立网络通过公网连起来。vpn就是internet上的一种隧道协议。

Internet网络层：IP协议
因特网是基于TCP/IP协议的，IP即Internet Protocol，互联网通信协议。IPv4是第四版协议。
IPv4：使用32位（4字节）ip地址，一共有42亿个地址，通常写作点分十进制的形式。地址分为ABC类，A类二进制最高位是0，B类是10，C类是110.
子网掩码：用于区分IP中那些是网络号那些是主机号，A类是255.0.0.0.路由器需要用子网掩码与IP进行and运算从而得到网段号，以判断目标与源地址是否处在同一个网络中，从而采取不同的策略。
1-126 A类 127-191 B 192-223 C
子网划分：可能有计算题。除了A类B类默认的子网掩码之外，额外多出来的非255的子网掩码段标识的就是子网。注意计算主机IP地址的时候排除全0和全1.

CIDR（Classless） 无分类域间路由选择，无分类编址。CIDR仅将ip号划分为网络前缀和主机号两部分，但是在最后写上了网络前缀所占的位数（实际上取代了子网掩码），这个信息仍称为子网掩码。后面的数字其实相当于子网掩码从前往后数有多少个1.

地址聚合：可以聚合两个地址块。把地址块按照二进制写出来，从前往后找完全相同的位数，最后再合起来。聚合后的ip地址不要算主机的位数。
另外还要注意主机号中如果有全1.聚合的时候提前一位让主机号变成011（因为全0和全1要保留）

NAT：网络地址转换：私有地址通过NAT转换成合法的IP地址，在过程中会自动修改IP报文的源ip地址和目的ip地址。私有地址并不能用在internet上（192。168啥的）由于IPv4严重不足，需要靠私有地址来缓解压力。
私有地址主机会将数据包发给NAT路由器，路由器记录其内网地址和端口，并为他分配全局地址和端口，并记录再路由表中，然后使用全局IP发送信息。当收到返回信息的时候，再根据NAT路由表转换为私有IP地址，发给主机。

ICMP协议：internet控制报文协议，控制消息并不传输用户数据，但是会传送许多网络本身的信息，如ping就是。

ARP地址解析协议：将ip地址转化为mac地址的协议，即逻辑地址到物理地址的映射。ARP是链路层或网络层协议。
ARP工作过程：广播请求，单播应答。先查看ARP高速缓存表中是否有目标的MAC地址记录，如果有则直接通过MAC地址传输。如果没有记录，则向局域网中所有主机广播ARP请求，寻找目标MAC。所有主机都会对比IP，若是自己的IP则会直接给源主机返回一个ARP数据包，其中包含自己的MAC地址。源主机会将地址写入缓存，然后用MAC地址进行传输。如果源主机和目标不再同一网段，则通过网关MAC。因此跨网段通信，其他所有网段的mac地址都会是网关的mac。

DHCP 动态主机配置协议：服务器控制一段IP地址范围，客户机登陆的时候可以自动获取服务器分配的ip地址和子网掩码。
自动分配：服务器为主机指定一个永久固定的ip，不能再分配给其他客户机。动态分配：分配一个具有时效性的ip，时间到期就可以被其他主机使用。手工分配：管理员来分配。DHCP采用UDP来传输，而且是一个应用层协议。

OSPF 开放式最短路径优先：链路状态路由的一种实现，使用的算法是迪杰斯特拉，以计算最短路径树。

BGP 边界网关协议：
AS 自洽系统：同一实体管辖下具有相同路由策略的IP网络。BGP用于在不同的AS之间交换路由信息，通常由路由器来执行，这个路由器称为边界网关。BGP属于外部网关路由协议，实现自洽系统间无环路的域间路由，Internet广域网主要就是用BGP协议来连接不同网络。邻居关系通过人工配制实现，对等实体通过TCP交换数据。
在路由协议中，只有BGP用TCP作为传输层协议。

传输层：

相比于网络层的两端是主机，传输层是提供不同主机上不同进程之间的逻辑通信，即端到端的通信，即使在不可靠的网络层传输下，传输层也能提供可靠的传输。
端口号是用来标识应用程序的标识，长度为16位，65535.
熟知端口号为0-1023，是分配给一些最重要的应用进程的。例如DNS=53，HTTP=80
端口号只具有本地意义，标志本地计算机应用层的各进程，不同计算机的端口号没有联系。

三次握手四次挥手
TCP建立连接的过程是三次挥手。三个标志位SYN，ACK，FIN
PC1发送SYN报文（Seq=x，SYN=1）
PC2发送SYNACK报文 （Seq=y，Ack=x+1，SYN=1，ACK=1）
PC1发送ACK报文（Seq=x+1，Ack=y+1，ACK=1）
客户端向服务器发送syn同步请求，服务器收到请求后会针对客户端的syn同步请求进行ack响应，同时也发送一个syn同步请求。最后客户端收到syn请求后会回复一个ack响应。
为什么三次握手：因为TCP是可靠的传输层协议，传输前会建立双向数据通信通道，保证没有问题时才会发送数据。三次握手实际上就是双方相互告知起始序列号值，再确认对方收到的准确无误后才能继续传输数据。另一方面根据课本，要防止已失效的请求又回到服务器端，也就是说服务器需要再收到一个ack以确定第一个seq请求并不是失效的，对方已经准备好接受信息。
注意在建立连接后所有的ACK字段都要置1.Seq每次在自己的基础上+1，Ack则是对方发来的Seq+1，表示之前已收到。因此本次的Seq等于对方的Ack（很合理，根据稍待确认，Ack中的值表示下一个期望的序列号，则主机会将对方需要的序列号发回去，也就是Seq了）
四次挥手：客户端发送FIN/ACK(FIN置1，Seq=u，客户端进FIN_WAIT_1)
服务端收到客户端的FIN请求，发送一个ACK，ACK=u+1，Seq=v，服务端进入CLOSE_WAIT，客户端收到进入WAIT_2
现在服务端也发送一个FIN给客户端，ACK为1，Seq为w，ACK=u+1，服务端进入LAST_ACK
客户端收到FIN，进入TIME_WAIT,发送一个ACK，Seq=u+1，ACK=w+1，然后CLOSE。
为什么断开要四次？数据传输方向是双向的，一个方向数据通道关闭需要一次请求和一次曲儿，所以要断两次。两个方向就是四次。
半关闭：客户机发送了FIN请求，服务器也给予ACK响应，但是服务器到客户机还有数据要传，所以没有立即发送FIN。一旦发送FIN，说 明不再有数据传输了，所以主动发起的一方要发FIN。

TCP状态机：
CLOSED 关闭状态，什么也不做
LISTENING
SYN_RCVD 被动接受
SYN_SEND,ESTABLISHED,
FIN_WAIT_1,FIN_WAIT_2,TIME_WAIT,CLOSING
CLOSE_WAIT
TIME_WAIT
CLOSED

流量控制：对发送方发送速率进行控制，从而产生一种动态平衡。
TCP的滑动窗口：流量控制
滑动窗口其实和链路层的滑动窗口有点像，但是针对的是TCP分组。
参数：发送窗口，接收窗口，拥塞窗口
与链路层类似，有停止等待，回退n和选择重传协议
RTT往返时延，为数据完全发送完（把最后一个比特推送到数据链路上）到收到确认信号的时间。实际上接收方要等发送方把所有分组的数据都发送完毕才会发送确认报文。

发送窗口大小取决于接收窗口和拥塞窗口的大小，取二者的最小值。接受端在ack中会汇报自己的接收窗口，发送方会根据该窗口控制自己发送数据的大小，所以是接收端控制发送端的速度（或者拥塞情况）。必须按顺序ack，收到ack之后滑动窗口才能往前走。sndwindow会根据接收方返回的接收窗口来调整。
拥塞窗口：使得发送窗口不仅由接收窗口，还由网络拥塞情况来调整，当拥塞发生时，tcp会进行自我牺牲。

Nagle算法：在极端情况下，用户数据极少但是包的报头却占用了大量空间，如每次发送1字节数据却要浪费40字节的头部信息。Nagle算法主要避免发送过小的数据包，要求tcp连接上最多只能有一个未被确认的小分组，在到达之前不能发送其他的小分组。Nagle算法会等待一段时间将一系列小分组收集起来合成一个片段发送。大分组不去管。
如果这时还没有等待确认的小分组，无论如何都可以直接发。如果尚有未确认的小分组，则将其它进入的小分组放在缓存里等待合成一个发送。
可能造成发送时延。因此可能会被禁用。

delay ack延时发送ack，ack会等待是否有响应数据一块发送，如果超出时间则正常发送ack，这样能减少ack的数量。

愚笨窗口综合征：应用层一次从传输层实体读取一个字节，传输层就发送一个字节的窗口更新段，发送方就专程把一个字节打包好发出来，如此浪费了大量资源。
解决方法：clark算法，禁止接收方发送只有一个字节的窗口更新数据段，当接收方能处理他建立连接时告知发送方的最大数据段大小（发送方只能发这么大），或者缓冲区一半已空，才发送窗口更新数据段。

TCP拥塞控制：Reno算法：慢启动，拥塞避免，拥塞发生，快速恢复。
慢启动slow start：维护一个拥塞窗口cwnd congestion window，一开始先不要发送大量数据，先从最小逐渐扩大拥塞窗口大小，从1开始，每次增大一倍（单位时MSS，最大单个报文长度），每次收到ack则+1，直到出现丢包，则将窗口减半。
拥塞避免阶段：减半之后，为了避免产生拥塞，现在每轮发送拥塞窗口+1，呈线性增长。当收到某个报文三个重复的ack（说明下一个没送到），则认为一个报文丢失了。
为什么会多次ack：因为tcp有超时重传机制。接收方发送ack时，会一直ack需要的数据包，所以如果发送方多次收到同样的ack，说明丢包。
报文丢失有两种情况：TD表示收到三个一样的ack，TO表示timeout，TO要更加严重。如果TD则将窗口减半，阈值设为现在的窗口大小+3倍报文段大小，如果再收到重复ack，窗口+1。如果收到新的ack则说明成功重传，随后进入拥塞避免（每次加1直到丢包），此时cwnd=慢启动阈值。

但是如果超时RTO说明拥塞严重，此时阈值设为cwnd/2，cwnd直接变成1，进入慢启动过程。

一旦报文丢失，则无需等待超时定时器（RTO）耗尽，立即重发（快重传），并要求接收方收到该重传（失序）报文段立即重复确认。
快速恢复：拥塞窗口减半，慢启动阈值定为现在的拥塞窗口。
tcp累计确认机制：每次接收方只会ack最近一次没有确认的报文段的ack（没收到就继续ack），所以会产生重复ack（冗余ack），在发生冗余ack的时候，由于tcp传输可能失序，所以后面的是否已经在缓存中，发送方无法从ack中知道，只有等到下一个ack来才知道发到哪了。

UDP：用户数据包协议，是一种无连接就可以发送ip数据包的方法。报文格式也比较简单，只有源端口，目的端口，长度和校验码，被封装在ip数据内。
udp无需维护连接状态，不需要建立连接，需要的时候就抓取数据，并尽快扔到网络上。因为很简单所以也没有拥塞控制，仅仅受应用软件生成数据的速率影响。他是一个不可靠的协议，RIP中就是用udp来修改路由表。
因为不可靠，所以不保证数据能收到，也无需等待应答，经常会出现分组丢失，但是网络开销和效率要好得多，处理更快。音频，视频，qq等使用udp，尽管丢包，影响也不大。

（PS，ip协议报头以32比特，4字节为一行，所以不满的要填充0，称为padding）

第七章 应用层

http协议：超文本传输协议 get post blablabla header 正文
用于给浏览器解析的。http时无状态协议，对事务处理没有记忆能力，所以诞生了cookie和session
dns协议：域名系统，使用端口53，用于向dns服务器查询域名对应的ip地址。
客户端向首选dns服务器查询，服务器中如果存在则权威回答，如果不存在则检查本地缓存，如果有记录直接返回。如果都不存在，向根域名服务器查询。
根域名返回相应顶级权威域名服务器地址，然后继续查询。
迭代查询。最终结果保存在本地缓存中并返回客户端，完成查询。大多数防火墙都会开放dns服务。
本地dns服务器，递归查询和迭代查询。
主机向本地dns服务器查询一般都是递归查询，本地域名服务器向根域名发起迭代查询。