网络层：控制平面

一、路由选择算法

1.路由

路线的概念

• 路径:根据特定指标(传输延迟、经过的站点数等)从源节点到目标节点寻找更好的路径。

• 较好的路径:根据某些索引的小路径
• 指标:站数、延迟、成本、队列长等,或一些简单的指数加权平均
• 要指明网络用户要突出哪些方面以及应该给予哪些指标更大的重视,应使用哪些指标?

• 网络单元路由(路由信息通知+路由计算)

• 网络由单元路由,路由信息传输、计算和匹配的成本低
• 前提是网络中的所有节点地址前缀都是相同的,并且物理上是聚集的
• 路由器是如何计算网络到其他网络的问题

• 网络到网络路由器 = Router - Router-to-router

• 与其他网络相对应的路由器相对应的路由器
• 在网络中:路由器与主机之间的通信,连结层解决方案
• 给这个路由器是给这个网络

• 路由算法:完成路由功能的网络层软件的一部分

1.2网络的图形抽象

• 路由器输入:拓扑、侧成本、源节点
• 输出的输出:源节点的集合树
  

最优原则

• 水槽树

• 从这个节点到所有其他节点形成最佳路径的树
• 路由选择算法是为所有路由器找到和使用集合树
  

• 注意

为什么我们不使用图表,而不是树木,是因为图表是环形,在价格相同的情况下,在存在差异时更难作出选择

1.4路径选择算法的原理

• 正确性:算法必须正确和完整,以便通过分组连接到目标站;完成:所有目标站地址可以在路由表中找到;目标站地址不能处理;
• 简化:算法应在计算机上简化:优化,但复杂算法,时延较大,不实用,不应增加通信量,以获取路由信息;
• 鲁棒性:算法应能够适应通信量和网络拓扑的变化;通信量和网络拓扑的变化可以迅速适应;数据不应传输到非常拥挤的链路,数据不应传输到中断的链路;注意,一些课本也翻译成“坚固”
• 稳定性:结果路径不应波动
• 公平:对每一个观点的公平
• 优化:一个指数的最优,时间、成本等,或者一个综合指数;事实上,获得最优的结果是昂贵的,而且可以是次优的

1.5路由器算法分类

全球或本地路由信息?

• 全局

• 所有路由器都有完整的拓扑和侧成本信息
• “link state”算法

• 分布式

• 路由器只知道与其有物理连接的邻域路由器,以及相应的邻域路由器的替代值
• 与邻居交换路由信息,计算路由信息
• “distance vector”算法

静态或者动态的?

• 静态:

路由随时间变化缓慢

• 动态:

路径随链路价格的变化而变化迅速、周期性,例如LS和DV都是动态的

2.链接状态

2.0Dijestra算法

• 概述

Diekstra算法是一种典型的最短路径算法,用于计算从一个节点到另一个节点最短路径。

2.1LS路由工作流程

• 点通过各种渠道获取整个网络拓扑,信息如网络中所有链路的成本(该部分与算法无关,属于协议和实现)

也就是说,每个点都从除自己的点到邻近点的所有点中获取路径信息

• 使用LS路由算法,从车站到其他车站的最优路径(收集树)计算并得到路由表
• 根据此路由表分配子集(数据图模式)

• 严格说来,这不是朝着正确的方向迈出的一步
• 分配到输入端口的网络层

2.2连结状态路由

2.2.1LS路由的基本工作过程

1. 找到邻接的节点,获取对方的网络地址
2. 测量邻接节点的成本(延误、费用)
3. 将LS子集的成本描述到邻近的节点上
4. 通过扩散方法将一个子集分配给所有其他路由器,每个路由器的拓扑和侧面成本需要超过四个步骤
5. 通过Dijkstra算法找到最短路径(这是路由算法)

1. 每个节点独立计算到其他节点的最短路径(router=network)
2. 迭代算法:步骤k能够知道从这个节点到其他节点的最短路径

2.2.2 找到邻接的节点,获取对方的网络地址

• 在路由器启动后,将HELLO子集发送到所有线
• 其他路由器接收HELLO分组,返回响应,在响应分组中告诉它们的名字(仅全球)
• 在网络中,从其他路由器获取的信息可以被认为通过将HELLO子集发送到一个人工节点来引入

2.2.3 测量邻接节点的成本(延误、费用)

• 发送一个小组要求对方立即作出反应
• 回返救济工程处单位
• 通过测量时间来估计延迟

2.2.描述邻近节点的状况的子集

• 发送者名称
• 序号，年龄
• 列表:给它一个邻接节点,并将其延迟给邻接节点

2.2.通过扩散将分组分配给所有其他路由器

• 序列数:用于控制无限扩散,每个路由器被记录(源路由器、序列数)并发现重复或旧路由器没有扩散

• 具体问题1:循环使用
• 具体问题2:路由器故障后序列从0开始
• 具体问题3:序列错误

• 如何解决这个问题:年龄

• 当生成子集时,年龄场不是0
• 每个时间段,AGE字段减少到1
• 0的AGE字段的子集将被丢弃

• 分布单元数据结构

• 来源:哪个节点接收LS子集
• Seq, Age:序列号码,年龄
• 发送旗帜: 发送必须向指定的邻近站点发送LS分组的标签
• ACK旗帜:哪些车站必须向邻近车站发送
• 数据:源站LS子集[20]B节点数据结构

2.2.通过狄克斯特拉算法找到最短路径(路程算法)

• 路由器获取每个站点和整个网络的LS分组拓扑
• 通过Dickstra算法计算到其他路由器(收集树)的最短路径
• 在路由表中安装计算结果

2.2.7签名标记

2.2.8LS路径选择算法的工作原理

• 节点标记:每个节点使用(D(v),p(v))标记,例如:(3,B)

• D(v)通过已知的最优路径从源节点到节点的距离
• P(v)预定节点标记

• 2类节点

• 临时节点:从源节点到此节点没有最佳路径的节点
• 永久节点:从源节点到此节点找到最佳路径的节点

• 初始化

• 除源节点外,所有节点都是临时节点
• 除与源节点成本相邻的节点外,节点成本为∞

• 从所有临时节点中找到最低成本的临时节点并将其转换为永久节点(当前节点)W
• 该节点的所有邻接节点(V)在临时节点集合中

• 如 D(v)>D(w) + c(w,v), 则重新标注此点, (D(W)+C(W,V), W)
• 否则，不重新标注

• 开始一个新的循环

2.2.9Dickstra算法的例子

• 可能的冲击:链路的成本=链路所承载的流量,计算的路径每次不同
  

3.距离向量路由

3.0动态编程算法

• 概述

动态编程方程(策略)将每个选择纳入最终结果,可以由您自己详细检查

3.1 基本思路

• 每个路由器 maintain a routing table with a structure such as a graph (other cost) that maintains all nodes
  

• 路由器和邻近路由器之间的路由器表交换(续)

• 根据收到的路由信息更新路由表(重复)

3.1.1 例子一

从图中可以看出,核心思想是迭代

3.1.2更新价格和路由信息

• 邻近节点之间价格及价格的实现

• hops 、 delay 、 queue length
• 邻接节点之间的成本实现:通过物理测量

• 路由信息的更新

• 根据测量结果,将A节点送到邻近地点的成本(例如延误)
• 根据每个邻近车站向目标车站B提出的费用
• 计算从A站到目标站B通过每个邻近站的交通费
• 找出一个最小成本,然后将相应的下一个Z节点,通过这个Z节点到达B节点,成本是A-Z-B

3.1.3 例子二

1. 以当前节点J为例,相邻节点A,I,H,K
2. J测得到A,I,H,K的延迟为8ms,10ms,12ms,6ms
3. 通过交换DV，从A,I,H,K把它们送到G的延迟是18ms,31ms,6ms,31ms因此从J经过A,I,H,K到G的延迟
   为26ms,41ms,18ms, 37ms
4. 将到G的路由表项更新为18ms,下一跳为:H
5. 与其他目标一样,除了这个节点J

3.2距离向量算法

• 核心思想

• 每个节点向其邻居发送自己的距离向量估计,让另一节点在时间或DV变化时计算
• 当x从它的邻居接收DV时,它通过B-F方程计算并更新自己的距离向量:
  Dx(y) ← minv{c(x,v) + Dv(y)} 每个节点y N
x到y的成本 x到邻居v的成本v要求y的成本
• Dx(y)估计最终收敛到实际最低生成值dx(y),一个分布式迭代算法
  

3.2.1 例子

3.3距离向量路由

3.3.1DV的无限计算问题

• DV的特点

好消息迅速传播,坏消息缓慢传播

• 好消息传的快

同样,通过每次迭代,链路可以同时更新到整个网络,并及时更新

• 坏消息传的慢

当从起点到终点的链条在某个时刻断裂时,由于重复问题,我们需要从头到尾更新信息,说链子坏了,但此时从后节点到起点的成本是一个价值状态,当迭代更新到启动点的第二个节点时,发现已完成更新的数目被中断,第三点是告诉他的兄弟,我不会打扰到头点的道路,而你却以我开支续约,事实上,目前由于点根背后的迭代问题,根本不知道前线被中断了,导致了信息错误。

3.3.2分割水平算法解决了DV的无限计算问题

• 概述

类似于悲观锁的使用,当前面是不可访问的信息,而背后信息未知的节点也认为前面是不可访问的,后面是不可访问的,然后向每个节点循环

LS和DV算法的比较

在互联网的自主系统中内部路径选择

1.RIP ( 路由信息协议 )

1.1 概述

• 1982年发布BSD-UNIX的实现
• 距離向量算法

• 距离向量:成本=1, hops的数量(最大=15 hops)
• DV每30秒与邻居交换,通知
• 每个通知包括:最大25个目标子网
• 由UDP协议发送的消息

1.2RIP广告

• DV:每30秒交换邻居之间的通知消息

• 在更改路线时定期发送通知消息
• 另一方请求,可发出通知书

• 每个通知:DV内最大25个目标网络

• 目标网络+跳跃率,每公告最大25个分网,最大16个跳跃率

1.3 例子

A向D发送他的矢量表,D知道通过A需要1,通过Z需要4,通过Z需要5,然后D更新他的矢量表

1.RIP:链故障及恢复

如果180秒没有收到通告信息----->邻居或者链路失效

• 人们发现穿过邻居的道路是无效的
• 将向邻国发出新的通知
• 因此,邻国发出新的通知(如路线更改)
• 整个网络的传输
• 使用毒性逆转来停止乒乓球圈(无法进入的距离:无穷跳跃=16段)

1.5RIP处理

• RIP通过应用过程实现: route-d (daemon)
• 通过UDP消息发送的循环消息,定期重复
• 网络层协议使用传输层服务以实现层实体的方式应用
  

2.首先打开最短的路径

2.1 概述

• “open”：标准可公开获得
• 使用LS算法

• LS子群在网络中分布(在AS内)
• 全球网络拓扑,成本,在每个节点都保持不变
• 使用迪克斯特拉算法的路由器计算

• 载入OSPF通知信息:每个邻近路由器的表格项目
• 通知将通过整个国家(通过洪水)

直接在IP数据消息上发送OSPF消息(不通过UDP和TCP,与RIP不同)

• IS-IS路由协议:几乎类似OSPF

2.2OSPF“高级”功能

• 安全:所有OSPF报告都经过认证(反恶意攻击)
• 允许有相同的成本的多个路径存在(RIP协议中只有一个)
• 对于每个链,不同的TOS的多成本矩阵

• 卫星链的成本比提供服务的成本低,而提供实时服务的成本高
• 支持根据不同成本计算最佳路径,例如根据时间和延迟计算最佳路径

• 单播和多播的综合支持:

• 多播OSPF(MOSPF)使用同OSPF一样的拓扑数据库

• 在大型网络中支持层次性OSPF

2.3层次化OSPF路径

• 层次结构的2级:局部,骨髓

• 链路国家通知只发生在本地区域内
• 每个节点都有本地区域的拓扑信息;对于其他区域来说,通过区域边界路由器(最短路径)知道去那里的方向

• 区域边界路由器将自身区域内的网络距离聚集起来,并通知其他区域边界路由器。
• 骨路由器:只在骨区运行OSPF路由器
• 边界路由器: 连接其他 AS 。
  

ISP间的路径选择:BGP

1.层次路由

1.1平面路由器概览

• 网络中的所有路由器的位置是相同的
• 通过LS、DV或其他路由算法,所有的路由器知道其他路由器(子网络)如何工作
• 在飞机上的所有路由器

1.2飞机路线问题

• 在大规模网络中,存储、传输和计算路由信息的成本是巨大的

• DV:距离向量大,不能收敛
• LS:LS子集中的数百万节点最短路径算法的传输、存储和计算

• 管理问题:

• 不同的网络所有者想以自己的方式管理网络
• 想从外部隐藏您的网络的细节
• 当然,您还想与其他网络连接

1.3 层次路由

1.3.1层次路由:将互联网分成AS(路由器区域)

• 自动系统,区域内路由器的集合“autonomous systems” (AS)
• AS 只 标记 AS 号 ( ASN ) 。
• 一个 ISP可以包括一个或多个AS

1.3.两条路径成为:两层路径

• AS内部路由:在相同的AS内部路由器上运行相同的路由协议

• “intra-AS” routing protocol：内部网关协议
• 不同的AS可以运行不同的内部门户协议
• 能解决规模和管理问题
• 例如:RIP、OSPF、IGRP
• 网络交换路由器:可以与其他AS端路由器连接的AS端路由器

• AS互操作的AS调度协议

• “inter-AS” routing protocol：外部网关协议
• 解决AS之间的路由问题,并完成AS之间的互连

1.4层次路由的优点

1.4.解决规模问题

• 内部 Gateway 协议解决方案: AS 内部有限的路由器互相到达, AS 内部尺寸控制

• 如果存在太多的AS节点,则可以将AS分开,使得AS内部节点的数量有限

• AS之间路由的大小

• 添加一个AS,对于AS之间的路径,一般只是添加一个节点=子网(每个AS可以由一个点表示)
• 对于其它的AS,只增加了一个表,这就是新的AS如何运作的
• 扩张的力量:规模增加,性能不下降太多

1.4.解决管理问题

• 每个AS可以运行不同的内部门户协议
• 你可以保持你的网络秘密的细节

2.Internet AS互连:BGP

• 说明

以前,我们使用层次结构路由来解决节点数量过多问题,导致效率下降,因此层次结构路由被分成多个AS,这些大的AS应该使用哪些协议来通信,然后BGP出现

• TCP协议消息传输

2.0 BGP报文

2.1 概述

• BGP (Border Gateway Protocol):《区域间路线图协定》的“事实上”标准

“把互联网连接到每个AS的胶带”

• BGP 向 每个 AS 提供 的 方式 如下 :

• e(外部)BGP:从邻近的ASes获取子网可访问的信息
• i(内部)BGP:获取的子网地址信息被传递到AS内的所有路由器
  
• 根据所提供的资料和策略,决定“好”路径到达子网

• 允许子网通知其他互联网网络“我在这里”
• 距离向量算法(路径向量)

不仅距离向量,而且每个目标网络的详细路径(AS序列列表)可以避免一个简单的DV算法路由环的问题

2.2 BGP基础

• BGP对话:两个半永久的BGP路由器("双人")TCP连接交换BGP消息:

向不同的目标子网前缀发送通知的路径(BGP是一个路径向量协议)

• 例子
  

2.3 路径的属性& BGP 路由

2.3.1当通知是子网前缀时,通知包括BGP属性

• prefix + attributes = “route”

2.3.两个重要特征

• AS-PATH通过前缀通知的AS列表:AS 67 AS 17

• 检测循环;多路径选择
• 当转移到其他AS时,您需要在路径中添加自己的AS号

• NEXT-HOP在NetX - HOP属性中,有多个链从当前的AS到下一个跳 AS,告诉另一个人通过那个I.
• 其他属性:路由选项,如何插入属性

2.3.3基于战略的路线:

• 当开关路由器收到路由通知时,使用输入策略来接受或划线。

• Filtering Cause 例1:不要通过一个AS,将一些前缀转移到一个子集
• Filtering Cause 例2: prefix上已经有一个优先路径

• 该战略还决定它收到的路线信息是否通知其其他邻国

2.3.4 例子

2.4BGP路径选择

• 路由器可以获取多个网络前缀路径,路由器必须选择路径。路径选择可以基于:

1. 本地优惠值属性:优惠政策决策
2. 最短的AS-PATH:AS跳数
3. 最新HOP路由器:热豆路由器
4. 附加评判:使用BGP指示

• 一个前缀与多个路径相符,并使用消除规则,直到一条路径离开

2.4.1热土豆战略

• 2d是由iBGP所知道的,它可以通过2a或2c到达X

选择具有最低内部区域成本的开关作为X出口(例如2d选择2a,即使可能有更多的AS跳到X):不要担心区域间成本!

3.为什么内部的门户协议与外部的门户协议如此不同?

3.1 策略

• 内部(内部)管理员需要控制通信路径,使用其网络传输数据;
• 内部(外部)管理员,所以没有必要制定战略;

AS内每个子网的主机尽可能多地使用资源进行快速路由

3.2 规模

• AS中间路由器必须考虑规模问题,以支持网络数据传输
• 因为内部路由大小并不是一个大问题

• 如果AS太大,可以分成更小的AS;尺寸可以控制
• 还有一点在AS之间
• 或者AS内部路由支持层次性路由,层次性路由节省表空间,减少更新的数据流量

3.3 性能

• 内部行政机构:注重绩效
• 机构间:战略可能比业绩更重要

五、SDN控制平面

• 前言

在第四章中,我们从网络层的数据平面上讨论了SDN,这是前章内容的补充

1.传统方式的实现

• 互联网网络层: 从历史上看,它通过分布式、每个路由器实现

• 单一路由器包含: 交换设备的硬件 、 私有路由器 OS ( 如 Cisco IOS ) 和 运行在它上的互联网标准协议 ( IP 、 RIP 、 IS-IS 、 OSPF 、 BGP ) 的私有实现
• 需要不同的中间框来实现不同的网络层功能:防火墙、负荷平衡设备和NAT..

• 五年后,互联网开始重新思考结构性缺陷并寻找替代品

1.1传统方法:每路由器控制飞机

2.SDN模式:逻辑集中控制平面

2.1OpenDaylight(ODL)控制器

• ODL Lithium控制器
• 网络应用程序可以在SDN控制中或外部
• 服务抽象层 SAL:与内部和外部应用程序和服务交互

• 控制应用程序与控制器分离(应用控制器以外的应用程序)
• 意图框架：服务的
• 高标准:描述什么而不是如何
• 大量重点放在分布式核心上,以提高服务可靠性和性能可扩展性
  

2.2SDN:我们面临的挑战

• 加强控制计划:可靠、可靠、可扩展和安全的分布式系统

• 不效率的鲁棒性:控制可靠分布式系统的有力理论
• 可靠、安全:从一开始就铸造

• 网络和协议满足特殊任务的需求

例如实时,高可靠性,高安全性

• 互联网内可扩展性

不只是内部部署,而是网络部署

ICMP:互联网控制报告协议(Ping)和跟踪路径

• Traceroute程序让我们看到路由IP数据消息从一个主机传递到另一个主机。Traceroute程序还允许我们使用IP源路由选项。Traceroute程序使用ICMP错误消息类型,在Windows中,类似的命令叫做tracert。
  

为什么在运行Ping时不能捕捉ICMP消息?如果运行Ping时,主机的IP地址能接收消息吗?：

因为它代表了家庭机器的返回循环地址,通常,此地址在您的机器上 ping,以检查是否正确安装TCP/IP协议。whether ping or local IP (在Windows和Linux下),无法进入 ping数据框架,也就是说,双方的 pings不会通过网络卡,所有这些都是通过循环处理的。 ping 和 ping 机器的进程是不同的。ip输出函数首先检查地址是否是一个回声地址:

1. 如果返回地址是返回地址,则直接传递到处理的返回驱动程序,返回IP输入函数。
2. 如果不是, 检查它是广播地址还是多播地址.
3. 如果不是广播或多播地址,请检查是否是一个主机地址。如果它是主机地址,则由循环驱动程序处理,循环驱动程序返回IP输入函数。
   如上所示,不通过网络卡的 ping 包是一个需要通过网络卡的 ping 机,因此当运行时,不能捕捉ICMP消息;运行机的IP地址可以接收消息。

本文由 在线网速测试 整理编辑，转载请注明出处，原文链接：https://www.wangsu123.cn/news/28284.html。