computer networksTanenbaum第5章 网络层文档格式.docx
《computer networksTanenbaum第5章 网络层文档格式.docx》由会员分享，可在线阅读，更多相关《computer networksTanenbaum第5章 网络层文档格式.docx（102页珍藏版）》请在冰点文库上搜索。
携带该子网链接到internet的那个路由器的地址【该路由器就标识了这个子网】；
也即：
数据包在网络上传输的出口，如：
H1和H2通讯，则就是RouterF的地址，相对应的是RouterA是通讯的入口，数据包最终由F交给H2）
数据报的方式数据传输的可靠性很高（若通讯子网的某个节点坏了或堵塞了，后续的数据可以绕道传输）
四、面向连接服务的实现（指虚电路子网）
五、虚电路和数据报子网的比较
1、虚电路子网
1）通过路径选择后建立连接
2）分组按序传输
3）服务质量能得到保证
4）通讯后撤销连接
5）适合于实时传输
2、数据报子网
1）每个分组分别选择最佳路径，健壮性较好
2）整个网络系统的信道利用率高，成本低
3）差错控制和排序工作由协议高层（主机）完成
4）适合非实时的传输
路由算法
一、概要
1、路由算法是网络层软件的一个重要部分，它决定进入的分组应该从哪一根输出线传输
2、如果是数据报子网，将在每一个分组到达时作此决定
3、如果是虚电路子网，是在虚电路建立时决定，该连接上所有分组都沿此线路传输
4、路由与转发：
路由是寻址，转发是当一个分组到达时发生的动作
5、路由算法设计必须考虑的问题：
正确性、简单性（路由的计算时间开销小）、健壮性、稳定性（路由计算的结果不能出现两个相同的目的地但转发的路径不一样）、公平性、最优性（路由计算结果得出的路径应该是最好的路径）
6、路由算法最优性的度量标准（衡量路由算法的好坏）
1）路径长度
2）hop数
3）延时时间
7、路由算法的结果就是路由器中的路由表
二、路由算法分类
1、静态算法
为路由器配置一张最优的路由表。
假设网络的拓扑结构是不变的，在这种情况下为每个节点查找一条最短的路径。
1）最短路径算法（Dijkstra）
最常用的静态算法，Dijkstra算法将一个网络抽象成一个加权图，每个路由器是图中的一个节点，每条物理的链路就是图中的一条边，边上的权值可以是真正的链路的长度，也可以是在这个链路上的延迟时间等等，可以自己设定。
Dijkstra算法就是要在这样的一个加权图中找到一条权值最小的路径。
若将每一条边的权值设为1，则得到的最短路径也是跳数最少的路径
Dijkstra算法：
通过用边的权值作为距离的度量来计算最短路径，有最少边数的路径不一定是最短路径，得到的是某个节
点到其它节点的最短路径，即：
该点的路由表。
算法为：
节点5首先找与其直接相连的节点（1、2），则
5-2之间的最短路径为（5、2）；
接下来看节点2可以到达哪些节点，计算节点2到这些节点的最短路径（节
点可到节点3、6，到达节点3、6的最短路径分别为【（2、3）（2、3、6）】），然后根据这两条路径，来计
算节点5到节点3、6的最短路径，并将计算的结果和原来的节点5到节点3、6的最短路径作比较，若要
小，则替换掉原来的设置（在系统初始时，节点5到节点3、6的路径会被标识为无穷大，所以会被替换掉）；
再接下来会根据节点2可以到达的节点3、6来查找节点3、6分别可以直接到达哪些节点以及到达邻接点
的最短路径，接着又来计算节点5到这些邻接点的最短路径，并将结果和原来的之比较，看有没有必要替
换，这个过程一致循环往复，直到当前系统中的所有节点都被遍历到为止，当算法结束时，就可以得到节
点5的路由表。
如图：
采用的数据结构
集合S：
到目前为止尚未找到最短路径的节点的集合或到目前还未遍历到的节点
数组R：
R[i]为从指定源点到节点i去的路径上，节点i的前一个节点（确定了前一个节点就能确定指定源点到节点i的
路径）
数组D：
D[i]为从指定源点到节点i的最短距离
算法的初始化
初始化集合S为除源节点外的所有节点
初始化数组D：
如果从源节点到节点v的边存在（与源节点直接相连），则D（v）为该边的权值，否则为无穷大
初始化数组R：
如果从源节点到节点v的边存在（与源节点直接相连），则R（v）为源节点，否则为0
算法
while（集合S非空）
{
从S中选一节点u，使D[u]最小;
如果（D[u]为无穷大）//D[u]为无穷大说明该图是一个不联通的图
{错误！
无路径存在，退出}
把u从S中删除；
对（u,v）是边的每一个节点v//考察u的邻接点
{
如果（v仍在S中）
C=D[u]+weight（u,v）;
//考察经过u到v的距离
如果（C<
D[v]）//找到了一条指定源点到节点v更短的的路径
R[v]=u;
//替换指定源节点到v的最短路径和长度
D[v]=C;
}
从5出发到各个节点的最短路径
由数组R可得到节点5到各个节点的路径：
到节点1：
5→1
到节点2：
5→2
到节点3：
5→2→3
到节点4：
5→2→3→6→7→4
到节点6：
5→2→3→6
到节点7：
5→2→3→6→7
从而得到节点5的路由表
去往节点
下一节点
1
2
3
4
6
7
2）扩散法（flooding）
没有路由表，不计算路径，有路就走，节点从一个方向上接受到数据，就将数据向除了该方向以外的链路转发。
如从5出发到4，数据包从5→1,2；
2→3,6；
3→6,4；
6→3,7；
7→4；
要解决的问题：
数据包重复到达某一个节点，如：
3，6
解决办法：
在数据包头设一计数器，每经过一个节点自动加1，达到规定值时，丢弃数据包
在每个节点上建立登记表，则数据包再次经过时丢弃
优缺点：
重复数据包多，浪费带宽；
可靠性高，路径最短，常用于军事
2、自适应算法
适用于动态路由，适用于网络拓扑结构动态变化的情况，当网络拓扑结构变化时，应该有一套通知的机制，告诉网络中的
节点变化的情况。
这样的一套通知的机制就叫做动态路由算法。
路由器动态建立和维护一张最优的路由表
1）距离矢量算法（D-V）：
多用于小型的网络
距离矢量算法是动态的、分布式的算法
实现分布式算法的三要素（即：
动态路由算法的三个步骤）：
A.Themeasurementprocess（测量）：
每个节点能了解、知道自己周围的情况：
它附近哪个节点出故障了、哪个节点启动了等等，并能根据实际情况更新自
己的向量Di和Si
B.Theupdateprotocol（更新邻接点距离矢量）：
将知道的情况通知其它节点，每过一段时间相邻的节点之间就会交换向量Di，
C.Thecalculation（计算）：
各个节点根据上一步骤中收到的信息（Di）更新自己的路由表，即重新计算Si
每个路由器用两个向量Di和Si来表示该点i到网上所有节点的路径距离及其下一个节点
相邻路由器之间交换路径信息
di1：
从节点i到节点1的时延向量；
di2：
从节点i到节点2的时延向量
si1：
从节点i到节点1的一条最小时延路径上的下一个节点
si2：
从节点i到节点2的一条最小时延路径上的下一个节点
di1si1
di2si2
Di=di3Si=si3
….….
dinsin
其中：
n：
网络中的节点数
Di
：
节点i的时延向量（节点i到网上所有其它节点的最小时延组成的向量）
dij：
节点i到j的最小时延的当前估计值
Si：
节点i的后继节点向量，即：
路由表（节点i到网上所有其它节点的下一个节点组成的向量）
sij：
从节点i到j的最小时延路径上的下一节点
各个节点根据路径信息更新路由表
dij=min（dix+dxj）（x∈A）
//从i到j的时延取途经每个节点时的时延的最小值，因此在距离矢量算法中每个节点根据其从邻接点得到的信息更新自己//的路由表，而不能看到整个网络的拓扑结构，而只知道、看到自己的邻居
Sij=x//从i到j途经的下一个节点为x
其中：
A：
与i相邻的所有节点的集合
i到j的最短距离
dix：
i到x的最短距离
dxj：
x到j的最短距离
该行为集合A，x=A、I、H、K
D-V算法的缺点
A.交换的路径信息量大
B.各个节点的路径信息不一致，因为路径信息的交换是两两交换的，而网路的情况是动态变化的，可能会出现信息交换的速度跟不上网路情况动态变化的速度。
C.收敛速度慢（对坏消息）
a）无穷计算问题：
好消息传播的快，坏消息传播得慢，都会产生路径信息不一致的情况
b）克服收敛速度慢的方法
水平分裂
同距离矢量法，只是到A的距离并不是真正的距离，对于下方点通知真正的距离，对于上方点，给出无穷大。
如
上图中的C点，它向D通知到A的真正距离，而向B通知到A的距离是无穷大
Holddown
当发现不通时，不重新选择路由，而是把它设成无穷大
这些方法尚在研究之中
D.不适合大型网络
2）链路状态算法（L-S）：
多用于大型的网络，如：
Internet中的OSPF路由协议就采用L-S算法
A.基本思想（即经过以下五个步骤来动态更新路由）
a）每个节点定时测量，检测它的邻接节点，并得到其网络地址
当一个路由器启动后或定时，向每个点到点线路（即：
自己的每一个端口）发送HELLO分组，另一端的路由器发送回来一个应答来说明我是谁（含自己的IP地址）
b）接着测量它到各邻接节点的延迟或开销
发送一个Echo分组要求对方立即响应，通过测量一个来回时间再除以2，发送方就可以得到一个延时估计值，想要更精确，可以重复这个过程，取其平均值
c）然后组装成一个分组（用其所有邻居节点的信息，包括：
我有哪些邻居，我到这些邻居的距离）以告知它刚知道的所有信息
构造分组：
子网及其节点到其邻接点（路由器）的线路开销测量值（即：
延时，假设以ms计）
d）再接下来将这个分组发给网上的所有其它路由器（解决了距离矢量算法中节点中路径信息不一致的问题）
这样网络上的每一个节点都将收到所有其它节点传递过来的消息，这样每个节点都可以得到整个网络的拓扑结构，最后每个节点可以针对得出的整个网络的拓扑结构，使用静态路由算法，得出到其它节点的最短路径。
为了避免是先有鸡还是先有蛋的问题，节点在发送用链路状态分组时采用扩散法（向邻接点）发布链路状态分组。
为了避免扩散法中分组会重复到达某个节点的问题，在L-S中采用了登记表的策略。
以B为例，B的邻接点有A、C、F，源节点E的链路状态分组经A和F到节点B，节点B必须再将E的状态分组转送到C，并向A和F发ACK。
下图为节点B的登记表
存在的问题：
同一个源节点的状态分组会重复到达同一个节点
序号的大小总是有限的，如果序号循环使用，就会发生重复，则无法区分到达的分组是一个新的分组还是一个在网络
上兜了一个圈后到达的过时分组
如果一个路由器重启，序号将从0开始重新计数，但这些分组会被当成过时分组
如果分组在传输时，序号发生错误（如：
4被看成65540，即：
第16位的0被误传成1），则很多分组将被看成过时
分组（此时5~65539均被认为是过时分组，因为当前的分组序号是65540）
解决办法（每个节点加一个登记表【L-S采用此法】或每个分组加一个计数器，）
使用一个32位序号，即使每秒发送一个分组，137年才会循环一次：
解决序号循环使用的问题
在每个分组中加一个年龄字段（如：
初值为60），每秒将年龄减1，为0后该分组将被丢弃，否则不会被认为是
过时分组：
解决路由器重启和序号传输错误的问题
e）计算到每个其它路由器的最短路径
用Dijkstra算法计算到每个节点的路由
得到该节点到每个节点的最短路径
B.L-S路由算法的优缺点
a）优点
各路由器的路由信息的一致性好；
收敛性好，好、坏消息也一样传播得快，各个节点得到的整个的网络拓扑结构是一样的。
节点在发送链路状态分组时，传递的分组信息只包含我的几个邻居节点的信息，而无论网络规模如何，任一节点的邻居总是有限的，不会随网络规模的扩大而扩大，因此分组报文不会太长，适用于大型网络，报文长度仅涉及邻接点，而与网络规模关系不大；
b）缺点
每个路由器需要较大的存储空间来保存整个网络的拓扑结构，用Dijstra算法计算路由时，由于网络规模大，节点数多，
因此计算的工作量大，创建路由表的时间很长
3、拓扑相关的路由算法
在大型的网络中，使用L-S算法，路由器需要花费大量的时间来计算路由，这样会减少路由器用来转发分组的时间，为解
决这个问题可以使用下面的路由算法。
1）分层路由
随着网络规模的增长，存储和处理路由表所需的资源也急剧增长，从拓扑上分层是解决问题的一个方法；
分层的概念：
将路由器分成组，每一路由器只需知道组内任何一台路由器的路由，以及到其它组的路由，且把其它组中所有的路由器抽象成一个，以减少路由表的长度（路由表长的缺点：
占用的空间大、查找路由时间长、维护困难）
A.分层实例
B.如何决定分层路由的层数
有N个路由器的最优层次数是㏑N，每个路由器需要e㏑N个路由表项
现在的Internet网络采用的就是这种分层路由的方法：
把网络分成一个一个自治区，有自治区内部的路由也有自治区外部的路由。
2）广播路由
A.广播路由的解决方法分为两类
要进行广播的节点向其它的所有节点分别发送报文
缺点：
发送数据量大。
需要知道网上所有节点的地址
扩散法
流量大，消耗大量带宽；
某些节点还可能收到重复的报文
B.具体的广播路由算法
a）多目的地路由
分组中包含需要到达的多个目的地的地址表
到达一个节点时，路由器检测所有的目的地址表，确定输出线路集合，路由器为每一条输出线路复制一个新的分组，
每个分组中仅含有要用此线路的目的地址表
优点：
流量小，节约带宽；
缺点：
费用承担不公平
b）生成树算法
将网络的拓扑结构图抽象成一棵以发送节点为根的生成树，如上例A要向B、C、D、E、F发送广播报文，则其生成树为：
路由器将分组沿生成树发送（除了进入线路之外）
带宽得到最佳的利用；
每个路由器必须知道其可用生成树
如：
链路状态路由算法可得到生成树，距离矢量路由算法却不能得到
c）逆向路径传送（有点类似与扩散法）
基本原理：
当某一广播分组到达路由器时，路由器对它进行检测，如该分组来自通向广播源节点发送分组的线路，则将该分组转发到除了进线以外的其它线路，否则丢弃。
当前节点如何来判断到来的分组是来自于通向广播源节点发送分组的线路呢？
这是根据每个当前节点的路由表来确定的—是对自己路由表的反向的使用。
如：
节点A收到了一个分组，那么节点A就根据自己的路由表（A-F-I）进行判断，如果该分组是一个从节点F传递过来的节点I发出的分组则认为该分组是来自通向广播源节点发送分组的线路，并转发该分组，如果该分组是一个从节点E传递过来的节点I发出的分组则认为该分组不是来自通向广播源节点发送分组的线路，并将其丢弃。
可见，只要是逆着当前节点的路由表到来的分组都被认为是合法的，否则不合法被丢弃。
说明
在（a）子网中，每个节点都已生成一张路由表，假设每个节点的路由表中到节点I（广播源）的路径中的下一跳分别为：
如果节点F收到一个从I来的分组，则立即向节点A和节点D转发，
当节点D收到一个经F来的节点I的分组，它意识到如它有分组要发送给I的话，是走节点F的，所以立即向节点C和G转发，若D收到的广播分组是从C或G来的，则根据其自身的路由表（上图）判断该分组不是来自通向广播源发送分组的线路（即：
来自F），就会把收到的分组丢弃掉。
所以节点对收到的分组是接受转发还是丢弃是根据其路由表来判断的。
根据上述逆向路径转发的原则，可根据广播源节点I构造如下一棵生成树，其广播报文沿生成树传输：
3）多址传输路由选择
其接收方不是网上的所有节点，而是网上的一组节点，internet的D类地址支持多址传输，其一个地址对应一组节点，它
是如何控制一个分组发给一组节点的呢？
主要有2种方法：
生成树方法、核心树方法
A.多址传输路由选择使用IP的D类地址
B.生成树法
a）按组从网络的拓扑结构中抽取出来，组中的每个成员都必须以自己作为出发点（根）建立一棵到同一个子网中其它节
点的生成树，当节点要转发分组时就沿此生成树转发下去，每个节点收到分组后都依据自己的生成树如此转发。
根据自己所在小组对生成树进行修剪，得到一棵本小组修剪过的生成树，并告诉同组的其它成员
b）多址传输时仅沿相应的生成树转发
c）缺点：
每个节点既要记住以自己为根的生成树，也要记住网上所有其它节点它们的生成树，所以存储量大，如一个网
络有n个组，每个组平均有m个成员，则每个节点要存储m*n棵生成树
C.核心树（core-basedtree）
一棵核心树也是一棵生成树，每个组只有一棵生成树，组内任何节点发送数据都要依据这棵生成树，对一个组的拓扑结构进行分析，然后选择一个离大家的距离都比较平均的节点作为树根来构造一棵生成树，若某节点要发送一个分组给这个组成员，则先发给树根，由树根将该分组沿核心树发往各个成员，这样，每个组只有一棵核心树，节约了存储空间
4）Peer-to-Peer网的节点查找：
P2P中的路由算法
以上的路由查找都是以目的节点的地址作为查找的键值，而对等网络的路由不同，它是问哪一类信息存储在什么地方，是一种特殊的网络组织结构。
A.对等网：
大量的用户通过固定线路接入internet，共享资源
B.对等网的特点：
a）全分布：
所有节点都是对称的，没有中心控制节点或分层的概念。
在普通的网络中，基本上都是Client/Server的工作模
式，一些节点是server，另外一些是Client，而对等网络的每个节点既是server又是Client。
b）每个节点都有一些其它用户感兴趣的信息
C.对等网的路由：
没有一个中心数据库，如何找到要寻找的信息是对等网络的关键问题，一个经典的算法是Chord算法
D.Chord算法：
结构化的对等网
Chord算法用一个环来组织网络，它通过一个散列的方法（如：
SHA-1把一个IP地址散列到0~2m-1之间的一个数据，然后就按照这个次序组织成一个环【0后面是1，1后面是2，2后面是3.。
。
，2m-1之后就回到0，这样就形成了逻辑上的一个环】）将网络上的节点组织成一个逻辑的环型的结构，但要注意的是这个环上有些节点是存在的，有些则不存在（比如m等于10，则散列数值可以是0、1、2、。
、1023，但我网上可能只有500台机器，另外500多个节点是空的节点，这些空节点是没有必要连到环上的，Chord算法通过successor函数找到下一台有意义的节点，从而形成一个由实节点构成的环）。
我们的目的是要查找这个环上节点的资源，如何知道某个资源存放在环上的哪台机器上呢？
要使用索引，但在对等网上，资源的索引是分散在网中的各个节点上的。
对于网上的每一个资源都取一个名字（即name，别人来查找该资源的时候就使用该名字来查找），该名字作为对该资源的标识，同时对这个名字定义一个hash算法，把它散列到一个键值key，这个键值就是一个存储的位置（环上某个节点的标识符。
如前所述，网上的所有节点是连接成一个逻辑的环，在该环上每个节点有一个标识符【即：
节点IP的散列值】）。
然后就将该资源的索引【二元组（name，IP地址）】存放到这样的一个节点上：
该节点的标识符与该资源name的键值key相等的。
在查找该资源时，先根据资源的名字name做一个hash散列，得到的键值就是要查找的资源的索引所在的节点标识符，然后就到该节点上找到该资源的索引，从而得到该资源所在的节点的IP，这样就可以找到相应的资源了。
总之，在对等网中，将每一个节点散列到一个编号，每一个资源的名字也散列到一个编号，将该资源的索引存放到相应编号的节点上。
a）假设
系统中有n个用户，每个用户既提供资源，也要查找资源
每个用户都有可提供的信息资源，并且都已作了索引供其它用户使用
每个用户都有一个IP地址，并可被散列成m位的一个数字，称为节点标识符（Chord用SHA-1算法来散列），节点标识符为0~2m
所有2m个标识符按递增次序连接成一个环，而不管节点是否存在
定义函数successor（k）：
找出大于等于k的第一个存在节点（如果节点k是实节点，则该函数返回节点k本身，否则返回编号大于k的第一个实节点）
信息资源名称（name）同样被散列为一个m位的数字，称为键值key（key=hash（name））
信息索引的存储：
信息的索引在所有节点上是随机分布的，当一个节点要提供信息name时，它首先构造一个二元组（name，IP地址），然后调用successor（hash（name））去存储该二元组（得到的键值key所对应编号的节点有可能是一个空节点，该节点并不实际存在，所以要调用函数successor来找到大于等于key的第一个存在节点，然后将该资源的索引放到该节点上），不同节点上的同名信息，其索引将被存在同一节点
信息的查找：
当某个用户需要查找名称为name的信息时，向successor（key）发一个请求，要求返回拥有信息name的节点的IP地址
E.Chord算法优化
Chord算
升级会员 