2015下半年软件设计师考点，难点3

　　Master Method 

　　T(n) = aT(n/b)+h(n)

　　a >=1 ; b >1 ; h(n) : 不参与递归的复杂度函数

　　判断n^log b (a)与h(n)的大小关系

　　= Θ(h(n)) ：该方法的复杂度为   Θ(h(n)*lg(n))

　　> Θ(h(n)) ：该方法的复杂度为   Θ(n^(log a/log b))

　　< Θ(h(n)) ：该方法复杂度为 Θ(h(n))

　　这样可以帮助你快速的分析出你得算法的复杂度是否符合要求。

算法

集线器、网桥、交换机

　　集线器（HUB）：物理层的设备。

　　　　因设备转发数据包引起的广播

　　　　HUB只能看懂物理层上的东西（比如一段物理信号），工作在局域网(LAN)环境

　　　　所起的作用相当于多端口的中继器。其实，集线器实际上就是中继器的一种，其区别仅在于集线器能够提供更多的端口服务，所以集线器又叫多口中继器。

　　　　工作过程：首先是节点发信号到线路，集线器接收该信号，因信号在电缆传输中有衰减，集线器接收信号后将衰减的信号整形放大，最后集线器将放大的信号广播转发给其他所有端口。

　　网桥，即桥接器（Network Bridge）：数据链路层设备。

　　　　可以对MAC 地址进行分区，隔离不同物理网段之间的碰撞（也就是隔离“冲突域”）。能从发来的数据包中提取MAC信息，并且根据MAC信息对数据包进行有目的的转发，而不采用广播的方式，这样就能减少广播风暴的出现，提升整个网络的效率

　　　　网桥却能看懂一些帧的信息

　　　　网桥的天性应该是：连接两个同构网络

　　　　一个端口可以连接一个网段（这里的网段是物理网段，并不是我们平时说的IP网段，是指IP 地址属于同一网络地址段（也就是IP 地址中的网络ID一样），位于不同地理位置的不同LAN 分段，是基于物理意义上的地理区域进行划分的）

　　　　网桥只有两个端口，所以所连接的两个物理网段的主机通常就是由当时的集线器进行集中连接的（网桥端口通常不是直接连接主机的）。软件中通常所说的桥接（如VMware中的桥接工作模式）也就是网桥的作用，它连接的也是同一网络或子网中的两个网段。

　　　　基本网桥只有两个端口，还有一种网桥叫做多口网桥，多口网桥有多个端口

　　　　网桥常用于将共享带宽的计算机结点数较多的大局域网分成既相对独立又能相互通信的两个局域网网段，从而改善各个子网段的性能和安全性。

　　交换机（Switch）：数据链路层设备　

　　　　作用是转发数据包。和网桥一样它也是通过识别帧中的MAC地址，然后对特定的端口进行转发的。

　　　　能看懂一些帧的信息

　　总结：

　　　　网桥和交换机用户分割冲突域，就是网桥和交换机可以较少被逼的广播(hub导致的)，但不能分割广播域。不严格地说，交换机可以看作网桥的高度集成。

　　　　HUB 所有端口都在同一个广播域，冲突域内。
　　　　Switch所有端口都在同一个广播域内，而每一个端口就是一个冲突域。
　　　　Router的每个端口属于不同的广播域。

邮件协议

　　SMTP（Simple Mail Transfer Protocol）,简单邮件传输协议:

　　　　SMTP协议属于TCP/IP协议族，它帮助每台计算机在发送或中转信件时找到下一个目的地，端口为25。

　　　　建模在 FTP 文件传输服务上的一种邮件服务，主要用于传输系统之间的邮件信息并提供来信有关的通知，它是一组用于由源地址到目的地址传送邮件的规则，由它来控制信件的中转方式。

　　POP（Post Office Protocol）： 是一种电子邮局传输协议，而 POP3 是它的第三个版本

　　　　规定了怎样将个人计算机连接到 Internet 的邮件服务器和下载电子邮件的电子协议，端口为110

　　IMAP:交互式邮件存取协议：主要作用是邮件客户端（例如MS Outlook Express)可以通过这种协议从邮件服务器上获取邮件的信息，下载邮件等。　　　　

　　　　运行在TCP/IP协议之上，使用的端口是143。

　　总结：

　　　　1.用户在发送邮件时，会先按照SMTP协议，将邮件发送到发送者的SMTP服务器上，接着再由发送者SMTP服务器将邮件发送到接收者的SMTP邮件服务器上，最后由接收者通过pop3协议从接收服务器上将邮件下载下来

　　　　举个例子，用户A( aaa@126.com)要向用户B( bbb@qq.com)发送一封邮件，那么邮件会先发送到发送SMTP服务器上即smtp.126.com,然后由smtp.126.com投送到smtp.qq.com,最后再到bbb@qq.com上。

　　　　2.POP允许电子邮件客户端下载服务器上的邮件，但是您在电子邮件客户端的操作（如：移动邮件、标记已读等），这是不会反馈到服务器上的，比如：您通过电子邮件客户端收取了QQ邮箱中的3封邮件并移动到了其他文件夹，这些移动动作是不会反馈到服务器上的，也就是说，QQ邮箱服务器上的这些邮件是没有同时被移动的 。但是IMAP就不同了，电子邮件客户端的操作都会反馈到服务器上，您对邮件进行的操作（如：移动邮件、标记已读等），服务器上的邮件也会做相应的动作。也就是说，IMAP是“双向”的。同时，IMAP可以只下载邮件的主题，只有当您真正需要的时候，才会下载邮件的所有内容。

TCP流量控制、拥塞控制

流量控制：

　　让发送发送速率不要过快，让接收方来得及接收。利用滑动窗口机制就可以实施流量控制。

      原理这就是运用TCP报文段中的窗口大小字段来控制，发送方的发送窗口不可以大于接收方发回的窗口大小。

　　TCP的两端都有发送/接收缓存和发送/接收窗口。TCP的缓存是一个循环队列，其中发送窗口可以用3个指针表示。而发送窗口的大小受TCP数据报中窗口大小的影响，TCP数据报中的窗口大小是接收端通知发送端其还可以接收多少数据，所以发送窗口根据接收的的窗口大小的值动态变化。

　　流量控制往往指点对点通信量的控制，是个端到端的问题。流量控制所要做的就是抑制发送端发送数据的速率，以便接收端来得及接收。

拥塞控制：

　　防止过多的数据注入到网络中，这样可以使网络中的路由器或链路不致过载。

　　拥塞控制所要做的都有一个前提，就是网络能够承受现有的网络负荷。它是一个全局性的过程，涉及到所有的主机、所有的路由器，以及降低网络传输性能有关的所有因素。

路由：

主机路由：

　　也就是到单一设备的路由，那么肯定要使用255.255.255.255来限定单一ip地址。

　　目的地址是一个完整的主机地址

　　当为某个目的I P地址搜索路由表时，主机地址项必须与目的地址完全匹配

网络路由：

　　目的地址是一个网络地址（主机号部分为0）。

　　网络地址项只需要匹配目的地址的网络号和子网号就可以了

默认路由，缺省路由：

　　网络比较大的时候，用静态路由就比较不合适了。用缺省路由可以减少管理员的工作量

　　这个路由将匹配所有的包. 能帮助减少路由条目

　　目的地ip和子网掩码为0.0.0.0和0.0.0.0

　　在RIP协议中，特殊地址0.0.0.0表示默认路径路由。当RIP更新报文中不便于罗列出所有的网络，或者当一个路由器要处理所有未明确列出的网络通信时可以使用默认路径路由。通常，每个自治系统都有自己首选的默认路由，0.0.0.0项不会通过自治系统的边界。　　

　　是一种特殊的静态路由，指的是当路由表中与包的目的地址之间没有匹配的表项时路由器能够做出的选择。如果没有默认路由，那么目的地址在路由表中没有匹配表项的包将被丢弃· 默认路由在某些时候非常有效，当存在末梢网络时，默认路由会大大简化路由器的配置，减轻管理员的工作负担，提高网络性能。

静态路由：

　　一般是由管理员手工设置的路由。路由选择器不共享路由信息（单方向路由）

　　一般中小型的网络，网络拓扑比较简单，不存在线路冗余等因素，所以通常采用静态路由的方式来配置

动态路由：

　　路由器中的动态路由协议根据网络拓扑情况和特定的要求自动生成的路由条目。需要一个路由协议，如RIP或OSPF

　　大型网络网络拓扑复杂，路由器数量大，线路冗余多，管理人员相对较少，要求管理效率要高等原因，通常都会使用动态路由协议，适当的辅以静态路由的方式。

默认网关：

　　我们在我们PC机上配的默认网关就是默认路由，比如说我们的内网为192.168.1.0网段，出口路由器的内网端口地址为192.168.1.1（假设为末梢网络，路由器配置为默认路由），那样我们PC机的默认网关或者默认路由的下一条地址就是192.168.1.1

　　意思是如果要跟外网通信的话所有的包都发往192.168.1.1这个地址，也就是路由器的内网端口地址！这时路由器的默认路由再起作用，把所有的包发往路由器的WAN口或者下一跳！ip default gateway一般是在交换机上设置默认网关的命令！

直连路由：

　　发往直连路由的设备中不但具有指明目的端的I P地址，还具有其mac地址

网关路由，间接路由：

　　当报文被发往一个间接路由时，I P地址指明的是最终的目的地，但是mac地址指明的是网关（即下一跳路由器）。

总结：

　　默认路由与静态路由的区别

　　直连路由和网关路由是由下一跳区分的，而主机路由和网络路由是由目的地址的完整度区分的；

层次化局域网模型，局域网分层模型：

　　简化设计过程，提高组网效率

　　中小型、小型局域网一般可采用核心/接入层 ；大型、大中型局域网络一般可采用核心/汇聚/接入层