Dr Sandra I. Woolley Translated by D.Shang

Presentation on theme: "Dr Sandra I. Woolley Translated by D.Shang"— Presentation transcript:

1 Dr Sandra I. Woolley Translated by D.Shang
计算机网络 封包交换网络 Dr Sandra I. Woolley Translated by D.Shang

2 目录 封包交换网络和网络层。 封包交换网络的结构。 封包网络中的路由。 最短路径路由。 距离矢量 (Bellman-Ford)
链路状态Link-State (Dijkstra) Packet switching and the network layer Structure of a packet switch Routing in packet networks Shortest path routing Distance Vector (Bellman-Ford) Link-State (Dijkstra)

3 封包交换 信息作为数据包中的负载传输。 封包可能经历随机的延时或直接被丢失。 不同的用途需要传输不同的信息。 我们怎样传输封包？ t1 t0
Network

4 网络层 网络层是最复杂的一层。 寻址需要涉及极大量的网络，而且需要合适的路由算法。 寻址和路由是网络层中两个需要考虑的问题。
寻址：信息应该被传输到哪？ 路由：信息应该通过哪条路径传输。 The network layer is the most complex layer. Addressing needs to accommodate extremely large-scale networks and must work together with appropriate routing algorithms. These two challenges, addressing and routing, are the essence of the network layer. Addressing: where should information be directed to? Routing: what path should be used to get information there?

5 网络服务 网络层为传输层提供服务。 网络服务可以是连接导向传输或者非连接。保证高效和低延迟。 信息 Segments 端系统β 端系统α
物理层 数据连接层 端系统α 网络层 传输层 信息 Segments 网络服务 物理层 数据连接层 网络层 网络层 网络层 数据连接层 数据连接层 物理层 物理层 网络层为传输层提供服务。 网络服务可以是连接导向传输或者非连接。保证高效和低延迟。

6 网络的核心和边缘复杂度 网络中最复杂的部分是网络的边缘。 在终端的高层原件用来检测网络并采取纠正行动。
保持网络核心的简洁，并在网络边缘增加必要的复杂度，可以增强网络的扩展性。 Complexity is best at the edge of the network. Higher-level components at the ends are better positioned to check functionality and take corrective action. Keeping the core of the network simple and adding the necessary complexity at the edges enhances scalability.

7 网络层的作用 必要的： 路由：检测传输数据包的最佳通路机制。需要网络中各个设备协作完成。 转发：从网络元件的输入端传送封包到输出端。
优先级和调度：检测各个网络元件中封包传输的顺序。 额外的： 拥塞控制，分割和重组，安全。 Essential Routing: mechanisms for determining the set of best paths for routing packets requires the collaboration of network elements. Forwarding: transfer of packets from NE (network element) inputs to outputs. Priority & Scheduling: determining order of packet transmission in each NE. Optional Congestion control, segmentation & reassembly, security.

8 路由的主要功能 数据包如何传输？ 互联网的分散性是路由的主要困难。 内部网关协议（IGPs）用来检测同一网域中的路由。
路由必须连续且稳定。 应对网络的增长，扩展性是必要的。 IP地址的分级结构对于控制路由表的规模是很必要的。 How to get packet from here to there? Decentralized nature of Internet makes routing a major challenge. Interior gateway protocols (IGPs) are used to determine routes within a domain. Exterior gateway protocols (EGPs) are used to determine routes across domains. Routes must be consistent & produce stable flows. Scalability required to accommodate growth. Hierarchical structure of IP addresses essential to keeping size of routing tables manageable.

9 交换功能 输入和输出的动态互联。 实现了传输资源的动态共享。 两种基本方法: 非连接 面向连接传输 Backbone Network
Access Network Switch Dynamic interconnection of inputs to outputs. Enables dynamic sharing of transmission resource. Two fundamental approaches: Connectionless Connection-Oriented: Call setup control, Connection

10 封包交换网络 连接导向的网络需要在传输数据之前设立一个网络间的链接。 非连接的网络不需要建立链接。在到达目的地之前，封包被独立的导向。
两种方法都需要数据包交换机来管理封包。 数据包交换机储存并传送数据包。 数据包交换机 网络 传输线 用户 A connection-oriented network involves setting up a connection across the network before information can be transferred. A connectionless network does not involve setting up connections. Packets are routed independently until they reach their destination. Both approaches need packet switches to direct packets. Packet switches store and forward packets.

11 非连接/数据报 封包 数据源和目的地的地址存在封包的报头中。 非连接（数据报）的封包是被分别导向的。 封包到达时可能出现错误。
Packet 2 Packet 1 Source and destination addresses in packet headers. Connectionless (datagram) packets are routed independently. Packets may arrive out of order

12 路由表和数据报网络 路由导向是根据表中的记录。 路由包含找到下一个通向目标的结点。 路由表中含有每个目的地并指明了到达下一结点的输出端口。
当含有大量目标时，表就会变得十分冗长。 目标地址 输出端口 1345 12 2458 7 0785 6 1566 Route is determined by table lookup. Routing decision involves finding next hop in route to given destination. Routing table has an entry for each destination specifying the output port that leads to the next hop. Table size becomes problematic for very large numbers of destinations.

13 举例：互联网路由 互联网协议在网络间使用数据报封包交换。 互联网作为数据链路。 主机拥有双端ip地址： 网络地址+主机地址
路由器来王城网络地址的查找工作 这减少了路由表的大小。 另外，网络地址是被分配的，也可以被聚合 这在TCP/IP的课程中称为CIDR。 Internet protocol uses datagram packet switching across networks Networks are treated as data links Hosts have two-part IP address: Network address + Host address Routers do table lookup on network address This reduces size of routing table In addition, network addresses are assigned so that they can also be aggregated Discussed as CIDR in TCP/IP lectures

14 虚电路分组交换 虚电路分组交会在传输源和目的地之间建立固定的通路。路径的建立优先于封包的传输。 路由表将被配置到路径中的每一个交换机中。
同一个连接的所有封包都延同一条通路传输。最终封包按顺序先后到达。 一个简短的标头指出了每条链路对应的链接。 封包按队列传输。 比特率可以变化。在通信建立时可以进行协商。 Virtual-circuit packet switching involves establishing a fixed path between source and destination. This is established prior to packet flow. Routing tables are configured in every switch along the path. All packets for a connection follow the same path. Packets arrive in sequence. An abbreviated header identifies connection on each link. Packets queue for transmission. Variable bit rates possible, negotiated during call set-up.

15 虚电路传输表 每一个封包交换的端口都拥有一个传输表。 查询传入数据包的VCI(虚电路标识)。
定义输出端口（下一个结点）之后插入下一个连接的虚电路标识。 可以提供很高的传输速度。 表中也包含优先级或者处理封包需要的其他信息。 输入 VCI 输出端口 输出 15 58 13 7 27 12 44 23 16 34 Each input port of packet switch has a forwarding table. Lookup entry for VCI (virtual circuit identifier) of incoming packet. Determine output port (next hop) and insert VCI for next link. Very high speeds are possible. Table can also include priority or other information about how the packet should be treated.

16 封包交换的结构

17 封包交换：传输的数据在此聚合 1 1 2 2 输入包含从多路器和其他封包交换结构访问的多路流。 数据流在输入端分离并被传输到正确的输出端。
封包被缓冲，划分先后顺序，汇聚到输出线上。 • • • • • • 1 1 2 2   N N

18 Generic Packet Switch … 交换机的内部结构 接收线卡 控制器 互联网络 传输线卡
标头处理。 解复 大型交换机中路由 控制器 小型交换机中路由 信号和资源分配（连接导向传输模式）。 内部配置和维护。 互联网络 在线卡间传送封包。 传输线卡 Scheduling & priority 复用 *每个线卡都有输入和输出 控制器 1 2 3 N 线卡 互联网络 输入端 输出端 数据 控制 (a) … “Unfolded*” View of Switch Ingress (receive) Line Cards Header processing Demultiplexing Routing in large switches Controller Routing in small switches Signalling and resource allocation (in connection-oriented mode) Internal configuration and maintenance Interconnection Fabric Transfer packets between line cards Egress (transmit) Line Cards Scheduling & priority Multiplexing *Each line card contains both inputs and outputs.

19 纵横制交换 … … … … 纵横制相对串行传输可以提供更高的传输速度。克服了串行传输的速度瓶颈。
大型的交换机都是由纵横交换机和多级空间交换机组成的。 可以在输入，输出或两端同时设立缓存。（注意性能和复杂度的变化） (a) 输入缓存 (b) 输出缓存 输入 输入 1 3 1 2 8 3 2 3 3 … … N N … … 1 2 3 N 1 2 3 N The crossbar is a higher-speed alternative to serially transferred interconnection fabrics which can cause bottlenecks. Large switches built from crossbar and multistage space switches Can buffer at input, output, or both (performance vs. complexity) 输出 输出

20 自路由交换：Banyan 交换 自路由交换不需要控制器。 输出端口的序号决定了不同路径。
1 2 输入 输出 3 4 5 6 7 Stage 1 Stage 2 Stage 3 印度榕树是一种形状奇特的树，枝条上生有气根，垂入土中即变成新树。 自路由交换不需要控制器。 输出端口的序号决定了不同路径。 101 → (1) 下端口, (2) 上端口, (3)下端口 其中 0 = 上端口，1 = 下端口。 Self-routing switches do not require a controller. The output port number determines the route. 101 → (1) lower port, (2) upper port, (3) lower port In the example … 0=up and 1=down

21 封包网络中的路由

22 封包网络中的路由 从1端到6端有3条路径（不考虑回路和环路如1-4-3-6）： 1-3-6, 1-4-5-6, 1-2-5-6 如何选择？
最短延时？最少步数？最大带宽？最小损耗？最高可靠度？ 1 2 3 4 5 6 Node (switch or router)

23 创建路由表 需要链路状态的信息。 像上/下连接；拥塞；延迟或其他指标。 需要用路由协议传输连接状态信息。 交换了什么信息？多久交换一次？
和相邻路由器交换信息，采用广播或泛洪的方式。 需要根据信息计算路径。 单指标；多指标 单路径路由；可选路径路由 Need information on state of links. Link up/down; congested; delay or other metrics Need to distribute link state information using a routing protocol. What information is exchanged? How often? Exchange with neighbours; Broadcast or flood Need to compute routes based on information. Single metric; multiple metrics Single route; alternate routes

24 路由算法的需求 处理网络变化 拓扑结构或者带宽变化，网络堵塞。 可以将路由分类。 可以处理循环的情况。 最优性 资源的使用，路径的长度。
强壮性 在出现高负载、网络阻塞、错误或设备失效的情况下能继续工作。 简约性 高效的软件实现，合理的处理负载。 Responsiveness to change Topology or bandwidth changes, congestion Rapid convergence of routers to consistent set of routes Freedom from persistent loops Optimality Resource utilization, path length Robustness Continues working under high load, congestion, faults, equipment failures, incorrect implementations Simplicity Efficient software implementation, reasonable processing load

25 集中式路由和分布式路由 集中式路由 所有路由都由一个中央节点定义。 所有状态信息都被送到中央节点。 可以适应频繁的拓扑变化。 不可扩展
分散式路由 路由由使用分散算法的路由器定义。 状态信息在路由器之间交换。 可以适应拓扑和其他的变化。 扩展性强。 Centralized Routing All routes determined by a central node All state information sent to central node Problems adapting to frequent topology changes Does not scale Distributed Routing Routes determined by routers using distributed algorithm State information exchanged by routers Adapts to topology and other changes Better scalability

26 静态路由和动态路由 静态路由 人为设定好后就不再改变；需要人为管理。 当传输可以预测且网络结构比较简单时才可以使用。
用来取代部分动态算法设置的路由。 用来充当默认路由器。 动态路由 可以适应网络状态的变化。 自动化。 根据接收的最新网络状态信息计算并设置路由。 Static Routing Set up manually, do not change; requires administration Works when traffic predictable & network is simple Used to override some routes set by dynamic algorithm Used to provide default router Dynamic Routing Adapt to changes in network conditions Automated Calculates routes based on received updated network state information

27 虚拟电路中的分包路由导向。 虚电路标识(virtual-circuit identifier) 拥有一个本地签名.
上图的中A连接了两条虚电路。虚电路1导向B；虚电路5导向D。 在连设置的过程中路由被定义。 交换机中的表指出了所选择的路径。 1 2 3 4 5 6 A B C D 7 8 Switch or router Host VCI The VCI (virtual-circuit identifier) has local significance. A above has 2 VCs. VC1 goes toward B and VC5 goes on to D. Route determined during connection setup. Tables in switches implement forwarding that realizes selected route.

28 虚电路例子：在A的VCI5到D (假设虚电路都是双向的。)
Incoming Outgoing Node VCI Node VCI A A A A B B B B C C D D Node 1 Node 2 Node 3 Node 4 Node 6 Node 5 从A到D的虚电路标识。 A & VCI 5 → 3 & VCI 3 → 4 & VCI 4 → 5 & VCI 5 → D & VCI 2

29 数据报封包网络中的路由表 (不用虚电路，连接节点1和节点5。)
Node 1 Node 2 Node 3 Node 4 Node 6 Node 5 Destination Next node

30 非分层地址和路由 路由和地址之间没有距离关系。 每个路由表需要定义16种输入。 1 4 3 R1 R2 2 5
R1 1 2 5 4 3 … … … … R2

31 分层地址和路由。 前两位指明需要访问的网络 每个路由表只需要第一4种输入。 1 4 3 R1 R2 2 5
R1 R2 1 2 5 4 3

32 平面路由和分级路由 平面路由 路由路由器都是对等的。 不能扩展。 分层路由
划分为：。区域内的路由（一级路由），域内独立的区域之间的路由称（二级路由） 一些路由器是路由的骨干。 另一些路由器只在区域内通信。 效率较高，因为它符合典型的传输流模式。 可扩展到更大的主机数量。

33 Specialized Routing 泛洪 在启动网络时使用。 在需要向所有节点传输信息时使用。 偏射路由
预先设置的路由程序，之后不能改变。 没有路由合成。

34 最短路径--路由

35 寻找最短路径—路由 在信息源和目的地之间很很多条通路。 路由的功能包括选择一条合适的通路完成传输。
一般情况下，链接连点的链路都会包含距离或者损耗信息。 路由其实就是选择最短路径的过程。 Puxi Viaduct, Shanghai Many possible paths connect any given source and to any given destination. Routing involves the selection of the path to be used to accomplish a given transfer. Typically it is possible to attach a cost or distance to a link connecting two nodes. Routing can then be posed as a shortest path problem.

36 路由指标 测量一条路径的可取性。 路径长度 = 花费或者距离的总和。 用到的指标
经过结点的个数: 所使用资源的粗略测量。 可信度: 链接的有效性; BER（ Bit Error Rate )误码率。 延时: 整条路径延时的总和。复杂度。 带宽: 一条路径的承载能力。 负载: 可以使用的路由器和链路。 花费: $$$ Means for measuring desirability of a path Path length = sum of costs or distances Possible metrics Hop count: rough measure of resources used Reliability: link availability; BER Delay: sum of delays along path; complex and dynamic Bandwidth: “available capacity” in a path Load: Link & router utilization along path Cost: $$$

37 最短路径方法 距离矢量协议 相邻路由器间交换记录了到目标距离的表。 对每一个目标都定义了一个最优下一步。
Bellman-Ford 算法就是其中之一。 链路状态协议 链路状态信息传送到所有路由器。 路由器完成拓扑信息。 得出最短路径。 迪科斯彻最短路径算法。 Distance Vector Protocols Neighbours exchange list of distances to destinations Best next-hop determined for each destination The distributed Bellman-Ford is an example. Link State Protocols Link state information flooded to all routers Routers have complete topology information Shortest path (& hence next hop) calculated Dijkstra (centralized) shortest path algorithm

38 距离矢量路由 本地标识 方向 距离 路由表 对于每个目标： 下一结点 合成表 相邻路由间交换路由表信息。 决定当前最优下一步 告知相邻路由器
周期性 在每次交换后 Dest. next Dist.

39 到Rome的最短据距离 Rome j i Dj Di Cij 结点如何判断到目标结点的最短路径？比如到节点Rome.
若 Di 是从结点i到结点Rome的最短距离，同时j是i的在最短路径上的相邻结点，那么Di = Cij + Dj

40 Bellman-Ford 算法 考虑对目标d的的计算。 初始化 每个结点的表都有一行记录目标d的信息。
结点d到到结点d的距离是0: Dd=0 其他结点到结点d的距离是无穷大: Dj=∞ , 对于 j d 下一跳结点nj = -1 指明还没有定义j结点 for j  d 发送 发送新的距离矢量到跨越本地链路的相邻路由。 接收 在结点j,搜寻下一个到d最短距离结点。 Minj { Cij + Dj } 若得到新的结点或距离，替换旧的 (nj, Dj(d)) 为(nj*, Dj*(d)) 返回发送步骤。

41 Bellman-Ford 算法 现在同时考虑所有的目标。 初始化 每一个结点都有一行记录目标d的信息。
结点d到结点d的距离是0: Dd(d)=0 其它结点到d的距离是无穷: Dj(d)= ∞ ,对于j  d 下一个结点nj = -1 表示还没有定义。 发送 发送新的距离矢量到相邻结点。 接收 找到下一个到d距离最短的结点 Minj { Cij+ Dj(d) } 替换 (nj, Di(d)) 为(nj*, Dj*(d)) 如果更新了距离矢量。 返回到发送步骤。 Now consider parallel computations for all destinations d Initialization Each node has 1 row for each destination d Distance of node d to itself is zero: Dd(d)=0 Distance of other node j to d is infinite: Dj(d)= ∞ , for j  d Next node nj = -1 since not yet defined Send Step Send new distance vector to immediate neighbours across local link Receive Step For each destination d, find the next hop that gives the minimum distance to d, Minj { Cij+ Dj(d) } Replace old (nj, Di(d)) by new (nj*, Dj*(d)) if new next node or distance found Go to send step

42 Rome 对于目标点Rome， 对于目标点Rome， 结点3的表项。 结点1的表项。 (-1, ) 1 2 3 3 1 5 4 6 2
步骤 结点 1 结点2 结点3 结点4 结点5 初始化 (-1, ) 1 2 3 对于目标点Rome， 结点3的表项。 对于目标点Rome， 结点1的表项。 3 1 5 4 6 2 Rome

43 Rome 1 2 (-1, ) 1 (6,1) (6,2) 2 3 D3=D6+1 n3=6 D6=0 3 1 5 4 6 2 D6=0
步骤 结点 1 结点2 结点3 结点4 结点5 初始化 (-1, ) 1 (6,1) (6,2) 2 3 D3=D6+1 n3=6 D6=0 1 3 1 5 4 6 2 Rome 2 D6=0 D5=D6+2 n5=6

44 步骤 结点 1 结点2 结点3 结点4 结点5 初始化 (-1, ) 1 (6, 1) (6,2) 2 (3,3) (5,6) 3 3 1 3 1 5 4 6 2 3 Rome 6 2

45 Rome 1 3 3 6 4 2 初始化 (-1, ) 1 (6, 1) (6,2) 2 (3,3) (5,6) 3 (4,4) 3 1
步骤 结点 1 结点2 结点3 结点4 结点5 初始化 (-1, ) 1 (6, 1) (6,2) 2 (3,3) (5,6) 3 (4,4) 1 3 3 1 5 4 6 2 3 Rome 6 4 2

46 在第三步时，所有结点到结点6的最短路径都被找到。
步骤 结点 1 结点2 结点3 结点4 结点5 初始化 (-1, ) 1 (6, 1) (6,2) 2 (3,3) (5,6) 3 (4,4) 在第三步时，所有结点到结点6的最短路径都被找到。 3 1 5 4 6 2

47 Rome 当网络在结点3和6间断开时，结点3和4间便形成了一个循环。 1 5 3 3 4 2 (3,3) (4,4) (6, 1)
步骤 结点 1 结点2 结点3 结点4 结点5 初始化 (3,3) (4,4) (6, 1) (6,2) 1 (4, 5) 2 3 当网络在结点3和6间断开时，结点3和4间便形成了一个循环。 1 5 3 3 1 5 4 6 2 3 Imagine now that the network is disconnected. We will see a loop created between nodes 3 and 4. Rome 4 2

48 Rome 5 7 3 5 3 2 4 结点4也可以选择结点2作为下一个结点，因为根据表，此时由2或5到达目标的距离相同。 初始化 (3,3)
步骤 结点 1 结点2 结点3 结点4 结点5 初始化 (3,3) (4,4) (6, 1) (6,2) 1 (4, 5) 2 (3,7) (5,5) 3 5 7 3 3 1 5 4 6 2 5 3 Rome 2 4 结点4也可以选择结点2作为下一个结点，因为根据表，此时由2或5到达目标的距离相同。

49 Rome 5 7 7 5 2 4 6 结点2也可以选择结点5作为下一个结点，因为根据表，此时由4或5到达目标的距离相同。 (3,3)
步骤 结点 1 结点2 结点3 结点4 结点5 初始化 (3,3) (4,4) (6, 1) (6,2) 1 (4, 5) 2 (3,7) (5,5) 3 (4,6) (4, 7) 5 7 7 3 1 5 4 6 2 5 Rome 2 4 6 结点2也可以选择结点5作为下一个结点，因为根据表，此时由4或5到达目标的距离相同。

50 Rome 7 7 9 5 6 2 结点1也可以选择结点3作为下一个结点。 1 (3,3) (4,4) (4, 5) (6,2) 2
步骤 结点 1 结点2 结点3 结点4 结点5 1 (3,3) (4,4) (4, 5) (6,2) 2 (3,7) (2,5) 3 (4,6) (4, 7) (5,5) 4 (2,9) 7 7 9 3 5 4 6 2 1 5 Rome 6 2 结点1也可以选择结点3作为下一个结点。

51 路径无穷计算问题 几个结点都已对方作为下一结点，最终导致路径无穷计算(结点4是目标) … 3 1 2 4 X (2,3) (3,2)
(a) (b) 几个结点都已对方作为下一结点，最终导致路径无穷计算(结点4是目标) Update 结点 1 结点 2 结点 3 中断前(a) (2,3) (3,2) (4, 1) 中断后(b) 1 (3,4) 2 (2,5) 3 (3,6) 4 (2,7) 5 (3,8) …

52 所存在的问题：错误发生后很难发现 处理方法 水平分割 路由器从某个接口学到的路由，不会再从该接口发回给邻居路由器。 带毒性逆转的水平分割
路由器从某个接口学到的路由，会再从该接口发回给邻居路由器，但将距离设为无穷大。 快速的消除路由直接循环。 对于路由间接循环不起作用。

53 带毒性逆转的水平分割 几个结点都已对方作为下一结点 3 1 2 4 X Update 结点 1 结点 2 结点 3 (2, 3)
(b) 几个结点都已对方作为下一结点 Update 结点 1 结点 2 结点 3 中断前 (2, 3) (3, 2) (4, 1) 中断后 (-1, ) 结点3检测到没有到结点4的路径，结点3到结点4的距离改为无穷大。结点2通过结点3访问结点4。 1 结点2没有路径访问结点4，故结点2到结点4的距离改为无穷大。 2 结点1接测到没有路径访问结点4。

54 链路状态算法 基本思路：两步 每个源节点都有一个包含所有结点和整个网络链路状态的图。 从图中找到从源节点到目标结点的最短路径。
广播链路状态信息。 网络中的每个结点都向其他结点广播： 相邻结点的ID：Ni=set of neighbours of i 到相邻结点的距离: {Cij | j Ni} 泛洪是一种常用的广播封包的方法。 Basic idea: two step procedure Each source node gets a map of all nodes and link metrics (link state) of the entire network Find the shortest path on the map from the source node to all destination nodes Broadcast of link-state information Every node i in the network broadcasts to every other node in the network: ID’s of its neighbours: Ni=set of neighbours of i Distances to its neighbours: {Cij | j Ni} Flooding is a popular method of broadcasting packets

55 Dijkstra 算法 N: 设置已经找到最短路径的节点 初始化: (从源节点s开始)
N = {s}, Ds = 0, “s节点到自己的距离为0” 和s直接相连节点：Dj=Csj 对于j  s 步骤 A: (找到最近的节点i) 节点i选择到源节点距离最小的且不在集合N内节点。 将节点i加入到集合N中。 如果所有节点都在集合N中，则结束。 步骤 B: (更改各点距离) 对于每个不包含于N的节点 Dj = min (Dj, Di+Cij) 返回步骤A。 N: set of nodes for which shortest path already found Initialization: (Start with source node s) N = {s}, Ds = 0, “s is distance zero from itself” Dj=Csj for all j  s, distances of directly-connected neighbours Step A: (Find next closest node i) Find i  N such that Di = min Dj for j  N Add i to N If N contains all the nodes, stop Step B: (update minimum costs) For each node j  N Dj = min (Dj, Di+Cij) Go to Step A 从源节点到j节点的最小距离都要经过集合N中的节点i。

56 Dijkstra’s 算法执行过程     N D2 D3 D4 D5 D6 {1} 3 2 5  1 {1,3} 4
Iteration N D2 D3 D4 D5 D6 Initial {1} 3 2 5  1 {1,3} 4 {1,2,3} 7 {1,2,3,6} {1,2,3,4,6} {1,2,3,4,5,6}     

57 通过Dijkstra 算法得到各点的最短路径
1 2 4 5 6 3 3 1 2 4 5 6 1 2 4 5 6 3 1 2 4 5 6 3 1 2 4 5 6 3 1 2 4 5 6 3

58 当连接失败时 如果连接失败 路由器将设置距离为无穷大，同时向网络各点发送更新封包。
所有的路由器都会马上更新自己的链路数据库并重新计算最短路径。 网络很快就能恢复。 但是旧的更新信息可能会产生干扰 向更新信息中加入时间标签或者序号。 检查接收到的更新信息是不是最新的。 如果是最新信息，将其加入数据库并发送。 如果是旧信息，则送出更新信息 If a link fails … router sets link distance to infinity & floods the network with an update packet all routers immediately update their link database and recalculate their shortest paths recovery very quick But watch out for old update messages add time stamp or sequence no to each update message check whether each received update message is new if new, add it to database and broadcast if older, send update message on arriving link

59 总结 封包交换和相关网络层 封包交换网络的结构 封包网络中的路由 最短路径路由 距离矢量 (Bellman-Ford)
链路状态(Dijkstra)

60 Thank You 需要自学 阅读第7章 拓扑封包网络(考点) 虚电路的内容Details of virtual circuits (考点)
ATM网络 networks (非考点) 传输管理Traffic management (非考点) 拥塞控制 (除了TCP拥塞控制其他非考点)