计算机网络网络层路由算法34页PPT

在日常生活中，随处都可以看到浪费 粮食的 现象。 也许你 并未意 识到自 己在浪 费，也 许你认 为浪费 这一点 点算不 了什么
非自适应路由算法
固定路由算法（fixed routing algorithm） 洪泛法（flooding） 随机走动法（random walk） 基于流量的路由算法（flow-based routing）
由所有的线路平均延迟，可直接计算出流量的加权 平均值，从而得到整个网络的平均分组延迟
这样找出网络的最小平均延迟就可以实现最优路由 选择
在日常生活中，随处都可以看到浪费 粮食的 现象。 也许你 并未意 识到自 己在浪 费，也 许你认 为浪费 这一点 点算不 了什么
自适应路由算法
孤立路由选择 集中路由选择 分布式路由选择
当结点或链路发生故障时，该方法可使路由算法有 较好的稳健性
在日常生活中，随处都可以看到浪费 粮食的 现象。 也许你 并未意 识到自 己在浪 费，也 许你认 为浪费 这一点 点算不 了什么
基于流量的路由算法
该方法不仅考虑网络的拓扑结构，还要考虑网络的 负载因素
对某一给定的线路，如果已知负载量与平均流量， 那么可以根据排队论的知识计算出该线路上的平均 分组延迟
• 如果找不到相应的表项，在G的路由表中增加一项 ：(N,G’,D’+C)
• 如果V=G’，G中路由表对应的表项根据D’+C和D的 比较获得
– 如果D’+C<D，G中表项更新为(N,G’,D’+C)
– 否则G中表项保持原状，仍为(N,V,D)
在日常生活中，随处都可以看到浪费 粮食的 现象。 也许你 并未意 识到自 己在浪 费，也 许你认 为浪费 这一点 点算不 了什么

66、节制使快乐增加并使享受加强。 ——德 谟克利 特 67、今天应做的事没有做，明天再早也 是耽误 了。——裴斯 泰洛齐 68、决定一个人的一生，以及整个命运 的，只 是一瞬 之间。 ——歌 德 69、懒人无法享受休息之乐。——拉布 克 70、浪费时间是一桩大罪过。——卢梭
计算机网络网络层路由算法
11、获得的成功越大，就越令人高兴 。野心 是使人 勤奋的 原因， 节制使 人枯萎 。 12、不问收获，只问 太多， 那样只 会使人 胆孝懒 惰，因 为不实 践，甚 至不接 触社会 ，难道 你是野 人。(名 言网) 13、不怕，不悔(虽然只有四个字，但 常看常 新。 14、我在心里默默地为每一个人祝福 。我爱 自己， 我用清 洁与节 制来珍 惜我的 身体， 我用智 慧和知 识充实 我的头 脑。 15、这世上的一切都借希望而完成。 农夫不 会播下 一粒玉 米，如 果他不 曾希望 它长成 种籽； 单身汉 不会娶 妻，如 果他不 曾希望 有小孩 ；商人 或手艺 人不会 工作， 如果他 不曾希 望因此 而有收 益。-- 马钉路 德。

如果I，J，K的最佳路由是r1+r2，则当I把分组交 给J时，J一定会沿着r2把分组转发出去。
北邮计算机学院：⺩王小小茹
汇集树(Sink Tree)
计算机学院：王小茹
Shortest Path Routing 5.2.2 最短路径路由算法
北邮计算机学院：⺩王小小茹
计算机学院：王小茹
智能科学与网络工程系：王小茹
一一个好消息，A链路修好了！
A D
B 2 C C 1 C D 0-
B
B 0 C 1 C D 2 C
C
B1 B C0 D1 D
初始时：
A
B 0 C 1 C D 2 C B
B1 B C0 D1 D C
B 2 C C 1 C D 0D
n
思考：
n n n n
A需要多久才能获得全⺴网网的路由信息？ B需要多久才能知道可达A的路由信息？ C需要多久才能知道可达A的路由信息？ D需要多久才能知道可达A的路由信息？
数据报服务
北邮计算机学院：⺩王小小茹
数据报服务和虚电路服务 优缺点的归纳
对比的方面 服务 分组的顺序 一定 到达目的站 序 端到端的 负责 差错处理和 可以由分组交换网 负责也可以由用户 由用户主机
北邮计算机学院：⺩王小小茹
虚电路服务
数据报
总是按发送顺序
到达目的站时不 按发送顺
ROUTING ALGORITHMS 5.2 路由算法
B C D 1 0 1 B D
B 2 C C 1 C D 0D
B C D 2 1 0 C C -
C C A
-
A B C D A B C D
2 1 0 1 2 1 0 1
B B D B B D

仅和相邻路由器交换信息。 交换的信息是当前本路由器所知道的全部信息，即自 己的路由表。 按固定的时间间隔交换路由信息，例如，每隔 30 秒。
RIP协议的工作过程
路由表的建立 初始化的路由器的路由表中只有直连路由（距离是1） RIP启动和运行过程 路由器刚启动RIP时，以广播形式向其相邻路由器发送请求报文， 相邻路由器响应该请求，并回送包含本地路由信息的相应报文。 路由器周期性地向外发送路由刷新报文；路由表信息不断更新。 路由刷新报文主要内容是由若干（V，D）组成的表；
“距离”的定义
从一路由器到直接连接的网络的距离定义为 1。 从一个路由器到非直接连接的网络的距离定义为所经 过的路由器数加 1。 RIP 协议中的“距离”也称为“跳数”(hop count)， 因为每经过一个路由器，跳数就加 1。
“距离”的定义
RIP 认为一个好的路由就是它通过的路由器的数目少，即 “距离短”。
自治系统（ＡＳ,Autonomous system）
将Internet划分成多个相对独立的系统，相对独立的系统中各组织可以采 用自己的规则和管理策略。每个相对独立的系统称为自治系统（ＡＳ）。 每个自治系统由Internet注册机构分配一个唯一的数字编号来标识。
一个自治系统（ＡＳ）由同一机构管理，使用统一选路策略的路由器的 集合。自治系统内部的路由选择称为域内路由选择，运行内部网关协议 （IGP，interior Gateway Protocol）；自治系统之间的路由选择称 为域间路由选择，运行外部网关协议（EGP, External Gateway protocol） 。
引入自治系统（ＡＳ）的基本思想：通过不同的编号来区分不同的自治系 统通过采用路由协议和自治系统编号，路由器就可以确定彼此间的路径和 路由信息的交换方法。

elnN个。当然由分层引起的路径 长度的实际增长非常小。
精选课件
18
广播路由
同时给全部的目标地址发送一个 数据包称为广播
扩散法。
多目标路由：每个数据包含一组 目标地址，经过路由器，针对目 标选路，目标分散
逆向路径转发（reverse path forwarding)
沿汇集树（sink tree）生成树
类似的值。
假设使用延迟作为距离度量，并且路由器知道他到 每个邻居的延迟。每隔T秒每个路由器向他的每个 邻居发送一个表，该表记录了它到每个目标的延迟， 同时它也从邻居那里收到一个类似的表。
精选课件
7
交换距离信息更新路由表示例
精选课件
8
无穷计算问题
A BCD E
A BCD E
∞∞∞ 1 ∞∞ 12∞ 123 123
reverse routes.
路径维护
每个节点周期性的广播一个 HELLO消息并期望它的邻居 做出回应，如果回应没有到 来说明消息广播者已经知道 它的邻居已失效或离开接收 范围，因而不再跟自己有连 接。这些信息用来清除掉那 些不再有效的消息。
精选课件
31
在最近的T时间内曾经给它发送 过到达该目标的邻居—该目标的 活动邻居
（a）
∞ 初始时
1
∞ 第1次交换后 3
∞ 第2次交换后 3 ∞ 第3次交换后 5
4 第4次交换后 5
7
7
∞
23 23 43 45 65 67 8... 7 ∞∞
（b）
4 初始时 4 第1次交换后 4 第2次交换后 4 第3次交换后 6 第4次交换后 6 第5次交换后 8 第6次交换后
∞
问题的核心在于当X告诉Y自己有一条通往某个地方的路径

应用层
综合了OSI的会话层、表 示层和应用层的功能，提 供各种网链路层相同 ，负责将比特流组合成帧 并进行传输。
网络层
传输层
与TCP/IP的传输层相同， 提供可靠的传输服务。
与TCP/IP的网络层相同， 处理IP地址和路由选择。
Part
03
物理层
物理层的基本概念
物理层的定义
THANKS
感谢您的观看
实现Web应用中的请求/响应模型，支持 Web页面的浏览和数据传输。
HTTP的请求方法
GET、POST、PUT、DELETE等，定义了客 户端对资源的操作方式。
HTTP的状态码
HTTP的消息格式
表示服务器对请求的处理结果，如200表示 成功，404表示资源未找到。
包括请求行、请求头、请求体、响应行、响 应头、响应体等部分，定义了HTTP消息的 格式和内容。
网络层的主要功能
网络层的主要功能包括路 由选择、拥塞控制和网络 互连等。
网络层的协议
网络层的主要协议包括IP 协议、ICMP协议、IGMP 协议等。
路由算法与路由协议
01 02
路由算法的分类
路由算法可以分为静态路由算法和动态路由算法两类。静态路由算法由 管理员手动配置，而动态路由算法则通过路由协议自动学习和更新路由 信息。
常见的路由协议
常见的路由协议包括RIP、OSPF、BGP等。这些协议通过不同的算法和 机制来实现路由信息的交换和更新。
03
路由协议的工作原理
路由协议通过定期发送和接收路由信息报文来交换和更新网络中的路由
信息。当网络拓扑发生变化时，路由协议会自动重新计算最佳路径并更
新路由表。
IPv4与IPv
IPv4的基本概念

⽹络层的路由算法概述概念什么是转发？分组到达, 取出⽬标地址,查看转发表, 将分组转发出去⼀个节点的局部操作什么是转发表？转发表的每⼀⾏必须包含从要到达的⽬的⽹络，到输出端⼝和某些MAC地址信息（如下⼀跳以太⽹地址）的映射。

什么是路由？根据分组中包含的信息（⽬标地址）找到转发路径，是建⽴路由表的过程，要使⽤路由算法数据报的路由每⼀个到达的分组虚电路的路由建⽴虚电路时会话路由：会话期间，⼀直保持什么是路由表？⽹络号到下⼀跳 (IP addresses)不同于数据链路层转发表的格式不同转发表的更新⽅法不同回忆⼀下数据链路层是啥样⼦的呢？转发表⽬标的物理地址和转发的端⼝号表的更新⼿⼯配置反向学习MAC Port#⽽⽹络层是这样的：转发表⽬标⽹络到下⼀跳地址(or 接⼝)表的更新直接连接⼿⼯配置 (static route)通过路由协议（dynamically route）NetNum NextHop/Interface#⽬标Correctness(正确性) Simplicity (简单性) Robustness (健壮性) Stability (稳定性) Fairness (公平性) Optimality (最优性)分类静态路由算法根据⽹络初始状态进⾏路由选择不能适应⽹络拓扑的变化⼿⼯配置转发表动态路由算法根据⽹络当前信息量和拓扑结构进⾏路由选择周期更新对链路通信代价变化及时响应需要路由协议交换信息优化原则优化原理：如果路由器 J 在从路由器 I 到 K 的最佳路径上则从 J to K 的最佳路也在同⼀路上从所有源到给定⽬标的最佳路由的集合称为汇集树 (sink tree)路由算法的⽬标就是 discover the sink tree for all router。

防火墙技术原理及应用
防火墙技术原理
通过设置规则，允许或阻止特定类型的数据包通过பைடு நூலகம்从而达 到保护网络安全的目的。
防火墙技术应用
在企业网络中，通常将防火墙部署在网络出口处，用于过滤 进出网络的数据包，防止未经授权的访问和攻击。
网络管理策略制定与实施
网络管理策略制定
根据企业的业务需求和网络环境，制定相应的网络管理策略，包括网络访问控制、数据 备份与恢复、网络安全审计等。
包括Wi-Fi、4G/5G等，为用户提供灵活、便捷的网络接入方式 。
家庭宽带接入方式介绍
ADSL接入
利用普通电话线提供宽带接入服务，速度较 慢，但价格相对较低。
小区宽带
由运营商在小区内建设宽带网络，为用户提 供宽带接入服务。
光纤到户（FTTH）
将光纤直接接入用户家中，提供高速、稳定 的宽带服务。
电力线通信（PLC）
根据网络覆盖范围的不同，计算机网络可分为局域网（LAN）、城域网（MAN ）、广域网（WAN）等；根据网络拓扑结构的不同，可分为星型、环型、总线 型、树型、网状等；根据传输介质的不同，可分为有线网和无线网。
计算机网络的功能与应用
功能
计算机网络具有数据通信、资源共享、分布式处理等功能，可以大大提高计算机系统的效能和方便性 。
计算机网络技术基础ppt课件 完整版
目录
• 计算机网络概述 • 网络体系结构及协议 • 局域网技术 • 广域网技术 • 网络互联与接入技术 • 网络安全与管理策略
01
计算机网络概述
计算机网络的定义与发展
定义
计算机网络是指将地理位置不同、功能独立的多个计算机系统通过通信设备和 线路连接起来，以功能完善的网络软件（网络协议、信息交换方式及网络操作 系统等）实现网络中资源共享和信息传递的系统。

计算机⽹络-⽹络层-路由算法计算机⽹络-⽹络层-路由算法最优化原则1.最佳路径的每⼀部分也是最佳路径如果路由器J在从路由器I到K的最优路径上，那么从J到K的最优路径必定沿着同样的路由路径2.通往路由器的所有最佳路径的并集是⼀棵称为汇集树3.路由算法的⽬的为所有路由器找出并使⽤汇集树最短路径路由Dijkstra算法1.每个节点⽤从源节点沿已知最佳路径到该节点的距离来标注，标注分为临时性标注和永久性标注2.初始时，所有节点都为临时性标注，标注为⽆穷⼤3.将源节点标注为0，且为永久性标注，并令其为⼯作节点4.检查与⼯作节点相邻的临时性节点，若该节点到⼯作节点的距离与⼯作节点的标注之和⼩于该节点的标注，则⽤新计算得到的和重新标注该节点5.在整个图中查找具有最⼩值的临时性标注节点，将其变为永久性节点，并成为下⼀轮检查的⼯作节点6.重复第四、五步，直到⽬的节点成为⼯作节点泛洪算法描述⼀种将数据包发送到所有⽹络节点的简单⽅法,每个节点通过将其发送到所有其他链接之外来泛洪在传⼊链接上接收到的新数据包，它属于静态算法问题重复的数据包，由于循环可能会⽆限多节点需要跟踪已泛洪的数据包以阻⽌洪泛即使在跳数上使⽤限制也会成倍爆炸两种解决措施每个数据包的头中包含⼀个跳计数器，每经过⼀跳后该计数器减1，为0时则丢弃该数据包记录哪些数据包已经被扩散了，从⽽避免再次发送这些数据包。

⽅法：1.每个数据包头⼀个序号，每次发送新数据包时加12.每个路由器记录下它所看到的所有(源路由器，序号)对3.当⼀个数据包到达时，路由器检查这个数据包，若是重复的，就不再扩散了选择性扩散它是⼀种泛洪⽅法的⼀种改进，将进来的每个数据包仅发送到与正确⽅向接近的线路上扩散法应⽤情况扩散法的⾼度健壮性，可⽤于军事应⽤分布式数据库应⽤中，可⽤于同时更新所有的数据库可⽤于⽆线⽹络中扩散法作为衡量标准，⽤来⽐较其它的路由算法距离⽮量算法描述距离向量是⼀种分布式路由算法，最短路径计算跨节点分配，属于动态算法，被⽤于RIP协议。

4．子网划分中应当注意的问题 ➢ 划分了子网时，最好保留一个路由器地址。因为子网之
间的通信需要使用路由器。 ➢ 子网划分的目的并不是解决IP地址不够用的问题，因为
使用子网划分反而会使IP地址减少。子网划分主要解决 网络号不够用的问题。 ➢ 由以上计算可知，子网划分方法复杂，划分的子网号也 不便于记忆，不利于进行网络管理。况且，目前企业申 请到一个或数个网络号的情况也非常少。因此，对于大 多数企业和个人，内部局域网一般使用C类或B类私有地 址，这样进行网络管理更为简单可靠，而外部网络的互 连往往采用NAT（网络地址转换）技术。
3．子网的划分方法 在划分子网之前，应当先分析网络目前的需
求和将来的扩展，子网划分步骤如下： 第一步：确定网络中物理网段的数量，以及每个物
理网段上主机的数量。 第二步：计算需要的掩码二进制位数。 第三步：计算子网掩码值。 第四步：计算子网主机地址范围。
最新版整理ppt28页，共85页
4.2.3 有类子网划分技术
最新版整理ppt5页，共85页
4.1.3 最大数据传输单元长度
物理层一般要限制每次发送数据帧的最 大长度。任何时候IP层接收到一份要发送 的IP分组时，它要判断向本地哪个接口发 送数据（选路），并查询该接口，获得 MTU（最大数据传输单元）长度。
IP协议把MTU与IP分组长度进行比较， 如果IP分组太大，则需要进行分片。分片 可以发生在原始发送端的主机上，也可以 发生在中间路由器上。
最新版整理ppt23页，共85页
4.2.2 特殊IP地址
2．特殊IP地址
网络ID
网络号或主机 全0
号的比特位为全0 全1
或全1的地址有特 全0
殊的意义，它们不 全1
能分配给主机使用。 全0

如从5出发到4：
数据包从51,2；23,6；36,4；63,7；74
要解决的问题：数据包重复到达某一节点，如3，6
扩散法（续）

解决方法

在数据包头设一计数器，每经过一个节点 自动加1，达到规定值时，丢弃数据包 在每个节点上建立登记表，则数据包再次 经过时丢弃

缺点：重复数据包多，浪费带宽 优点：可靠性高，路径最短，常用于军事
si1：从节点i到节点1的一条最小时延路径上的下一个节点 si2：从节点i到节点2的一条最小时延路径上的下一个节点
其中：n —网络中的节点数 Di—节点i的时延向量 dij—节点i到j的最小时延的当前估计值 Si—节点i的后继节点向量 sij—从节点i到j的最小时延路径上的下一节点
路由表的更新
dij = min(dix + dxj)
静态或动态的? 静态: 路由变化较少的情况 动态: 路由变化较快的情况 定期更新 为了响应链路成本的 变化
介绍相关的路由算法

最短路径算法（Dijkstra） 扩散法(flooding) 距离矢量算法 链路状态算法
最短路由选择

Dijkstra算法（1959）：通过用边的权值作为 距离的度量来计算最短路径，有最少边数的路 径不一定是最短路径 如下图：5和4之间边数最少的路径是5234 但最短路径是523674

数据报和虚电路比较
数据报还是VC网络: why?
因特网

ATM



数据交换在计算机之间进行 “弹性”服务,没有严格的实 时性要求 “聪明”的端系统 (计算机) 可进行自适应,执行控制, 出 错恢复 网络内部比较简单, “边缘上” 比较复杂 利用了许多链路类型 各具有不同的特性 统一服务标准十分困难