1 AS内部路由

• Internet采用层次路由
• AS内部路由协议也称为内部网络协议IGP
  (interior gateway protocols)
• 最常见的AS内部路由协议:
  
  • 路由信息协议： RIP(Routing Information Protocol)
  • 开放最短路径优先： OSPF(Open Shortest Path First)
  • 内部网关路由协议： IGRP(Interior Gateway RoutingProtocol)，Cisco私有协议

2 RIP协议简介

2.1 RIP

• 早于1982年随BSD-UNIX操作系统发布
• 距离向量路由算法
  
  • 距离度量：跳步数 (max = 15 hops), 每条链路1个跳步
  • 每隔30秒，邻居之间交换一次DV，成为通告(advertisement)
  • 每次通告：最多25个目的子网(IP地址形式)

2.2 RIP: 链路失效、恢复

如果180秒没有收到通告→邻居/链路失效。

• 经过该邻居的路由不可用
  
  • 重新计算路由
• 向邻居发送新的通告
• 邻居再依次向外发送通告（如果转发表改变）
• 链路失效信息能否快速传播到全网？
  
  • 可能发生无穷计数问题
• 毒性逆转技术用于预防乒乓(ping-pong)环路(另外：无穷大距离 = 16 hops)

2.3 RIP路由表的处理

• RIP路由表是利用一个称作route-d (daemon)的应用层进程进行管理
  
  • 应用进程实现
• 通告报文周期性地通过UDP数据报发送

3 OSPF协议简介

3.1 OSPF (Open Shortest Path First)

• “开放” : 公众可用
• 采用链路状态路由算法
  
  • LS分组扩散（通告）
  • 每个路由器构造完整的网络(AS)拓扑图
  • 利用Dijkstra算法计算路由
• OSPF通告中每个入口对应一个邻居
• OSPF通告在整个AS范围泛洪
  
  • OSPF报文直接封装到IP数据报中
• 与OSPF极其相似的一个路由协议:IS-IS路由协议

3.2 OSPF优点(RIP不具备)

• 安全(security): 所有OSPF报文可以被认证(预防恶意入侵)
• 允许使用多条相同费用的路径 (RIP只能选一条)
• 对于每条链路，可以针对不同的TOS设置多个不同的费用度量 (e.g., 卫星链路可以针对“尽力”(best effort) ToS设置“低”费用；针对实时ToS设置“高”费用)
• 集成单播路由与多播路由:
  
  • 多播OSPF协议(MOSPF) 与OSPF利用相同的网络拓扑数据
• OSPF支持对大规模AS分层(hierarchical)

3.3 分层的OSPF

4 Internet AS间路由协议: BGP

• 边界网关协议BGP (Border Gateway Protocol): 事实上的标准域间路由协议
  
  • 将Internet “粘合”为一个整体的关键
• BGP为每个AS提供了一种手段:
  
  • eBGP: 从邻居AS获取子网可达性信息.
  • iBGP: 向所有AS内部路由器传播子网可达性信息.
  • 基于可达性信息与策略，确定到达其他网络的 “好”路径.
• 容许子网向Internet其余部分通告它的存在：
  “我在这儿！ ”

BGP基础

• BGP会话(session): 两个BGP路由器 (“Peers” )交换BGP报文:
  
  • 通告去往不同目的前缀（prefix）的路径 (“路径向量(path vector)” 协议)
  • 报文交换基于半永久的TCP连接

• BGP报文:

  • OPEN: 与peer建立TCP连接，并认证发送方
  • UPDATE: 通告新路径 (或撤销原路径)
  • KEEPALIVE: 在无UPDATE时，保活连接；也用于对OPEN请求的确认
  • NOTIFICATION: 报告先前报文的差错；也被用于关闭
    连接

• 当AS3通告一个前缀给AS1时:

  • AS3承诺可以将数据报转发给该子网
  • AS3在通告中会聚合网络前缀

BGP基础: 分发路径信息

• 在3a与1c之间, AS3利用eBGP会话向AS1发送前缀可达性信息.
  
  • 1c则可以利用iBGP向AS1内的所有路由器分发新的前缀可达性信息
  • 1b可以（也可能不）进一步通过1b-到-2a的eBGP会话，向AS2通告新的可达性信息
• 当路由器获得新的前缀可达性时，即在其转发表中增
  加关于该前缀的入口（路由项） .

路径属性与BGP路由（route）

• 通告的前缀信息包括BGP属性
  
  • 前缀+属性= “路由”
• 两个重要属性:
  
  • AS-PATH(AS路径): 包含前缀通告所经过的AS序列: e.g., AS 67,AS 17
  • NEXT-HOP(下一跳): 开始一个AS-PATH的路由器接口，指向下一
    跳AS.
  • 可能从当前AS到下一跳AS存在多条链路

BGP路由选择

• 网关路由器收到路由通告后，利用其输入策略(import policy)决策接受/拒绝该路由

  • e.g., 从不将流量路由到AS x
  • 基于策略(policy-based) 路由

  • 路由器可能获知到达某目的AS的多条路由，基于以下准则选择：

    1. 本地偏好(preference)值属性: 策略决策(policy decision)
    2. 最短AS-PATH
    3. 最近NEXT-HOP路由器: 热土豆路由(hot potato routing)
    4. 附加准则

BGP路由选择策略

• A,B,C是提供商网络/AS(provider network/AS)
• X,W,Y是客户网络(customer network/AS)
• W,Y是桩网络(stub network/AS): 只与一个其他AS相连

• X是双宿网络(dual-homed network/AS): 连接两个其他AS

  • X不期望经过他路由B到C的流量
  • … 因此， X不会向B通告任何一条到达C的路由

• A向B通告一条路径： AW

• B向X通告路径： BAW
• B是否应该向C通告路径BAW呢?
  
  • 绝不! B路由CBAW的流量没有任何“收益”，因为W和C均不是B的客户。
  • B期望强制C通过A向W路由流量
  • B期望只路由去往/来自其客户的流量！

为什么采用不同的AS内与AS间路由协议?

• 策略(policy):
  
  • inter-AS: 期望能够管理控制流量如何被路由，谁路由经过其网络等.
  • intra-AS: 单一管理，无需策略决策
• 规模(scale):
  
  • 层次路由节省路由表大小，减少路由更新流量
  • 适应大规模互联网
• 性能(performance):
  
  • intra-AS: 侧重性能
  • inter-AS: 策略主导