computer networks outline（3）

介质访问控制子层

在一个广播网络中，如果有多方要争抢信道来传输信息，那么这时如果仅有一个信道，这个信道的分配问题将会非常困难。为了解决分配困难的问题，来确定多路访问信道下一个使用者的协议属于数据链路层的一个子层，该层称为介质访问控制子层。

信道分配问题

静态信道分配

静态分配信道所用的方法就是我们之前使用的频分多用FDM和时分多用TDM技术，这种技术在绝大多数的情况下都有它的弊端，都会造成不必要的带宽浪费，静态分配是我们不提倡的。

动态信道分配

在动态分配信道研究之前，我们先做五个假设：流量独立，单信道，冲突可观察，时间连续或分槽，载波侦听或不听。单信道的假设是核心。只有单信道，我们现在研究的动态分配才有意义。

动态分配协议

ALOHA

纯ALOHA
当用户有数据需要发送时就传输，如果冲突，那么这些冲突的帧全被破坏，过一会主机会把收到的帧广播出去，这些发送方侦听广播，如果没有某个帧说明该帧冲突，需要重发送。
一个公式：

S=Ge^-2G

其中S为吞吐量，G为在一个帧时老帧和新帧合起来的传输帧数。根据图表计算后可得，最大吞吐量在G为0.5时左右取得，这时S大约等于0.184。换句话说，最好的利用率大约在18.4%左右。

分槽ALOHA
分槽ALOHA于纯的区别在于增加了时间槽的概念，不允许帧随时发送，而是等到下一个时间槽。这种方法得到的效率高了一倍：

S=Ge^-G

这时S最大可以达到0.368，最高利用率36.8%。

载波侦听多路访问协议

如果一个协议中，站能够监听别的站是否存在载波，并一句这个采取相应的动作是否传输帧，那么这种协议成为载波侦听协议。

1-坚持CSMA
如果有站要发送时，先侦听信道，如果空闲就发出，在站发现空闲时这种传输方法的传输概率为1。但是这种方法可能出现的问题是两个或多个站同时认为信道是空闲的而引发冲突。

非坚持CSMA
非坚持也是先侦听，如果信道当前不空闲，那么他不持续监听，而是等待一个随机时间，之后再次重复上面的方法，这种方法利用率更高，但是延迟也越来越大。

p-坚持CSMA
如果信道是空闲的，则它按照概率p发送数据；而以概率q=1-p，将此次发送推迟到下一个时间槽。

带冲突检测的CSMA（CSMA/CD）
站在侦听到信道为空之后发送，发送后持续对发送的帧继续进行侦听，如果自己已经发送的帧和发送时的比特流不同，说明该帧已经发生了冲突，那么就放弃，这样更节省效率。

有限竞争协议

当一个时间槽中有五个以上的站来竞争时，这个时候效率就不是很高。那么将所有的站分组，每组只有五个以内的站，对于第一个时间槽，第一组来竞争以此类推。

网络层

存储-转发

所有的客户端主机都连接在ISP的设备上，如果主机要发送数据包，先把数据包发送给离他最近的一个路由器上，也先储存在路由器上，沿着路由器转发一直到目的主机。

虚电路与数据报子网比较

问题	数据报网络	虚电路网络
电路建立	不需要	需要
状态信息	路由器不保留连接状态	针对每个链接，每条VC都需要路由器保存其状态
寻址	每个包包含全部的源和目标地址	每个包包含简短的VC号
路由方向	每个数据包被单独路由	建立VC时选择路由，所有包都遵循该路由
路由器失效影响	没影响，除了那些路由器崩溃期间丢包	穿过故障路由器的所有VC都中断
服务质量	困难	容易
拥塞控制	困难	容易

路由算法

最短路径算法
一个开始节点（永久节点），将所有于这个节点相邻的节点全部标记上路径和前一个节点的序号，不断地将整个图中所有节点更新，最后得到一个点到另外一个点的最短路径。

泛洪算法
泛洪算法，将每一个入境的数据包发送到除了该数据包到达的那条线路以外的每条出境路线。

距离矢量算法
每个路由器维护一张表，表中列出了当前已知的到每个目标的最佳距离，以及所使用的链路。这些表通过邻居间相互交换信息而不断被更新，最终每个路由器都了解到达每个目的地的最佳链路。但是可能会触发无穷计算问题。

链路状态路由
发现自己的邻居结点，了解网络地址。设置到每个邻居结点的距离或者成本。构造一个包含所有刚刚获知的链路信息包，用泛洪算法将包发送给所有其他路由器，并接受来自所有其他路由器的信息包。计算出到每个其他路由器的最短距离。

拥塞控制算法

网络供给
大量使用的链路和路由器尽早地实行升级避免拥塞。

流量感知路由
及时报告路由的堵塞情况，帮助路由器把数据包绕开热点区域。

准入控制
新的连接将导致网络变得拥挤不堪，那么就 拒绝这种新连接的建立。

负载脱落
一切努力都失败了，网络不得不丢弃它无法传递的数据包。

IP

IPv4的地址是一个32位地址，由高位可变长网络和低位的主机两部分组成。同一局域网上，对应一块连续的IP地址空间，这块地址空间称为地址的前缀。子网掩码是将地址中所有的前缀变成1。在内部将一个网络划分成很多块供给多个网络使用，但对外仍像一个网络一样，分割后得到的成为子网。

类型	范围
A	1.0.0.0-127.255.255.255
B	128.0.0.0-191.255.255.255
C	192.0.0.0-223.255.255.255
D	224.0.0.0-239.255.255.255
E	240.0.0.0-255.255.255.255

还有一些IP信息详见我的另外一篇博客：http://blog.csdn.net/quinnnorris/article/details/54092847

传输层

传输层和网络层一起构成了网络协议层次的核心，传输层为应用层使用网络提供了抽象的模式。

传输层服务原语

原语	含义
LISTEN	阻塞操作，等待入境连接请求
CONNECT	与等待中的对等实体建立连接
RECEIVE	阻塞操作，等待入境报文
SEND	给对等实体发送给一个报文
DISCONNECT	终止一个连接

连接建立和释放

客户端调用原语LISTEN阻塞一个端口，等待响应。客户端发送一个CONNECT原语，与该服务器进行通话，双方通过RECEIVE和SEND通话。最后双方都使用DISCONNECT结束连接。

三次握手

建立一个连接时，要求一方检查连接请求是否的确实当前的。主机发送x，回复x和y，主机再发送x和y来进行数据操作。

TCP，UDP

无连接协议UDP，给应用程序提供发送数据包，允许他们在所需的层次上架构自己的协议。面向连接的协议TCP几乎做了其他所有的事情。

TCP协议中的吞吐量计算、时延计算

拥塞控制算法，控制位设置