九乡新闻网自制脉冲式喷气发动机:基于Linux系统的边界网关协议的设计与实现-1
来源：百度文库 编辑：九乡新闻网 时间：2024/04/28 19:39:25
国内图书分类号：TP316.4
西 南 交 通 大 学
研 究 生 学 位 论 文
基于Linux系统的边界
网关协议的设计与实现
年 级 二零零六级
姓 名 徐金荣
申请学位级别 工学硕士
专 业 计算机软件与理论
指 导 教 师 李 允
二零零八 年 十二 月
Classified Index:TP316.4
Southwest Jiaotong University
Master Degree Thesis
DESIGN AND IMPLEMENTATION OF BGP BASED ON LINUX SYSTEM
Grade: 2006
Candidate: XuJinRong
Academic Degree Applied for: Master of Engineer Science
Major: Computer Software and Theory
Supervisor: LiYun
December.2008
西南交通大学学位论文版权使用授权书
本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权西南交通大学可以将本学术论文编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。
本学位论文属于
1．保密 ?，在 年解密后适用本授权书；
2．不保密 √，适用本授权书。
学位论文作者签名： 指导教师签名：
日期 日期
西南交通大学学位论文创新性声明
本人郑重声明：所呈交的学位论文，是在导师指导下独立进行研究工作所得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中作了明确的说明。本人完全意识到本声明的法律结果由本人承担。
本学位论文的主要创新点如下：
论文主要基于Linux平台进行BGP协议的设计，Linux系统有强大的网络功能且成本低廉，硬件环境容易获取，便于推广和使用；BGP协议开发过程中，结合Dynamips cisco路由仿真软件进行测试，仅需一台PC机就可以完成所有网络实验，有一定的教学推广价值；基于Linux系统的BGP路由软件采用模块化开发方法，便于新的协议的开发和移植，如果加入更多的协议，便可以设计出功能更全的路由软件，让其运行在高性能多网卡的PC机上，就可以充当路由器的角色，有潜在的商业价值。
摘 要
Internet是一个由多个自治系统相互连接构成的网络，BGP协议就是一种应用在基于TCP/IP网络的多个自治系统间交换网络层可达性信息的路由协议，研究BGP协议对Internet的发展有着重要的意义。
本文使用Linux操作系统提供的TCP/IP协议栈设计并实现了一款BGP协议路由软件。该路由软件主要包含两个子系统，一个是BGP子系统，用于运行BGP协议；另一个是RMer子系统，用于读取和更新Linux内核路由，同时将内核信息通过RMER报文发送给BGP系统。
BGP系统中实现了BGP邻居关系的建立、BGP路由通告、BGP路由聚合、BGP路由重分配、BGP路由属性的管理和BGP有限状态机等。BGP系统和RMer子系统间使用基于Linux系统本地的TCP连接进行通信，RMer系统和Linux内核之间使用入输出控制接口进行通信。BGP系统和RMer系统共同使用VTY模块解析和处理用户输入的命令行。总系统中采用了虚拟线程管理机制，共有6种类型的线程，READ类型线程用于读操作，WRITE类型线程用于写操作，TIMER类型线程用于处理超时事件，EVENT类型线程用于处理BGP状态机事件，READY类型表示准备就绪可以被调度的线程，UNUSED类型表示空闲的线程。
在系统设计过程中，利用Linux系统强大的网络功能，充分使用了模块化的设计方法，便于BGP功能的扩展和新协议的增加。对该BGP路由软件测试的结果表明，本文设计的基于Linux TCP/IP协议栈的BGP协议实现了BGP协议的主要功能，能够稳定地运行，具有一定的学术科研价值和商业价值。
关键词：BGP；Linux；TCP/IP；协议；路由
Abstract
Internet is a kind of network consists of multiple interconnected autonomous systems. Border Gateway Protocol (BGP) is used to exchange Network Layer Reachability Information (NLRI) between multiple autonomous systems in Transmission Control Protocol/Internet Protocol (TCP/IP) networks. Analysis of BGP is significant to the development of Internet.
This paper designs a BGP routing software based on Linux. This software includes two subsystems. On
BGP system realizes the establishment between BGP neighbors, BGP route advertisement, BGP route aggregation, BGP route redistribution, management of BGP route attributes and BGP Finite State Machine (FSM) etc. BGP system communicates with RMer system by Linux local based TCP connection, RMer system communicates with Linux kernel by input/output control (ioctl). BGP system and RMer system commonly use VTY module to parse and process command line. System performs virtual thread mechanism, which includes six types threads, READ type thread is related to read operation, WRITE type thread is related to write operation, TIMER type thread is used to process time out event, EVENT type thread is used to process BGP FSM, READY type thread means this thread is ready to be scheduled, UNUSED type thread means this thread is idle.
Linux system’s powerful network functions and modular design technologies are widely used during the process of designing system, which is convenient to extend BGP functions and add new protocols. The test result of this system shows that the BGP protocol based on Linux TCP/IP protocols stack realize main BGP functions and can run stably. This research has certain academic and commercial value.
Keywords: BGP; Linux; TCP/IP; protocol; route
目 录
第1章 绪 论 1
1.1 课题研究的背景及意义 1
1.2 本文的主要工作 2
1.3 论文组织结构 3
第2章 边界网关协议BGP4 4
2.1 BGP基本工作原理 5
2.2 BGP报文格式 7
2.2.1 报文头格式 7
2.2.2 OPEN报文格式 7
2.2.3 UPDATE报文格式 8
2.2.4 KEEPALIVE报文格式 10
2.2.5 NOTIFICATION报文格式 10
2.3 BGP路径属性 11
2.3.1 ORIGIN属性 12
2.3.2 AS_PATH属性 12
2.3.3 NEXT_HOP属性 13
2.3.4 MULTI_EXIT_DISC属性 15
2.3.5 LOCAL_PREF属性 15
2.3.6 ATOMIC_AGGREGATE属性 16
2.3.7 AGGREGATOR属性 17
2.4 BGP决策过程 17
第3章 系统模块设计 19
3.1 系统体系结构 19
3.2 CLI模块 22
3.3 THREAD管理机制 24
3.4 VTY服务器 32
3.5 BGP路由器间通信 33
3.6 BGP和RMER系统间通信 37
3.7 RMER和LINUX内核间通信 41
第4章 BGP协议的实现 44
4.1 静态路由表管理 44
4.2 动态路由表管理 47
4.3 RMER和BGP间的路由更新报文 49
4.4 BGP有限状态机 51
第5章 BGP协议测试 57
5.1 BGP测试平台 57
5.2 BGP功能测试 58
第6章 结论与展望 62
致 谢 63
参考文献 64
攻读学位期间发表的论文 67
第1章 绪 论
1.1 课题研究的背景及意义
Internet是一个全球互联的计算机网络。随着Internet的飞速发展，在全球范围的层面上对其进行有效地管理将越来越困难。出于管理和扩展的目的，因特网被分割成许多不同的自治系统（Autonomous System，AS[1]）。换句话说，因特网是由自治系统汇集而成的。AS自身可以有自己的一套规则和策略，能够把自己和其它AS惟一地区别开来。
一个AS是拥有同一选路策略、在同一技术管理部门下运行的一组路由器。每个AS被看作是一个进行自我管理的网络，一个自治系统只负责管理自己内部的路由。以AS为边界，可以将常用的动态路由协议分为AS间的外部网关协议（Exterior Gateway Protocol，EGP[2]）和AS内部的内部网关协议（Interior Gateway Protocol，IGP[1]）。边界网关协议（Border Gateway Protocol，BGP[3]）就是为TCP/IP[4,5]网络设计的用于自治系统之间的EGP路由协议。该协议的基本功能是与其他BGP协议自治系统交换网络层可达信息（Network Layer Reachable Information，NLRI[3]），这种可达信息包含了通往目标所要穿越的自治系统记录，利用这些信息，系统就可以构建一个无环的自治系统连接图，并把形成的外部路由信息重发布给内部网关协议IGP。随着Internet的迅速发展，网络拓扑的日趋复杂，多个自治系统间的通信的要求越来越高，BGP协议也显得越来越重要。
BGP可以说在一定程度上综合了距离向量和链路状态算法的优点，是一种路径向量协议。被称为路径向量协议的原因在于BGP路由信息中包含着AS号的一个序列，这个序列指明了路由经过的路径。利用这个信息可建立起各AS的连接图，从而避免路由循环。
我们已经知道在单个AS中使用内部网关路由协议（如RIP[6]，OSPF[7]等）执行路由功能。BGP的引入使实现自治系统间无环路由信息交换更容易，并且能够通过无类域间路由选择（Classless Inter-Domain Routing, CIDR[8]）来控制路由表的扩展。设计BGP也是为了通过使用自治系统来提供Internet的一个结构化的清晰视图。
IETF的Inter-Domain Routing工作组分别在1989年公布了BGP协议的版本1（BGP-1），1990年公布了版本2（BGP-2），1993年公布了版本3（BGP-3），1995年公布了版本4（BGP-4），BGP-4是目前Internet上使用的外部路由协议。BGP在不断发展的过程中逐渐成为Internet路由体系结构的基础。
本课题使用的硬件平台是X86平台，使用的操作系统是Linux系统，这样做的优点是：
1， 将更多的精力放到对BGP协议的设计上，不用考虑硬件的设计问题；
2， Linux系统有很成熟的TCP/IP协议栈，为BGP协议的稳定运行提供保证；
3， 路由器价格昂贵，在多接口的PC机上运行特定的协议，使其具备特定的路由功能，可以节约成本；
4， 在X86的Linux平台下，便于对协议进行开发和调试，只要在设计时充分考虑移植性，设计出来的协议可以很容易就移植到其他硬件和软件平台下。
1.2 本文的主要工作
本论文使用Linux系统提供的TCP/IP协议栈，设计和实现了BGP协议。具体来说，主要的工作内容有如下几点：
1．BGP协议的设计
本论文的BGP协议是参考RFC1771实现的，其中包括BGP协议的基本工作原理、BGP协议的四种报文、BGP协议的有限状态机、BGP协议的路径属性以及BGP决策过程的实现。
2．BGP协议功能设计
在BGP协议设计完成的基础上，尽可能完善地对BGP协议功能进行设计，包括基本BGP协议配置命令，BGP路由聚合，BGP路由重分配，BGP路径属性管理等功能的设计。
3．系统体系结构设计
因为本论文是基于Linux系统的BGP协议设计，使用的Linux系统提供的结构，如何管理好BGP协议和操作系统之间的关系，这是一个关键点。论文中从thread管理机制、VTY模块、BGP子系统、RMer子系统等多个方面进行模块化设计，层次清晰，具有较强的可移植性，同时对各个模块间的通信方式进行了设计。
4．BGP协议的测试
本文使用cisco路由器模拟软件Dynamips，对本系统的功能进行了测试，其中包括对基本BGP协议配置命令，BGP路由聚合命令，BGP路由重分配命令，BGP路径属性管理命令等功能进行了测试。
1.3 论文组织结构
本论文共分6章：
第1章是“绪论”。分析该课题的研究背景及意义，明确课题研究目标，了解国内外研究现状，介绍了本文的主要工作，简述了论文的组织结构。
第2章介绍了边界网关协议的基本概念，包括BGP协议的基本工作原理，BGP报文，BGP状态机，BGP路径属性等。
第3章对系统中的各个模块进行了详细的设计。
第4章是BGP协议的实现部分，主要涉及BGP路由表，以及BGP有限状态机的实现。
第5章是对本文实现的BGP协议进行测试，并对测试结果进行分析。
第6章总结了本论文的主要工作及对本课题未来工作的展望。
第2章 边界网关协议BGP4
20世纪80年代初期，ARPANET[9]使用一种称之为GGP[10]的距离向量路由协议。在该协议中，每一个路由器都要知道达到每个可达网络的路由。随着Internet的发展，ARPANET的构建者们发现这种路由协议的扩展性很差，首先，随着网络规模的增加，路由表的更新以及路由算法的开销变得相当庞大。其次，随着GGP软件数量的增加以及运行平台的多样化，软件升级的阻力也变大了，将Internet看成一个完整的通信系统是不可能的。为了解决Internet的扩展性问题，RFC827[11]中引入了自治系统AS和外部网关协议EGP的概念。RFC827中提出的解决方案是将ARPANET从一个单一的互联网络转移到一个相互连接的、自主控制的网络系统。在每个互联网络的内部，也就是我们所说的AS内部，管理机构可以自主选择路由协议来管理这个AS。这样做的效果是，AS的概念扩大了互联的范围，并为这种分层机构加入了新的一层。曾经是一个单一的互联网络，现在变成了一个由AS构成的网络，这些AS本身就是一个独立的互联网络。在AS内部运行的路由协议称之为IGP。GGP是缺省的第一个IGP，目前GGP已经完全被RIP、IGRP[12]、OSPF以及IS-IS[13]等路由协议所取代。在AS之间通过EGP协议来进行通信。
EGP对于ARPANET来讲已经足够了，但是EGP不能检测到环路，因此在这种情况下，它不能高效地选路，它的聚合时间很长并且缺乏支持路由策略的工具。于是在1989年的RFC1105[14]中提出了一个全新的AS域间协议，它就是BGP协议。BGP的第一个版本在一年后的RFC1163[15]中得到更新。在1991年的RFC1267[16]中BGP再一次被升级。人们习惯性地把这3个版本分别称为BGP-1、BGP-2以及BGP-3。
在1995年的RFC1771中，提出了最新的BGP版本BGP-4。最重要的区别就是BGP-4是无类的，而早期的版本都是有类的。外部网关协议存在的根本目的是为了保证Internet上路由的可管理性以及可靠性。无类域间路由CIDR同样也是因为这个目的而产生的。CIDR最早在1993年的RFC1517中提出，作为标准的建议在同年的RFC1519[17]中完成，并在RFC1520[18]中再次得到修改，而BGP-4的出现就是为了支持CIDR。
2.1 BGP基本工作原理
BGP是一种用于在AS间传递网络可达信息的路径向量协议。BGP通过在对等体间交换网络可达信息来构建AS可达信息拓扑图，对BGP而言，整个Internet就是一个大的AS图，到Internet上任一目的的路由可以通过一个AS路径来表示。
BGP到它的每一个运行BGP的对等体间都形成了基于单播的连接，为了提高连接的可靠性，BGP使用TCP作为它底层的传输机制，端口号为179。BGP的更新机制也因为让TCP层来处理像确认、重传以及排序等任务而在一定程度上得到了简化。
BGP有4种类型的报文，包括OPEN报文、KEEPALIVE报文、UPDATE报文、NOTIFICATION报文。首先两个BGP对等体必须执行标准的TCP三次握手，并且打开一个到端口179的TCP连接。然后交换OPEN报文并确认BGP连接参数，如果在收到的OPEN报文中没有发现差错，会互相发送KEEPALIVE报文以确认连接正常。在确认连接正常后，BGP对等体之间的连接就完全建立起来了，对等体之间开始交换UPDATE信息，最初交换的是完整的BGP路由表，之后只需要进行增量更新。BGP对等体之间会周期性地发送KEEPALIVE报文以确认连接正常。当遇到报文出错或其它异常情况时发送NOTIFICATION报文并关闭连接[45,46]。
BGP路由器进行BGP路由通告时要遵守如下规则[19]：
1. 如果本地有多条目的前缀相同的BGP路由存在时，把最优的BGP路由通告BGP 邻居；
2. BGP路由器会把自己从EBGP邻居学来的路由通告给所有其他BGP邻居（包括IBGP邻居和EBGP邻居）；
3. BGP路由器不会把从IBGP邻居学来的路由通告给其他IBGP邻居；
4. BGP路由器是否要把从IBGP邻居学来的路由通告给EBGP邻居，取决于路由的同步情况；
5. 一旦BGP连接建立成功，BGP路由器会把自己所有的BGP路由通告给新建立的BGP邻居。
用户可以通过命令行接口（Command Line Interface，CLI）对路由器进行配置，BGP相关的配置命令如表2-1所示。
表2-1 BGP相关配置命令[42-44]
router bgp as-number 该命令用于打开一个BGP路由进程。默认情况下系统没有BGP路由进程。
neighbor ip-address remote-as
as-number BGP路由器用于和EBGP peer或者IBGP peer之间建立邻居关系。
network ip-address /mask-bit 将指定的网络通过BGP协议广播出去。
neighbor ip-address shutdown 该命令可以在不删除与这个邻居相关的neighbor配置命令的前提下结束BGP会话。
neighbor ip-address maximum-prefix
maximum 限制从特定邻居得到的前缀数目，当前缀数目超过maximum时，BGP peer会话会被关闭。
bgp router-id ip-address 用于明确地设置BGP路由器的ID。
aggregate-address ip-address /mask-bit 在BGP路由表中创建一个聚合的条目。
redistribute protocol 把通过除BGP外的路由协议得到的路由重新分配到BGP中。
bgp bestpath as-path ignore 用于最优路由选择。当该命令打开时，表示在最优路径选择时，不考虑AS-path属性。默认情况下，系统会考虑AS-path属性。
bgp bestpath compare-routerid 用于最优路由选择。当BGP路由器从不同的EBGP peer收到多条路由时，BGP路由器的最优路由选择程序会选择路由器ID最小的那条路由作为最优路由。默认情况下，该命令是关闭的，当两条路由的其他属性均相同时，BGP路由器会选择先到达的那条路由。
bgp enforce-first-as 当BGP路由器收到来自于EBGP peer的一个update报文，如果该条路由的AS_PATH属性中的第一个AS号不是该EBGP peer所在的AS号，系统就拒绝该路由。默认情况下，该命令是打开的。
neighbor ip-address next-hop-self 当BGP路由器通过EBGP得到路由，并且这些路由需要广播给一个IBGP邻居时，发送的下一跳信息并不改变。使用这个命令，BGP路由器可以改变发送给IBGP对等体的下一条信息，把自己作为下一跳的路由器。
bgp always-compare-med 用于最优路由选择。在最优路由选择过程中，系统只对来自相同自治系统的路由的MED值进行比较，但是这种比较不是必须的，如果要强制比较，可以使用bgp deterministic-med。默认情况下，BGP路由器不会比较来自不同AS的路由的MED值，这条命令强制BGP路由器对所有的路由的MED值进行比较，而不管它们是否来自相同的自治系统。
bgp deterministic-med 用于最优路由选择。强迫BGP路由器对来自相同自治系统的路由的MED值进行确定性比较。默认情况下，如果没有配置该命令，系统不会强制对来自相同自治系统的路由的MED值进行比较。
bgp bestpath med missing-as-worst 使用该命令表示当BGP路由器收到一个未带MED属性的路由时，会将该路由的MED值设为一个无穷大的数4294967294。默认情况下，当系统接收到未带MED属性的路由时，会将该路由的MED值设为0。
bgp default local-preference number 用于最优路径选择。改变默认的本地优先级。在未打开该命令之前，系统默认的本地优先级为100。本地优先级属性用于IBGP peer之间，具有较高本地优先级的路由优先。
2.2 BGP报文格式
2.2.1 报文头格式
BGP报文的最大尺寸是4096字节，最小尺寸是19字节。所有的BGP报文都有一个通用的报文头，如图2-1所示，BGP报文头由16字节的标志域、2字节的长度域和1字节的类型域组成。根据报文类型的不同，报文头后面可以携带不同类型的数据信息[20]。
图2-1 BGP报文头格式
标志域：16字节，用来检测接收的BGP报文以及BGP对等体间同步的丢失。如果报文类型是OPEN，则标志域必须全为1；如果OPEN报文不携带验证信息，则随后的其他报文的标志域必须为全为1。否则随后的其他报文的标志域的值可以通过验证算法计算求得。
长度：2字节，以字节为单位的报文的长度，其中包含报文头的长度。
类型：1字节，OPEN、UPDATE、NOTIFICATION、KEEPALIVE对应的类型值分别为1、2、3、4。
2.2.2 OPEN报文格式
OPEN报文是BGP对等体间TCP连接建立后双方发送的第一个报文。OPEN报文被接受后发送KEEPALIVE报文以确认OPEN报文。OPEN报文一旦确认，UPDATE、KEEPALIVE和NOTIFICATION报文才开始交换。图2-2为OPEN报文格式。
图2-2 OPEN报文格式
版本：1字节，表示发送者运行的BGP版本。
我的自治系统：2字节，表示发送者的AS号。
保持时间：2字节，发送者建议的以秒为单位的保持计时器的值。接收方收到的OPEN报文中的保持时间与自己所配置的保持时间相比较，较小的值作为本地保持计时器的值。保持时间为两个相继的KEEPALIVE或/和UPDATE报文间的以秒为单位的最大值。保持计时器超时就认为该对等体连接中断。保持时间为0秒或者至少为3秒，为0秒时表示保持计时器永远不会超时，系统使用的默认值为180秒。
BGP ID：4字节，发送者的路由器ID。默认情况下，如果配置了loopback接口，路由器ID为loopback接口中的最高的IP地址，如果没有配置loopback接口，路由器ID为所有物理接口中最高的IP地址。
可选参数长度：1字节，指示接下来可选参数域的整体长度，用字节来表示。如果该值为0，表示无可选参数。
可选参数：由若干个三元组<参数类型、参数长度、参数值>组成，长度分别为1字节、1字节、可变长度。
2.2.3 UPDATE报文格式
UPDATE报文是BGP最重要的一种报文，也是最复杂的报文，它携带了Internet的路由可达信息。正是通过UPDATE报文，BGP形成了关于整个Internet的无循环的拓扑视图。UPDATE报文主要由网络层可达信息NLRI、路径属性、不可达路由三部分组成。UPDATE报文格式如图2-3所示。
图2-3 UPDATE报文格式
不可达路由长度：2字节，以字节为单位的撤销路由域的长度，0表示无撤销路由，并且在该消息中不包含撤销路由域。
撤销路由：变长，是需要撤销的路由的一个列表，由一系列<长度、前缀>二元组组成。长度占1个字节，表示以比特为单位的被撤销路由的IP地址前缀的长度，如果该值为0，表示前缀与所有的路由匹配。通过给前缀填充一些尾比特来保证该字段长度以字节为单位，尾比特的值任意，一般置零。
总路径属性长度：2字节，以字节为单位的路径属性域的长度，0表示在这个消息中不包含属性和NLRI。
路径属性：变长，列出了与NLRI相关的属性。由一系列<属性类型、属性长度、属性值>三元组组成，如图2-4所示。P比特位用来表示可选过渡属性是完整的还是不完整的。对于公认属性或者可选非过渡属性来说，P比特位值为0。表2-2给出了常见的属性类型码以及每个属性类型可能的属性值。
图2-4 BGP路径属性及属性类型格式
表2-2 属性类型和相关的属性值
属性名称 属性类型码 属性值码 属性值
ORIGIN 1 0 IGP
1 EGP
2 INCOMPLETE
AS_PATH 2 1 AS_SET
2 AS_SEQUENCE
NEXT_HOP 3 0 下一跳的IP地址
MULTI_EXIT_DISC 4 0 4字节MED值
LOCAL_PREF 5 0 4字节LOCAL_PREF值
ATOMIC_AGGREGATE 6 0 没有
AGGREGATOR 7 0 聚合体的AS号和IP地址
网络层可达信息：变长，由一系列<长度、前缀>二元组组成。其中，长度占1个字节，表示以比特为单位的NLRI的IP地址前缀的长度，如果该值为0，表示前缀与所有的路由匹配。通过给前缀填充一些尾比特来保证该字段长度以字节为单位，尾比特的值任意，一般置零。
2.2.4 KEEPALIVE报文格式
BGP相邻对等体间周期性地交换KEEPALIVE报文，并据此来判断远端对等体是否可达。KEEPALIVE报文发送间隔建议为保持时间的1/3，默认值为60秒，但是该时间段不能低于1秒。如果保持时间为0，则无须周期性地发送KEEPALIVE报文。KEEPALIVE报文只有19字节的报头信息，后面没有任何数据。
2.2.5 NOTIFICATION报文格式
在BGP协议中，每当检测到一个错误，总要发送一个NOTIFICATION报文，然后关闭相关的对等体连接。NOTIFICATION报文包括错误码、错误子码、数据三个域，如图2-5所示。
图2-5 NOTIFICATION报文格式
在NOTIFICATION报文中，错误码表示当前错误的类型，错误子码则提供了更详细的错误信息，数据域则是与当前错误相关的具体数据，可以用于诊断出错信息。RFC1771中定义了6种错误码和20种错误子码，如表2-3所示。
错误码：1字节，指示错误的类型。
错误子码：1字节，提供有关错误的更详细的信息。
数据：变长，用来诊断错误的原因。数据域的内容取决于错误码和错误子码。
表2-3 BGP错误码及错误子码
错误名称 错误码 错误子码 错误子码的详细内容
报文头错误 1 1 连接不同步
2 报文长度无效
3 报文类型无效
OPEN报文错误 2 1 不支持的版本号
2 无效的对等体AS
3 无效的BGP ID
4 不支持的可选参数
5 鉴别失败
6 不可接受的保持时间
UPDATE报文错误 3 1 畸形的属性列表
2 不可识别的公认属性
3 公认属性丢失
4 属性标志错误
5 属性长度错误
6 ORIGIN属性无效
7 AS路由环路
8 NEXT_HOP属性无效
9 可选属性错误
10 网络字段无效
11 畸形的AS_PATH属性
保持计时器超时 4 0 无
有限状态机错误 5 0 无
终止 6 0 无
2.3 BGP路径属性
路径属性是一条BGP路由的特定属性信息，它准确描述了一条BGP路由，路径属性是用于BGP路由决策的主要参数。路径属性可以分为4大类：公认必遵、公认自决、可选过渡、可选非过渡。表2-4列出了各个路径属性所属的类别。
公认必遵：UPDATE报文中NLRI路由必须携带的属性。所有的BGP路由器都必须能够识别和处理该属性。公认必遵属性丢失，表示发生错误。
公认自决：所有的BGP路由器都必须能够识别该属性，但不要求必须出现在UPDATE报文NLRI的属性字段中。
可选过渡：不要求所有的BGP路由器必须能够识别该属性。如果不能识别，BGP路由器应该接受该属性，并传递给其他BGP对等体。
可选非过渡：不要求所有的BGP路由器必须必须能够识别该属性。如果不能识别，BGP路由器应该忽略该属性，不再传递给其他BGP对等体。 表2-4 BGP路径属性
属性名称 属性类别
ORIGIN 公认必遵
AS_PATH 公认必遵
NEXT_HOP 公认必遵
MULTI_EXIT_DISC 可选非过渡
LOCAL_PREF 公认自决
ATOMIC_AGGREGATE 公认自决
AGGREGATOR 可选过渡
2.3.1 ORIGIN属性
ORIGIN属性是一个公认必遵属性，它指明了BGP路由信息的来源。ORIGIN属性由产生该BGP路由的AS指定，在传递过程中一般不会变化。当BGP有多条路由时，它会将ORIGIN属性作为最优路由选择的一个因素。它规定了下面几种源：
1) IGP：通过network命令或从发起者AS的一个内部协议学习到的路由就具有此属性。
2) EGP：从EGP学习到的路由具有此属性。
3) INCOMPLETE：通过其它手段学习到的路由具有此属性，例如使用聚合操作所产生的路由。INCOMPLETE属性并不代表路由有故障，只代表路由来源的信息不完整。BGP通过重分配学习到的路由会携带INCOMPLETE属性，因为在这种情况下无法决定路由的初始源。
2.3.2 AS_PATH属性
AS_PATH是一个公认必遵属性，这个属性指出了到达该目的网络所要经过的一系列自治系统的自治系统号，它有两种排列方式：AS_SET 和AS_SEQUENCE。当一个BGP speaker通过UPDATE报文转发一条BGP路由时候，它根据以下规则修改路由信息的AS_PATH属性：
1. 当通告一条路由给internal peer时，不修改AS_PATH属性；
2. 当通告一条路由给external peer时，按下面情况进行：
1) 如果当前AS_PATH属性的第一个段是AS_SEQUENCE，就把自己当前所处的自治系统号做为最后一个元素放到这个队列里面（默认情况下是在最左边）。如果这个动作导致AS＿PATH段的溢出，则新增加一个AS_SEQUENCE段，并把自己做在的自制系统号放在里面；
2) 如果当前AS_PATH属性的第一个段的类型为AS_SET，则新增一AS_SEQUENCE段，并把当前所处的自制系统号添加进去；
3) 如果当前AS_PATH属性为空，则新增一个AS_SEQUENCE段，并把当前所处的自制系统号添加进去。
AS_PATH属性的另一个功能就是避免路由环路。如果BGP路由器从它的外部对端收到一条路由，而AS_PATH包含这个BGP路由器自己的AS号，于是该路由器就知道这是条环路路由，从而将这样的路由丢弃掉。
2.3.3 NEXT_HOP属性
NEXT_HOP是一个公认必遵属性，它指明了到达目的地网络的下一跳路由器的IP地址。NEXT_HOP的取值要遵循如下规则：
1) 如果正在进行路由宣告的路由器和接收的路由器在不同的AS内（外部对等体），NEXT_HOP是正在宣告的路由器接口的IP地址。
2) 如果正在进行路由宣告的路由器和接收的路由器在同一个AS内（内部对等体），并且UPDATE报文的NLRI指明的目的网络也在同一个AS内，那么NEXT_HOP就是正在宣告的路由器接口的IP地址。
3) 如果正在进行路由宣告的路由器和接收的路由器在同一个AS内（内部对等体），并且UPDATE报文的NLRI指明的目的网络在不同AS内，则NEXT_HOP就是学习到该路由的外部路由器接口的IP地址。
图2-6说明了第一条规则。如图所示，R1和R2路由器在不同的AS内。R1向R2宣告一条路由192.212.1.0/24，因为R1和R2之间是EBGP的关系，所以这条路由的NEXT_HOP就是R1的IP地址192.168.5.1。
图2-6 NEXT_HOP规则一
图2-7说明了第二条规则。R1和R3在同一个AS内，同时R1向R3宣告的BGP路由192.212.1.0/24也在本AS内，所以这条路由的NEXT_HOP就是发起者R1的IP地址172.18.211.1。R1和R3之间是IBGP的关系，由于它们之间没有直接物理连接，而是通过IGP建立的TCP连接。为了发送数据包到宣告的目的地，接收路由器必须执行一个循环路由查找过程。首先，它要查找目的网络192.212.1.0/24，在BGP路由表中发现，下一跳为172.18.211.1。但是该IP地址不属于与子网相连的路由器中的任何一个，路由器必须查找到达172.18.211.1的路由。这条路由是通过IGP学到的，在IGP路由表中查到下一跳为172.18.10.1。
图2-7 NEXT_HOP规则二
图2-8说明了第三条规则。如图所示，R2通过IBGP向R4宣告一条路由192.212.1.0/24，由于该路由不在本AS内，则该路由的NEXT_HOP属性就是学习到该路由的外部对等体的IP地址，即R1的IP地址192.168.5.1。
图2-8 NEXT_HOP规则三
2.3.4 MULTI_EXIT_DISC属性
MULTI_EXIT_DISC属性简称为MED属性，属于可选非过渡属性，它类似于IGP中的度量值。当到达某AS有多条路径时，MED用来提示远端对等体如何进行优先选路。MED值越低，路由优先级越高。
MED属性在AS之间进行传递，MED属性一旦进入一个AS，就不再离开该AS。通常，路由器只比较来自于同一AS的EBGP对等体的路由的MED属性值，因为BGP认为来自不同AS的MED属性值是不具有可比性的。可以通过命令bgp always-compare-med使BGP比较来自不同AS的路由的MED属性。
2.3.5 LOCAL_PREF属性
LOCAL_PREF属性属于公认自决属性，与MED属性不同的是，LOCAL_PREF属性值由本地指定，而不是由邻居对等体指定。LOCAL_PREF值越大，路由优先级越高。
LOCAL_PREF属性在IBGP对等体间传递，不会传送到EBGP对等体中。如果一个在AS内部运行BGP的路由器收到了到一个目的地的多条路由，它将这些路由的LOCAL_PREF属性值进行比较，选择具有最高的LOCAL_PREF的路由。
图2-9显示了如何使用LOCAL_PREF属性。AS 300从两个ISP获得路由。但是ISP1为首选服务提供商。连接到ISP1的路由器宣告路由的LOCAL_PREF为200，连接到ISP2的路由器宣告路由的LOCAL_PREF为100。所有的AS 300内部的对等体，包括连接到ISP2的路由器，对于同一目的路由，更优先选用从ISP1学到的路由。
图2-9 根据LOCAL_PREF选择路由
2.3.6 ATOMIC_AGGREGATE属性
ATOMIC_AGGREGATE属性属于公认自决属性。当BGP选择通告一条聚合路由时，需要为路由添加ATOMIC_AGGREGATE属性，这些路由在继续传递过程中要保持原子聚合属性和聚合特性。在路由聚合时，会丢失一些路由信息，而且路由会变得不太准确。当在一个运行BGP的路由器中执行聚合时，所丢失的信息是路径的细节。
ATOMIC_AGGREGATE用来警告下游路由器出现了路径信息丢失。任何时候，当一个运行BGP的路由器将更具体的路由归纳为有较少细节的聚合路由，并且出现路径信息丢失时，运行BGP的路由器必须将ATOMIC_AGGREGATE属性附加到聚合路由中。任何一台运行BGP的下游路由器收到有ATOMIC_AGGREGATE属性的路由，不能使这条路由中的NLRI信息更详细。并且当把该路由宣告给其他对等体时，ATOMIC_AGGREGATE属性必须继续附加在该路由中。
2.3.7 AGGREGATOR属性
AGGREGATOR属性属于可选过渡属性，该属性由聚合路由器所属的AS号码和路由器ID组成，用以记录路由聚合信息。ATOMIC_AGGREGATE属性指示出现了路径信息的丢失，AGGREGATOR属性指示在哪个路由器上发生了聚合操作。
2.4 BGP决策过程
BGP路由信息库（RIB）包括3个部分：
1) 输入路由表（Adj-RIBs-In）：BGP通过IBGP或EBGP从远端对等体接收路由，并将这些路由不加修改地存储到输入路由表中。
2) 本地路由表（Loc-RIB）：该路由表用于存储使用本地路由策略而选出的最佳路由。经过判决处理的路由是BGP协议认为的最佳路由，本地路由表中的路由是输出路由表中路由信息的来源。
3) 输出路由表（Adj-RIBs-Out）：存储发送到远端对等体的路由信息。
BGP决策过程是通过对Adj-RIBs-In表中的路由使用本地路由策略，同时将选定的或者修改过的路由放到Loc-RIB表和Adj-RIBs-Out中而选择路由。这个决策的过程需要3个步骤：
步骤1，为每一条可用路由计算首选等级。只要是BGP路由器接收到的BGP UPDATE报文中含有新的路由、发生变化的路由或者撤销的路由，就需要调用该步骤。对每条路由都要分开考虑，得到一个非负整数指示该路由的首选级别。
步骤2，从到达特定目的地的所有可用路由中选取最好的路由。并把这些路由放到Loc-RIB表中。只有步骤1完成以后才调用该步骤。
步骤3，将合适的路由放到Adj-RIBs-Out表中，用于向BGP对等体宣告，只有在步骤2完成，并且Loc-RIB表发生变化后才调用该步骤。路由聚合等操作就在该步骤进行。
除非一个路由策略有特殊说明，否则第2步通常会在到达一个特定目的地的所有可用的路由中选取最具体的路由。如果路由的NEXT_HOP属性所指明的地址是不可达的，就不会选择该路由。
当到达同一目的地的路由有多条时，BGP路由器需要使用本地路由策略选择最优的路由，该策略主要是根据BGP路由的属性进行处理的，以下是本地路由策略使用的准则[21]：
1) 优选weight权重最大的路由；
2) 优选具有最高LOCAL_PREF值的路由；
3) 优选AS路径最短的路由；
4) 优选ORIGIN属性最小的路由，IGP小于EGP，EGP小于Incomplete；
5) 优选MED值最小的路由；
6) 优选来自于EBGP对等体的路由，其次是IBGP路由；
7) 优选路由始发者ID最小的路由。
8) 优选来自较小IP地址的BGP邻居的路由
第3章 系统模块设计
3.1 系统体系结构
系统是由两个子系统构成，一个是BGP子系统，专门负责BGP协议相关的操作；另一个是RMer系统，该子系统负责与BGP系统的通信，以及与Linux内核间的通信。图3-1描述了系统体系结构，从图中可以看出，BGP子系统没有直接和Linux内核通信，而是通过RMer子系统来读写Linux内核路由表的。RMer子系统和BGP子系统之间建立socket[22]连接，通过RMER报文进行通信。BGP子系统和RMer子系统共同使用VTY模块来进行人机交互，VTY模块接收用户输入的CLI[48]命令行，同时向用户反馈信息。BGP有限状态机、路由管理策略和报文处理单元是BGP系统中的几个关键模块，它们分别负责状态机的运行、BGP路由表的管理、BGP报文的处理。
图3-1 系统体系结构图
系统中使用的是基于TCP连接的通信。BGP系统有两种方式与远端的BGP邻居建立TCP连接，一种是以客户端的身份主动向邻居的TCP179号端口发起连接请求，另一种是使用TCP179号端口，以服务器的身份等待远端邻居的连接请求。VTY模块使用TCP2501号端口，以服务器的身份等待来自用户的连接请求。BGP系统和RMer系统之间建立的是基于本地的TCP连接，使用的是AF_UNIX[23]类型的socket，而VTY模块和BGP系统使用的是基于AF_INET[23]类型的socket。
本文采用了开源路由软件zebra[24]中的thread机制。图3-2描述了BGP的thread系统结构。BGP系统中有6种类型的thread，包括timer thread、read thread、write thread、event thread、ready thread和unused thread。所有的这些thread都会由一个thread管理者集中进行管理。BGP系统会创建一个read thread和一个write thread。前者用于从RMer接收数据，后者用于向RMer发送数据。当RMer系统和BGP系统之间建立socket连接后，RMer会通过该socket将自己从Linux内核中获取的interface信息发给BGP系统，当有数据到达时，BGP系统会从该socket中读取并处理数据。
图3-2 Thread系统结构图
BGP状态机维护BGP peer之间的各种连接状态以及状态机事件。状态机初始为Idle状态，start状态机事件触发状态机启动运行。经过一系列的状态转换，最终到达了Established状态。在Established状态下，BGP peer之间可以进行交换BGP路由信息。BGP系统使用read thread读取来自BGP peer的数据，交给BGP 路由管理模块进行处理，决定是否对BGP RIB添加或删除某条路由。BGP系统会使用write thread将BGP 路由管理模块选择出的最优路由写入BGP系统和RMer系统建立的socket中，将BGP路由通告给RMer系统。
图3-3为系统流程图，首先系统进行初始化工作，对相关的变量进行初始化，其次RMer系统向Linux内核获取interface相关的信息以及内核路由表，接着系统读取路由器的初始配置信息，对路由器进行初始配置。在执行thread_fetch函数查找就绪thread之前，系统要创建local server、local client、VTY server和BGP server。local server阻塞在处理函数为rmer_accept的read thread上，local client阻塞在处理函数为rclient_connect的event thread上，VTY server阻塞在处理函数为vty_accept的read thread上，BGP server阻塞在处理函数为bgp_accept的read thread上。
图3-3 总系统流程图
当这4个thread创建完毕后，系统调用thread_fetch函数监控各个thread，一旦有thread就绪，就让该thread得到执行。当local server和local client间的TCP连接建立成功后，local server创建一个处理函数为rmer_client_read的read thread用于读取来自local client的数据；local client创建一个处理函数为rclient_read的read thread用于读取来自local server的数据，同时local client向local server发送INTERFACE_ADD和REDISTRIBUTE_ADD报文，发送INTERFACE_ADD报文的目的是向RMer索取内核的interface信息，发送REDISTRIBUTE_ADD报文的目的是把BGP路由通告给RMer。当VTY server和VTY client间的TCP连接建立成功后，VTY server会创建两个thread，一个是处理函数为vty_read的read thread用于接收和响应VTY client输入的CLI命令，另一个是处理函数为vty_flush的write thread用于向VTY client输出信息。当BGP server和BGP client间的TCP连接建立成功后，BGP server会创建一个处理函数为bgp_event的event thread用于运行BGP状态机。
3.2 CLI模块
CLI模块主要是用于处理用户输入的CLI命令，所有的CLI命令会被存放在系统定义的容器cmdvec中。容器结构体是系统中存储数据的基本单位，可以存放任何类型的数据。下面给出容器相关的数据结构。
struct _vector
{
unsigned int max; //正在被使用的块的个数
unsigned int alloced; //容器总共分配的块的个数
void **index; //可以当作是一个数组，数组成员是任何类型数据的首地址
};
typedef struct _vector *vector;
vector cmdvec;
cmdvec是一个存放CLI节点的容器，CLI节点采用数据结构struct cmd_node来表示，该数据结构中包含CLI节点的类型、CLI节点提示符和CLI部件。其中CLI部件使用cmd_vector进行存储。下面给出数据结构struct cmd_node对应的源代码。
struct cmd_node
{
enum node_type node; //CLI节点的类型
char *prompt; //CLI节点提示符
vector cmd_vector; //该容器里面存放的是该CLI命令对应的字符串
};
struct cmd_node enable_node =
{
ENABLE_NODE,
"%s# ",
};
enum node_type
{
……
VIEW_NODE //VIEW类型节点
ENABLE_NODE, //ENABLE类型节点
CONFIG_NODE, //CONFIG类型节点
……
}
例如ENABLE_NODE类型的CLI节点，当进入enable模式后，提示符变为“hostname#”，此时输入“show”命令，就会调用“show”命令对应的处理函数，显示系统所有的命令。每一种类型的CLI节点中有一个容器cmd_vector，该容器中可以存放众多的同一类型的CLI部件，CLI部件使用数据结构struct cmd_element来表示。
struct cmd_element
{
char *string; //CLI命令模板，表示用户输入的命令必须遵循此格式
int (*func) (struct cmd_element *, struct vty *, int, char **); //CLI命令处理函数
char *doc; //对该CLI命令的一个文字性描述
vector strvec; //将string和doc中的内容用desc结构表示，存在strvec中
int cmdsize; //容器strvec中元素的个数
char *config; //配置字符串
vector subconfig; //配置字符串的各个子字符串
};
struct desc
{
char *cmd; //CLI命令字符串中的一个子字符串
char *str; //该CLI子字符串对应的文字性描述
};
struct cmd_element show_version_cmd =
{
"show version",
show_version,
"Show running system information\n"
"Displays RMer version\n"
};
为了便于理解，以“show version”这个CLI命令为例，string中有两个CLI子字符串，一个是“show”，对应的文字性描述为“Show running system information\n”，另一个是“version”，对应的文字性描述为“Displays RMer version\n”。 show_version是一个该CLI命令对应的处理函数。
图3-4以VIEW类型CLI节点下的“show version”命令为例，描述了CLI模块的组织结构。cmdvec是全局的容器，存放的数据结构为struct cmd_node的CLI节点，采用CLI节点类型作为索引。view_node节点中的cmd_vector容器中存放的是数据结构为struct cmd_element的CLI部件。show_version_cmd中的strvec容器中存放的是descvec容器，descvec容器中有且仅有一个struct desc类型元素。
图3-4 CLI模块结构图
3.3 Thread管理机制
总系统中使用6种类型的thread，与这6种类型thread相对应的是6种类型的thread队列：read队列、write队列、timer队列、event队列、ready队列、unused队列。每一种队列只能存放相应类型的thread。event队列中的thread会立即得到执行，当event队列中的thread全部执行完以后，系统会从ready队列中选择thread执行，read队列, write队列和timer队列中的thread必须进入ready队列以后才有机会得到执行。
#define THREAD_READ 0
//当对文件描述符执行读操作时，会触发该类型thread进入ready队列
#define THREAD_WRITE 1
//当对文件描述符执行写操作时，会触发该类型thread进入ready队列
#define THREAD_TIMER 2
//当设置的时间到达时，会触发该类型thread进入ready队列
#define THREAD_EVENT 3
//该类型thread用于执行一个事件，该事件可以立即得到执行
#define THREAD_READY 4
//处于ready状态的thread，从ready队列头开始依次执行
#define THREAD_UNUSED 5 //空闲的thread
在数据结构struct thread中，func是函数指针，指向thread的处理函数，arg和val分别表示处理函数的第一个和第二个变量，fd表示thread是对哪个文件描述符进行操作，sands变量是定时器，只有在timer thread中才会用到，表示当系统时间大于或等于sands时该timer thread会进入ready队列，准备执行。
struct thread
{ unsigned long id; //thread的ID号
unsigned char type; //thread的类型
struct thread *next; //指向下一个thread
struct thread *prev; //指向前一个thread
struct thread_master *master; //指向该thread的master
int (*func) (struct thread *); //thread处理函数
void *arg; //处理函数的第一个变量
union {
int val; //处理函数的第二个变量
int fd; //文件描述符
struct timeval sands; //时间戳变量
} u;
};
系统中使用thread master管理这6种类型的所有thread，struct thread_master数据结构中有6个thread队列，3个文件描述符集，以及一个thread计数器alloc组成。队列是采用thread_list类型的链表结构。
struct thread_master
{
struct thread_list read;
struct thread_list write;
struct thread_list timer;
struct thread_list event;
struct thread_list ready;
struct thread_list unuse;
fd_set readfd;
fd_set writefd;
fd_set exceptfd;
unsigned long alloc;
};
struct thread_list
{
struct thread *head;
struct thread *tail;
int count;
};
在系统的6种类型thread中，read thread、write thread、timer thread、event thread是由系统直接创建产生的，ready thread和unused thread是由状态转换而产生的，并非由系统直接创建产生。
一个新的thread可以通过调用如下4个函数产生，调用哪个函数，取决于需要创建的thread的类型：
1， thread_add_read：添加一个read thread到read队列，该thread负责从socket中读取数据。
2， thread_add_write：添加一个write thread到write队列，该thread负责向socket中写数据。
3， thread_add_timer：添加一个timer thread到timer队列，该thread负责定时一个timer事件，当时间到达时，该thread会自动被调用。
4， thread_add_event：添加一个event thread到event队列，该thread被添加后会立即得到执行。
thread_add_read函数的源代码如下所示：
struct thread *thread_add_read (struct thread_master *m,
int (*func)(struct thread *),
void *arg,
int fd)
{
struct thread *thread;
if (FD_ISSET (fd, &m->readfd)) /*如果该描述符已经被设置，return*/
{
rlog (NULL, LOG_WARNING, "There is already read fd [%d]", fd);
return NULL;
}
thread = thread_new (m);
thread->type = THREAD_READ;
thread->id = 0;
thread->master = m;
thread->func = func;
thread->arg = arg;
FD_SET (fd, &m->readfd); /*根据fd，设置master的读描述符集*/
thread->u.fd = fd;
thread_list_add (&m->read, thread);
return thread;
}
thread_add_write函数的源代码如下所示：
struct thread *thread_add_write (struct thread_master *m,
int (*func)(struct thread *),
void *arg,
int fd)
{
struct thread *thread;
if (FD_ISSET (fd, &m->writefd)) /*如果该描述符已经被设置，return。*/
{
rlog (NULL, LOG_WARNING, "There is already write fd [%d]", fd);
return NULL;
}
thread = thread_new (m);
thread->type = THREAD_WRITE;
thread->id = 0;
thread->master = m;
thread->func = func;
thread->arg = arg;
FD_SET (fd, &m->writefd);
thread->u.fd = fd;
thread_list_add (&m->write, thread);
return thread;
}
thread_add_timer函数的源代码如下所示：
struct thread *thread_add_timer (struct thread_master *m,
int (*func)(struct thread *),
void *arg,
long timer)
{
struct timeval timer_now;
struct thread *thread;
struct thread *tt;
thread = thread_new (m);
thread->type = THREAD_TIMER;
thread->id = 0;
thread->master = m;
thread->func = func;
thread->arg = arg;
gettimeofday (&timer_now, NULL);
timer_now.tv_sec += timer;
thread->u.sands = timer_now;
for (tt = m->timer.head; tt; tt = tt->next) /*寻找合适的插入点*/
if (thread_timer_cmp (thread->u.sands, tt->u.sands) <= 0)
break;
if (tt)
thread_list_add_before (&m->timer, tt, thread);
else thread_list_add (&m->timer, thread);
return thread;
}
thread_add_event函数的源代码如下所示：
struct thread *thread_add_event (struct thread_master *m,
int (*func)(struct thread *),
void *arg,
int val)
{
struct thread *thread;
thread = thread_new (m);
thread->type = THREAD_EVENT;
thread->id = 0;
thread->master = m;
thread->func = func;
thread->arg = arg;
thread->u.val = val;
thread_list_add (&m->event, thread);
return thread;
}
图3-5 thread的处理流程
在主函数中，系统会通过while循环，一直调用thread_fetch函数取出准备就绪的thread，然后该thread对应的处理函数。图3-5描述了thread在系统中所经过的处理流程。thread_fetch函数的流程图如图3-6所示，其源代码如下。
struct thread *thread_fetch (struct thread_master *m, struct thread *fetch)
{
int ret;
struct thread *thread;
fd_set readfd, writefd, exceptfd;
struct timeval timer_now;
struct timeval timer_min;
struct timeval *timer_wait;
retry:
/*从event队列中选择event thread进行调度*/
while ((thread = thread_trim_head (&m->event)))
{
*fetch = *thread;
thread->type = THREAD_UNUSED;
thread_add_unuse (m, thread);
return fetch;
}
/*从ready队列中选择thread进行调度*/
while ((thread = thread_trim_head (&m->ready)))
{
*fetch = *thread;
thread->type = THREAD_UNUSED;
thread_add_unuse (m, thread);
return fetch;
}
/*从timer队列中选择thread进行调度*/
if (m->timer.head)
{
gettimeofday (&timer_now, NULL);
timer_min = m->timer.head->u.sands;
timer_min = thread_timer_sub (timer_min, timer_now);
if (timer_min.tv_sec < 0)
{
timer_min.tv_sec = 0;
timer_min.tv_usec = 10;
}
timer_wait = &timer_min; /*timer队列首的timer thread即将被调度的剩余时间*/
}
else
{
timer_wait = NULL; /*timer队列中无timer thread*/
}
readfd = m->readfd;
writefd = m->writefd;
exceptfd = m->exceptfd;
/*select监听master的读写描述符集，timer_wait为超时值*/
ret = select (FD_SETSIZE, &readfd, &writefd, &exceptfd, timer_wait);
if (ret < 0)
goto retry;
/*接下来判断是哪一个描述符发生变化或者超时引起引起select函数从阻塞中退出的?，注意，发生改变的描述符仍然处于SET的状态，未发生改变的描述符已经被CLR掉了。*/
/*首先判断是否有read thread的fd发生变化*/
thread = m->read.head;
while (thread)
{
struct thread *t;
t = thread;
thread = t->next;
/*如果该read thread的fd发生变化了，让其进入ready队列*/
if (FD_ISSET (t->u.fd, &readfd))
{
FD_CLR(t->u.fd, &m->readfd);
thread_list_delete (&m->read, t);
thread_list_add (&m->ready, t);
t->type = THREAD_READY;
}
}
/*其次判断是否有write thread的fd发生变化*/
thread = m->write.head;
while (thread)
{
struct thread *t;
t = thread;
thread = t->next;
if (FD_ISSET (t->u.fd, &writefd))
{
FD_CLR(t->u.fd, &m->writefd);
thread_list_delete (&m->write, t);
thread_list_add (&m->ready, t);
t->type = THREAD_READY;
}
}
/*最后判断是否有timer thread发生超时*/
gettimeofday (&timer_now, NULL);
thread = m->timer.head;
while (thread)
{
struct thread *t;
t = thread;
thread = t->next;
if (thread_timer_cmp (timer_now, t->u.sands) >= 0)
{
thread_list_delete (&m->timer, t);
thread_list_add (&m->ready, t);
t->type = THREAD_READY;
}
}
thread = thread_trim_head (&m->ready); /*从ready队列首取出一个thread进行调度*/
if (!thread) /*如果ready队列为空，重复执行该算法*/
goto retry;
*fetch = *thread;
thread->type = THREAD_UNUSED;
thread_add_unuse (m, thread);
return fetch;
}
图3-6 thread调度算法
3.4 VTY服务器
VTY服务器模块用于人机交互，接收和处理用户输入的CLI命令。系统中运行了VTY的服务器端程序，使用的TCP端口号为2501，用户通过VTY客户端程序和VTY服务器建立TCP连接。VTY服务器和VTY客户端之间的通信原理如图3-7所示。当用户通过telnet[25]登录到VTY server上以后，VTY server会阻塞在read( )[26]上，等待用户输入CLI命令。当用户输入命令并回车后，VTY server读取并判断CLI命令的有效性，如果有效，则调用相应的CLI命令处理函数，并通过write( ) [26]向用户返回结果或相关的提示信息。
图3-7 VTY客户端和服务器间的通信
VTY服务器程序是通过vty_server_start函数实现的，该函数的主要源代码如下。该函数被调用时，参数port取值为2501。源代码中使用thread_add_read函数添加一个处理函数为vty_accept的read thread，该thread用于接受来自VTY客户端的连接请求。
void vty_server_start (unsigned short port)
{
union sockunion su;
int accept_sock;
int on = 1;
memset (&su, 0, sizeof (union sockunion));
su.sin.sin_family = AF_INET;
su.sin.sin_port = htons(port);
su.sin.sin_addr.s_addr = htonl(INADDR_ANY);
/*创建socket*/
accept_sock = socket (AF_INET, SOCK_STREAM, 0);
/*设置socket 选项*/
setsockopt (accept_sock, SOL_SOCKET, SO_REUSEADDR, (void *) &on, sizeof (on));
bind (accept_sock, (struct sockaddr *)&su, sizeof (struct sockaddr_in)); /*bind操作*/
listen (accept_sock, 3);
/*添加一个处理函数为vty_accept 的read thread，监听来自其他VTY clinet的连接请求*/
thread_add_read (master, vty_accept, NULL, accept_sock);
}
vty_accept函数的主要源代码如下。其中vty_create函数用于创建一个新的VTY结构，同时该函数还会对socket进行读写操作，用于和VTY客户端进行数据通信。
int vty_accept (struct thread *thread)
{
union sockunion su;
int accept_sock,vty_sock;
accept_sock = thread->u.fd;
/*添加一个处理函数为vty_accept 的read thread，用于监听来自VTY clinet的连接请求*/
thread_add_read (master, vty_accept, NULL, accept_sock);
memset (&su, 0, sizeof (union sockunion));
vty_sock = accept (accept_sock, (struct sockaddr *)&su, &sizeof (union sockunion)); /*accept操作*/
/*根据新建立的TCP连接，专门创建一个VTY结构，用于和VTY client进行通信*/
vty_create (vty_sock, &su);
}
3.5 BGP路由器间通信
当本地的BGP路由器和远端的BGP路由器建立TCP连接后，本地的BGP路由器可能会有两种角色，一种是BGP服务器，另一种是客户端，所以在本系统中，BGP服务器和BGP客户端的功能都应该实现。当系统启动后，BGP服务器是一直运行着的，使用的TCP端口号为179，它等待着来自BGP客户端的连接请求。BGP客户端的程序是在BGP状态机的入口函数中启动的。BGP服务器和BGP客户端之间的通信原理如图3-8所示。当BGP服务器和BGP客户端建立TCP连接后，通过调用write和read函数发送和接受BGP报文。
图3-8 BGP客户端和服务器间的通信
BGP服务器程序是通过bgp_server_start函数实现的，该函数的主要源代码如下。该函数被调用时，参数port取值为179。源代码中使用thread_add_read函数添加一个处理函数为bgp_accept的read thread，该thread用于接受来自BGP客户端的连接请求。
void bgp_server_start (unsigned short port)
{
union sockunion su;
int accept_sock;
int on = 1;
memset (&su, 0, sizeof (union sockunion));
su.sin.sin_family = AF_INET;
su.sin.sin_port = htons(port);
su.sin.sin_addr.s_addr = htonl(INADDR_ANY);
accept_sock = socket (AF_INET, SOCK_STREAM, 0); /*创建socket*/
/*设置socket 选项*/
setsockopt (accept_sock, SOL_SOCKET, SO_REUSEADDR, (void *) &on, sizeof (on));
bind (accept_sock, (struct sockaddr *)&su, sizeof (struct sockaddr_in)); /*bind操作*/
listen (accept_sock, 3);
/*添加一个处理函数为bgp_accept 的read thread，用于监听来自BGP客户端的连接请求*/
thread_add_read (master, bgp_accept, NULL, accept_sock);
}
bgp_accept函数的主要源代码如下。当BGP服务器和BGP客户端TCP连接建立成功后，BGP服务器会专门创建一个peer用于和BGP客户端进行通信，同时将该peer转交给BGP状态机管理。
int bgp_accept (struct thread *thread)
{
int accept_sock,bgp_sock;
union sockunion su;
struct peer *peer;
struct peer *peer1;
char buf[SU_ADDRSTRLEN];
accept_sock = thread->u.fd;
/*添加一个处理函数为bgp_accept 的read thread，监听其他BGP客户端的连接请求*/
thread_add_read (master, bgp_accept, NULL, accept_sock);
memset (&su, 0, sizeof (union sockunion));
bgp _sock = accept (accept_sock, (struct sockaddr *)&su, &sizeof (union sockunion));
/* 根据BGP客户端的IP地址，检查其配置情况。如果没有配置neighbor命令创建peer，或者该BGP peer不是处于Active状态，建立的该TCP连接均无效*/
peer1 = peer_lookup_by_su (&su);
if (! peer1 || peer1->status == Idle) {
close (bgp_sock);
return -1;
}
/*如果建立的TCP连接有效，创建一个本地的peer，专门用于和BGP客户端的peer进行通信，本文中称该本地的peer为BGP local server peer，与其通信的另一端peer为BGP remote client peer。*/
peer = peer_new ();
listnode_add_sort (peer_list, peer);
SET_FLAG (peer->sflags, PEER_STATUS_ACCEPT_PEER);
peer->su = su;
peer->fd = bgp_sock;
peer->status = Active;
char buf[SU_ADDRSTRLEN + 1];
sockunion2str (&su, buf, SU_ADDRSTRLEN);
peer->host = strdup (buf); /*BGP remote peer的可打印IP地址*/
/*添加一个处理函数为bgp_event的event thread运行BGP FSM，当前状态为Active，状态机事件为TCP_connection_open*/
thread_add_event (master, bgp_event, peer, TCP_connection_open)；
return 0;
}
处于Idle状态的状态机接收到BGP_Start事件后调用事件处理函数，该函数会使BGP客户端向BGP服务器发出连接请求。bgp_start函数的主要源代码如下。首先调用bgp_client_start向BGP服务器发起连接请求，如果连接成功，就启动BGP状态机，处于Connect状态的状态机接收到TCP_connection_open事件；如果TCP连接正在建立中，bgp_start函数创建一个处理函数为bgp_read的read thread和一个处理函数为bgp_write的write thread，等待TCP连接的建立。
int bgp_start (struct peer *peer)
{
int status;
status = bgp_client_start(peer);
switch (status)
{
case -1: /*连接成功*/
thread_add_event (master, bgp_event, peer, TCP_connection_open_failed)；
break;
case 0: /*连接失败*/
thread_add_event (master, bgp_event, peer, TCP_connection_open)；
break;
case 1: /*连接进行中*/
BGP_READ_ON (peer->t_read, bgp_read, peer->fd); //等待TCP连接的建立
BGP_WRITE_ON (peer->t_write, bgp_write, peer->fd); //等待TCP连接的建立
break;
}
return 0;
}
BGP客户端程序是通过bgp_client_start函数实现的，相关的源代码如下。函数中使用的参数peer是用户通过输入neighbor remote-as命令后而创建的，称之为BGP local client peer，与之相对的远端路由器通过该CLI命令创建的peer，称之为BGP remote peer。
int bgp_client_start (struct peer *peer)
{
int ret;
on = 1;
peer->fd = socket (AF_INET, SOCK_STREAM, 0); /*创建socket*/
setsockopt (peer->fd, SOL_SOCKET, SO_REUSEADDR, (void *) &on, sizeof (on));
sockopt_reuseaddr (peer->fd);
/*将peer->fd设为非阻塞socket*/
fcntl (peer->fd, F_SETFL, fcntl (peer->fd, F_GETFL, 0)|O_NONBLOCK);
ret = connect (peer->fd, (struct sockaddr *) &peer->su, sizeof (struct sockaddr_in));
if (ret == 0) /*连接成功*/
{
fcntl (peer->fd, F_SETFL, val);
return 0;
}
if ((ret < 0) && (errno != EINPROGRESS)) /*连接失败*/
return -1;
/*连接进行中*/
fcntl (peer->fd, F_SETFL, val); /*将peer->fd恢复为原来的设置*/
return 1;
}