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
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 ?
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
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
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
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
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
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
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......
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
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
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报文时,它便知道了它不需要再发送另外的探测分组
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
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'
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:
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