第1页：第4章：网络层
第4章：网络层
- understand principles behind network layer services:
- network layer service models
- forwarding versus routing
- how a router works
- routing (path selection)
- dealing with scale
- advanced topics: IPv 6, mobility
- instantiation, implementation in the Internet
第2页：第4章：网络层
第4章：网络层
- 4. 1 Introduction
- 4.2 Virtual circuit anddatagram networks
- 4.3 What’s inside arouter
- 4.4 IP: Internet Protocol
- Datagram format
- IPv 4 addressing
- ICMP
- IPv 6
- 4.5 Routing algorithms
- Link state
- Distance Vector
- Hierarchical routing
- 4.6 Routing in the Internet
- 4.7 Broadcast andmulticast routing
第3页：网络层
网络层
- transport segment fromsending to receiving host
- on sending sideencapsulates segmentsinto datagrams
- on rcving side, delivers segments to transport layer
- network layer protocolsineveryhost, router
- router examines header fields in all IP datagrams passing through itapplication transport networkdata link physical application transport networkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysical
第4页：Two Key Network-Layer Functions
Two Key Network-Layer Functions
- forwarding:movepackets from router’sinput to appropriate router output
- routing:determine route taken bypackets from sourceto dest.
- routing algorithms analogy:
- routing:process ofplanning trip fromsource to dest
- forwarding:processof getting through single interchange
第5页：网络层概述与服务模型（示意图）
网络层概述与服务模型（示意图）
value in arrivingpacket’s headerr outing algorithm local forwarding table header value output link 01000101011110013221 Interplay between routing and forwarding
第6页：连接建立
连接建立
- 3 rdimportant function insomenetwork architectures:
- before datagrams flow, two end hostsandinterveningrouters establish virtual connection
- network vs transport layer connection service:
- network:between two hosts (may also involveinervening routers in case of VCs)
- transport:between two processes
第7页：网络服务模型
网络服务模型
- guaranteed delivery
- guaranteed deliverywith less than 40 msecdelay Example services for aflow of datagrams:
- in-order datagram delivery
- guaranteed minimum bandwidth to flow
- restrictions onchanges in inter-packet spacing
第8页：Network layer service models:Network
Network layer service models:Network
Network layer service models:Network Architecture Internet ATMATMATMATMService Modelbest effort CBRVBRABRUBRBandwidthnoneconstantrateguaranteedrateguaranteedminimumnone Lossnoyesyesnono Ordernoyesyesyesyes Timingnoyesyesnono Congestion feedbackno (inferredvia loss)nocongestionnocongestionyesno Guarantees ?
第9页：第4章：网络层
第4章：网络层
- 4. 1 Introduction
- 4.2 Virtual circuit anddatagram networks
- 4.3 What’s inside arouter
- 4.4 IP: Internet Protocol
- Datagram format
- IPv 4 addressing
- ICMP
- IPv 6
- 4.5 Routing algorithms
- Link state
- Distance Vector
- Hierarchical routing
- 4.6 Routing in the Internet
- 4.7 Broadcast andmulticast routing
第10页：Network layer connection
Network layer connection
- datagram network provides network-layer connectionless service
- VC network provides network-layer connection service
- analogous to the transport-layer services,but:
- service:host-to-host
- no choice:network provides one or the other
- implementation:in network core
第11页：Virtual circuits
Virtual circuits
- call setup, teardown for each callbeforedata can flow
- each packet carries VC identifier (not destination hostad dress)
- every router on source-dest path maintains “state” foreach passing connection
- link, router resources (bandwidth, buffers) may beallocatedto VC (dedicated resources = predictable service)“source-to-dest path behaves much like telephone circuit”
- performance-wise
- network actions along source-to-dest path
第12页：VC implementationa VC consists of:1
VC implementationa VC consists of:1
- packet belonging to VC carries VC number(rather than dest address)
- VC number can be changed on each link.
- New VC number comes from forwarding table
第13页：Forwarding table 122232123VC number
Forwarding table 122232123VC number
Forwarding table 122232123VC number interface number Incoming interface Incoming VC # Outgoing interface Outgoing VC #1 12 3 222 63 1 183 7 2 171 97 3 87… … … …Forwarding table innorthwest router:Routers maintain connection state information!
第14页：Virtual circuits: signal
Virtual circuits: signal
- used to setup, maintain teardown VC
- used in ATM, frame-relay, X.25
- not used in today’s Internet application transport networkdata link physical application transport networkdata linkphysical 1. Initiate call 2. incoming call 3. Accept call 4. Call connected 5. Data flow begins 6. Receive data
第15页：数据报网络
数据报网络
- no call setup at network layer
- routers: no state about end-to-end connections
- no network-level concept of “connection”
- packets forwarded using destination host address
- packets between same source-dest pair may takedifferent paths application transport networkdata link physical application transport networkdata linkphysical 1. Send data 2. Receive data
第16页：转发表目的地址 Range 链路
转发表目的地址 Range 链路
Forwarding table Destination Address Range Link Interface 11001000000101110001000000000000 through 01100100000010111000101111111111111001000000101110001100000000000 through 11100100000010111000110001111111111001000000101110001100100000000 through 211001000000101110001111111111111 otherwise 34 billion possible entries
第17页：Longest prefix match
Longest prefix match
Longest prefix matching Prefix Match Link Interface 110010000001011100010011001000000101110001100011100100000010111000112 otherwise 3DA: 11001000 00010111 00011000 10101010 Examples DA: 11001000 00010111 00010110 10100001 Which interface?Which interface?
第18页：Datagram or VC network: why?Internet
Datagram or VC network: why?Internet
- data exchange among computers
- “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 difficult ATM (VC)
- evolved from telephony
- human conversation:
- strict timing, reliability requirements
- need for guaranteed service
- “dumb” end systems
- telephones
- complexity inside network
第19页：第4章：网络层
第4章：网络层
- 4. 1 Introduction
- 4.2 Virtual circuit anddatagram networks
- 4.3 What’s inside arouter
- 4.4 IP: Internet Protocol
- Datagram format
- IPv 4 addressing
- ICMP
- IPv 6
- 4.5 Routing algorithms
- Link state
- Distance Vector
- Hierarchical routing
- 4.6 Routing in the Internet
- 4.7 Broadcast andmulticast routing
第20页：路由器体系结构概述两大关键路由器
路由器体系结构概述两大关键路由器
- run routing algorithms/protocol (RIP, OSPF, BGP)
- forwarding datagrams from incoming to outgoing link
第21页：Input Port Functions Decentralized
Input Port Functions Decentralized
- given datagram dest., lookup output portusing forwarding table in input portmemory
- goal: complete input port processing at‘line speed’
- queuing: if datagrams arrive faster thanforwarding rate into switch fabric Physical layer:bit-level reception Data link layer:e.g., Ethernetsee chapter 5
第22页：Three types switching fabrics
Three types switching fabrics
Three types of switching fabrics
第23页：Switching Via Memory First generation
Switching Via Memory First generation
- traditional computers with switching under direct control of CPU
- packet copied to system’s memory
- speed limited by memory bandwidth (2 buscrossings per datagram)Input Port Output Port Memory System Bus
第24页：Switching Via Bus
Switching Via Bus
- datagram from input port memoryto output port memory via a sharedbus
- bus contention:switching speed limited by bus bandwidth
- 32 Gbps bus, Cisco 5600: sufficient speed for access and enterprise routers
第25页：Switching Via Interconnection Network
Switching Via Interconnection Network
- overcome bus bandwidth limitations
- Banyan networks, other interconnection netsinitially developed to connect processors inmultiprocessor
- advanced design: fragmenting datagram into fixed length cells, switch cells through the fabric.
- Cisco 12000: switches 60 Gbps through theinterconnection network
第26页：Output Ports
Output Ports
- Buffering required when datagrams arrive fromfabric faster than the transmission rate
- Scheduling discipline chooses among queued datagrams for transmission
第27页：Output port queue
Output port queue
- buffering when arrival rate via switch exceeds output line speed
- queueing (delay) and loss due to output portbuffer overflow!
第28页：如何缓存
如何缓存
- RFC 3439 rule of thumb: average buffering equal to “typical” RTT (say 250 msec) timeslink capacity C
- e.g., C = 10 Gps link: 2.5 Gbit buffer
- Recent recommendation: with Nflows,buffering equal to RTT C. N
第29页：Input Port Queuing
Input Port Queuing
- Fabric slower than input ports combined-> queueingmay occur at input queues
- Head-of-the-Line (HOL) blocking:queued datagramat front of queue prevents others in queue frommoving forward
- queueing delay and loss due to input buffer overflow!
第30页：第4章：网络层
第4章：网络层
- 4. 1 Introduction
- 4.2 Virtual circuit anddatagram networks
- 4.3 What’s inside arouter
- 4.4 IP: Internet Protocol
- Datagram format
- IPv 4 addressing
- ICMP
- IPv 6
- 4.5 Routing algorithms
- Link state
- Distance Vector
- Hierarchical routing
- 4.6 Routing in the Internet
- 4.7 Broadcast andmulticast routing
第31页：因特网网络层转发表
因特网网络层转发表
- path selection
- RIP, OSPF, BGPIP protocol
- addressing conventions
- datagram format
- packet handling conventions ICMP protocol
- error reporting
- router “signaling”Transport layer: TCP, UDPLink layer physical layer Network layer
第32页：第4章：网络层
第4章：网络层
- 4. 1 Introduction
- 4.2 Virtual circuit anddatagram networks
- 4.3 What’s inside arouter
- 4.4 IP: Internet Protocol
- Datagram format
- IPv 4 addressing
- ICMP
- IPv 6
- 4.5 Routing algorithms
- Link state
- Distance Vector
- Hierarchical routing
- 4.6 Routing in the Internet
- 4.7 Broadcast andmulticast routing
第33页：IP 数据报格式
IP 数据报格式
- 20 bytes of TCP
- 20 bytes of IP
- = 40 bytes + applayer overhead
第34页：IP 分片 & 重组
IP 分片 & 重组
- network links have MTU(max.transfer size)-largest possible link-level frame.
- different link types,different MTUs
- large IP datagram divided(“fragmented”) within net
- one datagram becomes several datagrams
- “reassembled” only at final destination
- IP header bits used toidentify, order related fragments fragmentation:in:one large datagramout:3 smaller datagrams reassembly
第35页：IP 分片和重组标识
IP 分片和重组标识
- 4000 bytedatagram
- MTU = 1500 bytes 1480 bytes indata field offset =1480/8
第36页：第4章：网络层
第4章：网络层
- 4. 1 Introduction
- 4.2 Virtual circuit anddatagram networks
- 4.3 What’s inside arouter
- 4.4 IP: Internet Protocol
- Datagram format
- IPv 4 addressing
- ICMP
- IPv 6
- 4.5 Routing algorithms
- Link state
- Distance Vector
- Hierarchical routing
- 4.6 Routing in the Internet
- 4.7 Broadcast andmulticast routing
第37页：IP 编址概述
IP 编址概述
- IP address:32-bitidentifier for host,router interface
- interface:connection between host/routerand physical link
- router’s typically havemultiple interfaces
- host typically has oneinterface
- IP addresses associated with eachinterface 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
第38页：子网
子网
- IP address:
- subnet part (highorder bits)
- host part (low orderbits)
- What’s a subnet ?
- device interfaces withsame subnet part of IPaddress
- can physically reacheach other without inter vening router 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.27 network consisting of 3 subnetssubnet
第39页：Subnets 223.1.1.0/24223.1.2.0/24223.1
Subnets 223.1.1.0/24223.1.2.0/24223.1
- To determine thesubnets, detach eachinterface from itshost or router,creating islands ofisolated networks. Each isolated networkis called asubnet. Subnet mask: /24
第40页：Subnets many?223.1.1.1223.1.1.3223.1
Subnets many?223.1.1.1223.1.1.3223.1
Subnets How 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
第41页：IP addressing: CID
IP addressing: CID
- subnet portion of address of arbitrary length
- address format:a.b.c.d/x, where x is # bits insubnet portion of address 11001000 0001011100010000 00000000 subnetparthostpart 200.23.16.0/23
第42页：IP addresses: get one?Q:How
IP addresses: get one?Q:How
- 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:dynamically get address from as server
第43页：DHCP: Dynamic Host Configuration
DHCP: Dynamic Host Configuration
- host broadcasts “DHCP discover” msg
- DHCP server responds with “DHCP offer” msg
- host requests IP address: “DHCP request” msg
- DHCP server sends address: “DHCP ack” msg
第44页：DHCP client-server scenario
DHCP client-server scenario
DHCP client-server scenario 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.27ABEDHCPserverarriving DHCPclientneedsaddress in thisnetwork
第45页：DHCP client-server scenario DHCP
DHCP client-server scenario DHCP
DHCP client-server scenario DHCP server: 223.1.2.5 arrivingclienttime DHCP 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 secs DHCP requestsrc: 0.0.0.0, 68 dest:: 255.255.255.255, 67 yiaddrr: 223.1.2.4 transaction ID: 655 Lifetime: 3600 secs DHCP ACKsrc: 223.1.2.5, 67 dest: 255.255.255.255, 68 yiaddrr: 223.1.2.4 transaction ID: 655 Lifetime: 3600 secs
第46页：IP addresses: get one?Q:How
IP addresses: get one?Q:How
IP addresses: how to get one?Q:How doesnetworkget subnet part of IPaddr?A:gets allocated portion of its provider ISP’saddress space ISP's block 11001000 00010111 00010000 00000000 200.23.16.0/20 Organization 011001000 00010111 00010000 00000000 200.23.16.0/23 Organization 111001000 00010111 00010010 00000000 200.23.18.0/23 Organization 211001000 00010111 00010100 00000000 200.23.20.0/23... ….. …. …. Organization 711001000 00010111 00011110 00000000 200.23.30.0/23
第47页：Hierarchical addressing: route
Hierarchical addressing: route
Hierarchical addressing: route aggregation“Send me anythingwith addresses beginning 200.23.16.0/20”200.23.16.0/23200.23.18.0/23200.23.30.0/23 Fly-By-Night-ISPOrganization 0 Organization 7 Internet Organization 1ISPs-R-Us“Send me anythingwith addresses beginning 199.31.0.0/16”200.23.20.0/23 Organization 2...... Hierarchical addressing allows efficient advertisement of routing information:
第48页：层次编址补充 specific 路径
层次编址补充 specific 路径
Hierarchical addressing: more specific routes ISPs-R-Us has a more specific route to Organization 1“Send me anythingwith addresses beginning 200.23.16.0/20”200.23.16.0/23200.23.18.0/23200.23.30.0/23 Fly-By-Night-ISPOrganization 0 Organization 7 Internet Organization 1ISPs-R-Us“Send me anythingwith addresses beginning 199.31.0.0/16 or 200.23.18.0/23”200.23.20.0/23 Organization 2......
第49页：IP addressing: last word... Q:How
IP addressing: last word... Q:How
- allocates addresses
- manages DNS
- assigns domain names, resolves disputes
第50页：NAT: Network Address Translation 10.0
NAT: Network Address Translation 10.0
NAT: Network Address Translation 10.0.0.110.0.0.210.0.0.310.0.0.4138.76.29.7 local network(e.g., home network)10.0.0/24 rest of Internet Datagrams with source ordestination in this networkhave 10.0.0/24 address forsource, destination (as usual)Alldatagramsleavinglocalnetwork havesamesingle source NAT IP address: 138.76.29.7,different source port numbers
第51页：NAT 网络地址转换
NAT 网络地址转换
- Motivation:local network uses just one IP address asfar as outside world is concerned:
- range of addresses not needed from ISP: just one IPaddress for all devices
- can change addresses of devices in local network without notifying outside world
- can change ISP without changing addresses ofdevices in local network
- devices inside local net not explicitly addressable,visible by outside world (a security plus).
第52页：NAT 网络地址转换实现
NAT 网络地址转换实现
- outgoing datagrams:replace(source IP address, port#) of every outgoing datagram to (NAT IP address,new port #). . . remote clients/servers will respond using (NATIP address, new port #) as destination addr.
- remember (in NAT translation table)every (source IP address, port #) to (NAT IP address, new port #)translation pair
- incoming datagrams:replace(NAT IP address, newport #) in dest fields of every incoming datagramwith corresponding (source IP address, port #)stored in NAT table
第53页：NAT: Network Address Translation 10.0
NAT: Network Address Translation 10.0
NAT: Network Address Translation 10.0.0.110.0.0.210.0.0.3S: 10.0.0.1, 3345D: 128.119.40.186, 80110.0.0.4138.76.29.71:host 10.0.0.1 sends datagram to 128.119.40.186, 80NAT translation table WAN side addr LAN side addr 138.76.29.7, 5001 10.0.0.1, 3345…… ……S: 128.119.40.186, 80D: 10.0.0.1, 33454S: 138.76.29.7, 5001D: 128.119.40.186, 8022:NAT router changes datagram source addr from 10.0.0.1, 3345 to 138.76.29.7, 5001,updates table S: 128.119.40.186, 80D: 138.76.29.7, 500133:Reply arrivesdest. address:138.76.29.7, 50014:NAT router changes datagramdest addr from 138.76.29.7, 5001 to 10.0.0.1, 3345
第54页：NAT 网络地址转换
NAT 网络地址转换
- 16-bit port-number field:
- 60,000 simultaneous connections with a single LAN-side address!
- NAT is controversial:
- routers should only process up to layer 3
- violates end-to-end argument
- NAT possibility must be taken into account by appdesigners, eg, P2P applications
- address shortage should instead be solved by IPv 6
第55页：NAT traversal problem
NAT traversal problem
- client want to connect toserver with address 10.0.0.1
- server address 10.0.0.1 localto LAN (client can’t use it asdestination addr)
- only one externally visible NATted address: 138.76.29.7
- solution 1: statically configure NAT to forwardin coming connectionre quests at given port toserver
- e.g., (123.76.29.7, port 2500)always forwarded to 10.0.0.1 port 2500010.0.0.110.0.0.4NATrouter 138.76.29.7 Client?
第56页：NAT traversal problem
NAT traversal problem
- solution 2: Universal Plug and Play (UPn P) Internet Gateway Device (IGD) Protocol. Allows NATted host to:
- learn public IP address(138.76.29.7)
- enumerate existing portmappings
- add/remove port mappings(with lease times)i.e., automate static NAT portmap configuration 10.0.0.110.0.0.4NATrouter 138.76.29.7IGD
第57页：NAT traversal problem
NAT traversal problem
- solution 3: relaying (used in Skype)
- NATed server establishes connection to relay
- External client connects to relay
- relay bridges packets between to connections 10.0.0.1NATrouter 138.76.29.7 Client 1.connection torelay initiatedby NATted host 2.connection torelay initiatedby client 3.relaying established
第58页：第4章：网络层
第4章：网络层
- 4. 1 Introduction
- 4.2 Virtual circuit anddatagram networks
- 4.3 What’s inside arouter
- 4.4 IP: Internet Protocol
- Datagram format
- IPv 4 addressing
- ICMP
- IPv 6
- 4.5 Routing algorithms
- Link state
- Distance Vector
- Hierarchical routing
- 4.6 Routing in the Internet
- 4.7 Broadcast andmulticast routing
第59页：ICMP 因特网控制报文协议
ICMP 因特网控制报文协议
- used by hosts & routers tocommunicate network-level information
- error reporting:unreachable host, network,port, protocol
- echo request/reply (usedby ping)
- network-layer “above” IP:
- ICMP msgs carried in IPdatagrams
- ICMP message:type, code plusfirst 8 bytes of IP datagramcausing error 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
第60页：Trace route and ICMP
Trace route and ICMP
- Source sends series of UDP segments to dest
- First has TTL =1
- Second has TTL=2, etc.
- Unlikely port number
- When nth datagram arrivesto nth router:
- Router discards datagram
- And sends to source an ICMP message (type 11,code 0)
- Message includes name ofrouter& IP address
- When ICMP message arrives, source calculates RTT
- Trace route does this 3 times Stopping criterion
- UDP segment eventually arrives at destination host
- Destination returns ICMP“host unreachable” packet(type 3, code 3)
- When source gets this ICMP, stops.
第61页：第4章：网络层
第4章：网络层
- 4. 1 Introduction
- 4.2 Virtual circuit anddatagram networks
- 4.3 What’s inside arouter
- 4.4 IP: Internet Protocol
- Datagram format
- IPv 4 addressing
- ICMP
- IPv 6
- 4.5 Routing algorithms
- Link state
- Distance Vector
- Hierarchical routing
- 4.6 Routing in the Internet
- 4.7 Broadcast andmulticast routing
第62页：IPv6
IPv6
- Initial motivation:32-bit address space soonto be completely allocated.
- Additional motivation:
- header format helps speed processing/forwarding
- header changes to facilitate Qo SIPv 6 datagram format:
- fixed-length 40 byte header
- no fragmentation allowed
第63页：IPv 6 Header (Cont)Priority:identify
IPv 6 Header (Cont)Priority:identify
IPv 6 Header (Cont)Priority:identify priority among datagrams in flow Flow Label:identify datagrams in same “flow.”(concept of“flow” not well defined). Next header:identify upper layer protocol for data
第64页：Other Changes from IPv 4
Other Changes from IPv 4
- Checksum:removed entirely to reduce processing time at each hop
- Options:allowed, but outside of header,indicated by “Next Header” field
- ICMPv 6:new version of ICMP
- additional message types, e.g. “Packet Too Big”
- multicast group management functions
第65页：Transition From IPv 4 IPv
Transition From IPv 4 IPv
- Not all routers can be upgraded simultaneous
- no “flag days”
- How will the network operate with mixed IPv 4 and IPv 6 routers?
- Tunneling:IPv 6 carried as payload in IPv 4 datagram among IPv 4 routers
第66页：IPv6隧道：逻辑视图
IPv6隧道：逻辑视图
Tunneling ABEFIPv 6IPv 6IPv 6IPv 6 tunnel Logical view:Physical view:ABEFIPv 6IPv 6IPv 6IPv 6IPv 4IPv 4
第67页：IPv6隧道：物理视图
IPv6隧道：物理视图
Tunneling ABEFIPv 6IPv 6IPv 6IPv 6 tunnel Logical view:Physical view:ABEFIPv 6IPv 6IPv 6IPv 6CDIPv 4IPv 4 Flow: XSrc: ADest: Fdata Flow: XSrc: ADest: Fdata Flow: XSrc: ADest: Fdata Src:BDest: EFlow: XSrc: ADest: Fdata Src:BDest: EA-to-B:IPv 6E-to-F:IPv 6B-to-C:IPv 6 inside IPv 4B-to-C:IPv 6 inside IPv 4
第68页：第4章：网络层
第4章：网络层
- 4. 1 Introduction
- 4.2 Virtual circuit anddatagram networks
- 4.3 What’s inside arouter
- 4.4 IP: Internet Protocol
- Datagram format
- IPv 4 addressing
- ICMP
- IPv 6
- 4.5 Routing algorithms
- Link state
- Distance Vector
- Hierarchical routing
- 4.6 Routing in the Internet
- 4.7 Broadcast andmulticast routing
第69页：路由算法与图抽象（示意图）
路由算法与图抽象（示意图）
value in arrivingpacket’s headerr outing algorithm local forwarding table header value output link 01000101011110013221 Interplay between routing, forwarding
第70页：uyxwvz 2213112535 Graph: G = (N
uyxwvz 2213112535 Graph: G = (N
uyxwvz 2213112535 Graph: 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 abstraction Remark: Graph abstraction is useful in other network contexts Example: P2P, where N is set of peers and E is set of TCP connections
第71页：Graph abstraction: cost
Graph abstraction: cost
- c(x,x’) = cost of link (x,x’)-e.g., c(w,z) = 5
- cost could always be 1, orinversely related to bandwidth,or inversely related tocongestion Cost of path (x 1, x 2, x 3,…, xp) = c(x 1,x 2) + c(x 2,x 3) + … + c(xp-1,xp)Question: What’s the least-cost path between u and z ?Routing algorithm: algorithm that finds least-cost path
第72页：路由算法分类全局
路由算法分类全局
- all routers have complete topology, link cost info
- “link state” algorithms Decentralized:
- router knows physically-connected neighbors, linkcosts to neighbors
- iterative process ofcomputation, exchange ofinfo with neighbors
- “distance vector” algorithms Static or dynamic?Static:
- routes change slowlyover time Dynamic:
- routes change morequickly
- periodic update
- in response to linkcost changes
第73页：第4章：网络层
第4章：网络层
- 4. 1 Introduction
- 4.2 Virtual circuit anddatagram networks
- 4.3 What’s inside arouter
- 4.4 IP: Internet Protocol
- Datagram format
- IPv 4 addressing
- ICMP
- IPv 6
- 4.5 Routing algorithms
- Link state
- Distance Vector
- Hierarchical routing
- 4.6 Routing in the Internet
- 4.7 Broadcast andmulticast routing
第74页：A Link-State
A Link-State
- net topology, link costsknown to all nodes
- accomplished via “linkstate broadcast”
- all nodes have same info
- computes least cost pathsfrom one node (‘source”) toall other nodes
- givesforwarding tablefor that node
- iterative: after kiterations, know least costpath to k dest.’s Notation:
- c(x,y):link cost from nodex to y; = ∞ if not direct neighbors
- D(v):current value of costof path from source todest. v
- p(v):predecessor nodealong path from source to v
- N':set of nodes whose least cost path definitively known
第75页：链路状态路由算法（示意图）
链路状态路由算法（示意图）
Dijsktra’s Algorithm 1 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) = ∞78 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' :12D(v) = min( D(v), D(w) + c(w,v) )13 15 until all nodes in N'
第76页：Dijkstra’s algorithm: example Step
Dijkstra’s algorithm: example Step
Dijkstra’s algorithm: example Step 012345N'uuxuxyuxyvuxyvwuxyvwz D(v),p(v)2,u 2,u 2,u D(w),p(w)5,u 4,x 3,y 3,y D(x),p(x)1,u D(y),p(y)∞2,x D(z),p(z)∞∞4,y 4,y 4,yuyxwvz 2213112535
第77页：Dijkstra’s algorithm: example
Dijkstra’s algorithm: example
Dijkstra’s algorithm: example (2)uyxwvz Resulting shortest-path tree from u:vxywz(u,v)(u,x)(u,x)(u,x)(u,x)destinationlink Resulting forwarding table in u:
第78页：Dijkstra’s algorithm, discussion
Dijkstra’s algorithm, discussion
- each iteration: need to check all nodes, w, not in N
- n(n+1)/2 comparisons: O(n 2)
- more efficient implementations possible: O(nlogn)Oscillations possible:
- e.g., link cost = amount of carried traffic ADCB11+ee 0 e 1100ADCB2+e 0001+e 1ADCB02+e 1+e 100ADCB2+e 0 e 01+e 1 initially… recomputer outing… recompute… recompute
第79页：第4章：网络层
第4章：网络层
- 4. 1 Introduction
- 4.2 Virtual circuit anddatagram networks
- 4.3 What’s inside arouter
- 4.4 IP: Internet Protocol
- Datagram format
- IPv 4 addressing
- ICMP
- IPv 6
- 4.5 Routing algorithms
- Link state
- Distance Vector
- Hierarchical routing
- 4.6 Routing in the Internet
- 4.7 Broadcast andmulticast routing
第80页：Distance Vector Algorithm Bellman-Ford
Distance Vector Algorithm Bellman-Ford
Distance Vector Algorithm Bellman-Ford Equation (dynamic programming)Definedx(y) := cost of least-cost path from x to y Thendx(y) = min {c(x,v) + dv(y) }where min is taken over all neighbors v of xv
第81页：Bellman-Ford
Bellman-Ford
Bellman-Ford exampleuyxwvz 2213112535 Clearly, dv(z) = 5, dx(z) = 3, dw(z) = 3 du(z) = min { c(u,v) + dv(z),c(u,x) + dx(z),c(u,w) + dw(z) }= min {2 + 5,1 + 3,5 + 3} = 4 Node that achieves minimum is nexthop in shortest path➜forwarding table B-F equation says:
第82页：距离向量算法
距离向量算法
- Dx(y)= estimate of least cost from x to y
- Node x knows cost to each neighbor v:c(x,v)
- Node x maintains distance vector Dx=[Dx(y): yєN ]
- Node x also maintains its neighbors’distance vectors
- For each neighbor v, x maintains Dv= [Dv(y): yєN ]
第83页：Distance vector algorithm (4)Basic idea
Distance vector algorithm (4)Basic idea
- Each node periodically sends its own distance vector estimate to neighbors
- When a node x receives new DV estimate fromneighbor, it updates its own DV using B-F equation:Dx(y)←minv{c(x,v) + Dv(y)} for each node y∊N
- Under minor, natural conditions, the estimate Dx(y) converge to the actual least costdx(y)
第84页：Distance Vector Algorithm (5)Iterative
Distance Vector Algorithm (5)Iterative
- local link cost change
- DV update message fromneighbor Distributed:
- each node notifiesneighborsonlywhen its DVchanges
- neighbors then notify their neighbors ifnecessarywaitfor (change in local linkcost or msg from neighbor)recompute estimatesif DV to any dest haschanged,notify neighbors Each node:
第85页：x y zxyz 0 2 7∞∞∞∞∞∞from
x y zxyz 0 2 7∞∞∞∞∞∞from
x y zxyz 0 2 7∞∞∞∞∞∞fromcost tofromfromx y zxyz 0 fromcost tox y zxyz∞∞∞∞∞cost tox y zxyz∞∞∞710 cost to∞2 0 1∞ ∞ ∞2 0 17 1 0 timexz 127 ynode x tablenode y tablenode z table Dx(y)=min{c(x,y)+Dy(y),c(x,z)+Dz(y)}=min{2+0,7+1}=2 Dx(z)=min{c(x,y)+Dy(z),c(x,z)+Dz(z)}=min{2+1,7+0}=332
第86页：x y zxyz 0 2 7∞∞∞∞∞∞from
x y zxyz 0 2 7∞∞∞∞∞∞from
x y zxyz 0 2 7∞∞∞∞∞∞fromcost tofromfromx y zxyz 0 2 3 fromcost tox y zxyz 0 2 3 fromcost tox y zxyz∞∞∞∞∞cost tox y zxyz 0 2 7 fromcost tox y zxyz 0 2 3 fromcost tox y zxyz 0 2 3 fromcost tox y zxyz 0 2 7 fromcost tox y zxyz∞∞∞710 cost to∞2 0 1∞ ∞ ∞2 0 17 1 02 0 17 1 02 0 13 1 02 0 13 1 02 0 13 1 02 0 13 1 0 timexz 127 ynode x tablenode y tablenode z table Dx(y)=min{c(x,y)+Dy(y),c(x,z)+Dz(y)}=min{2+0,7+1}=2 Dx(z)=min{c(x,y)+Dy(z),c(x,z)+Dz(z)}=min{2+1,7+0}=3
第87页：距离向量链路代价 changes 链路
距离向量链路代价 changes 链路
- node detects local link cost change
- updates routing info, recalculates distance vector
- if DV changes, notify neighbors“goodnewstravelsfast”xz 1450 y 1 At timet 0,ydetects the link-cost change, updates its DV,and informs its neighbors. At timet 1,zreceives the update fromyand updates its table. It computes a new least cost toxand sends its neighbors its DV. At timet 2,yreceivesz’s update and updates its distance table.y’s least costs do not change and henceydoesnotsend anymessage toz.
第88页：距离向量链路代价 changes 链路
距离向量链路代价 changes 链路
- good news travels fast
- bad news travels slow-“count to infinity” problem!
- 44 iterations before algorithm stabilizes: seetext Poisoned reverse:
- If Z routes through Y toget to X :
- Z tells Y its (Z’s) distanceto X is infinite (so Y won’troute to X via Z)
- will this completely solve count to infinity problem?xz 1450 y 60
第89页：LS 和 DV 算法对比
LS 和 DV 算法对比
- LS:with n nodes, E links, O(n E) msgs sent
- DV:exchange between neighbors only
- convergence time varies Speed of Convergence
- LS:O(n 2) algorithm requires O(n E) msgs
- DV: convergence time varies
- may be routing loops
- count-to-infinity problem Robustness:what happensif router malfunctions?LS:
- node can advertiseincorrectlinkcost
- each node computes onlyitsowntable DV:
- DV node can advertiseincorrectpathcost
- each node’s table used byothers
- error propagate thrunetwork
第90页：第4章：网络层
第4章：网络层
- 4. 1 Introduction
- 4.2 Virtual circuit anddatagram networks
- 4.3 What’s inside arouter
- 4.4 IP: Internet Protocol
- Datagram format
- IPv 4 addressing
- ICMP
- IPv 6
- 4.5 Routing algorithms
- Link state
- Distance Vector
- Hierarchical routing
- 4.6 Routing in the Internet
- 4.7 Broadcast andmulticast routing
第91页：层次路由规模
层次路由规模
- can’t store all dest’s inrouting tables!
- routing table exchange would swamp links!administrative autonomy
- internet = network ofnetworks
- each network admin maywant to control routing in itsown network Our routing study thus far-idealization
- all routers identical
- network “flat”… nottrue in practice
第92页：层次路由
层次路由
- aggregate routers intoregions,“autonomous systems” (AS)
- routers in same AS runsame routing protocol
- “intra-AS” routing protocol
- routers in different AScan run different intra-AS routing protocol Gateway router
- Direct link to router inanother AS
第93页：层次路由（示意图）
层次路由（示意图）
- forwarding table configured by bothintra-and inter-ASrouting algorithm
- intra-AS sets entriesfor internal dests
- inter-AS & Intra-Assets entries forexternal dests
第94页：层次路由中的AS间任务（示意图）
层次路由中的AS间任务（示意图）
- suppose router in AS1 receives datagramdest outside of AS1
- router should forward packet togateway router, butwhich one?AS1 must:1.learn which destsreachable through AS2, which through AS32.propagate this reachability info to allrouters in AS1 Job of inter-AS routing!
第95页：示例 Setting 转发表 路由器
示例 Setting 转发表 路由器
- suppose AS1 learns (via inter-AS protocol) that subnetxreachable via AS3 (gateway 1 c) but not via AS2.
- inter-AS protocol propagates reachability info to allinternal routers.
- router 1 d determines from intra-AS routing info thatits interface Iis on the least cost path to 1 c.
- installs forwarding table entry(x, I)3 b 1 d 3 a 1 c 2 a AS3AS1AS21 a 2 c 2 b 1 b 3 cx…
第96页：路由器1d转发表设置示例
路由器1d转发表设置示例
- now suppose AS1 learns from inter-AS protocol thatsubnetxis reachable from AS3 andfrom AS2.
- to configure forwarding table, router 1 d mustdetermine towards which gateway it should forward packets for destx.
- this is also job of inter-AS routing protocol!3 b 1 d 3 a 1 c 2 a AS3AS1AS21 a 2 c 2 b 1 b 3 cx……
第97页：Learn from inter-ASprotocol that subnetx
Learn from inter-ASprotocol that subnetx
- now suppose AS1 learns from inter-AS protocol thatsubnetxis reachable from AS3 andfrom AS2.
- to configure forwarding table, router 1 d mustdetermine towards which gateway it should forward packets for destx.
- this is also job of inter-AS routing protocol!
- hot potato routing:send packet towards closest oftwo routers.
第98页：第4章：网络层
第4章：网络层
- 4. 1 Introduction
- 4.2 Virtual circuit anddatagram networks
- 4.3 What’s inside arouter
- 4.4 IP: Internet Protocol
- Datagram format
- IPv 4 addressing
- ICMP
- IPv 6
- 4.5 Routing algorithms
- Link state
- Distance Vector
- Hierarchical routing
- 4.6 Routing in the Internet
- 4.7 Broadcast andmulticast routing
第99页：Intra-AS Routing
Intra-AS Routing
- also known as Interior Gateway Protocols (IGP)
- most common Intra-AS routing protocols:
- RIP: Routing Information Protocol
- OSPF: Open Shortest Path First
- IGRP: Interior Gateway Routing Protocol (Cisco proprietary)
第100页：第4章：网络层
第4章：网络层
- 4. 1 Introduction
- 4.2 Virtual circuit anddatagram networks
- 4.3 What’s inside arouter
- 4.4 IP: Internet Protocol
- Datagram format
- IPv 4 addressing
- ICMP
- IPv 6
- 4.5 Routing algorithms
- Link state
- Distance Vector
- Hierarchical routing
- 4.6 Routing in the Internet
- 4.7 Broadcast andmulticast routing
第101页：RIP ( 路由信息协议
RIP ( 路由信息协议
- distance vector algorithm
- included in BSD-UNIX Distribution in 1982
- distance metric: # of hops (max = 15 hops)DCBAuvwxyzdestinationhopsu 1 v 2 w 2 x 3 y 3 z 2 From router A to subsets:
第102页：RIP advertisements
RIP advertisements
- distance vectors:exchanged among neighbors every 30 sec via Response Message (also called advertisement)
- ech advertisement: list of up to 25 destination nets within AS
第103页：RIP 示例目的网络下一路由器
RIP路由表示例：下表列出相关数据。
RIP路由表示例| Destination Network | Next Router | Num. of hops to dest. |
|---|
| w | A | 2 |
|---|
| y | B | 2 |
|---|
| z | B | 7 |
|---|
| x | — | 1 |
|---|
第104页：RIP 示例目的网络下一路由器
RIP 示例目的网络下一路由器
RIP: Example Destination Network Next Router Num. of hops to dest.w A2 y B2 z B A7 5 x--1….…..... Routing table in Dwxyz ACDBDest Next hopsw-1 x-1 z C 4….… ... Advertisementfrom A to D
第105页：RIP 链路故障和恢复若
RIP 链路故障和恢复若
- routes via neighbor invalidated
- new advertisements sent to neighbors
- neighbors in turn send out new advertisements (iftables changed)
- link failure info quickly (?) propagates to entire net
- poison reverseused to prevent ping-pong loops(infinite distance = 16 hops)
第106页：RIP表处理
RIP表处理
- RIP routing tables managed byapplication-level process called route-d (daemon)
- advertisements sent in UDP packets, periodically repeated physicallink network forwarding(IP) table Transprt(UDP)routed physicallink network(IP)Transprt(UDP)routed forwarding table
第107页：第4章：网络层
第4章：网络层
- 4. 1 Introduction
- 4.2 Virtual circuit anddatagram networks
- 4.3 What’s inside arouter
- 4.4 IP: Internet Protocol
- Datagram format
- IPv 4 addressing
- ICMP
- IPv 6
- 4.5 Routing algorithms
- Link state
- Distance Vector
- Hierarchical routing
- 4.6 Routing in the Internet
- 4.7 Broadcast andmulticast routing
第108页：OSPF (Open Short
OSPF (Open Short
- “open”: publicly available
- uses Link State algorithm
- LS packet dissemination
- topology map at each node
- route computation using Dijkstra’s algorithm
- OSPF advertisement carries one entry per neighbor router
- advertisements disseminated toentire AS (viaflooding)
- carried in OSPF messages directly over IP (rather than TCPor UDP
第109页：OSPF “advanced” features (not RIP)
OSPF “advanced” features (not RIP)
- security:all OSPF messages authenticated (toprevent malicious intrusion)
- multiple same-costpaths allowed (only one path in RIP)
- For each link, multiple cost metrics for different TOS(e.g., satellite link cost set “low” for best effort;high for real time)
- integrated uni-andmulticast support:
- Multicast OSPF (MOSPF) uses same topology database as OSPF
- hierarchical OSPF in large domains.
第110页：Hierarchical OSPF
Hierarchical OSPF
Hierarchical OSPF
第111页：Hierarchical OSPF
Hierarchical OSPF
- two-level hierarchy:local area, backbone.
- Link-state advertisements only in area
- each nodes has detailed area topology; only knowdirection (shortest path) to nets in other areas.
- area border routers:“summarize” distances to netsin own area, advertise to other Area Border routers.
- backbone routers:run OSPF routing limited tobackbone.
- boundary routers:connect to other AS’s.
第112页：第4章：网络层
第4章：网络层
- 4. 1 Introduction
- 4.2 Virtual circuit anddatagram networks
- 4.3 What’s inside arouter
- 4.4 IP: Internet Protocol
- Datagram format
- IPv 4 addressing
- ICMP
- IPv 6
- 4.5 Routing algorithms
- Link state
- Distance Vector
- Hierarchical routing
- 4.6 Routing in the Internet
- 4.7 Broadcast andmulticast routing
第113页：Internet inter-AS routing: BGP
Internet inter-AS routing: BGP
- BGP (Border Gateway Protocol):thedefacto standard
- BGP provides each AS a means to:1. Obtain subnet reachability information from neigh boring ASs.2. Propagate reachability information to all AS-internal routers.3. Determine “good” routes to subnets based onreachability information and policy.
- allows subnet to advertise its existence torest of Internet:“I am here”
第114页：BGP基础
BGP基础
- pairs of routers (BGP peers) exchange routing infoover semi-permanent TCP connections:BGP sessions
- BGP sessions need not correspond to physicallinks.
- when AS2 advertises prefix to AS1:
- AS2 promisesit will forward any addresses datagrams towards that prefix.
- AS2 can aggregate prefixes in its advertisement 3 b 1 d 3 a 1 c 2 a AS3AS1AS21 a 2 c 2 b 1 b 3 ce BGP sessioni BGP session
第115页：BGP可达性信息分发
BGP可达性信息分发
- using e BGP session between 3 a and 1 c, AS3 sendsprefix reachability info to AS1.
- 1 c can then use i BGP do distribute new prefixinfo to all routers in AS1
- 1 b can then re-advertise new reachability infoto AS2 over 1 b-to-2 a e BGP session
- when router learns of new prefix, creates entryfor prefix in its forwarding table.3 b 1 d 3 a 1 c 2 a AS3AS1AS21 a 2 c 2 b 1 b 3 ce BGP sessioni BGP session
第116页：Path attributes & BGP routes
Path attributes & BGP routes
- advertised prefix includes BGP attributes.
- prefix + attributes = “route”
- two important attributes:
- AS-PATH:contains ASs through which prefix advertisement has passed: e.g, AS 67, AS 17
- NEXT-HOP:indicates specific internal-AS routerto next-hop AS. (may be multiple links fromcurrent AS to next-hop-AS)
- when gateway router receives route advertisement, usesimport policyto accept/decline.
第117页：BGP 路径选择
BGP 路径选择
- router may learn about more than 1 routeto some prefix. Router must select route.
- elimination rules:1.local preference value attribute: policy decision 2.shortest AS-PATH3.closest NEXT-HOP router: hot potato routing 4.additional criteria
第118页：BGP messages
BGP messages
- BGP messages exchanged using TCP.
- BGP messages:
- OPEN:opens TCP connection to peer andauthenticates sender
- UPDATE:advertises new path (or withdraws old)
- KEEPALIVEkeeps connection alive in absence of UPDATES; also ACKs OPEN request
- NOTIFICATION:reports errors in previous msg;also used to close connection
第119页：BGP 路由策略
BGP 路由策略
- A, B, C areprovider networks
- X, W, Y are customer (of provider networks)
- X isdual-homed:attached to two networks
- X does not want to route from B via X to C
- .. so X will not advertise to B a route to CABCWXYlegend:customer network:provider network
第120页：BGP 路由策略 (2)
BGP 路由策略 (2)
- A advertises path AW to B
- B advertises path BAW to X
- Should B advertise path BAW to C?
- No way! B gets no “revenue” for routing CBAWsince neither W nor C are B’s customers
- B wants to force C to route to w via A
- B wants to routeonlyto/from its customers!ABCWXYlegend:customer network:provider network
第121页：为何不同
为何不同
- Inter-AS: admin wants control over how its traffic routed, who routes through its net.
- Intra-AS: single admin, so no policy decisions needed Scale:
- hierarchical routing saves table size, reduced update traffic Performance:
- Intra-AS: can focus on performance
- Inter-AS: policy may dominate over performance
第122页：第4章：网络层
第4章：网络层
- 4. 1 Introduction
- 4.2 Virtual circuit anddatagram networks
- 4.3 What’s inside arouter
- 4.4 IP: Internet Protocol
- Datagram format
- IPv 4 addressing
- ICMP
- IPv 6
- 4.5 Routing algorithms
- Link state
- Distance Vector
- Hierarchical routing
- 4.6 Routing in the Internet
- 4.7 Broadcast andmulticast routing
第123页：R1R2R3R4 source duplication R1R2R3R4
R1R2R3R4 source duplication R1R2R3R4
- deliver packets from source to all other nodes
- source duplication is inefficient:
- source duplication: how does source determine recipient addresses?
第124页：In-network duplication
In-network duplication
- flooding: when node receives brdcst pckt,sends copy to all neighbors
- Problems: cycles & broadcast storm
- controlled flooding: node only brdcsts pktif it hasn’t brdcst same packet before
- Node keeps track of pckt ids already brdcsted
- Or reverse path forwarding (RPF): only forwardpckt if it arrived on shortest path betweennode and source
- spanning tree
- No redundant packets received by any node
第125页：ABGDEc FABGDEc F(a) Broadcast initiated
ABGDEc FABGDEc F(a) Broadcast initiated
- First construct a spanning tree
- Nodes forward copies only along spanningtree
第126页：ABGDEc F12345(a)Stepwise constructionof
ABGDEc F12345(a)Stepwise constructionof
- Center node
- Each node sends unicast join message to centernode
- Message forwarded until it arrives at a node already belonging to spanning tree
第127页：Multicast Routing: Problem Statement
Multicast Routing: Problem Statement
- Goal:find a tree (or trees) connecting routers having local mcast group members
- tree:not all paths between routers used
- source-based:different tree from each sender to rcvrs
- shared-tree:same tree used by all group members Shared tree Source-based trees
第128页：方法面向构建多播 trees 方法
方法面向构建多播 trees 方法
- source-based tree:one tree per source
- shortest path trees
- reverse path forwarding
- group-shared tree:group uses one tree
- minimal spanning (Steiner)
- center-based trees…we first look at basic approaches, then specific protocols adopting these approaches
第129页：广播与多播路由（示意图）
广播与多播路由（示意图）
- mcast forwarding tree: tree of shortestpath routes from source to all receivers
- Dijkstra’s algorithm R1R2R3R4R5R6R7216345 irouter with attached group member router with no attached group memberlink used for forwarding,i indicates order linkadded by algorithm LEGENDS: source
第130页：Reverse Path Forwardingi
Reverse Path Forwardingi
- rely on router’s knowledge of unicastshortest path from it to sender
- each router has simple forwarding behavior:
第131页：反向路径转发示例
反向路径转发示例
- result is a source-specific reverse SPT
- may be a bad choice with asymmetric links R1R2R3R4R5R6R7 router with attached group member router with no attached group member datagram will beforwarded LEGENDS: source datagram will not beforwarded
第132页：反向路径转发剪枝
反向路径转发剪枝
- forwarding tree contains subtrees with no mcastgroup members
- no need to forward datagrams down subtree
- “prune” msgs sent upstream by router with nodownstream group members R1R2R3R4R5R6R7 router with attached group member router with no attached group member prune message LEGENDS: sourcelinks with multicast forwarding PPP
第133页：Shared-Tree
Shared-Tree
- Steiner Tree:minimum cost treeconnecting all routers with attached group members
- problem is NP-complete
- excellent heuristics exists
- not used in practice:
- computational complexity
- information about entire network needed
- monolithic: rerun whenever a router needs tojoin/leave
第134页：Center-based
Center-based
- single delivery tree shared by all
- one router identified as“center”of tree
- to join:
- edge router sends unicastjoin-msgaddressedto center router
- join-msg“processed” by intermediate routersand forwarded towards center
- join-msgeither hits existing tree branch forthis center, or arrives at center
- path taken byjoin-msgbecomes new branch oftree for this router
第135页：Center-based
Center-based
Center-based trees: an example Suppose R6 chosen as center:R1R2R3R4R5R6R7 router with attached group member router with no attached group memberpath order in which joinmessages generated LEGEND2131
第136页：Internet Multi casting Routing: DVMRP
Internet Multi casting Routing: DVMRP
- DVMRP:distance vector multicast routing protocol, RFC1075
- flood and prune:reverse path forwarding,source-based tree
- RPF tree based on DVMRP’s own routing tables constructed by communicating DVMRP routers
- no assumptions about underlying unicast
- initial datagram to mcast group flooded everywhere via RPF
- routers not wanting group: send upstream prunemsgs
第137页：DVMRP: continued…
DVMRP: continued…
- soft state:DVMRP router periodically (1 min.)“forgets” branches are pruned:
- mcast data again flows down unpruned branch
- downstream router: reprune or else continue toreceive data
- routers can quickly regraft to tree
- following IGMP join at leaf
- odds and ends
- commonly implemented in commercial routers
- Mbone routing done using DVMRP
第138页：多播隧道
多播隧道
- mcast datagram encapsulated inside “normal” (non-multicast-addressed) datagram
- normal IP datagram sent thru “tunnel” via regular IP unicast toreceiving mcast router
- receiving mcast router unencapsulates to get mcast datagram physical topology logical topology
第139页：PIM: Protocol Independent Multicast
PIM: Protocol Independent Multicast
- not dependent on any specific underlying unicastrouting algorithm (works with all)
- two different multicast distribution scenarios :Dense:
- group members densely packed, in“close” proximity.
- bandwidth moreplentiful Sparse:
- # networks with group members small wrt #interconnected networks
- group members “widelydispersed”
- bandwidth not plentiful
第140页：Consequences Sparse-Dense Dichotomy
Consequences Sparse-Dense Dichotomy
- group membership byrouters assumed until routers explicitly prune
- data-driven constructionon mcast tree (e.g., RPF)
- bandwidth and non-group-router processing profligate Sparse:
- no membership until routers explicitly join
- receiver-driven construction of mcasttree (e.g., center-based)
- bandwidth and non-group-router processing conservative
第141页：广播与多播路由（示意图）
广播与多播路由（示意图）
- underlying unicast protocol provides RPF infofor incoming datagram
- less complicated (less efficient) downstream flood than DVMRP reduces reliance onunderlying routing algorithm
- has protocol mechanism for router to detect itis a leaf-node router
第142页：广播与多播路由（示意图）
广播与多播路由（示意图）
- center-based approach
- router sendsjoinmsgto rendezvous point(RP)
- intermediate routers update state andforwardjoin
- after joining via RP,router can switch tosource-specific tree
- increased performance:less concentration,shorter paths R1R2R3R4R5R6R7 joinjoinjoinall data multicastfrom rendezvous point rendezvous point
第143页：广播与多播路由（示意图）
广播与多播路由（示意图）
- unicast data to RP,which distributes down RP-rooted tree
- RP can extend mcasttree upstream tosource
- RP can sendstopmsgif no attached receivers
- “no one is listening!”R1R2R3R4R5R6R7 joinjoinjoinall data multicastfrom rendezvous point rendezvous point
第144页：第4章小结
第4章小结
- 4. 1 Introduction
- 4.2 Virtual circuit anddatagram networks
- 4.3 What’s inside arouter
- 4.4 IP: Internet Protocol
- Datagram format
- IPv 4 addressing
- ICMP
- IPv 6
- 4.5 Routing algorithms
- Link state
- Distance Vector
- Hierarchical routing
- 4.6 Routing in the Internet
- 4.7 Broadcast andmulticast routing
