TCP Maximum Segment Size (MSS)

这篇是一个小小的查缺补漏,还记得大三网络实验最后助教检查实验问过这个问题:“MSS是干什么的?”,当时背了个定义蒙混过去了,没有仔细理解,现在又遇到了,补上~

MSS是什么?

下图中看到的是TCP连接发送和接收的过程示意图,最大报文段长度(MSS)的作用是限制在TCP层产生的报文段的最大长度(当然要在滑动窗口允许的前提下)。

TCP发送接收过程图

TCP发送接收过程图

比如如果MSS为1000个字节,每个TCP报文的最大长度为1020字节(附加20字节TCP头部),之后传递到IP层加装20字节IP头部封装成为IP报文利用链路层发送。

继续阅读:

关于Linux环境C/C++网络框架的一点思考

最近又看了一个网络框架的源码,和之前看过的比起来,应该说是各有特色,互有所长。在这个全民写框架的时代,可能是因为框架(Framework)听起来逼格比较高,所以大家都乐于去写一个自己的“框架”,那么,一个合格的网络框架究竟应该是什么样的?我们又该从何下手?

什么是网络框架

网络框架,顾名思义,是给网络应用程序使用的框架,本文中指代在Linux环境下使用C/C++编写的网络服务器框架。用户在使用框架时应该能够做到在对底层网络完全不了解或者所知很少的情况下,轻松实现自己所需要的后台网络服务应用。

原材料

听上去似乎很神奇,但实际上网络框架所要完成的只有一件事情——封装。网络框架所做的事情就是将Linux提供的底层网络API进行封装,向用户提供一套没有网络细节的接口。

继续阅读:

Hello, SciPy!

“学而时习之,不亦乐乎”,利用放假几天时间,简单复习了一下之前学习的Machine Learning课程,并且用刚上手没两天的SciPy重新完成了大部分Ng的课后作业,SciPy真的非常好用~

SciPy

SciPy

上图是SciPy官方网站对SciPy的介绍,SciPy并不是单个开源项目,而是一组开源项目共同构成的Python科学计算生态系统,一个非常值得一看的系列Tutorial在这里

下面是重写后的课后练习的notebooks:

  1. Linear regression
  2. Logistic Regression
  3. Multi-class Classification
  4. Learning curve(Bias v.s. Variance)
  5. SVM
  6. K-Means & PCA

神经网络相关的实验还没有重写,sklearn没有提供监督学习的神经网络组件,需要用pylearn2来做,有时间补上。

OpenStack网络迷宫:Neutron以及LBaaS

"一团糟" - 我对OpenStack网络实现的第一感觉

“一团糟” – 我对OpenStack网络实现的第一感觉

OpenStack的网络模块相信不会有人否认是整个OpenStack中最复杂的部分,即使是OpenStack社区的成员也常常被网络模块的复杂性搞的焦头烂额。因为研究负载均衡的关系,我不得不对网络模块进行一点粗浅的了解,这里按照个人的理解把这些东西总结起来写下来。

本文算不上是的OpenStack网络分析(没有实力写),但求可以以自己的一些粗浅理解,为想要一窥OpenStack网络实现的同学提供哪怕一点点帮助。

PS:本文中所描述的所有概念和实现均基于OpenStack当前版本(neutron git version : 2921d3c686b5f5cd68d51f906766983f975b1cf2),在此也强烈建议任何想要了解OpenStack网络的同学一定要实际搭建一个可用的环境来对其中网络的每一个环节进行推敲。

继续阅读:

SRM657 DIV1 Problem Sets

原题链接:Problem Sets

Cat Snuke came up with some problems. He wants to construct as many problem sets as possible using those problems. Each problem set must contain exactly three problems: one for the Easy slot, one for the Medium slot, and one for the Hard slot. Each problem can only be assigned to a single slot in a single problem set. He came up with E + EM + M + MH + H problems in total. The distribution of the problems is as follows:

  • E problems can only be used in the Easy slot.
  • EM problems can be used either in the Easy slot or the Medium slot.
  • M problems can only be used in the Medium slot.
  • MH problems can be used either in the Medium slot or the Hard slot.
  • H problems can only be used in the Hard slot.

Return the maximal number of problem sets he can construct.

继续阅读:

SRM656 DIV1 Random Pancake Stack

被虐了……这个题目其实不难,但是从一开始想法有个漏洞没有发现…一直没有转过弯来…还是需要训练训练…

原题链接:Random Pancake Stack

Charlie has N pancakes. He wants to serve some of them for breakfast. We will number the pancakes 0 through N-1. For each i, pancake i has width i+1 and deliciousness d[i].

Charlie chooses the pancakes he is going to serve using the following randomized process: He starts by choosing the first pancake uniformly at random from all the pancakes he has. He places the chosen pancake onto a plate. This pancake now forms the bottom of a future stack of pancakes. Then, Charlie repeats the following procedure:

  1. If there are no more pancakes remaining, terminate.
  2. Choose a pancake uniformly at random from the pancakes that have not been chosen yet.
  3. If the width of this pancake is greater than the width of the pancake on top of the stack, terminate without taking it.
  4. Place the chosen pancake on top of the stack and go back to step 1.

You are given the vector d with N elements. The total deliciousness of a serving of pancakes is the sum of the deliciousness of all pancakes used in the serving. Compute and return the expected value of the total deliciousness of the pancakes chosen by Charlie.

继续阅读:

有向图强连通分支:Kosaraju’s algorithm

有向图强连通分支算是个基础算法,不过总是忘记,写下来备忘。

无向图强连通分支非常简单,使用图的遍历算法(DFS或BFS)即可,而有向图的强连通分支计算则要复杂一些,Kosaraju’s algorithm实现了\(O(n+m)\)时间复杂度的有向图强连通分支算法。

算法的核心思想在于:从有向图中任何一个点出发做DFS,必然能从图中“拖”出一个点集,和无向图中不同的是,这个点集不一定构成强连通分支,但是如果我们能通过一个合适的顺序进行DFS(“sink” vertex),则可以依次把每一个强连通分支“拖”出来,得到正确的结果,那么算法的要点则在于如何寻找这个合适的顺序。

继续阅读:

全局最小割:Karger’s Min Cut Algorithm

Cut in an undirected graph

Cut in an undirected graph

提到无向图的最小割问题,首先想到的就是Ford-Fulkerson算法解s-t最小割,通过Edmonds–Karp实现可以在\(O(nm^2)\)时间内解决这个问题(\(n\)为图中的顶点数,\(m\)为图中的边数)。

但是全局最小割和s-t最小割不同,并没有给定的指定的源点s和汇点t,如果通过Ford-Fulkerson算法来解这一问题,则需要枚举汇点t(共\(n-1\)),时间复杂度为\(O\left(n^2m^2\right)\)。

Can we do better?

继续阅读:

Machine Learning小结(5):异常检测

写这篇小结的时候,Ng的课程已经结束了(期待SoA哈哈哈),回顾整个课程内容,虽然Ng有意的屏蔽了大部分的数学内容,但是提纲挈领的为我们展现了常见机器学习算法的基本容貌和应用技巧,令人受益良多。从视频、课后问答到编程作业,都完美的示范了一门在线课程应该是什么样子的,不能感谢更多。

回到正题,异常检测,也称为离群点检测,是用来发现一些特征不同于预期的样本,在应用中具有极高的价值。异常检测有多种方法,Ng课程中讲的是基于统计学方法(高斯模型)的异常检测。

继续阅读: