计算机网络笔记(6)

基本数据链路层协议

协议1:一个乌托邦式的单工协议

单工协议即数据只能单向传输。这个协议假设信道永远不会丢失或损坏帧,接收方的处理能力足够快,缓冲区足够大。

发送程序无限循环,接受程序响应事件,协议1中不包含流量控制和纠错功能。

协议2:无错信道上的单工停-等式协议

发送方的速度如果过快,接收方会被淹没,除了增强接收方的处理能力,可以让接收方给发送方发送反馈,发送方收到后才可以发送下一帧。

发送程序无限循环并等待接收方确认,接受程序响应事件后发送确认帧。

协议3:有错信道上的单工停-等式协议

有错信道上传输数据需要增加校验,接收方仅在数据正确时发送确认帧。但在确认帧丢失的情况下(超时),发送方将重发。接收方难以判断帧是重发还是新发,因此帧前加上序号以区分。

重复的帧也会收到确认帧,以便发送方决策。

计算机网络笔记(7)

回顾

帧同步、差错控制、对等通信协议

乌托邦协议、简单流量控制、出错重传(定时器、序列号)、捎带确认

发送窗口的大小等于能够发送的帧的数量

数据链路层和传输层使用滑动窗口协议

滑动窗口协议

全双工:任何一方即是发送方也是接收方。

捎带确认:确认并非单独的帧,而是被附加到数据帧。

序号:任何帧都有一个序号,确认帧也包含被确认帧的序号。

窗口:窗口是一个环,并且存在上下界。发送方窗口内的序号代表那些可以被发送或还未收到确认的帧。当有新的包从网络层传来,它被赋予最高序号的下一个序号,同时窗口上边界前移一个序号。收到确认帧后,窗口下边界也前移一个序号。

对于接收方,如果接收到的帧的序号等于窗口下边界,那么下边界前移,如果落在窗口内,那么放入缓存区,落在窗口外则被丢弃。在任何情况下,接收方都要发送确认帧,这可以为发送方的行为提供决策依据。

协议4:一位的滑动窗口协议

发送窗口大小=接收窗口大小=1,效率极低。只有窗口大于1才能提高信道利用率。

特殊情形

如果超时时间过短,那么每一帧都可能被发送多次。

当双方同时开始发送,会出现如下情景:发送方收到带有确认信息的帧,但确认信息不正确(发送方发送的第一帧也含有确认信息),导致双方都必须重发。

PS:我感觉第一帧如果能特殊标记,那么也能够避免第一帧携带的确认信息+同时发送导致重发的情况。

协议5:回退n

发送窗口大于1,接收窗口等于1。出错时重传帧数多,适用于信道质量好,出错率少的情况。

阻塞前发送的帧数

w<=1+2BD,具体参考https://www.guohere.com/4613.html的20题。

可发送帧数与序号

可发送帧数在协议5中并不等于序号空间的大小,而是要-1,因为在确认帧丢失并重发的情况下,接收方需要判断新的一批是新帧还是重发帧。

协议6:选择重传

发送窗口和接收窗口都大于1,ack累计,出错时可以累计重传,可以否定重传。于是接收方可以只丢弃错帧,发送方可以只重传出错帧,适用于信道质量不好的情况。

接收方的窗口大小要小于等于表达第n帧的状态数,否则窗口重叠会导致无法辨认重传信息属于哪个窗口。发送窗口一般等于接收窗口,接收窗口必须小于能表达的窗口序号/2。

了解概念

HDLCHigh-level Data Link Control)协议

面向连接:协议建立、释放逻辑连接

流控制:滑动窗口协议,有序号和确认

差错控制:使用回退n帧协议或者选择重传协议

PPPPoint-to-Point Protocol)协议

面向字符的数据链路协议,字符填充成帧,面向网络层的IP协议,具有差错控制、身份认证功能

ADSL

广泛用于通过本地回路宽带接入

链路层总结

帧同步、差错控制、协议

第四章介质访问控制子层(Media Access ControlMAC

概念

MAC层介于物理层与数据链路层之间,Link层包括MAC和LLC。

以太网(Ethernet)包括经典以太网与8028.3Ether ne

数据通信方式

单播(unicast):点对点

广播(broadcast):全部可以传输,信道共享。MAC算法使广播基于规则而平等。

组播(multicast):一组中的广播

动态分配信道

ALOHA协议

无线中,设备随时可以发送信息,由于可能冲突而浪费信道容量,闲时很高效,忙时几乎无法避免冲突,信道利用率只有18.4%。

时隙(SlottedALOHA协议

时间分槽,时间被分成很多固定长度(一帧的传输时间)的时间片,设备在任意时间片开始时发送信息,减小了冲突的可能(只可能发生在同一时间片),信道利用率36.8%

载波侦听多路访问协议(Carrier Sense Multiple AccessCSMA

CSMA的特征是“先听后发”,是对ALOHA协议的改进。

非持续式:侦听信道,介质空闲时发送,介质忙时等待一个随机时间,再忙再重复。会由于等待的随机时间浪费信道容量。

1-持续式:侦听信道,介质闲时发送,忙时持续侦听,一旦空闲立即发送,如果冲突,等待一个随机时间再继续侦听。多个设备准备发送时,由于侦听到同一空闲,会发生冲突。

p-持续式:侦听信道,如介质空闲,以p的概率发送,(1-p)的概率等待随机时间。如介质忙或等待了一个随机时间,持续侦听,空闲后重复步骤一。

冲突域(物理层概念):数据包产生和冲突的网络区域,存在共享媒质区就一定存在冲突域。CSMA即使侦听到空闲,仍然有可能冲突,原因有两点:同时开始的传输、介质中的传播延迟

Json Web Tokens

这篇文章是对网络上相关信息的总结,详情可以参考《JSON Web Token 入门教程》

http://www.ruanyifeng.com/blog/2018/07/json_web_token-tutorial.html

使用JWT

JWT作为一道具有过期时间的令牌存储在Cookie或localStorage,与服务器通信时都会捎带上。既可以写在Cookie里,也可以放在HTTP头中,还可以写在具体的请求里。

JWT结构

JWT由3个JSON对象组成,最终的JWT是经过转码(参考Base64)的字符串。

Header

键包括alg(algorithm)与typ(type),指出了签名算法与令牌类型。

Payload

JWT传输的信息,键包括生效时间、过期时间、签发人等。

Signature

在服务器上用密钥生成Header与Payload的签名,防止JWT信息被篡改。

JWT注意事项

  • JWT默认不加密,有需要可以加密
  • 如果不加密,建议使用HTTPS协议防止被盗用
  • JWT有效时长无法更改,不建议设置时间太长

简析依赖反转与依赖注入

他们都用于降低耦合度。

依赖反转(Dependency inversion principle, DIP)

在一个有层级结构的软件系统中,低层向高层提供服务,而高层利用低层的接口继续向更高层提供服务,达到了构建复杂系统的目的。在这个过程中,高层的实现依赖于低层,低层决定了高层应该如何实现。

依赖反转让低层也依赖于高层,怎么做到呢?将高层对低层的依赖抽象为接口,低层只需要去实现接口就好了,于是高层与低层都依赖于接口。这么做的好处是高层与低层可以分离,我们可以为系统开发插件或其他需要在低层运行的包。

依赖注入(Dependency Injection, DI)

依赖注入是实现控制反转(Inversion of Control, IoC)的最常用方式。

控制反转的重点是,将对象需要的对象的引用全部传入,但只是使用而不控制这些对象的新建或销毁。传入的方法可以是通过构造函数、设置属性、接口,这是依赖注入的过程。

IOC Container

IOC组件或框架,用于减少重复实现IOC的代码。

Mixin一句话介绍

我们通常通过类的继承实现类的复用,但复杂的继承关系会影响程序可读性。Mixin不能单独使用,而是作为方法集合向类提供功能,既实现了代码复用,又降低了复杂度。

Mixin与多继承的区别在于后者容易导致代码复杂,Mixin与接口的区别在于后者不带实现。

转载:POST请求的Content-Type

https://imququ.com/post/four-ways-to-post-data-in-http.html

application/x-www-form-urlencoded

这应该是最常见的 POST 提交数据的方式了。浏览器的原生 <form> 表单,如果不设置 enctype 属性,那么最终就会以 application/x-www-form-urlencoded 方式提交数据。请求类似于下面这样(无关的请求头在本文中都省略掉了):

BASHPOST http://www.example.com HTTP/1.1
Content-Type: application/x-www-form-urlencoded;charset=utf-8

title=test&sub%5B%5D=1&sub%5B%5D=2&sub%5B%5D=3

首先,Content-Type 被指定为 application/x-www-form-urlencoded;其次,提交的数据按照 key1=val1&key2=val2 的方式进行编码,key 和 val 都进行了 URL 转码。大部分服务端语言都对这种方式有很好的支持。例如 PHP 中,$_POST['title'] 可以获取到 title 的值,$_POST['sub'] 可以得到 sub 数组。

很多时候,我们用 Ajax 提交数据时,也是使用这种方式。例如 JQuery 和 QWrap 的 Ajax,Content-Type 默认值都是「application/x-www-form-urlencoded;charset=utf-8」。

multipart/form-data

这又是一个常见的 POST 数据提交的方式。我们使用表单上传文件时,必须让 <form> 表单的 enctype 等于 multipart/form-data。直接来看一个请求示例:

BASHPOST http://www.example.com HTTP/1.1
Content-Type:multipart/form-data; boundary=----WebKitFormBoundaryrGKCBY7qhFd3TrwA

------WebKitFormBoundaryrGKCBY7qhFd3TrwA
Content-Disposition: form-data; name="text"

title
------WebKitFormBoundaryrGKCBY7qhFd3TrwA
Content-Disposition: form-data; name="file"; filename="chrome.png"
Content-Type: image/png

PNG ... content of chrome.png ...
------WebKitFormBoundaryrGKCBY7qhFd3TrwA--

这个例子稍微复杂点。首先生成了一个 boundary 用于分割不同的字段,为了避免与正文内容重复,boundary 很长很复杂。然后 Content-Type 里指明了数据是以 multipart/form-data 来编码,本次请求的 boundary 是什么内容。消息主体里按照字段个数又分为多个结构类似的部分,每部分都是以 --boundary 开始,紧接着是内容描述信息,然后是回车,最后是字段具体内容(文本或二进制)。如果传输的是文件,还要包含文件名和文件类型信息。消息主体最后以 --boundary-- 标示结束。关于 multipart/form-data 的详细定义,请前往 rfc1867 查看。

这种方式一般用来上传文件,各大服务端语言对它也有着良好的支持。

上面提到的这两种 POST 数据的方式,都是浏览器原生支持的,而且现阶段标准中原生 <form> 表单也只支持这两种方式(通过 <form> 元素的 enctype 属性指定,默认为 application/x-www-form-urlencoded。其实 enctype 还支持 text/plain,不过用得非常少)。

随着越来越多的 Web 站点,尤其是 WebApp,全部使用 Ajax 进行数据交互之后,我们完全可以定义新的数据提交方式,给开发带来更多便利。

application/json

application/json 这个 Content-Type 作为响应头大家肯定不陌生。实际上,现在越来越多的人把它作为请求头,用来告诉服务端消息主体是序列化后的 JSON 字符串。由于 JSON 规范的流行,除了低版本 IE 之外的各大浏览器都原生支持 JSON.stringify,服务端语言也都有处理 JSON 的函数,使用 JSON 不会遇上什么麻烦。

JSON 格式支持比键值对复杂得多的结构化数据,这一点也很有用。记得我几年前做一个项目时,需要提交的数据层次非常深,我就是把数据 JSON 序列化之后来提交的。不过当时我是把 JSON 字符串作为 val,仍然放在键值对里,以 x-www-form-urlencoded 方式提交。

Google 的 AngularJS 中的 Ajax 功能,默认就是提交 JSON 字符串。例如下面这段代码:

JSvar data = {'title':'test', 'sub' : [1,2,3]};
$http.post(url, data).success(function(result) {
    ...
});

最终发送的请求是:

BASHPOST http://www.example.com HTTP/1.1 
Content-Type: application/json;charset=utf-8

{"title":"test","sub":[1,2,3]}

这种方案,可以方便的提交复杂的结构化数据,特别适合 RESTful 的接口。各大抓包工具如 Chrome 自带的开发者工具、Firebug、Fiddler,都会以树形结构展示 JSON 数据,非常友好。但也有些服务端语言还没有支持这种方式,例如 php 就无法通过 $_POST 对象从上面的请求中获得内容。这时候,需要自己动手处理下:在请求头中 Content-Type 为 application/json 时,从 php://input 里获得原始输入流,再 json_decode 成对象。一些 php 框架已经开始这么做了。

当然 AngularJS 也可以配置为使用 x-www-form-urlencoded 方式提交数据。如有需要,可以参考这篇文章

text/xml

我的博客之前提到过 XML-RPC(XML Remote Procedure Call)。它是一种使用 HTTP 作为传输协议,XML 作为编码方式的远程调用规范。典型的 XML-RPC 请求是这样的:

HTMLPOST http://www.example.com HTTP/1.1 
Content-Type: text/xml

<?xml version="1.0"?>
<methodCall>
    <methodName>examples.getStateName</methodName>
    <params>
        <param>
            <value><i4>41</i4></value>
        </param>
    </params>
</methodCall>

XML-RPC 协议简单、功能够用,各种语言的实现都有。它的使用也很广泛,如 WordPress 的 XML-RPC Api,搜索引擎的 ping 服务等等。JavaScript 中,也有现成的库支持以这种方式进行数据交互,能很好的支持已有的 XML-RPC 服务。不过,我个人觉得 XML 结构还是过于臃肿,一般场景用 JSON 会更灵活方便。

先验概率与后验概率

高中的时候做过一道题:X有两个孩子,其中一个是男孩,另一个是女孩的概率等于多少?

我其实很纠结,显然概率不等于0.5,但很害怕出题人自己也不懂,问过数学老师最后也没有弄清楚。

现在想来,那时候不懂先验和后验的区别和重要性。

先验概率是通过统计得来的,比如生男生女的概率可以认为是1/2。

而后验概率则是观察到某一事件发生后,得到的在已知条件下的概率。

回到这道题,两个孩子已经出生了。不考虑条件,两个男孩或者两个女孩的概率都是1/4,一个男孩和一个女孩的情况占1/2,现在去掉两个女孩的情况,一男一女的概率等于0.5/0.75,也就是2/3。

值得一提的是,这个例子中的两个事件是两个孩子的性别,他们有相同的概率,因此可以通过0.5的先验概率分析得出答案,如果是两个不同概率的事件,需要更多先验概率才能分析和计算。

30秒看懂矩阵

矩阵

也许应该括起来

数字元素排列的矩形阵列

矩阵加法

大小相同的矩阵对相同位置的数字相加,自然也可以相减

矩阵乘法

矩阵和常数相乘

矩阵中每一个数都和这个常数相乘,这个意义上矩阵除以常数也没问题。不过从解方程的意义上讲,矩阵乘以常数之后还是一样的矩阵。

矩阵和矩阵相乘

当第一个矩阵的列数等于第二个矩阵的行数,他们可以相乘。乘法规则是,第一个矩阵第m行的元素与对应的第二个矩阵第n列的元素相乘,他们的结果再相加,得到了相乘后矩阵的第m行第n列元素(因此相乘的结果是一个m行n列的矩阵)。

从规则很快可以看出来,两个矩阵的位置是不能交换的,因此矩阵乘法不满足交换律;再结合矩阵加法的规则,模拟一下过程,可以看出来矩阵乘法满足分配律和结合律。矩阵乘法的规则可以从线性方程组的角度解释推导。

矩阵乘法与线性变换

我花了不少时间才明白上面是在说什么(丢

Rn是所有长度为n的行矢量,同样,Rm是所有长度为m的行矢量。现在Rn要变成Rm,实际上是Rn中的行矢量x能够映射到Rm中的某个行矢量。定义了f表示映射函数,用f(x)=Af*x表示经过矩阵的映射x得到长度为m的表示。

尽管是行矢量,但我们知道矩阵乘法要求第一个矩阵的列数要等于第二个矩阵的行数,因此算的时候竖着写,矢量x看作一个n*1的矩阵,能够得到一个m*1的矩阵,也就是映射后的矢量。通过矩阵,我们能够实现在维度不同的空间中映射矢量,但不一定可逆。

上图中二维平面的例子就是长度为2的矢量做变换,算是比较直观了。

内积与外积

向量的乘法产生内积与外积,其中外积是一个矩阵,内积是一个实数。

外积

m*1的列向量与1*n的行向量相乘,最终得到m*n矩阵,而这个矩阵上i行j列的值等于列向量第i行乘以行向量第j列。

内积

也叫点积,或者数量积,如果m=n,可以得到内积,高中数学就已经做过这样的计算。例如(a,b)*(c,d)=ac+bd

element-wise multiplication & matrix multiplication

前者相乘的规则是:对应位置上的元素分别相乘,因此两个矩阵大小应一致,numpy中用v*u表示。后者是矩阵乘法,用dot(v,u)。

矩阵转置

转置后的矩阵m行n列的元素是原来n行m列的元素,矩阵由n*m变为m*n。矩阵w转置的标记如图所示。

非凸优化与梯度下降

首先抛一个知乎的回答:在数学中一个非凸的最优化问题是什么意思?

作者:王业磊
链接:https://www.zhihu.com/question/20343349/answer/17347657

在深度学习中,我们需要学习一些参数,使我们的模型更加准确。但这些参数一开始是0或随机的,深度学习的过程是将这些参数一次次迭代,从而找到最优解。

w,b:参数 J(w,b):代价函数

从上图可以看到,求导的结果为负的时候,w和b的值会增加,反之亦然,这使得w和b逐渐接近最优解(极值)。这里可能出现的问题是,α的取值要合适,暂时不做探讨;并且不能出现多个局部最优解(多个极值),这就是要求J为凸函数的原因了。

有一点需要指出:偏微分使用符号∂而不是d,但这种使用形式并没有太多的道理,无须在意。

REPL是什么

REPL(Read Eval Print Loop:交互式解释器)提供了一个CLI(command-line interface:命令行界面)下读取值、求值、输出值、循环代码的环境。

在Linux里,用软件包管理器安装的语言环境很多都包含REPL,如Python, NodeJS等。

你可以在REPL中输入表达式(包括多行)、变量名,上一行的表达式结果可以用_代替。

你也可以使用tab键标记当前行。

REPl支持的以.开头的命令可以用.help查看:

.help

你可以使用两次Ctrl+C或一次Ctrl+D退出REPL。