互联网协议 Internet Protocol"/>
【IP 笔记 3.】北邮 互联网协议 Internet Protocol
DataLink Layer
问答:
- Deliver traffic to “neighbouring” routers
- Switch(交换机是在家里网络的,通常不在Internet之中)
6.1 introduction, services
introduction
作用区间:
- host与router之间,host和router都称为node
- 相邻的node之间的连接称为links
- wired links
- wireless links
- LANS
- layer-2 pkt 叫frame,用来包装datagram
layer2的作用:
Content
不同的datagram用不同的link protocol来传输
每一个link protocol提供不同的service
比喻: 从Princeton 到Lausanne的旅行
- Limo:从Princeton 到 JFK
- Plane:JKF 到 Geneva
- Train:从 Geneva 到Lausanne
整个tourist 就是 datagram
每一个交通的片段就是 communication link
不同的交通方式 link layer protocol
旅行管理 routing algorithm
Services
-
Framing, link access:
- 加Adder讲datagram包装乘fram,如果要share medium的话,还要加上trailer channel access
- 在Header中加上MAC地址来区分这个source和dest
-
Reliable delivery between adjacent node
- 确保的是在相邻的node中间是reliable的
-
Flow control
- 在相邻的node中确保
-
Error detection
-
Error correction
-
Half-duplex and full-duplex
Link layer应用在哪
在每一个host中
- 应用在 network interface car NIC 中
6.2 Error detection, correction
EDC:检测和改正的bit
D :data
Parity checking
Single bit parity
- 探测单个bit的错误
Two-dimensional bit parity
- 探测并改正单个bit error
Cyclic redundancy check
计算CRC,G
是多少位,CRC的位数减一
D
: data bits
G
: r+1 bit pattern(generator)
目标:选择 r位的 CRC bits R
,使得
<D, R>
正好能被G
整除- 接收端知道G,将
<D, R>
除G
,如果是非全零的就代表有错误
CRC计算例子
把G
放到D
下面,顶格做XOR运算(相同则为0,不同为1)直算到比G少一位的CRC出来。
6.3 multple access protocols
有两种“links”
- point-to-point
- broadcast (shared wire or medium)
共享介质或者线的话会引发问题——collision
- 两个或两个以上信号同时传输
解决方法:Multiple access protocol
理想多址协议
Channel capacity:R (bps)
期望通过多址协议实现:
- 一个node发送时,可以达到Capacity
- 当M个node同时发送时,每一个node都是 R/M
- 完全的去中心化
- 没有用来协调传输的node
- 没有同步器,例如时钟或者slot
- 简单
选择:分Channel,随机访问,轮着来
TDMA
FDMA
Random Access Protocols
前提:
-
当node有pkt要发时,会以Capacity的全速率发送
-
当有两个或两个以上的node同时transmitting时,会有“collision”
Random Access Protocol 指定:
- 如何检测collision
- 如何从collision中恢复
random access MAC protocol 的例子:
- slotted ALOHA
- ALOHA
- CSMA,CSMA/CD,CSMA/CA (Carrier Sense Multiple Access(Collision Detection/Collision Avoidance))
Slotted ALOHA
假设条件:
- 全部的frame都是一个大小的
- 时间被分割到固定大小的slot中
- nodes只在slot开始时进行传输
- nodes之间要同步
- 如果两个或两个以上的结点在同一个slot中传输时,全部的node都会检测到collision
运转模式:
- node有了新的frame时会在下一个slot时候发
- 没有collision,在下一个slot发新的
- 有collision,node在每一个从slot中以概率p来重发原来的frame
优点:
- 只有一个node激活时,可以以capcity全速传输
- 高度去中心化,只要确保每一个nodes同步即可
- 简单
缺点:
- 有collision时会直接浪费掉slot
- 存在闲置的slot
- slot要在比发送pkt时间内检测到collision
- 需要时间同步
Pure ALOHA
简单,没有同步
运转机制:
- 当frame到达时,立马发出
后果:
- collision的概率升高
特点:
- 不需要统一时钟,但效率只有slotted ALOHA的一半
CSMA
Carrier Sense Multiple Access
运转机制:在发送之前监听信道
- 如果channel空闲 => 发送
- 如果channel忙碌 => 等待
缺点:
- collision依然存在,监听中存在delay。
- 如果collision出现,整个pkt传输的time都会被浪费
CSMA/CD (Collision Detection)
载波感知,在传输的时候停止一小段时间
- collision可以在很短的时间内检测出
- collision会使得传输中止,减少信道损耗
Collision Detection:
- 在有线的LANs中很容易检测到 (measure signal strengths, compare transmitted, received signals)
- 在无线网络中难以检测 (difficult in wireless LANs: received signal strength overwhelmed by local transmission strength)
检测到Collision就停
Ethernet CSMA/CD 算法
- Network Interface Card(NIC) 接收来自Network Layer的数据并创建 Frame
- 如果NIC 检测到 channel 是空闲的,那么就发送数据。如果检测到 Channel 是繁忙的,就会等待到其空闲时再发送
- 如果NIC传输了整个frame而没有检测到另一个传输,NIC就用frame完成
- 如果NIC检测到了另一个正在传输,那么会中断(abort)自己的传输并发送 Jam(堵塞) 信号
- 在中止后,NIC进入到二进制的指数级的backoff中
- 在检测到第m个collision后,NIC从[ 0 0 0, 2 m − 1 2^m-1 2m−1]的范围中选择一个随机数 K K K ,NIC会继续等待 K ∗ 512 K*512 K∗512 个bit的时间,然后返回第二步
- 越多的collision则会等待越久
计算
Frame Size
Collision Detection
Collision Window
- 与端到端传输延迟有关
最小的pkt size要大于Collision Window (the transimitting station is still trasmitting long enough for a corrupted signal to be detected)
计算题:最小帧大小
F r a m e S i z e m i n = R T T ∗ R b FrameSize_{min}=RTT*R_b FrameSizemin=RTT∗Rb
为什么要长过Collision Window
- 为了能检测到Collision
CSMA/CA (Collision Avoidance)
避免collision:两个或两个以上的node同时传输
主要用在无线领域中 802.11
802.11:CSMA - 在传输之前感知
802.11:没有collision探测
- 因为在发送后信号很微弱,不容易感知
- 所以只能避免collision
IEEE 802.11 MAC Protocol: CSMA/CA
802.11 发送端
- 如果检测到channel空闲了一段时间(DIFS),那么就会发送整个frame
- 如果检测到channel繁忙,那么回开始在随机的backoff 计时器直到信道空闲
- 如果没有 ACK 回来,那么会随机增加backoff的interval
802.11 接收端
收到了frame后等一段时间(SIFS)后回复ACK (因为存在潜在的Terminal问题,所以需要ACK)
DCF = Distributed Coordination Function
DIFS = DCF InterFrame Space
SIFS = Short InterFrame Space
Avoiding Coolision (more)
想法:允许发送端“保留”channel,而不是Random Access of Data。为了更长的数据frame预防collision
- Sender先使用CSMA发送一个很小的 request-to-send(RTS) pkt到基站(BS)
- 基站会广播clear-to-send(CTS)来回应 RTS
- CTS是被全部节点抄收的
- sender可以发送数据frame
- 其他的station推迟transmissions
通过发送小的reservation pkt来完全预防collision的发生
6.3 总结
channel partitioning, by time, frequency or code
- TDMA, FDMA, CDMA
random access (dynamic)
- ALOHA, Slotted-ALOHA, CSMA, CSMA/CD
- carrier sensing: easy in some techonogies (wire), hard in wireless
- CSMA/CD used in Ethernet
- CSMA/CA used in 802.11
6.4 LANs
MAC Addresses and ARP
与IP地址不同
-
32-bit IP 长度
- 用在network layer中来address interface的
- 用于layer3 (network layer)中的forwarding
-
MAC (or LAN or physical or Ethernet) address:
-
功能:使用“本地”从一个接口获得帧到另一个物理连接的接口(相同的网络,在ip寻址意义上)
-
长度:48 bits (烧录在NIC中)
-
用16进制来表示 例如
1A-2F-76-09-AD
-
LAN Address and ARP
每一台适配器(Adapter)在LAN中都有唯一的LANaddress
MAC地址是由IEEE颁发的
制造商购买一个范围内的MAC地址
比喻:
- MAC就像身份证号,是固定的
- IP地址像邮政码,是可变的
ARP: address resolution protocol
Question: 如何在知道IP地址的情况下定义端口的MAC地址
使用ARP表:每一个IP地址在LAN中都有一个表,用于连接host的ip和其MAC
- 对LAN中的node进行IP/MAC的MAP
- TTL(Time To Live),经过一段时间后,address map会被删除(通常为20mins)
ARP protocol: smae LAN
流程如下:
A想给B发datagram
- B的MAC地址不在A的ARP表中
一个包含了B的IP地址的ARP query包以广播(Broadcast)形式发送
- 目的地MAC address = FF-FF-FF-FF-FF-FF (全部为1)
- LAN中的全部node都接收到ARP query
B接收到了ARP查询包会将B的MAC地址回复给A
- 使用frame将有B的MAC信息的发送给A’s MAC(非广播形式)
A缓存IP-to-MAC地址对在自己的ARP表中直到information过期(time out)
- soft state: 过期了的information会被丢弃(除非刷新)
ARP是plug-and-play的
- node可以在没有其他node同意的情况下自己创建自己的ARP表
Addressing: routing to another LAN
目标:从A经过R发送datagram到B
- 关注addressing —— 在IP(datagram)以及MAC(frame)
- 假设A知道B的IP地址
- 假设A知道第一个路由器
R
的ip地址(如何知道?) - 假设A知道
R
’s MAC 地址(如何知道?)
A创建IP datagram,包含IP souce A,dest B
A创建link-layer frame,包含R’s MAC address以及dest address,Frame包含了A-to-B IP datagram
- 为什么包含R’s MAC address,因为link-layer是复制adjacent node之间的通信的,所以只用包含临近node之间的地址,发送端为源,临近的终点为dest
Frame从A发到R
R接收到Frame,取出datagram,移入IP层
R通过IP source A,destination B来进行forwarding
R创建link-layer frame,内含B’s MAC address作为终点地址,整个frame包含了A-to-B的ip datagram
Testing
Address Resolution Protocol, ARP 仅用在终点IP地址已知的情况下寻找终点MAC地址
Ethernet
一个区域内有线连接的LAN技术
便宜,简单
速度可以达到 10Mbps~10Gbps
Physical Topology
Bus: 90s中期受欢迎,全部的node都在同一个域里面,又一个bus相连接
Star:现在的用法,用一个switch连接全部的host
Ethernet Frame Structure
内部包含了例如IP datagram在内的网络层协议
preamble:
-
七个以
10101010
接着一个字节10101011
的字节 -
用于同步接收器,就像时钟频率一样
address:
- 6个字节的source,destination MAN address
type:
- 用来指示更高层(网络层)的协议是什么,大部分为IP(也有一些,AppleTalk)
CRC:
- cyclic redundancy 接收端校验码
Unreliable, Connectionless
Ethernet是不可靠的,Connectionless的
Connectionless
- 在NIC之间发送和接收是没有握手的
Unreliable
- 接收端NIC不会发送ACK或者NACK
- 只能依靠TCP协议来接收那些丢失掉的data
Ethernet’s MAC Protocol
使用的是:unslotted CSMA/CD with binary backoff
Switches
作为link-layer的device发挥作用: (都是对Ethernet来说的)
- store, forward Ethernet frames
- 使用USMA/CD校验接收到的frame‘s MAC address, 当frame在段上被转发时,有选择地将frame转发给一个或多个传出link
透明的
- host不知道switch的存在
Plug-and-play, self-learning
- 不需要配置,即插即用
多个同时传输出现时
是full duplex的,多个同时传输可以考switch来确保不会有collision出现
Switch forwarding table
每一个switch都有一个switch table,告诉不同的接口应该走哪个出口出
self-learning
switch要自我学习哪个host能通过哪个接口到达
- 当frame到达时,switch会学习发送端的address
- 在switch table中记录sender/address对
算法:
如果这个终点的这个MAC-IP对能在表中找到
- 如果frame就是来自其destination上标记的地方
- 丢弃
- 否则
- forward到entry指示的interface
否则
- flood (forward到除到达接口以外的全部的接口 broadcast)
Switches vs. Routers
两个都可以实现store-and-forward
-
router: network-layer devices
-
switches: link-layer devices
两个都有forwarding table
- router: 利用routing算法以及IP地址来计算table
- switch: 自我学习,利用flooding(不知道就广播等待回复)
WLANs
无线网络中的元素:
基站
- 基站与基站之间是通过有线连接的
- 负责提供一片区域内的无线连接
无线连接
基础设施模式
- 基站:将移动设备连接到有线连接的互联网中
- handoff:手机变成基站提供一部分的无线连接
ad hoc mode
- 没有基站
- nodes之间仅能在覆盖范围内传输
- nodes之间是自组织成网络的
IEEE 802.11 Wireless LAN
类型(全部使用CSMA/CA,可以在基站模式和ad-hoc中使用)
连接不同的接入点(access point AP)
-
对不同的接入点使用不同的信道
-
自主选择信道
-
如果临近的AP使用相同的信道会有interferes
-
AP发送SSID和MAC地址作为信标
-
host基于SSID来选择AP
-
host使用的是DHCP(动态分配IP协议)来获取IP地址
802.11 LAN 结构
无线host通过基站来通信
- 基站(BS)相当于接入点(AP)
Basic Service Set (BSS) (aka “cell”) 结构模式包含:
- wireless host
- AP:基站
- ad hoc mode:host only
802.11 frame addressing
记住前三个地址分别是什么
- 地址1:接收这个frame的MAC地址
- 地址2:发送这个frame的MAC地址
- 地址3:第一个相连的router的interface的MAC地址
- 地址4:ad hoc mod专用(非ac-hoc模式则为全零)
VLAN
作用:is used to group devices logically for easy management
Virtual Local Area Network, 通过switch设定特定的局域网。在已有的一个LAN中设定多个独立的LANs
port-based VLAN:交换机的ports分组,在一个交换机上实现多个虚拟的交换机
Port-based VLAN
traffic isolation:从1-8到达发出的frame只能在1-8端口之间流通
dynamic membership:端口可以动态的分配给不同的VLAN
forwarding between VLANs:通过routing来实现,相当于独立的几个switch来进行forwarding
VLANs 扩展多个Switches
trunk port:在VLANs中的frame会经过多个不同的switch
6.5 link virtualization MPLS
需要在支持MPLS的路由上才能使用
Multiprotocol label switching (MPLS)
目标:使用固定长度的label来实现更快速的IP forwarding
- 使用最长前缀对比
- 仍然使用IP地址
MPLS capable routers
aka label-swtiched router
仅通过label的值来forward到要输出的接口
- MPLS forwarding table与IP forwarding table是不同的
flexibility:MPLS转发决策可能与IP的转发决策不同
- 使用目的地址和源地址以不同的方式将流路由到相同的目的地
- 如果链路故障,重路由流很快:预先计算的备份路径(对VoIP很有用)
MPLS vs. IP paths
IP routing:到终点的路径仅取决于终点的地址
MPLS routing:到终点的路劲取决于source的地址以及终点的地址。(多了source地址)
- fast reroute:预计算备份了routes
MPLS forwarding tables
- 两个不同的label可以都去同一个目的地。也就是说,同一个目的地可以有不同的label就代表了有不同的path
- 只需要检测输入的label是多少,马上匹配到输出的label
6.5 Testing
6.6 a day in the life of a web request
从上到下全部的layer都要走一遍
用户访问网页
使用DHCP获取laptop的IP,DHCP请求用UDP来包装(transport layer),包装在IP中(network layer),发送到Ethernet中
Ethernet Frame 在LAN中广播(终点为:FF-FF-FF-FF-FF-FF-FF-FF),DHCP服务器收到广播的请求
Ethernet在DHCP服务器端解包IP,解包UDP
DHCP服务器创建包含有客户端IP地址、第一个路由器的IP地址、DNS服务器的name及地址的DHCP ACK
在DHCP服务器包装成frame,通过LAN forward到client(switch learning)并在client处解包
客户端接收到DHCP服务器ACK回应
此时,客户端有以下信息:name&addr of DNS server,第一个路由器的IP地址
在发送HTTP请求前,想DNS询问网站url对应的IP
DNS查询创建,用UDP包装,用IP包装,进入Eth。
为了发送frame到router,需要router interface的MAC地址才能发送(ARP),所以创建ARP查询请求
ARP请求广播,路由器抄收,并将自己的interfer的MAC地址返回给client
client知道了第一个路由器的MAC地址,现在可以发送DNS请求了
包含DNS查询请求的IP datagram在LAN中一路forward直到DNS
DNS解包DNS查询请求
DNS回应请求,发送网页url对应的IP地址
为了发送HTTP请求,客户端首先打开对web server监听的TCP socket
TCP SYN segment发送到web-server
进行三次握手
确立TCP连接
HTTP请求发送到TCP socket中
包含HTTP请求的IP datagram发送到对应的网站
网站使用HTTP reply反馈http请求
来回来回
更多推荐
【IP 笔记 3.】北邮 互联网协议 Internet Protocol
发布评论