计算机网络矢量表

㈠ 计算机网络的组成

报文交换特点：1，在源与目的结点之间无须建立专用通道，对网络的故障适应能力较强；2，没有建立和拆除电路的时间延迟；3，线路利用率较高，可以进行速率上的调整；4，可靠性较高；5，每个节点对报文进行全面的处理，如果传输出错，要重发整个报文。

分组交换（packet switching）：传输的信息是报文分组，将一个长的报文分割成若干个分组来传输。

高速交换：ATM（异步传输模式）：把线路交换跟分组交换相结合。以固定长度（53字节：信元头5字节，正文48字节）。FR（帧中继）：采用永久虚电路，只要接收完帧的目的地址（不是指向本结点就立即转发帧）若传输出错，则给下游结点发送错误指示，要它终止接收，并要求上游重发该帧。

9．以数据报为例叙述交换技术的工作过程

10．CSMA/CD总线型网络的拓朴结构，帧结构及其基本工作过程

CSMA/CD（Carrier sense Multiple Access with Collision Detection）带有冲突检测的载波侦听多路访问。

拓朴结构：？

11．令牌环网的拓朴结构，帧结构及其基本工作过程

12．计算机网络流量控制的目的和流量控制的级别

目的：1，防止网络因过载而引起吞吐量下降和延时的增加；2，减少拥塞，避免死锁；3，在互相竞争的用户之间公平合理地分配资源。

四种级别：1，相邻结点间的流量控制，2，源结点和目的结点间的流量控制；3，主机与源结点间的流量控制；4，源主机与目的主机间的流量控制。

13．关于源路由网桥的概念和工作原理（P102）

源路由网桥（IEEE802。5工作组选用的网桥，面向令牌环网）：是指源站点要提供侦传送的路由信息，该路由信息（Routing Information）设置在该帧的头部，用于标识帧的传输路径（面向连接的网桥）。

工作原理：源站要向目的站通信前，必须寻找通向目的站的路径（实际上是建立连接的过程：源站首先向全网广播一个“探测帧”，该帧每经过一个网桥，网桥把自己相关路由信息写入该探测帧，为该到达目的站时，该数据包就记录下一张它所经过的路径图（路由表）。目的站会使这个探测帧返回（实际由目的站发出一个应答帧）当源站接收到应答帧时，则可以说连接已建立）。

14．关于透明网桥的概念和工作原理（P99）

所谓透明网桥是指网桥的操作过程对其端口上连接的网段上的工作站是“透明的”，换句话说，工作站用户并不知道网桥的存在。

15．路由器的基本工作过程及其作用

基本工作过程：

A， 路由器工作在网络层，它的传输单位是分组（packet），又称数据包

B， 当路由器接收到一个包时，首先进行拆包，把数据链路层的信息去掉，读取网络层的信息

C， 根据包的目的地址（指向）进行：本地提交（本网是目的结点所在网络）；分组转发（选择转发路由）

D，数据安全性检查（转发检验）

E， 通过安全检查后，则进行打包，（封装）加入数据链路层的信息，转发该包。

基本功能：

1， 协议转换

2， 路由选择

3， 支持多协议的路由选择

4， 流量控制

5， 分组的分段与组装

6， 网络管理功能

（未完成）16．路由选择算法的分类和理想路由选择算法应具有的特点

路由算法有：距离矢量算法和链路状态算法。

距离矢量算法：以某一参考点到达目的结点的距离作为度量的算法。这里的距离指该路径上所经历的最少网关（也指路由器）数。

链路状态算法：实际上是一种“最短路径优先”的算法。

特点：？

17．距离向量算法和RIP的工作过程(p110)

距离向量算法的基本思想：以某一参考点到目的结点的距离作为算法的度量。

RIP（routing Information Protocol）路由信息协议工作过程：1，初始化（启动RIP协议）；2，路由表交换路由信息；3，路由表更新（最知线路优先）。（P113）

18．路由器的主机名和端口配置使用方法

配置主机名（路由器）：每台路由器主机的缺省名Router。假设把它配置为路由器R2则输入命令：

router (config) #host name Router (R2)

显示：Router R2 (config) #

端口配置（端口地址配置）：

① Router R2 (config) # interface eithernet 0

② Router R2 (config-if) # ip address 200.111.50.1 255.255.255.0

配置端口的IP地址：200.111.50.1

相应的子网掩码：255.255.255.0

③ Router R2 (config ) # interface serial 0 (0是串行口)

④ Router R2 (config-if)# ip address 128.120.1.1 255.255.255.0

19．奈奎斯特和香农定律原理

（离散信号的信道容量）奈奎斯特定律：C = 2 F log2 L (bps) 每秒的信道容量，信道的最大传输速率

C：信道容量。 F：带宽。 L：符号的离散取值。

（连续信号的信道容量）香农定律：C = F log2 (1+S/N)

S:通过的信号平均功率。 N：噪声（干扰信号）的功率。所谓噪声是指干扰信号（噪声）在所有频率上的强度都一样。 S/N：采用信噪比来代替。 SNR 其单位是分贝。DB

分贝值 = 10 log10 (S/N) 分贝值是可测量的。则可利用分贝值得到S/N。

20．计算机网络中常用的编码技术

（1） 单极性不归零编码（NRZ）

（2） 曼彻斯特编码（Manchester Encoding）

（3） 差分曼彻斯特编码

21．画图说明频移键控法的工作原理

22．PCM技术的基本工作步骤

1， 取样：按照一定的时间间隔采样测量模拟信号幅值

2， 量化：将取样点测量的信号幅值分级取整

3， 编码：将量化的结果（整数据）用二进制数表示出来

23．异步传输的编码结构

也叫“起/停方式”：每传送1个字符（5bit/8bit）都在字符前面加入一位开始位（“0”表示使用停电平表示传送开始），而在代码校验（奇/偶）后面跟随停止位（1位，3/2位或2位，用“1”高电平表示，代表字符传输结束）

以ASCII码的A字符为例（11位异步码结构）

A字符：41H = 1000001 编码后：01000001111

24．HDLC的帧结构和基于比特流的传输控制流程规程的主要特性

HDLC(High Data Link Control)高级数据链路控制：基于比特传输的控制规程。主要特征如下：

① 通信方式：全双工

② 差错控制：循环冗余码（CRC）

③ 同步方式：同步

④ 电码：随机码（任意二进制编码）

⑤ 信息长度：可变区

⑥ 速率：2400bps以上

⑦ 发关方式：连续发送，即发送方送出一个信息帧后，不等接收方的应答，则继续发关随后的帧，接收方的应答信号是利用全双工的另一信道在它发送给发送方的信息帧的控制字段中夹带回“已收到某编号的信息帧”（期待接收某个编号的帧）这表明此号帧以前的信息帧已正确接收。如果发现传输出错，则请求重传该号帧及其随后的帧。

HDLC的帧结构：

F
A
C
I
FCS
F

同步标志（01111110） 地址 控制字段 正文 循环冗余码 标志

25．计算机网络中使用的循环冗余码校验的工作原理

26．多路复用的基本思想和种类

多路复用原理：就是让一条线路复用成多个子信道来使用

种类有：

1， 频分多路复用（FDM）：分割线路的带宽，形成多个子信道（频度）

2， 同步时分多路复用（TDM）：分割线路的传输时间形成多个子信道（一个时间片）时隙

3， 统计时分多路复用（STDM）：分割线路的传输时间。但动不是固定给用户分配时间片，而是需要传送时，才给它分配时间片。

4， 波分多路复用（WOM）：光纤上使用分割的是信号光的波长

27．频分多路复用的工作原理

28．时分多路复用的种类和各自的工作特性

29．会话层的同步方法

为了控制信息流同时能够从软件或操作失误中恢复过来，会话层允许在数据中插入同步点，当出现故障时，找到故障处的前一个同步点并从该同步点进行恢复，这个过程称为再同步。对话过程中可以插入次同步点，如果传输中出了故障，控制流可以退回到对话中的一个或多个次同步上进行恢复。主同步点必须被确认，次同步点不需要确认。

30．表示层的局部语法和传送语法

局部语法：某一具体计算机所使用的语法称为局部语法。局部语法的差异使得同一数据对象在不同的计算机中被表示成不同的比特序列。

传送语法：符全传送过程要求的语法。数据以传送语法的形式在网络中传送，发送方将符合自己局部语法的比特序列转换成符合传送语法的比特序列。

31．交换机的交换结构和各自的特点

交换结构有：软件执行交换结构、矩阵交换结构、总线交换结构、共享存储器交换结构。

软件执行交换结构：借助CPU和RAM的硬件环境，用特定的软件来实现端口之间的帧交换。所有功能均由软件来实现，操作灵活，但随着端品数和增加，CPU的负担加重。

矩阵交换：采用硬件方法进行交换。优点是利用硬件交换，结构紧凑，交换速度快，延迟时间短，缺点是随着端口的增加，监控和管理变得困难。

总线交换：对总线的带宽要求较高，造价高，但性能也好。

存储交换：结构简单、容易实现，但通过RAM操作会产生延时。

32．交换机的组成和各部分的主要作用

大多数交换器都有一块背板，把各种板卡插在其上面，实现相应连接，交换器的主要部件包括控制、逻辑、阵列、及端口四个。

1， 控制部件：其作用是控制、管理交换器，识别连接到各端口的局域网的类型，并自动地进行交换器的测试

2， 逻辑部件：其作用是读取输入数据帧的目的地址，并以此目的地址与端口地址表中的内容进行比较，找出该目的地址对应的端口号，批示阵列部件按通对应的（输出端口）矩阵开头（来接到输出端口）

3， 阵列部件：一旦接收到逻辑部件的指令时，启动源端口（输入）与目的端口（输出）之间的交叉连接，并保持该连接直到该帧全部传送完

4， 端口部件：可以看成一组物理接口

33．交换机的转发率和过滤率

交换器的过滤率是在某段时间内（通常为1秒）所解释多少帧的目的地址，这种能力称为过滤率。

转发率是指在某段时间内（1秒）所转发帧的数目，称为转发率。

34．如何使用交换机、集线器、路由器、防火墙和常用传输介质组建企业网络

35．关于VLAN的定义和其主要功能（P87）

VLAN（virtual LAN）虚拟局域网：建立在物理交换机之上的，它利用软件进行逻辑工作组的划分和管理。

36．X．25的协议体系结构

X.25协议是CCITT关于公用数据网上以分组方式工作的DTE与DCE之间的接口标准，其功能是为公用数据网在分组交换方式下提供终端操作，它不涉及通信子网的内部结构。

层次结构：自下至上分别称为物理级、帧级、分组级。

37．帧中继的基本工作原理

38．ATM的协议参考模型（P141）

39．ATM交换技术的特点

特点：

（1） 采用面向连接的工作方式。

（2） 采用异步时分多路方式

（3） 网络没有逐段链路的差错控制和流量控制。

（4） 信头功能简单

（5） 小的信元长度

40．ATM交换虚连接的工作过程（P132）

41．什么是ISDN，定义了哪些设备和接口

ISDN是用来解决一些小的办公室或拨号用户需要比传统电话拨号服务能提供更宽传输带宽的应用，同时ISDN也可用来提供线路备份。

42．IP地址结构和子网划分的作用

结构：每个IP地址共有32位，分为4段，以X。X。X。X表示，每个X为8位，取值为0~255。分为网络地址和主机地址两部分，其中网络地址表示一个网络，主机地址用来表示这个网络中的一台主机。

子网划分作用：

㈡ 计算机网络中的路由器使用距离向量算法

1、假设路由器使用距离向量算法，下图给出了网络拓扑及路由器的初始路由表（只包含部分字段），假设A给B传了一次路由信息，B处理后又也给C传了一次路由信息，请在表中填写经过路由信息交换之后B和C的路由表（相邻路由器间距离计为1）。
2、B路由器增加2条：10.3.0.0 s0 1
10.4.0.0 s1 1
3、C路由器增加2条：10.3.0.0 s0 2
10.2.0.0 S0 1

㈢ 计算机网络自学笔记：选路算法

网络层必须确定从发送方到接收方分组所经过的路径。选路就是在网络中的路由瞎物器里的给某个数据报确定好路径(即路由)。

一 台主机通常直接与一台路由器相连接，该路由器即为该主机的默认路由器，又称为该主机的默认网关。 每当某主机向外部网络发送一个分组时，该分组都被传送给它的默认网关。

如果将源主机的默认网关称为源路由器,把目的主机的默认网关称为目的路由器。为一个分组从源主机到目的主机选路的问题于 是可归结为从源路由器到目的路由器的选路问题。

选路算法的目标很简单:给定一组路由器以及连接路由器的链路，选路算法要找到一条从源路由器到目的路由器的最好路径，通常一条好路径是指具有最低费用的路径。

图 G=(N，E)是一个 N 个节点和 E 条边的集合，其中每条边是来自 N 的一对节点。在网 络选路的环境中，节点表示路由器，这是做出分组转发决定的节点，连接节点的边表示路由 器之间的物理链路。

一条边有一个值表示它的费用。通常一条边的费用可反映出对应链路的物理长度、链路速度或与该链路相关的费用。

对于 E 中的任一条边(xy)可以用 c(xy )表示节点 x 和 y 间边的费用。一般考虑的都是无向 图，因此边(xy)与边(y x)是相同的并且开销相等。节点 y 也被称为节点 x 的邻居。

在图中为各条边指派了费用后，选路算法的目标自然是找出从源到目的间的最低费用路径。图 G=(N，E)中的一条路径(Path)是一个节点的序列，使得每一对以(x1,x2)， (x2,x3)，…，是 E 中的边。路径的费用是沿着路径所有边费用的总和。

从广义上来说，我们对 选路算法分类的一种方法就是根据该算法是全局性还是分布式来区分的。

.全局选路算法： 用完整的、全局性的网络信息来计算从源到目的之间的最低费用路径。

实际上， 具有全局状态信息裂歼的算法常被称作链路状态 LS 算法， 因为该算法必须知道网络中每条链路的费用。

.分布式选路算法： 以迭代的、分布式的方式计算出最低费用路径。通过迭代计算并与相邻节点交换信息，逐渐计算出到达某目的节点或一组目的节点的最低费用路径。

DV 算法是分布式选路算法， 因为每个节点维护到网络中的所有其他节点的费用(距离)估计的矢量。

选路算法的第二种广义分类方法是根据算法是静态的还是动态的来分类。

一： 链路状态选路算法 LS

在链路状态算法中，通过让每个节点向所有其他路由器广播链路状态分组， 每个链路状态分组包含它所连接的链路的特征和费用， 从而网络中每个节点都建立了关于整个网络的拓扑。

Dijkstra 算法计算从源节点到网络中所有其他节点的最低费用路径.

Dijkstra 算法是磨源液迭代算法，经算法的第 k 次迭代后，可知道到 k 个目的节点的最低费用路径。

定义下列记号:

D(V)随着算法进行本次迭代，从源节点到目的节点的最低费用路径的费用。

P(v)从源节点到目的节点 v 沿着当前最低费用路径的前一节点(，的邻居)。

N`节点子集；如果从源节点到目的节点 v 的最低费用路径已找到，那么 v 在 N`中。

Dijkstra 全局选路算法由一个初始化步骤和循环组成。循环执行的次数与网络中的节点个数相同。在结束时，算法会计算出从源节点 u 到网络中每个其他节点的最短路径。

考虑图中的网络，计算从 u 到所有可能目的地的最低费用路径。

.在初始化阶段 ，从 u 到与其直接相连的邻居 v、x、w 的当前已知最低费用路径分别初始化为 2，1 和 5。到 y 与 z 的费用被设为无穷大，因为它们不直接与 u 连接。

.在第一次迭代时， 需要检查那些还未加到集合 N`中的节点，找出在前一次迭代结束时具有最低费用的节点。那个节点是 x 其费用是 1，因此 x 被加到集合 N`中。然后更新所有节点的 D(v)，产生下表中第 2 行(步骤)所示的结果。到 v 的路径费用未变。经过节点 x 到 w 的 路径的费用被确定为 4。因此沿从 u 开始的最短路径到 w 的前一个节点被设为 x。类似地， 到 y 经过 x 的费用被计算为 2，且该表项也被更新。

.在第二次迭代时 ，节点 v 与 y 被发现具有最低费用路径 2。任意选择将 y 加到集合 N` 中，使得 N’中含有 u、x 和 y。通过更新，产生如表中第 3 行所示的结果。

.以此类推…

当 LS 算法结束时，对于每个节点都得到从源节点沿着它的最低费用路径的前继节点， 对于每个前继节点，又有它的前继节点，按照此方式可以构建从源节点到所有目的节点的完 整路径。

根据从 u 出发的最短路径，可以构建一个节点(如节点 u)的转发表。

二 距离矢量选路算法 DV

LS 算法是一种使用全局信息的算法，而距离矢量算法是一种迭代的、异步的和分布式的算法。

Bellman-Ford 方程：

设 dx(y)是从节点 x 到节点 y 的最低费用路径的费用，则有  dx(y) = min {c(x,v) + dv(y) }

PS： 方程中的 min，是指取遍 x 的所有邻居。

Bellman-Ford 方程含义相当直观，意思是从 x 节点出发到 y 的最低费用路径肯定经过 x 的某个邻居，而且 x 到这个邻居的费用加上这个邻居到达目的节点 y 费用之和在所有路径 中其总费用是最小的。 实际上，从 x 到 v 遍历之后，如果取从 v 到 y 的最低费用路径，该路 径费用将是 c(x,v)+ dv(y)。因此必须从遍历某些邻居 v 开始，从 x 到 y 的最低费用是对所有邻 居的 c(x,v)+dv(y)的最小值。

在该 DV 算法中，当节点 x 看到它的直接相连的链路费用变化，或从某个邻居接收到一 个距离矢量的更新时，就根据 Bellman-Ford 方程更新其距离矢量表。

三 LS 与 DV 选路算法的比较

DV 和 LS 算法采用不同的方法来解决计算选路问题。

在 DV 算法中，每个节点仅与它的直接相连邻居交换信息，但它为它的邻居提供了从其 自己到网络中(它所知道的)所有其他节点的最低费用估计。

在 LS 算法中，每个节点(经广播)与所有其他节点交换信息，但它仅告诉它们与它直接 相连链路的费用。

·报文复杂性：

LS 算法要求每个节点都知道网络中每条链路的费用，需要发送 O(nE)个消息。

DV 算法要求在每次迭代时，在两个直接相连邻居之间交换报文，算法收敛所需的时间 依赖于许多因素。当链路费用改变时，DV 算法仅当在会导致该节点的最低费用路径发生改 变时，才传播已改变的链路费用。

·收效速度：

DV算法收敛较慢，且在收敛时会遇到选路环路。DV算法还会遭受到计数到无穷的问题。

•健壮性：  在 LS 算法中，如果一台路由器发生故障、或受到破坏，路由器会向其连接的链路广播 不正确费用，导致整个网络的错误。

在 Dv 算法下， 每次迭代时，其中一个节点的计算结果会传递给它的邻居，然后在下次迭代时再间接地传递给邻居的邻居。在这种情况下，DV 算法中一个不正确的计算结果也会扩散到整个网络。

四.层次选路

两个原因导致层次的选路策略：

•规模： 随着路由器数目增长，选路信息的计算、存储及通信的开销逐渐增高。

•管理自治： 一般来说，一个单位都会要求按自己的意愿运行路由器(如运行其选择的某 种选路算法)，或对外部隐藏其内部网络的细节。

层次的选路策略是通过将路由器划分成自治系统 AS 来实施的。

每个 AS 由一组通常在相同管理控制下的路由器组成(例如由相同的 ISP 运营或属于相同 的公司网络)。在相同的 AS 内的路由器都全部运行同样的选路算法。

在一个自治系统内运行的选路算法叫做自治系统内部选路协议。 在一个 AS 边缘的一台 或多台路由器，来负责向本 AS 之外的目的地转发分组，这些路由器被称为网关路由器

在各 AS 之间，AS 运行相同的自治系统间选路协议。

㈣ 计算机网络中的距离向量算法（RIP）的基本原理

RIP协议采用距离向量算法，在实际使用中已经较少适用。在默认情况下，RIP使用一种非常简单的度量制度：距离就是通往目的站点所需经过的链路数，取值为1~15，数值16表示无穷大。RIP进程使用UDP的520端口来发送和接收RIP分组。RIP分组每隔30s以广播的形式发送一次，为了防止出现“广播风暴”，其后续的的分组将做随机延时后发送。在RIP中，如果一个路由在180s内未被刷，则相应的距离就被设定成无穷大，并从路由表中删除该表项。RIP分组分为两种：请求分组和响应分组。

㈤ 距离矢量路由算法 （计算机网络题

通过B到个点的距离为：(11，6，14，18，12，8)，因为B到A的距离为5，C到B的距离为6所以C到A的距离更新为5+6=11，C到B的距离没变为6，C通过B到C的距离为6+8=14，C通过B到D的距离为6+12=18，C通过B到E距离6+6=12，C通过B到F距离为6+2=8。

通过D到个点的距离为：(19，15，9，3，12，13)，通过D到A的距离为3+16=19，通过D到B的距离为3+12=15，通过D到C的距离为6+3=9，通过D到D的距离为3，通过D到E的距离为3+9=12，通过D到F的距离为3+10=13。

通过E到个点的距离为：(12，11，8，14，5，9)，通过E到A的距离为5+7=12，通过E到B的距离为5+6=11，通过E到C的距离为5+3=8，通过E到D的距离为5+9=14，通过E到Eden距离为5，通过E到F的距离为9。

取到达每一目的地的最小值(C除外)得到: (11， 6，0，3, 5，8)就得出了新的路由表。输出的路线输出线路是: (B,，B， -，D，E， B)。

(5)计算机网络矢量表扩展阅读：

路由算法的度量标准：

路由算法使用了许多种不同的度量标准去决定最佳路径。复杂的路由算法可能采用多种度量来选择路由，通过一定的加权运算，将它们合并为单个的复合度量、再填入路由表中，作为寻径的标准。

通常所使用的度量有：路径长度、可靠性、时延、带宽、负载、通信成本等。

路径长度：

路径长度是最常用的路由。一些路由协议允许网管给每个网络连接人工赋以代价值，这种情况下，路由长度是所经过各个链接的代价总和。

可靠性：

可靠性，在路由算法中指网络连接的可依赖性（通常以位误率描述），有些网络连接可能比其它的失效更多，网路失效后，一些网络连接可能比其它的更易或更快修复。

路由延迟：

路由延迟指分组从源通过网络到达目的所花时间。很多因素影响到延迟，包括中间的网络连接的带宽、经过的每个路由器的端口队列、所有中间网络连接的拥塞程度以及物理距离。

带宽

带宽指连接可用的流通容量。在其它所有条件都相等时，10Mbps的以太网链接比64kbps的专线更可取。虽然带宽是链接可获得的最大吞吐量，但是通过具有较大带宽的链接做路由不一定比经过较慢链接路由更好。

负载：

负载指网络资源，如路由器的繁忙程度。负载可以用很多方面计算，包括CPU使用情况和每秒处理分组数。持续地监视这些参数本身也是很耗费资源的。

通信代价：

通信代价是另一种重要的metric，尤其是有一些公司可能关心运作费用甚于关心性能。即使线路延迟可能较长，他们也宁愿通过自己的线路发送数据而不采用昂贵的公用线路。

参考资料来源：网络-路由算法