计算机网络总复习
第一章
1、计算机网络的产生和发展,实质上是计算机技术和通信技术相结合与发展的过程
2、计算机网络的发展历程分为3个阶段:面向终端的计算机通信网络;分组交换网;OSI的确定到Internet。
3、什么叫计算机网络?其两级子网的功能各是什么?
计算机网络=计算机子网+通信子网,通信子网负责整个网络的纯粹通信部分,计算机子网是各种网络资源的集合。通信子网由两个不同的部件组成,即传输线和交换单元。
4、网络的拓扑结构主要有总线型、环型、星型和网状结构。分别画出上述拓扑结构示意图,并简述其优缺点。
所谓拓扑结构就是指网络中通信线路和站点(计算机或设备)的几何排列形式。
1、星形:各站点通过点到点的链路与中心站相连
优点:结构简单、建网易,故障诊断易,增加新节点易,监控易。
缺点:太依赖中心节点,可靠性低。
2、总线形:所有节点都连到一条主干电缆上
优点:安装简单方便,成本低,铺设电线最短。
缺点:故障诊断困难,总线故障会引起整个网络瘫痪,增加新节点难,监控难。
3、环形: 各节点形成闭合的环,可实现任意两点间通信
优点:容易安装和监控。
缺点:容量有限,环中任意一处故障都会造成网络瘫痪,增加新节点难。
4、树形: 总线型和星型的综合。
5、网状: 以上各种拓扑结构为基础的综合应用。
5、简述计算机网络的分类。
一、按照其覆盖的地理范围,计算机网络可以分为广域网( WAN,wide area network )、城域网( MAN,metropolitan area network )和局域网( LAN , local area network )。
二、按计算机和设备在网络中的地位分类
1、基于服务器的网络
● 工作站/文件服务器模式
● 客户机/服务器(C/S)模式:工作特点:文件从服务器被下载到工作站上,然后在工作站上进行处理。
● 浏览器/服务器(B/S)模式:主要特点:与软硬件平台无关性,把应用逻辑和业务处理规则放在服务器一侧。
2、对等网络或称为对等式的网络(Peer to Peer)
● 特点:灵活方便,但较难实现集中管理和控制,安全性低。
三、其他分类
1、按传输介质分类
● 有线网:包括有线电话线网、电力线网、有线电视电缆网、同轴电缆网、双绞线网、光纤网;
● 无线网:包括无线电话网、语音广播网、无线电视网、微波通信网、卫星通信网。
2、按通信方式分类
● 点对点传输网络:数据以点到点的方式在计算机或通信设备中传输。星型网、环形网采用这种传输方式。适用于大的网络。
● 广播式传输网络:数据在共用通信介质线路中传输。无线网和总线型网络属于这种类型。适用于地理范围小的网络或保密要求不高的网络。
3、按网络的使用的目的分类
● 共享资源网:使用者可共享网络中的各种资源,例如,文件、扫描仪、绘图仪、打印机以及各种服务。
● 数据处理网:用于处理数据的网络,研究机构的科学计算机网络、企业管理网。
● 数据传输网:用来收集、交换、传输数据的网络。例如,情报检索网络和信息浏览等。
目前网络使用目的都不是单一的,而是综合型的
6、按地理位置划分,计算机网络可分为:广域网、城域网和局域网。
7、按计算机和设备在网络中的地位对计算机网络分类,可以划分为基于服务器的网路哦和对等网络。
8、计算机网络硬件系统是由服务器、客户机、通信处理设备和通信介质组成。
第二章
1、 网络协议由以下3个要素组成:语法、语义和同步
为进行网络中的数据交换而建立的规则、
或约定即网络协议(network protocol),简称为协议。网络协议主要由以下3个要素组成:
● 语法 数据与控制信息的结构或格式 。
● 语义 需要发出何种控制信息,完成何种动作以及做出何种响应。
● 同步 事件实现顺序的详细说明
2、 网络的体系结构:计算机网络和各层次及其协议的集合
3、 第n层的实体在实现自身定义的功能时,只能使用n-1层提供的服务
4、 接口就是上层实体和下层实体交换数据的地方,被称为服务访问点(SAP)。每一个SAP都有一个唯一的标识,成为端口(Port)或套接字(Socket)。
5、 简述协议和服务的关系
● 协议是“水平的”,即协议是控制对等实体之间通信的规则。
● 服务是“垂直的”,即服务是由下层向上层通过层间接口提供的。
● N层实体向N+1层实体能提供的服务:
1. N层实体提供的某些功能
2. 从N-1层及其以下各层实体及本地系统得到的服务
3. 通过与对等的N层实体的通信得到的服务
6、 上下层实体之间交换的数据传输单元成为数据单元,数据单元有3种:协议数据单元、接口数据单元和服务数据单元。
7、 试画出OSI/RM模型的层次结构,并简述各层的基本功能。
8、 试画出TCP/IP模型的层次结构,并简述各层的基本功能。
9、 下述问
在OSI/RM中的哪一层处理:
1) 确定一接插件的机械尺寸和电器特性;
2) 将传输的数据划分为帧;
3) 决定路由;
4) 检察远程登陆用户身份的合法性;
5) 将数据压缩和解压缩;
6) 控制打印机打印头换行
10、 比较OSI/RM和TCP/IP模型的比较及联系。
● 相同点
1. 均以协议栈的概念为基础,协议之间彼此独立
2. 模型中各个层的功能基本相似
TCP/IP与OSI体系结构的对照
● 不同点
1. OSI模型有7层; TCP/IP模型则仅有4层
2. OSI模型区分了服务,接口和协议的概念;TCP/IP模型没有明确的区分
3. OSI区分了物理层与数据链路层;TCP/IP甚至没有分别提及这两层
4. TCP/IP模型中网际层是一个接口,处在网络层和数据链路层之间
5. OSI模型出现在协议发明之前,因此模型与协议间存在不符合要求的服务
。但是由于它不偏向任何一种协议,通用性更好;TCP/IP模型则相反,先出现协议,模型与协议匹配良好但不适用于其他协议栈
6. OSI模型在网络层支持无连接和面向连接的通信,传输层仅支持面向连接的通信;TCP/IP模型在网络层仅支持无连接的服务,在传输层支持两种类型的服务
第三章
1、 数据:数据通信中传输的二进制代码,是传输信息的载体
2、 信息:是这些数据的内容和解释
3、 信号:是数据在传输过程中的物理表示形式
● 数据(Data)——数据通信中传输的二进制代码,是传输信息的载体
● 信息(Information)——数据的内容和解释
● 信号(Signal)——数据在传输过程中的电磁波表示形式
1. 模拟信号——随时间连续变化的物理量
2. 数字信号——相对于时间和幅值而言都是不连续的,即离散的物理量
4、 简述数字信号与模拟信号的区别。
5、 设一数据串为10110100,画出经过FSK、ASK、PSK(相对PSK和绝对PSK)条之后的波形。
6、 设一数据串为10110100,画出其对应的曼彻斯特和差分曼彻斯特编码(设初始状态为高电平)。
7、 按信号传输方向与时间的关系,发送方和接收方的通信有3种方式:单工、半双工和双工。
8、 在电话系统的干路中,若将n个音频级信号(每个带宽为4KHz)复用,警戒频带为1 KHz,问带宽至少需要多大?
9、 交换技术按原理划分,可分为线路交换和存储转发交换两种技术。其中存储转发交换又可按转发的信息单位不同,分为报文交换和分组交换。分组交换有两种常用的方法:数据报和虚电路。
10、 线路交换包括3个过程:建立线路、传输数据和释放线路
11、 简单比较线路交换和分组交换的区别。
12、 简述虚电路的原理,并比较其与数据报的区别。
交换又称转接,是在多节点网络中,利用交换机等转接设备,在节点间建立临时连接,完成通信的一种技术。
● 线路交换
● 存储转发交换
1. 报文交换
2. 分组交换
1、线路交换
● 电路交换必定是面向连接的。
● 电路交换的三个阶段:
1. 建立连接
2. 通信
3. 释放连接
● 缺点
2. 计算机数据具有突发性,这导致通信线路的利用率很低
3. 建立物理线路所花时间较长
● 优点
4. 传输延迟短
5. 一旦线路建立,就不会发生冲突
2、报文交换
● 在 20 世纪 40 年代,电报通信也采用了基于存储转发原理的报文交换(message switching)。
● 报文为传输单位,存储转发交换节点需配置大容量的存储器。
● 报文交换的时延较长,从几分钟到几小时不等。
● 适用于高信息量的数据通信。
● 现在报文交换已经很少有人使用了。
3、分组交换
● 对报文交换技术的改进
● 分组为传输单位,存储转发降低了对交换节点的存储容量的要求,缩短了网络延迟
● 适用于大型、高信息容量的数据通信
● 两种方法
1. 数据报—每个分组独立传输,分组可能经由不同的路径到达接收站,需对数据报进行排序重组
2. 虚电报—建立一条发送站和接收站之间的路径—虚电路(不是一条专用线路,它可以与其他连接共享 ),所有的分组都沿着这条虚电路按顺序传送
虚电路与线路交换的区别
线路交换是各交换节点为发送站和接收站建立一条专用的物理通路。而虚电路方式是在交换节点之间建立路由,即在交换节点的路由表内创建一个表项。当交换节点收到一个分组后,它检查路由表,按照其匹配项的出口发送分组。因此虚电路不是一条专用线路,它可以与其他连接共享。
分组交换的优点
● 高效—动态分配传输带宽,对通信链路是逐段占用。
● 灵活—以分组为传送单位和查找路由。
● 迅速—不必先建立连接就能向其他主机发送分组;充分使用链路的带宽。
● 可靠—完善的网络协议;自适应的路由选择协议使网络有很好的生存性。
分组交换带来的问题
● 分组在各结点存储转发时需要排队,这就会造成一定的时延。
● 分组必须携带的首部(里面有必不可少的控制信息)也造成了一定的开销。
4、三种交换的比较
电路交换
报文交换
分组交换
能否进行实时通信
线路接通后可进行实时会话通信,但不能实时多功能通信
非实时、存储转发,不能进行会话式通信
可接近实时存储转发,可进行会话式通信
网络传输时延
小、当建立呼叫时有一定的时延
大、报文长短影响时延大小
小
线路利用率
当进行断续通信或短报文通信时线路利用率低
高
高
通信速率和码变换
不能进行通信速率和码变换
能
能
差错控制功能
不具有
可具有
具有
传输路由
每次通信过程中路由不变
每一报文传递过程中路由不变
可以有不同路由
网络过载的影响
随着网络负荷加大,受损率增加
随着网络负荷加大,传递时延加大,引起阻塞
可进行流量控制,可在一定传递时延条件下防止阻塞
计费方式
按距离和时间计费
按字节或按字节与连接时间计费
按字节或分组数及连接时间计费
13、 光纤分为单模光纤和多模光纤两种。
14、 分别采用奇校验和偶校验,计算下列数据的校验位:0010110;1010110。
在数据后填加一个奇偶位,可以检测出数据中奇数个错误
● 奇校验
1011010 —— 10110101
● 偶校验
1011010 —— 10110100
例:使用偶校验(“1”的个数为偶数)
10110101 ——>101101011
10110001 ——>101100010
15、 设一生成多项式为g(x)=x4+x3+1,求g(x)所对应的二进制比特串。传输数据为1101001,利用上述的生成多项式,计算CRC循环冗余码。(要有计算过程)
CRC码基本思想
● 使用纠错码传数据,效率低,适用于不可能重传的场合;大多数情况采用检错码加重传。
● 校验和(checksum)加在帧尾,使带校验和的帧的多项式能被G(x)除尽;收方接收时,用G(x)去除它,若有余数,则传输出错
运算步骤:
● 设G(x)为r阶,在帧的末尾附加r个0,使帧成为m+r位,则相应的多项式是xrM (x);
● 按模2的除法用对应于G(x)的位串去除对应于xrM (x)的位串;
● 按模2的除法从对应于xrM (x) 的位串减去余数(总是等于或小于1)。结果就是要传送的带校验和的帧,叫多项式T(x)。
例如,求1011010的CRC编码,设除数为10011,,则实际发送比特为:10110101111
16、 对于16位的数据,纠正其中单比特错误所需要的最小冗余比特是多少?
码字(codeword):一个帧包括m个数据位,r个校验位,n = m + r,则此n比特单元称为n位码字。
海明距离(Hamming distance):两个码字之间不同的比特位数目。例:0000000000 与0000011111的海明距离为5
● 如果两个码字的海明距离为d,则需要d个单比特错就可以把一个码字转换成另一个码字;
● 为了检查出d个错(单比特错),需要使用海明距离为 d + 1 的编码;
● 为了纠正d个错,需要使用海明距离为 2d + 1 的编码;
设计纠错码
● 要求:m个信息位,r个校验位,纠正单比特错;
● 对2m个有效信息中任何一个,有n个与其距离为1的无效码字,因此有:(n + 1) 2m 2n。利用 n = m + r,得到 (m + r + 1) 2r,给定m,利用该式可以得出校正单比特误码的校验位数目的下界
17、 设传输数据为101101011,写出该数据的海明码。(偶校验)
海明码
● 码位从右边开始编号,从“1”开始;
● 位号为2的幂的位是校验位,其余是信息位;
● 每个校验位使得包括自己在内的一些位的奇偶值为偶数(或奇数)。
● 为看清数据位k对哪些校验位有影响,将k写成2的幂的和
海明码工作过程
● 每个码字到来前,接收方计数器清零;
● 接收方检查每个校验位k (k = 1, 2, 4 …)的奇偶值是否正确;
● 若第 k 位奇偶值不对,计数器加 k;
● 所有校验位检查完后,若计数器值为0,则码字有效;若计数器值为m,则第m位出错。
● 若校验位1、2、8出错,则第11位变反
● 使用海明码纠正突发错误
1. 可采用k个码字(n = m + r)组成 k n 矩阵,按列发送,接收方恢复成 k n 矩阵
2. kr个校验位,km个数据位,可纠正最多为k个的突发性连续比特错
例:数据: 1 0 1 1 0 1 0
d7 d6 d5 d4 d3 d2 d1
位置: 11 10 9 8 7 6 5 4 3 2 1
海明码: 1 0 1 0 1 0 1 0 0 0 0
d7 d6 d5 r8 d4 d3 d2 r4 d1 r2 r1
接收方接收到数据后,按照同样的规则进行奇偶校验得出新的r1,r2,r4,r8。如果传输正确,对于偶校验来说,这4个新值都应为0。
假设第4位发生了错误,即接收到的数据为10101011000,那么接收方计算的结果是:r1=0,r2=0,r4=1,r8=0,4位组合起来为0100,即表示第4位出现了错误,然后把1取反,从而纠正了该错误。
18、 简述退后n帧协议的思想及其窗口大小的约束条件。
退后N帧的工作原理
● 在发送完一个数据帧后,不是停下来等待确认帧,而是可以连续再发送若干个数据帧。
● 如果这时收到了接收端发来的确认帧,那么还可以接着发送数据帧。
● 由于减少了等待时间,整个通信的吞吐量就提高了。
● 要求接收方的数据链路层必须按次序把分组交给网络层。
● 当帧n的确认到达时,帧n-1,n-2等也都被自动确认。
退后N帧协议的思路
接收方将出错的帧及其后续帧一起丢弃,对出错的帧不发送确认帧;发送方在出错帧的确认帧超时后,从出错的帧开始重传所有已发送但未被确认的帧
退后N帧协议窗口大小的约束条件
考虑最大发送窗口大小为8的情况:
● 发送过程发送帧0~7帧;
● 帧7的捎带确认最终返回到发送过程;
● 发送过程发送另外8帧0~7,序号再次为0~7;
● 现在帧7的另一个捎带确认到达。
问题:第二次发送的8帧是成功了还是全部丢失了?
解决方法:发送和接收窗口尺寸小于2k,K(序列号的位数)
19、 简述选择重传协议的思想及其窗口大小的约束条件。
选择重传协议的工作原理
● 允许接收过程接收并缓存坏帧或丢失帧后面的帧。
● 接收方只把出错的帧丢弃,其后续帧保存在缓存中,向发送方发送对出错帧的非确认帧(NAK)。
● 如果落在窗口内并从未接收过,就接受此帧,并存储起来。
● 直到比它序列号小的所有帧都按次序已经交给了网络层后,此帧才提交给网络层。
选择重传协议的的思路
接收方发现有出错的帧后,只把该出错的帧丢弃,其后续帧保存在接收方的缓存中,并向发送方对出错帧的非确认帧,
发送方。发送方只要重传该出错帧,接收方正确接收到重传的出错帧后,再按帧的序列号重组并向上一层提交。
选择重传协议窗口大小的约束条件
● 发送窗口和接收窗口尺寸大小相同—两个窗口的尺寸≤2k的一半,即2k-1
●
发送窗口和接收窗口尺寸大小不同—两个窗口尺寸之和≤ 2k
20、 高级数据链路控制HDLC是一个面向位的协议,他支持半双工和全双工通信,面向位的含义是协议把帧当作位流,而不是字节流。
21、 HDLC定义了3种类型的帧,分别为信息帧、监控帧和无标号帧。
第四章
1、 分别论述3种CSMA/CD介质访问控制技术的控制过程,各自的优缺点。
载波侦听(Carrier Sense):站点在发送帧之前,首先侦听信道有无载波,若有载波,说明已有用户在使用信道,则不发送帧以避免冲突。三种方式:
● 坚持型CSMA(1-persistent CSMA)
● 非坚持型CSMA(nonpersistent CSMA)
● p-坚持型CSMA(p-persistent CSMA)
(1)坚持型CSMA(1-persistent CSMA)
● 协议思想
1. 站点有数据发送,先侦听信道;
2. 若站点发现信道空闲,则发送;
3. 若信道忙,则继续侦听直至发现信道空闲,然后 完成发送;
4. 若产生冲突,等待一个随机时间,然后重新开始发送过程
● 优点
减少了信道空闲时间
● 缺点
1. 增加了发生冲突的概率;
2. 广播延迟越大,发生冲突的可能性越大,协议性能越差
(2)非坚持型CSMA(nonpersistent CSMA)
● 协议思想
1. 若站点有数据发送,先侦听信道;
2. 若站点发现信道空闲,则发送;
3. 若信道忙,等待一个随机时间重新开始发送过;
4. 若产生冲突,等待一随机时间重新开始发送;
● 优点
减少了冲突的概率,信道效率比1-坚持CSMA高
● 缺点:
1. 不能找出信道刚一变空闲的时刻
2. 增加了信道空闲时间,数据发送延迟增大
3. 传输延迟比1-坚持CSMA大
(3)p-坚持型CSMA(p-persistent CSMA)
● 协议思想
1. 若站点有数据发送,先侦听信道;
2. 若站点发现信道空闲,则以概率p发送数据,以概率q =1- p 延迟至下一个时间槽发送。若下一个时间槽仍空闲,重复此过程,直至数据发出或时间槽被其他站点所占用
3. 若信道忙,则等待下一个时间槽,重新开始发送
4. 若产生冲突,等待一随机时间,重新开始发送
● 折中
:既能像非坚持型CSMA那样减少冲突,又能像1-坚持型CSMA那样减少媒体空闲时间的,适用于分槽信道
(4)三种CSMA协议的比较
2、 令牌环介质访问控制多用于环型拓扑结构的网络,属于有序的竞争协议。
3、 简述令牌环介质访问控制的操作过程。
● 使用一个特殊的令牌帧,当某个站点有数据帧要发送时,必须等待标记为空的令牌帧到来,将令牌帧的空标记改为忙,并将数据帧发送到环上。
● 发送的数据帧在环上循环的过程中,所经过的环上的各个站点都将帧上的目的地址与本站点的地址进行比较,若不等则直接传给后面的站点,若相等则将帧复制接收,然后继续传给后面的站点。
● 发送的数据帧在环上循环一周后再回到发送站,由发送站将该帧从环上移去,同时将令牌的忙标记改为空标记,传给后面的站。
● 空令牌帧在环上循环,经过某站点时,若该站点有数据帧要发送则重复上述过程,若该站点没有数据帧发送则直接将令牌帧传给下一个站点
令牌环的工作举例
4、 令牌总线介质访问控制多用于总线型拓扑结构的网络,其物理结构是总线的而逻辑结构却是环型的。
5、 令牌总线协议不存在单独的令牌帧格式,由控制字段说明是否包含数据,是否为令牌。
6、 局域网具有共享传输信道、传输速率较高、误码率低以及可靠性高等特点。
7、 局域网的拓扑结构大多采用总线型、环型和星型。
8、 简述IEEE802三种协议的比较。
1、802.3
● 优点
1. 使用最为广泛;
2. 算法简单;
3. 站点可以在网络运行中安装;
4. 使用无源电缆;
5. 轻负载时,延迟为0
● 缺点
1. 使用模拟器件,每个站点在发送的同时要检测冲突;
2. 最短帧长64字节,对于短数据来讲开销太大;
3. 无优先级,发送是非确定性的,不适合于实时工作;
4. 电缆最长2500米(使用中继器);
5. 速率提高时,帧传输时间减少,竞争时间不变(2),效率降低;
6. 重负载时,冲突严重
2、802.4令牌总线
● 优点
1. 发送具有确定性,支持优先级,可处理短帧;
2. 使用宽带电缆,支持多信道;
3. 重负载时,吞吐量和效率较高。
● 缺点:
1. 使用大量的模拟装置;
2. 协议复杂;
3. 轻负载时,延迟大;
4. 很难用光纤实现
3、802.5令牌环
● 优点
1. 使用点到点连接,完全数字化;
2. 使用线路中心,自动检测和消除电缆故障;
3. 支持优先级,允许短帧,但受令牌持有时间限制,不允许任意长的帧;
4. 重负载时,吞吐量和效率较高。
1. 缺点
1. 中央监控;
2. 轻负载时,延迟大。
4、三种协议帧格式比较
三种局域网的标准不兼容,差别很大。在很重的负载下,802.3局域网彻底不能用,而采用令牌的局域网则可达到接近于100%的效率;若负载范围是从轻到中等,则三种局域网都能胜任
9、 为什么一个以太网的帧有最小尺寸?
最短帧长
●
避免帧的第一个比特到达电缆的远端前帧已经发完,帧发送时间应该大于 2;
● 10Mbps LAN,最大冲突检测时间为51.2微秒,最短帧长为64字节;
● 网络速度提高,最短帧长也应该增大或者站点间的距离要减小
10、 5-4-3规定:在以太网中允许有5个网段、4个中继器和3个可以连接客户机的网段(最多使用4个中继器,构成5个网段,其中只有3个网段可以连接客户机)
11、 简单分析透明网桥和源路由网桥的工作原理和区别。
透明网桥工作原理
● 网桥接收到一帧后,通过查询交换表(地址/端口对应表)来确定是丢弃还是转发;
工作规则:
● 如果源和目的地LAN相同,则丢弃该帧;
● 如果源和目的地LAN不同,则根据目的地转发该帧;
● 如果目的地LAN未知,则进行扩散。
源路由网桥的原理
● 发送主机必须知道到所有其他机器的最佳路径: 当目的主机不在自己的LAN内时, 帧的发送者在发出的帧头内构造一个准确的路由序列,包含要经过的网桥、LAN的编号;并将发出帧的源地址的最高位置1。
透明网桥和源路由网桥的比较
透明网桥
源路由桥
面向
无连接
面向连接
透明性
完全透明
不透明
配置方式
自动
手工
路由
次优化
优化
定位
逆向学习
发现帧
失效处理
由网桥处理
由主机处理
复杂性
在网桥中
在主机中
12、 从交换机的工作方式上,可以分为穿通交换方式、存储转发交换方式和碎片丢弃方式3种。它们的含义和优缺点分别是什么?
1、 穿通交换方式是一旦接收到信息帧中的目的地址,就开始转发。不对帧进行校验。
2、 存储转发方式是将信息帧都接收完毕并进行校验确认,然后转发正确的帧,过滤处理坏帧。
3、 碎片丢弃交换方式是穿通交换方式和存储转发交换方式的折衷方案。在512bit到达交换机的输入端口后,按照目的地址转发,并不进行校验。“碎片”不会有512bit的长度。对于小于512bit的帧,交换机都视为碎片并将其丢弃
13、 VLAN与使用网桥或交换机构成的一般逻辑子网的最大区别是:不受地理位置的限制,即构成VLAN的站点所发送的数据可以广播传输到该VLAN的所有站点,而不同VLAN的站点的数据不能直接广播传输。
14、 高速局域网可以分为两大类:高速共享介质局域网和交换局域网。
第五章
1、 路由选择算法通常使用路由选择表,表中的每一项是一对地址(N,R),其中N是目标网络地址,而R是下一个路由器的地址。
2、 静态路由选择算法是指节点的路由表一旦确定不再自动改变的路由算法。
3、 最短路径算法采用迭代算法,具体思路是:建立一个节点集合,在每次的循环中逐个建立集合的元素,最后是每个节点都知道最终节点的最短路径。
最短路由选择
● 基本思想
构建子网的拓扑图,图中的每个结点代表一个路由器,每条弧代表一条通信线路。为了选择两个路由器间的路由,算法在图中找出最短路径。
● 测量路径长度的方法
1. 结点数量
2. 地理距离
3. 传输延迟
4. 距离、信道带宽等参数的加权函数
● Dijkstra算法
1. 每个结点用从源结点沿已知最佳路径到本结点的距离来标注,标注分为临时性标注和永久性标注;
2. 初始时,所有结点都为临时性标注,标注为无穷大;
3. 将源结点标注为0,且为永久性标注,并令其为工作结点;
4. 检查与工作结点相邻的临时性结点,若该结点到工作结点的距离与工作结点的标注之和小于该结点的标注,则用新计算得到的和重新标注该结点;
5. 在整个图中查找具有最小值的临时性标注结点,将其变为永久性结点,并成为下一轮检查的工作结点;
6. 重复第四、五步,直到目的结点成为工作结点
最初五步计算从A到D的最短路径,
4、 自治系统即遵循共同的路由策略统一管理下的网络群
5、 OSPF协议与SPF算法的不同点是当路由器初始化或网络结构发生变化时,才向其相邻的节点发送链路状态广播信息包,其他路由器将变化的信息包在向其相邻节点广播更新路由表。
6、 当通信子网中存在有大量的数据包,造成网络性能下降,甚至不能工作的状况,就认为网络发生了拥塞。造成拥塞的原因归根结底就是网络资源不能满足数据传输的要求。
7、 简述流量控制与拥塞控制的区别。
流量控制(flow control):与点到点的通信量有关,主要解决快速发送方与慢速接收方的问题,是局部问题,一般都是基于反馈进行控制的
拥塞控制(congestion control):需要确保通信子网能够承载用户提交的通信量,是一个全局性问题,涉及主机、路由器等很多因素
8、 拥塞控制的方法可以分为两类:预防拥塞控制方法和抑制拥塞控制方法。
1、预防拥塞控制方法
● 合理分配缓冲区法
1. 平分法
2. 最大分配法
● 许可证法
1. 限制通信子网内的分组数目,使之不超过某一固定值,从而避免拥塞。
2. 实现的方法:让固定数目的许可证在通信子网中随机巡流,任何一个想进入网络的分组必须先获得一个许可证才能进行通信,分组到达终点时须释放许可证。为了减少等待许可证所造成的延迟,每个结点保持一定小数量的许可证。这种方法能防止全局性拥塞,但仍不能完全消除局部拥塞,同时这种方法还要防止许可证的丢失。
● 漏桶算法(The Leaky Bucket Algorithm)
将用户发出的不平滑的数据包流转变成网络中平滑的数据包流
● 令牌桶算法(The Token Bucket Algorithm)
1. 假设令牌桶的大小为C(字节数),令牌产生速率为ρ(字节/s)、令牌桶的最大传输速率M(字节/s),以最大传输速率发送数据的时间为S秒,则:
2. 若在令牌产生过程中没有分组等待发送,那么经过t时间长后就回发生令牌溢出,其中t=C/ρ。
3. 假设需要发送的分组很多,并在传输分组时令牌桶是满的,则可以最大传输速率发送数据的时间为:S=C/(M-ρ)。
● 漏桶和令牌桶的区别
1. 漏桶算法不允许空闲主机保留发送权,以备以后有大的突发通信量出现时使用;令牌桶却允许,最大到桶的大小n。
2. 令牌桶算法在桶满时丢失令牌,但绝不丢失分组;与之相比,漏桶算法会在桶满时丢之分组。
2、抑制拥塞控制方法
● 负载丢弃法
1. 葡萄酒算法
2. 奶酪算法
3. 随即丢弃法
● 阻塞包算法
9、 简述漏桶算法和令牌桶算法的思想及其他们的不同点。
● 漏桶算法不允许空闲主机保留发送权,以备以后有大的突发通信量出现时使用;令牌桶却允许,最大到桶的大小n。
● 令牌桶算法在桶满时丢失令牌,但绝不丢失分组;与之相比,漏桶算法会在桶满时丢之分组。
10、 广播地址仍然包含一个有效的网络号和主机号,也称为直接广播地址。
11、 某单位有一C类IP地址网段,其网络地址为192.169.5.0,如果要将该往段分为16个子网,应如何划分?子网掩码是什么?
● 将要划分的子网数转换成最接近的2的整数幂的值;
● 将确定的幂值按从高位排序占用主机地址相应位,将其转换为十进制数;
● 写出子网掩码;
● 确定子网范围——最复杂;
10个子网,取24,占主机4位11110000,十进制为240,C类网子网掩码255.255.255.240
问题:如果是B类网呢?
例如:网络号为202.119.100,主机IP地址是202.119.100.1~202.119.100.254,10个子网的IP地址范围,如下表所示:
12、 Ipv4和Ipv6分段有什么区别?
● IPV6固定头部长度
● 协议域没有,因为Next header域指明最后IP头部后跟的是什么
● 与分段有关的域没有了。IPv6中主机能动态确定使用的数据报长度。当主机发送过大的分组时,路由器送回一条错误消息。
● 校验和域没有了,因为计算校验和会极大降低性能,而数据链路层和传输层都有自己的校验和。
13、 一个Ipv6的地址为:2060:0000:0000:0000:0009:0A00:500D:826E,用速记法可以表示为:2060::0009:0A00:500D:826E
14、 简述路由器的工作原理和工作过程。
1、路由器的工作原理
在网际层实现网络互联,具备路径选择功能,可以互联多个网络及多种类型的网络。
2、路由器的工作过程
● 信息包到达路由器排到等待处理队列,按照“先来先出”的原则等待。
● 路由器提取目标地址,查看路由表:
1. 有多条路径时,选择一条最佳路径;
2. 下一个网络允许的信息包的长度比源路径信息包长度小,路由器进行分段。