Goal
- understand principles behind network control plane
- traditional routing algorithms
- SDN controllers
- network management, configuration
- instantiation, implementation in the Internet
- OSPF, BGP
- OpenFlow, ODL and ONOS controllers
- Internet Control Message Protocol: ICMP
Terms
- LS – Link-State
- DV – Distance-Vector
- ICMP – Internet Control Message Protocol
- BGP – Border Gateway Protocol
- AS – autonomous systems 自治系统
Routing Algorithms
LS
Link-State routing algorithm
Dijkstra:
获得最低开销路径图
宏观规划
DV
每个节点将自己的距离向量表发给自己的邻居
收到后，使用B-F方程更新自己的距离向量表 → 计算比较加入中间节点前后的路径长度
- 异步迭代
- distributed – 各个节点只有在距离向量表发生改变时才告知其邻居节点
- Poisoned reverse 毒性逆转（count-to-infinity problem）：
- If Z routes through Y to get to X → Z tells Y Z’s distance to X is infinite
(so Y won’t route to X via Z) - 判断依据：不断增加
- 考单个结点的话 写每次更新后的表 一次往外扩一个邻居
Comparison
健壮性：一个路由器错误 LS错误更少 DV会错整个网络
收敛速度：LS更快 O($n^2$) 而DV可能遇到环路 甚至无穷计数
报文复杂性：LS更复杂 每个节点要知道网络中每条链路的开销
Hierarchical Routing
- Each AS within an ISP
- ISP may consist of one or more ASes
- routers in same AS run same routing protocol 同一自治系统内运行相同的路由协议
- “intra-AS” routing protocol 自治系统内路由协议
- Gateway router AS交界处的路由器
- inter vs. intra routing algorithm
- forwarding table configured by both intra-AS and inter-AS
OSPF
开放最短路优先
- use LS
- use service of IP
- each router has full topology, uses Dijkstra’s algorithm to compute forwarding table
- all OSPF messages authenticated → security
- intra 内部
- 可以允许多条相同开销的路径 可以分担流量
RIP
路由信息协议
- DV routing algorithm
- use service of UDP
- 默认的路由更新周期为30s
- RIP 规定最大跳数为15 大于15就不可达
- intra 内部网关协议
- no longer widely used
BGP
边界网关协议
- inter-AS routing protocol
- use service of TCP
- BGP用路径向量不是DV
- compete with IP protocol
- eBGP, iBGP
- 3c learns x from eBGP
- 3a learns x from iBGP(from 3c)
- 1c learns x from eBGP
- 1d learns x from iBGP
- iBGP 和 intra-routing(OSPF, RIP) 的区别
- iBGP用路径向量不是DV OSPF用LS
- iBGP是一种自治系统内部的路由协议，用于在同一自治系统内部的不同路由器之间进行路由交换；而OSPF是一种链路状态路由协议，用于在同一区域内的不同路由器之间进行路由交换，更省资源 不需要根据外部状态频繁更新
- iBGP找出去的路 OSPF找内部去每个路由器的路径
- 2 attributes
- AS-PATH: list of ASes through which prefix advertisement has passed 经过的AS
- NEXT-HOP: indicates specific internal-AS router to next-hop AS 下一个AS的对应入口网关
- 每条 BGP 路由包含 3 个组件： NEXT-HOP; ASPATH; 目的前缀prefix（AS2, AS3, X)
- hot potato routing
- find the least-cost intra-AS path to NEXT-HOP 先用出AS的最短路径（最低开销网关）
- 减小自已AS中的开销 不管整体开销
- 路由路径选择
- 路由被指派 一个本地偏好
- 相同本地偏好时 选取最短AS-PATH的路径
- 相同的AS- PATH时 选取最近的NEXT-HOP
ICMP
- ICMP解决的问题
- IPv4 has no error-reporting or error-correcting mechanism
- lacks a mechanism for host and management queries 无查询机制
- ICMP msgs carried in IP datagrams ⇒ network layer above IP (IP header+ICMP message)
- IP 路由器不能找到一条通往 HTTP 请求中所指定的主机的路径、该路由器就会向你的主机生成并发出一个ICMP报文以指示该错误 各种异常都会进行异常反馈
- When source gets ICMP “destination port unreachable”(type3, code3), stops
- router and host both can send ICMP
Structrue
- 使用type+code的组合反应出的差错
Traceroute应用
发送一系列 TTL=1, 2, 3….., n 的UDP segments 每个经过对应TTL数量的路由器后 TTL过期 就会收到一个路由器返回的 type=11, code=0 的ICMP报文 从而计算RTT
Notice
- 快速以太网数据帧有效载荷最小长度46字节
- 题中可能会说IP datagram长度多少 然后MTU多少 这里的IP datagram也是包含header的20byte的 或者说要看清是整体长度还是有效载荷
数据部分的长度必须能被8整除，780不能被 8 整除,所以要将780改成最大能被8整除的数即 776
要减去全0和全1 全1是广播 全0是子网的网络地址
Show Comments
