巫肇曦

博客

  • LeetCode 109. 有序链表转换二叉搜索树

    class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        return partition(head, getLength(head));
    }

    public int getLength(ListNode head) {
        int length = 0;
        while (head != null) {
            length++;
            head = head.next;
        }
        return length;
    }

    public TreeNode partition(ListNode head, int length) {
        if (length == 0) return null;
        if (length == 1) return new TreeNode(head.val);
        int mid = length / 2 - 1;
        ListNode node = head;
        for (int i = 0; i < mid; i++) {
            node = node.next;
        }
        ListNode now = node.next;
        node.next = null;
        TreeNode tree = new TreeNode(now.val);
        int newLen = mid + 1;
        tree.left = partition(head, newLen);
        tree.right = partition(now.next, length - newLen - 1);
        return tree;
    }
}

  • 百度移动端一面

    多态的3个条件：继承、方法重写、父类引用指向子类对象

    软引用（SoftReference）和弱引用（WeakReference）：活到内存不足和下一次垃圾回收

    sleep和wait区别

  • 待学习的知识

    CPU打高怎么排查?

    频繁发生Full GC怎么排查 ：从F-GC发生的因素答了，他还是想要成熟的排查思路（例如如何使用jmap等等这些工具）

    DM直接内存聊一下

    IO多路复用讲一下

    wait、sleep、park 轻量级锁 重量级锁 偏向锁聊一下

    Synchronized 与 ReentrentLock区别与联系

    如何紧凑存储一大串字符串

    给你5个文件，每个文件有一亿个数字，找出其中最大的100个，并且给出三条性能优化方案

    BIO-AIO-NIO-IO多路复用讲一下 

    孤儿进程与僵尸进程

    linux如何传递信号

    如何设计秒杀系统 ：从缓存、消息队列削峰的角度简单答了一下

    Spring模块

    Bean的生命周期

    AQS Node类里面的字段及其意义 

    AQS为何使用双向 链表

    ReentrentLock公平与非公平实现原理

    AQS共享模式与排他模式

    Kafka组件讲一讲

    Kafka消费者组的OffSet讲一讲

    新加入一个消费者，如何重新进行Partition的负载均衡

    HDFS的组件

    聊一下HDFS存储一个文件的全流程 

    Mysql存储的物理原理

    除了索引，如何优化Select

    rpc的连接复用咋做的

    cglib的动态代理咋实现的

    http1.1连接复用

    http2.0特性

    给你1T 文件的ip地址，怎么找出出现次数最多的 考虑内存有限

    成熟的rpc应该考虑哪些特性 rpc的注册中心可能会有什么问题比较影响性能

    序列化协议有哪些 protobuff有哪些缺点

    kafka相关八股文

    docker和虚拟机分别的使用场景 各有什么优缺点

    ThreadLocal知道吗，底层原理了解嘛

    epoll底层

    回表

    最左匹配

    分页

    分库分表

    对象的建立

    锁升级

    ConcurrentHashmap问到怎么算size

    HyperLogLog 是用来做什么的，原理，误差率

    Kafka 怎么实现高吞吐量

    怎么判断出现了拥塞

    分布式集群主键 id 的处理

    为什么不建议用字段值较长的字段作为索引 

    大文件的排序

    第三次握手的 ACK 报文丢失后，服务端会怎么办，服务端关闭连接后 客户端 会怎么办

    Redis数据结构，底层结构了解过吗，你用过哪些，怎么用的

    Redis为什么快， 源码 有了解过吗

    Mysql的逻辑结构是怎样的呢，简述一条sql的执行过程

    索引建设需要注意些什么，遇到幻读怎么办，慢查询优化，写了一条联合索引的查询，判断是否命中索引

    JVM组成部分，高并发下怎么保证接口幂等性，同步锁优化，压测参与了吗，jmeter了解过不

    高DAU下的微服务设计，Nacos作用是什么等等

    问Spring的特性，你感受到aop和ioc在spring框架下的好处了吗？常用的哪些注解

    spring mvc的流程

    分库分表怎么分的，在spring里怎么配置的

    项目 用到的分布式id发号器，你怎么做技术选型的，简单比较一下常见的几种方案呢

    volatile和synchronized讲讲

    Kafka选型的原因

    DNS 查询时，一个域名多个服务器，怎么做到的（负载均衡 + 一致性哈希）

    单机下，TCP接收到的包可能发向不同应用，怎么做到的(不会。。。。)

    Spring框架实现

    Spring如何做到的每个请求打到对应Controller

    synchronized关键字（两个队列，1.8优化，锁升级，应用场景）

    volatile关键字（可见性、有序性，使用场景，mesi原理+线程模型）

    了解哪些阻塞队列

    ThreadLocal是线程安全的吗 

    Mysql为啥必须要有主键

    LFU如何实现O1

    netty优点 netty线程模型 

    线程池优点 

    volatile指令重排发生在哪个步骤

    redis   io模型 

    sql语句优化，联表查询有什么注意点

    MySQL有哪些索引类型？（B+树，哈希，全文，空间数据）

    finally怎么用

    mesi协议

    内存屏障

    redis数据结构

    redis 过期键删除策略（定期删除、惰性删除、定时删除）

    kafka副本了解吗，讲一下

    为什么不让一个partition被同组的多个consumer消费

    Dubbo有了解过吗

    redis 和mysql一致性解决方案 

    序列化与反序列化

  • JVM垃圾回收

    可达性分析算法

    以 GC Roots 为起始点进行搜索，可达的对象都是存活的，不可达的对象可被回收。Java 虚拟机使用该算法来判断对象是否可被回收，GC Roots 一般包含以下内容：

    • 虚拟机栈中局部变量表中引用的对象
    • 本地方法栈中 JNI 中引用的对象
    • 方法区中类静态属性引用的对象
    • 方法区中的常量引用的对象

    安全点(Safe Point)与安全区域(Safe Region)

    而主动式中断的思想是当垃圾收集需要中断线程的时候，不直接对线程操作，仅仅简单地设置一 个标志位，各个线程执行过程时会不停地主动去轮询这个标志，一旦发现中断标志为真时就自己在最 近的安全点上主动中断挂起。轮询标志的地方和安全点是重合的，另外还要加上所有创建对象和其他 需要在Java堆上分配内存的地方，这是为了检查是否即将要发生垃圾收集，避免没有足够内存分配新 对象。由于轮询操作在代码中会频繁出现，这要求它必须足够高效。HotSpot使用内存保护陷阱的方式， 把轮询操作精简至只有一条汇编指令的程度。

    记忆集(Remembered Set)与卡表(Card Table)

    Serial(新生代)/Serial Old(老生代) 收集器

    它只会使用一个处理器或一条收集线程去完成垃圾收集工作，更重要的是强调在它进行垃圾收集时，必须暂停其他所有工作线程，直到它收集结束。

    Serial/Serial Old收集器运行示意图

    ParNew(新生代) 收集器

    ParNew收集器实质上是Serial收集器的多线程并行版本，除了同时使用多条线程进行垃圾收集之外，其余的行为包括Serial收集器可用的所有控制参数、收集算法、Stop The World、对象分配规则、回收策略等都与Serial收集器完全一致，在实现上这两种收集器也共用了相当多的代码。除了Serial收集器外，目前只有它能与CMS 收集器配合工作。

    ParNew/Serial Old收集器运行示意图

    Parallel Scavenge(新生代)收集器

    Parallel Scavenge收集器也是一款新生代收集器，它同样是基于标记-复制算法实现的收集器，也是 能够并行收集的多线程收集器。Parallel Scavenge收集器的特点是它的关注点与其他收集器不同，CM S等收集器的关注点是尽可能 地缩短垃圾收集时用户线程的停顿时间，而Parallel Scavenge收集器的目标则是达到一个可控制的吞吐 量(Throughput)。所谓吞吐量就是处理器用于运行用户代码的时间与处理器总消耗时间的比值。

  • 常见HTTP状态码

    服务器返回的  响应报文 中第一行为状态行，包含了状态码以及原因短语，用来告知客户端请求的结果。

    状态码类别含义
    1XXInformational（信息性状态码）接收的请求正在处理
    2XXSuccess（成功状态码）请求正常处理完毕
    3XXRedirection（重定向状态码）需要进行附加操作以完成请求
    4XXClient Error（客户端错误状态码）服务器无法处理请求
    5XXServer Error（服务器错误状态码）服务器处理请求出错

    1XX 信息

    • 100 Continue ：表明到目前为止都很正常，客户端可以继续发送请求或者忽略这个响应。

    2XX 成功

    • 200 OK
    • 204 No Content ：请求已经成功处理，但是返回的响应报文不包含实体的主体部分。一般在只需要从客户端往服务器发送信息，而不需要返回数据时使用。
    • 206 Partial Content ：表示客户端进行了范围请求，响应报文包含由 Content-Range 指定范围的实体内容。

    3XX 重定向

    • 301 Moved Permanently ：永久性重定向
    • 302 Found ：临时性重定向
    • 303 See Other ：和 302 有着相同的功能，但是 303 明确要求客户端应该采用 GET 方法获取资源。
    • 注：虽然 HTTP 协议规定 301、302 状态下重定向时不允许把 POST 方法改成 GET 方法，但是大多数浏览器都会在 301、302 和 303 状态下的重定向把 POST 方法改成 GET 方法。
    • 304 Not Modified ：如果请求报文首部包含一些条件，例如：If-Match，If-Modified-Since，If-None-Match，If-Range，If-Unmodified-Since，如果不满足条件，则服务器会返回 304 状态码。
    • 307 Temporary Redirect ：临时重定向，与 302 的含义类似，但是 307 要求浏览器不会把重定向请求的 POST 方法改成 GET 方法。

    4XX 客户端错误

    • 400 Bad Request ：请求报文中存在语法错误。
    • 401 Unauthorized ：该状态码表示发送的请求需要有认证信息（BASIC 认证、DIGEST 认证）。如果之前已进行过一次请求，则表示用户认证失败。
    • 403 Forbidden ：请求被拒绝。
    • 404 Not Found

    5XX 服务器错误

    • 500 Internal Server Error ：服务器正在执行请求时发生错误。
    • 502 Bad Gateway ：网关错误。
    • 503 Service Unavailable ：服务器暂时处于超负载或正在进行停机维护，现在无法处理请求。

  • HTTP方法

    GET

    获取资源。当前网络请求中，绝大部分使用的是 GET 方法。

    HEAD

    获取报文首部。和 GET 方法类似，但是不返回报文实体主体部分。主要用于确认 URL 的有效性以及资源更新的日期时间等。

    POST

    传输实体主体。POST 主要用来传输数据，而 GET 主要用来获取资源。更多 POST 与 GET 的比较请见第九章。

    PUT

    上传文件。由于自身不带验证机制，任何人都可以上传文件，因此存在安全性问题，一般不使用该方法。

    PATCH

    对资源进行部分修改。PUT 也可以用于修改资源，但是只能完全替代原始资源，PATCH 允许部分修改。

    DELETE

    删除文件。与 PUT 功能相反，并且同样不带验证机制。

    OPTIONS

    查询支持的方法。查询指定的 URL 能够支持的方法。会返回 Allow: GET, POST, HEAD, OPTIONS 这样的内容。

    CONNECT

    要求在与代理服务器通信时建立隧道。使用 SSL（Secure Sockets Layer，安全套接层）和 TLS（Transport Layer Security，传输层安全）协议把通信内容加密后经网络隧道传输。

    TRACE

    追踪路径。服务器会将通信路径返回给客户端。发送请求时，在 Max-Forwards 首部字段中填入数值，每经过一个服务器就会减 1，当数值为 0 时就停止传输。通常不会使用 TRACE，并且它容易受到 XST 攻击（Cross-Site Tracing，跨站追踪）。

  • 计算机网络总结

    第一章：

    计算机网络：是将大量计算机设备互联在一起提供数据传输的系统

    1. 大量的计算机或设备互联在一起，计算机具有独立处理能力
    2. 目的: 资源共享( 数据共享和设备共享）
    3. 网络中数据传输由大量的网络通信协议控制
    4. 网络中数据传输由大量的传输介质和传输技术实现

    逻辑结构：

    边缘部分：用户主机组成，用户直接使用，进行通信和资源共享

    两个用户主机间的通信实质上是两个主机中的应用进程间的通信

    客户服务器方式、P2P(Peer to Peer)对等连接方式

    线路交换三步骤：线路建立、数据传输、线路释放

    存储转发分类：报文交换、分组交换

    报文交换：

    无论数据有多长，都作为一个逻辑数据单元加上目的地址、源地址和控制信息，并按规定格式封装

    报文交换主要问题：

    1. 路由器要保留副本，以备出错时重发，而报文长短不一，需要为长报文预留存储空间，但多数情况下，可能是短报文
    2. 报文过长时，等待时间长
    3. 相同误码率的情况下，报文越长，出错概率越大，重发机会也就越高
    4. 报文长度不一，通信协议须判断报文的结束和开始位置，协议的效率不高

    报文分组交换：长报文被分为多个短的有限长度分组，1 千或几千比特，每个分组分配分组号，在接收端所有分组按序号重新组装为长的报文

    固定格式、长度限制，有效节约时间、空间

    动态的为每个分组选择不同的路径通过通信子网

    数据报方式: Datagram, DC

    特点：

    报文的不同分组可通过不同的路径进行传输

    分组可能不按顺序到达目的主机，可能重传或丢失

    在传输过程中，每个分组需要携带源地址和目的地址

    虚电路方式:Virtual Circuit , VC

    虚电路连接、数据传输、虚电路释放

    特点：

    1. 在传输分组前建立逻辑连接：虚电路连接
    2. 报文的所有分组沿着同一条虚电路连接进行传输
    3. 分组按序到达目的主机，一般不会丢失或重发
    4. 每个分组赋予一个虚电路标识符，分组中没有必要加目的地址和源地址
    5. 在每个节点有必要做差错控制，但没必要进行路由选择
    6. 每个节点支持多条虚电路连接

    存储转发的优点：

    1. 多个数据单元共享一条通信信道，提高信道使用率
    2. 选择最佳路径通过通信子网
    3. 平衡网络栽荷
    4. 减少传输差错
    5. 在采用不同速率或不同编码格式的信道间交换数据单元
    6. 可使用优先级　

    线路交换： 比特流直接到达终点

    报文交换： 存储转发

    分组交换： 存储转发

    第一个网络：ARPANET

    网络体系结构：

    网络层次结构与各层协议的集合：TCP/IP、OSI/RM

    实体：任何可发送或接收信息软件或硬件进程

    对等实体：不同节点同一层的实体

    协议：控制两个或多个对等实体进行通信的规则的集合

    ····························

    协议基本要素：

    语法：协议元素与数据的组合格式

    语义 : 协议中各协议元素的含义

    时序（同步）：通信过程中，通信双方操作的执行顺序和规则

    WAN广域网、MAN城域网、LAN局域网、PAN个人区域网

    接口或服务访问点或端口SAP（Service Access Point）：同一结点内相邻层之间交换信息的通道

    协议数据单元, PDU(Protocol Data Unit)： 将要发到对等层的信息

    接口控制信息，ICI(Interface Control Information):    帮助下一层完成其功能的信息

    服务数据单元, SDU(Service Data Unit):    等待发送至下一层的信息

    一个SDU可以由多个PDU组成，一个PDU也可以分解成多个SDU

    与通信有关的报文：通信方式、通信控制、通信信道

    第一类工作:与文件传输直接相关，确保接收方已准备接收和存储文件，双方采用同样的文件格式，如果不一致，至少一方要负责格式转换

    第二类工作：提供通信服务

    第三类工作：网络接入：负责网络接口的详细工作，如数据帧的格式、长度等

    层次划分原则:

    • 所有功能分为不同的层
    • 网络中的每个节点具有相同的层
    • 不同节点的对等层具有相同功能
    • 同一节点相邻层间通过SAP进行通信
    • 每一层可以利用下层提供的服务而不管其如何实现
    • 每一层均为上一层提供服务
    • 不同节点同一层的对等实体间可以通过通信协议实现通信

    OSI/RM体系结构

    应用层、表示层、会话层、传输层、网络层、数据链路层、物理层

    TCP: Transmission Control Protocol ( 传输控制协议）
    IP：Internet Protocol (网络互连协议）

    TCP/IP：应用层、运输层、网络层、网络接口层

    五层协议：应用层、运输层、网络层、数据链路层、物理层

    计算机网络的性能指标：

    速率、带宽、吞吐量、时延、时延带宽积、往返时间、利用率

    速率：

    数据率（data rate）或比特率(bit rate): 单位时间内传输二进制码元的数量，单位为比特/秒，记做b/s,或bps（bit per second）

    数据传输速率= 1/T(bps)

    常用单位：Kbps、Mbps、Gbps 、Tbps

    1Kbps = 103bps、1Mbps = 103Kbps、1Gbps= 103Mbps、1Tbps = 103Gbps、Pbps、Ebps、Zbps、Ybps

    模拟传输:  传输模拟信号

    数字传输:  传输数字信号

    总时延：排队时延、处理时延、发送时延、传播时延

    四种时延所产生的地方：

    日程表 描述已自动生成

    处理时延：交换结点为存储转发而进行一些必要的处理所花费的时间。

    排队时延：结点缓存队列中分组排队所经历的时延，长短往往取决于网络中当时的通信量。

    发送时延：发送数据时，数据帧从结点进入到传输媒体所需要的时间，即从发送数据帧的第一个比特算起，到该帧的最后一个比特发送完毕所需的时间。

    传播时延：电磁波在信道中需要传播一定的距离而花费的时间。

    发送时延传播时延
    决定因素数据帧长度发送速度信道长度传播速度
    减少时延高速网络链路，即发送速度选择合适的传输介质
    光纤信道的传输率高是因为可以用很高的速度向光纤信道发送数据空气中，3.0*105KM/s铜缆，2.3*105KM/s光纤，2.0*105KM/s

    RTT：Round Trip Time, 通信双方交互一次所需的时间，包括各中间结点的处理时延、排队时延、发送时延、传播时延

    信道利用率：某信道有百分之几的时间是被利用的，即有数据通过。

    网络利用率：全网络的信道利用率的加权平均值。

    第一次作业

    1、假设信号在媒体上的传播速率为3*108m/s, 媒体长度L为4500KM，试计算当数据率分别为1Mbit/s和10Gbit/s时，在以上媒体中正在传播的比特数是多少？

    要点：传播时延：= 4500*103/(3*108)=1.5*10-2s

    当数据率为1Mbit/s 时比特数：

    1.5*10-2*106=1.5*104b/s=15Kb

    当数据率为10Gbit/s 时比特数：

    1.5*10-2*10*109=1.5*108b/s=150Mb

    2、收发两端之间的传输距离为2000KM，信号在媒体上的传播速率为3*108m/s。试计算以下两种情况的发送时延和传播时延：

    （1） 数据长度为107字节, 数据发送率为100K bit/s。

    （2） 数据长度为103字节, 数据发送率为1G bit/s。

    要点：

    • 数据长度为107字节, 数据发送率为100K bit/s。

    发送时延=数据帧长度（bit）/发送速率（bit/s）

    =8*107bit/100*103bit/s=800s

    传播时延=信道长度（m）/电磁波在信道上的传播速率（m/s）

    =2000*103m/3*108m/s=6.67*10-3s

    （2） 数据长度为103字节, 数据发送率为1G bit/s。

    发送时延=数据帧长度（bit）/发送速率（bit/s）

    =8*103bit/109bit/s=8*10-6s

    传播时延=信道长度（m）/电磁波在信道上的传播速率（m/s）

    =2000*103m/3*108m/s=6.67*10-3s

    3、应用层数据交给运输层传送，需加上20字节的TCP首部，再交给网络层传送，需加上20字节的IP首部，再交给数据链路层的以太网传送，需加上首部和尾部共18 字节。

       当应用层数据长度为100字节时，共传送多少数据？并请计算数据传输效率？

       当应用层数据长度为1000字节，共传送多少数据？并请计算数据传输效率？

    （数据传输效率：传送的应用层数据除以所传送的总数据，即应用层数据加上各层首部和尾部的开销。）

    要点：应用层数据长度100byte时:

    传送数据：100+20+20+18=158byte

    数据传输效率=100/158=63.3%

    应用层数据长度为1000byte 时：

    传送数据：1000+20+20+18=1058byte

    数据传输效率=1000/1058=94.5%

    第二章 物理层：

    物理层的主要任务：确定与传输媒体的接口特性

    数据：运送消息的实体

    信号：数据的电气或电磁的表现

    模拟信号：消息的参数是连续的

    数字信号：消息的参数是离散的

    规程：用于物理层的协议

    基带信号：来自信源的信号

    带通信号：经过载波调制后的信号

    接口特性：机械特性、电气特性、过程特性、功能特性

    并行通信：待发送的每个字符的8位二进制编码同时通过8条并行的通信信道进行发送

    串行通信：将待发送的每个字符的8位二进制编码按由低位到 高位的顺序依次发送

    单工通信：单向通信——只能有一个方向的通信而没有反方向的交互

    半双工通信：双向交替通信——通信的双方都可以发送信息，但不能双方同时发送或接收信息

    全双工通信：双向同时通信——通信的双方可以同时发送和接收信息

    基带调制：

    仅对基带信号的波形进行变换

    把数字信号转换成另一种数字信号，输出的是数字信号—基带信号

    带通调制：

    把基带信号频率范围搬移到较高的频段，并转换为模拟信号

    基带信号转换成模拟信号、输出的是模拟信号—带通信号

    U(t)=Um × sin(ωt +φ0) 

    Um: 振幅

    ω: 频率

    φ: 相位

    振幅键控或调幅法：ASK （调幅AM）

    由载波的两个不同的振幅分别代表二进制的0或1 

    容易实现，但易受干扰

    移频键控或调频法：FSK。（调频FM）

    载波的不同频率分别代表二进制数的0或1 ，如高频代表1，低频代表0

    容易实现，但抗干扰能力强于ASK

    移相键控或调相法：PSK （调相PM）

    载波的不同相位变化分别代表不同的二进制数值

    绝对调相：利用载波的绝对相位值分别代表0或1

    　如：　 φ0＝0，　  1

    　    　 φ0＝π，　  0

    相对调相：用相位的相对偏移值表示1或0，或者说用载波在两位数字信号的交接处产生的相位偏移来表示不同的数字信号。
    　如：　    0，  相位不偏移
                1,    相位偏移π

    多相调制

    二相调制：一个信号代表一位二进制数，二个相位值分别代表二进制数0和1
    四相调制：一个信号代表二位二进制数，四个相位值分别代表二进制数0和1的四种组合 （00,01,10,11）
    八相调制：一个信号代表三位二进制数，八个相位值分别代表二进制数0和1的八种组合(000，001，010，011，100，101，110，111）

    基带信号的编码方法

    不归零码: NON-RETURN TO ZERO， NRZ

    利用两个不同的电平值分别代表两个二进制数0和1 ，如用正电平代表: 1 ，负电平代表: 0

    归零码：RETURN TO ZERO， RZ

    利用两个不同的脉冲分别代表两个二进制数0和1 ，如用正脉冲代表: 1 ，负脉冲代表: 0

    曼切斯特编码 ：MANCHESTER

    每位的中间有一次电平跳变，即电平值从高到低或从低到高，如低到高跳变： 0，从高到低跳变:  1，跳变既可以用作数据，也可用作同步时钟，自含钟编码或自同步编码


    差分曼切斯特编码：DIFFERENTIAL  MANCHESTER

    每位值根据其开始边界来决定是否发生跳变，中间依然有跳变，如果是1，不跳变，如果是0，有跳变

    采样定律：如果对信号以固定的时间间隔进行采样，当采样频率大于等于两倍的最大有效信号频率，所采样本就包含了原始信息的所有信息。

    PCM：

    采样：隔一定的时间间隔，将模拟信号的电平幅度值取出来做为样本，采样频率为2B

    量化：将采样样本幅度值按量化级决定取值的过程。（1）量化级（2）量化级幅值（3）量化

    编码：用相应位数的二进制代码表示量化后的采样样本的量化级值。如果用二进制数进行编码，则编码位数＝log2K, 其中K为量化级数。

    观察分析电信号的基本方法：时域分析法、频域分析法

    时域方法: 以时间 t 为自变量，观察信号随单位时间变化的情况

    频域法：以频率f为自变量，观察电信号的频谱构成、振幅与相位，分析电信号通过某一信道后频谱分量的变化              

    奈奎斯特准则： Rmax=2·Wlog2V（bps）

                  最大数据传输速率        信道带宽

    香农定理： Rmax = W·log2（1+S/N） (bit/s)

    文本, 信件 描述已自动生成
    文本 描述已自动生成

    物理层下面的传输介质：

    传输媒介的特性：

    双绞线：屏蔽双绞线，STP； 非屏蔽双绞线，UTP

    物理特性：由按规则螺旋结构排列的2 根、4 根或8 根绝缘导线组成，每对线有不同的颜色，都可作为一条通信线路，各线对螺旋排列的目的是为了使线对间的电磁干扰最小。

    同轴电缆：

    传输特性：

    基带同轴电缆:  50欧姆，基带信号，也即数字信号，数字传输，一路信号占用信道的所有带宽，多路复用时采用TDM技术

    宽带同轴电缆:  75欧姆，模拟信号, 模拟传输，每路信号占用信道带宽的不同频率，多路复用时采用FDM技术，也可以传输基带信号

    光纤：

    直径为8～100μm的柔软、能传导光波的介质,可由玻璃和塑料制成，其中，合成硅的纯度越高，光纤的性能越好，衰减也越小

    不同层具有不同的折射率

    不同的光线注入角度不同

    通过传输不同颜色的光纤实现多路复用

    单模光纤√多模光纤
    单个可分辨角度多个可分辨角度
    单一光线多种光线
    芯径<5μm芯径>50μm
    无反射,  直线前进反射，波状前行
    注入型激光二极管发光二极管
    长距离短距离
    高速低速
    衰减小衰减大
    高成本低成本
    UTP  STP同轴电缆光纤
    连接特性点对点多点点对点多点点对点
    地理范围使用放大器：15km不使用放大器：100m <100km不使用放大器：6-8km

    抗干扰    		弱强于UTP强最强
    成本越来越高
    安装容易容易中等困难

    多路复用技术分类:

    频分多路复用：Frequency-Division Multiplexing，FDM

    • 每路信号占用载波的不同频率
    • 一个载波可同时传输多路信号
    • 使用警戒带宽以避免信号间相互干扰

    时分多路复用：Time-Division Multiplexing，TDM 

    • 时间被划分为小的时隙
    • 每路信号占用给定的时隙
    • 在给定的时隙内，每路信号占用信道的所有带宽
    FDMTDM
    多路信号同时使用一条物理信道多路信号轮流使用一条物理信道
    每路信号使用载波的不同频率每路信号使用载波的不同时隙
    模拟传输数字传输

    同步时分多路复用                      SYNCHRONOUS TDM，STDM

    异步时分多路复用，统计时分多路复用    ASYNCHRONOUS TDM，ATDM

    STDM（Statistic TDM）统计时分复用

    波分多路复用：Wavelength Division Multiplexing，WDM

    光的频分复用，工作原理基本类似于FDM，用于高速光网络，使用衍射光栅来实现多路不同频率光波信号的合成与分解，从而实现多路复用

    密集波分复用 DWDM

    码分多路复用：Code Division Multiplexing，CDM （计算）

    码分多址 （Code Division Multiple Access：CDMA）

    扩频：将信号扩展至更高的频率以预防拥塞、干扰，提高传输的可靠性和高可复用性

    令向量 S 表示站 S 的码片向量，令向量 T 表示其他任何站的码片向量。 

    两个不同站的码片序列正交，就是向量 S 和T 的规格化内积(inner product)都是 0： 

    文本框:

    任何一个码片向量和该码片向量自己的规格化内积都是1 

    一个码片向量和该码片反码的向量的规格化内积值是 –1

    各用户使用经过特殊挑选的唯一码型，因此彼此不会造成干扰。

    每个站分配的码片序列不仅必须各不相同，并且还必须互相正交(orthogonal)。

    实用的系统中是使用伪随机码序列。

    这种系统发送的信号有很强的抗干扰能力，其频谱类似于白噪声，不易被发现。

    文本, 信件 描述已自动生成

    数字传输系统：

    同步光纤网 SONET   –>     第48级光载波 OC-48 

    同步数字系列 SDH

    第一级同步模块 STM-1

    宽带接入：

    不对称数字线 （ADSL，Asymmetric Digital Subscriber Line）–>  固定电话运营商

    1. 在一对双绞线上可为用户提供非对称的上、下行速率，非常符合普通用户联网的实际需要
    2. 较充足的带宽，可用于传输多种宽带数据业务
    3. 不影响用户对普通电话的使用

    光纤同轴混合网 （HFC，Hybrid Fiber Coax） –>  有线电视运营商

    比 CATV 网更宽的频谱，双向传输功能

    每个家庭要安装一个用户接口盒UIB (User Interface Box)

    第二次作业

    1、规程和协议有什么区别？

    要点：协议（protocol）是指在计算机网络中为进行网络中数据交换而建立的规则、标准或约定称为网络协议，简称协议，以明确规定所交换数据的格式以及有关的同步问题。

    规程（procedure）：在数据通信的早期，对通信所使用的各种规则都称为“规程”，后来具有体系结构的计算机网络开始使用“协议”这一名词。因为物理层主要考虑网络的通信问题，物理层的协议和规程基本同义，在其它各层通常称协议。

    2、什么是本地通信？什么是远程通信？

    要点：远程通信通常是指在连接的系统间，通过使用模拟或数字信号调制技术进行的声音、数据、传真、图象、音频、视频和其它信息的电子传输。

    本地通信则通常是指计算机或主机内部各进程间的通信。

    第 3 章  数据链路层：

    功能： 帧同步功能、差错控制功能、流量控制功能、链路管理功能

    信道：点对点信道（PPP协议）、广播信道（CSMA/CD协议）

    基本问题：封装成帧、透明传输、差错检测

    链路（link）：一条点到点的物理线路段，中间没有任何其他的交换结点。

    数据链路（data link）：除了物理线路外，还必须有通信协议来控制数据的传输。若把实现这些协议的硬件和软件加到链路上，就构成了数据链路。（使用网络适配器）

    数据链路层传送的协议数据单元：帧

    点对点信道的数据链路层通信步骤：

    1、结点A的数据链路层把网络层交下来的Ip数据报添加首部和尾部封装成帧

    2、结点A把封装好的帧发送给结点B的数据链路层

    3、若结点B的数据链路层收到的帧无差错，则从封装的帧中提取出Ip数据报上交给上面的网络层，否则丢弃此帧

    封装成帧（framing）：

    SOH（start of header）：帧开始符 ascii 1

    EOT（end of transmission）：帧结束符 ascii 4

    MTU：Maximum Transfer Unit，最大传送单元，即帧的数据部分的长度限制，一般为1500

    透明传输：

    设法使数据中可能出现的控制字符SOH和EOT在接收端不被解释为控制字符

    “透明”：某一个实际存在的事物看起来却好像不一样

    解决透明传输问题的方法：

    字节填充(byte stuffing)、字符填充(character stuffing)

    1. 发送端的数据链路层在数据中出现控制字符“SOH”或“EOT”时，在前面插入一个转义字符“ESC”(其十六进制编码是 1B)。
    2. 如果转义字符也出现数据当中，那么应在转义字符前面插入一个转义字符。
    3. 接收端的数据链路层在将数据送往网络层之前删除插入的转义字符。

    差错检测：

    在传输过程中可能会产生比特差错，1 可能会变成 0 而 0 也可能变成 1。在一段时间内，传输错误的比特占所传输比特总数的比率称为误码率 BER (Bit Error Rate)。

    误码率与信噪比有很大的关系。为了保证数据传输的可靠性，在计算机网络传输数据时，必须采用各种差错检测措施。

    循环冗余检验（CRC， Cyclic Redundancy Check）：    计算！！

    (1) 将要发送的数据比特当做一个多项式f(x)的系数

    (2) 在发送端用收发双方预先约定的生成多项式G(x)去除，求得一个余数多项式R(x)

    (3) 将余数多项式加到 数据多项式之后发送到接收端

    (4) 在接收端用同样的生成多项式G(x)去除接收数据多项式f’(x)

    (5) 如果能够整除，则传输无差错

    (6) 如果不能够整除，则传输差错

    模2运算：二进制加法不进位，或者说每一位进行xor与运算^

    FCS（Frame Check Sequence）：帧检验序列

    不是可靠传输，可能出现帧丢失、帧重复、帧失序，为了实现可靠传输还要加上帧编号、确认、重传机制。

    CRC特点：

    1. 检查出全部单个错
    2. 检查出全部离散的二位错
    3. 检查出全部奇数个错     
    4. 检查出全部长度小于或等于K位的突发错
    5. 以[1-(1-1/2)k-1]的概率检查出长度为(K+1) 位的突发错

    奇偶检验：

    在传输前，在数据后加奇偶位，目的计算机重新计算奇偶位并与接收到的奇偶位相比较，如果再者相同，无差错；如果两者不同，有差错。

    方法简单，检错能力差，不能检测出两个位或偶数位发生错误的情况，检错率最高达50%, 用于通信要求较低的情况。

    点对点协议 PPP (Point-to-Point Protocol)

    1. 简单   首要的要求
    2. 封装成帧   必须规定特殊的字符作为帧定界符
    3. 透明性    必须保证数据传输的透明性，保证透明传输
    4. 多种网络层协议     必须能在同一条物理链路上同时支持多种网络层协议
    5. 多种链路类型    必须能在多种链路类型上运行
    6. 差错检测    
    7. 检测连接状态
    8. 最大传送单元（MTU）
    9. 网络层地址协商
    10. 数据压缩协商

    PPP协议组成：

    将IP数据报封装到串行链路的方法。

    用来建立、配置和测试数据链路连接的链路控制协议LCP（Link Control Protocol）。

    网络控制协议NCP（Network Control Protocol）

    协议字段：

    0x0021，PPP 帧的信息字段是IP数据报

    0xC021, 信息字段是PPP链路控制数据

    0x8021，信息字段是网络控制数据  

    PPP协议不提供使用序号和确认的可靠传输

    帧检验序列 FCS 字段可保证无差错接受，数据链路层出现差错的概率不大。

    在因特网环境下，PPP 的信息字段放入的数据是 IP 数据报。

    数据链路层的可靠传输并不能够保证网络层的传输也是可靠的。

    透明传输问题

    同步传输链路（SONET/SDH）：硬件完成比特填充 

    1. 信息字段中出现了和标志字段 F 完全一样的8比特组合：01111110
    2. 发送端在 5 个连 1 之后填入0比特再发送出去
    3. 在接收端把 5 个连 1之后的 0 比特删除

    异步传输链路：字符（字节）填充法

    1. 当信息字段中出现和标志字段相同的比特组合时，在该比特组合前加转义符0x7D，并将该字符编码进行改变
    2. 将信息字段中出现的每一个 0x7E 字节转变成为 2 字节序列(0x7D, 0x5E)。 
    3. 若信息字段中出现一个 0x7D 的字节, 则将其转变成为 2 字节序列(0x7D, 0x5D)。
    4. 若信息字段中出现 ASCII 码的控制字符（即数值小于 0x20 的字符），则在该字符前面要加入一个 0x7D 字节，同时将该字符的编码加以改变。  

    PPP特性小结

    1. 能够控制数据链路的建立；
    2. 能够对IP地址进行分配和使用；
    3. 允许同时采用多种网络层协议；
    4. 能够配置和测试数据链路；
    5. 能够进行错误检测；
    6. 支持身份验证
    7. 有协商选项，能够对网络层的地址和数据压缩等进行协商。

    使用广播信道的数据链路层

    以太网的两个标准：DIX Ethernet V2 (1981.11)、IEEE 802.3

    数据链路层划分：

    LLC（Logical Link Control）：逻辑链路控制(子层)

    MAC（Media Access Control）：媒体接入控制(子层)

    计算机通过（网卡）网络适配器和局域网进行通信

    网卡（网络适配器）功能：

    1. 数据缓存：匹配网络数据传输率和主机的处理速度
    2. 帧的封装和拆封：加上控制字段→通过帧传输→去除控制字段
    3. 介质访问控制：CSMA/CD
    4. 串/并转换：将主机中的并行数据转换成连续位串，反之亦然
    5. 数据编码和解码：将数据转换成适宜在物理传输介质上进行传输的信号，反之亦然
    6. 数据发送
    7. 数据接收、过滤功能：从网络上每收到一个 MAC 帧就首先用硬件检查 MAC 帧中的 MAC 地址。如果是发往本站的帧则收下，进行处理。否则就将此帧丢弃，不进行处理。

    以太网发送的数据都使用曼彻斯特(Manchester)编码

    以太网提供的服务是尽最大可能的交付，不可靠的交付

    CSMA/CD：Carrier Sense Multiple Access with Collision Detection：载波监听接入/碰撞检测

    载波侦听：每一个站在发送数据之前先要检测一下总线上是否有其他计算机在发送数据，如果有，则暂时不要发送数据，以免发生碰撞

    多路访问：许多计算机以多点接入的方式连接在一根总线上

    冲突检测：结点在发送的同时将其信号波形于从总线上收到的信号波形相比较，“边发送边监听”

    只能半双工通信

    争用期：通常定义为2t，两倍端到端延迟，或往返延迟，也称碰撞窗口。只有经过争用期这段时间还没有检测到碰撞，才能肯定这次不发生碰撞。规定为512比特时间，即发送512bit（64字节）所需的时间，具体看网速。

    使用二进制指数退避（truncated binary exponential backoff）算法

    k=Min(重传次数, 10), 从离散的整数集合{0, 1, 2, (2k-1)}中随机选出一个数，记为r，重传应推后的时间是r倍的争用期。当重传次数大于16次则丢弃改帧并向上级报告。

    凡长度小于64字节的帧都是由于冲突而异常中止的无效帧，意味着有冲突产生。

    帧间最小间隔：一个站在检测到总线开始空闲后，还要等待 9.6 s，相当于 96 bit 的发送时间， 才能再次发送数据。

    目的：使刚刚收到数据帧的站的接收缓存来得及清理，做好接收下一帧的准备。

    CSMA/CD协议要点：

    先听后发，边听边发、冲突停止，延迟重发

    （1）准备发送：适配器从网络层获得一个分组，加上以太网的首部和尾部组成以太帧，放入适配器的缓存中

    （2）发送前：检测信道

         信道繁忙: 保持侦听

         信道空闲：等待帧间最小间隔 9.6 s时发送以太帧

    （3）发送过程中：保持侦听

         发送成功：争用期内没有检测到冲突，以太帧发送成功，返回第一步

         发送失败：争用期内检测到冲突，停止发送数据，发送干扰信息加强以方便其它站点检测到冲突，适配器执行二进制指数退避算法，等待r倍512比特时间后，返回第二步。当重传次数达16次仍不能成功时，停止重传，并报告上层

    逻辑上还是总线网，同一时刻只能允许一个站发送数据

    DIX 以太网 V2 的 MAC 帧格式

    类型字段用于标志上一层使用的是什么协议，以便把收到的MAC 帧的数据上交给上一层的相应协议。值大于1536（0x0600）字节，为类型，值小于1536字节，为长度。

    IEEE注册管理机构 RA（Registration Authority）:局域网全球地址的法定管理机构

    唯一，固定 , 固化在网卡（网络适配器）的存储器中

    单个/组 (I/G)  ：第一个字节的最低位，用来确定地址是

            单个地址：I/G位为0 ，单播

             组地址：   I/G位为1 ，多播  

    全球/本地 (G/L)  ：第一个字节的最低第二位，用于确定该地址

            全球管理：G/L 位设置为 0，通过分配唯一的公司 ID，IEEE 对地址进行全球管理。

            本地管理：G/L 位被设置为1，网络管理员已覆盖制造地址，并指定其他地址。

    当数据字段的长度小于 46 字节时，应在数据字段的后面加入整数字节的填充字段，以保证以太网的 MAC 帧长不小于 64 字节。 

    在传输媒体上实际传送的要比 MAC 帧还多两个字段共8个字节，由硬件插入，不参与差错检测。

    无效的 MAC 帧：

    1. 帧的长度不是整数个字节；
    2. 用收到的帧检验序列 FCS 查出有差错；
    3. 数据字段的长度不在 46 — 1500 字节之间；
    4. MAC帧长度不在 64 — 1518 字节之间；

    扩展的以太网

    在数据链路层扩展以太网、在数据链路层扩展以太网

    在物理层扩展以太网

    光纤和一对光纤调制解调器将主机连接到集线器

    用多个集线器连成更大的局域网

    优点：

    1. 使原来属于不同网段的计算机能够进行通信。
    2. 扩大了局域网覆盖的地理范围。

    缺点：

    1. 局域网覆盖范围增大，但总的吞吐量并未提高（碰撞域增加）。
    2. 集线器只能互连相同的局域网。   

    在数据链路层扩展以太网：交换式局域网、虚拟局域网

    交换式局域网

    交换式局域网的关键:以太网交换机

    以太网交换机的基本结构：储存转发

    交换机功能：学习功能、转发功能、泛洪功能、过滤功能

    1.交换机的学习功能：地址映射表的建立和维护

    地址映射表存储在每个端口，每个端口要有足够的缓存容量以记住MAC 地址和MAC地址数量。MAC地址数量：可存储在交换机的地址映射表中的MAC地址的最大数量（一般为1024） ，该值越大，速度越快，转发的效率越高。

    交换机采用地址学习的方法建立和维护地址映射表，在数据帧进入交换机的端口时，读取源地址及数据以获得MAC地址和端口间的对应关系, 检查地址映射表，如果该地址不存在，加入地址表，如果已经存在，就更新。

    2.交换机的转发和泛洪功能：

    • 转发功能：表中有目标MAC地址，更新MAC地址表中记录时间，并转发相应帧
    • 泛洪功能：如果本地交换机地址表中没有目标MAC地址，交换机就将收到的数据帧从除接收端口外的所有端口转发出去

    3.交换机的过滤功能：数据帧中的源地址和目的地址对应的端口在同一个端口，不转发，也不做任何处理

    交换机数据帧转发方式：直接交换方式 、存储转发方式、改进直接交换方式或碎片隔离式、混合交换方式

    直接交换方式：获取目的地址并立即传送出去

    1. 延迟少
    2. 不进行差错控制
    3. 没有缓存, 不支持两个不同速率端口间的直接连接
    4. 当交换机中的端口数量增加, 交换矩阵会越来越复杂，越难以实现

    存储转发方式：存储，差错控制，提取目的地址，检查ＭＡＣ地址映射表，将数据帧转发到相应的端口

    1. 延迟长
    2. 差错控制
    3. 支持不同速率间两个端口间的直接连接

    改进直接交换方式或碎片隔离式 ：直接交换方式和存储转发方式相结合

    1. 在转发前检查数据帧长度
    2. 帧长度<64字节, 丢弃 
    3. 帧长度≥64字节, 检查地址字段和控制字段并转发

    交换机使用特定的缓冲器—FIFO（First In First Out, 先进先出) 队列

    混合交换方式：利用自适应交换机根据实际网络环境选择不同的转发方式

    1. 当网络通畅时，采用直接交换方式，以使转发时间最短
    2. 当网络阻塞时，采用存储转发方式，以降低转发速率
    3. 自适应交换机的每个端口有适应不同速率的能力，支持10, 100 和 1000Mbps间的交换.

    虚拟局域网（Virtual Local Area Network,  VLAN）

    如果将局域网中的结点按工作性质与需要划分成若干逻辑工作小组，则每个逻辑工作小组就是一个虚拟网络

    主要特点：

    虚拟局域网是建立在交换式局域网的基础上，用软件划分和管理逻辑工作组

    逻辑工作组中的节点不受其物理位置的限制，或可分散在不同的物理网段

    节点间可相互通信，好似在一个相同的物理网段中

    虚拟网的组网方式：交换机端口、MAC 地址、IP 地址、IP 广播组

    基于交换机端口号—静态VLAN：

    1. 网络管理员通过网络管理软件或设置交换机将某些端口号划分给某虚拟网
    2. 除非重新设置，该端口将一直保持对该虚拟网的从属性
    3. 同一虚拟网中的端口可在一个或不同的交换机中
    4. 每个端口或网段只能属于一个虚拟网
    5. 当用户从一个端口移至另一个端口时，需要重新设置
    6. 操作麻烦

    基于MAC地址—动态VLAN：

    1. 借助智能管理软件根据MAC地址划分VLAN
    2. 利用MAC 地址定义虚拟网成员后，当用户从一个网段移到另一个网段 时，其虚拟局域网成员身分不变
    3. 在初始时间，所有用户需要划分进至少一个虚拟网
    4. 当虚拟网规模太大时，很难一个一个配置

    以太网特点：

    • 成熟技术
    • 互操作性好
    • 价格相对便宜
    • 统一的帧格式
    • 适应多种传输媒体
    • 可扩展
    • 灵活
    • 易于安装
    • 稳健性好

    不同速率Gigabit以太网规格：

    吉比特10吉比特40/100吉比特
    数据帧以太帧以太帧以太帧
    传输模式全双工/半双工双全工全双工
    兼容向下兼容向下兼容向下兼容
    拓扑星型星型星型
    图片包含 表格 描述已自动生成

    第三次作业：

    1、  要发送的数据为1101011011，采用CRC的生成多项式是P(X)=X4+X+1, 试求应添加到数据后面的余数是多少？若数据在传输过程中，最后一个1变成了0，接收端能不能发现？

    要点：余数为1110，可以发现差错（过程略）

    第四次作业

    1、  CSMA/CD和时分多路复用都是为了共享信道，两者各有何优缺点？

    要点：

     CSMA/CD时分多路复用
    接入媒体方式动态争用静态划分信道
    冲突/检测有，需要冲突检测无，不需要冲突检测
    主要应用场景局域网广域网

    2、  在以太帧中，会在物理层插入帧开始定界符，为什么不插入帧结束定界符？

    要点：帧开始定界符标明MAC帧开始。不需要帧结束定界符是因为以太网规定帧间最小间隔为 9.6 微秒，即帧与帧之间是有间隔的，帧开始定界符之后连续到达的比特流都属于同一个帧，所以不需要结束定界符。

    3、  在MAC帧中，当数据部分小于46字节，有填充字符时，如何判断具体的数据部分？

    要点：在上层IP协议中，有一个字段为“总长度”，即IP报首部和数据部分之和。当网络层接收到填充后的MAC帧，去掉首部和尾部后，超出总长度的部分即为识别为填充部分。

    4、  一个主机曾经连在一个交换机的端口上，并发送了数据，它的MAC地址会不会永远储存在MAC地址映射表中?为什么？

    要点：取决于地址表中的地址指定模式。手动指定，将一直存在，除非一次新的手动指定将其删除；动态指定，MAC地址在表中的生存时间（TTL老化时间）有限制，默认为300秒。超过生存时间，没有数据发送的MAC地址，将被默认为已经下线，地址将被删除。生存时间可根据需要进行设置。

    第 4 章  网络层

    最重要的内容：

    1. IP 地址与物理地址的关系、
    2. 路由选择协议的工作原理、
    3. 传统的分类的 IP 地址（包括子网掩码）和无分类域间路由选择 CIDR

    只向上提供简单灵活的、无连接的、尽最大努力交付的服务

    网络层概述：

    目的：屏蔽各种不同类型网络之间的差异，实现两个端系统之间的数据透明传送

    主要功能：路由选择、阻塞控制

    网际协议IP：

    Internet Protocol : TCP/IP 体系中两个最主要的协议之一

    与IP配套使用：

    1. 地址解析协议 ARP (Address Resolution Protocol)
    2. 网际控制报文协议 ICMP (Internet Control Message Protocol)
    3. 网际组管理协议 IGMP (Internet Group Management Protocol)

    网络中间设备：又称为中间系统或中继(relay)系统。

    1. 物理层中继系统：转发器(repeater)。
    2. 数据链路层中继系统：网桥或桥接器(bridge)。
    3. 网络层中继系统：路由器(router)，实现网络互连
    4. 网桥和路由器的混合物：桥路器(brouter)。
    5. 网络层以上的中继系统：网关(gateway)。  

    虚拟互连网络：

    定义：也称逻辑互连网络，即利用协议使结构和性能各异的物理网络互连起来，从用户角度看好像是一个统一的网络

    IP 网：使用 IP 协议的虚拟互连网络

    意义：主机进行通信时，就好像在一个网络上通信一样，不考虑互连的各具体的网络异构细节   

    IP 地址及其表示方法：

    IP 地址目的：给每个连接在因特网上的主机（或路由器）分配一个在全世界范围内唯一的 32 位标识符

    IP 地址分配机构：

    1. 因特网名字与号码指派公司 (Internet Corporation for Assigned Names and Numbers，ICANN)
    2. 我国用户：亚太网络信息中心（Asia Pacific Network Information Center, APNIC）

    分类 IP 地址：

    两个字段组成，分别是：

          网络号 net-id：标志主机（或路由器）所连接到的网络

          主机号 host-id：标志该主机（或路由器）。

    两级的 IP 地址可以记为：

          IP 地址 ::= { <网络号>, <主机号>}

    图片包含 图表 描述已自动生成

    IP 地址特点：

    (1)  IP 地址是一种分等级的地址结构。

          第一，IP 地址管理机构在分配 IP 地址时只分配网络号，主机号由得到该网络号的单位自行分配。

    图示, 文本 描述已自动生成

          第二，路由器仅根据目的主机所连接的网络号来转发分组，路由表中的项目数及所占的存储空间大幅度减少

    (2) 实际上 IP 地址是标志一个主机（或路由器）和一条链路的接口。

    第一，当一个主机同时连接到两个网络上时，该主机就必须同时具有两个网络号不相同的 IP 地址。

    第二，一个路由器至少应当连接到两个网络，至少应当有两个不同的 IP 地址。

    (3) 用转发器或网桥连接起来的若干个局域网仍为一个网络，具有同样的网络号 net-id。

    (4) 所有分配到网络号 net-id 的网络，无论地理范围大小，都是平等的 

    IP 地址与硬件地址

    1. 路由器只根据目的站的 IP 地址的网络号进行路由选择 
    2. 在具体的物理网络的链路层，只能看见 MAC 帧而看不见 IP 数据报
    3. IP层抽象的互联网屏蔽了下层很复杂的细节，在抽象的网络层上讨论问题，就能够使用统一的、抽象的 IP 地址，研究主机和主机或主机和路由器之间的通信

    地址解析协议 ARP

    每一个主机都设有一个 ARP 高速缓存(ARP cache)，存储所在局域网上的各主机和路由器的 IP 地址到硬件地址的映射表。当主机A 欲向本局域网上的某个主机 B 发送 IP 数据报时，就先在其 ARP 高速缓存中查看有无主机 B 的 IP 地址。

    情形一：有，就可查出其对应的硬件地址，再将此硬件地址写入 MAC 帧，然后通过局域网将该 MAC 帧发往此硬件地址。

    情形二：无，启动地址解析协议ARP  

    （1）主机A的ARP进程在本地局域网上广播发送一个ARP请求分组

    （2）在本局域网上的所有主机上运行的ARP进程都收到ARP请求分组

    （3）主机B的IP地址与主机A的ARP请求分组中要查询的IP地址一致，收下请求分组并将其中的IP地址和MAC地址，写入自己的ARP缓存

    （4）主机B向请求主机A发送响应分组（单播），并将自己的硬件地址写入响应分组

    （５）主机A收到主机B的响应分组，将其中的IP地址和MAC地址，写入自己的ARP缓存。

    应当注意的问题：

    1. ARP 是解决同一个局域网上的主机或路由器的 IP 地址和硬件地址的映射问题。
    2. 要找的主机和源主机不在同一个局域网上时，需要通过 ARP 找到一个位于本局域网上的某个路由器的硬件地址，然后把分组发送给这个路由器，由路由器把分组转发给下一个网络。剩下的工作由下一个网络来做
    3. 从IP地址到硬件地址的解析是自动进行的，主机的用户对这种地址解析过程是不知道的。

    使用 ARP 的四种典型情况：

    发送方目的方硬件地址备注
    主机本网络上的另一个主机目的主机的硬件地址
    主机另一个网络上的一个主机本网络上的一个路由器的硬件地址剩下的工作由这个路由器来完成
    路由器本网络上的一个主机目的主机的硬件地址
    路由器另一个网络上的一个主机本网络上另一个路由器的硬件地址剩下的工作由这个路由器来完成

    IP 数据报的格式

    一个 IP 数据报由首部和数据两部分组成

    首部由固定部分和可变部分组成

    　　　固定部分：固定长度，共 20 字节，是所有 IP 数据报必须具有的

    　　　可变部分：可选字段，且长度可变

    图形用户界面, 应用程序, 表格, Excel 描述已自动生成

    版本——占 4 位，指 IP 协议的版本，IPv4

    首部长度——占 4 位，以每4个字节为单位表示长度。 首部长度必须是4字节的整数倍，否则需用填充域填0来补齐。

    区分服务——占 8 位，用来获得更好的服务

    总长度——占 16 位，指首部和数据之和的长度，单位为字节，因此数据报的最大长度为 65535 字节，总长度必须不超过最大传送单元 MTU。

    标识(identification) ，占 16 位，产生数据报的标识/编号的计数器。

    标志(flag)    占 3 位，目前只有前两位有意义。

    片偏移：占13 位，较长的分组在分片后某片在原分组中的相对位置，以 8 个字节为偏移单位。计算！！

    图示, 日程表 描述已自动生成

    生存时间：占8位，记为 TTL (Time To Live)，数据报在网络中可通过的路由器数的最大值，新产生的IP报文中，TTL字段通常被设置为最大值255。

    协议：占8位，数据报携带的数据使用何种协议，以便目的主机的 IP 层将数据部分上交给哪个处理过程。

    首部检验和：占16 位，字段只检验数据报的首部，不检验数据部分。不采用 CRC 检验码而采用简单的计算方法。

    源地址和目的地址都各占 4 字节，为IP地址。

    可变部分：选项字段，长度可变(1 个字节到 40 个字节) ，取决于所选择的项目。

    1. 目的：增加 IP 数据报的功能
    2. 实际：首部长度可变，增加每一个路由器处理数据报的开销，很少被使用。 在IPv6版已经定义为固定长度

    特定主机路由：为特定的目的主机指明一个路由

    默认路由(default route)：只要没有指定特定主机路由，就一律选择默认路由

    注意：

    1. IP 数据报的首部中没有地方可以用来指明“下一跳路由器的 IP 地址”。
    2. 当路由器收到待转发的数据报，不是将下一跳路由器的 IP 地址填入 IP 数据报，而是送交下层的网络接口软件。
    3. 网络接口软件使用 ARP 负责将下一跳路由器的 IP 地址转换成硬件地址，并将此硬件地址放在链路层的 MAC 帧的首部，然后根据这个硬件地址找到下一跳路由器。  

    划分子网

    IP地址的不足：

    1. IP 地址空间的利用率有时很低。 
    2. 给每一个物理网络分配一个网络号会使路由表变得太大因而使网络性能变坏。
    3. 两级的 IP 地址不够灵活。 

    子网划分：将一个IP地址下连续的大段主机地址拆分成若干连续的较小的网络组，使得拆分后网络组的IP地址容量适合实际物理网络（网段）的规模，这种较小的网络组就叫做子网。

    子网划分好处（原因）：

    1. 充分利用IP地址资源
    2. 允许系统管理员按照自己的需要组织网络地址空间
    3. 同一类型主机划分为一个子网，便于管理
    4. 网络之外子网不可见
    5. 精简路由表项目数，提高效率
    6. 内部路由则由网络地址的所有者负责

    划分子网的基本思路：

    1、划分子网纯属一个单位内部的事情，对外仍然表现为没有划分子网的网络

    2、从主机号借用若干位作为子网号 subnet-id，主机号 host-id 相应减少了若干位

    IP地址 ::= {<网络号>, <子网号>, <主机号>}

    在 IP 地址中增加“子网号字段”，从两级 IP 地址到三级 IP 地址

    3、根据网络号识别目的网络：根据IP数据报的目的网络号 net-id，找到连接在本网络上的路由器

    4、根据子网号识别子网：路由器按子网号 subnet-id 找到目的子网

    5、根据主机号识别主机并交付IP数据报：最后将 IP 数据报直接交付目的主机

    子网掩码：

    注意：从IP 数据报的首部无法判断源主机或目的主机所连接的网络是否进行了子网划分

    子网掩码(subnet mask)：标志子网号在IP地址中的位置，由32位一连串的“1”（网络号掩码）和一连串的“0”（子网号掩码）组成

    当IP地址与其子网掩码相“与”（二进制逻辑与）时，就可以得到该地址的网络号和子网号,  也即子网的网络地址

    图片包含 日程表 描述已自动生成

    子网掩码的特点：

    1. 子网掩码是一个网络或一个子网的重要属性。
    2. 路由器的路由表中的每一个项目，除了要给出目的网络地址外，还必须同时给出该网络的子网掩码。
    3. 路由器在和相邻路由器交换路由信息时，必须把自己所在网络（或子网）的子网掩码告诉相邻路由器。
    4. 若一个路由器连接在两个子网上就拥有两个网络地址和两个子网掩码。

    无分类的两级编址（无分类的域间路由选择，CIDR, Classless Inter-Domian Routing）：

    网络前缀：IP地址 := {<网络前缀>, <主机号>}，IP地址/网络前缀位数

    32位IP地址中有多少位代表网络地址对应于三级编址中子网掩码中 1 的个数

    CIDR 最主要的特点：

    1. CIDR 消除了传统的 A 类、B 类和 C 类地址以及划分子网的概念，因而可以更加有效地分配 IPv4 的地址空间。
    2. CIDR使用各种长度的“网络前缀”(network-prefix)来代替分类地址中的网络号和子网号。
    3. IP 地址从三级编址（使用子网掩码）又回到了两级编址。

    路由聚合(route aggregation)：

    • 一个 CIDR 地址块可以表示很多地址，这种地址的聚合常称为路由聚合，它使得路由表中的一个项目可以表示很多个原来传统分类地址的路由。
    • 路由聚合也称为构成超网(superneting)。

    最长前缀匹配：选择两个匹配的地址中更具体的一个，即选择具有最长前缀的地址

    路由选择算法：

    路由选择算法：网络层软件的一部分，负责确定数据报的传输路由。分为静态和动态。

    优化目标：

    1. 分组平均时延小，网络吞吐量大
    2. 降低跳数（数据包经过的路由器数量）

    静态路由选择算法：非自适应—事先脱线计算好或设定好的，在网络启动时就下载到路由器中

    1. 静态路由选择算法：节点的路由表一旦确定不再自动改变的路由算法
    2. 静态路由的路由表一般在网络建立初期建立，可由网络管理员手工配置，也可采用某种路由算法产生。
    3. 静态路由信息默认情况下是私有的，不会在路由器之间互相传递。
    4. 静态路由一般适用于规模较小、比较简单、不太变化的网络环境

    最优化原则（optimality principle）：如果路由器 J 在路由器 I 到 K 的最优路由上，那么从 J 到 K 的最优路由会落在同一路由上

    汇集树（sink tree）：从所有的源结点到一个给定的目的结点的最优路由的集合形成的一个以目的结点为根的树

    基本思想：构建子网的拓扑图，图中的每个结点代表一个路由器，每条连线代表一条通信线路。为了选择两个路由器间的路由，算法在图中找出最短路径

    测量路径长度的度量方法：

    1. 结点数量
    2. 地理距离
    3. 传输延迟
    4. 距离、信道带宽等参数的加权函数

    动态路由选择算法：自适应—根据拓扑结构、通信量的变化动态改变其路由选择。

    可根据网络的变化适时调整路由表选择最佳路径

    工作过程：

    1、测量，通过测量了解网络的拓扑结构、流量、延迟等

    2、报告，向相关节点报告测量结果

    3、更新，根据新路由表重新选择最佳路径  

    4、决策，得到报告的节点根据测量结果更新路由表

    距离向量路由算法:（基于RIP）

    1. 基本思想：每个路由器维护一张表，表中给出了到每个目的地的已知最佳距离和线路，

    目的站      最短距离估计值         输出线路

    • 每隔一段时间，路由器向所有邻居结点发送它到每个目的结点的距离表，同时它也接收每个邻居结点发来的距离表
    • 根据交换的距离信息更新路由表

    算法步骤：

    1. 对地址为X的相邻路由器发来的RIP报文，先修改此报文中的所有项目：把“下一跳”字段中的地址都改为X，并把所有的“距离”字段的值加一。每一个项目都有3个关键参数，即：（到目的网络N，距离是的，下一跳路由器是X）。
    2. 对修改后的RIP报文中的每一个项目，进行以下步骤：

    若原来的路由器没有目的网络N，则把该项目添加到路由器中。

    否则（即在路由器中有目的网络N，这时就再看下一跳路由器地址）

           若下一跳路由器地址是X，则把收到的项目替换原路由表的项目。

    否则（即这个项目是：到目的网络N，但下一跳路由器不是X）

           若收到的项目中的距离小于路由表中的距离，则进行更新。

           否则什么也不做。

    • 若3分钟还没有收到相邻路由器的更新路由表，则把此相邻路由器记为不可达的路由器，即把距离置为16。
    文本, 信件 描述已自动生成

    缺点：

    1. 开销大(节点间要不断的相互交换信息)
    2. 交换的信息从相邻节点开始，由于延时获得全网状态信息的时间有先有后，有可能先前的最佳路径在当前已经不是最佳了，甚至是不通的，最终造成阻塞。（好消息传播快，坏消息传播慢）

    分层路由：

    1. 分而治之的思想；
    2. 根据需要，将路由器分成区域（regions）、聚类（clusters）、区（zones）和组（groups）…

    问题：路由表中的路由不一定是最优路由

    路由选择协议：

    • 自治系统(AS，autonomous system)：即遵循共同的路由策略统一管理下的网络群
    • 内部网关协议(IGP interior gateway protocol)：在自治系统内部执行路由功能。如路由信息协议(RIP)、开放最短路径优先(OSPF)
    • 外部网关路由协议(EGP exterior gateway protocol) ：在不同的自治系统间进行路由。如边缘网关协议(BGP Border Gateway Protocol)

    内部网关协议(RIP Routing Information Protocol)：

    距离：用中间路由器的数量进行度量

    基本思路：

    1. 每个路由器向与它相连的网络发送报告，说明它到本自治系统中所有网络的最短距离以及到每个网络应经过的下一跳路由器            
    2. 与其相连的路由器据此推断出自己可以通过两个站点到达各网络及其最短距离，并更新路由表
    3. 各个路由器不断接收信息、存储、再发送信息来建立、维护自己的路由表

    RIP的主要缺点：好消息传播得快，而坏消息传播得慢

    RIP的局限性：

    1. RIP约定目的端距离值超过15就不可达
    2. RIP采用路段数作为度量值，过分简化的距离值可能使得路由选择表达不到最佳状态
    3. 支持RIP的设备要从所有设备接收RIP更新向量，可能会使个别设备的配置错误影响到整个网络的配置
    4. 路由迅速发生变化（如链路出现故障）时，算法可能无法稳定，将出现路由表的不一致问题和慢收敛问题。
    5. RIP不支持负载均衡，不能在两个网络之间同时使用多条路由。RIP选择一条具有最少路由器的路由（即最短路由），不会选择另一条高速但路由器更多的路由。

    内部网关协议： OSPF  (Open Shortest Path First)

    1. “开放”：公开发表，不受某一家厂商控制
    2. “最短路径优先”：使用 Dijkstra提出的最短路径算法SPF，分布式的基于链路状态协议。

    IETF的IGP工作组为IP网开发的路由协议，目前主要用第其第二版。

    OSPF三个要点：

    1. 使用洪泛法向本自治系统中所有路由器发送信息
    2. 只有当链路状态发生变化时，路由器才用洪泛法向所有路由器发送信息
    3. 发送的信息就是与本路由器相邻的所有路由器的链路状态，但这只是路由器所知道的部分信息。

    OSPF最主要的特征：

    分布式链路状态协议及其分布式链路状态数据库：(link-state database) 路由器之间频繁地交换链路状态信息，最终所有的路由器都能建立一个链路状态数据库，实质上也就是全网的一致的拓扑结构图。

    OSPF采用层次结构的区域划分：

    在一个区域内的路由器最好不超过 200 个，洪泛法交换链路状态信息的范围局限于每一个区域而不是整个的自治系统。

    组成：

    自治系统边界路由器（ASBR）、主干路由器（BR）、区域边界路由器（ABR）、区域内路由器（IR）

    区域内部路由器：Internal Router，所有接口都属于同一个OSPF区域，不与其他区域相连接，只维护其所在区域的LSDB（链路状态数据库）。如R1，R2，R8，R9

    区域边界路由器：Area Border Routers，ABR：可以同时属于两个以上的区域，其中一个必须是骨干区域（area 0），主要用于连接骨干区域和非骨干区域，可以是物理连接，也可以是逻辑连接，生成和维护所连接区域的LSDB。如R3，R4，R7

    主干路由器：Backbone Routers，属于主干区域（area 0），只维护骨干区域的LSDB,  所有非骨干区域之间的信息都要通过骨干区域进行中转。所有的ABR和位于Area0的内部路由器都是骨干路由器。如R3，R4，R5，R6，R7
    自治系统边界路由器：AS Boundary Routers , ASBR，与其他AS交换路由信息的路由器, 通常使用多种路由协议。 不一定位于AS边界，有可能是ABR或，甚至区域内部路由器，只要它引入了外部路由信息，生成维护和与它相邻的自治系统间的LSDB。如R6

    OSPF 直接用 IP 数据报传送

    OSPF特点：

    1、不用 UDP 而是直接用 IP 数据报传送

    2、数据报很短

    3、链路状态发生变化时，才用洪泛法向所有相邻的路由器发送信息

    4、对不同的链路可设置成不同的代价

    5、可实现通信负载平衡

    6、所有在 OSPF 路由器之间交换的分组都具有鉴别的功能

    7、支持可变长度的子网划分和无分类编址 CIDR。

    8、每一个链路状态都带上一个 32 位的序号，序号越大状态就越新

    9、OSPF规定每隔一段时间，要刷新一次数据库中的链路状态

    10、 没有“坏消息传播得慢”的问题

    外部网关协议 BGP:

    1. 不同自治系统的路由器之间交换路由信息的协议。
    2. 2006 年 1 月， BGP-4，可简写为 BGP。
    3. 力求寻找一条能够到达目的网络且比较好的路由,而并非要寻找一条最佳路由。
    4. BGP 发言人，BGP speaker：每一个自治系统的管理员要选择至少一个路由器作为该自治系统的“ BGP 发言人” ，往往就是BGP 边界路由器，相邻的来自不同自治系统的 BGP 发言人一般都是通过一个共享网络连接在一起

    BGP 发言人和自治系统 AS 的关系:

    BGP 交换路由信息：两个BGP 发言人建立TCP连接，交换BGP报文，建立BGP会话，交换路由信息

    1. BGP 交换网络可达性信息，即到达某个网络所要经过的一系列 AS。
    2. 当 BGP 发言人互相交换了网络可达性的信息后，各 BGP 发言人就根据所采用的策略从收到的路由信息中找出到达各 AS 的较好路由。

    BGP 协议的特点:

    1. 路径向量算法：每个路由信息块列出沿某路由到达目标网络要经过的所有AS
    2. 路由表包括目的网络前缀、下一跳路由器，以及到达该目的网络所要经过的各个自治系统序列
    3. 交换路由信息的结点数量级是自治系统数的量级
    4. 每一个自治系统中 BGP 发言人（或边界路由器）的数目很少
    5. 刚刚运行时，BGP 的邻站交换整个 BGP 路由表，以后只需要在发生变化时更新有变化的部分
    6. 力求寻找一条能够达到目的网络且比较好的路由，并非要寻找一条最佳路由

    BGP-4 四种报文:

    (1) 打开报文：与相邻的另一个BGP发言人建立关系

    (2) 更新报文：用来发送某一路由的信息，以及列出要撤消的多条路由

    (3) 保活报文：用来确认打开报文和周期性地证实邻站关系

    (4) 通知报文：用来发送检测到的差错

    路由器:

    一种具有多个输入端口和多个输出端口的专用计算机

    任务：转发分组，即将路由器某个输入端口收到的分组，按照分组要去的目的地（即目的网络），把该分组从路由器的某个合适的输出端口转发给下一跳路由器。

    转发VS路由选择:

    1. “转发”(forwarding)：根据转发表将用户的 IP 数据报从合适的端口转发出去。
    2. “路由选择”(routing)：按照分布式算法，根据从各相邻路由器得到的关于网络拓扑的变化情况，动态地改变所选择的路由。
    3. 路由表：根据路由选择算法得出。
    4. 转发表：从路由表得出。

    输入端口处理收到的分组：数据链路层剥去帧首部和尾部后，将分组送到网络层的队列中排队等待处理

    输出端口将交换结构传送来的分组发送到线路：当交换结构传送过来的分组先进行缓存。数据链路层处理模块将分组加上链路层的首部和尾部，交给物理层后发送到外部线路。

    缓存管理不当，会造成分组丢弃: 路由器处理分组的速率赶不上分组进入队列的速率，或者输出端线路速率过低，则队列的存储空间最终必定减少到零，使后面再进入队列的分组由于没有存储空间而只能被丢弃。路由器中的输入或输出队列产生溢出是造成分组丢失的重要原因。  

    第5次作业

    1、试判别下列IP地址属于什么类型的网络？该类型网络的网络号和主机号各占多少位？最大可指派的网络数是多少？为什么？

    129.48.199.4

    26.24.230.16

    188.167.56.214

    78.12.69.248

    199.6.3.5

    要点：129.48.199.4 B 类 

    26.24.230.16 A 类 

    188.167.56.214 B 类 

    78.12.69.248 A 类 

    199.6.3.5 C 类

    　　　A类地址：网络号8位，主机号24位，最大可指派的网络数：128(27)-2=126，全０的IP和127不能用

    B类地址：网络号16位，主机号16位，最大可指派网络数：16384(214)－1＝16383，地址段全为０的一般不用

    C类地址：网络号24位，主机号8位，2097151(221)-1＝2097152，地址段全为０的一般不用

    2、  连接不同网络的中间设备主要是什么？工作在哪一层协议？转发器或网桥连接的网络是同一个网络还是不同的网络？

    要点：中继器（转发器），工作在物理层，物理层协议

    集线器，工作在数据链路层，数据链路层协议

    路由器，工作在网络层，网络层协议

    网关，工作在网络层或传输层或应用层，支持相应层协议

    交换机，一般工作在数据链路层，支持数据链路层协议。但有的交换机支持网络层，甚至传输层协议，相应地称为每三层交换机或第四层交换机。

    转发器或网桥连接的是同一个网络的不同网段。

    3、  与IP协议配套使用的协议的主要有哪三种？

    要点：地址解析协议 ARP（Address Resolution Protocol） 

    网际控制报文协议 ICMP（Internet Control Message Protocol） 

    网际组管理协议 IGMP（Internet Group Management Protocol）

    第六次作业

    1、以下地址中的哪一个和86.32/12匹配？说明理由。

    （1）86.39.189.156

    （2）86.79.63.54

    （3）86.58.120.76

    （4）86.45.206.154

    要点：考察第二字节前四位，如为0010，匹配，否则不匹配

          结果（1）（4）匹配，（2）（3）不匹配

    2、假定网络中的路由器B的路由表有如下项目，分别表示目的网络、距离和下一跳路由器，现收到来自路由器C的路由信息，试求出路由器B更新后的路由表

    //

    Answer:

    B（更新后）
    N18A没有新信息不变
    N25C下一跳不变，但路径变长
    N33C新路径，增加
    N46C新路径，增加
    N68F从C走，代价会增大，不变
    N84C没有新信息不变
    N93C从C走，代价会减少，变
    N103G没有新信息不变

    第五章 运输层

    目的：实现端到端的通信

    主要协议：TCP/UDP

    主要功能：可靠传输、流量控制、拥塞控制

    传输层基本概念：

    • 端系统上通常运行多个进程，为允许多个进程共享网络，需要有一个层次来提供多路复用和解多路复用功能。

    在发送方，多个进程都需要使用同一个传输层协议，向对方传送数据，这称为传输层的复用功能。

    在接收方，其传输层在拆解报文的首部后，能够将这些数据正确交付到其对应的应用进程。这称为传输层的分用功能

    • 网络层提供的服务有时不能满足应用程序的需要，需要有一个层次将网络层低要求的服务转变成应用程序需要的高级服务。

    传输服务:

    （1）传输实体（transport entity）：完成传输层功能的硬软件；

    （2）传输服务：传输层实体利用网络层提供的服务向高层提供有效、可靠的服务；

    传输层提供两种服务:

    面向连接的传输服务（TCP）: 连接建立、数据传输、连接释放

    无连接的传输服务（UDP）：发送方无需事先建立连接，只要有数据需要发送，就直接发送

    网络进程需要三级寻址即特定网络、主机地址和端口号。

    运输层协议和网络层协议的主要区别：

    • 网络层IP 协议的作用范围(提供主机之间的逻辑通信)
    • 传输层TCP 和 UDP 协议的作用范围(提供进程之间的逻辑通信)
    UDP TCP
    用户数据报协议：User Datagram Protocol传输控制协议：Transmission Control Protocol  
    无连接的，尽最大努力交付，面向连接
    不保证可靠交付，不需要确认，提供可靠交付
    不使用拥塞控制，全双工通信
    支持一对一、一对多、多对一和多对多的交互通信每一条 TCP 连接只能有两个端点即点对点或一对一（不提供广播或多播服务）
    首部开销小，只有 8 个字节
    面向报文面向字节流

    运输层的端口：利用进程标识符区分不同的进程

    在运输层使用协议端口号(protocol port number)，通常简称为端口(port)。只要把要传送的报文交到目的主机的某一个合适的目的端口，剩下的工作(即最后交付目的进程)就由 TCP或UDP 来完成。

    • 在协议栈层间的抽象的协议端口是软件端口
    • 路由器或交换机上的端口是硬件端口
    • 端口用一个 16 位端口号进行标志
    • 端口号只具有本地意义

    三类端口号：

    1. 熟知端口/系统端口：数值一般为 0~1023
    2. 登记端口：数值为1024~49151，为没有熟知端口号的应用程序使用。使用这个范围的端口号必须在 IANA 登记
    3. 客户端口号/短暂端口：数值为49152~65535，客户进程选择暂时使用

    UDP：面向报文

    • 发送方 UDP 对应用程序交下来的报文，在添加首部后就向下交付 IP 层。
    • 应用层交给 UDP 多长的报文，UDP 就照样发送，即一次发送一个报文，既不合并，也不拆分
    • 接收方 UDP 对 IP 层交上来的 UDP 用户数据报，在去除首部后就原封不动地交付上层的应用进程，一次交付一个完整的报文
    • 应用程序必须选择合适大小的报文

    TCP：面向字节流

    • TCP 连接是一条虚连接而不是一条真正的物理连接。
    • TCP 对应用进程一次把多长的报文发送到TCP 的缓存中是不关心的。
    • TCP 根据对方给出的窗口值和当前网络拥塞的程度来决定一个报文段应包含多少个字节
    • TCP 可把太长的数据块划分短一些再传送。TCP 也可等待积累有足够多的字节后再构成报文段发送出去。

    TCP 把连接作为最基本的抽象，每一条 TCP 连接两个端点，也叫做套接字(socket)或插口

    套接字：端口号拼接到(concatenated with) IP 地址构成

    可靠传输工作原理

    停止等待协议（停-等协议）：

    • 停等：每发送完一个分组就停止发送，等待对方的确认，在收到对方的确认后再发送下一个分组
    • 超时计时器：发送一个分组开始计时，收到该分组的确认时关闭计时器，否则超时，触发超时重传事件
    • 超时重传：每发送出一个报文后开启一个定时器，只要到一段规定时间后没有收到确认，就认为刚发的分组丢失，重传该分组
    • 在发送完一个分组后，必须暂时保留已发送的分组的副本
    • 分组和确认分组都必须进行编号
    • 超时计时器的重传时间应当比数据在分组传输的平均往返时间更长一些

    停止等待协议: 简单，但信道利用率太低

    流水线传输：Go-back-N(回退 N)

    • 发送方连续发送多个分组，不必每发完一个分组就停顿下来等待对方的确认
    • 信道上一直有数据不间断地传送，信道利用率高
    • 累积确认:接收方对按序到达的最后一个分组发送确认，意为到这个分组为止的所有分组都已正确收到了。

    优点：容易实现，即使确认丢失也不必重传确认

    缺点：不能向发送方反映出接收方已经正确收到的所有分组的信息

    TCP流量控制：

    流量控制(flow control)：让发送方的发送速率不要太快，既要让接收方来得及接收，也不要使网络发生拥塞。

    利用滑动窗口实现流量控制：

    1. TCP 为每一个连接设有一个持续计时器
    2. TCP 连接的一方收到对方的零窗口通知时，启动持续计时器
    3. 持续计时器设置的时间到期，发送一个零窗口探测报文段(仅携带 1 字节的数据)，对方对探测报文段确认时给出现在的窗口值
    4. 若窗口仍然是零，收到报文段的一方重新设置持续计时器
    5. 若窗口不是零，打破死锁僵局

    控制 TCP 报文段的发送时机：

    1. TCP 维持一个值等于最大报文段长度 MSS的变量：只要缓存中存放的数据达到 MSS 字节时，就组装成一个 TCP 报文段发送出去。
    2. 推送操作：发送方的应用进程指明要求发送报文段。
    3. 计时器：计时器期限一到，就把当前已有的缓存数据装入报文段发送出去

    拥塞控制的一般原理：

    拥塞(congestion)：在某段时间，若对网络中某资源的需求超过了该资源所能提供的可用部分，网络性能变坏

    ‘’

    发生拥塞的条件：

         对资源需求的总和 > 可用资源 

    慢启动（slow start）、拥塞避免（congestion avoidance）、快重传、快恢复

    判断网络拥塞得依据就是出现了超时。

    发送方的最大报文段大小SMSS(Sender Maximum Segment Size)

    TCP小结

    • TCP基于连接
    • 面向字节流
    • 双工通信
    • 滑动窗口机制、确认机制、重传机制、检验和机制等

    可靠传输、流量控制和拥塞控制

  • TCP的三次握手与四次挥手

    三次握手

    客户端 (SYN_SENT) >>> SYN=1, seq=client_isn >>> 服务器 (LISTEN)

    客户端() <<< SYN=1, ACK=1, seq=server_isn, ack=client_isn+1 <<< 服务器 (SYN_RCVD)

    客户端(ESTABLISHED) >>> SYN=0, seq=cilent_isn+1, ACK=1, ack=server_isn+1 >>> 服务器(ESTABLISHED)

    SYN泛洪攻击：客户端不发送第三次握手确认导致服务器大量消耗资源而宕机。

    解决方法：SYN cookies，只有等到客户端发送了包含server_isn+1的ack后服务器再去分配资源。

    四次挥手

    1. 第一次挥手： Client端发起挥手请求，向Server端发送标志位是FIN报文段，设置序列号seq，此时，Client端进入FIN_WAIT_1状态，这表示Client端没有数据要发送给Server端了。
    2. 第二次挥手：Server端收到了Client端发送的FIN报文段，向Client端返回一个标志位是ACK的报文段，ack设为seq加1，Client端进入FIN_WAIT_2状态，Server端告诉Client端，我确认并同意你的关闭请求。
    3. 第三次挥手： Server端向Client端发送标志位是FIN的报文段，请求关闭连接，同时Client端进入LAST_ACK状态。
    4. 第四次挥手 ： Client端收到Server端发送的FIN报文段，向Server端发送标志位是ACK的报文段，然后Client端进入TIME_WAIT状态。Server端收到Client端的ACK报文段以后，就关闭连接。此时，Client端等待2MSL的时间后依然没有收到回复，则证明Server端已正常关闭，那好，Client端也可以关闭连接了。

    为什么要等待2MSL？

    • 第一点：保证TCP协议的全双工连接能够可靠关闭：
      由于IP协议的不可靠性或者是其它网络原因，导致了Server端没有收到Client端的ACK报文，那么Server端就会在超时之后重新发送FIN，如果此时Client端的连接已经关闭处于CLOESD状态，那么重发的FIN就找不到对应的连接了，从而导致连接错乱，所以，Client端发送完最后的ACK不能直接进入CLOSED状态，而要保持TIME_WAIT，当再次收到FIN的收，能够保证对方收到ACK，最后正确关闭连接。
    • 第二点：保证这次连接的重复数据段从网络中消失
      如果Client端发送最后的ACK直接进入CLOSED状态，然后又再向Server端发起一个新连接，这时不能保证新连接的与刚关闭的连接的端口号是不同的，也就是新连接和老连接的端口号可能一样了，那么就可能出现问题：如果前一次的连接某些数据滞留在网络中，这些延迟数据在建立新连接后到达Client端，由于新老连接的端口号和IP都一样，TCP协议就认为延迟数据是属于新连接的，新连接就会接收到脏数据，这样就会导致数据包混乱。所以TCP连接需要在TIME_WAIT状态等待2倍MSL，才能保证本次连接的所有数据在网络中消失。

    1. time_wait状态如何产生？ 
    由上面的变迁图，首先调用close()发起主动关闭的一方，在发送最后一个ACK之后会进入time_wait的状态，也就说该发送方会保持2MSL时间之后才会回到初始状态。MSL值得是数据包在网络中的最大生存时间。产生这种结果使得这个TCP连接在2MSL连接等待期间，定义这个连接的四元组（客户端IP地址和端口，服务端IP地址和端口号）不能被使用。

    2.time_wait状态产生的原因

    • 为实现TCP全双工连接的可靠释放。由TCP状态变迁图可知，假设发起主动关闭的一方（client）最后发送的ACK在网络中丢失，由于TCP协议的重传机制，执行被动关闭的一方（server）将会重发其FIN，在该FIN到达client之前，client必须维护这条连接状态，也就说这条TCP连接所对应的资源（client方的local_ip,local_port）不能被立即释放或重新分配，直到另一方重发的FIN达到之后，client重发ACK后，经过2MSL时间周期没有再收到另一方的FIN之后，该TCP连接才能恢复初始的CLOSED状态。如果主动关闭一方不维护这样一个TIME_WAIT状态，那么当被动关闭一方重发的FIN到达时，主动关闭一方的TCP传输层会用RST包响应对方，这会被对方认为是有错误发生，然而这事实上只是正常的关闭连接过程，并非异常。
    • 为使旧的数据包在网络因过期而消失。为说明这个问题，我们先假设TCP协议中不存在TIME_WAIT状态的限制，再假设当前有一条TCP连接：(local_ip, local_port, remote_ip,remote_port)，因某些原因，我们先关闭，接着很快以相同的四元组建立一条新连接。本文前面介绍过，TCP连接由四元组唯一标识，因此，在我们假设的情况中，TCP协议栈是无法区分前后两条TCP连接的不同的，在它看来，这根本就是同一条连接，中间先释放再建立的过程对其来说是“感知”不到的。这样就可能发生这样的情况：前一条TCP连接由local peer发送的数据到达remote peer后，会被该remot peer的TCP传输层当做当前TCP连接的正常数据接收并向上传递至应用层（而事实上，在我们假设的场景下，这些旧数据到达remote peer前，旧连接已断开且一条由相同四元组构成的新TCP连接已建立，因此，这些旧数据是不应该被向上传递至应用层的），从而引起数据错乱进而导致各种无法预知的诡异现象。作为一种可靠的传输协议，TCP必须在协议层面考虑并避免这种情况的发生，这正是TIME_WAIT状态存在的第2个原因。

    3.time_wait状态如何避免

    1. 服务器可以设置SO_REUSEADDR套接字选项来通知内核，如果端口忙，但TCP连接位于TIME_WAIT状态时可以重用端口。在一个非常有用的场景就是，如果你的服务器程序停止后想立即重启，而新的套接字依旧希望使用同一端口，此时SO_REUSEADDR选项就可以避免TIME_WAIT状态。可以改为长连接，但代价较大，长连接太多会导致服务器性能问题，而且PHP等脚本语言，需要通过proxy之类的软件才能实现长连接；
    2. 修改ipv4.ip_local_port_range，增大可用端口范围，但只能缓解问题，不能根本解决问题；
    3. 客户端程序中设置socket的SO_LINGER选项；
    4. 客户端机器打开tcp_tw_recycle和tcp_timestamps选项；
    5. 客户端机器打开tcp_tw_reuse和tcp_timestamps选项；
    6. 客户端机器设置tcp_max_tw_buckets为一个很小的值

  • 操作系统总结

    微内核OS结构

    基本概念：

    1. 足够小的内核
    2. 基于客服/服务器模式
    3. 应用“机制与策略分离”原理
    4. 采用面向对象技术

    基本功能：

    1. 进程（线程）管理
    2. 低级存储器管理
    3. 中断和陷入处理

    进程

    程序并发执行时的特征：

    1. 间断性
    2. 失去封闭性
    3. 不可再现性

    进程的特征：

    1. 动态性
    2. 并发性
    3. 独立性
    4. 异步性

    进程状态：

    1. 就绪 -> 执行
    2. 执行 -> 就绪、阻塞、终止
    3. 阻塞 -> 就绪
    4. 创建 -> 就绪
    5. 终止

    操作系统内核：

    1. 支撑功能：中断处理、时钟管理、原语操作
    2. 资源管理功能：进程管理、存储器管理、设备管理

    同步机制应遵循的规则：

    • 空闲让进
    • 忙则等待
    • 有限等待
    • 让权等待

    进程通信

    1. 共享存储器（内存）系统（Shared-Memory System）
    2. 管道，共享pipe文件，互斥读写，半双工
    3. 消息传递系统/消息队列。直接通信、间接通信
    4. client-server通信。socket、rp

    线程与进程的比较

    1. 调度的基本单位
    2. 并发性
    3. 拥有资源
    4. 独立性
    5. 系统开销

    线程的实现

    1. 内核支持线程KST (Kernel Supported Thread)
    2. 用户级线程ULT (User Level Thread)

    调度算法：

    • 先来先服务FCFS
    • 短作业优先SJF
    • 优先级PSA
    • 高相应比HRRN (等待时间+要求服务时间)/要求服务时间

    调度方式：

    • 抢占式
    • 非抢占式 优先权、短进程、时间片

    轮转调度

    • 根据FCFS进行时间片轮转
    • 优先级，静态、动态
    • 多级队列 ，多个队列不同调度算法
    • 多级反馈队列，优先级越高时间片越短

    公平调度：根据获得CPU时间的比率、根据用户数

    实时系统调度算法

    • 非抢占性：轮转，优先级排序 抢占性：基于时钟中断、立即抢占
    • 最早截止时间优先EDF算法
    • 最低松弛度优先LLF
    • 优先级倒置的解决办法：优先级继承

    死锁的原因

    1. 竞争不可抢占性资源引起死锁
    2. 竞争可消耗资源引起死锁
    3. 进程推进顺序不当引起死锁

    死锁的条件

    1. 互斥条件
    2. 请求与保持
    3. 不可抢占
    4. 循环等待

    处理死锁的方法

    1. 死锁预防：破坏一个或多个条件、一次性或逐步分配释放资源
    2. 死锁避免：银行家算法（贪心）
    3. 死锁检测：资源分配图（拓扑排序？）
    4. 死锁解除：终止所有进程、逐个终止进程、最小代价

    分页储存管理

    • 页面、页面大小（1～8KB）
    • 页表 逻辑位置到物理位置的映射，控制位
    • 地址变换机构 页表寄存器、快表
    • 两级和多级页表
    • 反置页表

    分段存储管理方式

    • 方便编程
    • 信息共享
    • 信息保护
    • 动态增长
    • 动态链接

    段页式

    虚拟存储器

    局部性：时间局部性、空间局部性

    特征：多次性、对换性，虚拟性

    请求页表机制：

    • 状态位P： 是否已经调入内存
    • 访问字段A：记录一段时间内的访问次数
    • 修改位M：调入内存后是否被修改过
    • 外存地址：此页在外存上的地址

    缺页中断

    页面调入策略：

    • 何时：预调页策略、请求调页策略
    • 何地：足够空间的对换区Swap空间、未被修改直接换出修改过的进入swap、unix方式为运行的在文件区运行过的在对换区

    页面置换算法：

    • 最佳Optimal（无法实现）
    • 先进先出FIFO
    • LRU
    • LFU
    • Clock算法、改进Clock （循环遍历，未被访问则换出，改进后根据访问位A和修改位M分四类，都为0则为最佳，都为1则为最不佳）
    • 页面缓冲PBA

    抖动：页面反复换进换出

    中断

    中断和陷入：中断来自CPU外部、陷入来自CPU内部

    中断向量表（函数偏移表）、中断优先级

    对多中断源的处理方式：屏蔽中断、嵌套中断

    中断处理程序：

    1. 测定是否有未响应的中断信号
    2. 保护被中断进程的CPU状态（所有CPU寄存器的内容）
    3. 转入相应的设备处理程序
    4. 中断处理
    5. 恢复CPU现场并退出中断

    使用中断的可编程I/O

    假脱机技术（预先把数据读出来）、SPOOLing技术

    缓冲：单缓冲（互斥）、双缓冲、环形缓冲

    磁盘

    磁道、扇区（数据、控制字段、gap间隔）

    磁盘调度算法：

    • 先来先服务FCFS
    • 最短寻道时间优先SSTF（离当前磁道最近的，可能导致饥饿）
    • 扫描算法SCAN（像电梯一样往一个方向扫）
    • 循环扫描算法CSCAN （来回扫）

    磁臂沾着：某进程反复请求对某一次到的I/O操作，从而垄断整个磁盘设备

    解决的算法：

    • NStepSCAN算法（多个队列，当前正在扫描的队列和其他扫描的队列）
    • FSCAN（两个队列、当前和下一轮）

    文件管理

    索引文件：

  • MySQL中的锁

    MySQL的InnoDB中主要有8种锁（来自MySQL 8.0）

    • Shared and Exclusive Locks 读锁和写锁
    • Intention Locks 意向锁
    • Record Locks 行锁
    • Gap Locks 间隙锁
    • Next-Key Locks 行锁+间隙锁
    • Insert Intention Locks
    • AUTO-INC Locks
    • Predicate Locks for Spatial Indexes

    未完待续