2011年10月22日

TCP连接的3次握手和4次挥手

在TCP/IP协议中,TCP协议提供可靠的连接服务,采用三次握建立一个连接。

      第一次握手:建立连接时,客户端发送syn包(syn=j)到服务器,并进入SYN_SEND状态,等待服务器确认;

      第二次握手:服务器收到syn包,必须确认客户的SYN(ack=j+1),同时自己也发送一个SYN包(syn=k),即SYN+ACK包,此时服务器 进入SYN_RECV状态;

      第三次握手:客户端收到服务器的SYN+ACK包,向服务器发送确认包ACK(ack=k+1),此包发送完毕,客户端和服务器进入ESTABLISHED状态,完成三次握手。 完成三次握手,客户端与服务器开始传送数据。


四次挥手

由于TCP连接是全双工的,因此每个方向都必须单独进行关闭。这个原则是当一方完成它的数据发送任务后就能发送一个FIN来终止这个方向的连接。收到一个FIN只意味着这一方向上没有数据流动,一个TCP连接在收到一个FIN后仍能发送数据。首先进行关闭的一方将执行主动关闭,而另一方执行被动关闭。

(1)客户端A发送一个FIN,用来关闭客户A到服务器B的数据传送。

(2)服务器B收到这个FIN,它发回一个ACK,确认序号为收到的序号加1。和SYN一样,一个FIN将占用一个序号。

(3)服务器B关闭与客户端A的连接,发送一个FIN给客户端A。

(4)客户端A发回ACK报文确认,并将确认序号设置为收到序号加1。


为什么需要“三次握手”

            在谢希仁著《计算机网络》第四版中讲“三次握手”的目的是“为了防止已失效的连接请求报文段突然又传送到了服务端,因而产生错误”。在另一部经典的《计算机网络》一书中讲“三次握手”的目的是为了解决“网络中存在延迟的重复分组”的问题。这两种不用的表述其实阐明的是同一个问题。
            谢希仁版《计算机网络》中的例子是这样的,“已失效的连接请求报文段”的产生在这样一种情况下:client发出的第一个连接请求报文段并没有丢失,而是在某个网络结点长时间的滞留了,以致延误到连接释放以后的某个时间才到达server。本来这是一个早已失效的报文段。但server收到此失效的连接请求报文段后,就误认为是client再次发出的一个新的连接请求。于是就向client发出确认报文段,同意建立连接。假设不采用“三次握手”,那么只要server发出确认,新的连接就建立了。由于现在client并没有发出建立连接的请求,因此不会理睬server的确认,也不会向server发送数据。但server却以为新的运输连接已经建立,并一直等待client发来数据。这样,server的很多资源就白白浪费掉了。采用“三次握手”的办法可以防止上述现象发生。例如刚才那种情况,client不会向server的确认发出确认。server由于收不到确认,就知道client并没有要求建立连接。”

为什么需要“四次挥手”
            那可能有人会有疑问,在tcp连接握手时为何ACK是和SYN一起发送,这里ACK却没有何FIN一起发送呢。原因是因为tcp是全双工模式,接收到FIN时意味将没有数据再发来,但是还是可以继续发送数据。

附录:状态详解

       CLOSED:表示初始状态。

       LISTEN:表示服务器端的某个SOCKET处于监听状态,可以接受连接。    

       SYN_RCVD:这个状态表示接受到了SYN报文,在正常情况下,这个状态是服务器端的SOCKET在建立TCP连接时的三次握手会话过程中的一个中间状态,很短暂,基本上用netstat你是很难看到这种状态的,除非你特意写了一个客户端测试程序,故意将三次TCP握手过程中最后一个ACK报文不予发送。因此这种状态时,当收到客户端的ACK报文后,它会进入到ESTABLISHED状态。

      SYN_SENT: 这个状态与SYN_RCVD相呼应,当客户端SOCKET执行CONNECT连接时,它首先发送SYN报文,因此也随即它会进入到了SYN_SENT状态,并等待服务端的发送三次握手中的第2个报文。SYN_SENT状态表示客户端已发送SYN报文。

     ESTABLISHED:表示连接已经建立

     FIN_WAIT_1: 这个状态要好好解释一下,其实FIN_WAIT_1和FIN_WAIT_2状态的真正含义都是表示等待对方的FIN报文。而这两种状态的区别是:FIN_WAIT_1状态实际上是当SOCKET在ESTABLISHED状态时,它想主动关闭连接,向对方发送了FIN报文,此时该SOCKET即进入到FIN_WAIT_1状态。而当对方回应ACK报文后,则进入到FIN_WAIT_2状态,当然在实际的正常情况下,无论对方何种情况下,都应该马上回应ACK报文,所以FIN_WAIT_1状态一般是比较难见到的,而FIN_WAIT_2状态还有时常常可以用netstat看到。

  FIN_WAIT_2:上面已经详细解释了这种状态,实际上FIN_WAIT_2状态下的SOCKET,表示半连接,也即有一方要求close连接,但另外还告诉对方,我暂时还有点数据需要传送给你,稍后再关闭连接。

  TIME_WAIT: 表示收到了对方的FIN报文,并发送出了ACK报文,就等2MSL后即可回到CLOSED可用状态了。如果FIN_WAIT_1状态下,收到了对方同时带FIN标志和ACK标志的报文时,可以直接进入到TIME_WAIT状态,而无须经过FIN_WAIT_2状态。

  CLOSING: 这种状态比较特殊,实际情况中应该是很少见,属于一种比较罕见的例外状态。正常情况下,当你发送FIN报文后,按理来说是应该先收到(或同时收到)对方的ACK报文,再收到对方的FIN报文。但是CLOSING状态表示你发送FIN报文后,并没有收到对方的ACK报文,反而却也收到了对方的FIN报文。什么情况下会出现此种情况呢?其实细想一下,也不难得出结论:那就是如果双方几乎在同时close一个SOCKET的话,那么就出现了双方同时发送FIN报文的情况,也即会出现CLOSING状态,表示双方都正在关闭SOCKET连接。

  CLOSE_WAIT: 这种状态的含义其实是表示在等待关闭。怎么理解呢?当对方close一个SOCKET后发送FIN报文给自己,你系统毫无疑问地会回应一个ACK报文给对方,此时则进入到CLOSE_WAIT状态。接下来呢,实际上你真正需要考虑的事情是察看你是否还有数据发送给对方,如果没有的话,那么你也就可以close这个SOCKET,发送FIN报文给对方,也即关闭连接。所以你在CLOSE_WAIT状态下,需要完成的事情是等待你去关闭连接。

  LAST_ACK: 这个状态还是比较容易好理解的,它是被动关闭一方在发送FIN报文后,最后等待对方的ACK报文。当收到ACK报文后,也即可以进入到CLOSED可用状态了。

posted @ 2011-10-22 00:50 csolay 阅读(473) | 评论 (0)编辑 收藏

扩展堆栈(stack) O(1) 时间访问栈中最小值(或最大值)

问题描述:扩展stack的实现,完成正常的push,pop操作,新增访问最小(或最大)元素的接口Min(),使得push,pop,Min的时间复杂度都是O(1)。

问题分析:拿到这道题,我们最先的思考往往是,设计一个算法从栈中拿到最小值,所以开始考虑任何可以用来实现该功能的排序和查找算法。假设栈中有n个元素,一切排序和查找都不可能实现O(1)的时间复杂度找到最小值。

再看题目,既然是扩展stack的实现,stack是一种数据结构,一种数据的组织方式,扩展它,也就允许我们对其数据组织方式和存储内容作一些改变吧。所以我们就有了下面的思路:

把当前最小值存起来,并且在进行push和pop操作的时维护它。维护要求如下:

1、如果有比当前最小值大的元素入栈,当前最小值不变

2、如果有比当前最小值小(或等于)的元素入栈,当前最小值变为新加入元素

3、如果有比当前最小值大的元素出栈,当前最小值不变(注意:弹出的操作时,一定不可能弹出比当前最小值还小的元素,也就是说如果你弹出了一个比当前最小值还小的元素,就证明你的那个当前最小值不是当前最小值)

4、如果有和当前最小值的元素相同出栈,当前最小值变为当前当前最小值入栈之前那个最小值,当前最小值退出。

综上,我们发现一个规律:对于最小值而言,如果有更小的数入栈,需要将其保存为当前最小,如果当前最小数出栈,当前最小数变成当前最小数入栈之前那个最小数,所以,对于最小数而言也具有先进后出,后进先出的特点,只是并不是每次push和pop操作都牵涉到最小数的进出。所以我们考虑用双栈来实现,一个栈用来存放数据,满足栈数据结构原始要求,一个栈用来存放最小值,在每次push和pop操作执行时,按照上面的规则维护最小值栈。

posted @ 2011-10-22 00:20 csolay 阅读(1011) | 评论 (0)编辑 收藏

仅列出标题  
<2019年2月>
272829303112
3456789
10111213141516
17181920212223
242526272812
3456789

导航

统计

常用链接

留言簿

随笔分类

随笔档案

友情链接

搜索

最新评论

阅读排行榜

评论排行榜