画布 1
计算机网络
  计算机网络和因特网
    定义
      一些相互连接的、自治的计算机的集合
    什么是因特网
      具体构成
        计算设备
          主机、端系统
        联网设备
          通信链路
          分组交换机
            接收、转发分组
            类型
              路由器
              链路层交换机
            分组交换技术
              发送端将要发送的数据分块，添加首部形成分组，分别发送到目的端，再组装恢复原数据
              端系统之间的通信路径不专用
        因特网服务提供商ISP
          提供不同类型的网络接入
          每个ISP独立管理，运行IP协议
        协议
          因特网协议TCP/IP
            TCP
              传输控制协议
            IP
              网际协议
          协议定义了通信实体之间发送、接收报文的格式和传输顺序，以及收到报文所采取的动作
      提供服务
        面向连接的可靠服务
          握手过程
          特性
            可靠的数据传送
              确认
              重传
            流控制
              将接收方来不及接收时，发送方降低发送速率
            拥塞控制
              防止因特网进入迟滞状态
              当网络拥塞时，降低发送速率
          传输控制协议TCP
        无连接的不可靠的服务
          特点
            不可靠
            无流控制或拥塞控制的功能
        任何一种分布式应用程序只能使用其中一种服务
    网络边缘
      外围部件、主机
      客户机
      服务器
      对等模式P2P
        最小限度（或不）使用专用服务器
        同时起客户机程序和服务器程序的双重作用
    网络核心
      电路交换
        预留端到端资源，建立连接，维持直至通信结束
        发送方以恒定速率传送数据（如传统电话网络）
        每个链路可有n条电路，能够支持n条同步连接
        多路复用
          频分多路复用FDM
          时分多路复用TDM
            只有一个时段允许发送
        效率低
        空闲时，浪费链路时间
      分组交换
        不预留资源
        按需使用资源，可能要排队等待
        分组以链路中的最大传输速率传输
        存储转发技术
          存储传法时延（传输时延）
            将一个分组转发到输出链路上所需的时间
          排队时延
            分组在输出缓存中等待转发的时间
        端到端的时延不稳定
      报文交换
        将要发送的整个信息作为一个报文发送
        被存储转发淘汰了
      分组交换网络
        虚电路网络
          源和目的主机之间建立虚连接
        数据报网络
          根据目的地址转发分组
          不需要建立连接
      拓扑结构
        星型
          结构简单
          可靠性差
        总线型、树型
          都连接到一条公共数据传输线上
          易于扩充，实时性较差
        环型
        分布式/网状
    接入网和物理媒体
      接入网
        将端系统连接到其边缘路由器的物理系统
      边缘路由器
        端系统到任何其他远程端系统的路径上的第一台路由器
      网络接入
        数字用户线DSL
          使用频分多路复用
            分为三个不重叠频段
          建立点对点来连接，所有带宽专用非共享
          随时提供服务
        混合光纤同轴电缆HFC
          共享广播媒体
          化为两个信道
          带宽更高
          随时提供服务
        无线接入
          无线局域网
          广域无线接入网
      物理媒体
        引导型媒体
          有线
          双绞线
            双绞线电缆
          同轴电缆
            抗干扰能力强，数据率高
          光纤
            速度高
            抗电磁干扰好
            传输距离远
            因特网的主干
            成本高
        非引导型媒体
          无线
          陆地无线电信道
          卫星无线电信道
    ISP和因特网主干
      第一层ISP
        最顶层，数量少
        是因特网的主干网络
        可以直接相连
        对等
      第二层ISP
        可与多个第一层ISP相连，从属关系
        是第一层的客户
        第二层ISP之间可以直接相连
      第三层ISP
        最靠近端系统
        经过第二层ISP与更大的因特网相连
    时延和分组丢失
      时延
        节点处理时延
          检查比特差错
          决定输出链路
          时延基本忽略不计
        排队时延
          在链路上传输的排队时间
          流量强度
            流量强度=La/R
              L：分组长度
              a：平均分组到达速率
              R：链路速率
            若流量强度大于1，则平均时延为无穷大
        传输时延
          将分组的所有比特推向链路（即传输，或发射）所需要的时间
          传输时延=L/R
            L：分组长度
            R：链路的传输速率
        传播时延
          比特在链路上从一节到下一节点传播所需要的时间
          传播时延=d/s
            d：两个节点之间的距离
            s：传播速率（光速或接近光速）
        端到端时延
      分组丢失
        链路的缓存队列满了，故丢弃分组
      因特网中的时延和路由
        Traceroute
    协议层次及其服务模型
      体系结构
        分层结构
      协议分层
        上层调用下层的服务，下层为上层提供服务
        第n层提供的报文的可靠传输
          通过使用第n-1层的不可靠报文传输服务，以及本层的检测和重传丢失报文的功能实现
        缺点
          有些功能可能在不同层重复出现
      因特网协议栈
        应用层
          报文
          提供各种网络服务
          OSI细分
            应用层
            表示层
            会话层
        运输层
          报文段
          在应用程序的客户机和服务器之间提供传输应用层报文服务
          TCP，UDP
        网络层
          数据报
          主机和主机之间传输网络层分组
        链路层
          帧
          在邻近节点之间传输数据
        物理层
          比特
      节点分层
        路由器
          只能实现第一层到第三层，能够实现IP协议
        链路层交换机
          实现第一层和第二层
        主机
          实现所有5个层次
      分组后数据传递过程
        发送方逐层封装
        接收方逐层解封
    发展历史
      分组交换的发展
        电话交换网
        分组交换
        通信子网
          由结点交换机、通信线路及设备组成
          保证高效、可靠地数据通信
          网络核心
        资源子网
          网络外围，包括主机、终端、软件
          数据处理
          网络边缘
      因特网爆炸
        电子邮件
        Web
        即时讯息
        MP3对等文件共享
  应用层
    应用层协议原理
      概念
        应用程序软件只在端系统上运行，不需在网络核心设备上运行
      网络应用层程序体系结构
        客户机/服务器
          客户机
            向服务器发出请求
            具有动态IP地址
            可以间歇性打开
            彼此之间不直接通信
          服务器
            为多个客户机提供服务
            拥有永久的IP地址
            总是打开
        纯P2P体系结构
          无打开的服务器
          任意端系统可以直接通信
          对等方间歇地连接
          IP地址不固定
          文件共享BitTorrent、迅雷
          可扩展度高、难以管理
        客户机/服务器与P2P的混合体系结构
          即时讯息应用
      进程通信
        进程
          在主机上运行的程序
        进程通信
          同一主机中两个进程间的通信，由操作系统控制
          不同主机中进程的通信，通过网络交换报文进行
        发送进程
          产生报文并向网络发送
        接受进程
          接收报文，并回送报文
        客户机和服务器进程
          由成对的进程组成
          客户机进程
            发起通信的进程
          服务器进程
            等待其他进程联系的进程
        套接字
          同一台主机内应用层和运输层之间的接口
          也叫做应用程序编程接口API
          发送进程（套接字）→传送报文→接收进程（套接字）
          对套接字的运输层端几乎不能控制
        进程寻址
          进程识别信息
            哪台主机上的哪一个进程
            主机名称或地址，IP地址
            进程标识，端口号
            创建新程序时，必须分配不重复的新端口号
          根据进程识别信息找到对应进程
        用户代理
          是用户与网络应用程序之间的接口
      应用层协议
        应用层协议是网络应用的一部分
        公共领域协议
          如HTTP
        专用层协议
          如Skype使用的协议
      应用程序所需要的服务
        应用程序间通信
        可靠的数据服务（无数据丢失）
        带宽（数据传输率）
        定时（数据传输的时间限制）
      因特网运输协议提供的服务
        传输控制协议TCP
          面向连接的服务
          可靠地传输服务
          过程
            建立连接
            传输报文
            拆除连接
          拥塞控制
          未提供的服务
            不确保最小传输速率
            不提供时延保证
          不适合实时应用
        用户数据报协议UDP
          提供最小服务模式运行
          不可靠的数据传输
          没有拥塞控制机制
          不提供时延保证
    Web应用与HTTP协议
      概述
        URL
          统一资源定位符
          存放对象的服务器主机名和对象的路径名
        是无状态的，不保存用户信息
      HTTP连接
        非持续
          每个TCP连接上只传送一个Web对象
          工作过程
            1. 客户机初始化一个TCP连接
            2. 服务器在80端口监听TCP连接请求
            3. 客户发送HTTP请求报文
            4. 服务器发出响应报文
            5. 服务器关闭TCP连接
            6. 客户机解析HTML文件
          每个TCP连接只传输一个请求报文和一个响应报文
          浏览器可以同时打开多个连接
          往返时延RTT
            一个小分组从客户机到服务器，再回到客户机所花的时间
          总响应时间=2RTT+文件传输时间
          传输时延长
        持续
          每个TCP连接上传送多个Web对象
          默认使用
          服务器在发送响应后保持该TCP连接
          相同客户机与服务器之间的后续请求和响应报文通过相同的连接进行传送
          连接经过一定的时间间隔（超时间隔）未被使用，服务器就关闭该连接
          非流水线式
            客户机只能在前一个响应接收到之后才能发出新的请求
            每次都是一个RTT时延
          流水线方式
            连续产生请求
            连续发送对应对象
            节省RTT时延
            TCP连接空闲时间短
      Cookie
        允许Web站点跟踪、识别用户
        四个部分
          HTTP响应报文有一个cookie首部行
          HTTP请求报文有一个cookie首部行
          用户主机保留有一个cookie文件并由浏览器组织管理
          Web站点的后端数据库保存cookie
      Web缓存
        Web缓存器（代理服务器）
        代表起始服务器来满足HTTP请求的网络实体
        保存最近请求过的对象副本
        可以在客户机或服务器或中间系统工作
        代替原始服务器满足HTTP请求
        需要检查本地是否有该对象的拷贝
          若无则与该对象的起始服务器打开一个TCP连接
        减少客户机请求的响应时间
        减少机构内部网络与因特网连接链路上的通信量
        添加Web缓存器可以减小时延
      条件GET
        使缓存器能够证实其保存的对象是否为最新
        使用方法
          1. Web服务器回发响应报文，包括对象最后的修改时间
          2. 缓存检查该对象是否被修改，发送一个条件GET请求报文
          3. 若对象被修改，Web服务器发一个最新的对象，若未被修改，发送304 Not Modified报文
    FTP
      文件传输协议，向远程主机上传或者下载文件
      用户通过一个FTP用户代理与FTP服务器交互
      控制连接
        传输控制信息（如用户标识、口令等）
        在21端口上建立
      数据连接
        准确传输文件
        在20端口上建立
        每进行一次文件传输，都要建立一个新的数据连接
      控制连接是持续的，数据连接是非持续的
      FTP与HTTP的比较
        FTP是带外传送，即控制连接与数据连接分离
        HTTP是带内传输，即请求、响应、传输文件都在一个TCP连接的发送
        FTP协议是有状态的，即保留用户状态
        HTTP协议是无状态的
    电子邮件
      结构
        用户代理
          邮件阅读器
          撰写邮件时，向邮件服务器发送
          接收邮件时，从邮件服务器获取
        邮件服务器
          报文队列
          通过SMTP协议转发到接收方邮件服务器
        简单邮件传输协议SMTP
          使用TCP，端口号25
          每个邮件服务器上都有SMTP的客户机端和服务器端
          SMTP不使用中间邮件服务器发送邮件
          SMTP是一个推协议，把邮件推向对方服务器
          使用7位ASCII码报文
          把所有对象放在一个报文中
      邮件访问协议
        用户代理从邮件服务器上取回邮件的协议
        是一个拉协议
        POP3
          用户读取邮件后，服务器不再保存
        IMAP
          建立TCP实时连接，是一个联机协议
        HTTP
    DNS
      主机标识方式
        主机名
        IP地址
      域名系统DNS
        进行主机名到IP地址的转换
        一个由分层的DNS服务器实现的分布式数据库
        允许主机查询分布式数据库的应用层协议
        通常直接由其他应用层协议使用，用户只是间接使用
        运行在UDP上，使用端口53
      运行过程
        1. 用户主机运行DNS客户端
        2. 浏览器从URL中解析出主机名，传给DNS客户端
        3. DNS客户端向DNS服务器发送一个包含主机名的请求
        4. DNS客户端收到含有IP地址的报文
        5. 浏览器向该IP地址指定的Web服务器发起一个TCP连接
      查询方法
        递归查询
          客户端只发起一次请求，要求对方给出最终的结果
          负责到底
        迭代查询
          要么给出所查询的IP地址，要么告诉本地服务器下一步应该向哪一个域名服务器查询
          你去问他吧
    P2P文件共享
      位于网络边缘的端系统互相之间可以直接获取对象
      流行协议，BitTorrent
      运行过程
        1. 运行P2P文件共享软件
        2. 搜索一首MP3歌曲
        3. 显示所有在线对等方，并可以提供拷贝
        4. 选择一个对等方，向其请求MP3文件
        5. 两个用户之间建立一个直接的TCP连接
        6. 传送文件
      直接在对等方之间传输
      高度可扩展能力
      使用客户机/服务器模式
  运输层
    运输层服务
      运输层服务
      为不同主机上的应用进程提供逻辑通信的功能
      就好像不同主机是直接相连的
      进程之间使用逻辑通信功能彼此发送报文
      无需考虑具体链路
      只运行在端系统中
      网络层提供主机之间的逻辑通信，而运输层提供进程之间的逻辑通信
      运输层协议所能提供的服务受底层网络协议服务模型的限制
      因特网运输层协议
        用户数据协议UDP
        传输控制协议TCP
      网络层
        IP（网际协议）
        尽力而为服务，属于不可靠服务
    复用和分解
      多路复用
        发送主机
        从不同套接字收集数据块，并未每个数据块封装上首部信息，生成报文段，传递到网络层
      也就是多个数据使用了一个运输层的通道，要把他们塞进去和区分开
      多路分解
        接收主机
        将报文段中的数据交付到正确的套接字，即接收方运输层从报文段的多个字段中，识别出套接字，并将报文段定向到该套接字
      无连接的多路复用与分解
        UDP套接字组成（目的IP，端口号）
        具有不同源的套接字，但具有相同目的套接字的UDP报文段，可通过相同套接字定向到相同的目的进程（多对一）
        源端口号用途，目的方回发报文段中的“返回地址”
      面向连接的多路复用与分解
        TCP套接字组成（源IP，源端口号，目的IP，目的端口号）
        两个具有不同源套接字的TCP报文段，将被定向到两个不同的套接字
      高性能的Web服务器通常只是用一个进程，可以为每个连接创造一个线程
    UDP
      若要实现经过UDP的可靠传输，可以在应用层增加可靠性，实现特定的差错恢复
      差错检测
        发送方将每两个字节当作一个16位的整数，求和，对得到的和逐位取反
          最高位的进位加回结果的最后中
        接收方对接收到的信息（包括校验和）以16位求和，若结果全为“1”，则无误，若有“0”，则有错
    可靠数据传输原理
      构造可靠的数据传输协议
        通过协议，为上层提供可靠的数据传输（但是底层信道一般是不可靠的）
        RDT1.0
          假设
            底层信道完全可靠，数据传送不出错不丢失
            收发双方速率匹配
            不会发生任何差错
          有限状态机
            发送方
            接收方
        RDT2.0
          假设
            信道不完全可靠，可能会产生比特差错
            信道不会丢包
            所有分组按发送顺序被接收（有可能有比特错）
          机制
            自动重传请求协议ARQ
              ACK和NAK
            需要额外附加checksum字段
            停等协议
              发送完一个分组后停止，等待对方回答
          缺陷
            无法处理ACK和NAK受损的问题
          有限状态机
            发送方
            接收方
        RDT2.1
          假设
            没有丢包
          机制
            发送方附带序号信息，若受到模糊不清的ACK或者NAK，则简单重发上一分组
          有限状态机
            发送方
            接收方
        RDT2.2
          假设
            没有丢包
          机制
            不再发送NAK，而是接收方在ACK信息中表达上一个正确接收序号的ACK
          有限状态机
            发送方
            接收方
        RDT3.0
          机制
            会出现比特差错
            会出现丢包
              处理方法
                超时重发
                时间选择
                产生冗余分组
                设置一个计数定时器
          有限状态机
            发送方
            接收方与RDT2.2一致
        停等协议的性能
          能够正常工作，但效率极低
          利用率=发送方将比特发送到信道的时间/发送时间
      流水线可靠数据传输协议
        利用率
          利用率=(L/R)/(L/R+RTT)*N
        需要增加序号范围
        需要缓存多个分组
      Go-Back-N（GBN）
        发送方
          连续发送多个分组，停止等待
          收到确认ACK，继续发送后面分组
          超时，未收到应答，从出错分组开始重发
        接收方
          正确接收，发送确认ACK
          出错，将该分组和后面的分组都丢弃，不发出任何应答
        机制
          连续发送的分组个数不能太多
          GBN也被称为滑动窗口协议
          发送窗口
            已确认、已发未确认、准备发送、不能发送
            窗口大小N为已发未确认和准备发送两个窗口的大小之和
        发送窗口最大尺寸
          若序号位数为n位，则发送窗口的最大尺寸是WT=2^k-1，而不是2^k
          若滑动窗口大小为2^k，如果接收方关于正确接收这2^k个数据的ACK全部丢失或超时，则会出现发送方重发这组数据，但是接收方误以为是新数据
        有限状态机
          发送方
          接收方
        缺陷
          出错时，要重复发送后面的全部分组，影响效率
      选择性重传SR
        改进
          发送方只重传出错（丢失或受损）的分组
        发送方
          连续发送多个数据分组，停止等待
          收到确认ACK，继续发送后面分组，基序号向前移动到具有最小序号的未确认分组处
          超时，未收到应答，只重发出错分组
          每个分组都有自己的定时器
        接收方
          不按序号接收数据分组
          接收正确，交付上层，并发确认ACK
          接收出错，丢弃该分组，将以后正确的分组放入缓存，当出错分组正确接收到后，按照顺序一起向上层交付
          只有接收分组序号等于基序号，才会被交付
          只要序号落在接收窗口内的正确分组都接收
        窗口最大尺寸
          若序号位数有k位，则发送和接收窗口的最大尺寸为2^(k-1)
          若接收方发送的一组ACK信息全部丢失，则接收方的滑动窗口和发送方的滑动窗口将会出现重复序号，会出错
      存在问题
        若发送方和接收方的窗口都没有包含x，但有可能会出现一个具有序号或确认号x的分组的旧拷贝
        规定分组最长的寿命以解决这个问题
    TCP
      特点
        面向连接
          握手交换控制信息
        全双工数据
          双向传输
        点到点
        流量控制
          发送速率不超过接收方能力
        拥塞控制
          网络拥塞时遏制发送方速率
      序号和确认号
        序号
          报文段中第一个数据字节在字节流中的位置编号
        确认号
          期望从对方收到下一个字节的序号
    拥塞控制原理
      拥塞原因与开销
        情况分析
          无限缓存路由器
            当分组到达速率接近来链路容量时，分组排队时延非常大
          有限缓存路由器
            发送方必须执行重传以补偿因为缓存溢出而丢弃的分组
            发送方可能会提前发生超时，并重传在队列中已被推迟但还未丢失的分组（浪费）
          有限缓存路由器和多跳路径
            通过同一个缓存路由器时，经过多跳的路径由于输出λout的限制，与直接与缓存路由器相连的主机而言，在供应载荷趋近于无穷大的情况下，空闲缓存将会被立即占满，此时经过多跳路径的吞吐量将会趋近于0
            改进：优先考虑已经历过一定数量的上游路由器的分组
      拥塞控制方法
        端到端拥塞控制
          通过对网络行为（如分组和延迟）的观察，推断网络是否存在拥塞
        网络辅助的拥塞控制
          通过网络层构件向发送方提供关于网络拥塞状态的明确反馈信息
        拥塞信息反馈方式
          直接反馈
          经由接收方的反馈
      ATM ABR拥塞控制
        异步传输模式ATM
        可用比特率ABR
        明确的计算出它所能发送的最大速率，并以此进行调整
        控制框架
          传输数据信元与资源管理信元（信元也就是分组）
    TCP拥塞控制
      端到端控制
        由发送方根据感知到的拥塞程度，来限制其发送流量的速率
      限制发送速率
        设置拥塞窗口cwind
          对发送方向的网络发送流量速率进行限制
      感知网络拥塞
        超时或者3个重复ACK
      拥塞控制算法
        加增倍减算法AIMD
          不拥塞就窗口加1，拥塞就窗口减半
        慢启动
          不拥塞就窗口加倍
          启动的一点也不慢
        超时事件后的保守机制
          Tahoe
            先使用慢启动，超过阈值后若无拥塞则窗口加1
            若产生拥塞，则窗口变为1，阈值变为拥塞窗口的一半，随后再进行慢启动和加增
          Reno
            若产生拥塞，则阈值变为一半，窗口大小从一半开始加增（跳过从1开始的慢启动）
  网络层
    概述
      网络层服务
      路由器仅有网络层以及下面两层
      将分组从发送主机移动到接收主机
      转发
        当一个分组到达输入链路时，将其移动到合适的输出链路
        转发表
        本地动作
      选路
        确定分组经过的路由或路径
        由选路算法决定
        网络范围动作
      网络服务模型
        可能提供的服务
          确保交付
          具有时延上界的确保交付
          有序分组交付
          确保最小带宽
          安全性
        因特网网络层提供的服务
          尽力而为服务
          上面的可能服务一个都达不到
        ATM提供的服务
          都满足几乎
      向运输层提供主机到主机的服务
      运输层只这几两个端系统，路由器并不知道运输层连接，网络层是要所有的路由器都参与进来
    虚电路和数据报网络
      虚电路网络
        提供连接服务
        VC(Virtual Circuit)
        组成
          源和目的之间的一条连接路径
          VC号
          路由器转发表中的表项
        工作原理
          在源和目的之间创建一个VC
            发：发起呼叫
            接：入呼叫
            接：接受呼叫
            发：呼叫已连接
          源向该VC发送带有VC号的分组
          每经过一台中间路由器，用新的VC号代替原VC号
          分组在每条链路上的VC号不同
          据此直至目的地
        路由器控制VC号
          每创建一条虚电路，就增加一项，否则就删除
        每条链路采用不同VC号的优点
          减少分组首部VC字段的长度
          简化虚电路的建立过程
      数据报网络
        提供无连接服务
        特点
          网络层无呼叫建立
          路由器没有端到端连接的状态
          分组使用目的主机地址转发
            相同源和目的地的分组可能采用不同的路径
        原理
          发送方给要发送的分组加上目的端系统地址，并送入网络，经过若干中间路由器查询转发表转发分组，直到目的地
        转发表
          使用目的地址和转发表的最长前缀匹配法
          只维持转发状态信息
          由选路算法修改（1-5分钟）
          可能选择不同的路径，到达的顺序可能不是按照发送顺序
      优缺点
        虚电路
          网络功能复杂
          端系统设备简单
          来源于电话接线的真实电路
        数据报
          网络层服务模型简单
          端系统功能复杂
    路由器的构成
      输入端口
        实现输入链路的链路层和物理层功能
        查找转发表决定转发至哪个输出端口
          分散式转发
            在输入端口本地做出交换决策，选路处理器将转发表拷贝给各个端口后就在更新前无需再激活
          集中式转发
            直接将分组转发给中央选路处理器
        查表速度
          要求
            输入端口的处理速度要超过线路速度（减少排队）
          查找方式
            线性查找
            二分查找
            内容可寻址内存（CAM）
      交换结构
        将分组从输入端口转发到输出端口中
        方式
          内存
            用于早期的用计算机作为的路由器
            受内存带宽的速度限制（要穿过两次总线）
            现代路由器由输入线路上的处理器来执行目的地址查找
              类似共享内存的多处理机
          总线
            通过一条共享总线将分组直接传送到输出端口
            可能会排队
            受到总线速率限制
          纵横式
            输入端口沿水平，输出端口沿垂直
            要考虑垂直（输出）总线是否空闲
      输出端口
        需要有排队和缓存管理功能
      选路处理器
      排队现象
        输入端口不容易排队
          则交换结构的速率至少是输入线路速率的n倍
        输出端口容易排队
          最坏情况：n个输入端口的数据均从一个输出端口输出
        分组调度程序
          先来先去服务FCFS
          加权公平排队服务WFQ
        分组丢弃方法
          去尾
          主动队列管理AQM
            在缓存填满前丢弃分组或首部加标记，向发送方提供拥塞信号
            随机早期检测RED
              小于最小阈值：纳入队列
              最小阈值和最大阈值之间：以某种概率倍标记或丢弃
              大于最大阈值：标记或丢弃
    选路算法
      选路
        数据报
          不同分组可能采用不同路径路由
        虚电路
          所有分组采用同一路径
      默认路由器
        也叫做第一跳路由器
        即直接与源或目标主机相连的路由器
        源路由器、目的路由器
      网络的抽象图模型
        使用节点图表示网络的结构
        边的值（链路费用）
          直接相连
            c(x,y)=链路费用
          不直接相连
            c(x,y)=∞
          要使得路径上的链路费用之和最小
      选路算法分类
        全局性还是分散性
          全局选路算法
            以全部网络信息计算最低费用
            e.g. 链路状态算法LS(Link State)
          分散选路算法
            只有与其直接相连链路的费用信息
            e.g. 距离向量算法DV(Distance Vector)
        静态还是动态
          静态选路算法
          动态选路算法
            负载或拓扑发生变化时改变路径
        对负载是否敏感
          负载敏感算法
            链路费用动态变化，反映拥塞级别
          负载迟钝算法
            链路费用不反映拥塞级别
        链路状态算法LS
          前提条件
            已知网络拓扑和所有链路费用
          获取方法
            每个节点向网络中广播链路状态分组（含有它所连接的链路费用）
            由链路状态广播算法实现
            每个节点会获得一个相同且完整的网络视图
          Dijkstra最低费用路径算法
            是一种迭代算法
            符号定义
              c(x,y)节点x到y的链路费用
              D(v)从源节点到目的节点v的当前费用
              p(v)从源节点到节点v的路径上的前一节点
              N'最低费用已被求出的节点集合
            具体算法我不信你不会
              1. 初始化
              2. 从不在N'的节点中找出一个到源节点的费用最低的节点w，加入N'，并以此更新它的邻居节点的D(v)值
              3. 重复第二步
            根据目的节点找出顺序和其费用以及前一节点，可以画出源节点u到目的节点的最低费用路径树
            复杂度O(n^2)
          默认路由
            将相同的点合并成一项，目的节点用“*”表示
            优先级最低，若在转发表找不到对应表项，就使用默认路由
          缺陷
            可能产生振荡
              不停的选择不同的两条路
            避免震荡
              避免所有路由器同时运行LS算法
              以周期性运行LS算法，不同路由在不同时刻运行
        距离向量算法DV
          特点
            分布式
              从其直接相连邻居接收信息
            迭代
              计算过程一直持续到邻居间没有更多信息交换为止
            自我终结
              算法能自行停止
            异步
          算法
            1. 初始化，计算到所有邻居的费用Dx(y)，非邻居节点Dx(y)=∞
            2. 发现直接相连的链路费用变化，或受到邻居的新距离向量，更新自己的距离向量Dx(y)=minv{c(x,v)+Dv(y)}
              在经过每个邻居v到目的点y的距离向量中，选择一个最小值作为当前新距离向量，并将所经过的邻居v作为节点x转发表中到目的节点y的下一跳路由器v*(y)
              若更新过程中发生改变，则向其邻居发送新距离向量
              注意：只利用别人的更新自己到各个节点的距离向量，别人的不用管
          选路表
            每个节点维护一张选路表（距离表）
            行：一个距离向量
            列：所有目的节点
          链路费用改变与故障
            节点之间来链路费用减少的“好消息”在网络中能迅速的传播
            链路费用增加的“坏消息传播得很慢
              会产生选路回环，即A通过B选路，B通过A选路
              前面几次的更新会出错，因为A经过B到达C的费用其实是原来的错误的B→A→C的路径
              毒性逆转
                如果z通过y选路到达目的地x，则z会告诉y（只告诉y这个无穷大，其他正常告诉），它到x的距离是无穷大
                未能解决“不可计数问题”
                当涉及到三个或更多节点的回路将不能被毒性逆转技术检查到
        LS和DV比较
          DV只与邻居交流，LS通过广播与所有节点交流
          LS算法可以迅速处理不正确费用，具有一定健壮性；而DV算法会有选路回环，不正确的计算值会扩散至整个网络
        层次选路
          按区域或自治系统的形式组织路由器，将一个大的系统划分成若干个小系统（自治系统AS），自治系统再互相连接
          AS
            在相同管理者控制下的路由器组成
            运行自己的选路算法
            自治系统要知道其他AS可以到达哪里
            AS之间运行相同的AS间选路协议
          网关路由器
            负责AS之间的互相连接
    因特网的选路
      AS内部选路协议
        OSPF开放最短路径优先
          采用Dijkstra的一种链路状态协议
      AS间选路协议
        BGP边界网关协议
          基于距离向量的路由协议
  链路层
    概述
      链路层服务
      信道类型
        广播链路
          需要通过媒体访问协议来协调传输和避免冲突
          共享一个链路
          使用MAC协议协调多个节点的帧传输
        点对点通信链路
      提供的服务
        将分组通过一个链路，从一个节点传输到邻近的另一个节点
        可靠传输
        流量控制
        差错检测
        差错纠正
        全双工和半双工
      链路层协议
        以太网、802.11无线LAN，令牌环、PPP、ATM
      适配器（网络接口卡NIC）
        将网络层数据报封装成链路层帧
        特点
          是一个半自治的单元
          适配器负责发送和接收帧
            出错则丢弃，不通知适配器所在节点；正确则向上传递数据报，中断其所在节点
        组成
          总线接口
            与父节点通信
          链路接口
            实现链路层协议
    差错检测和纠错技术
      纠错流程
        发送节点
          将数据D附加若按差错检测和纠错位EDC，一起发送到链路
        接收节点
          接收比特序列D'和EDC'
          接收方D'和EDC'，判断D'是否与初始的D相同
        可能会出现有差错未能检测到的情况
      奇偶校验
        一比特奇偶校验
          发送方
            将要发送的信息D（d位）后面附加一个奇偶校验位，使得“1”的个数是奇数（奇校验）或偶数（偶校验）
            将这d+1位一起发送
          接收方
            检测受到的d+1位信息中“1”的个数
          特点
            可以发现奇数个错误，但不能发现偶数个错误
            若差错集中突发，未检测到的概率可以达到50%
        二维奇偶校验
          将数据形成矩阵形式，进行每行每列的偶校验
          特点
            可以检测并纠正单个比特差错
            能够检测（但不能纠正）分组中任意两个比特的差错
        前向差错纠正FEC
          可以ARQ一起应用
          减低分组传输的往返传播时延，适用于实时网络应用
      检查和校验
        运输层常用
        发送方
          将数据每两个字节当作一个16位的整数，求和，对得到的和逐位取反
        接收方
          对接收到的信息（包括检查和）以16位求和，全“1”则无差错，有“0”则有差错
        特点
          分组开销小
          差错检测能力弱
          适用于运输层
          链路层中的差错检测有适配器中专用的硬件实现，采用更强的CRC方法
      循环冗余检测CRC
        进行多项式编码
          双方提前协商好生成多项式G是什么
        发送方
          计算出一个r位的附加比特R，添加到D的后面产生DR（d+r比特）
          DR能被G模2运算（按位异或）整除，一起发送
        接收方
          用G除接收到的DR（d+r比特）
          若余数非0，则传输发生差错
          若余数为0，传输正确，去掉尾部r位，得到所需数据D
        R的计算
          将数据D后面添加r个0，除以给定的生成多项式G，所得的余数即为R（r位）
        模2运算
          操作数的按位异或运算
          乘2^r，即比特模式左移r个位置
        简明运算
          数据D添加r个0在后面，除以G得到余数R，组合成为DR。接收方检测DR是否能被G整除
        生成多项式G的选择
          可选8、12、16、32比特
          8比特用于保护ATM信元头部
          32比特为标准的CRC32用于链路级协议
        特点
          能检测小于r+1位的突发差错，任何奇数个差错
    多路访问协议
      解决问题
        如何协调多个发送和接收节点对共享广播信道的访问
      存在冲突
        两个以上的节点同时传输帧，所有冲突帧都将丢失
      信道划分协议
        时分多路复用TDM
          每个节点只在固定分配的时隙中传输
          特点
            避免冲突，公平
            节点速率有限R/N b/s
            效率不高：必须等待传输时隙
        频分多路复用FDM
          将带宽R b/s划分为N个较小信道，分配给N个节点
          特点
            避免冲突，公平
            节点带宽有限、效率不高
        码分多址CDMA
          给每个节点分配一个不同的编码
          每个节点用自己唯一的编码对要发送的数据进行编码
          不同节点允许同时发送，不会互相干扰
      随机访问协议
        ALOHA
          采用星型网络结构
          时隙ALOHA
            操作过程
              有帧要发送，需要等待下一个时隙开始
              无冲突则能成功传输帧
              有冲突，在节点检测到冲突后，以概率p在后续的每一个时隙重传直至成功
            特点
              以全速R连续传输
              分散的
              发送控制简单
              有多个活动节点时效率低
            三种时隙
              冲突时隙C
              空闲时隙E
              成功时隙S
            时隙成功概率
              只有一个节点传输而其他N-1个节点不传输
              Np(1-p)^(N-1)
              最大效率：1/e=0.37
          纯ALOHA
            非时隙的，完全分散的
            操作过程
              有帧要发就立即传输
              如果冲突，就以概率p立即重传该帧
              若掉入1-p的概率中，则等待一个帧的传输时间，再以概率p传输该帧
              直至成功
            问题
              一帧尚未结束，另一帧又开始，会产生冲突
            成功概率
              p(1-p)^(2(N-1))
              最大效率：1/2e=0.18
          特点
            相互独立的，分散的
            发生冲突时不会停止传输
            效率不高
        载波侦听多路访问CSMA
          载波侦听CS
            监听信道
            若有其他节点正在发送帧，则随机等待一段时间，再侦听信道
            若信道空，则立即开始传输
          冲突检测CD
            便发送边监听
            若发生冲突，立即停止传输
          CSMA
            没有冲突检测
            即是发生了冲突，依然持续发送
            这会导致整个帧都无用
          CSMA/CD
            以太网采用此种协议
            检测到冲突就放弃传输
      轮流协议
        轮询协议
          存在主节点
          主节点以循环的方式轮询每个节点，并告诉能够传输的最大帧数
          特点
            能够完全消除冲突和空间隙，效率高
            存在轮询时延
            如果主节点失效，整个信道都不能用
        令牌传递协议
          没有主节点
          设置一个令牌token
          令牌以固定顺序循环传递，给节点传输机会
          若要传输，就立即传输，传完后令牌到下一节点
          否则令牌直接给到下一节点
          特点
            分散的，效率高
            一个节点的失效会使整个信道崩溃
            一个节点忘记释放令牌，必须恢复令牌到环中
            IEEE802.5令牌环
      局域网
        特点
          地理范围小
          使用多路访问协议
          传输速率R高
        应用
          单位用户通过LAN接入因特网
        两种LAN技术
          随机访问技术
          令牌传递技术
            令牌环
              令牌沿环路顺序传递
              有节点要发，则等待令牌到来
              得到令牌，发送一个帧，沿着整个环传播
              到达目的节点，接收，做标记
              帧沿环路循环一周返回源点，检查标记是否传输成功
              不成功则重发，成功则将帧从环中移走，并传递令牌
            FDDI
              范围更大的LAN
              目的节点将帧从环中移走
    链路层编址
      应用层地址
        主机名
      网络层地址
        IP地址
          层次结构
      链路层地址
        MAC地址
          6字节长
          唯一
          永久
          平面结构
          由网卡负责封装与识别
      特殊帧
        广播帧地址
        全1地址
    以太网
      采用LAN技术
      最为流行
      以太网帧结构
        CRC检测范围不包括前同步码
        IP数据报超过最大传输单元MTU为1500字节
        前同步码
          用于时钟同步
          无效信号，接收后删除，不向上传输