Week5
Technology: Internets and Packets
新年好！（￣▽￣）
Layer1: Link
Keywords: Packet, Shared Network, Layered Network Model, Link Layer, Ethernet, Bob Metcalfe
Introduction/ The Link Layer
从本周开始，我们终于完成了History部分，要转向Technology部分的讲解了。
回顾一下历史，上世纪60-80年代用的最多的还是Store and Forward Networking网络（Week2的笔记）。其实仔细分析来说这种网络没有太多的sharing的成分，只不过是按部就班地输送一些信息。要如何解决一些诸如如何处理网络中断、如何分享链接、如何处理信息堵塞这样的问题？80年代的创新成果就是packet switch network，ARPANET。因为涉及到了很多新想法，所以这项技术从研发到成熟花费了20年甚至更多的时间。更多细节可以到week2中去领略一番。
ARPANET带领我们进入一个新思路：Shared Network，数据的传送思路从由只有一个强大的电脑负责转发数据包，转换到了由多个非常小的电脑去专门负责把数据往下一个目的地运送，这就是路由器。和以往的长途传递不一样，每个路由器只负责很短的一段路，而且只做短期存储，主要目的是往下一个路由器进行传送。另外，有一个核心思想就是把一大段信息分成许多个packets。例如密歇根大学的所有电脑、服务器组成一个当地网络，通过路由和packet switching 技术将想要发送出去的信息发送出去，信息会经由路由找到正确的道路到达目的地，就形成了通信，也就是Internet。
Shared Network的基本原理着重于packets。hop的理念是依然存在的。信息从你的服务器中输出要跳跃到第一个路由器，然后不断在路由器之间hop、hop、hop……hop，就蕴含着很多的问题需要解决，为了简化解决方案，使其清晰、可管理，人们就想出了一个叫Layered Network Model（分层网络模型）的东西，就是类似于框架、骨架那样的东西，所有的东西都按照这个来展开。
这个模型做的工作并不是一下解决一个大问题，而是把许多的大问题分解成一个个的小问题。他们想解决的大问题比如要确保稳定地实现信息的传输，但如果按照这四部分分解，各个攻破。解决了所有小问题，大的问题也就能实现，思路也更加清晰。
有时面对一个极其复杂困难的问题，将其分解成小问题有助于我们分析思路，提出更好地解决方法。不过如何分解问题也是一种艺术，所以就存在不止一种网络模型，不仅存在我们现在提到的这种四层分层，还有OSI（Open System Interconnection model)，它有七层。
如果想要按照Layered Network Model的四层模型去分解问题，那么就需要去设计协议文档，document来解决一些问题。例如这四层到底是如何定义的？各自掌管哪些方面的问题？互相之间如何共同协作？不同的计算机之间如何工作？路由器如何工作？等等等等。协议文件就是解决互联网中所有组成部件如何共同协作的问题。
图片。
接下来就看看协议的内容究竟是什么样。
第一层：Link Layer（aka Physical Layer）
不要忘了，我们建立这种四层模式的初衷是为了简化问题。所以在第一层Link Layer，链路层的解决问题重点还是在于如何在物理层面上实现传输数据。虽然这个问题可能很复杂，但在这个Link Layer上，我们只需考虑这个问题，不需要考虑别的，这也是分层考虑的好处。
信息传送到目的地可能需要经过很多种的传输介质：有线、无线传输、光缆……等等。不过一段光缆，长40英里也好，长40英尺也好，都是一个link。一个link就是一个hop，这就需要路由器，路由器从一个link中把数据拉下来然后推向下一个link。打比方来说吧，人们寄信，首先邮局从你家的邮箱里把信件拉走，这时你的信可能是放在邮递员的自行车上，后来你的信上了卡车、然后又上了火车、……这就是一个个link。一个个邮递员、卡车、火车就是Link Layer的组成部分。这里面很重要的一点就是每个邮递员、或者每种交通工具并不是就把你的信直接送到收信人手中，而信只是在每个环节都只是向目的地更加靠近了。这就是Link Layer的思路。
Ethernet就是一种应用极其广泛的Link Layer。硬件制造商在制造带有以太网或者无线适配器的电子器件时，都会带有一系列的字符去标识这些硬件。这一列字符的特征是六组两两结合的字符，包含字母和数字。这其实属于一种物理地址，硬件之间就是通过这个来识别的。举个例子，在一个房间里，有一个wifi环境下可能有很多台电脑在共享同一片空气。我们必须解决如何共享的问题，物理地址就是解决方法——在packet中用物理地址标记发送方和目的地。回到刚才那个例子，在一个WiFi环境下，电脑A想和电脑B通信，电脑C在接收到他俩之间的通信时，能通过物理地址知道自己不属于这场通信。这样Shared Network
就能正常工作。
Link Layer要解决的另一个很重要的问题是如果出现了冲突该怎么解决？老师说了数据传输has a lot to do with courtesy。好比如果所有司机们文明行车，红灯停绿灯行，那么交通就不会乱，不过理想是美好的，现实是残酷的，总有那么些人不文明行车，会导致一些混乱的发生。前面提到Ethernet是一个很不错的Link layer。Ethernet解决这个问题的方案叫做Carrier Sense Media Access with Collision Detection，虽然总的我不太清楚怎么翻译，但能看到Collision，也就知道是发生冲突了。Packets如果遇到了冲突，那么势必会降低网络的传输速度。如果一个Link Layer不能很好的解决这个问题，那一定不是个好的Link Layer。
下面仔细的介绍一下Ethernet的方案。在我们要传输数据时，先Listen。先听听信道里面有没有东西在传输，如果有我们就等，如果没有我们再开始传输。如果已经有人在占用了，我们就要等待他完成他的传输。传完之后，我们还要listen，如果能清晰地听到我们的数据，就说明传输得不错，但如果不能听见，这就说明遇到了两台电脑同时传输了信息，导致了冲突的问题。所以两台电脑都得各退一步，不过这时就需要用到有点儿复杂的随机数运算，两台电脑退的步数不是相同的，这样就不会退步了之后再传输结果再冲突了。不得不说，非常文明啊。在社会中，也是要按照规则来办事效率是最高的。
接下来我们就去接触一下以太网的发明者Bob Metcalfe，让他告诉我们一些以太网的故事。
Bob Metcalfe - The Ethernet Story
继承和发展，随机重传过程
Bob Metcalfe原先是在Xerox Palo Alto Research Center工作，研究的内容是个人计算机（PC）上面的网络方面的架构。当时对packet switching和ARPANET的研究已经基本完成。Bob他们设计出来了第一架镭射打印机，名字是Ears（为什么打印机的名字叫耳朵。。），不过他说这个是不是第一个还是有争议的。为了尽可能地提高这台打印机的效率，解决其与计算机的连接问题，逐渐转变了Bob的工作方向。在Bob之前有一个研究成果叫做Signet，是由Charles Simony开发的，后来Bob接手了这份工作。Charles Simony后来去开发了一个文本编辑器叫做Bravo，也就是后来大名鼎鼎的Microsoft Office 系列，也让他成为了亿万富翁。BTW，Signet的全称是Simonyi's Infinitely Glorious Network。（西蒙尼の无限荣光网，这名字可真tm够中二的……）不过Signet已经有很多理念和今天的LAN（Local Area Network，局域网）很相近，可以说是一个很超前的设计。
在夏威夷大学，Bob开始研究一个关于LAN中如何协调分配的问题，有一个成果就是Aloha Net，它解决了很多packet分配方面的问题。例如在夏威夷岛上有许多的收音机，如何让它们共享频道？夏威夷大学有许多的终端，如何在互相通讯时保持协调？以及涉及到上文提到的随机重传过程的原理（randomized retransmission procedure）。
Manchester coding
BTW，Bob提到他的愿景是只有一条电缆，而不是16条或者32条甚至更多，他的办公室由于网线太多，被称为老鼠窝（rats’ nest）所以要为共享网络设计原理。Bob说这里有一个关于硬件的故事和一个关于软件的故事，他自己是偏软件的。不过有一天，他去买了一公里的网线回来，在一端连接上信号脉冲发送器，并在另一端连上示波器观察信号的输出。他发现当他在这一段发送方波时，另一端出来的不是方波而是类似于正弦波，有上下缓慢起伏的波形。不过，Bob放上了一个digital gate之后，就又能获得方形波了。（数字、门，我想到了逻辑电路，不过我还没学。。）也就是说，Bob发现了这种恢复波形的方法，也就是说能进行传输了。
Bob他们把这个方波称为Manchester，并在传输时进行编码，叫做Manchester coding， 因为不太懂，所以看了一下wiki应该是和逻辑电路有关，而且之前我也了解过CPU时钟频率什么的，不过不太懂，所以贴下英文原文和wiki地址吧。
编码方式十分简单，每个bit的前一半只是起补充作用，后一半的bit才是真正起传输作用的。wiki中feature说明Manchester coding确保线电压转换频繁，时钟频率成正比，这有助于时钟恢复。我没打全看懂，但现在知识储备还不够，之后回看的时候应该能更有收获。
Manchester Coding的好处就是传输数据是连续的过程。在探测传输有无冲突时，不需要长时间的耗费，只需要花费短时间即可知道是否有信息正在传输。
cyclic redundancy checksum
Ethernet和Aloha network（之前夏威夷大学研发的一种技术）相比，有一个优势，就是前者可以检测出是否有信息正在被传输，可以避免传输冲突。
第二个特点是完全是数字信号了，而不是模拟信号。计算机科学家在研究这个东西时，和无线电专业的人士有很多合作。当时为了研究这个，浪费了大量的带宽。
Bob也提到了，每个packet携带着两个各8位的物理地址，这与Aloha Network相比也有改进，后者只含一个地址。在packet的后面，还加上了cyclic redundancy checksum （循环冗余校验）技术，wiki页面，这项技术广泛应用于硬件设计方面，能够检测出信息数据是否被损坏。如果发生了信息传递的冲突，那么就会有信息垃圾堆积在信道里，后续要传递的信息也会发生堵塞。Bob做的工作就是把这些无用的信息扔掉。
前面说过，Bob的方向偏软件，不是很擅长硬件的操作。他认识了一个人，叫做David Boggs，此人擅长硬件，后来和Bob一起合作，是Ethernet的另一位创造者。
前面提到，Bob不想让电缆连接成rat nest那样杂乱。于是他们只设一条主路，每当有新的电脑要连接进入时，只是增加一个分支（tap）。Bob也不希望，每次增加分支会导致网速下降。所以后来他们创建了gerald tap，解决了这个问题。
以太网在一开始就有2.94MB/S的速度，不过在 Xerox 时，很快发展到了20BM/S。在802标准中，规定为10MB/S。
Problems link layer solved
小记
这次内容挺多的，就分成两部分吧。春节前几天出去玩，所以就耽误了点进度。祝大家新春快乐。