高级计算机网络(改版).docx

1 试从多个方面比较电路交换、报文交换和分组交换的主要优缺点。答 ：（1）电路交换在通信之前要在通信双方之间建立一条被双方独占的物理通路。优点：传输数据的时延非常小，实时性强，不存在失序问题。控制较简单。缺点：电路交换的平均连接建立时间长，信道利用率低。（2）报文交换 将用户的报文存储在交换机的存储器中。当所需要的输出电路空闲时，再将 该报文发向接收交换机或终端，它以“存储转发”方式在网内传输数据。优点：中继电路利用率高，可以多个用户同时在一条线路上传送，可实现不同速率、不同规程 的终端间互通。缺点：以报文为单位进行存储转发，网络传输时延大且占用大量的交换机内存和外存，不能满足对实时性要求高的用户。（3）分组交换 分组交换采用存储转发传输方式，但将一个长报文先分割成若干个较短的分组，然后把这些分组逐个地发送出去。优点：带宽利用率高，动态分配传输带宽，对通信链路是逐段占用。可生存性高，采用网状拓扑和分布式路由选择协议，并且无需建立链路。缺点：时延较大，分组在个节点存储转发时需要排队，这会造成一定的时延，转发效率低。一方面转发分组需要查找路由表，另一方面分组必须携带首部，造成一定的额外开销。2 因特网的两大组成部分（边缘部分与核心部分）的特点是什么？他们的工作方式各有什么特点？答：边缘部分 由所有连接在因特网上的主机组成。特点：用户直接使用的，用来进行通信和资源共享。核心部分 由大量网络和连接这些网络的路由器组成。特点：为边缘部分提供服务（提供连通性和交换）。边缘部分的通信方式：客户-服务器方式（ C/S 方式），对等方式（ P2P 方式）客户和服务器都是指通信中所涉及的两个应用进程。客户端：服务的请求方；客户程序必须知道服务器程序的地址。不需要特殊的硬件和很复杂的操作系统。服务器:服务的提供方；通过不间断的监听，被动地等待并接受来自各地的客户的通信请求。服务器程序不需要知道客户程序的地址。一般需要强大的硬件和高级的操作系统支持。对等连接方式是指两个主机在通信时并不区分哪一个是服务请求方还是服务提供方。对等连接方式从本质上看仍然是使用客户服务器方式，知识对等连接中的每一个主机既是客户又是服务器。核心部分 向网络边缘中的大量主机提供连通性，使边缘部分中的任何一个主机都能够向其他主机通信。 在网络核心部分起特殊作用的是路由器。路由器是实现分组交换的关键构件，其任务是转发收到的分组。 3 计算机网络有哪些常用的性能指标？答：1.速率 比特（bit）是计算机中数据量的单位。速率即数据率(data rate)或比特率(bit rate)是计算机网络中最重要的一个性能指标。速率的单位是 b/s，或 kb/s, Mb/s, Gb/s 等。2.带宽“带宽”是数字信道所能传送的“最高数据率”，单位是“比特每秒”，或 b/s3.吞吐量吞吐量(throughput)表示在单位时间内通过某个网络的数据量。吞吐量受网络的带宽限制。4.时延发送时延 发送数据时，数据帧从结点进入到传输媒体所需要的时间。 也就是从发送数据帧的第一个比特算起，到该帧的最后一个比特发送完毕所需的时间。传播时延 电磁波在信道中需要传播一定的距离而花费的时间。处理时延 交换节点为存储转发而进行一些必要的处理所花费的时间。排队时延 节点缓存队列中分组排队所经历的时延。总时延=发送时延+传播时延+处理时延+排队时延5.利用率 指出某信道有百分之几的时间是被利用的。4 分层的概念，分层的好处。答：分层的概念：分层可将庞大而复杂的问题，转化为若干较小的局部问题，而这些较小的局部问题就比较易于研究和处理。（1）各层之间是独立的。（2）灵活性好。（3）结构上可分隔开。（4）易于实现和维护。（5）能促进标准化工作。 各层所要完成的功能：（1）差错控制（2）流量控制（3）分段和重转（4）复用和分用（5）连接建立和释放。分层的缺点：有些功能会在不同的层次中重复出现，因而产生了额外开销。5 试述七层协议的网络体系结构的要点，包括各层的主要功能。答： 各层的主要功能：（1）应用层应用层直接为用户的应用进程提供服务。应用层协议：HTTP、SMTP、FTP等。表示层：功能是定义数据格式及加密。会话层：定义了如何开始、控制和结束一个会话。会话层主要功能：1.为会话实体建立连接2.数据传输3连接释放(2）运输层任务是负责向两个主机中进程之间的通信提供服务。 因特网的运输层可使用两种不同的协议。即面向连接的传输控制协议 TCP 和无连接的用户数据报协议 UDP。 面向连接的服务能够提供可靠的交付。无连接服务则不能提供可靠的交付。只是 best-effort delivery.(3)网络层网络层负责为分组选择合适的路由，使源主机运输层所传下来的分组能够交付到目的主机。（4）数据链路层数据链路层的任务是将在网络层交下来的数据报组装成帧（frame)，在两个相邻结点间的链路上实现帧的无差错传输。（5）物理层物理层的任务就是透明地传输比特流。6 IP地址的编制方案。IP协议是Internet的核心协议，提供数据传输的最基本服务，实现网络互连。IP是不可靠的无连接数据报协议，提供尽力而为的传输服务。IP协议屏蔽了物理网的差异，实现了地址和数据单元格式的统一（1）分类的 IP 地址。IP 地址可以分为两级：IP 地址 := , n 地址由两个固定长度的字段组成：n 网络号net-id：标志主机（或路由器）所连接到的网络；n 主机号host-id：标志该主机（或路由器）。n 两级IP地址的优点n 第一，IP 地址管理机构在分配 IP 地址时只分配网络号，而剩下的主机号则由得到该网络号的单位自行分配。这样就方便了 IP 地址的管理。n 第二，路由器仅根据目的主机所连接的网络号来转发分组（而不考虑目的主机号），这样就可以使路由表中的项目数大幅度减少，从而减小了路由表所占的存储空间。 n 2子网的划分n IP 地址空间的利用率低（A类和B类） n 给每一个网络分配一个网络号会使路由表变得太大因而使网络性能变坏。 n 在 IP 地址中又增加了一个“子网号字段”，使两级的 IP 地址变成为三级的 IP 地址。n 这种做法叫作划分子网(subnetting) 。n 划分子网的基本思路n 从主机号借用若干个比特作为子网号 subnet-id，而主机号 host-id 也就相应减少了若干个比特。IP地址 := , , n 子网掩码n 从一个IP数据报的首部并无法判断源主机或目的主机所连接的网络是否进行了子网的划分。n 使用子网掩码(subnet mask)可以很方便地找出 IP 地址中的子网部分。 n 3 构成超网CIDR采用两级地址结构：IP地址 := , n CIDR 将网络前缀都相同的连续的 IP 地址组成“CIDR 地址块”。n CIDR的技术优点n 可根据各网络的实际大小，量身定制地址块，最有效的利用IP地址，减少浪费。n 可进行路由聚合，有效减少主干路由器的路由表规模。n CIDR 最主要的特点n CIDR 消除了传统的 A 类、B 类和 C 类地址以及划分子网的概念，因而可以更加有效地分配 IPv4 的地址空间。n CIDR使用各种长度的“网络前缀”(network-prefix)来代替分类地址中的网络号和子网号。n IP地址从三级编址（使用子网掩码）又回到了两级编址。 n 4地址转换NAT 所有使用本地地址的主机在和外界通信时需要在NAT路由器上将本地地址转换成IPG才能和因特网连接。7 IP包的组成。n 一个 IP 数据报由首部和数据两部分组成。n 首部的前一部分是固定长度，共 20 字节，在固定部分的后面是一些可选字段，其长度是可变的。 8 TCP和UDP的特点对比。UDP 的主要特点n UDP 是无连接的，即发送数据之前不需要建立连接。n UDP 使用尽最大努力交付，即不保证可靠交付，同时也不使用拥塞控制。n UDP 是面向报文的。UDP 没有拥塞控制，很适合多媒体通信的要求。 n UDP 支持一对一、一对多、多对一和多对多的交互通信。n UDP 的首部开销小，只有 8 个字节。 TCP 最主要的特点n TCP 是面向连接的运输层协议。n 每一条 TCP 连接只能有两个端点(endpoint)，每一条 TCP 连接只能是点对点的（一对一）。 n TCP 提供可靠交付的服务。n TCP 提供全双工通信。n 面向字节流。 7 传输层的可靠传输机制。可靠传输的工作原理（1） 停止等待协议使用确认和重传机制，可以在不可靠的传输网络上实现可靠的通信。这种可靠传输协议常被称为自动重传请求ARQ。ARQ表明重传的请求是自动进行的。接收方不需要请求发送方重传某个出错的分组。停止等待协议的优点是简单，缺点是信道利用率太低。（2） 连续ARQ协议 累计确认 接收方一般采用累计确认的方式。即不必对收到的分组逐个发送确认，而是对按需到达的最后一个分组发送确认，表示：到这个分组为止的所有分组都已正确收到了。累计确认的优点是：容易实现，即使确认丢失也不必重传。缺点：不能向发送发反应出接收方已经正确收到的所有分组的信息。回退N（GO-back-N）表示需要再退回来重传已发送过的N个分组。当通信线路质量不好时，连续ARQ协议会带来负面的影响。TCP的三次握手连接过程：1. 建立连接，客户端发送syn包(syn=j)到服务器，并进入SYN_SEND状态，等待服务器确认。2. 服务器收到syn包，必须确认客户端的SYN（ack=j+1）,同时自己也发送一个SYN包（SYn=k）,此时服务器进入SYN_RECV状态。3. 客户端收到服务器的SYN+ACK包，向服务器发送确认包ACK（ack=k+1）,发送完毕后，客户端和服务器进入established状态，完成三次握手，客户端与服务器开始传送数据。（1）TCP提供传输的可靠性：应用数据被分割成TCP认为最适合长度进行发送。当TCP发出一个报文后，它启动一个定时器，等待目的端确认收到这个报文段。如果不能及时收到一个确认，将重发这个报文段。TCP将保持它首部和数据的校验和。如果收到段的校验和有差错，TCP将丢弃这个报文段和不确认收到此报文段。TCP报文段的到达也可能会失序。如果必要，TCP将对收到的数据进行重新排序，将收到的数据以正确的顺序交给应用层。TCP的接收端必须丢弃重复的数据。TCP提供流量控制。TCP连接的每一方都有固定大小的缓冲空间。TCP的接收端只允许另一端发送接收端缓冲区所能接纳的数据。TCP传输是传输层与网络层、应用层间的数据传送。它以报文段为单位进行传输的传输方式，超时重传的策略等，都为传输提供了可靠性。TCP的流量控制1. 利用滑动窗口实现流量控制建立连接时，每端都为该连接分配一块接收缓冲区。接收方通过将缓冲区的剩余空间大小放入windows size域来通知发送方。当接收方将数据交给应用程序后，发送一个ACK段来告知发送方新的接收窗口大小。发送方每次发送的数据量不能超过windowns size中指定的字节数。TCp滑动窗口技术通过动态改变窗口大小来调节两台主机间数据传输。 如果发送方把数据发送得过快，接收方可能会来不及接收，这就会造成数据的丢失。所谓流量控制就是让发送方的发送速率不要太快，要让接收方来得及接收。 利用滑动窗口机制可以很方便地在TCP连接上实现对发送方的流量控制。流量控制：指点对点通信量的控制，是端到端正的问题。流量控制所要做的就是抑制发送端发送数据的速率，以便使接收端来得及接收。接收方流量控制和网络流量控制。设置窗口大小为w=min(cwnd,awnd)TCP的拥塞控制 拥塞控制：防止过多的数据注入到网络中，这样可以使网络中的路由器或链路不致过载。几种拥塞控制方法慢开始( slow-start )、拥塞避免( congestion avoidance )、快重传( fast retransmit )和快恢复( fast recovery )。TCP Tahoe 包括慢开始、拥塞避免、快重传三个阶段。慢开始：在不清楚网路环境的情况下向网络传送数据，要求TCP缓慢地探测网络以确定可用带宽，以避免突然传送大量数据而是网络拥塞。Start with cwnd=1(slow start),on each successful ACK increment cwndCwnd=ssthresh(慢开始阈值)慢开始算法的原理：在主机刚开始发送报文段是先设置拥塞窗口cwnd=1，即设置为一个最大报文段MSS的数值。在没收到一个对新的报文段的确认后，将拥塞窗口加1，即增加一个MSS的数值。用这样的方法逐步增大发送端的拥塞窗口cwnd，可以使分组注入到网络的速率更加合理。拥塞避免算法：让拥塞窗口cwnd缓慢地增大，即每经过一个往返时间RTT就把发送方的拥塞窗口cwnd加1，而不是加倍。这样拥塞窗口cwnd按线性规律缓慢增长，比慢开始算法的拥塞窗口增长速率缓慢得多。Start with cwmd=ssthreshOn each successful ACK:cwnd-cwnd+1/cwndLinear growth of cwndEach RTT:cwnd-cwnd+1Enter SS when loss(adjust ssthresh) 无论在慢开始阶段还是在拥塞避免阶段，只要发送方判断网络出现拥塞（其根据就是没有收到确认），就要把慢开始门限ssthresh设置为出现拥塞时的发送方窗口值的一半（但不能小于2）。然后把拥塞窗口cwnd重新设置为1，执行慢开始算法。这样做的目的就是要迅速减少主机发送到网络中的分组数，使得发生拥塞的路由器有足够时间把队列中积压的分组处理完毕。 如下图，用具体数值说明了上述拥塞控制的过程。现在发送窗口的大小和拥塞窗口一样大。快重传算法首先要求接收方每收到一个失序的报文段后就立即发出重复确认（为的是使发送方及早知道有报文段没有到达对方）,发送方只要一连收到三个重复确认就应当立即重传对方尚未收到的报文段。Adjusts ssthresh-max(flightsize/2,2)Enter slow start(cwnd=1)由于发送方尽早重传为被确认的报文段，因此整个网络的吞吐量提高了20%。算法描述：n 赋初值：n Cwnd=1；n Ssthresh=65535bytes;n Win=min(cwnd,awnd)；n Number=1;n Loop:n +number;n If (cwnd=Ssthresh)Cwnd+=1 /*慢启动*/n Else n /*拥塞避免*/n cwnd+=mss*(mss/cwnd)n If(overtime)n Ssthresh=(1/2)*cwnd;n Cwnd=1;n Goto loop;n n If number=3n win=losscwnd;n Ssthresh=1/2*cwnd;n Cwnd=1;/*快速重传*/n 快恢复算法，其过程有以下两个要点： . 当发送方连续收到三个重复确认，就执行“乘法减小”算法，把慢开始门限ssthresh减半。这是为了预防网络发生拥塞。请注意：接下去不执行慢开始算法。 . 由于发送方现在认为网络很可能没有发生拥塞，因此与慢开始不同之处是现在不执行慢开始算法（即拥塞窗口cwnd现在不设置为1），而是把cwnd值设置为慢开始门限ssthresh减半后的数值，然后开始执行拥塞避免算法（“加法增大”），使拥塞窗口缓慢地线性增大。TCP Reno：慢开始，拥塞避免，快重传，快恢复 区别：新的 TCP Reno 版本在快重传之后采用快恢复算法而不是采用慢开始算法。 在采用快恢复算法时，慢开始算法只是在TCP连接建立时和网络出现超时时才使用。随机早期检测RED基本思想：通过监控路由器输出端口队列的平均长度来探测拥塞，一旦发现拥塞逼近，就随机地选择连接来通知拥塞，使他们在队列溢出导致丢包之前减小拥塞窗口，降低发送数据速度，从而缓解网络拥塞。特点：基于FIFO队列调度策略的，并采用了基于时间的平均队列长度，并且随机的选择正进入路由器的分组进行丢弃。这种方法能被有效地实施而无需在路由器中维持每个流的状态信息。因此其实施起来也较为简单。n 使路由器的队列维持两个参数，即队列长度最小门限 THmin 和最大门限 THmax。n RED 对每一个到达的数据报都先计算平均队列长度 LAV。n 若平均队列长度小于最小门限 THmin，则将新到达的数据报放入队列进行排队。n 若平均队列长度超过最大门限 THmax，则将新到达的数据报丢弃。n 若平均队列长度在最小门限 THmin 和最大门限THmax 之间，则按照某一概率 p 将新到达的数据报丢弃。9 Dij算法和DV算法1 IIntialization: 2 N = A 3 for all nodes v 4 if v adjacent to A 5 then D(v) = c(A,v) 6 else D(v) = infinity 7 8 Loop 9 find w not in N such that D(w) is a minimum 10 add w to N 11 update D(v) for all v adjacent to w and not in N: 12 D(v) = min( D(v), D(w) + c(w,v) ) 13 /* new cost to v is either old cost to v or known 14 shortest path cost to w plus cost from w to v */ 15 until all nodes in N 距离向量算法基本思想基本思想: u 如果邻居知道到达目的地的距离，且自己知道到达邻居的距离，则能算出自己到达目的地的距离 每个结点周期性地向其邻居发送自己距离矢量 当结点x接收到来自邻居的新DV估计，它使用Bellman-Ford方程更新其自己的DV :Dx(y) minv c(x,v) + Dv(y) 对每个结点y N1 Initialization: 2 for all adjacent nodes v: 3 D (*,v) = infinity /* the * operator means for all rows */ 4 D (v,v) = c(X,v) 5 for all destinations, y 6 send min D (y,w) to each neighbor /* w over all Xs neighbors */ 8 loop 9 wait (until I see a link cost change to neighbor V 10 or until I receive update from neighbor V) 11 if (c(X,V) changes by d) 13 /* change cost to all dests via neighbor v by d */ 14 /* note: d could be positive or negative */ 15 for all destinations y: D (y,V) = D (y,V) + d 16 17 else if (update received from V wrt destination Y) 18 /* shortest path from V to some Y has changed */ 19 /* V has sent a new value for its min DV(Y