通信与网络笔记-网络部分

《通信与网络笔记-网络部分》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

通信与网络复习笔记——网络部分第八讲差错控制编码和线性分组码•信道的损伤导致差错，无法保证可靠性•差错控制传输重传：反馈，符号级译码→符号级编码反馈检验（收到再发）、检错重发（收端检错，反馈请求重发，适用于可靠性高）前向纠错：无反馈信道，发端不需要缓存，收端直接纠错，适用于信道差混合差错控制：纠错+重传，纠错成功则输出，纠错失败则要求重传•检错、纠错：发送上引入冗余。不是逐符号逐符号映射发送，而是成组的多个比特关联发送。多个信息比特→码组（码字）；消息字集合→发送空间（更大，冗余）。•分组码：输入信息kbit一组，每组长度n，则许用码组个数，总码组数可检错：差错后变成禁用码组。不可检错概率，编码效率（k/n，)越大，检错越强。kbit信息变成nbit码组，效率k/n。例子：1/3效率编码：0,1→{000,111}。检错：可以检任意2bit错，110肯定有错，*错2位bit。纠错：可以纠任意1bit错，110纠错为111，一位误比特。纠错1bit和检错2bit不可同时进行。•基带检错码：5B6B码，4B3T码（主要目的是抑制直流分量，检错能力低）5B6B另一种形式：奇偶校验码（码组1有奇数个，校验位=1）可以检出任意1bit错和奇数个错编码效率高：来源于成组的编码•前向纠错译码：最小差错概率（总差错概率最小）、最大似然准则（哪一个码组最像接收）所有可以发送的码组等概率时二者相等。最大似然：汉明距离度量相似性，越像距离最短。汉明距离：码组不同位数（最小）汉明距离d，错的个数不大于不会错判。（或错的个数<汉明距离-对的个数）所以纠错能力或者。•检错和纠错能力：若没有重传功能，检错意义不大，最小码距给定时应最大化纠错能力检错能力：任意图案差错不多于检错能力e可被检出

1纠错能力：任意图案差错不多于纠错能力t可被纠正e+1≤dmin纠错时检错：不多于e个能发现，不多于t个能纠正t+e+1≤dmin若给定纠错、检错指标，则有一个最小距离dmin，记为df（自由距），表征自由度纠错、检错不是同一体的，相邻的2个码组，一个可以检错e,则另一个是纠错t。大半径是检错的e，小半径是纠错的t。由于距离离散化，要求不相交等价于任意距离≥1•码长：编码后的总比特。效率（码率）：k/n，信息比特长度除以编码后总长一个分组码记为(n,k,df)•线性码：码组集合关于线性运算封闭，任意许用码组的线性组合仍是许用码组线性分组码：码长有限。线性运算：+，*，满足交换律、结合律、分配律。都在有限域上。（如二元域）本处的限域是伽罗华域——素数域，元素个数q是素数（q元），加分、乘法定义为模q的加和乘。码组常写为矢量。全0序列必然为许用码组。重量：非0元个数。汉明距离就是两个码组差的重量。许用码组的差也是许用码组。最小汉明距离（自由距）不低于最小许用码的码重（非0）。线性码：最小汉明距等于最小许用码重（非0）df=Mmin。•线性分组码(n,k)，p进制：全空间：n维空间，共有p^n个点，许用码组集：k维子空间，可以用一组基来表示。任意码组表示：gi是矢量

2长度为k的信息矢量：k维→n维映射，G是生成矩阵，K行n列。•一般生成矩阵向系统码生成矩阵转化A)系统码编码序列中直接包含所有信息符号的码是系统码。任意线性分组码可表达为系统码的形式。B)线性变换得到系统码生成矩阵：任意生成矩阵G，K行线性无关，可做分解，G1满秩，K行K列。其中，令P=就是系统码生成矩阵，关系G=G1*P；分解过程：对G行变换消元，直到左边出现单位阵，右边得到Q。对行进行可逆变换，得到的k行仍然是许用码字的一组基，不影响许用码字集合和最小码距。也可以有列变换。列交换把K列主元列移到前面。对列进行换位，等价于对编码后的序列c，变换符号顺序，不影响最小码距。C)编码：C=b*P，C的前K位是信息序列。后n-k位是监督位（校验）。设D=b*G，是用旧的生成矩阵得到的码，则系统码C和D许用码字集合相同，最小汉明距离相同，但是b→C和b→D的映射规则不同。O线性分组码译码：•检错：判断是否是许用码字，三种方法——遍历搜索、生成矩阵、校验矩阵I)生成矩阵检错：判据，成立与否解释：P是列交换矩阵保证G前K列线性无关，即G表示为。，f1是长度为K的行向量，f2长度n-k。Q：，对G作行消元得到，r是收到的码组。II)校验矩阵检错基本思想：找一组向量，其中每个都和所有许用码组正交。用它们与接收到的许用码组做内积看是否为0。任意许用码组都可以表达为，Q可以对G作分解得到。

3长度k的行向量f1和n-k的f2，是[f1f2]与所有许用码组正交的充要条件满足这个条件的[f1f2]可写为。校验矩阵：H=，各行均为校验序列。码空间和校验空间：全空间n维，生成矩阵G的空间是k维，校验矩阵的空间就是其零空间，维数n-k（若行数>n-k，也只有n-k维线性无关）。=0.检错：接收到r,是否为0.•有限域空间：没有单位矢量、投影的概念。同时出现在校验空间和码空间的序列不只有零。•纠错译码先检错，如果有错，则找一个最想的序列。接收到r，r=c+e，e是误差，c是差错控制编码，和校验矩阵正交。为校正子。校正子用于指示错误位置。可以得到一张最轻的误码图案表。译码：译收到的码、计算校正子的值，查表译出错码。对于重量为1的误码——若校正子和的第K行相同，则信息行向量的第K位错码。若没有哪行和校正子相同，则误码重量不为1。则有多种可能性。某些特定的2位错码判决后可能变成3位错码。能纠正一位错的充要条件：校验矩阵H各列不完全相同，且无全0列。纠正n位码，至少需要位校正子，即监督码，Q每行至少2个1，否则监督位自己错了。•汉明码：m个监督位,行数m列数取最大（再多无意义）,编码效率（3,7）码：3个监督位，7列，信息码长4。3个监督位可以指示8种错误，每种都是1位错码，所以纠错能力t=1。检错能力e=1。最小汉明距离3。生成矩阵：，转置监督矩阵汉明码的所有非0校正子，都有错码图案对应，属于完备码（冗余充分利用），可以纠出所有的错。

4•误码性能信道误比特率Pe，则出现不可纠错图案的概率：（上面考虑的是错码位数在纠错能力之内时）•AWGN信道，BPSK调制，编码效率为R，解调误码率△无编码调制误比特率：；编码调制：Eb1bit原始信息的传输能量*每个信息比特平均出错概率：•结论：二进制信道，大多数情况编码可以改善性能，而在恶劣环境下可能会越纠越错。引入冗余，牺牲带宽，损失能量，码率降低。码长越长性能越好。O循环码•线性分组码，常是系统码；循环性：若是许用码字，也是许用码字，依赖寄存器。•多项式表示：左移K位：O突发误码•发生于多进制调制实现的二进制信道。（MFSK）

5高SNR,格雷映射，最多错1bit，低SNR不止（尤其MFSK）。•突发错误信道：时变信道。突发错误长度：首错到尾错长度。•处理方法：为了对付突发的信道差错，交织器改变发送码元的时间顺序。原本时间上相邻的错码距离最大化。交织块矩阵：横着写入，竖着读出。设宽度（横）为n，深度（纵）为m。m决定了相邻码元交织后的间隔，又称交织深度。假设分组码能纠正b个突发错误，则交织后可以纠正mb个错误。但不是m越大越好，带来解码延迟。解交织：竖着写入，横着读出，解交织打散了突发误码。•高进制编码：多个相邻信息比特看成一组，形成一个高进制符号。例：8个比特看成一个字节（256进制），以字节为单位编码每k个多进制符号→(n,k)分组编码→n个多进制符号→比特流，送入有突发错的信道当突发错发生在一个比特组内部时，不管错几个比特，都只对应于一个多进制符号错，即比特组的突发错，变成了符号级的随机错。•O卷积码：针对信息流的编码•信息符号流→编码器→编码符号流I)分组码处理：分段，每段用线性分组码编码。，若非时变分组码段间无记忆II）卷积码处理：不分组，编码结果不存在有限长的一组参数：（n,k,N）。N约束长度（移位寄存器级次）；K信息码位，每次进出的bit数；n每次输出位数；码率：k/n，每次进来的位数比上出去的位数。

6•卷积码与分组码的比较卷积码：适合于流，看中误比特率，有记忆分组码：适合数据块，看中误字率把卷积码截短得到分组码。•有记忆的编码：当前的编码不仅受当前影响，受过去影响。当前n维输出由前后k位共同映射。引入记忆，哪怕丢了一组也可以恢复。输出编码流具有相关性。•有限记忆卷积码：输出取决于当前输入和D触发器取值。D触发器取值称为状态。I)多项式表示：Yk=ΣX(k-i)*AiAi是个k行n列矩阵，抽头加权系数，X是输入流矢量Di是延时例子：（2,1,3）码，n=2,k=1,m=3-1(延时)。则A为1行2列矩阵，求和项数为m+1=3约束长度N：抽头个数，等于寄存器（延时）个数+1II)矩阵表示每一行对应于相应延时的冲激响应III）树形表示（2,1,3）码为例

7事先画出树，标记好每条边的值。根据当前输入选择分支，当前输入为0，向上走，输入为1，向下走。根据状态输出，输出等于路径边上的值。(n,k,N)状态有M=个。（2,1,3）码有4个状态(记为abcd）。第四级分支就出现重复。记忆深度只有3。树的应用：计算最小码距。定义为，非零码字的最小码重。（2,1,3）码画出3级（记忆深度），从下走（上面出现全零状态），找到111000码重只有3,最小。所以最小码距是3.IV）网格图表示以两个D触发器的组合值为状态，描述从当前状态在不同的输入时的输出。左：每个分支上的标注为x/y，x表示当前的输入，y是编码输出初始状态00，信码来把路定，0上1下，编码去看路径V）状态图如果是非时变卷积码，网格图每一拍都一致的，可以画成状态转移图节点是寄存器的状态，边是状态的转移以及输出。

8先标状态点，再加转移边输出写一旁，自环不可忘状态图计算自由距：自由距等于寄存器从零状态开始，经过非零状态，再回到零状态•卷积码的最大似然译码特点：概率译码，软判决译码概率译码：不依靠代数结构，利用信道转移特性P(r|c)代数译码：分组码的译码方式，只利用代数结构。卷积码不具有很好的代数结构。软判决译码：r是连续的，P(r|c)可以描述连续信道硬判决译码：连续分布的接收符号判决成离散的，再译码，损失性能。•卷积码译码器的度量：似然值、距离编码矢量接收矢量I)似然值度量：相似度用条件概率描述（假设信道无记忆）值越大，相似度越高II)距离：总距离（平方）是每个分组距离（平方）之和距离越小相似性越高。•卷积码的概率译码：逐分支译码、维特比译码I）逐分支译码（2,1,3）码：编码符号0（向上）发-1；为1（向下）发+1

9收到2个符号，求最小距离等价于求最大相关，即2个符号作差（前-后）。差值小于0，向上走，差值大于0，向下走。II）维特比译码：动态规划的卷积译码方法A）硬判决和收尾代价：每段路径的值（编码时的输出）与对应接收码字的汉明距离最佳译码：最小代价的路径代价最小的最优路径=上一步最优路径+这一步中代价最小（贪婪算法）起始0状态。如果某状态多条最优路径，则只可检错不可纠错，随便选一条。没有现成代价图，基于网络接受码字确定，不必计算所有路径代价。沿着网格向前进，每态只留唯一径，对比序列算代价，计算很烦要细心收尾：若要求收尾（对应额外输入），则再筛选出一条。收尾指最后一步要回到00B）软判决除了计算代价，别的都和硬判决一样。代价计算：接收的符号值a,b做加法。每段路径的值（编码时的输出）决定了对应a,b相加的符号。0是’-’，1是’+’，如，若接收到00，则-a-b，若接受到01，则-a+b维特比译码复杂度：次加比选，每次加比选包含次加法和次比较。个贮存单元。•维特比译码的特点最大似然的序列译码算法复杂度与信道质量无关运算量、存贮量与码长呈线性关系运算量和存贮量都与状态数呈线性关系状态数随分组大小k及编码深度m呈指数关系第九讲复接与多址•构建信道（专享）：专线、频道、时段……构建信道（共享）：总线（可保证两两之间的可通性资源分享，使规模受限）、开放空间

10•多点之间的通信：全连通：信道数目正比于节点数目平方，所有信道可以同时工作；交换机：信道数目正比于节点数目。尽管信道数不再是瓶颈，但交换机的能力仍是瓶颈；多跳组网：基本正比。存在延时、拥塞。共性问题：时间管理机制，频率管理机制（链路间难以同步时，这是主要问题）•复接：将信息统一承载到信道多址：各源独自占用通道，各自接入O波形分割•区分信息以便接收端分离：根据区分的方式：时间分割、频率分割、扩频码分割、空间分割、编码分割按数学上的区分：正交分割、非正交分割•频率调制：最自然。独立调制、合并发送（复接FDM、多址FDMA）各路无需定时同步；可能造成较高的峰均比及交调。功放效率低。时间分割：TDM,TDMA。造成延迟。需要定时管理，峰均比低功放效率好TDM可以统一调制；

11•时分方法：（3种颜色表示3个通道，）周期性分组传输：积攒K个符号再传输，K个符号延时。一个时隙对应一个通道，包括通道标志。一帧多个时隙，时隙数≥通道数。一帧时间对应于单通道K个符号时长。符号级时间分割：。一帧对应于一个码元长度，包含多个时隙。一个时隙一个通道符号。突发包：收齐了才发有保护时隙，用于检测是否被他人占用。时分是频率混叠的，但若实现采样点无失真，可以不串扰。•正交基：[0,T]，带限波形可用正交基表示，2BT个基。fc=(fH+fL)/2基的组合系数是复基带波形按fs=B采样的值（实虚部）•若每个通道平均每T秒要传一个实电平符号，则：B带限的波形，可为2BT个通道服务若同一时刻的I、Q路分配给同一个通道，这样每个通道在一个T秒的时间里，可以传一个复电平符号，这样每T秒时间里，可以支持BT个复通道时限带限（复）信号：BT维度复空间，基：波形由BT维矢量X决定：•符号级码分割：将发送复基带波形写成一个BTs维列矢量

12对TB限，多电平通道的复用/多址，需要为每个电平通道分配一个基本波形不同通道的基本波形不同：第i个通道的基本波形，又可表示成一个BT维的列复矢量，记为ci=[c1i,c2i,…,cNi]’其中N=BT，可称其为通道i的特征码。不同通道的特征码不同，于是形成了所谓的码分多址/复用•码分割特殊形式：频分——C=Wn（FFT的基矩阵）；时分——C=I（单位阵）其他符号级码分割：在一个符号周期内选择不同的波形分配给不同的通路。n正交码：walsh码（正交性依赖于各路间的严格定时同步）n非正交码：随机码、长伪随机码（干扰程度取决于它们之间波形的相关系数）正交可用维数：符号周期与可用总带宽的乘积——BT（根据奈奎斯特采样定理）•码分割最佳接收：问题：，n是噪声（方差），s是信号（功率为P）解结构：最大信噪比——匹配滤波接收；，匹配检测子最小失真——迫零算法；，迫零检测子最小均方误差（噪声+失真）——高信噪比下=迫零，低信噪比=匹配，MMSE检测子•准则1,最大化信噪比：噪声显著强于干扰时，更关心SNR，

13有△处理增益为N，与带宽扩展比例（扩频比）相同•准则2，最小失真：ZeroForcing——强迫使失真为0，其中。解是所有通路的符号矢量估计，没有干扰项，但是噪声会增强。高SNR时，用这个方法可以把失真趋近于0。•准则3，最小均方误差：假设S是实Gaussian。输出y=as+n，噪声n(方差)与S(功率P)独立估计：。的最小条件：最小误差值：。a:抑制噪声信噪比很低，b→0，均方误差→P信噪比高，b→1/a，均方误差减少倍。复Gaussian信号估计：均方误差最小条件：，I、Q误差都最小，为复Gaussian随机矢量S估计：M维的S独立同分布，方差为P，N维的独立同分布方差为

14O空间分割•点到点多路复用：，复用空间矩阵形式Y=Hx+n；•特例：蜂窝小区：H是对角线占优矩阵•通信系统的例子：CDMA。每一个蜂窝小区内：下行：基站到终端，用不同正交码发送给客户，CDM（同步很好）上行：终端到基站，非正交码各自发送，CDMAO时分复用•时分中具体因素恒定业务速率：时延、抖动小，时隙划分细；非恒定业务速率：恒定速率的时有时无，动态分配时间资源，利用统计平稳，时延抖动大可能中断；固定分配时间资源，最大速率，延时、抖动小。突发包业务：包长为单位，时隙划分粗，时延、抖动大。（图：恒定速率、非恒定速率、动态分配）•信令：告知接收机控制信息（资源如何分配、同步头、动态变化）公共信令：涉及所有用户，专门开辟时隙；

15专用信令：一路用户，可占用为此路用户分配的时间资源•多级时分复接：底层，速率低，具体业务；高层，效率高，综合业务、透明数据业务。•恒定速率业务：同步复接，各路时钟频率一样，不易实现；异步复接，时间资源分配会不足或者溢出。解决办法：多预留。对设备要求低。异步多出来的时间资源：每时隙比特增加/若干时隙后加一时隙/采用动态分配。•单位时间各通道数据量有差异：完全统计复用：复接器集中处理，每时隙各路数据串起来发，用户数量很多的时候效果好标准盒子：单位时间各路数据量装入标准盒子，不满塞入填充位，盒子按最大容量设计，无法统计复用，各路速率相同，盒子大小与帧长、时隙长无关，只是为了调整码速率。盒子有标签，指示放入的是信息还是填充，标签要重点保护。（负面效果：定时抖动）•时分复用的开销：信令、同步（通常帧定时就是时隙定时，另外需要文件头）•帧同步/包同步：定时同步：找比特流的起始比特位置。做法：插入已知比特——集中插入（便于提取，适于突发）、均匀分散插入（引起延时、抖动小，适合恒定速率业务）同步定时提取：匹配滤波。统计相配符号，计算相似度。核心是存一段比特然后找同步头（长L），集中插入式需要存L比特，分散插入式需要存NL比特。分散插入式的其他提取方法：序贯检测方法。假设是同部位，观察L周期，验证，如果不对，观察下一位。最坏需要延时：LN*N。第二步的改进：先观察L1周期，判断“像”，再观察L2周期验证。O时分多址•集中式以中心向用户分配时隙资源，全网同步。支持多用户通过共享信道接入同一节点和互联。

16可能由于延时不同，到达时刻不同，产生碰撞。解决：设置发送提前量，保证同时到达。•分布式用户接入信道与否自己控制。Aloha协议：接入时间任意，碰撞弃包。SlottedAloha：只按时隙接入，碰撞弃包。解决：载波侦听多路接入CSMA，听到信道空闲才接入。•CSMA（载波侦听多址接入）：空闲，等待一个随机时间再接入。传输前，先用短协议建立握手，同时告知其他用户。发起方：RTS。若无碰撞，目的方回CTS。碰撞概率模型分析：K个用户，每时隙接入概率P，独立。成功传输=只有1个用户接入：KP=λ，K很大则近似为泊松分布。第十讲：交换与路由•通信共性问题：信息度量、可达性（点到点）、有效性（谱效率）、可靠性（差错中断率）网络核心目标：可达性，有效性-流量，延时小，代价低•单个交换机：入端可达任意出端，支持任意配对。多个交换机：解决距离过长，复接和解复接（复接器共享到达交换机的链路）双向链路交换可用单向交换机实现。•双工实现双绞线：四线制（每个方向一对双绞线）、二线制（二四线转换，一对双绞线上双向传输）微波器件：环形器。

17时分双工（需严格定时，可实现不对称链路）、频分双工（预留频带，两个方向不需要定时同步）。•复接器只能汇聚数据，减少传输距离，不能解决交换机瓶颈。解决：用交换机共享链路。交换机的树形结构：顶层负荷很高，故障影响大。扁平结构：一个交换节点到别的节点有多条通路，分担负载。•交换与路由交换：讨论一个节点，输入流与输出流分发执行。哪口的哪些数据送往哪口。解决多个节点的时分全连通问题路由：如何做决定，走哪条路。每个路口往哪走。一定连接下（各节点连接关系给定）的条件下，确定源的数据通过哪些节点到宿，以及每个交换节点的控制命令。•交换实现（交换机内部结构）：电路交换、分组交换。a)电路交换：电路建立，传送消息，电路释放。延时小，透明，快速。差错控制终端负责。空分：矩阵控制电路节点接通。时分：存贮及时隙交换。电路交换示意图：事先确定一条路径——某个入口的某个时隙，对应某个出口的某个时隙独享到拆链b)分组交换：数据块的形式进入入线（以完整的报文为单位，或者拆成短的数据块）不事先分配，采用存贮转发方式进行。独立控制每个数据分组，数据块自带路径信息，交换机负责差错控制。灵活进行，随到随走，忙时等待。O网络规划

18•权值矩阵：没有连接的边，权值无穷。权值为代价。•最小成本实现全连通——最小生成树算法。Prim算法，Kruskal算法。O路由选择：源到宿的路由设计•寻找代价最低路径——延时。集中式控制：适用于电路交换，控制器拥有全局信息，通过专用通道统一决策，数据流不携带控制信息，适用于恒速率业务。而突发业务效率较低。分布式控制：适用于分组交换，各节点有自主权。数据块的包头可以含有节点控制指令，但是当链路太长的时候开销很大。所以包头只带有源、宿地址，节点自己计算决策（如查路由表）•路由表：根据目的地址投递。输入：目的地址；输出：从本节点哪个端口送出数据。路由表的维护：集中式，主控设备计算，广播；分布式，节点自行计算。•路由表的分布式生成：距离矢量：给定节点，给定根和目标，找代价最低路径。Bellman-Ford，单源Dijkstra最短路径算法。链路状态：谁和谁之间有通路，好/坏，代价。当发生改变时告知其他节点。每个节点有个全局链路代价。每个节点都有：全局视图、自己的路由表、完全相同算法，并计算自己到其他所有节点最短路径（路由表）•单源Dijkstra。输入：有代价的网络图。输出：本节点到其他所有节点代价最小路径，产生路由树。第十一讲流量•利用连通网有效地传输，有效性评价：流量。限制因素：节点、链路、终端。O静态流量问题•单源宿流量最大问题：适用于恒定速率业务单源单宿网：有且只有一个源和宿，有向图。可行原则：每条边流量不超过容量；入流量等于出流量。路：连接源与宿的通路，多条边的串联；流：一条、多条路的使用•求最大流量：最大流-最小割定理

19单源单宿网络，一部分节点放入集合V1，剩余的放入，源在V1中，宿在中。割：（V1，）表示所有”起点在V1中，终点在中”的有向边的集合，称为一个割。这些有向边的容量和定义为割的容量。（割指有向图，割集针对无向图）最大流-最小割定理：最大流的值等于等于最小割的容量。•找最大流：迭代。找一条每边可以增流的路，增流，再重新寻找，不断做下去。增加反向边CM的流量，就是减小正向边MC的流量，等效。•标号法：1、检查和标记：任意选一个已标记未检查节点i，检查和i关联的节点，若有一个未标记的j，则计算并标记j。如果i关联的节点都标记过了，则设置i已检查。循环这一步。直到宿被标记（转向增广过程）或者没有节点可以被标记（算法结束）。通常是宿被标记，开始一轮增广。2、增广过程：随便找一条可增广路，及全路可增的最大流量e。若节点标记符号是正号，则上一条边的流量增加e,若符号是负，则上一条边减小e。并更新配送方案。循环1和2。细节：标记有三种状态——未标记、已标记未检查、已标记已检查。标记记为（n1,n2,n3）。n1:从哪个节点关联过来的。n2:‘+’表示前向边，可增流；‘-’表示非零反向边，可以通过对该边减流来等效路的增流。n3：从源出发经过n1到本节点可增大的最大流值。这个过程从源开始。源先标记为（X，+，∞）。为已标记，未检查。•推广。多源多宿：添加辅助源和宿。节点容量受限：分裂为两个节点，一入一出，中间权值为节点容量无向图：视为双向图O动态流量问题•排队论初步：顾客排队，或者理解为（分组交换中的）缓存器关注点：队长分布，缓冲区大小，服务延时，溢出、拒绝概率•影响因素

20输入过程：顾客流的分布（到达时间）排队规则：系统类型（拒绝与非拒绝），服务规则（先到先服务、先到后服务、随机服务....）服务机构：服务员数量，服务方式（流水线、并列），排队方式（分别排队、混合排队）•三个基本参数λ（顾客单位时间内到达数目）,μ（服务速率，平均时间倒数）,m（服务员数目）•M/M/1排队系统：泊松到达（λ）、指数服务（μ）、1个服务员，设缓冲区无穷大。最简单的顾客到达：到达过程是泊松过程（期望λ），到达时间指数分布（期望1/λ)。到达时间，等价于数据包大小无记忆性：无论何时，下一个顾客到达时间都是相同指数分布。服务速率：单位时间，可服务的用户数目期望是μ，服务时间是期望1/μ的指数分布。•系统里有K个顾客的概率：t时刻有k个顾客概率Pt,k（泊松）则t→t+Δt内，有k个顾客的概率•系统稳定：则，再定义系统负载：ρ=λ/μ有差分方程：，边界条件由边界条件可以确定归一化解：平均顾客：•每个新顾客到达时，排在自己前面的顾客数量的期望是“系统内平均顾客数”排在自己前面的每个顾客的服务时间的期望是“平均每顾客服务时间”他们全部服务完成的时间的期望，就是自己要等待的时间的期望，即“平均等待时延”Little定理：系统内平均顾客×平均每顾客服务时间（即1/μ)=平均等待时延

21平均逗留时间=平均等待时间+平均服务时间•系统效率：平均窗口（服务员）占用率。单服务员系统：有顾客概率。占用率高：利用率高的同时，负荷也高，代价是服务质量下降（客观说是延时增加）。MM1:模型，当系统负载接近1时，队长和延时都会趋于无穷分组交换中，路由节点处的缓存器(buffer)：缓存常空，延时小，但是利用率低；常满，延时高，但利用率低。评判：负荷/延时——解决办法：让网络工作在合适工作点，控制流量•业务产生的随机性和节点转发不同步（服务时间随机性），导致了多节点网络到达和离去特别像M/M/1模型。•流量控制：网的情况决定恒流量业务，电路交换，预先为收发建立一个流（多条路），集中式控制随机业务（突发业务）：分组交换提高利用率，引入排队和缓存，瞬时可以节点入流量≠出流量（长期来说依然成立）•源头流量控制：每一对源、宿都是贪婪的，会尽可能抢资源，源会将自己送人的流量推到最大。大型网络、端到端自行控流：动态调整从源进入网络的业务量。面向用户，属于端到端，分层架构中属于高于网络层的内容（传输层），负责高层与网络层之间的接口。•传输层：端到端连接管理（建立与拆除）、差错控制（向上提供可靠的数据流服务）流量控制（向下保证网络的高效利用）差错主要来源：物理层、链路层差错，网络拥塞导致的丢包；主要控制手段，重传流量控制：网络判断主动控制，利用差错控制环节。TCP协议：面向连接、可靠的传输层协议。保证可靠性、流量控制、拥塞控制•流量控制两个环节

22a)流量调整：传输参数调整b)获取网络层信息：主动告知；盲估计（TCP采用），通过服务可靠性判断盲估计：使用差错控制，反馈确认。收端只确认收到的包（不管丢失的），每收到就回复ACK。发端等一定时间，没有ACK则重发。TCP中对应RTO（倒计时器的初值），由往返传输延时决定。另外，没有在RTO中收到ACK，则可认为网络拥挤，降低发包速率。盲估计的特点：“探测”网络状态；二值性——好（RTO内），坏（超时），好的时候不知道离坏有多远，坏的时候需要紧急规避，所以，‘好’的时候，流量缓慢提高，‘坏’的时候，流量迅速降低。执行：TCP滑窗和GobackN。收端回复一个ACK，发端发送一段窗长的数据。窗口大小决定数据速率，收端发端共同决定窗口长（取最小值）。超时，重传那个包和剩下的包。