桂林电子科技大学计算机科学与工程学院计算机科学导论课件 两军问题及网络协议.pptVIP

两军问题及网络协议 Andrew S. Tanenbaum在《计算机网络》（Computer Networks，潘爱民等译，清华大学出版社2004年8月第4版）一书中介绍了一个与网络协议有关的著名问题??两军问题（two army problem），用来说明协议设计的微妙性和复杂性。 两军问题可以这样描述：一支白军被围困在一个山谷中，山谷的两侧是蓝军。困在山谷中的白军人数多于山谷两侧的任一支蓝军， 两军问题及网络协议 而少于两支蓝军的总和。若一支蓝军对白军单独发起进攻，则必败无疑；但若两支蓝军同时发起进攻，则可取胜。两支蓝军希望同时发起进攻，这样他们就要传递信息，以确定发起攻击的具体时间。假设他们只能派谴士兵穿越白军所在的山谷（惟一的通信信道）来传递信息，那么在穿越山谷时，士兵有可能被俘，从而造成消息的丢失。现在的问题是：如何通信，以便蓝军必胜. 两军问题及网络协议 两军问题及网络协议 下面我们进行设计： 假设一支蓝军指挥官发出消息：“我建议在明天拂晓发起进攻，请确认”，如果消息到达了另一支蓝军，其指挥官同意这一建议，并且他的回信也安全送到，那么能否进攻呢？不能。这是一个两步握手协议，因为该指挥官无法知道他的回信是否安全送到了，所以，他不能发起进攻。 两军问题及网络协议 改进协议，将两步握手协议改为三步握手协议，这样，最初提出建议的指挥官必须确认对该建议的应答信息。假如信息没有丢失，并收到确认消息，则他须将收到的确认信息告诉对方，从而完成三步握手协议。然而，这样他就无法知道消息是否被对方收到，因此，他不能发起进攻。 两军问题及网络协议 那么现在采用四步握手协议会如何呢？结果仍是于事无补。 结论是：不存在使蓝军必胜的通信约定（协议）。 该结论可以用反证法证明，证明如下： 假如存在某种协议的话，那么，协议中最后一条信息要么是必要的，要么不是。如果不是，可以删除它，直到剩下的每条消息都是至关重要的。若最后一条消息没有安全到达 两军问题及网络协议 目的地，则会怎样呢？刚才说过每条信息都是必要的，因此，若它丢了，则进攻不会如期进行。由于最后发出信息的指挥官永远无法确定该信息能否安全到达，所以，他不会冒险发动攻击。同样，另一支蓝军也明白这个道理，所以也不会发动进攻。 两军问题及网络协议 Andrew用“两军问题”来阐述“网络释放连接问题”的要点，而在实际中，当两台通过网络互连的计算机释放连接（相对应“两军问题”的发起进攻）时，通常一方收到对方确认的应答信息后，不再回复，就释放连接（用的是一个三步握手协议），这样处理，协议并非完全没有错，但通常情况下已经足够了。本书不再讨论这个问题，但是，正如Andrew给出的结论那样，现在你应该很清 两军问题及网络协议 楚，释放一个可能有数据丢失的网络连接并不像人们初看起来那样简单。 两军问题及网络协议 网络协议（简称协议）是计算机网络的核心内容，它是为网络中的数据交换而建立的规则、标准或约定的集合。 实现计算机之间自动、可靠数据通信的网络协议，一般都极其复杂。借鉴复杂系统的研究方法，就是要进行集合的划分，于是人们将它划分为若干个子集（层次），各层各司其责，从而降低协议的复杂性，进而讨论和研究它们。 两军问题及网络协议 在Internet上，就是通过一个分层的具有不同功能的软件来实现数据交换的。这就像邮寄一个包裹的过程，首先将礼物打包，然后送到当地邮局，邮局通过货运公司的交通工具（可能经过若干中转站）将包裹送往目的地，目的地邮局将包裹取出，按照地址送给接收方，接收方打开包裹，取出礼物。 两军问题及网络协议 这个礼物的运送可以有三个层次来完成： （1）用户层； （2）邮局； （3）货运公司。 每一层将下一个较低层当作一种抽象工具使用（不用关心该层的细节）。在这个层次结构中的每一级在源地和目的地都有代表，在目的地的代表会与其在源地的对应代表进行相反的操作。 两军问题及网络协议 与此相似的，是控制Internet上通信的软件，其不同之处在于，Internet软件有四个层次，即应用层，传输层，网络层和链路层，每层均有相应的协议进行支撑，每台Internet上的机器都具有这样的软件及层次结构。一条信息在应用层产生，向下通过传输层和网络层的处理，然后通过链路层被传递。这个信息由目的地的链路层接收，通过网络层和传输层的逆操作，最后将信息送到应用层。 两军问题及网络协议 应用层包括所有的网络应用，如电子邮件、FTP、WWW等等。这些应用要支持该层相应的协议，如DNS（Domain Name System，域名系统），电子邮件协议（SMTP），文件传输协议（FTP），超文本传输协议（HTTP）等。从应用层产生的信息首先发送到传输层。 两军问题及网络协议 传输层从应用层接收信息，并将信息分成小的