RPC(一):基于python实现简单的RPC框架(上)

September 7, 2016 at 10:36 pm

似乎又要放着以前无数个坑不填来挖一个新的坑了,不过这次并不打算挖很深的坑。其实挺早就有对现有的RPC框架有一个简单的理解的想法,所以本文的初步想法是模仿tinyRPC来简单模拟一下RPC框架,这也是本篇的主要内容。如果后面有续篇的话,会花些时间看看像gRPC这样的库的实现机制,不过目前暂时也没有这方面的打算,所以目前而言本系列应该仅此一篇。如果一切顺利的话,之前的坑会在回到学校之后慢慢开始填。废话不多说了,先进入正题吧。 本文主要包含以下内容: 1. 客户端的类本地化调用 2. 序列化协议的设计 3. 通信协议的设计 客户端的类本地化调用 RPC框架中最基本的两个要素是客户端和服务器端,客户端是远程过程的调用者,而服务器端则是过程的实现者,所谓的RPC(Remote Procedure call),就是希望客户端可以像调用本地函数一样调用服务器端的函数。为了做成一个框架,我们需要让客户端可以实现任意函数的调用,由于本文使用python实现,这里利用python的__getattr__(self, name)函数来较为简单、干净地实现这个功能(在python中,如果访问一个类的属性,包括方法不存在时,会调用这个类的__getattr__()来试图返回这个属性或者这个方法的值,对于方法而言,此时可以返回一个函数,这个新的函数将会被调用。这个函数名字有一定的困扰,但在这里使用它可以极大简化代码)。 通过这个函数,我们可以将所有的远程过程调用统一到client的call方法里去: class RPCClient(object): def __getattr__(self, name): func […]

step_by_step实现简单HTTP服务器(一):HTTP服务器版helloworld

June 11, 2016 at 3:10 pm

本文打算用最少的代码来实现一个HTTP服务器最基本的功能,虽然冠上了序号,但是很难保证会有续集,目前的时间少得可怜,而我又太水。不过这一篇应该是可以独立成文的,最终要达到的目标是,通过浏览器访问服务器时,可以返回服务器上保存着的一个静态的helloworld页面。 本来是打算使用C++来写的,但由于C++标准库并没有提供socket的支持,无法很好地跨平台,而且C++中socket的接口相对繁琐,体现不出“最少”两个字,所以最终还是决定使用Java语言来写。本文一方面可以简单复习一下socket编程的知识,同时也梳理一下HTTP协议的一些基本内容。 废话不多说,下面我们一步一步实现一个HTTP服务器吧。本文的大体内容如下: 1. 实现一个TCP服务器 2. 应答HTTP请求,返回404 3. 实现简单的get请求 实现一个TCP服务器 http协议建立在tcp协议基础上。在Java中实现一个TCP服务器是相当容易的,这方面的资料网上也是非常多,但为了保证本文的完整性,这里还是都重新过一遍。我们的Server的类名为HttpServer,我们导入io和net包以进行相关的操作。为了简化代码,我们直接让main函数抛出所有异常: import java.io.*; import java.net.*; public class HttpServer{ public static […]

ThinkSNS源码分析(三):数据库交互与ORM初步

June 17, 2015 at 5:23 pm

Web系统最终都无可避免的和数据库打交道。虽然现在市面上存在的数据库类型很多,但对于Web系统而言,主流的还是传统的关系型数据库。ThinkSNS仅提供了对MySQL数据库的支持。好了,废话不多说,先看代码吧。 正如上一篇所约定的那样,我们以注册模块为例分析ThinkSNS对数据库的操作,相信你已经熟悉要在RegisterAction.class.php里找寻相关的代码了。粗略地阅读代码就会发现$_register_model和$_user_model这两个成员变量出现的场次非常多,和数据库的交互似乎都经由它们来完成。我们可以找到它们的实例化和使用示例代码: <? $this->_register_model = model('Register'); $this->_user_model = model('User'); $user_info = $this->_user_model->getUserInfo($this->uid); 这里的model函数是来自于function.inc.php的全局函数,它实例化一个model目录下的RegisterModel.class.php, UserModel.class.php的一个对象,而RegisterModel, UserModel均继承自核心类Model。在分析Model是什么之前,我们先沿着代码的思路往下看,看看Model究竟是如何执行数据库操作的。我们以UserModel的getUserList为例,这个方法显然返回指定条件的用户列表。我们可以找到如下查询语句: <? $list = $this->where ( […]

ThinkSNS源码分析(二):路由

June 10, 2015 at 11:20 am

在ThinkSNS中,我们访问的地址通常都是"index.php?app=...&mod=...&act=...",看起来都是访问同一个页面,但是根据参数不同等会呈现不同的状态,这就是所谓的路由。路由可以理解为根据地址栏里的地址,通过解析之后,生成最终所需要的页面的过程。如果完全没有路由功能,PHP页面也是可以工作的,我们只要访问特定的php文件就可以了,比如login.php对应了登录页面,add_friend.php对应了增加朋友页面。这样做明显的一个缺点是会造成页面的一个膨胀,而且相互关联的页面之间并不能很好地组织在一起,只能相互平行。不仅如此,不使用路由的方式给了用户过多的内部结构,无法避免用户对页面的直接访问,容易给恶意用户有机可乘。事实上路由正如实际的路由器一般,统一接受用户请求,然后分发到指定地方,在web中即为生成指定页面,路由中枢可以进行包括过滤等功能。 事实上很多HTTP服务器本身也提供了路由功能,如Apache服务器中的.htaccess文件。在ThinkPHP中,路由功能是由PHP代码自身实现的。大部分的访问地址均为"index.php?app=$app&mod=$mod&act=$act"的方式。其中$app指代具体的应用,$mod指代具体的模块,$act指代具体的操作。如上一篇中所提及的,这三者的关系是从大到小,即这个地址的意义为执行$app应用中的$mod模块的$act操作。 毫无疑问,由于是在代码层面上实现的路由,上述地址第一步经由HTTP服务器将我们带到index.php文件中。index.php中要进行路由,就要对传入的$app, $mod, $act三个参数进行解析,在index.php载入内核OpenSociax.php时,保存了这三个参数,代码如下: <? if(!isset($_REQUEST['app']) && !isset($_REQUEST['mod']) && !isset($_REQUEST['act'])){ $ts['_app'] = 'public'; $ts['_mod'] = 'Passport'; $ts['_act'] = 'login'; […]

ThinkSNS源码分析(一):模板渲染

May 30, 2015 at 10:13 pm

ThinkSNS是使用PHP开发的一款开源的微博系统,本系列打算借由这个微博系统的代码,较为全面地介绍Web开发中涉及到的点。初衷是借由此仿写一个ruby版,不过ruby版什么时候起头还是个问题,暂且搁置,还是先从源码分析走起。好了废话不多说进入正篇。 本系列的源码是ThinkSNS3.1版的,也没有兴趣对其它版本再进行研究了,这个版本已经够用。 其实在模板渲染之前还有很多细节是需要讲的,但是还是觉得把最终呈现给用户的东西先讲是最有代入感的。 我们知道PHP作为一门为Web而生的语言,一个很核心的特点就是以标签的方式放入代码,并且可以和html页面代码相互嵌套。设想当我们访问微博的主页index.php时,用户如果已经登录,那么现实的是带有内容的主页,否则,显示的则是登录页面。那么index.php就承载了判断用户是否已登录和根据这个信息呈现不同样子的html页面两个任务。从代码层面上就有判断用户是否登录、已登录的页面显示、未登录的页面显示三个部分,其中前者基本是纯的php代码,而后两者是大量的html代码和少量php代码的结合体。最糟糕的情况是这三部分代码还是三个不同的人写的,每个人都要在这个大文件里修改自己的部分。不仅如此,揉合在一起也会给调试、测试、修改造成不必要的麻烦。而且html和php是两种完全不同性质的语言,看代码时思维还要在这两者之间频繁地切换,非常不方便。无论如何,代码都需要作解耦处理。 最简单的处理方式就是将进行业务逻辑(所谓的模型)的代码和进行实际显示(所谓的视图)的代码分离开来: <? if($logged_in){ $ui->show_main_view(); } else{ $ui->show_login_view(); }?> 在此基础上,我们通常把含有大量html代码的这部分显示逻辑写入到文件中,需要时从文件中再去读取,这样也一定程度上节省了开支,如果页面不被访问,它的代码就常驻在文件中。这样的文件就是一个模板文件。在ThinkSNS中,大部分的模板文件都在apps/public/default文件夹中。 由于最终显示页面中包含来自于业务逻辑的数据,模板文件中就会包含相应的php代码。为了尽量让html和php两种语言分离,使得不懂php语言的界面人员可以较为方便地编写模板文件,我们要定义一种新的语言,它比php要来的更加简单,容易上手,这种语言最终由php代码编译转化为包含php代码的页面。这样做一方面可以减少模板文件的编写难度,降低编写门槛,使得界面人员方便编写,另一方面也可以更好地剥离html代码和php语言。我们把这种语言称为模板语言,我们把由模板语言编写成的模板文件经由后端代码编译生成最终页面的整个过程称为模板的渲染。 事实上,作为偏好于前端人员的产物,模板语言有很高的自由度。ruby语言的一种模板语言slim甚至为了加快页面编写移除了html的标签号,所有的html标签只需写个标签名即可。模板语言的设计好坏有时候影响到一个web框架的受欢迎程度(模板语言一定程度上独立于框架,但显然很难完全从框架中剥离,毕竟要经由框架提供编译功能,而且编写好的模板文件也有时也作为框架的一部分,所以通常都和框架一并出现)。 模板语言的设计应该来说是个大问题,毕竟是设计一门语言,这个问题超出了本系列的讨论范围。幸好ThinkSNS设计的模板语言非常简单,只是在原来的php代码和html标签的基础上做很小的修改。 模板的渲染工作由内核目录下的Template.class.php完成,Template类提供了load方法,它使用loadTemplate($template_file)方法载入、编译一个模板文件,再调用include关键字执行编译后的代码。从磁盘载入后的模板文件借由自身的complier方法(其实叫compile更合适)进行编译,编译除了调用parse方法对模板文件进行解析外还增加了少量的安全代码,这里就不讨论了。parse方法是真正意义上解析模板语言的代码。它首先预处理include语法标签。ThinkSNS模板语言中的所谓include语法如下: <include file="__THEME__/public_header" /> […]

IPv6入门(二):来看看IPv6的IP地址

March 7, 2015 at 10:23 pm

这里是本系列的第二篇,这一篇里主要就是来看看128位这么多位的地址,究竟能来干什么。这一部分技术性的东西较少,概念性的东西较多。首先会简单介绍一下IPv6地址的表示方法以及各个部分的意义。然后对IPv6地址的三大种类进行介绍,介绍部分可能略显啰嗦,可以视情况跳过。最后介绍一下IPv6中的子网划分(即IPv4地址中的网络部分)以及接口ID的生成(即IPv4中的主机部分)。好了,进入主题吧。 当初设计IPv4的时候,想想2的32次方这么大的数没可能被用掉吧,哪来那么多设备了,于是就是まさか…とは思わなかった(阿,……,万万没想到)句型,最后发现不够用了(1970年设计,1992年发现不够用)。而2的128次方是什么概念呢,是不是又是一次失算呢,嗯,大概是10的38次方的样子,再深入点说的话,就是地球上每平方米可以有10的23次方个地址,这样想想的话,就当前的样子,似乎也是妥妥够了,以后会怎么发展呢,也只能尽请期待了把。 IPv6地址的表示和意义 一个典型的IPv6地址写成冒号分隔的16进制形式,比如2001:0DB8:0000:2F3B:02AA:00FF:FE28:9C5A。还有一个小简化称为zero suppression,就是把冒号分隔的整个部分是0的部分只用1个0表示,leading zeros则省略,比如上面的写成2001:DB8:0:2F3B:02AA:00FF:FE28:9C5A。除了这种省略以外,对于多个0的部分,比如FE80:0:0:0:2AA:FF:FE9A:4CA2,可以使用双冒号(double colon)来进行进一步的压缩,FE80::2AA::FF:FE9A:4CA2。当然,不能同时有两个压缩的部分,否则就不知道压缩的部分究竟有多少个了。搞成这样其实正常人已经看不怎么懂了,即使是程序员看着也吃力,总之IPv6已经不再希望让普通人去理解,而是希望网络能更加智能化吧。 了解了IPv6的基本表示方式后,我们来看这128位到底都有些什么东西。首先,和IPv4一样,IPv6也有前缀[prefix]的概念,并且和IPv4的CIDR表示方法是一致的(关于这部分的内容自行复习IPv4的部分),形如address/prefix-length的形式,比如2001:DB8:2A0:2F3B::/64就是IPv6的一个大小为2的64次方的子网[subnet],而2001:DB8:3F::/48则是一个汇总路由[summarized route]前缀。这里区分子网和汇总路由,因为在IPv6中,子网的前缀长度固定为64个比特,那些比64个比特要小的都是由多个子网合成的汇总路由。IPv6里没有使用子网掩码,仅使用前缀表示。由于通常Ipv6中的前缀长度对于表示子网来说都是64,所以经常不需要写出前缀。 IPv6的地址种类 IPv6地址分成了三大类,单播[unicast],组播[multicast],泛播[anycast]。单从概念上来说,和IPv4中的单播、组播、泛播的概念是一致的。IPv6中没有广播[broadcast]地址的概念,使用组播地址来代替了IPv4中的广播的功能。为了作为日后的参考,下面将会对这三种类型的地址作较为详细地介绍。不感兴趣的话可以粗略看过并直接跳到后面部分,不过还是推荐至少看一下单播地址的部分。 我们首先来介绍一下单播。一个单播地址唯一标识了在它所归属的地址中的单个接口。而所谓所归属的地址,就是指在这个IPv6网络中每个地址都是唯一的,这样一个范围。可能在另一个范围中和这里使用了同样的IPv6地址,那这两个范围就不是同一个归属了。这种一个地址标识唯一接口的方式也就是单播,所有发往这个地址的包都到达这唯一一个接口。要唠叨一句的是接口和节点并不是一回事。一个节点(主机)可以有多个接口,而给这些接口分配的任意一个IPv6地址都可以标识这个节点。单播地址又分成了好几种,global unicast addresses, link-local addresses, unique local addresses, special […]

IPv6入门(一):从NAT以及它的吐槽开始

March 7, 2015 at 7:05 pm

好不容易填完了链路层协议设计的坑,虽然最后的收尾工作被彻底的放弃了。本篇算是“计算机网络”相关内容的一个番外篇,主要是对IPv6以及现行的(2015)和它相关的一些概念的介绍。“算法”部分“线段树”的坑正在整理中,等整理好了一并发生来。 不知道是不是惯例,看过的网络相关的书在讲IPv6之前都是从对NAT的吐槽开始的,等作者吐槽完NAT感觉有点舒适了,才慢慢开始洋洋得意地介绍IPv6的好处。既然如此,本篇也并不打算脱离这个规律,作为开篇,还是不要一上来就扯IPv6为好。 不论是NAT还是IPv6,都是由于IPv4的IP地址不够用这个原因引起的,虽然还有一些奇怪的其它原因,但地址不够无疑是最根本的。一个ISP提供商只有/16个IP(即65536个,可以温习一下IPv4的知识),那么实际可用的65534个。如果顾客的数量超过这个值,就产生问题了。对于那些不常使用网络的顾客还好,总是随机的分配IP,哪个顾客不用了,就回收IP,要用的顾客分发IP,以此来达到一种平衡。但事实是使用IP的人实在太多了,而且越来越多的人依赖于网络不能自拔,所以很多电脑都是长时间开着连着网络,更不要提用来作为服务器的机子了。IP提供商IP地址缺少的问题归根结底是IP地址总数太少的问题,如果IP地址多的用不完,提供商也就不会只有那么几个IP了。最好的方案就是大家都换到IPv6上去,总所周知,IPv6有128位,这个数字是在是太大了,在可预见的未来内应该是用不完把。但是,要全部替换成IPv6是件非常大的工作,需要全部机器上的地址全部重新分配、更新硬件和软件,这是不可能的,所以IPv6只能是以一种慢慢侵蚀慢慢扩大的方式,逐步地替换掉IPv4,IPv6从1990年开始制定,知道现在(2015)也没有大规模的使用,也证实了这一说法。于是在IP地址不够的情况下就有了一个quick fix,就是NAT(Network Address Translation)。 NAT的基本方针是,将一群用户通过LAN连接起来,它们内部使用私有IP地址,诸如192.168.0.1之类,然后他们的私有IP通过一个叫做NAT box的设备转化成同一个公共IP,于是ISP提供商实际上只用提供一个IP就可以对付一大堆用户。下图展示了一个简单的NAT box的示意图。 无论是用户10.0.0.1还是10.0.0.2,它们要发送的包都首先发送给NAT box,交由它改成公共IP,发给Internet。同样,也由他交回来。这里面要解决的唯一一个技术问题是从互联网拿回来的包如何正确传递给主机。对于在远端的Internet端而言,它只知道公共IP 198.60.42.12给它发了一个包,并不知道内部的私有地址细节,所以,它也只能原封不动的按这个地址给发回来。相当于一家人里的某个人以家庭的名义写了一封信出去,对方也只能以家庭的地址寄回来,接着就需要由家庭内部解决是谁写的了。为了实现这一点,NAT box需要对不同的用户发出的包做某种修改,这个修改不影响服务器对包的理解,但是当服务器返回一个包时,由于修改了这个东西,服务器返回时包含了这部分修改的东西,NAT box就可以据此识别出是谁发的包。不幸的是,IP包的结构里仅只有1个比特位是闲置不用的,其它内容都要被接收方利用,所以,实际发生的就是NAT采取的让人吐槽不已的方式。网络层已经没有办法干什么了,反正大部分人也就发发TCP包和UDP包,直接在上层协议中找个东西改改好了。一个非常合适的字段是TCP或者是UDP包中的source port字段,也就是源端口,它表明了服务器端发送信息回到客户端时由哪个程序(或协议)来接收,有过socket编程经验的都知道,如果没有特殊需要,客户端的源端口是不需要自己指定的,只需要指定服务器端的端口即可,客户端的源端口会由协议本身随机分配一个空闲端口。这个对客户端几乎透明,对服务器端仅仅是用来区分对方机器是哪个程序要自己的包的字段,实在是再好不过了,只要能在抵达真正的机器之前改回来,包的传输就不会出现任何问题。于是NAT的工作原理就非常简单了,source port有16位,所以在NAT中可以内建66536(出于前4096个端口都用特殊用处,还要少些)项的表,对于由10.0.0.1发过来的包,可以做如下修改: 10.0.0.1:5544 -> 198.60.42.12:3344,并把原先的IP和端口储存在NAT中。于是服务器端发送回的包的目的IP是198.60.42.12,目的端口是3344,NAT得到这个端口号后,查询自己内部表索引3344的位置,就是记录着10.0.0.1:5544的地方,于是就知道具体要给那个机器了。 于是终于到了吐槽的时刻了。一个比较核心的点是这样实际上就违背了IP设计的初衷。IP地址本意是让世界上所有机器都有唯一的标识,整个协议都是基于此设计的,而使用了NAT之后,一大堆的机器的IP都是192.168.0.1了。第二个槽点是,内部网通过NAT可以访问外部服务器,但是一台外部服务器是无法主动连接内部本地机器的,因为它并不知道内部LAN的分布情况,私有地址什么的,完全不知道。这也破坏了Internet的设计初衷,本意是任意两台机器都可以端对端连接,现在变成单向的了,外部服务器只能被连接不能主动连接内部机器。第三个槽点是NAT把Internet这种面向无连接的网络变成了某种意义上的面向连接的网络。一旦NAT挂掉,内部表数据丢失了,接下来的TCP连接就完全中断了,而如果只是普通的路由器,挂掉重启对TCP连接之后影响不大。第四个槽点是它违背了下层和设计和上层无关的原则。如果TCP有了二代,source […]

基础链路层协议(七):选择重传(selective repeat)协议

February 27, 2015 at 7:36 pm

不出意外的话这一节是关于链路层协议设计的最后一节内容了,在这篇之后还会有对一些传统的链路层协议的简介,至于错误检验和矫正部分的坑,有机会再填。废话不多说了。 首先放上选择重传协议的代码: #define MAX_SEQ 7 #define NR_BUFS ((MAX_SEQ + 1) / 2) typedef enum {frame_arrival, cksum_err, timeout, network_layer_ready, ack_timeout} event_type; […]

基础链路层协议(六):双向通信初步--使用Go-Back-N的滑动窗口协议

January 25, 2015 at 12:03 am

直到现在为止的讨论中,我们都忽略了一个帧到达接收端的时间以及一个应答帧返回发送端的时间。现实情况中,这些时间往往是不能忽视的。我们通过一个简单的例子说明这一点。考虑一个50kbps的卫星信道,它带有250ms的传播延迟(propagation delay)。为了方便讨论,这里先介绍一下传输延迟的具体定义。传输延迟指的是(光或其它波)信号从发送端到达接收端所需的时间,它的计算公式为d/s,其中d是发送端到接收端的距离,s是信号在介质中的传播速度。正如打电话有时会发生的延迟一样,不论数据量多少,延迟的量都是固定的,和数据量本身无关。假设我们再这样一个信道上发送一个1000比特的帧,那么受到信道带宽的限制,这个帧完全发送出去(而不是到达)需要1000 / 25000 = 20ms,这个延迟称为传输延迟(transmission),类比于打电话的例子,这相当于人讲话时的速度。说完一句话本身需要20ms,而这整句话到达对方那里还要延迟250ms,所以对方听到整句话需要270ms(当然这句话的第一个字在第250ms时就开始听到了)。于是第270ms时整个帧才到达接收端,那么极限情况下,发送端则要在270ms+250ms=520ms时收到应答信号(也就是直到这个时候才听到对方回的话)。那么,即使在最好的情况下,实际上发送者在520ms中仅发挥了20ms的作用,20ms/520ms = 96%,或者说只有4%的带宽得到了利用。 审视一下就会发现,出现上述结果的一个主要原因是我们规定在接收到应答帧后再发送第二个帧。如果我们不这样规定,而是允许发送w个帧之后再等待应答帧,就可以解决这个问题(对应打电话的例子,就是我们先说好几句话,而不是先等对方答前一句话,当然这在打电话中有些奇怪)。只要w足够大,滑动窗口就不会满,数据就能持续地被发送。 我们通过bandwith-delay product来计算w,指的是带宽和传播延迟的乘积。我们把bandwith-delay product除以每一帧的比特数记为BD,那么我们取w=2BD+1。这么取的原因是,我们希望当我们的w个帧完全发送出去时,正好赶上对方对第一个帧的应答,这样我们就可以继续发新的帧了(对应打电话的例子,我们希望我们说完所有n句话的时候,正好听到对方对于第一句话的应答)。我们以刚才的数据具体为例:容易计算得到w=26.那么当我们发送出所有的帧后,正好是520ms,对方在第250ms时开始接收到第一个帧,在第270ms时接收完成,在第520ms时应答帧到达发送端,于是可以发送新的帧了。此后,每20ms就会有一个应答帧到来,正值把前一个帧发送出去,于是又可以发送新帧。所以我们一共需要大小为26的窗口就够了。如果窗口的大小不够大,就容易发生窗口满了然后堵塞的现象,我们有以下公式来衡量: 这是上界,我们甚至没有考虑处理帧所要花的时间以及应答帧的长度,当然这些时间是比较短的。上面的公式告诉我们,如果传播延迟很大,我们所需要的窗口就要很大。如果我们采用以前的策略,也就是说w=1,那么即使延迟只是一个帧大小的量,效率也会远小于50%。这种让很多帧发送出去但还没处于应答的策略称为流水线(pipelining)。 当然之前的讨论是非常理想的。第一个明显的问题是,这么多的帧同时发送,如果中途某几个帧丢失了怎么办呢,在接收方发现出错之前,后续的帧慢慢地来到了。对于接收到错误帧的接收方,如何处理后续到来的正确帧呢?注意无论如何,接收方发送给网络层的帧必须是按顺序的。在流水线策略中,有两种基础的方法来解决这种错误问题。今天要介绍的这种,称为回退N(go-back-n),它的实现较为简单,策略就是舍弃接下来的所有帧,不对那些帧发送应答。这种策略实际上就对应了接收窗口的大小是1,换句话说,如果来的帧不是接收窗口所需要的下一个帧,就统统舍弃。如果在超时之前发送者的发送窗口被填满了,流水线上就慢慢没有作业了,最终发送者会因为超时而重发之前的帧。当然,这个策略在错误率较高的情况下会浪费大量带宽。   基于上述讨论,我们可以设计一个go_back_n的协议了,需要改动的地方较多,先放出代码,再一一分析。 static bool between(seq_nr a, seq_nr […]

基础链路层协议(五):双向通信初步--单比特滑动窗口协议

December 8, 2014 at 1:47 am

接下来我们正式讨论双向通信。接下来的几节中,我们将从最简单的单比特滑动窗口协议开始,慢慢扩充、完善滑动窗口协议。 首先介绍一下滑动窗口协议中的一些基本概念。 在滑动窗口协议中,每一个发出去的帧都带有一个sequence number,事实上我们再协议3中已经使用了这个概念来记录编号。在滑动窗口协议中,通常sequence number是一个0到某个特定最值之间的一个数字,最值一般是,以方便sequence number正好存在n-bit中。滑动窗口协议最核心的地方在于任何时刻,发送端总是维护了它可以发送的帧的sequence number的集合,我们称这些帧落在sending window[发送窗口]中。与之对应地,接收端维护了它能接收的帧的集合,称为receiving window[接收窗口]。发送窗口和接收窗口的上界和下界不一定相同,甚至它们的大小也不一定相同。在一些协议中它们的大小是固定的,而在另一些中甚至随着帧的接收、发送窗口的大小也发生变化。 发送窗口中维护了那些未收到应答的帧的序号,这些帧可能已经发送,或者将要被发送,总之还没收到应答。当一个包从网络层过来时,它被赋予最小的可用的sequence number,由此将窗口的upper edge[上界]增加1;类似地,当一个应答过来时,窗口的lower edge[下界]增加1。通过这种方式,窗口总是维护着一个未应答帧的(序号的)列表。 上图给出了一个单窗口的3-bit sequence number的窗口运作示意图。 (a)状态是初态,此时发送端的上界和下界都指向区域0的左边,表示没有数据,下一个可用序号是0,我们记一个区域的左边界的编号为区域编号,所以此时下界和上界均为0;接收端的下界为0,上界为1,如灰色部分所示,接收方期待序号为0的数据。 (b)状态中,发送方从网络层得到了一个帧,于是标记为序号0,上界加1,变为1,指向区域1的左端。 (c)状态中,接收方成功接收到0号帧,于是上界和下界都增加1,期待序号为1的数据。此时发送方没有收到应答帧,所以状态不变。 (d)状态中,发送方成功收到了应答帧,于是下界加1,下一个可用序号为1。 […]