基于Linux系统的边界网关协议的设计与实现

基于Linux系统的边界网关协议的设计与实现
3.6 BGP和RMer系统间通信
RMer系统和BGP系统之间采用的是UNIX本地的服务器客户端模式进行通信，它们创建的socket的地址格式为AF_UNIX，表示用于UNIX本地的通信。RMer系统与BGP系统之间的通信原理如图3-9所示，因为它们之间使用的是本地客户端和服务器模式进行通信，故称RMer系统为local server端，BGP系统为local client端。当BGP服务器和BGP客户端建立TCP连接后，通过调用write和read函数发送和接受RMER报文。

图3-9 RMer和BGP之间的通信
local server程序是通过local_server_start函数实现的，该函数的主要源代码如下。该函数的参数path为local server和local client通信时使用的临时文件"/tmp/.rserv"，该文件为socket使用的通信管道。local_server_start函数最后调用thread_add_read函数添加了一个处理函数为rmer_accept的read thread，该thread用于监听来自local client端的连接请求。
void local_server_start (char *path)
{
  int ret;
  int accept_sock, len;
  struct sockaddr_un serv;
  mode_t old_mask;
  unlink (path);    /*删除path所指定的文件，断开和该文件关联的所有socket连接*/
/*设置系统当前的umask值为(0)&(0777)，用于设置新创建的文件的访问权限，返回值为系统原来的umask值，由old_mask保存*/
  old_mask = umask (0);
  accept_sock = socket (AF_UNIX, SOCK_STREAM, 0); /*创建一个UNIX domain socket*/
  memset (&serv, 0, sizeof (struct sockaddr_un));
  serv.sun_family = AF_UNIX;
  strncpy (serv.sun_path, path, strlen (path));
  len = sizeof (serv.sun_family) + strlen (serv.sun_path);
  bind (accept_sock, (struct sockaddr *) &serv, len); /*bind操作*/
  listen (accept_sock, 5);       /*listen操作*/
  umask (old_mask); /*恢复系统原来的umask值*/
/*添加一个处理函数为rmer_accept的read thread，监听来自local client端的连接请求*/
  thread_add_read (master, rmer_accept, NULL, accept_sock);
}
rmer_accept函数的主要源代码如下。当TCP连接建立成功后，local server会创建一个struct rserv结构的变量，专门用于和local client进行通信，其中包括读写RMER报文。
int rmer_accept (struct thread *thread)
{
  int accept_sock;
  int client_sock;
  struct sockaddr_in client;
  socklen_t len;
  accept_sock = thread->u.fd;
/*添加一个处理函数为rmer_accept的read thread，监听来自local client端的连接请求*/
  thread_add_read (master, rmer_accept, NULL, accept_sock);
  client_sock = accept (accept_sock, (struct sockaddr *) &client, &sizeof (struct sockaddr_in));
/*根据新建立的TCP连接，创建一个struct rserv结构的变量，负责和local client通信*/
  rmer_client_create (client_sock);
  return 0;
}
当TCP建立成功后，在local server端提供一个struct rserv结构的变量，在local client端提供一个struct rclient结构的变量，二者之间实现通信。相关的数据结构源代码如下。
struct rserv
{
  int sock;      /*local server用来和local client通信的socket*/
  struct stream *ibuf;    /*输入缓存*/
  struct stream *obuf;   /*输出缓存*/
struct thread *t_read;   /*read and write thread*/
  struct thread *t_write; 
  int rtm_table;           /*local client使用的默认路由表*/
  u_char redist[RMER_ROUTE_MAX];     /*重分配信息*/
  u_char redist_default;     
  u_char ifinfo;       /*interface信息*/
};

struct rclient
{
  int sock;  /*local client用来和local server通信的socket*//
  int enable; /*有效位*/
  int fail;   /*连接失败的次数*/
  struct stream *ibuf;    /*输入缓存*/
  struct stream *obuf;   /*输出缓存*/
  struct thread *t_read; /* read and connect thread. */
  struct thread *t_connect;
  u_char redist_default; /*重分配信息*/
  u_char redist[RMER_ROUTE_MAX];
  u_char default_information;
  /*报文处理函数*/
  int (*interface_add) (int, struct rclient *, rmer_size_t);
  int (*interface_delete) (int, struct rclient *, rmer_size_t);
  int (*interface_up) (int, struct rclient *, rmer_size_t);
  int (*interface_down) (int, struct rclient *, rmer_size_t);
  int (*interface_address_add) (int, struct rclient *, rmer_size_t);
  int (*interface_address_delete) (int, struct rclient *, rmer_size_t);
  int (*ipv4_route_add) (int, struct rclient *, rmer_size_t);
  int (*ipv4_route_delete) (int, struct rclient *, rmer_size_t);
};
local client程序是通过local_client_start函数实现的，该函数的主要源代码如下。该函数中rclient所指向的结构是local client程序初始化时创建的，用于和local server进行通信。TCP连接建立成功后，local client调用thread_add_read添加了一个处理函数为rclient_read的read thread用于读取来自local server的RMER报文。

int local_client_start(struct thread *thread)
{
  struct rclient *rclient;
int sock, len, i;
struct sockaddr_un addr;
  rclient = thread->arg;
  rclient->t_connect = NULL;
/*如果已经连接成功了，return*/
if (rclient->sock >= 0)  
{
  return 0;
}
rclient->sock = socket (AF_UNIX, SOCK_STREAM, 0);
memset (&addr, 0, sizeof (struct sockaddr_un));
addr.sun_family = AF_UNIX;
strncpy (addr.sun_path, path, strlen (path));
len = sizeof (addr.sun_family) + strlen (addr.sun_path);
connect (rclient->sock, (struct sockaddr *) &addr, len);
/*如果连接失败了，重新尝试连接*/
if (rclient->sock < 0)  
{
rclient->fail++;
rclient_event (RCLIENT_CONNECT, rclient);
return -1;
}
/*连接成功，失败次数清零*/
rclient->fail = 0;   
rclient->t_read = thread_add_read (master, rclient_read, rclient, rclient->sock);
/*BGP向RMer请求interface信息*/
rmer_message_send (rclient, RMER_INTERFACE_ADD);
  /*把BGP路由发送给RMer系统*/
for (i = 0; i < RMER_ROUTE_MAX; i++)
  if (i != rclient->redist_default && rclient->redist[i])
rmer_redistribute_send (RMER_REDISTRIBUTE_ADD, rclient->sock, i);
  return 0;
}
RMer系统和BGP系统之间通信所使用的报文称之为RMER报文。RMER报文是由报文头和报文体组成，报文头格式如图3-10所示。其中长度域占2个字节，表示包含报文头在内的整个RMER报文的长度，类型域占1个字节，表示该RMER报文的类型，类型共有11种，如表3-1所示。
       
图3-10 RMER报文头格式

表3-1 RMER报文类型
RMER报文类型 说明
INTERFACE_ADD 添加一个网络接口
INTERFACE_DELETE 删除一个网络接口
INTERFACE_ADDRESS_ADD 添加网络接口的IP地址
INTERFACE_ADDRESS_DELETE 删除网络接口的IP地址
INTERFACE_UP 网络接口处于UP状态
INTERFACE_DOWN 网络接口处于DOWN状态
IPV4_ROUTE_ADD 添加一个路由
IPV4_ROUTE_DELETE 删除一个路由
REDISTRIBUTE_ADD 添加一个重分配信息
REDISTRIBUTE_DELETE 删除一个重分配信息
IPV4_NEXTHOP_LOOKUP 查找下一跳信息
RMer 端接收到RMER报文后，会调用相关的处理函数进行处理，如表3-2所示。
表3-2 RMer系统的报文处理函数
RMER报文类型 处理函数
INTERFACE_ADD rread _interface_add( )
INTERFACE_DELETE rread _interface_delete( )
IPV4_ROUTE_ADD rread _ipv4_add( )
IPV4_ROUTE_DELETE rread _ipv4_delete( )
REDISTRIBUTE_ADD rmer_redistribute_add( )
REDISTRIBUTE_DELETE rmer_redistribute_delete( )
IPV4_NEXTHOP_LOOKUP rread_ipv4_nexthop_lookup( )
BGP端接收到RMER报文后，会调用如表3-3所示的处理函数来更新自己的数据库。
表3-3 BGP系统的报文处理函数
RMER报文类型 处理函数
INTERFACE_ADD bgp_interface_add( )
INTERFACE_DELETE bgp_interface_delete( )
INTERFACE_UP bgp_interface_up( )
INTERFACE_DOWN bgp_interface_down( )
INTERFACE_ADDRESS_ADD bgp_interface_address_add( )
INTERFACE_ADDRESS_DELETE bgp_interface_address_delete( )
IPV4_ROUTE_ADD rmer_read_ipv4( )
IPV4_ROUTE_DELETE rmer_read_ipv4( )
3.7 RMer和Linux内核间通信
RMer系统使用ioctl[28,29]函数和Linux内核[41]进行通信，用户空间程序可以调用ioctl函数和硬件设备驱动程序或内核组件进行通信。ioctl函数的原型为：
int ioctl(int fd, int request, ... /* void *arg */  );
fd：为request控制命令需要操控的对象。
request：为需要执行的控制命令。
arg：第3个参数是一个指针，指针的类型取决于request。
表3-4描述了系统中使用到的request控制命令的类型，以及不同request控制命令对应的第3个参数的类型。
表3-4 系统中使用的ioctl request列表
request的取值 arg的类型 描述
SIOCGIFCONF struct ifconf 获取所有interface的列表
SIOCGIFINDEX struct ifreq 获取interface索引
SIOCGIFHWADDR struct ifreq 获取interface的硬件地址
SIOCGIFFLAGS struct ifreq 获取interface的flags
SIOCGIFMTU struct ifreq 获取interface的MTU值
SIOCGIFMETRIC struct ifreq 获取interface的Metric值
SIOCADDRT struct rtentry 向内核路由表增加路由
SIOCDELRT struct rtentry 从内核路由表删除路由
数据结构struct ifconf[30-36]用于SIOCGIFCONF控制请求，用来存储interface的配置信息，struct ifconf的源代码如下：
struct ifconf
{
int ifc_len;    /*size of buffer*/
union
{
  char * ifcu_buf;       /*buffer address*/
  struct ifreq *ifcu_req;  /*array of structures*/
} ifc_ifcu;
};
#define ifc_buf ifc_ifcu.ifcu_buf  /*buffer address*/
#define ifc_req ifc_ifcu.ifcu_req  /*array of structures*/
数据结构struct ifreq是真正存放interface信息的地方，源代码如下：
struct ifreq
  {
# define IFHWADDRLEN 6
# define IFNAMSIZ IF_NAMESIZE
    union
    {
  char ifrn_name[IFNAMSIZ]; /* Interface name, e.g. "en0".  */
    } ifr_ifrn;
    union
    {
  struct sockaddr ifru_addr;
  struct sockaddr ifru_dstaddr;
  struct sockaddr ifru_broadaddr;
  struct sockaddr ifru_netmask;
  struct sockaddr ifru_hwaddr;
  short int ifru_flags;
  int ifru_ivalue;
  int ifru_mtu;
  struct ifmap ifru_map;
  char ifru_slave[IFNAMSIZ]; /* Just fits the size */
  char ifru_newname[IFNAMSIZ];
  __caddr_t ifru_data;
    } ifr_ifru;
  };
# define ifr_name ifr_ifrn.ifrn_name   /*interface name*/
# define ifr_hwaddr ifr_ifru.ifru_hwaddr  /*MAC address*/
# define ifr_addr ifr_ifru.ifru_addr   /*address*/
# define ifr_dstaddr ifr_ifru.ifru_dstaddr  /*other end of p-p lnk*/
# define ifr_broadaddr ifr_ifru.ifru_broadaddr /*broadcast address*/
# define ifr_netmask ifr_ifru.ifru_netmask /*interface net mask*/
# define ifr_flags ifr_ifru.ifru_flags   /*flags*/
# define ifr_metric ifr_ifru.ifru_ivalue   /*metric*/
# define ifr_mtu ifr_ifru.ifru_mtu   /*mtu*/
# define ifr_map ifr_ifru.ifru_map   /*device map*/
# define ifr_slave ifr_ifru.ifru_slave   /*slave device*/
# define ifr_data ifr_ifru.ifru_data   /*for use by interface*/
# define ifr_ifindex ifr_ifru.ifru_ivalue      /*interface index*/
# define ifr_bandwidth ifr_ifru.ifru_ivalue  /*link bandwidth*/
# define ifr_qlen ifr_ifru.ifru_ivalue   /*queue length */
# define ifr_newname ifr_ifru.ifru_newname /*New name*/
# define _IOT_ifreq _IOT(_IOTS(char),IFNAMSIZ,_IOTS(char),16,0,0)
# define _IOT_ifreq_short _IOT(_IOTS(char),IFNAMSIZ,_IOTS(short),1,0,0)
# define _IOT_ifreq_int _IOT(_IOTS(char),IFNAMSIZ,_IOTS(int),1,0,0)
系统使用getifaddrs[37-40]函数获取interface的地址信息，这些信息存放在动态分配的内存中，必须使用freeifaddrs函数进行释放。interface的地址信息使用数据结构struct ifaddrs进行存储，所有interface的地址信息被串成一个链表结构，保存在系统动态分配的内存中，由指针ifap指向。如果getifaddrs函数执行成功，返回0，否则返回-1，并设置错误码。相关的源代码如下：
int getifaddrs (struct ifaddrs **ifap);  /*Create a linked list of `struct ifaddrs' structures*/
void freeifaddrs (struct ifaddrs *ifa);  /*Reclaim the storage allocated by getifaddrs'*/

struct ifaddrs
{
  struct ifaddrs *ifa_next;  /*Pointer to the next structure.  */
  char *ifa_name;    /*Name of this network interface.  */
  unsigned int ifa_flags;      /*Flags as from SIOCGIFFLAGS ioctl.  */
  struct sockaddr *ifa_addr;  /* Network address of this interface.  */
  struct sockaddr *ifa_netmask;  /*Netmask of this interface.  */
  union
  {
    /* At most one of the following two is valid.  If the IFF_BROADCAST bit is set in `ifa_flags', then ` ifa_broadaddr' is valid. If the IFF_POINTOPOINT bit is set, then `ifa_dstaddr' is valid. It is never the case that both these bits are set at once.*/
    struct sockaddr *ifu_broadaddr; /* Broadcast address of this interface. */
    struct sockaddr *ifu_dstaddr; /* Point-to-point destination address.  */
  } ifa_ifu;
# ifndef ifa_broadaddr
#  define ifa_broadaddr ifa_ifu.ifu_broadaddr
# endif
# ifndef ifa_dstaddr
#  define ifa_dstaddr ifa_ifu.ifu_dstaddr
# endif
  void *ifa_data;  /* Address-specific data (may be unused).  */
};
数据结构struct rtentry[37-40]用于SIOCADDRT和SIOCDELRT控制请求，这两个控制请求分别表示向内核添加和删除路由。struct rtentry的源代码如下：
struct rtentry
  {
    unsigned long int rt_pad1;
    struct sockaddr rt_dst;    /*Target address.*/
    struct sockaddr rt_gateway;   /*Gateway addr (RTF_GATEWAY).*/
    struct sockaddr rt_genmask;   /*Target network mask (IP).*/
    unsigned short int rt_flags;
    short int rt_pad2;
    unsigned long int rt_pad3;
    unsigned char rt_tos;
    unsigned char rt_class;
#if __WORDSIZE == 64
    short int rt_pad4[3];
#else
    short int rt_pad4;
#endif
    short int rt_metric;    /*+1 for binary compatibility!*/
    char *rt_dev;     /*Forcing the device at add.*/
    unsigned long int rt_mtu;  /*Per route MTU/Window.*/
    unsigned long int rt_window;  /*Window clamping.*/
    unsigned short int rt_irtt;   /*Initial RTT.*/
  };
第4章 BGP协议的实现
4.1 静态路由表管理
当VTY收到用户输入的添加或删除静态路由的命令后，系统会调用函数static_ipv4_func，对静态路由表进行更新。如果命令是添加静态路由，则调用的主要函数流程是static_ipv4_add->rib_static_install；如果命令是删除静态路由，则调用的主要函数流程是static_ipv4_delete->rib_static_uninstall。静态路由相关的函数调用如图4-1所示。

图4-1 静态路由相关函数调用
static_ipv4_add函数主要处理过程如下：
(1) 查找static_ipv4_table路由表中是否已经有相同前缀的路由存在；
(2) 如果有，并且其他属性和新配置的参数完全相同，则直接返回；
(3) 如果没有，为新路由节点分配内存，设定参数，插入到static_ipv4_table路由表中；
(4) 调用rib_static_install将新路由节点插入到RIB路由表ipv4_rib_table中。
   rib_static_install函数主要处理过程如下：
(1) 查找RIB路由表ipv4_rib_table中是否有相同前缀的路由存在；
(2) 如果有，添加nexthop信息，然后调用rib_process进行一些内部处理；
(3) 如果没有，新建路由节点，添加nexthop信息, 将该RIB节点插入到RIB路由表ipv4_rib_table中，然后调用rib_process进行一些内部处理。
static_ipv4_delete函数主要处理过程如下：  
(1) 查找static_ipv4_table路由表中是否有此需要删除的路由；
(2) 如果没有此路由节点，则直接返回；
(3) 如果找到此路由节点，则调用rib_static_uninstall，从RIB路由表ipv4_rib_table中删除原路由；
(4) 从static_ipv4_table路由表中删除该节点，释放内存。
rib_static_uninstall函数主要处理过程如下：
(1) 查找RIB路由表ipv4_rib_table中是否有和前缀对应的路由节点存在，如果没有，直接返回；
(2) 如果此路由节点存在，查找该路由节点中有无static类型的RIB存在，如果没有，直接返回；
(3) 如果该RIB存在，比较该RIB和要删除的RIB的nexthop信息是否一致；
(4) 如果nexthop信息不一致，直接返回。
(5) 如果该RIB只有一条nexthop信息，就从ipv4_rib_table中对应的路由节点中删除该RIB信息，然后调用rib_process进行一些内部处理，接着释放该RIB所占内存。
(6) 如果该RIB有多条nexthop信息，调用rib_uninstall从内核路由表中删除该RIB信息，调用nexthop_delete从该RIB节点中删除相应的nexthop信息并释放内存，然后调用rib_process向BGP系统和内核重新更新该RIB信息。
rib_process函数主要处理过程如下：
(1) 从前缀的RIB里面找出最优的RIB
(2) 如果没有要删除的RIB，并且当前使用的RIB是最优的，并且该RIB发生了变化，则：
1) 如果BGP系统允许该类型的RIB重分配为BGP路由，RMer系统向BGP系统发送IPV4_ROUTE_DELETE报文，先删除该RIB信息；
2) 如果非RMER_ROUTE_KERNEL或RMER_ROUTE_CONNECT路由，则先从内核中删除该RIB；
3) 更新该RIB的nexthop信息；
4) 如果非RMER_ROUTE_KERNEL或RMER_ROUTE_CONNECT路由，向内核添加该RIB；
5) 如果BGP系统允许该类型的rib重分配为BGP路由，RMer系统向BGP系统发送IPV4_ROUTE_ADD报文，添加该RIB信息。
(3) 如果有要删除的RIB，则：
1) 如果BGP系统允许该类型的RIB重分配为BGP路由，RMer系统向BGP系统发送IPV4_ROUTE_DELETE报文，删除该RIB信息；
2) 如果非RMER_ROUTE_KERNEL或RMER_ROUTE_CONNECT路由，则从内核中删除该RIB；
3) 更新该RIB的nexthop信息。
(4) 如果有最优的RIB，则：
1) 更新该RIB的nexthop信息；
2) 如果非RMER_ROUTE_KERNEL或RMER_ROUTE_CONNECT路由，向内核添加该RIB；
3) 如果BGP系统允许该类型的RIB重分配为BGP路由，RMer系统向BGP系统发送IPV4_ROUTE_ADD报文，添加该RIB信息。
4.2 动态路由表管理
  动态路由是指那些通过RIP、OSPF、BGP等动态路由协议学习的路由。BGP路由是BGP协议动态学到的动态路由，最终需要添加到全局的RIB路由表ipv4_rib_table中，这个全局的RIB路由表是由RMer系统维护的，所以BGP系统必须通过RMER报文，将BGP路由发送给RMer系统。当BGP系统向RMer系统发送IPV4_ROUTE_ADD类型的RMER报文时，表示添加一条BGP路由，当BGP系统向RMer系统发送IPV4_ROUTE_DELETE类型的RMER报文时，表示删除一条BGP路由。RMer系统通过函数rmer_client_read接收来自BGP系统的RMER报文。图4-2描述了动态路由相关的函数调用。

图4-2动态路由相关函数调用
rread_ipv4_add函数主要处理过程如下：
(1) 创建一个新的RIB节点；
(2) 解析来自BGP系统的RMER报文的内容，并获得路由前缀信息；
(3) 利用解析出的内容对RIB节点进行初始化；
(4) 调用rib_add_ipv4_multipath函数进一步处理。
rib_add_ipv4_multipath函数主要处理过程如下：
(1)  根据路由的类型，设置RIB节点的默认distance值；
(2) 从全局RIB路由表ipv4_rib_table中找出前缀对应的路由节点，并对该路由节点进行处理；
(3) 对RIB节点的flags域和nexthop域进行设置；
(4) 将该RIB节点插入到RIB路由表ipv4_rib_table中，然后调用rib_process进行一些内部处理。
rread_ipv4_delete函数主要处理过程如下：
(1) 解析来自BGP系统的RMER报文的内容，并获得要删除的路由前缀信息；
(2) 解析RMER报文的其他域的内容，包括type、flags、message以及nexthop信息等；
(3) 调用rib_delete_ipv4函数进一步处理。
rib_delete_ipv4函数主要处理过程如下：
(1) 查找RIB路由表ipv4_rib_table中是否有此路由节点存在，如果没有，直接返回；
(2) 如果此路由节点存在，查找该路由节点中和前缀类型相同的RIB节点；
(3) 如果该RIB节点存在，且为动态路由，从RIB路由表ipv4_rib_table中删除该RIB节点，然后调用rib_process进行一些内部处理，最后释放RIB节点所占内存。
4.3 RMer和BGP间的路由更新报文
BGP系统和RMer系统之间的路由信息的交换是通过IPV4_ROUTE_ADD和IPV4_ROUTE_DELETE两种报文来实现的。如图4-3所示，BGP系统使用rapi_ipv4_add和rapi_ipv4_delete函数向RMer发送IPV4_ROUTE_ADD和IPV4_ROUTE_DELETE报文，使用rmer_read_ipv4接收IPV4_ROUTE_ADD和IPV4_ROUTE_DELETE报文。RMer系统使用rsend_ipv4_add_multipath和rsend_ipv4_delete_multipath发送IPV4_ROUTE_ADD和IPV4_ROUTE_DELETE报文，使用rread_ipv4_add和rread_ipv4_delete函数接收IPV4_ROUTE_ADD和IPV4_ROUTE_DELETE报文。

图4-3 BGP和RMer传递路由信息
图4-4为RMer系统向BGP系统发送的路由更新报文格式，当报文类型域的值为IPV4_ROUTE_ADD时，表示为IPV4_ROUTE_ADD报文，当报文类型域的值为IPV4_ROUTE_DELETE时，表示为IPV4_ROUTE_DELETE报文。

图4-4 RMer向BGP发送的路由更新报文格式
图4-5为BGP系统向RMer系统发送的路由更新报文格式，当报文类型域的值为IPV4_ROUTE_ADD时，表示为IPV4_ROUTE_ADD报文，当报文类型域的值为IPV4_ROUTE_DELETE时，表示为IPV4_ROUTE_DELETE报文。

图4-5 BGP向RMer发送的路由更新报文格式
数据结构struct rapi_ipv4的代码如下：
struct rapi_ipv4
{
  u_char type;           //route type
  u_char flags;          // IBGP, EBGP or INTERNAL
  u_char message;       // NEXTHOP, IFINDEX, METRIC or DISTANCE
  u_char nexthop_num;   //the num of nexthop
  struct in_addr **nexthop; //nexthop addresses are stored in this array nexthop[nexthop_num]
  u_char ifindex_num;    //num of ifindex, set 0
  unsigned int *ifindex;   //ifindex
  u_char distance;        //distance
  u_int32_t metric;       //metric
};
数据结构struct prefix_ipv4的代码如下：
struct prefix_ipv4
{
  u_char family;         //address family
  u_char safi;           //sub address family
  u_char prefixlen;       //prefix length
  u_char padding;        //padding
  struct in_addr prefix;    //prefix
};
4.4 BGP有限状态机
BGP对等体在交换网络可达信息之前必须首先建立起一个BGP对话，BGP对等体间对话关系的全面建立和维持可以用图4-6所示的有限状态机来描述，图中的数字表示13种状态机事件。表4-1对应于图4-6，描述了当状态机事件发生时，状态机所执行的动作和状态转换情况。

图4-6 BGP有限状态机[9]

表4-1 BGP有限状态机状态转移表
当前状态 FSM事件 动作 发送报文 下一个状态
Idle 1 初始化资源；启动ConnectRetry计时器；初始化TCP连接 无 Connect
其他 无   无 Idle
Connect 1 无 无 Connect
3 完成初始化；清零ConnectRetry计时器 OPEN OpenSent
5 重启ConnectRetry计时器 无 Active
7 启动ConnectRetry计时器；初始化TCP连接 无 Connect
其他 释放资源 无 Idle
Active 1 无 无 Active
3 完成初始化；清零ConnectRetry计时器 OPEN OpenSent
5 关闭连接，重启ConnectRetry计时器 无 Active
7 启动ConnectRetry计时器；初始化TCP连接 无 Connect
其他 释放资源 无 Idle
OpenSent 1 无 无 OpenSent
4 关闭连接，重启ConnectRetry计时器 无 Active
6 释放资源 无 Idle
10 OPEN报文正确 KEEPALIVE OpenConfirm
  OPEN报文出错 NOTIFICATION Idle
其他 关闭TCP连接；释放资源 NOTIFICATION Idle
OpenConfirm 1 无 无 OpenConfirm
4 释放资源 无 Idle
6 释放资源 无 Idle
9 重启KeepAlive计时器 KEEPALIVE OpenConfirm
11 完成初始化；重启Hold计时器 无 Established
13 关闭TCP连接；释放资源 无 Idle
其他 关闭TCP连接；释放资源 NOTIFICATION Idle
Established 1 无 无 Established
4 释放资源 无 Idle
6 释放资源 无 Idle
9 重启KeepAlive计时器 KEEPALIVE Established
11 重启Hold计时器 KEEPALIVE Established
12
UPDATE报文正确 UPDATE Established
  UPDATE报文错误 NOTIFICATION Idle
13 关闭TCP连接；释放资源 None Idle
其他 关闭TCP连接；释放资源 NOTIFICATION Idle
下面对图4-6中BGP有限状态机的6个状态进行详细的分析。
1． Idle状态
Idle状态是BGP客户端的起始状态，BGP服务器最初处于Active状态。进入该状态，打开start计时器，表示start计时器超时后，BGP_Start事件会触发FSM从起点开始运行。BGP_Start事件到来时，跳转到Connect状态。事件处理函数会主动向BGP服务器发起连接请求。其他状态机事件到来时，跳转到Idle状态，并做相应的处理。
2．Connect状态
进入该状态，打开connect计时器，表示connect计时器超时后，BGP_Start事件到来时，跳转到Connect状态，事件处理函数为空。TCP_connection_open事件到来时，跳转到OpenSent状态，向BGP服务器发送OPEN报文，同时准备接收来自BGP邻居的OPEN报文。TCP_connection_open_failed事件到来时，跳转到Active状态，停止该BGP会话。ConnectRetry_timer_expired事件到来时，跳转到Connect状态。处理函数会先停止该BGP会话，接着重新向BGP服务器发出连接请求。其他状态机事件到来时，跳转到Idle状态，并做相应的处理。
3．Active状态
这是BGP服务器的初始状态。进入该状态，打开connect计时器，表示connect计时器超时后，ConnectRetry_timer_expired事件会发生。TCP_connection_open事件到来时，跳转到OpenSent状态，准备接收来自BGP邻居的OPEN报文。TCP_connection_open_failed事件到来时，跳转到Active状态，事件处理函数为空。ConnectRetry_timer_expired事件到来时，跳转到Connect状态，将BGP服务器的角色转换为BGP客户端的角色，向对方发出连接请求。其他状态机事件到来时，跳转到Idle状态，并做相应的处理。
4．OpenSent状态
进入该状态，打开hold计时器，表示hold计时器超时后，Hold_Timer_expired事件会发生。BGP_Start事件到来时，跳转到OpenSent状态，事件处理函数为空。TCP_connection_closed事件到来时，跳转到Active状态，关闭BGP会话。Hold_Timer_expired事件到来时，跳转到Idle状态，向BGP邻居发送hold计时器超时对应的NOTIFICATION报文。Receive_OPEN_message事件到来时，跳转到OpenConfirm状态，向BGP邻居发送KEEPALIVE报文，同时关闭hold计时器。其他事件到来时，跳转到Idle状态，并作相应的处理。
5．OpenConfirm状态
进入该状态，打开hold计时器和keepalive计时器，表示hold计时器超时后，Hold_Timer_expired事件会发生；keepalive计时器超时后，KeepAlive_timer_expired事件会发生。BGP_Start事件到来时，跳转到OpenConfirm状态，事件处理函数为空。Hold_Timer_expired事件到来时，跳转到Idle状态，向BGP邻居发送hold计时器超时对应的NOTIFICATION报文。KeepAlive_timer_expired事件到来时，跳转到OpenConfirm状态，事件处理函数为空。Receive_KEEPALIVE_message事件到来时，跳转到Established状态，向BGP邻居发送KEEPALIVE报文和UPDATE报文。其他事件到来时，跳转到Idle状态，并作相应的处理。
6．Established状态
进入该状态，打开hold计时器和keepalive计时器，表示hold计时器超时后，Hold_Timer_expired事件会发生；keepalive计时器超时后，KeepAlive_timer_expired事件会发生。BGP_Start事件到来时，跳转到Establish状态，事件处理函数为空。KeepAlive_timer_expired事件到来时，跳转到Establish状态，向BGP邻居发送KEEPALIVE报文。Receive_KEEPALIVE_message事件到来时，跳转到Establish状态。事件处理函数会停止hold计时器。Receive_UPDATE_message事件到来时，跳转到Establish状态，停止hold计时器。其他事件到来时，跳转到Idle状态，并作相应的处理。
BGP有限状态机所对应的数据结构如下所示。
struct {
  int (*func) ();
  int next_state;
} FSM [BGP_STATUS_MAX - 1][BGP_EVENTS_MAX - 1] =
{
  {
    /* Idle state*/
    {bgp_start,  Connect},     /* BGP_Start                     */
    {bgp_stop,   Idle},  /* BGP_Stop                      */
    {bgp_stop,   Idle},  /* TCP_connection_open           */
    {bgp_stop,   Idle},  /* TCP_connection_closed         */
    {bgp_ignore, Idle},   /* TCP_connection_open_failed    */
    {bgp_stop,   Idle},  /* TCP_fatal_error               */
    {bgp_ignore, Idle},   /* ConnectRetry_timer_expired    */
    {bgp_ignore, Idle},   /* Hold_Timer_expired            */
    {bgp_ignore, Idle},   /* KeepAlive_timer_expired       */
    {bgp_ignore, Idle},   /* Receive_OPEN_message          */
    {bgp_ignore, Idle},   /* Receive_KEEPALIVE_message    */
    {bgp_ignore, Idle},   /* Receive_UPDATE_message        */
    {bgp_ignore, Idle},   /* Receive_NOTIFICATION_message */
  },
  {
    /* Connect */
    {bgp_ignore,  Connect}, /* BGP_Start                     */
    {bgp_stop,    Idle},  /* BGP_Stop                      */
    {bgp_connect_success, OpenSent}, /* TCP_connection_open       */
    {bgp_stop, Idle},   /* TCP_connection_closed         */
    {bgp_connect_fail, Active},  /* TCP_connection_open_failed    */
    {bgp_connect_fail, Idle}, /* TCP_fatal_error               */
    {bgp_reconnect, Connect}, /* ConnectRetry_timer_expired    */
    {bgp_ignore,  Idle},  /* Hold_Timer_expired            */
    {bgp_ignore,  Idle},  /* KeepAlive_timer_expired       */
    {bgp_ignore,  Idle},  /* Receive_OPEN_message         */
    {bgp_ignore,  Idle},  /* Receive_KEEPALIVE_message    */
    {bgp_ignore,  Idle},  /* Receive_UPDATE_message       */
    {bgp_stop,    Idle},  /* Receive_NOTIFICATION_message */
  },
  {
    /* Active, */
    {bgp_ignore,  Active},  /* BGP_Start                     */
    {bgp_stop,    Idle},  /* BGP_Stop                     */
    {bgp_connect_success, OpenSent}, /* TCP_connection_open      */
    {bgp_stop,    Idle},  /* TCP_connection_closed          */
    {bgp_ignore,  Active},  /* TCP_connection_open_failed      */
    {bgp_ignore,  Idle},  /* TCP_fatal_error               */
    {bgp_start,   Connect}, /* ConnectRetry_timer_expired    */
    {bgp_ignore,  Idle},  /* Hold_Timer_expired            */
    {bgp_ignore,  Idle},  /* KeepAlive_timer_expired       */
    {bgp_ignore,  Idle},  /* Receive_OPEN_message          */
    {bgp_ignore,  Idle},  /* Receive_KEEPALIVE_message    */
    {bgp_ignore,  Idle},  /* Receive_UPDATE_message       */
    {bgp_stop_with_error, Idle}, /* Receive_NOTIFICATION_message  */
  },
  {
    /* OpenSent, */
    {bgp_ignore,  OpenSent}, /* BGP_Start                     */
    {bgp_stop,    Idle},  /* BGP_Stop                      */
    {bgp_stop,    Idle},  /* TCP_connection_open           */
    {bgp_stop,    Active},  /* TCP_connection_closed         */
    {bgp_ignore,  Idle},  /* TCP_connection_open_failed    */
    {bgp_stop,    Idle},  /* TCP_fatal_error               */
    {bgp_ignore,  Idle},  /* ConnectRetry_timer_expired    */
    {fsm_holdtime_expire, Idle}, /* Hold_Timer_expired            */
    {bgp_ignore,  Idle},  /* KeepAlive_timer_expired       */
    {fsm_open,    OpenConfirm}, /* Receive_OPEN_message      */
    {bgp_ignore,  Idle},  /* Receive_KEEPALIVE_message    */
    {bgp_ignore,  Idle},  /* Receive_UPDATE_message       */
    {bgp_stop_with_error, Idle}, /* Receive_NOTIFICATION_message  */
  },
  {
    /* OpenConfirm, */
    {bgp_ignore,  OpenConfirm}, /* BGP_Start                  */
    {bgp_stop,    Idle},  /* BGP_Stop                      */
    {bgp_stop,    Idle},  /* TCP_connection_open           */
    {bgp_stop,    Idle},  /* TCP_connection_closed         */
    {bgp_stop,    Idle},  /* TCP_connection_open_failed    */
    {bgp_stop,    Idle},  /* TCP_fatal_error               */
    {bgp_ignore,  Idle},  /* ConnectRetry_timer_expired    */
    {fsm_holdtime_expire, Idle}, /* Hold_Timer_expired            */
    {bgp_ignore,  OpenConfirm}, /* KeepAlive_timer_expired      */
    {bgp_ignore,  Idle},  /* Receive_OPEN_message          */
    {bgp_establish, Established}, /* Receive_KEEPALIVE_message    */
    {bgp_ignore,  Idle},  /* Receive_UPDATE_message       */
    {bgp_stop_with_error, Idle}, /* Receive_NOTIFICATION_message */
  },
  {
    /* Established, */
    {bgp_ignore,  Established}, /* BGP_Start                     */
    {bgp_stop,    Idle},  /* BGP_Stop                      */
    {bgp_stop,    Idle},  /* TCP_connection_open           */
    {bgp_stop,    Idle},  /* TCP_connection_closed         */
    {bgp_ignore,  Idle},  /* TCP_connection_open_failed    */
    {bgp_stop,    Idle},  /* TCP_fatal_error               */
    {bgp_ignore,  Idle},  /* ConnectRetry_timer_expired    */
    {fsm_holdtime_expire, Idle}, /* Hold_Timer_expired            */
    {fsm_keepalive_expire, Established}, /* KeepAlive_timer_expired   */
    {bgp_stop, Idle},   /* Receive_OPEN_message          */
    {fsm_keepalive, Established}, /* Receive_KEEPALIVE_message    */
    {fsm_update,   Established}, /* Receive_UPDATE_message       */
    {bgp_stop_with_error, Idle}, /* Receive_NOTIFICATION_message  */
  },
};



第5章 BGP协议测试
5.1 BGP测试平台
为了便于开发和测试，在Windows上采用虚拟平台进行实验的测试，该实验同样适合于真实的硬件环境。在测试测试过程中，需要使用到如下工具：
1， cisco路由器模拟软Dynamips[47]，下载地址为http://dynagen.org/
2， cisco 7200 IOS[49]镜像。Dynamips可以运行真实的Cisco 2691, 3620, 3640, 3660, 3725, 3745和7200 IOS镜像，这些镜像由cisco公司提供。
3， VMware[50]虚拟机，版本号为5.0.0，该软件由VMware公司提供。
4， cisco仿真路由器运行的操作系统为Microsoft Windows XP。
5， BGP路由器运行的操作系统：Red Hat Linux 9，内核版本为2.4.20，该操作系统由Red Hat[51]公司提供。
图5-1提供了一种网络测试拓扑图，其中R1和R2为Dynamips模拟的cisco 7200路由器，因为使用的是真正的cisco IOS内核，所以通过Dynamips模拟出来的cisco路由器和真实的路由器功能一样。RMer为运行在Linux操作系统下的BGP路由器，即需要测试的路由器，通过这种连接方式，可以很方便的对RMer路由器上的BGP功能进行测试。
图5-1 网络测试拓扑图
针对图5-1描述的网络拓扑结构，下面详细描述该测试环境中各个路由器间的通信原理。如图5-2所示，Windows操作系统上有一个虚拟网卡eth-win，Linux操作系统上有三个网卡eth0、eth1和eth2，这四个网卡全部和虚拟网络VMnet1相连。Windows和Linux之间是通过eth-win和eth0这两个网卡实现通信的，这就要求它们的IP地址必须配置在同一个网段。eth1和eth2是留给BGP路由器RMer使用的，其IP地址可以任意配置。R1和R2是Windows上运行的两个cisco路由器，通过配置R1的f0/0以太网接口和eth-win相连，R2的f0/0以太网接口和eth-win相连，这样就可以保证R1和RMer之间以及RMer和R2之间均为物理连通的，尽管实际上是通过eth-win和eth0间的连接实现的。通过配置R1、R2和RMer各个以太网接口的IP地址，就可以实现网络通信了。关于VMware以及Dynamips的操作请参考相关手册。

图5-2 BGP协议测试平台
图5-2所示的拓扑连接，构成了一个简单的广域网测试环境，因为是在一台主机上运行的，所以对主机的配置要求比较高，但是最大的优点在于，操作方便，实验结果清晰明了。本文侧重在BGP路由器功能上的实现，所以重在对BGP路由器的功能进行测试，但也不乏性能方面的考虑。路由器的性能与多方面的因素有关，本文主要是提供一种BGP协议的设计和实现方法，同时可以很方便地把该BGP路由软件移植到其他的硬件平台上。
5.2 BGP功能测试
如图5-1所示，路由器RMer从路由器R1和R2中得到网络10.3.3.0/24，在R1和R2分别使用1个回环、1个静态路由和路由映射模仿AS 4。本文以对BGP协议的MED属性的测试为例，说明测试的过程。
测试内容：
1， 运行bgp bestpath compare-routerid命令，表示当两条路由的其他属性均相同时，BGP路由器就会选择择路由器ID最小的那条路由。
2， 根据最优路由选择策略，默认情况下，如果没有使用bgp always-compare-med命令，RMer不会对来自R1和R2的两条相同路由的MED值进行比较，最终会选择始发者ID最小的路由。
3， 使用bgp always-compare-med命令后，显然会选择来自R2的BGP路由10.3.3.0/24。
R1配置信息：
hostname R1
interface Loopback0
ip address 5.5.5.5 255.255.255.255
interface FastEthernet0/0
ip address 10.1.1.1 255.255.255.0
router bgp 1
redistribute static route-map setmed
neighbor 10.1.1.2 remote-as 2
neighbor 10.1.1.2 route-map setas out
no auto-summary
ip route 10.3.3.0 255.255.255.0 Loopback0
route-map setmed permit 10
set metric 200
route-map setas permit 10
set as-path prepend 4
RMer配置信息：
hostname RMer
interface eth1
ip address 10.1.1.2/24
interface eth2
ip address 10.2.2.1/24
router bgp 2
bgp bestpath compare-routerid
neighbor 10.1.1.1 remote-as 1
neighbor 10.2.2.2 remote-as 3
R2配置信息：
hostname R2
interface Loopback0
ip address 6.6.6.6 255.255.255.255
interface FastEthernet0/0
ip address 10.2.2.2 255.255.255.0
router bgp 3
no synchronization
bgp log-neighbor-changes
redistribute static route-map setmed
neighbor 10.2.2.1 remote-as 2
neighbor 10.2.2.1 route-map setas out
no auto-summary
ip route 10.3.3.0 255.255.255.0 Loopback0
route-map setmed permit 10
set metric 100
route-map setas permit 10
set as-path prepend 4
执行bgp always-compare-med命令前：
R1#show ip bgp summary
BGP router identifier 5.5.5.5, local AS number 1
BGP table version is 2, main routing table version 2
1 network entries using 101 bytes of memory
2 path entries using 96 bytes of memory
2 BGP path attribute entries using 120 bytes of memory
1 BGP AS-PATH entries using 24 bytes of memory
0 BGP route-map cache entries using 0 bytes of memory
0 BGP filter-list cache entries using 0 bytes of memory
BGP using 341 total bytes of memory
BGP activity 1/0 prefixes, 4/2 paths, scan interval 60 secs
Neighbor        V    AS MsgRcvd MsgSent   TblVer  InQ OutQ Up/Down  State/PfxRcd
10.1.1.2        4     2      45      51        2    0    0 00:01:31        1

R2#show ip bgp summary
BGP router identifier 6.6.6.6, local AS number 3
BGP table version is 2, main routing table version 2
1 network entries using 101 bytes of memory
1 path entries using 48 bytes of memory
1 BGP path attribute entries using 60 bytes of memory
0 BGP route-map cache entries using 0 bytes of memory
0 BGP filter-list cache entries using 0 bytes of memory
BGP using 209 total bytes of memory
BGP activity 1/0 prefixes, 5/4 paths, scan interval 60 secs
Neighbor        V    AS MsgRcvd MsgSent   TblVer  InQ OutQ Up/Down  State/PfxRcd
10.2.2.1        4     2      50      53        2    0    0 00:03:09        0

RMer# show ip bgp
BGP table version is 0, local router ID is 172.18.211.10
Status codes: s suppressed, d damped, h history, * valid, > best, i - internal
Origin codes: i - IGP, e - EGP, ? - incomplete
   Network            Next Hop         Metric LocPrf Weight Path
*> 10.3.3.0/24        10.1.1.1            200             0 1 4 ?
*  10.3.3.0/24        10.2.2.2            100             0 3 4 ?
执行bgp always-compare-med命令后：
RMer# show ip bgp
BGP table version is 0, local router ID is 172.18.211.10
Status codes: s suppressed, d damped, h history, * valid, > best, i - internal
Origin codes: i - IGP, e - EGP, ? - incomplete
   Network            Next Hop         Metric LocPrf Weight Path
*> 10.3.3.0/24        10.2.2.2            100             0 3 4 ?
*  10.3.3.0/24        10.1.1.1            200             0 1 4 ?
Total number of prefixes 1
执行bgp always-compare-med命令前，RMer不会比较MED值，而是选择来自路由ID较小的路由。因为R1的ID为5.5.5.5，R2的ID为6.6.6.6，故RMer优先选择来自R1的路由。执行bgp always-compare-med命令后，RMer优先考虑MED值较小的路由，来自R3的路由的MED值为100，故优先选择该路由。
对系统的测试结果表明BGP协议的基本功能以及BGP状态机能够正常运行。BGP路由聚合、BGP路由重分配等功能能够正常运行，支持RFC1771所定义的AS_PATH属性、NEXT_HOP属性、MED属性和LOCAL_PREF属性。

第6章 结论与展望
本课题采用Linux操作系统提供的TCP/IP协议栈，对BGP协议进行实现，其中包括BGP四种报文处理、BGP有限状态机和BGP路径属性管理的实现等。系统实现了BGP协议的主要功能，其中包括BGP邻居关系的建立，BGP路由聚合操作，BGP路由重分配，BGP最优路径选择等操作。
本课题所设计的系统归纳起来有如下几个特点：首先，Linux操作系统有强大的网络功能且成本低廉，软硬件环境容易获取，便于推广和使用，这是选择Linux操作系统的一个主要原因。其次，在BGP协议开发过程中，结合cisco路由仿真软件Dynamips进行测试，仅需一台PC机就可以完成所有网络实验。优秀且易于获取的开发环境和功能强大的测试工具，使得本课题所采用的开发方法和测试方法可以广泛应用于网络的教学实验中，具有一定的教学推广价值。再次，本论文使用模块化开发方法，便于将BGP协议移植到新的平台上，同时便于新的协议的开发和BGP协议的扩展，最终可以设计出功能更全的路由软件，如果让其运行在高性能多网卡的PC机上，就可以在一定程度上替代路由器来使用。
本课题的设计还有许多值得改进之处。在BGP协议的设计过程中，主要是对BGP功能的实现，在该路由软件的性能上可以改进。比如可以把BGP协议能够直接写成内核模块，同时对Linux内核进行优化，提高系统的性能。除了在性能上的改进，本系统在功能上还需要进一步加以完善，其中包括两个部分。第一个部分是对BGP协议本身的完善，随着BGP协议的不断发展，更多的功能需要被加入进来，同时像对IPV6[52]的支持也是值得考虑的一点。另外一个部分就是对其他动态协议的支持，像RIP、OSPF等，只有把这些动态路由协议加入进来，并且实现和BGP协议之间的通信，这才算是一个完整的路由器。

致  谢
向在硕士课题研究工作的一年多时间里对我提供过指导和帮助的老师、同学和同事表示由衷的感谢！
感谢我的导师李允副教授，他渊博的学识，丰富的实践经验、一丝不苟的治学态度和精益求精的工作作风给予我极大的启迪和引导。在我研究生学习期间，李老师为我创造了良好的学习和研究环境，并经常给予我及时的指导和帮助，为我在技术和研究上为我指明了方向，使我能够在众多的技术和研究方向中迅速做出正确的选择，并能够将有用的知识很快地学以致用，使我在研究生期间能够得到全面的发展。在此，再一次表示我深深的敬意！
感谢明瑞电子有限公司，为我提供研究生论文研究相关工作的相关硬件和软件条件。感谢于逊、鄢文静、王孟等同事和我一起参与BGP协议的设计和开发。
最后，衷心感谢为评阅本论文而付出辛勤劳动的各位专家和学者！