Popular Tags:

基础链路层协议(一):乌托邦单向协议

November 6, 2014 at 12:47 am

最近正在对计算机网络的基础知识进行复习,由于链路层的一些基础协议在高层协议中也有所体现,于是开始挖链路层基础协议的坑。定位为比较入门级别的复习。 为了使接下来的讨论简单一些,我们对网络模型进行一定的简化: 我们假设各个层之间,如物理层、数据链路层、网络层之间,相互独立,层与层之间只能通过信息的传递形成交互。 上述简化针对于本系列的所有内容。 那么问题来了。我们希望建立一个由A向B传输数据的协议,从而实现A和B的数据传输。本篇介绍最为简单的一种协议,在本篇中,我们假设: 1.只进行A向B的单向传输 2.A总是可以不断产生数据 3.B总是可以立即处理收到的数据 4.数据不会发生丢失 5.忽略传输的时间 6.机器不会损坏 基于上述假设,对于发送端而言,实际上只需要不断地从网络层获取数据,然后发送给物理层就可以了。下面的代码给出了一个典型的发送端: void sender1(void){ frame s; packet buffer; while (true) […]

SCC-Tarjan算法正确性证明

July 1, 2014 at 11:44 pm

注:这篇文章由于存在不少错误而暂时(可能永久)地被废弃,相关的内容请转至图论算法漫谈之连通性(二):tarjan求强连通分量 Tarjan算法应该是求有向图强连通分量的最常用的算法,而且本身也非常的高效。网上关于Tarjan算法的介绍、模板都非常多,这里炒冷饭的目的是打算证明一下Tarjan算法的正确性,在网上找了好久,都没能找到一个我这种水平也能看得懂的证明,所以打算自己写一个。证明的主要参考来自Tarjan大神的论文。 强连通分量的概念 设G是一个有向图。如果对于G中的每个点v, w,都存在一条v到w的路径和w到v的路径(下文对于v到w的边表示为v=>w,v到w的路径表示为v==>w),那么称G是强连通的(strongly connected)。 对于G中的点v, w,如果存在v==>w和w==>v,那么称v和w是强连通的。为了引出强连通分量的概念,这里证明在G的点上的强连通关系是个等价关系。其中对称性、自反性是显然的,简单说明一下传递性。如果v和w强连通,而w和y强连通,v==>w,w==>y,v==>y,反之亦然,所以这显然是个等价关系。由于点的强连通性是一个等价关系,图G中的点就被划分成若干个等价类,而每个等价类中的点和它们在原G中的边显然构成一个强连通子图。于是图G就分解成若干个强连通子图(以及可能存在的连接这些子图的边),每一个子图就成为G的一个强连通分量(strongly connected component, SCC)。 DFS搜索树 Tarjan算法主要使用了DFS,并充分利用了DFS过程的特性。为了阐述的方便,下面以一个实际的图为例,介绍在DFS搜索中的一些概念。 上图给出了一个有向图,包括它的的所有顶点和所有边(包括所有虚线边)。 图中的编号对应了DFS遍历的顺序,在tarjan算法中,每个顶点的遍历序号通常记为DFN(v),也称为时间戳(从1开始)。 图中所有蓝色的边及相应顶点构成了一次DFS的搜索树,这些蓝色的边是树上的边,我们记树上的边(v, w)为       […]

动态规划求期望--原理 POJ2096

June 28, 2014 at 4:10 pm

用DP来求期望的题目已经不只做了一个了,但是一直对求解过程中使用的数学原理不是很明白。昨天发现,使用条件数学期望及全期望公式,或许可以较好地解释这个原理,但可能仍然存在问题,暂时先把它记下来(考虑过使用马尔科夫链来解释其中的状态转移,却觉得又不能把它看作一个随机过程,最终也没能得出结论,数学基础和智商都太差了,没有办法)。 原题地址:http://poj.org/problem?id=2096 题目大意: 题目的意思是把世界上的程序BUG分成n类,一个有无尽多个BUG的程序有s个子系统,一个大神每天随机的发现一个BUG,求发现所有n类BUG至少1个,所有子系统的BUG至少1个所需的天数的期望。由于发现BUG是随机的,所以属于某个类的概率是1/n,属于某个子系统的概率是1/s。 题解: 令S表示条件中描述的所需时间,显然S是一个一维随机变量,可以使用期望的定义来计算,但由于时间可能是无穷的,所以计算无法终结,初步计算就会发现计算过程是很复杂的,也很难找到规律。 这种题目通常就是使用DP来求解的。记(i,j)是已经发现了i种BUG、在j个子系统种发现BUG的状态,记S(i,j)是在已知发现了i种BUG、在j个子系统中发现BUG的前提下,达到目标所需的天数,记DP[i][j]为S(i,j)的期望。显然需要求解的是DP[0][0]。就目前来看,仅仅已知DP[n][s]=0,因为此时已经达到目标。 核心是状态及状态的转移,在(i,j)状态下,新的一天可能会发生这样4种事件: 1.(i,j) -> (i,j) 新发现的BUG在i种j个中, p1=ij/ns 2.(i,j) -> (i+1,j) 新发现的BUG在j个中,但不在i种中 p2=(n-i)j/ns 3.(i,j) -> […]

ZOJ 2139 ACM

February 28, 2014 at 11:18 pm

原题地址:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1139 离完成410题之后有一段时间了,前几天又被工作折腾,这两天终于有空练一两道题目,哎,工作真是辛苦,还有毕设要担忧,算了不扯淡了。本来是打算刷1235这四个数的排列中简单的题目的,结果瞄到2139这个题目霸气的标题,于是毅然决然要把它A了(好吧实际上是因为题目描述很短)。 题目的大意是说,有一个机器编号为n,如果你知道第k张卡片的密码,你就能算出编号为f(k)=k/2+(k%2)*2^(n-1)的卡片的密码,那么对于0到2^n-1这样2^n个数,至少要知道几张卡片的密码才能知道所有卡片的密码。 简单的算几个例子就可以发现不可能一张卡片得出所有卡片的密码,公式会循环,比如对于n=2时,f(0) = 0, f(1) = 2, f(2) = 1, f(3) = 3 知道编号为0的卡片,无论计算多少次公式,也永远也只能得到编号为0的卡片的密码,而知道卡片1,也只能得到卡片1,2的密码,知道卡片3,只能得到卡片3的密码。显然公式f(k)把卡片分成了若干个等价类,而目的就是求这个等价类的数目。其实想到这里,就应该知道是置换群相关的知识,应该使用Pólya定理。我对定理的理解太肤浅,所以找规律找了很久。。。实际上,公式里都是2,所以这么2的题目应该也要考虑2进制。只要想到了2进制就不难发现,如果k为偶数,那么就是右移一位,如果是奇数,那么就是右移一位,然后最高位补一,如对于n=4: 8 = 1000(2) = […]

ZOJ 3365 Integer Numbers

January 21, 2014 at 8:24 pm

原题地址:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3365 今天由于外力因素,没法干其它的事,于是在ZOJ上又水了水,算上这题,终于是AC400题了。回头想想,这个目标应该是在去年,还是前年就应该达成的,时间过得真快,不知不觉又被我水过去了两年么,果然已是拖延症晚期。 题目的大意是说小男孩写了一个连续的整数序列(n <= 50000),然后被腹黑的小女孩修改了一些数字,使得序列不再连续了。小男孩很伤心,希望你在修改尽量少的数字的前提下恢复序列的连续性,要求输出被修改的数字的个数和最终的序列,任何可行解都可接受,是个special judge。 考虑元素array[i],如果保持它不变,那么array[0]必须等于或者修改为array[i] - i,这是确定的,即所有元素都有保持它不变所需要的一个初值。拥有共同初值的元素构成一个等价类。元素最多的那个等价类中的所有元素就是需要保持不变的元素。使用O(n)的时间计算出所有元素的初值,问题就转化为求众数了。 一开始想用hash,后来想想C++没有hash,所以就有map求了一下,220 ms AC.后来发现ZOJ已经支持C++11,托STL设计者的福,仅修改了几行代码就有了unordered_map版本,150ms AC.但作为一个平均复杂度O(n)的算法来说,unordered_map在这个数据量上的表现并不理想。   #include <cstdio> #include <unordered_map> using namespace […]

ZOJ 3710 Friends

January 20, 2014 at 10:02 pm

原题地址:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3710 已经很久没有在ZOJ上刷题了,这算是回来刷的第一题,算是一个新的开始。 题目的大意是说有n(<=100)个人,他们之间的某些人互为朋友,这是初始条件。然后如果两个人有共同的k个及以上的朋友,他们就会变成朋友。要求的是通过这种方式形成的新朋友的对数。 最简单的方法莫过于模拟整个过程,把符合条件的人设为朋友,然后更新相应的状态。这里遍历所有的人是O(n^2)的,判断符合条件是O(n)的,然后外层加一个while(changed){}的循环。但这样复杂度就比较难以分析[分析不出来,sigh],就最坏的情况来看,如果每次只有一对新人符合条件,最后又是所有人都成为朋友,那么这个while循环就是O(n^2)的,所以整个算法是O(n^5)的。这个最坏的情况是否能达到,暂时分析不出来了。 这时候我是这样的两个思路: 1.把模拟的代码码出来,提交看是否AC,过了万事大吉。 2.想一个复杂度更小一点的算法。 我想着出题者一定不会只给这么一个模拟的复杂度都看不到的算法出来,而且说不定会把直接模拟的给卡死,所以直接跳过了第一步[事实证明是我想太多了,直接模拟是可以AC的] 幸好这道题也算有一个我比较满意的,以我的智商也能快速想到的O(n^3)的算法。当两个人有共同的k个及以上的朋友时,他们会变成朋友,并且它们变成朋友影响到的关系是O(n)的。比如A和B变成了朋友,那么唯一影响到的是所有A的朋友和B多了一个共同朋友A,所有B的朋友和A多了一个共同朋友B。所以只要维护一个记录两人共同朋友个数的数组common[][],初始化时把>=k的两个人存入队列(或者堆栈)中,每次从中取出两人,O(n)地更新,并把其中大于等于k的两个人存入队列中,重复上述操作直至队列为空。由于关系对最多O(n^2),所以队列里最多这么多个元素,而每次更新是O(n)的,是个O(n^3)的算法。 AC的时间是260ms,暂时还没有想到更好的算法,代码还可以做一些优化,但达不到目前最优的20ms,不知是如何实现的。 #include <cstdio> #include <cstring> #include <queue> using namespace std; int […]

ARP协议简介[摘自计算机网络总结第五章--网络层]

January 1, 2014 at 7:09 pm

在Internet上每一个机器都有一个或者多个IP地址,但IP地址并不能直接用于发送包,因为数据链路层的NIC[Network Interface Card, 网卡]不识别IP地址。对于以太网卡而言,每一张以太网卡有IEEE所提供的一个唯一的48位的以太网地址,我们需要把IP地址通过某个方式转化为以太网地址。 我们考虑一下的一个简单的局域网: CS网络和EE网络通过路由器连接,各自网络内则通过以太网交换机连接。我们考虑主机1要向主机2发送一个包。[注:通常主机1首先访问的是主机2的域名,然后发生域名解析,这个过程我们在第七章中讲述]目前,我们认为主机1直接访问的是主机2的IP地址。主机1的IP软件可以知道主机2和它在一个网段,这意味着可以不与路由器(网关)打交道,但是主机1的IP软件并不知道主机2的以太网地址,所以无法发送包。一个可行的方法是在某个地方保存一个IP地址到以太网地址的映射表,但对于大型网络来说,要维持这个映射表的实时性很不容易;一个更好的主意是主机1向自己所在的以太网段进行广播,询问谁拥有了这个IP地址。这个广播会发送到以太网段的每一个主机上,每个主机检查自己是否拥有这个IP。上例中,主机2会应答,并返回自己的以太网地址E2,由此主机1便可以向E2发送包。用来进行广播询问和获取应答的协议就是ARP[Address Resolution Protocol]。几乎所有Internet上的机器都运行这个协议。ARP相比于维护一个映射表文件简单许多,它大大减轻了系统管理员的负担。 上面描述的ARP协议的简单运作可以进行很多优化。首先,ARP协议要对返回的结果进行缓存,这样在短时间内访问同一地址时就可以不用发送第二次广播。当主机2要给主机1应答的时候,它同样需要进行一遍广播,这可以通过主机1在广播时包含自身的一个IP到以太网地址的映射来避免,当主机1的ARP包发送到主机2时,这个映射就写入了主机2的缓存[所有被询问到的主机都可以缓存这个映射]。为了保证映射表的实时性,一种方法是在几分钟后清空缓存;一个更聪明并可以优化性能的方法是当一个主机的以太网地址发生变化时向所有机器发送广播,这个过程通常是以一个询问自己IP对应的以太网地址来实现。正常情况下,询问自己IP对应的地址不会收到任何应答(因为其它人都不是这个IP,这就好比在一群互不相识的人中询问自己的身份证号对应的名字一样),但会产生让所有主机更新自己的IP-以太网地址映射的附带效应,这通常被称为无故ARP[gratuitous ARP]。无故ARP还具有查错的功能,如果真的获得了应答,说明当前网段存在了冲突的IP地址,这可以警告管理员马上修复这个问题。 下面我们考虑不同网段间传输时ARP协议的工作,假设主机1想要向主机4发包。当主机1试图向主机4发包时,IP软件可以识别出主机4在不同网段,此时就会试图把包先发给路由器,也被称为缺省网关[default gateway],通常缺省网关的IP地址是当前网段的最短地址,对于面向CS网络的端口的IP而言,是192.32.65.1。要向缺省网关发包,需要知道网关在CS端接口的IP地址,这通过一个正常的ARP广播实现,于是获取了E3。路由器如果路由器不知道主机4,它同样会使用ARP广播,最终路由器可以把包正确地发给主机4。 如果主机1没有设置缺省网关,或者IP软件并不讲包发给缺省网关,同样可以在主机1不知道主机4在不同网段的情况下发送包给主机4,我们讲讲这个的实现。主机1不知道主机4在不同网段,于是发送ARP包,此时E3收到了ARP包,并告诉主机1它即是主机4。然后E3获取主机1发送的包并发送给主机4,这个解决方案称为代理ARP[proxy ARP]。

Python读写配置文件-ConfigParser模块--摘自Python学习总结-Python基础二

October 20, 2013 at 12:29 pm

本文主要介绍了Python2中的ConfigParser模块,该模块用于读写Python风格的配置文件。 1          ConfigParser模块 使用配置文件而不是写死代码方便了最终用户定制程序。Python提供了ConfigParser模块用以编写、解析Python风格(类似Windows的INI文件风格)的配置文件。 1.1     编写配置文件 一个简单的Python风格的配置文件如下所示: [DEFAULT] ServerAliveInterval = 45 Compression = yes CompressionLevel = 9 ForwardX11 = yes […]

DNS学习总结[摘自计算机网络学习总结第七章-应用层]

September 15, 2013 at 11:53 pm

注:本文所指的课本为《Computer Networks FIFTH EDITION》 主要作者有ANDREW S. TANENBAUM 和 DAVID J. WETHERALL 7.1.1     DNS 命名空间 DNS中所有的域名具有全球唯一性,它们通过和邮局对地址的定位的方式,即国家、地域...,这种类似的方式进行唯一定位,由此可以得到一个域名构成的树结构,如下图: 当前(2013),Internet被分为大约250个顶级域名[top-level domains]。顶级域名可以在划分成二级域名,这个过程还可以再深入。 其它的内容作为了解,可以看书。 7.1.2     域名资源记录 […]