Network4:NetworkLayer

　　The primary tasks of a router lies in two aspects: (1) running routing protocols, and (2) forwarding datagrams. Some of the major routing protocols run on the Internet are as follow:

　　Among broadcast routing algorithms, Reverse Path Forwarding is a controlled flooding strategy, in which only a leaf of the tree would receive a redundant packet.

　　The following picture sheds light on the architecture of a router:

　　Weighted Fair Queuing (WFQ): 怎样的调度策略对于每个数据流都是公平的？

　　(1) FIFO并不公平，因为packet可能会不一样大，肯定会有数据流多吃多占；

　　(2) 最公平的情况应该是把每个packet拆成字节，然后挨个数据流轮询，每次发送一字节，但臣妾实在做不到；

　　(3) 可以根据 (2) 的理想情况计算每个packet到达和离开的虚拟时间，其中第i个流的第j个packet离开时间为：

　　　　$out_j^{(i)}=max\{out_{j-1}^{(i)},in_j^{(i)}\}+\frac{L_j^{(i)}}{weight_i}$；

　　(4) 我们根据 (3) 计算的离开时间将到达的packet组织成优先级队列，离开时间值越小的packet越先处理，可以保证各packet出队顺序与 (2) 相同。

　　The following picture illustrates the IPv4 Datagram Format:

　　Since Maximum Transmission Unit (MTU) exists,  a large datagram may be fragmented and assembled by IPv4 routers, which will never happen in IPv6.

　　CIDR (Classless Inter-Domain Routing): Traditionally, hosts on the Internet can be addressed in a classful way illustrated by the following picture. Nevertheless, a class B network is too large for an organization whereas a class C network may be too small. Therefore, RFC1519 put forward a solution that the remaining class C addresses be distributed according to vairable length subnet masks.

　　子网划分、分级CIDR与路由聚合缓解了路由表爆炸的问题，就像当年的多级页表、inode 和 DNS系统。

　　假设有一个网络的子网掩码是 $255.255.(256-2^{8-n}).0/(16+n)$，其中 $0\leq n<8$，将该网络进一步平均分为$2^m$个子网，则第$i$个子网地址为 $255.255.(256-2^{8-n}+i\cdot 2^{8-n-m}).0$。主干网中，若每两个路由器组成一个子网，则每个子网中主机号只要两位（全0和全1不可用），子网掩码可以是 $255.255.255.252$。

　　NAT (Network Address Translation) 是一个解决IPv4地址短缺的补丁，把 private IP address 转换成 public IP address，并通过映射不同端口号的方式区别子网中的不同客户。这种方法弊病颇多，而且治标不治本。更好的解决方式是改用IPv6，不仅扩大了地址空间，还消除了校验、分段和重组，提高了路由器效率。Tunneling 是一种利用IPv4路由器转发IPv6数据报的技术，它将整个IPv6数据报（包括IPv6头部）作为payload，用IPv4头部封装传递。IPv6基本头部格式如下：

　　ICMP (Internet Control Message Protocol): 路由器向数据包源端发送 Destination Unreachable, Time Exceeded, Source Quence 等消息，可用于ping 和 traceroute 等工具。

　　ARP (Address Resolution Protocol): 发送方以广播形式发出请求，目标地址的主机将自己的以太网地址回应给发送方，便于发送方进行IP地址向以太网地址的解析。

　　DHCP (Dynamic Host Configuration Protocol): 客户以广播形式寻找服务器 (DHCP Discover)，服务器（有可能是多个）以一个空闲IP地址作为回应 (DHCP Offer)；客户从所有offer中选一个作为自己的IP地址并正式请求 (DHCP Request)，服务器再次应答 (DHCP ACK)。

References:

　　1. Kurose, James F., Keith W. Ross. Computer Networking: a top-down approach[M]. 北京：高等教育出版社, 2009-08

　　2. Tanenbaum, Andrew S., David J. Wetherall. Computer Networks 5th edition[M]. 北京：清华大学出版社, 2011