网络层（internet/network layer）是第三层，它关注的是如何将源数据包一路畅通的送到接收方。
网络层必须知道网络拓扑结构（即所有路由器和链路的集合），并从中选择出适当的路径。同时，网络层还必须自信选择路由器，避免某调通信线路负载过重，而其他线路和路由器空闲。最后，当源端和接收端位于不同的网络时，还会出现新问题，这些问题都需要由网络层来解决。hop（跳）是一个network网络
网络层基本只运行在路由器上，而不是host上。
网络层提供两种服务，connectionless 和 connection-oriented
• Connectionless
Packet switching (Internet Protocol – IP)
Minimum required service: “send packet”
Called a “datagram network”
• Connection-oriented
Circuit Switching
Asynchronous Transfer Mode – ATM
MultiProtocol Label Switching – MPLS
“send packet” and “Establish connection”, “tear down connection”
Called a “virtual circuit network”
互联网是一个packet switched network
• Host H1 wants to send a packet to H2
1. Transmits it to the nearest router (A)
2. The packet is buffered while it is arriving, and the checksum is verified
3. If valid, the packet is stored until the outgoing interface is free
4. The router forwards the packet onto the next router in the path
5. Repeat 2-4
分组交换=Packet switching(connectionless)
其原理是将报文拆分成一系列相对较小的数据包，将其传输到目的地再进行重组，还原成原报文。
分组交换需要报文的拆分与重组。
由于要让每个分组都能顺利到达目的地并重组，需要给每个分组加上一些说明信息，即头文件：
因此会产生额外开销。
分组交换以较小的分组进行“存储-转发”，因此对路由器的“存储”要求低。
分组交换的优点
a.分组交换允许更多用户同时使用网络
b.适用于突发数据传输网络：资源充分共享，简单无需呼叫建立连接。
分组交换的缺点
如果很多人同时使用网络，可能产生拥塞（congestion)，导致分组延迟和丢失。（需要协议处理可靠数据传输和拥塞控制）。
分组交换为了避免出现失序，丢失或重复分组，分组到达目的节点时，对分组按编号进行排序等工作，增加了工作量。
电路交换 = Circuit Switching
电路交换是以电路连接为目的的交换方式，通信之前要在通信双方之间建立一条被双方独占的物理通道。
电路交换的三个阶段：
（1）建立连接 （2）通信 （3）释放连接
优点：
（1）由于通信线路为通信双方用户专用，数据直达，所以传输数据的时延非常小。
（2）通信双方之间的屋里通路一旦建立，双方可以随时通信，实时性强。
（5）电路交换的交换设备及控制均比较简单。
缺点：
（1）电路交换平均连接建立时间对计算机通信来说较长。
（2）电路交换家里连接后，物理通路被通信双方独占，即使通信线路空闲，也不能供其他用户使用，因而信道利用率低。
（3）电路交换时，数据直达，不同类型，不同规格，不同速率的终端很难相互进行通信，也难以在通信过程中进行差错控制。
MultiProtocol Label Switching 多协议标签交换
这个switch不用了解它的原理，记住它的一些特性
被运用在电路转换的协议中
• Widely deployed Virtual Circuit (connection-oriented) Network Layer Protocol (below the internet sublayer)
MPLS network is one IP hop
注重服务质量，最优化网络堵塞，网络质量和可靠的连接
• Primary purpose is Quality of Service
Prioritising traffic
Service Level Agreements for network performance
Reliable connectivity with known parameters
只有大公司之间的数据交换会用
• Popular with businesses that want to connect multiple sites and phone companies carrying voice traffic
相当贵
• Expensive: Price roughly 20-100 times more per Mbps than a standard internet connection. (Cost is much more similar.)
Quality of Service 服务质量
是一种可以为不同类型业务流提供差分（即“不同”）服务等级的技术。通过QoS可以给那些对带宽、时延、时延抖动、丢包率等敏感的业务流提供更加优先的服务等级，使业务能满足用户正常、高性能使用的需求。
为什么有时候服务质量重要？
因为每个网络服务的侧重点不一样，比如 VoIP vs file downloads VPN connections vs web browsing
Ip协议 Internet Protocol
是整个Internet的基础，它是无连接网络服务的重要范例。每个数据包携带一个目标IP地址，路由器使用该地址来单独转发每一个数据包。IPv4数据包的地址是32为，IPv6数据包的地址是128位。
ip地址不是每个host的地址，而是每个网络接口的地址，比如网卡
地址的种类：
Unicast: One destination (“normal” address)（大部分情况下）
Broadcast: Send to everyone（比如手机里的热点，wifi）
Multicast: Send to a particular set of nodes（比如说视频网站，直播平台）
– Used for streaming video of live events
Anycast: Send to any one of a set of addresses
– Used for database queries, like DNS, NTP
Geocast: Send to all users in a geographic area(基本上不会用到)
– “Location aware” services
– Send ad to those in store
– Send warning to those near a hazard
ipv4
0.0.0.0 - 255.255.255.255 每个IP地址长度为32bit, 每台主机和路由器上的每个接口都必须有一个全球唯一的IP地址。一个接口的IP地址的组成部分需要由其连接的子网来决定。IP地址的格式一般如下：
对于IP地址具有相同网络号且不跨越路由器可以彼此物理联通的接口称为IP子网。如下图的223.1.1.0/24, 223.1.2.0/24, 223.1.3.0/24.
分类编址（classes）（已经不被使用了）
子网划分
一个拥有许多物理网络的单位，可将所属的物理网络划分为若干个子网。划分子网纯属于一个单位内部的事情，本单位以外的网络看不见这个网络是由多少个子网组成的。
划分子网的方法是从网络的主机号借用若干位作为子网号（subnet-id）。IP地址变为{网络号+子网号+主机号}
凡是从其他网络发送给本单位某个主机的IP数据报，仍然是根据IP数据报的目的网络号找到连接在本单位网络上的路由器。但此路由器在收到IP数据报后，再按目的网络号和子网号找到目的子网，把IP数据报交付给目的主机。
子网掩码
将网络号和子网号全取1，将主机号全取0。
A网默认子网掩码为：255.0.0.0，B网默认子网掩码：255.255.0.0，C网默认子网掩码：255.255.255.0，借用3bit划分子网的B网子网掩码为：255.255.224.0
可以使用子网掩码和IP地址进行逐位的与运算得出子网网络地址。
CIDR-无分类编址
地址格式：a.b.c.d/x,其中x为前缀长度。
提高了IPv4地址空间分配效率
提高路由效率，实现了路由聚合，缩减了路由表规格
查找路由表使用最长前缀匹配优先（二叉线索树查找路由表）
ipv6
IPv6最主要的作用在于解决IPv4地址不够用问题。用于替代IPv4的下一代IP协议，它有更大的地址空间，地址长度为128位，能完全解决IPv4耗尽的问题。header更小，处理起来更快。Ipv6具备更高的安全性，集成了IPSec协议，作为IPv6固有的一部分。IPv6具备更好的可移动性。IPv6具备更好的保持服务。
1、IPV6地址由128位组成，使用8个16位段来表示，每个16位段使用十六进制数字表示即每4个十六进制为一组，之间使用英文冒号:分开
2、格式为：x:x:x:x:x:x:x:xx代表4个十六进制位，举例：2035:0001:2BC5:0000:0000:087C:0000:000A
3、IPV6地址包括两部分：前缀+本地标识
4、前缀：通过在IPV6地址后面加一个斜线/，再跟一个十进制的数字来标识一个IPV6地址的起始位由多少位是前缀位，一般前缀为64位，如：3ffe:1994:100:a::/64
路由选择（routing）
主要作用之一就是为不同网络之间传送数据包寻找路径并进行存储转发。
路由选择涉及三个方面：
路由表
路由协议
转发算法
路由器依据最长路径匹配原则查找路由表，确定相应的转发路径，并遵循一定的转发算法对数据包进行转发。路由表中的路由信息需要手工配置或由路由协议动态维护，路由器将基于管理距离（ Administrative Distance， AD）和路由度量（metric）选出进入路由表的最佳路径。
路由与路由表
用于指导数据包转发所需要的路径信息称为路由。路由信息记载了通往每个结点或网络的路径，并以记录的形式出现在路由器的路由表中。
路由器必须依靠路由表中的路由信息进程路径选择。在 Internet中，路由器为了能够正确转发 IP数据包，会根据数据包中的目的 IP 地址查找路由表，为它选择一条到达目的地的最佳路径，然后从相应端口将其转发给下一个路由器，重复此过程直到数据包来到与目的主机所直连的路由器，并由该路由器交付给目的主机。
路由表相当于一个小型数据库，实现一组目的地址到下一条路由 IP 地址的映射，由于制造厂商及规格的不同会导致路由信息的记录格式有所差异，但至少要有如下信息项：
目的地址（Destination）：标识 IP 数据包要到达的目的主机或目的网络的 IP 地址。
子网掩码（Mask）：与目的地址一起标识目的主机或路由器所在网段的地址。
下一条地址（Nexthop）：标识 IP 数据包所经由的下一个路由器的接口地址。
输出接口（Interface）：指示 IP 数据包将从该路由器哪个接口转发出去。
除了上述信息外通常还包含路由优先级、路由度量等项，用于辅助路径选择。当存在到达同一目的地的多条路由信息时，会根据这些辅助项选择一条最佳路由信息添加到路由表中用于后入的数据包转发。
CIDR与路由聚合(routing aggregation)
提高IPv4 地址空间分配效率
提高路由效率
将多个子网聚合为一个较大的子网
构造超网（supernetting）
路由聚合（route aggregation）
路由算法， Routing Algorithm
用来决定packet走哪一条output line
Properties of a good routing algorithm好算法的特性
– Correctness
– Simplicity
– Robustness – a router crash should not require a ‘network’ reboot
– Stability - a stable algorithm reaches equilibrium and stays there
– Fairness
– Efficiency
– Flexibility to implement policies
路由算法分类
静态路由：
手工配置
路由更新慢
优先级高
动态路由：
路由更新快
定期更新
及时响应链路费用或网络拓扑变化
flooding（洪泛）
是一个简单有效的路由算法，其基本思想是每个节点都是用广播转发收到的数据分组，若收到重复分组则进行丢弃处理。洪泛协议会导致数据分组以源节点为中心进行扩散，为了不造成大面积的扩散占用过多的网络资源以及使扩散收敛，需要设定合适的TTL（discarding packets）值，保证数据分组只经过有限跳路由；此外为了进行重复分组检测，每个节点需要维护一个数据分组序号SEQ和一张路由表，源节点每发送一个数据分组则将SEQ增1，并将该SEQ添加到数据分组的IP头部，其余节点收到数据分组后会将该SEQ记录到路由表并根据该SEQ进行重复分组检测。
洪泛算法最大的问题是会产生大量的重复分组，占用网络资源，使路由器和链路的资源过于浪费，以致效率很低。但是洪泛路由算法是一个最简单和最可靠的路由算法，在节点运动剧烈、进出网络频繁变化的场景下，全网洪泛是有效的方式，其具有极好的健壮性，可用于军事应用，也可以作为衡量标准评价其他的路由算法。
TTL（Time To Live）TTL的作用是限制IP数据包在计算机网络中的存在的时间，If unknown can be set to diameter of network如果TTL不知道设置多少可以设置为网络的diameter？？？？（总带宽？）
最优化原则（optimality principle）
如果路由器 J 在路由器 I 到 K 的最优路由上，那么从 J 到 K 的最优路由会落在同一路由上。
学了BGP后就知道这个原则有例外的时候
汇集树（sink tree）
从所有的源结点到一个给定的目的结点的最优路由的集合形成了一个以目的结点为根的树，称为汇集树；
路由算法的目的是找出并使用汇集树。
最短路径路由算法（Shortest Path Routing）
1）基本思想：构建子网的拓扑图，图中的每个结点代表一个路由器，每条弧代表一条通信线路。为了选择两个路由器间的路由，算法在图中找出最短路径。
2）测量路径长度的方法：结点数量、地理距离、传输延迟、距离或信道带宽等参数的加权函数。
Dijkstra算法
a:每个结点用从源结点沿已知最佳路径到本结点的距离来标注，标注分为临时性标注和永久性标注；
b:初始时，所有结点都为临时性标注，标注为无穷大；
c:将源结点标注且为0，为永久性标注，并令其为工作结点；
d：检查与工作结点相邻的临时性结点，若该结点到工作结点的距离与工作结点的标注之和小于该结点的标注，则用新计算得到的和重新标注该结点；
e:在整个图中查找具有最小值的临时性标注结点，将其变为永久性结点，并成为下一轮检查的工作结点；
f:重复d,e，直到目的结点成为工作结点；
具体工作方式如下：
链路状态路由算法 （Link State Routing）
1）距离向量路由算法（ Distance Vector Routing）的主要问题
选择路由时，没有考虑线路带宽；
路由收敛速度慢。
2）链路状态路由算法
1发现邻居结点，并学习它们的网络地址；
2路由器启动后，通过发送HELLO包发现邻居结点；
两个或多个路由器连在一个LAN时，引入人工结点；
测量到每个邻居结点的延迟或开销；
一种直接的方法是：发送一个要对方立即响应的ECHO包，来回时间除以2即为延迟。
3将所有学习到的内容封装成一个包；
包以发送方的标识符开头，后面是序号、年龄和一个邻居结点列表；
列表中对应每个邻居结点，都有发送方到它们的延迟或开销；
链路状态包定期创建或发生重大事件时创建。
4将这个包发送给所有其它路由器；
5算出到每个路由器的最短路径
3）基本思想
洪泛链路状态包，为控制洪泛，每个包包含一个序号，每次发送新包时加1。路由器记录信息对（源路由器，序号），当一个链路状态包到达时，若是新的，则分发；若是重复的，则丢弃；若序号比路由器记录中的最大序号小，则认为过时而丢弃；
4）改进
序号循环使用会混淆，解决办法：使用32位序号；
路由器崩溃后，序号重置；
链路状态包到达后，延迟一段时间，并与其它已到达的来自同一路由器的链路状态包比较序号，丢弃重复包，保留新包；
链路状态包需要应答；
计算到每个其它路由器的最短路径。
根据Dijkstra算法计算最短路径；
Border Gateway Protocol (BGP)边界网关协议
边界网关协议BGP（Border Gateway Protocol）是一种实现自治系统AS（Autonomous System）之间的路由可达，并选择最佳路由的距离矢量路由协议。
Autonomous Systems (AS) - collections of routers under the same administrative control
与内部网关协议不同，边界网关协议的目标并不是找到到目的网络的一个最短路径，而是找到一个合适的路径，因此BGP称为路径向量协议。
理由如下：
（1）互联网规模太大，如果使用最短路径算法计算时间将会很久。
（2）不同的自治系统有不同的策略，就好像不同的国家有不同的法律一样，有些路由器可能会过滤一些请求。
工作原理：
（1）在每个自治系统里面选择至少一个BGP发言人，这个角色是用来跟相邻自治系统来交换信息的，信息包括到达某个网络所要经过的一系列自治系统。
（2）当BGP发言人互相交换了网络可达性的信息后，各BGP发言人就根据所采用的策略从收到的路由信息中找出到达个自治系统的合适的路由。
BGP协议交换路由信息的节点数量级是自治系统的量级。
