1. 转发和路由⭐
网络层主要有两个功能:转发和路由
| forwarding 转发 | pkt到达router后,router为其选择合适的输出链路 |
|---|---|
| routing 路由 | pkt从发送方流向接收方,网络层决定pkt路径.计算路径的算法即路由选择算法 |
| 对比 | - forwarding: - 发生在路由器上 - 时间很短(纳秒),通常由硬件实现 - routing: - 发生位置不一定 - 时间长的多(几秒),通常由软件(算法)实现 |
| ⭐网络层服务 | 简单灵活的、无连接的、尽最大努力交付的数据报服务 |
| ⭐区分网络层&传输层 | - 网络层:在两台hosts之间的连接(VC网络中包括中间的routers) - 传输层:在两个process之间的连接 |
2. 分组交换网络
分组交换网络分为两种,对应Ch1中的电路交换&分组交换
| 数据报网络 datagram networks |
使用目的地地址转发pkt, |
|---|---|
| 虚拟连接网络 (VC) virtual connection networks |
使用VC号码转发pkt; 只有VC网络需要在IP数据报传输前建立virtual connection,即连接setup过程 |
2.1 VC网络
 |
|---|
- VC网络传输数据报前需要建立连接,使用VC**号码**转发pkt,不依赖destination - 使用在ATM, frame-relay, X.25,今天的Internet不再使用 - 路由器维持着连接状态(路由表) |
2.2 Datagram网络
 |
|---|
- 无需setup - 路由器没有保存e2e连接状态 - pkt转发依赖目标地址,非VC号,如下图,限定IP范围和输出链路的对应 |
|
对比
- 最长匹配
在DG交换中,一个IP地址为了避免重复匹配,选择”最长匹配”策略:选择可匹配目的地址中最长的一个
例题,已知路由表 和两个IP  |
|---|
| DA1:只能匹配0 DA2:可匹配1,2,选更长的1 *最长匹配的前提是匹配完整,不是说地址一和0,1,2前21位都一致,从里面选最长的,DA1甚至没有完整匹配 |
3. 路由器
3.1 构造&功能
|
构
造 | 整体 | | |
| :—-: | :—-: | —- | —- |
| | 
| | |
| | 输入 | | |
| | 
| |
- line termination:物理层
- link layer:链路层
- lookup:通过datagram的dest查询转发表,确定output
|
| | 交换结构 | | |
| | 
| 
| 
|
| | 由cpu控制,pkt复制到系统内存,速度被内存带宽限制 | 通过共享总线交换,但会被总线带宽限制 | 通过互联网络交换 |
| | 输出 | | |
| | 
| |
- 输出端有buffer:当流入速度快于流出速度,进行buffer,当溢出时会产生排队时延和丢包(路由器中未实现流控)
|
| | 联系“封装”过程 | | |
| | pkt进出router时链路层header与网络层header变化原因:
- 输入时:经过link层—>经过network层,进行lookup查询**转发表**,确定输出端口
- 输出时:经过network层,重设首部—>经过link层,重设首部
| | |
|
功
能 | 运行算法 | | |
| | 运行路由算法 | | |
| | 转发 | | |
| | 转发数据报到输出link | | |
4. IP—因特网协议
4.1 数据报—分片&重组
IP数据报结构
| 第二行 | id:标识相同数据报
一个数据报中的protocol overhead(协议开销):传输层TCP header+网络层IP header
转发后-1,为0时被丢弃,由于TTL每次变换,每次转发到新的router后checksum要重新计算
offset: 从小到大标识分片顺序
计算方法:当前分片前应抵达数据大小/8
(因此需剔除之前每片的ip hearder)
见👇例题
flag:默认为1,当为0,说明该片为所在数据报最后一片 | |
| :—-: | —- | —- |
| |
| |
| TTL | |
| 协议开销 | |
| 分片
&
重组 | 
| 分片:链路层frame的最大传输数据量(MTU)是协议相关,网络层的IP数据报大小被链路层MTU限制,sender可发出的原始数据报对于router可能无法一次发送,需要分片,因为分片发生在路径的router上 |
| | | 重组:重组无法发生在router,因为不同pkt无法保证路径相同,只能在dest上重组 |
| | | header⭐:为保证重组顺序,需要给每个分片pkt复制一遍原始数据报的header,加上传输层TCP的header,故每个分片pkt的开销:传输层TCP header+网络层IP header |
例题
|
1. 例题:图示分片后的pkt信息,已知TCP和IP的header都是20bytes:
1. receiver接收分片后网络层->传输层投递分片的顺序如何
- sender一共传输了多少字节(忽略链路层header)
3. sender上的应用层共传输了多少字节 | | | —- | —- | |
1. 根据id,一共有4个数据包,对于每个数据包根据offset判断先后,当flag==0,说明为末尾
(注意1000-1003不标识任何数据报投递的顺序,因此分片的投递不能写成DABJHEIGCF)
2. (500+500+…+150+200)-20×10+4×20=4090
分片后的header不属于sender原始数据,但4个数据报的header来自sender
3. 4090-8×20=3970
sender发出数据-4个IP header-4个 TCP header | | |
2. 例题:计算offset
| 分片1:
offset=0/8=0
分片2:
offset=(1500-20)/8=185
分片3:
offset=(3000-40)/8=370 |
4.2 IPV4
 |
IPV4记法 | 32bits,分四组,八位一组,化为十进制后可从0-255 |
|---|---|---|
| 子网 | 使用主机和路由器不同接口产生的隔离网络(左图6个子网) | |
| 子网掩码 (mask) |
如223.1.1.0/24其中/24为mask 32bits中最左侧24位定义了所在子网(现实中会表示为255.255.255.0说明左3*8为网络号) |
|
| 特殊IP | 0.0.0.0:本主机源地址 255.255.255.255:广播目的地址 - 特定子网广播地址:网络号不变,主机位全为1 |
- Classless Interdomain Routing—CIDR(**无类别域间路由选择**)
这是一种区别于过时的分类编址的方式,形式a,b,c,d/x,地址高x位是网络号,确定子网,低32-x区分子网内设备
4.3 DHCP
| 定义 | Dynamic Host Configuration Protocol—DHCP(动态主机配置协议): 当某组织获取一块地址后,通过DHCP可为组织内host自动分配IP地址,其把主机连进组织网络的能力让其也被称为”plug-and-plug”或者”zeroconf”协议 | |
|---|---|---|
| 过程 |  |
该过程的四次广播 - dicover:客户把数据报广播至所有与子网连接的节点 - offer:DHCP server(不一定一台),广播回复 - request:客户选取最优地址,继续广播,告知其余server该IP已被使用 - ACK:server确认 |
|
例题
例题:DHCP分配地址块,已知ISP有如下地址块 1. 分给8个组织网,host个数相等 1. 当要求分给三个组织网络,1st有120台host,2nd有250台host,3rd有120台host |
|---|
1. 8=2^3,为网络号延长3bits用来区分8个组织即可,则 |
2. 组织0,2:120<2^7,保证低7bits留给子网内设备;组织1:250<2^8,保证低8bits留给子网
|
4.4 NAT
| 定义 | Network Address Translation(网络地址转换): 如果给internet中每台设备一个唯一IP地址,那么IPV4资源无法满足,因此产生了NAT,一个NAT路由器有单一IP地址,假设为138.76.29.7,由其连接的组织网络中的设备都使用10.0.0.0/24编址(private network—专用网络),这些地址只对组织内其他设备有意义 |
|---|---|
| 区分 | 概念区分:NAT和子网划分🎭 - 子网划分是ISP把地址块分给不同的组织(子网),依旧使外网可识别的IP - NAT是转换网络地址使用,可以把公网IP转换为私网IP,私网IP无法被外网设备辨识 |
| 路由聚合 | 路由聚合—route |
aggregation: 使用单个网络前缀告知多个网络的能力
ISP告知外界所有前缀200.23.16.0/20的数据给它即可,而无需知道ISP内部信息 |
| 内->外 | 组织内设备给外网的pkt经过NAT路由器统一使用138.76.29.7 |
| 外->内 | 外界pkt通过NAT路由器,路由器查询NAT转换表,查找接收pkt的组内host |
| 示意 | WAN口:Wide Area Network连接外网; LAN口:local area network连接内网
|
| | 通过router后封装在frame中datagram的header改变⭐
- TTL: 每次-1
- checksum: 因为TTL变化
- 可能有IP: 当使用NAT技术时
- 出子网:改变src IP
- 入子网:改变dest IP
|
4.5 ICMP
| 定义 | ICMP（Internet Control Message Protocol）Internet控制报文协议。它是TCP/IP协议簇的一个子协议，用于在IP主机、路由器之间传递控制消息 |
|---|---|
| 应用 | - 错误报告—不可达的host,网络,端口,协议等 - echo request/response—ping的实现 - tracert/traceroute—host依次发生TTL为1/2/3…的pkt,路径router每次减一,为0丢弃,丢弃后发送ICMP消息回source,由此可以判断路径中router个数 |
(tracert重复上述过程三次)<br /> |
4.6 IPV6
| 
| Dual Stack
双协议栈技术就是指在一台设备上同时启用IPv4协议栈和IPv6协议栈
典型不同:
- flow:IPv6具有流,类似一项要求进行实时传输的服务,如音频视频(流媒体),但文件电邮传输不算流,因为非实时的
- 40字节header
- 地址长度从32bits->128bits
不再存在的IPv4属性:
- 分片, checksum, option
|
| —- | —- |
| 一个真实的IPv6地址 | |
| 
128bits,分为8组,每组16bits,用4个16进制数表示:
- ::是使用零压缩算法,表明该分组为0000
- %18是说明该地址仅针对标号为18的网络接口(网卡)
| |
| IPv4->IPv6:建隧道(Tunneling) | |
| 
|
1. B->C时把IPv6数据报封转为IPv4格式
1. CD完全无视其中的IPv6数据报
1. 到达E后,E识别出其中的IPv6数据报,提取后恢复IPv6转发
区分隧道和双栈:
CD类似一段隧道,过程中pkt在IPv4隧道中,与IPv6暂时切断联系,区分Tunneling和Dual
Stack,前者是转换,后者是通用 |
5. 路由选择算法⭐
一般根据算法是集中式/分散式划分
- 集中式(centralized):路由时已经知道全局信息(每个链路的状态)
- 分散式(decentrailzed):路由时路由器只知道相邻链路信息**,必须迭代,**分布式的计算出开销最小的路径
5.1 Link State 算法
LS算法是集中式算法,实际上为Dijkstra算法,给定图后求出单源最短路径,其核心为
例题: 见LS算法例题
复杂度:对于n个节点,复杂度在O(n)(可以优化到nlogn)
**5.2 Distance Vector算法
DV算法是分散式算法, 核心为Bellman-Ford方程:dx(y)=minc{c(x,v)+dv(y)}
特点⭐:**异步(Asynchronous ),迭代,自终结,分布式例题: 见DV算法例题
5.3 毒性逆转
链路开销改变时可能产生路由环路问题(开销变大时),需要使用毒性逆转来避免
6. Internet路由⭐
6.1 路由器自治系统
| 
|
- 如左图所示即为一个路由器组织自治系统**(Autonomous
System, AS),每个AS由一组相同管理下的路由器组成,不同ISP又可划分多个AS;
- 转发表通过intra-AS (自治系统内部路由选择协议)and inter-AS (自治系统路由选择协议)路由算法解决AS内以及AS间的路由选择问题;
- 网络中所有AS间的选择协议相同,为BGP(Broder
Gateway Protocol),边界网关协议
- 无论是否为网关路由器都会同时运行intra/inter**协议
|
| —- | —- |
6.2 AS内: RIP算法
RIP(routing information protocol)路由信息算法基于DV算法,但其中的链路开销变成到下一路由器的跳数hops
 |
一些特点: - 路由器每30s给邻居发送公告交换距离信息,当180s后没有回复,则认为其无效 - 公告通过UDP pkt发送 - 使用毒性反转防止路由环路 - 最大允许15跳,因此使用16跳标识∞ |
|---|---|
6.3 AS内: OSPF算法
OSPF(open shortest path first)最短路径优先算法,是一种LS算法,有以下特点:
- 公告会通过flooding发给整个AS - OSPF msg直接通过网络层IP携带,而非TCP或IP - 安全性:OSPF是授权的 - 当多条同样开销路径并存,不同于RIP的一般LS从相同开销中选一个,OSPF会一起保存 - 目前的大型网络基本都使用OSPF,因为其可以分级 |
 |
|---|---|
6.4 AS间:BGP
BGP(Broder Gateway Protocol),边界网关协议,为保证连接可靠性因此基于TCP
- 通过BGP路由信息
BGP实际上为某个AS中的路由想办法告知其余AS自己的存在,让他们自己斟酌怎么到这
- eBGP:外部BGP,连接横跨不同AS的BGP连接
iBGP:内部BGP,在一个AS内部中两台routers之间的BGP会话
最优路由确定 | BGP路由 | route=prefix+attribute | | —- | —- | | prefix | 目的地前缀,通常为子网或子网集合 | | attribute | attribute:当进入BGP的输入产生的路由不唯一,顺序调用以下规则直到剩下唯一一条
- local preference:本地偏好,由网管设置,直接选择最高偏好的AS
- shortest AS-PATH:AS-PATH包含了通告已经通知过的AS;如果偏好相同,选择最短AS-PATH的
- closest NEXT-HOP router:NEXT-HOP是AS-PATH起始路由器接口的IP;当偏好和AS-PATH都一样,从余下路由中进行热土豆选择,即最靠近NEXT-HOP的路由使pkt尽早离开当前AS
| | | 热土豆路由:路由器收到pkt后要尽快的把其送出自己的AS,即避免在自己AS中开销过大,但它不会关心在其余AS中的开销,总之是一个自私算法 |
例题: 见路由选择例题
- 小结**:关于不同协议运行基础⭐: | 用途 | 协议/算法 | 底层支持 | 类型 | | —- | —- | —- | —- | | AS内 | RIP | UDP | DV | | | OSPF | IP | LS | | AS间 | BGP | TCP | /** |
7. 广播和组播
了解内容
- 广播
广播(Broadcast):把pkt路由至所有节点,但此方法很低效,可能重复路由,需要优化
| 记录轨迹 | 直接在每个节点中做标记,只路由之前没有接收的pkt |
|---|---|
| reverse path forwarding | 在节点中存放S-D的最短路径,只有pkt通过最短路径来时才路由,否则多半是重复pkt |
| spanning tree | 构建扫描树后再路由 |
- 组播
组播(multicast)和广播的不同在于组播技术的初衷是在IP网络中，以”尽力而为”的形式发送信息到某个目标组**(subnet)**，这个目标组称为组播组,源主机发送一份数据,数据的目的地址是组播组地址,常见实现:
| shortest tree | 直接通过Dijkstra构建最短路径树后剪枝 |
|---|---|
| RPF | 同上 |
MindMap
若有收获，就点个赞吧
0 人点赞
