log.txt

2015-10-20 09:11:31
两个 link-layer switch (链路层交换机) 能彼此连接吗？
昨儿晚上看wiki说是switch根据MAC-端口映射来转发包，...
google了下，说是可以
之前以为不可以的，这么看来，switch有这样的功能：即不认识的MAC都从特定端口转发出去，之后就由这个端口连接的另一个switch来负责了

2015-10-20 10:26:36
[sim]
https://en.wikipedia.org/wiki/Collision_domain
) 模拟两台直连电脑间的collision
) 模拟三台通过hub(集线器)连接的..的collision

[learn]
https://en.wikipedia.org/wiki/Carrier_sense_multiple_access_with_collision_detection
CSMA/CD

2015-10-23 16:11:08
    sock.listen(backlog)
里头的backlog的含义有必要澄清，这个数是操作系统允许积压的尚未被accept的所有connection request(在这里就是一个SYN包)的最大个数
它说的不是服务器最多能维持几个tcp链接，而是说假如你accept得不够快的话，os最多帮你bookkeeping多少个链接请求

另外socket api里头分为 listen socket 和 data socket
其实在网络层面没这个区分，你 listen 在80就是80，这时还不存在connection，你只是跟os说了声“嘿，如果有人来找80，告我声啊”
(os是永远能收到发给任何端口的请求的，只是如果之前没有进程register在这个端口上，os就自己帮它回绝或者ignore了)
当请求到来的时候，只要有人监听，os就已经自作主张发回了ACK——不管你进程accept没有，这时其实connection就已经有了，在API层面由data socket代表，accept只是跟os取一下这个socket

2015-10-23 16:32:17
protocol定义了某一layer的两个entities之间的交互行为，两个entities可以逻辑上视为直接交互是因为下层layer提供的服务保证了它们正好看到自己层定义的协议
之前某处画的那个5层layer每层entities都交互实际上不准确，因为你看MAC层只能在双绞线两边儿交互，而IP层是确确实实穿过好多路由器交互的
所以更应该画成两边儿5层，中间经过几个3层
叫做53(年高考..模拟..囧)
4、5层直接交互，下面的是在每个hoop间交互的

2015-10-23 18:41:35
未来的学生会不会把Internet当作历史来学习；或者Internet只是更大的星际网络中一个古老的组成部分
连接地球和火星通信网的中间部分采用新的技术，使用新的协议

2015-10-24 14:31:39
关于带宽(bandwidth)和时延(latency)
设想一个传送带，这头儿有个搬运工往上放东西，他放的速度代表了带宽，即每秒能放上去多少字节的东西
传送带的速度以及距离决定了时延，即从这头儿放上去的东西需要多久能到那头儿

换个比喻，从一个城市到另一个城市的货运
我买了一条路，只能跑三轮儿，带宽相当小
你买了一条运河，大集装箱的轮船运，带宽极大

再来个，从地球到木星的链路，带宽不谈，时延大到简直了

最后一说：带宽就是圆柱体的截面

2015-10-26 19:17:24
computer networks (Andrew S. Tanenbaum) p86
这里说的很有意思，之前听说那些智能网络的概念还觉得对不对呀，是不是管得太多了？这里这个场景却确实很合适：
卫星通信是一种很便宜的broadcast——一个卫星的广播可以覆盖1/3个地球，把网络中cache的流量交给这种通信方式，点对点的交给线路通信
及至更细分的将流量类型与基础网络设施匹配的智能化调度，可以优化网络的使用

2015-10-28 19:01:45
https://www.grotto-networking.com/DiscreteEventPython.html
https://simpy.readthedocs.org/en/latest/
做到后面可能会用到simpy以及discrete event技术

2015-10-28 21:59:37
http://rpyc.readthedocs.org/en/latest/
想着用RPC来实现每个终端设备console中对终端的控制
python自带的xmlrpc弱爆了，object instance返回成dict
这个rpyc简直屌，完全是自己想象的样子，学名“transparent sysmmetric”

2015-10-29 12:34:21
感觉从GUI入手会蒙蔽逻辑，写得乱
打算下来先尝试用simpy做一个CLI的版本，然后再GUI化——GUI应该是独立于核心模拟的
也就是说不要GUI也能跑，而且可以有多个不同的GUI实现

2015-11-01 22:59:58
simpy必须用yield，没法二次封装，recv很难写
打算用线程重写，起手后发现不是那么简单——目前感觉至少相当于实现一个simpy的线程版

2015-11-02 09:43:03
有新想法了，琢磨了琢磨发觉用线程实现核心网(port, link)没有意义，做到最后还是各个线程间线性排队跑的，跟simpy一样
才意识到自己真正的需求只是api不要用yield，而这一点通过让用户写的entity逻辑代码跑在单独的线程中就可以
每个port自己维护一些threading.Event()
simpy里跑到相应的地方就给它们 e.set()
然后在用户代码里的wait()中，e.wait(); e.clear()
因为port到entity的关系是一对一的，所以不会有什么问题

2015-11-02 12:18:39
又思索了思索，意识到mint实际上需要支持两种模式
1) 实时网络
    开始运行后，所有线程模拟的那些硬件上，就已经有数据在不断地传输
    用户在GUI中点击某个电脑的send packet，另一边的数据流里，中间某处显出接收到的0101——前后都有线路噪声的0101
2) 逻辑网络
    所有网络中发生的行为都有精确的先后依赖
    比如可以保证pc1发送出1111的时候，链路上正好流过000的preamble

实时网络使用用户提供的entity线程、代码，所以不能用simpy的yield
逻辑网络可以使用simpy
但为了提供一致的接口(即用户代码中，用了mint的同步机制就是逻辑网络，不用就是实时网络)，所以只能使用线程

2015-11-04 11:52:35
之前写到hub就晕乎了，这些天来一直卡卡停停
昨儿跟肖师兄聊这个也聊了挺久
今儿终于搞定啦！精确时序，hub连3个host，啊哈哈哈

2015-11-04 13:13:56
描述一下目前的model:
In the first tik, what have the system done is allow all the entities to put the data (that they want to send) into the system's hardware world (i.e. ports).
Then comes the first tok.
The tok cosists of two phases: output and input.
In the output phase, ports pull the data given to them, set their output symbol accordingly (or '0' if there are no data given).
In the input phase, ports detect their peer's output symbol, convert into bits and push to their entity.

So a `recv` will block in the first tik, and only after the first tok, in the second tik will it be able to fetch one bit.

A tok will transfer one bit along a peered ports, a tik after it then will process this bit.

In the scene of links or hubs, their bit process is take one port's bit and give it to another port, we call this a "port pimp". The take requires one previous tok, and the give occured in one tik. These comprise into a full tik-tok step. So a bit travels along the network path will be delayed on every "port pimper" at least 1 tik-tok. If the pimper it self `wait` in the process, then the bit will be delayed more tik-tok. For example, in a system where a link with latency of 3 linking two hosts, the data transfer latency between the hosts will be 4.

2015-11-04 22:40:18
https://en.wikipedia.org/wiki/Consistent_Overhead_Byte_Stuffing
https://pypi.python.org/pypi/cobs
COBS - Consistent Overhead Byte Stuffing
    一种 framing protocol
    PPP 也会做 framing

https://en.wikipedia.org/wiki/High-Level_Data_Link_Control
https://www.quora.com/What-is-the-purpose-of-bit-stuffing-and-byte-stuffing-in-computer-communication
HDLC 用的是 bit stuffing
好像在asynchronous framming中也会用byte stuffing

https://networkengineering.stackexchange.com/questions/13233/bit-and-byte-stuffing-in-hdlc-frames/13281#13281?newreg=c9fe3315235f42599c1823467da64d4d
看样子说两种stuffing的使用场景不同：
    bit stuffing - synchronous serial link
    byte stuffing - asynchronous serial link (e.g. RS-232)

2015-11-04 23:55:54
http://www.sangoma.com/tutorials/sync_n_async/
这里讲解了 sychronous/asynchronous communication

2015-11-05 08:24:06
https://networkengineering.stackexchange.com/questions/5263/why-is-the-ethernet-frame-size-fixed
这里讲了为啥Ethernet的frame有最小/最大长度限制
主要是由于collision detection的需要，CSMA/CD啥的
这个framing之后再做

https://networkengineering.stackexchange.com/questions/10423/how-long-is-a-frame-really-supposed-to-be-and-when-is-a-frame-a-babble
and mark

2015-11-05 19:29:43
https://en.wikipedia.org/wiki/Code
直接看海明码好晕啊，，一路溯源，从这里看起

https://en.wikipedia.org/wiki/Coding_theory
https://en.wikipedia.org/wiki/Forward_error_correction

https://en.wikipedia.org/wiki/Binary_erasure_channel
https://en.wikipedia.org/wiki/Binary_symmetric_channel
移除信道反而说是最简单的

https://en.wikipedia.org/wiki/Erasure_code
移除编码

https://en.wikipedia.org/wiki/Hamming_distance
汉明距离

2015-11-05 21:12:06
https://en.wikipedia.org/wiki/Block_code
一路到这里，终于能看明白点儿了
block code 就是把一个bit串分成长度固定的一块儿一块儿，然后每块儿通过查字典翻译成某个另外的bit块儿——叫做codeword

2015-11-06 15:10:17
感觉可以暂时略过物理层的error detection/correction
线路错误导致的丢包可以直接模拟(比如不管错没错，NIC丢掉收到的第2个frame)
——因为书里大约意思是CRC这种东西都是物理设备(NIC)来做的，OS根本看不到检错纠错的过程，它只能意识到包到没到层面的事件

2015-11-07 00:12:04
[undone]
http://www.tldp.org/LDP/khg/HyperNews/get/net/net-intro.html
这里最开始的一小段示例代码大约说明了网络通信中buffer空间不足时发生了什么：
通信面向的数据都是分块的(frame, packet, etc..)，当某个块到达时没有足够的buffer来保存它，就丢弃这个块
这样可以保证存起来的数据的integrity——如果只是在比特流中丢弃某些bit，可能造成数据的misinterpretation

2015-11-07 07:52:16
来梳理下理解：
physical layer (layer 1) 提供的服务是

    put_bits_for_send bits
        This put the `bits` in the NIC output buffer.
        As long as there are bits in the buffer,
        NIC will retrieve some bit/bits, encoding into a symbol,
        modulate and output the symbol.
        (Maybe 13 bits ouput parallelly every 1ns on a parallel port,
        which run down a parallel link, reach in another parallel port,
        then enter in a modem.
        Where the modem collect them into its buffer,
        and do it's (probably different) encoding and outputing work,
        say, take 3 bit every 1ms and encoding into a symbol which has
        8 value and modulate into voltage 0.2, 0.4, ..., 0.8 etc and
        output to a serial line.)
        If there are no valid data in the NIC buffer, NIC just keep its
        output symbol intact (maybe 13 zero bits).
    
    get_bits n_bits
        ...(不写了，这么写太费劲)

link layer 的功能是被分成两个部分，分别在OS中和NIC中完成的
OS负责添加control header，然后把 header+payload 的 bytes 交给NIC
NIC负责添加preamble/postamble，bit/byte stuffing，然后把处理后的bits发出去
(问题：bit/byte stuffing 不会影响到比如 hamming code 吗？)
(猜测：NIC的下层功能不管纠错，如果出错，只会影响到某些frame的识别：比如有些该识别出来的没识别到(丢包)，或者不该识别的识别了(这个会由link layer层的后续处理来检测这个frame的非法性))
设想NIC的真实处理过程：
OS请求send (link layer) packet (i.e. header + payload)
NIC通过DMA把OS请求发送的bytes copy到自己的buffer中，注意是从buffer第2个字节开始放的，第一个字节留给preamble
然后发送过程中才在硬件电路上实现bit stuffing
如果在发送过程中(准确说是尚没有可用buffer的时候)OS又请求发送了，那就让它等着——呃，其实准确来说是OS留个口信然后就去干别的事儿了，让NIC不忙了之后自己interrupt

然后是接收
NIC上会检测preamble来识别frame，把识别出来的放在buffer里——所以这里可能是一个frame有最大值限制的原因！因为buffer大小是有限的。
这里要保证buffer至少能容纳两个frame——一个已接收到的fa的和一个正在接收的fb
嗳，其实这么model更好：
NIC有一个有限容量的queue，还有一个容纳正在接收frame的buffer
当一个frame接收完，queue没满的话就把这个frame放进去，满了的话就把frame丢掉
大概意思是这样，实现上具体细节没想清楚——这里的关键是要意识到，线路上的电压是一直变化的，假如1ns是1bit的话，时间过了这个bit没存起来那就丢了

所以终于搞明白 fast sender / slow receiver 的含义了(excited!)：
一个来不及处理incomming frame的NIC是会丢掉来包的，那么sender发的太快也没用，反正这些包都无法被收到，发在网络上还占用网络资源
所以，我们需要flow control

顺便，也明白了slow sender的含义：NIC处理速度有限(OS想发快也不行，NIC没ready它就只能等着——虽然可以干别的事，但发送这茬只能等NIC ready了再进行，因为OS手头的memory也有限呀)，NIC连接的信道bandwidth有限，乃至OS进行协议处理，OS上层application当producer生产数据的速度有限
这些共同决定了sender的发送速度，叫做bandwidth - 56Kbps, 1Gbps, etc..
链路上的波特率可以等价转换成比特率，也是bandwidth
链路的bandwidth，NIC每秒处理字节数的bandwidth，OS协议处理handle的数据的bandwidth，等等，，这些中的最小值决定了sender最终的bandwidth

链路的长度决定了latency：1个bit从这端进去，多久从那端出来

2015-11-07 09:18:32
https://en.wikipedia.org/wiki/Data_link_layer
在看这个，然后忽然想到这么一个场景
a,b,c都连在一个hub或switch上
然后a发了一个frame，里头的source address是假的——是写的b的，destination address写的c的
完了b和c又正在通信，这么着会不会因为a的这个frame而干扰到b跟c的通信？
于是：

https://en.wikipedia.org/wiki/MAC_spoofing
先不看了，等模拟器做到IP层再说——主要是涉及到ARP，完了ARP是涉及IP的

2015-11-07 14:26:15
在重写模型，要确认一下python里list的append之类操作是不是thread safe的

2015-11-07 21:43:06
总是做一段就卡住，然后在费力的思索过后某时又灵光一现
这次是卡在了flow control，不知道怎么model模拟器才能支持fast sender/slow receiver的概念
刚才是在厕所突然意识到，
    
    @proc
    def _():
        a.send('111')
    
    @proc
    def _():
        print b.recv(8)

这样的function/thread们的实质是在定义网络的行为——或者说网络在时间序列中发生的non-trivial的事件(event)
比如这里定义的是：a在时刻0发送111，b从时刻0开始接收，8个tik-tok后，收到足够的bit，然后打印出来
我们可以改写：
    
    @proc
    def _():
        wait(3)
        a.send('111')
    
    @proc
    def _():
        wait(8)
        print b.recv(8)

这样定义的就是：a在时刻3发送111，b在时刻8开始接收——因为port经过8个tik-tok已经收到了足够的bits，所以recv立即返回
而在之前的定义中，recv在没有足够的bits到来时会自动跳到下一个时刻去继续接收

之前做的一个所有非daemon线程结束就将模拟结束的feature，其实质就是当proc定义的网络中的non-trivial event都完成后，就结束模拟

之后想做的那种通过真实application定义host行为的feature，相比现在这种只由单线程定义的host行为，要求更高——比如application中可以开启任意多的线程，甚至进程(此时通过rpyc来进程通信)
那么此时，network中的 worker threads 和 behaviour threads 就是彼此牵制
比如对于一个有限buffer的NIC(Network Interface Controller - 网卡)，host的send也可能block

http://stackoverflow.com/questions/5407182/blocking-sockets-when-exactly-does-send-return
(看，这里就说socket的send (TCP/UDP)可能block - due to lack of kernel send buffer)

这里block的实质跟recv中是一样的，都是通过wait(0)来允许下一个tok的进行，从而到下一个tik中尝试仍然可能失败的接收

之前的model中，内容比较简单，所有的处理其实都是在behaviour thread中做的，而核心网中的port又混杂了一些本应是NIC该做的工作
现在想把port简化到只包含最基本的 output/input symbol 的地步
然后NIC、OS部分的工作放在 worker threads 中——现在是支持一个host多个线程的

NIC和OS的分工是这样的：
NIC只负责bit stuffing和premable/postamble的添加
其余都在OS里做
这意味着link layer是横跨NIC和OS两个部分的——书中也是这么描述的
当然这只是一种人为的划分，比如TOE(TCP offload engine [1])中就把整个TCP/IP stack放在了NIC中

[1]
https://en.wikipedia.org/wiki/TCP_offload_engine

这里的关键是，NIC中有几个线程在跑(具体有几个、分别干什么都还没有想清楚，不过这不是重点，按mint的设计思路，这些都是可以由用户决定的——用户如果愿意，专门开一个线程跑while True也没问题)，OS也有一堆
这要模拟的就是真实的PC机——但是现在自己的问题是... 对操作系统这片迷雾重重的虚拟层，想不明白呀~~

2015-11-11 11:22:52
感觉NIC和OS之间又有线程乱序的问题了：如果两者都是worker thread,
那么在一个tik-tok种可能NIC先pull了frame，然后OS才给NIC发数据

于是似乎应该给所有network掌管的线程都添加一个优先级
actor 最高
os 次之
worker 最次

其实worker的真实含义是 port operator，而且它们在一次tik-tok中要运行两个phase
一个是向port写，另一个是从port读
读一定要严格发生在写之后，这样才能保证能读到初始数据

但是又一想目前阶段似乎不需要做优先级
把OS model到actor上就行了

这样，fast sender 就是一个有大buffer的NIC，配合一个一口气塞满buffer的actor
此后NIC就以最高速率把frame一个接一个地扔到physical link上
slow receiver 呢，就是一个只有一点儿可怜小buffer(比如只能容纳一个frame)的NIC，配合一个recv一个frame之后处理了很久(比如wait(65536))的actor
这样，在actor下一次frame前，第二个frame之后的所有frame都会被丢弃
fast sender就想：咦，咋丢这么多，我真是日了狗了——然后哗哗哗又retransmit了一堆

下来就需要我们实现一个flow control的protocol，这个protocol效果如何呢，可以通过对比使用前和使用后在receiver的NIC上丢包事件的发生频度来衡量
conservative的protocol可能一个包都不丢，但效率不高
aggressive的protocol可能会丢一些包，不过相应地就会消耗更多的网络资源——那些因为receiver buffer不足而丢掉的数据都算作网络传输的overhead了

哦对了，顺便一提，当OS model到actor上时，因为network施加的限制，actor永远不会与worker同时运行，所以actor与worker线程间其实是不存在同步问题的——变量读写so easy!

2015-11-11 12:12:21
感觉NIC不该把byte转换成bits——效率太低了，直接在bytes上位操作输出输入bit估计效率更高些

2015-11-11 15:42:22
以上
但是这么debug起来挺方便的，以后性能成为瓶颈的时候再说吧，，位操作应该还挺麻烦的——主要是bit stuffing要死

现在NIC也做好了——就是说link layer中NIC负责的那部分包括
    framing (preamble/postamble)
    bit stuffing
以及NIC与OS的接口(send/recv)，与physical port的接口(send/recv)
都ok了

下来就可以做flow control啦
...是不是the little book of semaphores又要放了....

2015-11-12 08:36:47
一个刚想到的关于delimiter的事情，在non error free的信道上，以及假设preamble == postamble 的条件下:
对于连续的frames，前一个的postamble应该与后一个的preamble合二为一
对于不连续的frames，每一个应该都包含preamble和postamble
这是为了把链路上的frames分隔成下面的样子

    | frame 1 | non data | frame 2 | frame 3 |

假如 frame 1 的postamble被corrupted了

    | frame 1   non data | frame 2 | frame 3 |

frame 1 会因为 check sum 被丢弃，但不影响之后 frame 2, 3 的接收

如果不这么划分，而是每个frame都带完整的 preamble/postamble 的话

    | frame 1 | non data | frame 2 || frame 3 |

同上corrupted就会变成

    | frame 1   non data | _______ || _______ |
                                    \-- recognized as a empty frame

或者另一种情况：
    | frame 1 | non data | frame 2 | non data | frame 3 |
    | frame 1   non data | _______ | non data | _______ |

这样整个后面的frame都没法正常接收了

2015-11-12 09:00:29
目前做到了只含delimiter的frame发送，链路是假设error free的
OS负责的网络层没有任何header和checksum
用stop-and-wait实现流量控制

这里的场景就像，我想给Bob发frames，但是我开始时是不知道Bob的buffer能容纳多少frame的(根据frame的大小不同，这里的容量可以是动态的——实际应该以当时仍能容纳多少个最大size的frame定义)
我可以假定Bob至少能容纳一个frame——这个可以是硬件制造商保证的，它们的设备至少要符合某种协议的规定(比如Ethernet的1500)

https://en.wikipedia.org/wiki/Maximum_transmission_unit
或者可以动态决定

反正吧，暂时为了简化问题，我们就假设Bob至少可以容纳一个frame
所以我就每发一个然后等他ACK——在等到ACK之前我不会发下一个以免因为他那边容量不足而让我白发
这个就是stop-and-wait

以上是简单的单向的场景，实际中收发是双向的
那么我就得有办法识别我收到的frame究竟是对方传的数据还是ACK？
于是，加上我们error free、point to point的model中第一个link layer的header：
    IS_ACK
这个信息其实1bit就解决了，但是NIC以上都是面向byte的，所以就用一个byte——只用其中一位

       7     6     5     4     3     2     1     0
    -------------------------------------------------
    |     |     |     |     |     |     |     | ACK |
    -------------------------------------------------

现在，frame 的样子是：
    
    ACK + PAYLOAD

ACK字节今后可能会用到其他位，所以判断收到的frame是数据还是ACK的方法是
    
    is_ack = ACK_BYTE & 0x1

于是，双向的stop-and-wait仍然是，收到ACK再发下一个，只不过现在不怕对面有数据frame过来了

2015-11-12 17:45:18
模拟器的核心模型(core model)一改再改，从开始的点对点位传输到现在的流量控制，不断有新的需求导致核心模型无法支持，遂改之
至今已三五番，略心力交瘁
但是每次改好满足新的场景后都很有成就感
跟拉拉说起时云“所以证明这个东西是有难度的”

现在，NIC已经实现——每个host上的NIC跑一个线程
但是到OS这里又不适合了——OS上要跑协议栈
需要新的模型，目前想了一个，但不知道实现后是不是能用/好用
估计到最后的real application in virtual network的场景时还需要新的模型，而且在这之前也会仍不断地更替模型
但是当最后完成时，过程中解决的那些问题想然都可以做一篇研究生的小论文了——甚至毕业论文？倒是不知道这种工程类闭门造车的项目跟论文那种破东西搭不搭调

2015-11-13 10:28:11
ok, 下来要实现一个timer和指定drop frame的功能

2015-11-15 08:47:57
stop-and-wait 的缺点在于，即使 receiver 有足够的处理能力，sender 发出的包之间也最少间隔一个 RTT (round-trip time)
而使用sliding window时，只要window设的够大，就可能在window中的frame还没发完之前收到ACK，这样window往后sliding——如果后续ACK都及时到达，那么sender就可以连续发送，达到线路允许的最高效率
那么window应该设置多大呢？这可能就是不同的sliding window protocols的区别之处了——估摸着还有自适应的算法

2015-11-15 23:21:49
https://en.wikipedia.org/wiki/Media_access_control
https://en.wikipedia.org/wiki/Channel_access_method
这里提到 half-duplex point-to-point links 也属于 multiple access media
想一想就明白了：
比如一根铜线，我在这头加电，那头就会收到信号，但如果那头同时也在加电，那么两边就都无法正确收到对方的信号了
同一时间只能有一方发送的 point-to-point link ，就是 half-duplex link

2015-11-15 23:31:44
https://en.wikipedia.org/wiki/Logical_link_control
flow control 和 ARQ(Auto Repeat reQuest)(包含了error detection/correction) 都是属于 LLC(Logical Link Control) 上子层的
addressing, channel access control 等工作放在下子层MAC(Media Access Control)层中做

这里还说，modern网络一般都不在 link layer 做error detection和flow control之类的了(一般放在传输层或者应用层做)
所以现在LLC只负责multiplexing，但是现今除了IP几乎其他网络层协议都舍弃了，所以其实LLC简直没什么好做的了已经

2015-11-16 08:18:42
https://en.wikipedia.org/wiki/Media_access_control
这里说，“A MAC layer is not required in full-duplex point-to-point communication, but is often available in the equipment for compatibility reasons”
当时做 2-hosts 1-link 时候就现在想，这种从一条线路出去只有一个目的地的链接，frame里是不需要地址的——现在看来果然不需要
link layer 只负责直连的两个节点(通过repeaters, hubs, switches连接的也算直连)间的通信，更远的一条path上的通信是路由器负责的(或者说是IP负责的)

http://www.dummies.com/how-to/content/network-basics-collision-overview.html
这里说的还行，提到“signal combines”
老觉得没理解collision发生的具体方式有点儿虚，但估计其实只理解到collision发生时的数据会坏掉这一层就好了

https://learningnetwork.cisco.com/thread/34158
http://superuser.com/questions/558026/if-two-devices-are-emitting-a-wifi-signal-in-the-same-frequency-at-the-same-time

2015-11-16 13:35:21
channel allocation 中有一个点是，receiver必须知道自己收到的frame有错——之前是信道错误导致bit flip/bit missing之类的
现在是因为collision导致的corrupted frame——当然，collision可能导致任何错误，比如preamble被破坏以至根本detect不到这个frame

于是，之前用直接NIC上的drop模拟出错丢包乃至直接假设为error free信道的做法现在都不适用了
必须要checksum来检测corrupted frame
也就是说，checksum不止是用来检测信号错误的，哪怕信道上没有错误(error free)，但因为collision domain里冲突的发生，仍然会出现corrupted frame

2015-11-16 13:45:07
现在先速度点步进——等到协议层堆上去，模型大方向不差，然后做出GUI和完善的debug机制，然后细细地再走一遍

2015-11-16 16:00:13
自己琢磨着概念性实现了下switch——然后意识到这家伙是 store-and-forward 的，且需要inspect link layer 的 header 信息，比如MAC地址
而hub连buffer都不需要，它根本是工作在物理层的，只能看到baud

http://networkengineering.stackexchange.com/questions/1592/what-happens-when-2-computers-transmits-at-the-same-time-to-a-3rd-one-in-a-full/19788#19788
这里验证了 switch 是存储转发的，正因为此，所以不会有 collision 发生，不同 port 之间属于 different collision domain
但也因为存储转发需要buffer，所以 switch 可能 run out of buffer (比如7个人同时向另一个人发，目标人的outgoing buffer很快会被填满，之后就得开始丢包)
那么猜测 switch 上也实现了 flow control，虽然对于host来说，switch本身是透明的——即没有NIC，没有MAC地址等等

评论里还提到具体实现上因为性能追求，会做成 cut-through 即看到 dst MAC 就开始转发，但是如果因为某些原因发不了(e.g. outgoing queue full)，就 fallback 到 store-and-forward 模式

2015-11-16 16:33:39
https://en.wikipedia.org/wiki/Ethernet_flow_control
这里明确了几点：
1. switch 可以进行 flow control
2. 因为存储转发所以不同端口可以使用不同速率，但这可能造成高速ingress link耗尽低速egress link的outgoing buffer
3. 几个ingress link的数据aggregate起来也会造成egress link的buffer exhaustion
4. 但是ingress/egress link的flow control比host之间的端到端情景要complex一些：因为不是所有ingress来的数据都对某个egress link上的congestion有贡献，所以简单地让ingress link对端降速会错杀好人

https://en.wikipedia.org/wiki/Head-of-line_blocking
这里明确了 input port 有 input buffer
但是 output port 不一定有 output buffer —— 不过这样会造成HOL(Head of line blocking)
比如说i-1端口和i-4号端口队列头部都有一个要给o-2端口发的frame，算法选择了先发i-4的，那么i-1的在i-4发送的时间里就得等着
注意！这时i-1队列里所有不走o-2的frames也日了狗了都得因为队头那个要去o-2的家伙而等着，哪怕它们要去的o-7, o-8等等正空闲着
是不是很像那些直行车等在了人家左转道上的情景？

2015-11-16 17:06:50
http://www.cisco.com/c/en/us/support/docs/switches/catalyst-6000-series-switches/23563-143.html
搜 timeout 有真相
switch 的 forwarding table (MAC addr -> port 字典) entry应该是有保质期的
不然假设这么一个场景：
    b 给 a 发了一包
    switch 不知道 a 在哪，于是 flooding
    a 收到，回发ACK给b
    switch 记录 a 位于 port 1
    a 拔下来了，插到了 port 3
    b 又发了一包给 a
    switch 从 port 1 转发出去，但 a 已经不在那儿了
如果没有保质期，从此所有发给 a 的包都只会走 port1，而可怜的转移到port3的a永远也收不到给它的包了——除非它主动进行了向别人的通信，也许switch会更新a的entry

http://searchnetworking.techtarget.com/answer/Bridge-vs-switch
这里的视角挺有意思：它说对bridge来说，MAC地址其实不像门牌号，MAC只被用来确定它的主人位于哪个网络(port)

之前思索的时候有点纳闷这个事情：看样子switch做的也是routing的工作，那么为什么还要IP层和routers? 是因为历史遗留？不同网络互连？
这里提到一点：
switch会进行flooding，而这对于大网络是不合适的，，router "forward a packet only in one general direction"
a 连在 switch a 上，b 连在 switch b 上
switch a 连到 switch b 和 switch c
a 想给 b 发个frame，但 switch a 不知道 b 在哪，所以它 flood
这个 frame 被同时 flood 给了 switch b 和 switch c
switch b 可以把 frame deliver 到 b
但是注意，switch c 也收到了这个 frame，它也会尝试 deliver to b，而从 switch c 出去可能是半个地球的网络，一路 flood 出去，本来 a 和 b 只隔着一个实验室，结果全球的网络都跑上了它们的 frame

如果把 switch 换成 router，那么在 router a 这里就只会把 packet 发给 router b 而不会发给 router a
所以 switch 和 router 的区别就是，在网络中，switch 的 deliver path 是树状的，而 router 只是一条 path
所以 switch 只适合把小局域网组建成大局域网，更大的网络，为了不让局部通信泛滥全网，就要用 router 来连接子网


https://learningnetwork.cisco.com/thread/41392
这里说 bridge 和 switch "there is no difference except for the number of ports. A switch is nothing more than a multiport bridge."
也有别的说法，不过感觉总的来说，没有逻辑上的区别

2015-11-16 17:53:04
哈，感觉之前明白了 switch 和 route 区别的那个例子可以做成将来 mint-gui 中的一个 project：
显示两个 topology 相同的网络，只是一个 intersection 都是 switch 另一个都是 router
在 host a 上点击发送，switch 网络上所有 host 都会被点亮一下
而 router 网络中，只有途径 path 的LAN上的hosts会被点亮
very demonstrative!

2015-11-17 10:17:16
书里说，"In practive, only switched Ethernet is used nowadays."
也就是说，multiple access 的那些算法在 wired network 中几乎已经不用了
倒是 wireless 会用，而且跟 wired 还不大一样

2015-11-17 12:06:59
半路上再次想要搞懂 电、电线、信号 等等
下了本看上去挺卡通的介绍electronics的书，另外又去google voltage之类
这里
https://learn.sparkfun.com/tutorials/voltage-current-resistance-and-ohms-law

2015-11-17 13:08:54
https://learn.sparkfun.com/tutorials/what-is-electricity
这篇可以理解电子、电流

2015-11-17 15:11:59
感觉还是难在短期或者说有限的精力投入下入门，所以先略过

2015-11-17 17:01:32
ethernet frame 中 destination address 放在 source address 前面，这样 switch 可以收到 dst 后就 cut-through 转发
如果反过来，delay就会更大一些

2015-11-17 17:33:32
hub 逻辑上跟 bus 是一样的，可以想象把bus上每个跟host连接的端点处捏在一处，就变成了了hub
但是有一点区别：
hub 一个端口进来的信号，可以同时输出在所有其他端口上
但 bus 上一个端点进来的信号，需要不同的传播时间到达其他端点上

2015-11-17 22:30:11
书里说switch entry除了dst address, port number外，还有最近更新时间
然后，定期清理过旧的(a few minutes old)entry
不过这也意味着，如果一个host静默了一段时间(即没有发包)，那么它就会被清理——此后发给它的包就得再次flood
不过也只能这样，因为对switch来说，一个不说话的host可能有两种可能：1. 没说话；2. 死了 —— 它没法区分是哪一种，只能按 worst case 来，，否则就会出现之前说过的，host换了个port插上，但是永远收不到发给它的frame了

switch 只看 dst address，不做CRC检查，所以用cut-through来减少frame通过switch时带来的latency

2015-11-17 23:34:29
之前尝试写switch的逻辑时感觉虽然它们用到了link layer protocol，但它们不需要MAC地址——反正switch对host来说是透明的
但书里这儿说构造spanning tree的时候是需要每个switch给它们的邻居发送自己的MAC地址的
那么这个地址是每个switch一个么还是每个port上的NIC一个？还是别的什么？

2015-11-18 09:08:25
https://en.wikipedia.org/wiki/IEEE_802.1Q
看到VLAN的时候一直嘀咕802.1q的frame到底怎么跟legacy frame区分的
这里说明了：802.1q header 中前2个字节叫做TPID，是一个固定的值(0x8100)
也就是说，legacy frame里头，是不允许使用这个值的

2015-11-18 09:15:16
所以其实802.1q tag有两个不同的作用：
1. 指定priority
2. VLAN ID

priority 总是指定的(0代表best effort，就是平常的包)，VLAN ID如果VID的12个比特全0的话，就是指示该frame不归属于任何VLAN

拿到frame给人加了802.1q tag的switch，还要重做CRC计算，，这家伙引入不少latency呃
VLAN这东西普通人一般用不到，所以802.1q能够backward compatible真是很不错的

2015-11-19 10:57:22
看到 interconnect network 这里，明白之前不能只用 switch 来构建 world wide network 的另一个原因是：there are different kinds of networks!
比如 Ethernet 和 MPLS 的编址方式都不同！你想在跑 Ethernet 的 host 上发一个 frame 给 MPLS 上的主机，你都不知道地址该怎么填
比如，Ethernet 要求 MAC 地址，但目的 host 的编址用的是手机号，那么这个手机号怎么往 Ethernet 的 header 里填嘛
解决办法就是，所有 host 都在更高一层 layer 上使用 IP 编址
低一层的 layer (link layer) 只负责在同质网络内部传输数据——比如把 frame 传给作为 gateway 的那个 router

恩.. 之前说的 flooding 原因不能用 switch 构建全网——这并不是不能用MAC统一编址的必然原因，我还是可以用MAC作为任何host的编址，只是因为flooding，所以我用另一种设备 router 来组网就好了嘛
但是 MAC 可能不支持 hierarchy？或者，电脑可以从一个LAN拔出啦接到另一个LAN上，而MAC总是固定的，这就破坏了 hierachy 划分
加之上面说的，有些 host 是根本不用 MAC 地址的！
总而言之，最好的办法是再加一层 layer，用IP统一编址

2015-11-19 11:12:14
学计算机网络有时候会给人一种在学人类科技发展史的感觉——看着人类在几十年的时间里蹒跚学步，用各种方法、技巧搭建起今天这个庞大而还尚不完美(远称不上完美)的 Internet

2015-11-19 15:47:40
https://learningnetwork.cisco.com/thread/15380
每个 switch 都有自己的 MAC address，甚至 switch 的每个 port 都有自己的 MAC address

http://serverfault.com/questions/515163/how-to-find-the-mac-address-of-the-switch-i-am-connected-to
switch 分两种：unmanaged switch & managed switch
unmanaged switch 是没有 MAC address 的
managed switch 有(还可能很多)——正如前面链接里提到的，switch 的 MAC address 其实并不用于 link layer 的工作，，更多的是用于管理(以及spanning tree这个该叫什么来着？)

http://networkengineering.stackexchange.com/questions/10899/why-each-and-every-single-port-on-layer-2-switches-need-to-have-its-own-mac-add
恩.. split horizon rule

2015-11-19 16:08:25
看到 Strict/Loose source routing, Record route 等等 IP Options 的时候就想，妈蛋IHL只有4bits，最大能支持15个 header entry，默认又已经用掉5个，就剩下10个，，完了选项本身还要用掉一个，剩下能指定的IP最多也就9个，这哪够
然后就看到书里说了，ARPANET创建的时候，没有任何packet会经过超过9个router，所以Options就这么设计了，，现在么，当然不够了

2015-11-19 17:11:21
p450 "Perhaps some day people will look back and fault the folks who designed the telephone number scheme and say: 'What idiots. Why didn't they include the planet number in the phone number?' But at the time, it did not seem necessary."
真是感慨... 我们回头看classful addressing (of IPv4)时的感觉，正像未来的人类看我们的感觉

2015-11-22 09:36:51
之前几天不写重拾起来感觉有点儿把控不住那1000行代码了
这次重写是因觉着了正交化的必要——可以把线程管理外包给 timpy (自己写的 thread 版的 simpy)
以及，要简单！能分隔出去的特性尽量分隔出去，哪怕为此增加代码量，也要保持每个 logical unit 自身的紧凑——即只做一个概念下的事情

下面是思索 timpy 的部分：

a simulation has the following attributes at any moment:
    
    unscheduled events
        unknown to sim-controller, kept by user, but may be scheduled
        onto `timeline`
    .timeline
        keep scheduled events in ascending `now` order
    .now
        current simulation time
    .events
        events which has the same `now` with sim.now
        all triggered but the waiters is still waiting to be resumed
    .waiters
        waiter threads of which waiting event has been triggered
        eager to be resumed
    .resumings
        waiter threads which has the same priority

the following methods do the actual advance of time

    .step_single_waiter
        resume a single waiter
    
    .step_priority_group
        resume all the waiters with same current highest priority
    
    .step
        resume until the waiters have a different `now`

2015-11-22 17:00:48
正好，需要实现一个 heap

2015-12-01 09:28:51
https://en.wikipedia.org/wiki/Data_terminal_equipment
https://en.wikipedia.org/wiki/Data_circuit-terminating_equipment
发现计网作业里的有些问题还挺insighting的
比如这个东西，不查还真不知道

https://en.wikipedia.org/wiki/Twisted_pair
UTP 仔细看看也许能明白信号、线路的一些东西

2015-12-01 10:35:22
给host们赋了ip，开写 Host.l3send 的时候意识到需要ARP了
否则l3的用户说：“给我把这个发给1.0.0.2”，l3要用l2的send
而l2的send是这么定义的：send(data, dst_mac)
l3手里拿着个dst_ip，却要用dst_mac才能发送
怎么办？ARP + cached ARP table

但是问题来了，ARP packet 包在 l2 frame 里之后，recver 怎么知道拿到的 frame 里是什么东西？arp? ip? 还是别的什么？
我们知道 Ethernet frame 里有个 EtherType 的 field
https://en.wikipedia.org/wiki/EtherType#Examples
    0x0800 IPv4
    0x0806 ARP
    0x8863 PPPoE Discovery Stage
    0x8864 PPPoE Session Stage
    ...

当时不明白的是，不是来了个802.3把人 EtherType 给改成 length 了嘛
那么 802.3 的 frame，recver 是怎么判断 l2+ packet 的类型的？：
http://www.danzig.jct.ac.il/tcp-ip-lab/ibm-tutorial/3376c28.html
这里点明了，packet里还有个802.2的header，这里指定了type

呃，我自己写就先奔 Ethernet 去吧，，简单~~

2015-12-01 14:28:12
3000行了
ARP实现了一半

2015-12-02 12:09:07
目前的模型又有点捉襟见肘了
在思考一个新的模型，另外想借此机会把性能提上去(通过底层不使用bit stream的方式——直接发frame，之后如果需要用逻辑效果实现bit error等事件)
另外因为一路爬升摸到了些transport layer的模样，现在结合这个思索OS模型

对于host:
os维护一个sockets的列表，下头是一个NIC
nic通过interrupt与os互动(也可以让os来poll，不过看样子interrupt的方式可以简化之后的协议编写？)
    INT_FRAME_SENT
    INT_FRAME_RECVED
os在 frame_sent handler 中轮询 sockets 的状态，如果有谁需要发送，就拿它的数据交给nic——这里就涉及到socket priority的概念了，不能starve某个socket

另外又想到，可能维护的除了socket还得有别的potential sender——比如ARP这种位于transport layer之下的，但是也要发包

2015-12-04 23:51:24
开始写router了——又一次感觉到，当你真地去着手实现一个东西的时候，情势会逼你思考乃至真正理解这个东西

2015-12-05 14:45:18
https://en.wikipedia.org/wiki/Default_gateway
http://superuser.com/questions/59996/what-does-on-link-mean-on-the-result-of-route-print-command
每个机器上都有一个route table
windows 上可以 route print 来显示
所以其实route这件事在我们本机上就已经在发生了
比如我发给192.168.0.3的packet被os识别为on-link——即同一个ethernet网上的
而发给30.201.18.4的packet就会被forward给default gateway——目测是北邮的某个路由器(10.203.6.193) —— 连接的时候通过DHCP得到的

2015-12-05 15:32:31
http://unix.stackexchange.com/questions/94018/what-is-the-meaning-of-0-0-0-0-as-a-gateway
route print 会在某些entry里显示gateway为 On-Link，某些项为一个router的具体IP，比如10.203.6.193
于是困惑操作系统在数据上是怎么构造这个 On-Link 的值的，查了查，应该是 0.0.0.0

https://en.wikipedia.org/wiki/0.0.0.0
0.0.0.0这家伙在不同语境下有很多种不同的含义
) DHCP Request里头用作 Source IP——因为host此时还没有取得IP，它就声明自己是0.0.0.0
) 用在 route table 的 destination network 栏时，意指任意网络
) 用在 route table 的 gateway 栏时，意指“无”(比如VMnet1的Default Gateway会显示为空，就是因为值为0.0.0.0)

0.0.0.0不能作为 destination address，顶多能用在 source address 中(DHCP request)

2015-12-05 15:52:22
https://wiki.wireshark.org/Gratuitous_ARP
免费ARP

http://networkengineering.stackexchange.com/questions/5418/understanding-arp-and-routers
arp 和 route table 的关系
不在同一个网段的机子想通信，不会直接ARP彼此，而是ARP gateway，packet是交给gateway转发的

2015-12-06 17:34:05
http://www.infocellar.com/cable-dsl/routes.htm
ARP cache table 只会存储“本地”信息——本地的意思是，local ethernet network (通过switch, hub连接起来的) 或者 subnet (同一个ip网段——有相同的网络号)
所以只有 routing table 中属于 on-link 的那些 entry 才会涉及到 ARP

windows 上可以 arp -a 查看 arp cache
貌似是每个 interface 对应一个 table

2015-12-06 23:25:43
实现了静态路由的router，刚跟github上看自己的repository，都6W+ addition 3W+ deletion 了~~
系统一路演化过来，每一个阶段都要走到摇摇欲坠和破而后立的时候
此时尚在新王朝建立后中期的程度，各种不稳和不合的苗头才有一点，但总的看上去还是太平盛世——还能利用一段时间
可以想见的一些问题将来肯定是要面对的，比如性能(对于以后大规模网络的模拟)，比如架构(目前router和host共用interface的部分，概念就有点儿混乱，之后协议复杂化现实化后可能就不合适了)

2015-12-09 22:13:50
https://en.wikipedia.org/wiki/Dynamic_Host_Configuration_Protocol
http://serverfault.com/questions/294457/what-do-dhcp-lease-time-and-domain-name-do
DHCP的过程如下：
我们的电脑刚启动时是没有IP的(准确地说是某个网卡-interface)
然后我们的电脑会broadcast一个UDP包，问：“谁能给个IP用啊？” [DHCP Discover]
我们电脑所在的子网上如果有DHCP server(或者DHCP relay)，就会给我们发offer：“我有我有，你用这个IP吧” [DHCP Offer]
然后我们的电脑在拿到的offer中选一个，仍旧broadcast说：“我用这个IP了” [DHCP Request]
然后被request的那个DHCP server就会给我们发来ACK：“好的” [DHCP Ack]
我们的电脑在收到ACK后，就可以开始使用这个IP了

除了IP，DHCP还会配置子网掩码、默认网关、DNS服务器等等


DHCP lease的ip是有租期的，上面那个SO里说大约租期过半，我们的电脑就会请求续租(DHCP Request?)
如果我们够decent，还会在关机前发个DHCP release——不过这个不要求
DHCP是君子协定，服务器计算某个IP到期后就认为它可以分配给别的电脑了，，如果我们强行使用，就会在子网上造成IP冲突

2015-12-10 15:26:54
聊聊目前的状况
实现了基础的网络架构——Host, Link, Switch, Router
可以在链路上发 bit delimited 的 frame
实现了原型的 Ethernet, ARP, IP, UDP
目前打算做 DHCP，之后是 TCP, HTTP，以及 NAT

代码已经有了混乱的迹象，在整个协议栈原型上过一遍，了解了都有哪些使用场景之后，会整体重构(其实是重写啦~)一下，，加上性能的考虑

2015-12-10 18:55:59
我艹 DHCP 协议实现起来真是费劲
整体代码又到3K行了

2015-12-10 22:06:01
tcp有点儿复杂，一时写不出来，，今儿写晕了已经
等以后头脑清醒了，先仔细爬爬wiki再说

2015-12-11 09:43:56
因为整docker翻墙的东西跑来看SOCKS，干脆也写在这儿吧

https://en.wikipedia.org/wiki/SOCKS
"a SOCKS server proxies TCP connections to an arbitrary IP address, and provides a means for UDP packets to be forwarded"
也就是说，至少我们Bandwagon VPS上的 ShadowSocks Server 是可以 proxy TCP 和 UDP 的
也就是说，TCP和UDP之上的 HTTP, HTTPS, FTP, DNS 等等都可以了

https://pypi.python.org/pypi/shadowsocks
下了个shadowsocks的源码(Python写的)，看样子client和server都有，总共也不多，3K行

2015-12-11 11:48:09
擦.. 暂时看不懂——主要是觉得没精力，，以后吧

2016-08-03 14:35:09
https://www.zhihu.com/question/21484361
程序员工作只接触一些不需要高难技术的小项目，该如何提高自己？

里面提到不少网络相关的程序，可以想象自己最后把mint做成一个活跃的虚拟世界的互联网，上面跑着各种各样的应用程序，会挺有意思的