《计算机通信网 》第5章 网络层1

第五章网络层1背景与相关问题2路由算法概述3路由算法4拥塞控制5网络互联11背景与相关问题1.1背景1.2网络层提供的服务1.3网络层的功能1.4网络层基础21.1背景链路层仅实现了数据单元(DU)在信道上的传输物理层链路层物理层链路层物理层MAC物理层MAC物理层MAC物理层MAC链路层将DU向某个/某些相连的站点传输物理层链路层物理层链路层形成网络的基础在上层，将DU再次传送出去，扩大DU的传输范围DU在一个设备内部实现链路层将DU向对方站点传输31.1背景由任意多个局域网和点对点链路的连接结构网络基本元素L1L2L1L2L1L2L1L2L3=点对点局域网(总线、环形、…)路由器在L3中继DU任意连接结构41.1背景简化模型“链路层”“物理层”“信道”简化成链路(线条)，DU从源站点的L3出发，经过中间多个L3的转发，最终到达目的站网络层的核心任务将分组从源端传送到目的端分组将如何穿越网络从源端到达目的端？相连端到端中间节点：如何知道目的地在何处？多条路径该选哪条路？选好的路故障怎么办？网络拥塞怎么办？★51.2网络层提供的功能★寻址标识节点，节点定位路由选择传播路径信息、形成路径选择路径存储转发接收数据并存储，并按选择的路由转发（逐段转发）拥塞控制网际互联穿越多个同构或异构网络可能涉及分段与重组记帐61.3网络层提供的服务★向传送层提供穿越网络的、端到端的服务，并屏蔽网络的具体细节向传送层提供的服务与具体的网络环境和技术无关传送层不必也不需要了解具体的网络情况对传送层而言，对等实体的通信就像直接通信一样服务类别面向连接的服务通常由面向连接的协议实现无连接的服务通常由无连接的协议实现71.3网络层提供的服务针对网络层究竟应该提供何种服务，两大阵营产生了激烈的冲突争论的焦点：通信子网应承担什么样的任务？面向连接还是面向无连接的服务和技术？以电信公司为代表认为网络层应提供面向连接的服务以IETF（Internet工程任务组）为代表认为网络层应提供无连接的服务81.3网络层提供的服务以电信公司为代表的理由100年来电信系统的成功经验就是典范，认为：通信子网应采用面向连接的服务与技术网络层应该提供可靠的服务尽量简单的终端建立连接后，通信更容易受到控制,可在连接上限制用户流量以IETF为代表的理由通信子网应采用无连接的服务与技术，因为：通信注定不可靠需要终端自行解决差错等问题－－复杂终端终端的复杂性与终端的成本不一定成比例上升用户不必支付过时的、高额的通信费用网络的适应性更强、带宽利用率更高更自由91.3网络层提供的服务两种不同的观念形成了两种不同的通信子网构成方式面向连接的通信子网——虚电路无连接的通信子网——数据报典型的面向连接的网络层ATM的网络层X.25网的网络层典型的无连接的网络层Internet的网络层★10数据报与虚电路虚电路方式节点寻径速度快数据报方式健壮性强重新建立连接，重新开始11数据报与虚电路项目类型数据报子网虚电路子网都是以分组为单位，存储转发、逐站寻径建链与拆链NOYES地址源、目地址虚电路号保存状态信息NOYES（虚电路映射表）路由选择每个分组独立选路所有分组沿已建好的路径转发节点或线路损毁的影响影响不大，可立即重新选路所有经过的虚电路被终止，须重新建立连接拥塞控制较难较易服务质量较难较易灵活性更好稍差★121.4网络层基础网络地址：编址与寻址路由表（FIT）：记录到达目的地的路径信息Routed：查表方法及转发策略Routing：计算到目的节点的最佳路径，生成并维护路由表网络层分组格式（PDU）网络层协议进一步分析无连接模式、连接模式★131.4.1网络地址网络地址的编址需求全网唯一地址：每个站点至少有一个唯一网络地址来标识网络地址结构有规律，有助于站点位置的查找（寻址）全网统一编址两个编址参考实例邮政编码6100xx6102xx6117xx郫县成都双流清水河校区沙河校区61830000832000008320111483201120832011198320345661830114618301196183012061834321电话号码特点：区域编址内部子区域编码任意编排特点：中心编址按中心接口位置编排141.4.1网络地址电话网（中心编址）国家号+城市号+局号+终端号Internet（区域编址）网络号+子网号+主机号对比以太网MAC地址编码MAC地址：xx-xx-xx-xx-xx-xxIP地址：aaa.bbb.ccc.ddd平面地址，地址与站点位置无关结构地址，地址与站点位置相关：位置在某个网络(aaa.bbb.ccc.0)区域内结构地址为网络协议提供了寻找站点所在位置的部分线索，但这对于寻找网络站点还远远不够！151.4.1网络地址考虑站点A向站点B传递报文ABR1R2R3R4R5传递过程可以分解为：1、A将报文传递到R1上2、R1设法找到B所在的区域位置(R5),并寻找到R5的路径，沿路径传递报文3、R5将报文传递到B上寻址的关键点：是各个R如何找出目的R在何处、及确定传输路径的问题，与源网络或目的网络关系不大。(中心编址方案亦如此)161.4.1网络编址和寻址区域编址与中心编址方案的寻址差异区域编址可能有多个目的R带来寻址灵活性的同时，也带来了寻址计算的复杂性中心编址只仅有一个目的R寻址方式简便、单一171.4.2路由表与转发策略★路由表（RoutingTable）通过路由协议计算出某个节点到目的节点的最佳路由，形成的路径信息有时也与转发表同义（ForwardingTable-FIT）注意：有时分为路由信息表和转发表两种表，而转发表由路由信息表得到路由表的组成ABCED121122A节点的路由表目的下一站出口度量B直连21DC13……181.4.2路由表与转发策略转发策略查路由表（转发表），根据转发路径进行转发转发之前如何查表？最短适配：从高地址部分开始适配即从最大的范围开始例：8602861830328最长适配：从低地址部分开始适配即从最接近主机的路由开始例：202.115.12.0高地址－－网络号低地址－－主机号其它查找算法：顺序、折半、Hash……不考虑地址的结构性，可提高查找效率与以上两种方法配合以提高效率完整适配：要求路由表规模太大，一般不用191.4.2路由表与转发策略主要技术问题(按地址寻址方式)地址空间太大，每个节点都装不下IP地址：32bit（232个地址）IPv6地址：128bit（2128个地址）只能记录已知部分查表运算量太大如上万个站点的表IP协议的处理方法仅考虑网络号部分，忽略主机号部分可以大大减小转发表项数目但仍然还有很大的运算量目的子网下一节点出口链路子网号主机号IP地址32比特201.4.3路由选择（Routing）寻找各处站点，在本地建立路径的方向转发表(FIT）Routing协议设置路由信息211.4.3路由选择（Routing）每个站点的FIT表内容表示从自己出发达到任意目的地址的“最短路径”。(不同站点FIT内容不同)Routing协议站点间路由信息交互计算到任意站点的最短路由，生成FIT表的内容221.4.4网络层分组格式L3转发DU—微观问题需要在DU中携带转发信息，L3才能处理L3接收DU、寻找路径、转发DU功能构成L3协议定义协议数据格式(分组，Packet)DU=网络层Packet=[协议首部+Data_Block]协议首部={类型、状态、方向等信息}Data-Block=携带的数据块(若干字节数据)HDataDU网络层分组链路层DU链路层HData根据首部信息选择转发出口链路L3231.4.4网络层分组格式无连接模式分组标志：首部包含源地址和目的地址连接模式分组标志：首部包含流ID号(可能名称不同)VerHLenTOSTotalLengthIdentifierFlagsFragOffsetTTLProtocolHCSSourceIPAddressDestinationIPAddressDataBlockIP分组格式GPILGNLCN分组类型DataBlockX.25分组格式(源地址、目的地址)(逻辑信道号=流ID)241.4.5网络层协议—进一步分析两种典型的网络通信体制比较无连接模式(ConnectionlessMode)通信体制数据报(Datagram)通信连接模式(ConnectionMode)通信体制虚电路(VirtualCircuit)通信S1D1D2S2考察S1D1、S2D2两对通信25无连接模式典型特征PDU首部包含有源地址S和目的地址D中间节点用目的地址D寻找PDU转发方向S1D1D2S2HDataSD……报文常规传输路径报文即使走错，地址D也会指出正确方向特性：1、不需要为通信预先建立完整传输路径2、报文没有固定的传输路径(数据报通信体制)3、各个报文独立穿越网络4、网状结构下，部分节点或链路故障不会造成通信中断5、节点难以估计通信自己的通信流量26连接模式典型特征PDU首部用连接id标明中继方向需要事先建立连接id的中继关系S1D1D2S2报文常规传输路径报文走错，连接id将把报文送到错误方位HDataid……11①②①②①②①②①②⑤①②③②⑤①27连接模式连接id标识的传输路径逻辑上等效于一条传输电路(VirtualCircuit)S1D1D2S211①②n连接id的编号空间大小等同于该链路的虚电路数目特性：1、需要预先建立id转发的完整传输路径2、报文沿id标识的固定路径传输(虚电路传输体制)3、同源、同id的各个报文沿路径顺序传输4、传输路径上节点或链路故障将造成通信中断5、节点可估计通过自己的通信流量12n28网络层协议—进一步分析DU传输路径问题HData转发信息=目的地址根据地址选择出口链路到X，走AA到X，走C到X，走QQX123njkm12knjkm12injkmHData原始转发信息13HDataHDataHDatamk根据首部的不同ID，从同一源站点发出的分组将走不同的路径，同时，分组首部ID也随之改变根据首部不同目的地址，从同一源站点发出的分组将走不同的路径，分组首部不发生改变HDataC29网络层协议—进一步分析无连接vs连接FITConnectionless网络协议利用FIT表直接转发PDU尽量发挥FIT直接转发的优势：1、用于网状拓扑结构的网络中2、动态修改FIT，形成动态路由，以适应网络动态变化3、地址空间巨大，每个报文都需经FIT查表，CPU计算负担重FITConnection网络协议FIT表仅用于建立id之间的转发关系FIT和id双重处理，尽量降低FIT处理负担：1、采用简单拓扑结构(如树形结构)2、不考虑网络动态变化，固定FIT3、优化数据转发：连接报文数目数据报文数目4、id转发关系动态建立，一次建立多次使用5、链路id空间小，查表负担轻30查表算法目的子网下一中继出接口FIT表路由器有一个FIT表供路由查询FIT可能达到几千上万条表项，假设有10000条表项，对每个PDU的目的地址平均需要查询5000次表项假设路由器每秒可转发M个报文，表项查询速率将达到5000*M（表项/秒）连接id对接表连接id出id出接口每个接口有一个连接id对接表，其表项只有几千个接口收到PDU，根据PDU的id号(=a)查表转发时，直接采取表索引找到出id和出接口。id=连接id对接表[a].出id接口=连接id对接表[a].出接口31通信体制：小结无连接方式A-B的通信可随时切换传输路径具备抗链路或中继站点故障能力分组到达B的顺序可能发生与A发出的顺序不一致易于实现广播通信中继转发性能较弱(地址空间大，FIT表庞大)每个分组平均需要M/2次查表(M为表项数)面向连接方式A-B的通信沿固定路径传输不具备抗链路或中继站点故障能力分组按顺序传输难以实现广播通信中继转发能力强(只关注流经本站的ID，FIT表小巧)优化情况下，每个分组只需一次查表32★2路由算法概述★