• 1. Network Layer4-1Chapter 4: Network LayerChapter goals: 理解网络层原理服务: 转发forwording 选路routing (path selection) dealing with scale 路由器原理how a router works Internet实例及实现
    • 2. Network Layer4-2Chapter 4: Network Layer4. 1 概述 4.2 虚电路和数据报网络 4.3 路由器工作原理 4.4 IP: Internet Protocol 数据报格式 IPv4 编址 ICMP4.5 选路算法 Link state Distance Vector Hierarchical routing 4.6 Internet中的选路 RIP OSPF BGP
    • 3. Network Layer4-3Introduction(Network layer)将分组从一台发送主机移动到一台接收主机 发送方将数据封装成一个数据报(即网络层分组) 接收方接收数据报,提取出运输层报文段,并将其向上交付给运输层 网络层协议在所有的主机、路由器上运行 路由器的主要作用检查IP数据报报头,将数据报从入链路转发到出链路 network data link physical network data link physical network data link physical network data link physical network data link physical network data link physical network data link physical network data link physicalapplication transport network data link physicalapplication transport network data link physicalH2
    • 4. Network Layer4-4Key Network-Layer Functions转发:当一个分组到达某路由器的一条输入链路时,该路由器必须将该分组移动到适当的输出链路。 选路:当分组从发送方流向接收方时,网络层必须决定这些分组所采用的路由或路径。 选路算法Routing algorithms analogy: 选路是指分组从源到目的地时,决定端到端路径的网络范围的进程。 转发是指将分组从一个输入链路接口转移到适当的输出链路接口的路由器本地动作。
    • 5. Network Layer4-51230111value in arriving packet’s headerrouting algorithmlocal forwarding tableheader valueoutput link0100 0101 0111 10013 2 2 1Interplay between routing and forwarding
    • 6. Network Layer4-6Key Network-Layer Functions连接建立Connection setup 第三种重要的网络功能: ATM, frame relay, X.25 在数据流传输之前,两个主机要建立虚拟连接 Routers get involved Network and transport layer service: Network: between two hosts Transport: between two processes
    • 7. Network Layer4-7网络服务模型Q: What service model for “channel” transporting datagrams from sender to rcvr?在发送主机中,当运输层向网络层传递一个分组时,能由网络层提供的特定服务包括: 确保交付 具有时延上界的确保交付给定的源和目的之间提供分组的流: 有序分组交付 确保最小带宽 确保最大时延抖动 安全性服务
    • 8. Network Layer4-8Network layer service models:Network Architecture Internet ATM ATM ATM ATMService Model best effort CBR VBR ABR UBRBandwidth none constant rate guaranteed rate guaranteed minimum noneLoss no yes yes no noOrder no yes yes yes yesTiming no yes yes no noCongestion feedback no (inferred via loss) no congestion no congestion yes noGuarantees ?
    • 9. Network Layer4-9Chapter 4: Network Layer4. 1 概述 4.2 虚电路和数据报网络 4.3 路由器工作原理 4.4 IP: Internet Protocol 数据报格式 IPv4 编址 ICMP IPv64.5 选路算法 Link state Distance Vector Hierarchical routing 4.6 Internet中的选路 RIP OSPF BGP 4.7 广播和多播
    • 10. Network Layer4-10网络层连接和无连接服务网络层服务是由网络层向运输层提供的主机到主机的服务 仅在网络层提供连接服务的计算机网络被称为虚电路(Virtual-Circuit, VC)网络;仅在网络层提供无连接服务的计算机网络被称为数据报网络(datagram network)。 在运输层实现面向连接的服务与在网络层实现连接服务是根本不同的: Service: host-to-host No choice: network provides one or the other Implementation: in the core
    • 11. Network Layer4-11网络层连接和无连接服务数据报网络Datagram network Internet 虚电路网络VC network ATM, frame relay, X.25
    • 12. Network Layer4-12虚电路网络Virtual circuits network在数据流传送之前需要建立连接 每个数据包包括VC号,沿着该路径的每段链路一个号码(not destination host address) 每个路由器维护源-目的路径状态 链路、路由资源可能有VC分配 (bandwidth, buffers)源和目的主机之间的路径 performance-wise network actions along source-to-dest path
    • 13. Network Layer4-13VC implementation一条虚电路(VC)的组成: 源和目的主机之间的路径 VC号,沿着该路径的每段链路一个号码 沿着该路径的每台路由器中的转发表表项 属于一条虚电路的分组将在它的首部携带一个VC号. 一条虚电路在每条链路上可能具有不同的VC号. 每台中间路由器必须用一个新的VC号替代每个传输分组的VC号。该新的VC号从转发表获得。
    • 14. Network Layer4-14Forwarding table122232132VC numberinterface numberIncoming interface Incoming VC # Outgoing interface Outgoing VC #1 12 2 22 2 63 1 18 3 7 2 17 1 97 3 87 … … … …Forwarding table in northwest router:路由器必须为进行中的连接维持连接状态信息!
    • 15. Network Layer4-15VC implementationThree phrase 虚电路建立。VC establish 数据传送Data transmission 虚电路拆除VC teardown
    • 16. Network Layer4-16Virtual circuits:信令报文signaling protocols建立、维护、拆除 VC used in ATM, frame-relay, X.25 not used in today’s Internetapplication transport network data link physicalapplication transport network data link physical1. Initiate call2. incoming call3. Accept call4. Call connected5. Data flow begins6. Receive data
    • 17. Network Layer4-17Datagram networks在网络层没有建立连接的过程 routers: 路由器不维护任何有关虚电路的状态信息 no network-level concept of “connection” 使用分组的目的地址来转发该分组 packets between same source-dest pair may take different pathsapplication transport network data link physicalapplication transport network data link physical1. Send data2. Receive data
    • 18. Network Layer4-18Forwarding table Destination Address Range Link Interface 11001000 00010111 00010000 00000000 through 0 11001000 00010111 00010111 11111111 11001000 00010111 00011000 00000000 through 1 11001000 00010111 00011000 11111111 11001000 00010111 00011001 00000000 through 2 11001000 00010111 00011111 11111111 otherwise 34 billion possible entries
    • 19. Network Layer4-19Longest prefix matching Prefix Match Link Interface 11001000 00010111 00010 0 11001000 00010111 00011000 1 11001000 00010111 00011 2 otherwise 3DA: 11001000 00010111 00011000 10101010 ExamplesDA: 11001000 00010111 00010110 10100001 Which interface?Which interface?
    • 20. Network Layer4-20Datagram or VC network: why?Internet 数据在计算机之间传输 “elastic” service, no strict timing req. “smart” end systems (computers) can adapt, perform control, error recovery simple inside network, complexity at “edge” many link types different characteristics uniform service difficultATM 由电话网演变而来 human conversation: strict timing, reliability requirements need for guaranteed service “dumb” end systems telephones complexity inside network
    • 21. Network Layer4-21Chapter 4: Network Layer4. 1 概述 4.2 虚电路和数据报网络 4.3 路由器工作原理 4.4 IP: Internet Protocol 数据报格式 IPv4 编址 ICMP IPv64.5 选路算法 Link state Distance Vector Hierarchical routing 4.6 Internet中的选路 RIP OSPF BGP 4.7 广播和多播
    • 22. Network Layer4-22Router Architecture Overview两个重要功能: 运行路由算法/协议 (RIP, OSPF, BGP) 将数据报从输入链路转发至输出链路
    • 23. Network Layer4-23输入端口Decentralized switching: 输入端口的线路端接功能与数据链路处理实现了与通向路由器的各个输入链路相关的物理层和数据链路层 希望输入端口的处理速度能够达到线路速度(line speed),即执行一次查找的时间应少于从输入端口接收一个分组所需的时间。 queuing:一个被阻塞的分组必须要在输入端口处排队,并等待稍后被及时调度以通过交换结构Physical layer: bit-level receptionData link layer: e.g., Ethernet see chapter 5
    • 24. Network Layer4-24三种交换技术
    • 25. Network Layer4-25经内存交换第一代路由器: 在输入端口与输出端口之间的交换是在CPU(选路处理器)的直接控制下完成的 分组从输入端口处被拷贝到处理器内存中 像共享内存的多处理器,用一个线路卡上的处理器将分组交换进适当输出端口的内存中 若内存带宽为每秒可写进或读出B个分组,则总的转发吞吐量(分组从输入端口被传送到输出端口的总速率)必然小于B/2 Input PortOutput PortMemorySystem Bus
    • 26. Network Layer4-26经一根总线交换输入端口经一根共享总线将分组直接传送到输出端口,不需要选路处理器的干预 bus contention:路由器的交换带宽受总线速率的限制 1 Gbps bus, Cisco 1900:总线带宽可能超过1 Gbps,对于运行在接入网或企业网(如局域网与公司网)中的路由器来说,通过总线交换通常是足够的(非骨干路由器)
    • 27. Network Layer4-27经一个互联网络交换克服单一、共享式总线带宽限制 使用一个更复杂的互联网络,如过去在多处理器计算体系结构中用来互连多个处理器的网络 由2n条总线组成的互联网络,它将n个输入端口与n个输出端口连接. Cisco 12000: 。使用了一个互联网络,能提供高达60 Gbps的速率通过交换结构 目前在互联网络设计[Keshav 1998]中的一种趋势是,将长度变化的IP分组分片成固定尺寸的信元,加上标签并通过互联网络进行交换。
    • 28. Network Layer4-28输出端口Output Ports处理取出存放在输出端口内存中的分组并将其传送到输出链路上 当交换结构将分组交付给输出端口的速率超过输出链路速率时,就需要排队与缓存管理功能
    • 29. Network Layer4-29Output port queueing当通过交换到达的数据数率超过输出线速则缓存 输出端口的缓存溢出可能导致延迟和丢包 Packet scheduler:FCFS,WFQ Drop:AQM(RED)
    • 30. Network Layer4-30Input Port Queuing如果交换结构不能快得(相对于输入线路速率而言)使所有到达分组无时延地通过它传送,则在输入端口也将出现分组排队 Head-of-the-Line (HOL) blocking:输入排队交换机中的线路前部阻塞,即在一个输入队列中排队的分组必须等待通过交换结构发送(即使输出端口是空闲的) 输入端口的缓存溢出可能导致延迟和丢包!
    • 31. Network Layer4-31Chapter 4: Network Layer4. 1 概述 4.2 虚电路和数据报网络 4.3 路由器工作原理 4.4 IP: Internet Protocol 数据报格式 IPv4 编址 ICMP IPv64.5 选路算法 Link state Distance Vector Hierarchical routing 4.6 Internet中的选路 RIP OSPF BGP 4.7 广播和多播
    • 32. Network Layer4-32The Internet Network layerHost, router network layer functions:
    • 33. Network Layer4-33Chapter 4: Network Layer4. 1 概述 4.2 虚电路和数据报网络 4.3 路由器工作原理 4.4 IP: Internet Protocol 数据报格式 IPv4 编址 ICMP IPv64.5 选路算法 Link state Distance Vector Hierarchical routing 4.6 Internet中的选路 RIP OSPF BGP 4.7 广播和多播
    • 34. Network Layer4-34IP datagram format
    • 35. Network Layer4-35IP datagram formatverlength32 bitsdata (variable length, typically a TCP or UDP segment)16-bit identifierInternet checksumtime to live32 bit source IP addressIP protocol version numberheader length (bytes)max number remaining hops (decremented at each router)for fragmentation/ reassemblytotal datagram length (bytes)upper layer protocol to deliver payload tohead. lentype of service“type” of data flgsfragment offsetupper layer32 bit destination IP addressOptions (if any)E.g. timestamp, record route taken, specify list of routers to visit.how much overhead with TCP? 20 bytes of TCP 20 bytes of IP = 40 bytes + app layer overhead
    • 36. Network Layer4-36IP 分片和重组一个链路层帧能承载的最大数据量叫做最大传输单元(Maximum Transmission Unit,MTU) 不同链路类型,不同MTUs 以太网帧可承载不超过1500字节的数据,而某些广域网链路的帧可承载不超过576字节的数据 将IP数据报中的数据分片成两个或更多个较小的数据报,用单独的链路层帧封装这些较小的IP数据报 仅在最终的目的地重组“reassembled” IPv4的设计者将标识、标志和片偏移字段放在IP数据报中fragmentation: in: one large datagram out: 3 smaller datagramsreassembly
    • 37. Network Layer4-37IP Fragmentation and ReassemblyID =xoffset =0fragflag =0length =4000ID =xoffset =0fragflag =1length =1500ID =xoffset =185fragflag =1length =1500ID =xoffset =370fragflag =0length =1040One large datagram becomes several smaller datagramsExample 4000 byte datagram MTU = 1500 bytes 1480 bytes in data fieldoffset = 1480/8
    • 38. Network Layer4-38Chapter 4: Network Layer4. 1 概述 4.2 虚电路和数据报网络 4.3 路由器工作原理 4.4 IP: Internet Protocol 数据报格式 IPv4 编址 ICMP IPv64.5 选路算法 Link state Distance Vector Hierarchical routing 4.6 Internet中的选路 RIP OSPF BGP 4.7 广播和多播
    • 39. Network Layer4-39IP Addressing: introductionIP address:32比特, 标识主机、路由器接口 interface:主机与物理链路之间的边界 路由器一般有多个接口 主机可能有多个接口 每台主机和路由器接口都拥有自己的IP地址 一个IP地址在技术上是与一个接口相关联的,而不是与包括该接口的主机或路由器相关联的。223.1.1.1223.1.1.2223.1.1.3223.1.1.4223.1.2.9223.1.2.2223.1.2.1223.1.3.2223.1.3.1223.1.3.27223.1.1.1 = 11011111 00000001 00000001 00000001223111
    • 40. Network Layer4-40子网SubnetsIP address: subnet part (high order bits) host part (low order bits) What’s a subnet ? 设备接口具有相同的子网部分 可以不需要中转路由器互相访问223.1.1.1223.1.1.2223.1.1.3223.1.1.4223.1.2.9223.1.2.2223.1.2.1223.1.3.2223.1.3.1223.1.3.27network consisting of 3 subnetsLAN
    • 41. Network Layer4-41Subnets223.1.1.0/24223.1.2.0/24223.1.3.0/24Recipe 互连这3台主机的接口与路由器的一个接口的网络形成一个子网(subnet) 为了确定子网,分开主机和路由器的每个接口,从而产生了几个分离的网络岛,接口端接了这些独立的网络的端点。这些独立的网络中的每个都叫做一个子网(subnet)。 Subnet mask: /24
    • 42. Network Layer4-42SubnetsHow many?223.1.1.1223.1.1.3223.1.1.4223.1.2.2223.1.2.1223.1.2.6223.1.3.2223.1.3.1223.1.3.27223.1.1.2223.1.7.0223.1.7.1223.1.8.0223.1.8.1223.1.9.1223.1.9.2
    • 43. Network Layer4-43IP Addressing:methodsClassful addressing(1981) Subnet addressing(1983) 无类别域间选路CIDR addressing (1993)
    • 44. Network Layer4-44IP Addressing: Classful addressingclassful addressing 分为5类 点分十进制形式 IP address formats.
    • 45. Network Layer4-45IP Addresses: Classful addressing (2)Special IP addresses. 特殊的 IP addresses The values 0 and -1 (all 1s) have special meanings 127.xx.yy.zz are reserved for loopback testing
    • 46. Network Layer4-46IP Addresses: Classful addressing (3) Special IP addresses Private IP addresses A类 10.0.0.0 --10.255.255.255 B类 172.16.0.0--172.31.255.255 C类 192.168.0.0--192.168.255.255
    • 47. Network Layer4-47IP Addresses:SubnetSome problem a single class A, B, or C address refers to one network, not to a collection of LANs The solution is to allow a network to be split into several parts for internal use but still act like a single network to the outside world
    • 48. Network Layer4-48IP Addresses:Subnet(2)A campus network consisting of LANs for various departments.
    • 49. Network Layer4-49IP Addresses:Subnet(3)A class B network subnetted into 64 subnets. 子网掩码用点分十进制形式表示,或用斜线表示网络位数 example 255.255.252.0 An alternative notation is /22
    • 50. Network Layer4-50IP addressing: CIDRCIDR: Classless InterDomain Routing 子网部分的长度 address format: a.b.c.d/x, where x is # bits in subnet portion of address11001000 00010111 00010000 00000000subnet parthost part200.23.16.0/23
    • 51. Network Layer4-51IP addresses: how to get one?Q: 网络如何从IP地址得到子网? A: ISP会从已分给它的更大地址块中提供一些地址。ISP's block 11001000 00010111 00010000 00000000 200.23.16.0/20 Organization 0 11001000 00010111 00010000 00000000 200.23.16.0/23 Organization 1 11001000 00010111 00010010 00000000 200.23.18.0/23 Organization 2 11001000 00010111 00010100 00000000 200.23.20.0/23 ... ….. …. …. Organization 7 11001000 00010111 00011110 00000000 200.23.30.0/23
    • 52. Network Layer4-52Hierarchical addressing: route aggregation“Send me anything with addresses beginning 200.23.16.0/20”200.23.16.0/23200.23.18.0/23200.23.30.0/23Fly-By-Night-ISPOrganization 0Organization 7InternetOrganization 1ISPs-R-Us“Send me anything with addresses beginning 199.31.0.0/16”200.23.20.0/23Organization 2......Hierarchical addressing allows efficient advertisement of routing information:
    • 53. Network Layer4-53Hierarchical addressing: more specific routesISPs-R-Us has a more specific route to Organization 1“Send me anything with addresses beginning 200.23.16.0/20”200.23.16.0/23200.23.18.0/23200.23.30.0/23Fly-By-Night-ISPOrganization 0Organization 7InternetOrganization 1ISPs-R-Us“Send me anything with addresses beginning 199.31.0.0/16 or 200.23.18.0/23”200.23.20.0/23Organization 2......
    • 54. 路由器对IP 报文的转发过程Network Layer4-541. 接收报文,检查IP报头,版本号校验和; 2. 根据报文目的IP地址, 查询路由表,遵循最长前缀匹配; 3. 获得接口下一跳IP地址; 4. TTL减1,重新计算IP校验和; 5. 解析下一跳IP地址对应的MAC地址,封装新的链路层头部 6. 从路由器输出接口发出报文
    • 55. Network Layer4-55IP addresses 如何配?Q: How does host get IP address? hard-coded by system admin in a file Wintel: control-panel->network->configuration->tcp/ip->properties UNIX: /etc/rc.config DHCP: Dynamic Host Configuration Protocol:动态主机配置协议 “plug-and-play”
    • 56. Network Layer4-56DHCP: Dynamic Host Configuration ProtocolGoal: 当主机接入网络时,允许主机从网络中的网络服务器上动态地获得其IP地址。 Can renew its lease on address in use Allows reuse of addresses (only hold address while connected an “on”) Support for mobile users who want to join network (more shortly) DHCP overview: 主机广播“DHCP discover” msg DHCP 服务器响应 “DHCP offer” msg 主机请求IP address: “DHCP request” msg DHCP server 发送地址: “DHCP ack” msg
    • 57. Network Layer4-57DHCP client-server scenario223.1.1.1223.1.1.2223.1.1.3223.1.1.4223.1.2.9223.1.2.2223.1.2.1223.1.3.2223.1.3.1223.1.3.27ABEDHCP serverarriving DHCP client needs address in this network
    • 58. Network Layer4-58DHCP client-server scenarioDHCP server: 223.1.2.5arriving clienttimeDHCP discoversrc : 0.0.0.0, 68 dest.: 255.255.255.255,67 yiaddr: 0.0.0.0 transaction ID: 654DHCP offersrc: 223.1.2.5, 67 dest: 255.255.255.255, 68 yiaddrr: 223.1.2.4 transaction ID: 654 Lifetime: 3600 secsDHCP requestsrc: 0.0.0.0, 68 dest:: 255.255.255.255, 67 yiaddrr: 223.1.2.4 transaction ID: 655 Lifetime: 3600 secsDHCP ACKsrc: 223.1.2.5, 67 dest: 255.255.255.255, 68 yiaddrr: 223.1.2.4 transaction ID: 655 Lifetime: 3600 secs
    • 59. Network Layer4-59IP addressing: the last word...Q: How does an ISP get block of addresses? A: ICANN: Internet Corporation for Assigned Names and Numbers 分配地址(ARIN、RIPE、APNIC) 管理 DNS 分配域名, 解析冲突
    • 60. Network Layer4-60NAT: Network Address Translation10.0.0.110.0.0.210.0.0.310.0.0.4138.76.29.7local network (e.g., home network) 10.0.0/24rest of InternetDatagrams with source or destination in this network have 10.0.0/24 address for source, destination (as usual)All datagrams leaving local network have same single source NAT IP address: 138.76.29.7, different source port numbers
    • 61. Network Layer4-61NAT: 网络地址转换Motivation: NAT路由器对外界的行为就如同一个具有单一IP地址的单一设备: 不用从 ISP分配更多的地址: - 所有设备仅用一个 IP地址 可以改变设备的IP地址,但不用通知外网 可以改变ISP 地址,但不用改变内部网络设备的地址 内部网络的设备对外网不可见 (a security plus).
    • 62. Network Layer4-62NAT: Network Address Translation10.0.0.110.0.0.210.0.0.3S: 10.0.0.1, 3345 D: 128.119.40.186, 80110.0.0.4138.76.29.71: host 10.0.0.1 sends datagram to 128.119.40, 80NAT translation table WAN side addr LAN side addr138.76.29.7, 5001 10.0.0.1, 3345 …… ……S: 128.119.40.186, 80 D: 10.0.0.1, 3345 4S: 138.76.29.7, 5001 D: 128.119.40.186, 8022: NAT router changes datagram source addr from 10.0.0.1, 3345 to 138.76.29.7, 5001, updates tableS: 128.119.40.186, 80 D: 138.76.29.7, 5001 33: Reply arrives dest. address: 138.76.29.7, 50014: NAT router changes datagram dest addr from 138.76.29.7, 5001 to 10.0.0.1, 3345
    • 63. Network Layer4-63Chapter 4: Network Layer4. 1 概述 4.2 虚电路和数据报网络 4.3 路由器工作原理 4.4 IP: Internet Protocol 数据报格式 IPv4 编址 ICMP IPv64.5 选路算法 Link state Distance Vector Hierarchical routing 4.6 Internet中的选路 RIP OSPF BGP 4.7 广播和多播
    • 64. Network Layer4-64ICMP: Internet Control Message Protocol用于主机和路由器彼此交互网络层信息 差错报告:目的网络不可达, network, port, protocol 回显echo request/reply (used by ping) network-layer “above” IP: ICMP msgs carried in IP datagrams ICMP message:Type Code description 0 0 echo reply (ping) 3 0 dest. network unreachable 3 1 dest host unreachable 3 2 dest protocol unreachable 3 3 dest port unreachable 3 6 dest network unknown 3 7 dest host unknown 4 0 source quench (congestion control - not used) 8 0 echo request (ping) 9 0 route advertisement 10 0 router discovery 11 0 TTL expired 12 0 bad IP header
    • 65. Network Layer4-65ICMP 报文的格式 首 部ICMP 报文0数 据 部 分检验和类型代码(这 4 个字节取决于 ICMP 报文的类型)81631IP 数据报前 4 个字节 都是一样的ICMP 的数据部分(长度取决于类型)
    • 66. Network Layer4-66ICMP 差错报告报文共有 5 种 终点不可达 源站抑制 时间超过 参数问题 改变路由(重定向)
    • 67. Network Layer4-67ICMP 差错报告报文的数据字段的内容 首部IP 数据报ICMP 的 前 8 字节装入 ICMP 报文的 IP 数据报IP 数据报 首部ICMP 差错报告报文8 字节收到的 IP 数据报IP 数据报 首部8 字节ICMP 差错报告报文IP 数据报的数据字段
    • 68. Network Layer4-68不应发送 ICMP 差错报告报文 的几种情况 对 ICMP 差错报告报文不再发送 ICMP 差错报告报文。 对第一个分片的数据报片的所有后续数据报片都不发送 ICMP 差错报告报文。 对具有多播地址的数据报都不发送 ICMP 差错报告报文。 对具有特殊地址(如127.0.0.0或0.0.0.0)的数据报不发送 ICMP 差错报告报文。
    • 69. Network Layer4-69ICMP 询问报文有四种 回送请求和回答报文 时间戳请求和回答报文 掩码地址请求和回答报文 路由器询问和通告报文
    • 70. Network Layer4-70PING (Packet InterNet Groper) PING 用来测试两个主机之间的连通性。 PING 使用了 ICMP 回送请求与回送回答报文。 PING 是应用层直接使用网络层 ICMP 的例子,它没有通过运输层的 TCP 或UDP。
    • 71. Network Layer4-71Traceroute and ICMP源主机中的Traceroute向目的主机发送一系列普通的IP数据报 First has TTL =1 Second has TTL=2, etc. Unlikely port number 当第n个数据包到达第n个路由器,第n台路由器观察到这个数据报的TTL正好终止: 路由器将丢弃该数据报 发送一个ICMP告警报文给源主机(类型11编码0) 该告警报文包含有路由器的名字与IP地址当ICMP 消息到达,源主机计算RTT Traceroute 尝试 3次 Stopping criterion 数据报之一最终到达目的主机 目的主机将向源主机发送一个端口不可达的ICMP报文(type 3, code 3) 当源主机收到这个特别的ICMP报文时,它便知道了它不需要再发送另外的探测分组
    • 72. Network Layer4-72路由器 R1路由器 R2SD源端主机S目的主机D路由器 R3路由器 R4路由器 R5timeouttimeouttimeout
    • 73. Network Layer4-73Chapter 4: Network Layer4. 1 概述 4.2 虚电路和数据报网络 4.3 路由器工作原理 4.4 IP: Internet Protocol 数据报格式 IPv4 编址 ICMP IPv64.5 选路算法 Link state Distance Vector Hierarchical routing 4.6 Internet中的选路 RIP OSPF BGP 4.7 广播和多播
    • 74. Network Layer4-74Chapter 4: Network Layer4. 1 概述 4.2 虚电路和数据报网络 4.3 路由器工作原理 4.4 IP: Internet Protocol 数据报格式 IPv4 编址 ICMP4.5 选路算法 Link state Distance Vector Hierarchical routing 4.6 Internet中的选路 RIP OSPF BGP
    • 75. Network Layer4-75Interplay between routing and forwarding转发功能Forwarding function: 路由算法Routing algorithm: 在网络路由器上工作 选路算法在网络路由器中运行、交换和计算,以配置这些转发表的信息. Purpose:选路的工作是从发送方到接收方在通过路由器的网络中确定好路径(即路由)。
    • 76. Network Layer4-761230111value in arriving packet’s headerrouting algorithmlocal forwarding tableheader valueoutput link0100 0101 0111 10013 2 2 1Interplay between routing and forwarding
    • 77. Network Layer4-77uyxwvz2213112535Graph: G = (N,E) N = set of routers = { u, v, w, x, y, z } E = set of links ={ (u,v), (u,x), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z) }抽象图模型Graph abstractionRemark: Graph abstraction is useful in other network contexts Example: P2P, where N is set of peers and E is set of TCP connections在网络层选路的环境中,图中的节点表示路由器,这是做出分组转发决定的点;连接节点的边表示路由器之间的物理链路。(无向图)
    • 78. Network Layer4-78Graph abstraction:费用costsuyxwvz2213112535 if (x,y)belongs to E,a node y is said to be a neighbor of node x. c(x,x’) = cost of link (x,x’) - e.g., c(w,z) = c(z,w) =5 cost could always be 1, or inversely related to bandwidth, or inversely related to congestionCost of path (x1, x2, x3,…, xp) = c(x1,x2) + c(x2,x3) + … + c(xp-1,xp) Question: What’s the least-cost path between u and z ?Routing algorithm: algorithm that finds least-cost path
    • 79. Network Layer4-79路由算法分类全局性还是分布式来区分? Global: 用完整的、全局性的网络知识来计算从源到目的之间的最低费用路径 “link state” algorithms Decentralized: algorithm)以迭代的、分布式的方式计算出最低费用路径。 通过迭代计算过程并与相邻节点(即与该节点相连链路的另一端的节点)交换信息,一个节点逐渐计算出到达某目的节点或一组目的节点的最低费用路径 “distance vector” algorithms静态或动态路由? Static: 随着时间的推移,路由的变化是非常缓慢的 Dynamic: 在网络流量负载或拓扑发生变化时改变选路路径 周期更新 直接地响应拓扑或链路费用的变化
    • 80. Network Layer4-80Chapter 4: Network Layer4. 1 概述 4.2 虚电路和数据报网络 4.3 路由器工作原理 4.4 IP: Internet Protocol 数据报格式 IPv4 编址 ICMP IPv64.5 选路算法 Link state Distance Vector Hierarchical routing 4.6 Internet中的选路 RIP OSPF BGP 4.7 广播和多播
    • 81. Network Layer4-81A Link-State Routing AlgorithmDijkstra’s algorithm 网络拓扑和所有的链路费用都是已知的,可用作LS算法的输入 由链路状态广播“link state broadcast” 算法完成 所有节点具有了该网络的同一个完整的视图 计算从某节点(源节点,我们称之为u)到网络中所有其他节点的最低费用路径。 给出这个节点的转发表 iterative:经算法的第k次迭代后,可知道到k个目的节点的最低费用路径Notation: c(x,y): link cost from node x to y; = ∞ if not direct neighbors D(v):随着算法进行本次迭代,从源节点到目的节点v的最低费用路径的费用 p(v):从源节点到目的节点v沿着当前最低费用路径的前一节点(v的邻居) N':节点子集;如果从源节点到目的节点v的最低费用路径已确知,v在N'中
    • 82. Network Layer4-82Dijsktra’s Algorithm1 Initialization: 2 N' = {u} 3 for all nodes v 4 if v adjacent to u 5 then D(v) = c(u,v) 6 else D(v) = ∞ 7 8 Loop 9 find w not in N' such that D(w) is a minimum 10 add w to N' 11 update D(v) for all v adjacent to w and not in N' : 12 D(v) = min( D(v), D(w) + c(w,v) ) 13 /* new cost to v is either old cost to v or known 14 shortest path cost to w plus cost from w to v */ 15 until all nodes in N'
    • 83. Network Layer4-83Dijkstra’s algorithm: exampleStep 0 1 2 3 4 5N' u ux uxy uxyv uxyvw uxyvwzD(v),p(v) 2,u 2,u 2,uD(w),p(w) 5,u 4,x 3,y 3,yD(x),p(x) 1,uD(y),p(y) ∞ 2,xD(z),p(z) ∞ ∞ 4,y 4,y 4,yuyxwvz2213112535
    • 84. Network Layer4-84Chapter 4: Network Layer4. 1 概述 4.2 虚电路和数据报网络 4.3 路由器工作原理 4.4 IP: Internet Protocol 数据报格式 IPv4 编址 ICMP IPv64.5 选路算法 Link state Distance Vector Hierarchical routing 4.6 Internet中的选路 RIP OSPF BGP 4.7 广播和多播
    • 85. Network Layer4-85Distance Vector Algorithm (1)距离向量算法Distance Vector Algorithm 迭代的、异步的和分布式 分布式的,是因为每个节点都要从一个或多个直接相连的邻居接收某些信息,执行计算,然后将计算结果发回给邻居 迭代的,是因为此过程一直要持续到邻居之间没有更多的信息要交换为止 异步的,是因为它不要求所有节点相互之间步伐一致地操作
    • 86. Network Layer4-86Distance Vector Algorithm (1)Bellman-Ford Equation Define dx(y) := cost of least-cost path from x to y Then dx(y) = minv {c(x,v) + dv(y) } where minv is taken over all neighbors of x
    • 87. Network Layer4-87Bellman-Ford example (2)uyxwvz2213112535Clearly, dv(z) = 5, dx(z) = 3, dw(z) = 3du(z) = min { c(u,v) + dv(z), c(u,x) + dx(z), c(u,w) + dw(z) } = min {2 + 5, 1 + 3, 5 + 3} = 4Node that achieves minimum is next hop in shortest path ➜ forwarding tableB-F equation says:
    • 88. Network Layer4-88Distance vector algorithm (4)Basic idea: 每个节点x以Dx(y)开始,对N中的所有节点估计从它自己到节点y的最低费用路径的费用 当节点x从它的任何一个邻居v接收到一个新距离向量时,它保存v的距离向量,然后使用Bellman-Ford方程更新它自己的距离向量 Dx(y) ← minv{c(x,v) + Dv(y)} for each node y ∊ N只要所有的节点继续以异步方式交换它们的距离向量,每个费用估计Dx(y)就收敛到dx(y),dx(y)是从节点x到节点y的实际最低费用路径的费用
    • 89. Network Layer4-89Distance Vector Algorithm (5)迭代、异步: 每次本地迭代发起由: 本地链路费用变化 DV 从邻居得到更新信息 分布式: 仅在DV变化时,每个节点通知邻居 邻居通知他们的邻居 wait for (change in local link cost of msg from neighbor) recompute estimates if DV to any dest has changed, notify neighbors Each node:
    • 90. Network Layer4-901 1  2 1  3 1 FEDCBA5 1  6 1 2 1  5 1 3 1  4 1 4 1  6 1 1 1  5 1 一开始,各路由表只有到相邻路由器的信息网 3网 2网 4网 6网 5网 1“4”表示“从本路由器到网 4”“1”表示“距离是 1”“”表示“直接交付”
    • 91. Network Layer4-911 1  2 1  3 1 FEDCBA5 1  6 1 2 1  5 1 3 1  4 1 4 1  6 1 1 1  5 1 路由器 B 收到相邻路由器 A 和 C 的路由表网 3网 2网 4网 6网 5网 11 1  2 1  3 1 4 1  6 1 1 2 A 2 2 A 3 1  4 1  6 2 C更新后A 说:“我到网 1 的距离是 1。” 因此 B 现在也可以到网 1, 距离是 2,经过 A。”
    • 92. Network Layer4-921 1  2 1  3 1 FEDCBA5 1  6 1 2 1  5 1 3 1  4 1 4 1  6 1 1 1  5 1 路由器 B 收到相邻路由器 A 和 C 的路由表网 3网 2网 4网 6网 5网 11 1  2 1  3 1 4 1  6 1 1 2 A 2 2 A 3 1  4 1  6 2 C更新后A 说:“我到网 2 的距离是 1。” 因此 B 现在也可以到网 2, 距离是 2,经过 A。”
    • 93. Network Layer4-931 1  2 1  3 1 FEDCBA5 1  6 1 2 1  5 1 3 1  4 1 4 1  6 1 1 1  5 1 路由器 B 收到相邻路由器 A 和 C 的路由表网 3网 2网 4网 6网 5网 11 1  2 1  3 1 4 1  6 1 1 2 A 2 2 A 3 1  4 1  6 2 C更新后A 说:“我到网 3 的距离是 1。” 但 B 没有必要绕道经过路由器 A 再到达网 3,因此这一项目不变。
    • 94. Network Layer4-941 1  2 1  3 1 FEDCBA5 1  6 1 2 1  5 1 3 1  4 1 4 1  6 1 1 1  5 1 路由器 B 收到相邻路由器 A 和 C 的路由表网 3网 2网 4网 6网 5网 11 1  2 1  3 1 4 1  6 1 1 2 A 2 2 A 3 1  4 1  6 2 C更新后C 说:“我到网 4 的距离是 1。” 但 B 没有必要绕道经过路由器 C 再到达网 4,因此这一项目不变。
    • 95. Network Layer4-951 1  2 1  3 1 FEDCBA5 1  6 1 2 1  5 1 3 1  4 1 4 1  6 1 1 1  5 1 路由器 B 收到相邻路由器 A 和 C 的路由表网 3网 2网 4网 6网 5网 11 1  2 1  3 1 4 1  6 1 1 2 A 2 2 A 3 1  4 1  6 2 C更新后C 说:“我到网 6 的距离是 1。” 因此 B 现在也可以到网 6, 距离是 2,经过 C。”
    • 96. Network Layer4-96最终所有的路由器的路由表都更新了FEDCBA1 1  2 1  3 1  4 2 B 5 2 E 6 3 B1 1  2 2 A 3 2 A 4 3 A 5 1  6 2 F1 2 E 2 2 D 3 3 C 4 2 C 5 1  6 1 1 3 B 2 3 B 3 2 B 4 1  5 2 F 6 1 网 2网 6网 5网 1网 3网 41 2 A 2 1  3 2 A 4 3 A 5 1  6 2 F1 2 A 2 2 A 3 1  4 1  5 3 C 6 2 C
    • 97. Network Layer4-97Chapter 4: Network Layer4. 1 概述 4.2 虚电路和数据报网络 4.3 路由器工作原理 4.4 IP: Internet Protocol 数据报格式 IPv4 编址 ICMP IPv64.5 选路算法 Link state Distance Vector Hierarchical routing 4.6 Internet中的选路 RIP OSPF BGP 4.7 广播和多播
    • 98. Network Layer4-98层次选路Hierarchical Routing规模: with 200 million destinations: 选路信息显然需要巨大容量的内存! 所有路由器中要求的广播LS更新的开销将导致没有剩余的带宽供发送数据分组使用! 管理自治 internet = network of networks 一个组织应当能够按自己的愿望运行和管理其网络,还要能将其网络与其他外部网络连接 Our routing study thus far - idealization all routers identical network “flat” … not true in practice
    • 99. Network Layer4-99Hierarchical Routing通过将路由器组织进自治系统,“autonomous systems” (AS) AS: 在相同的AS内的路由器都全部运行同样的选路算法 在一个自治系统内运行的选路算法叫做自治系统内部选路协议“intra-AS” routing protocol 不同 AS 可以运行不同 intra-AS routing protocol网关路由器Gateway router 在一个AS内的一台或多台路由器将有另外的任务,来负责向本AS之外的目的地转发分组
    • 100. Network Layer4-1003b1d3a1c2aAS3AS1AS21a2c2b1bIntra-AS Routing algorithmInter-AS Routing algorithmForwarding table3cInterconnected ASes每台路由器接收来自一个AS内部选路协议和一个AS间选路协议的信息,并使用来自这两个协议的信息配置其转发表 Intra-AS sets entries for internal dests Inter-AS & Intra-As sets entries for external dests

    该用户的其他文档