第17章OSPF路由协议的软件模拟与设计

1、第17章 OSPF路由协议的软件模拟与设计第17章OSPF路由协议的软件模拟与设计Internet是一个分组交换网络，一个源节点应用程序所产生的数据分组要到达目的节点的对等层应用程序，通常要经过若干中间交换节点的转发中继，除非源和目的节点既在同一条数据链路上又在同一个子网中。如果转发设备是路由器或三层交换机，则设备中的数据链路层协议负责将待转发数据帧沿给定的数据链路传递到相邻的下一个节点，而网络层协议则要负责路由选择，即从可达目的节点的多条转发链路中选择出一条最佳的数据链路。路由有两种类型：静态路由和动态路由。静态路由即网络管理员手工配置的路由，这种路由有两个主要的缺陷：一个是不能对路由设备或

2、链路的失效以及网络拓扑的变化做出反应，一个是不适合于具有复杂拓扑结构的大规模网络（可扩展性）。因此，当需要管理的网络不是小型网络时，就需要使用动态路由。动态路由是路由选择协议根据网络中所有路由器及其接口链路的当前状态自动计算生成的。路由选择协议能够自动检测路由设备及其接口链路的状态，能够自动适应网络拓扑的变化。开放最短路径优先协议（OSPF，Open Shortest Path First）是一个基于链路状态算法、适合大型复杂网络、具有高效健壮特性的动态内部网关协议（工业上将路由器被称为网关）。“开放最短路径优先”的名字来源于以下事实：（1）这个协议基于Dijkstra的最短路径优先（SPF，

3、Shortest Path First）路由算法。（2）“开放”反映了这个标准是开放的标准而不是一个私有的标准，这与一系列由特定厂商专有的或专用于某种特定网络的链路状态协议形成了对比，如Novell Netware的链路服务协议NLSP（Netware Link Servise Protocol）、IBM SNA的高级对等网络协议APPN（Advanced Peer-to-Peer Networking）和ATM的专用网间接口协议PNNI（Private Network-to-Network Interace）。作为开放和通用标准运动的主要倡议者DEC公司为该协议做了最初的大部分工作，并把它作

4、为了私有产品DECnet体系结构的一部分。OSPF起源于1979年Bolt、Beranek和Newman公司为ARPANET开发的“新的实验性路由算法”以及随后ISO为OSI开发的IS-IS路由协议，是John T. Moy等人在1987年为克服RIP协议耗费带宽资源多、应对链路故障或拓扑变化收敛速度慢、适应树状拓扑结构难等缺点而开发的。OSPF最初的其它功能需求还包括：（1）采用更具描述性的路由度量值，以摆脱RIP协议网络直径最大15个路由器跳步的限制，以及可以将延时、带宽等其它路由度量因素考虑进来。（2）可利用等代价的多条路径，以达到均衡负载等转发策略。（3）具有路由选择的层次结构，以适应

5、大规模复杂网络以及树状层次网络拓扑结构。（4）支持更灵活的子网化技术，以适应变长子网掩码以及更进一步的无类别域间路由。（5）保证安全性，避免伪路由器通过发布默认或其它路由而使路由选择过程陷入混乱。（6）为保证可信性而区分内部和外部路由信息，内部路由信息可覆盖外部路由信息。虽然OSPF还支持基于服务类型TOS的路由选择，允许为每个不同的TOS配置不同的链路度量值并建立不同的路由表，但基于TOS的路由选择从未在Internet上流行。OSPF的各个版本间是不兼容的。第1版的RFC 1131定义于1989年，目前的第2版在RFC 2328中有详细说明，1999年12月，IETF发布了基于IPv6的O

6、SPF标准RFC2740，并称之为OSPFv3。17.1 对等层协议模拟基础知识17.1.1 标识符命名和编写规范标识符命名和编写规范为了使程序易于理解和维护，在一个项目中的代码编写要遵循统一的规范。由于这种规范并不是强制的，因此，有时也将其称为风格。在此只对本章程序代码中结构、类、函数、变量、常量等标识符在命名时所遵循的规范和保持的风格进行说明。标识符命名有两种风格：Unix风格和Windows风格。以网络接口（Network Interface）的数据结构为例，按照两种风格定义的数据结构比较如下： Unix风格 Windows风格 struct ifnet struct IfNet str

7、uct ifnet *if_next; struct ifaddr *if_addrlist; struct IfNet* m_pNext; char *if_name; struct IfAddr* m_pAddrList; char* m_szName; struct ifqueue struct IfQueue struct mbuf *ifq_head; struct Mbuf* m_pHead; if_snd m_Send 综合上述两种标识符命名风格，本章的程序代码采用了如下的标识符命名规范：（1） 结构、类和函数的标识符均要包括一个标识其所属功能层次或程序包的前缀，前缀和标识符以下

8、划线“_”隔开，如PHY_、DRV_、DEV_、ARP_、OSPF_、SNMP_等。另外，组成标识符的每个英文单词的首字母大写，其余字母小写。（2） 常量标识符均采用大写字母。另外，函数返回的提示性常量标识符均添加“RV_”前缀。例如:const int RV_OK 1const int RV_FAILURE 0在协议分组格式的设计中，为了使协议分组在常见的计算机体系结构下易于处理，协议分组中各字节通常都是对齐的：4字节字段从偏移量为4的倍数的字节单元开始，而2字节字段从偏移量为偶数的字节单元开始。排列整齐的分组使得在协议实现时可以采用诸如“分组模板”等数据结构，从而使分组收发程序的实现得以简

9、化，效率也得以提高。为了便于将描述协议分组的数据结构与分组格式相对照，从而使之更容易阅读和理解，在通用头文件中定义了常量标识符BITS_8、BITS_16和BITS_32。#ifndef BITS_8#define BITS_8 unsigned char#endif#ifndef BITS_16#define BITS_16 unsigned short int#endif#ifndef BITS_32#define BITS_32 unsigned long#endif（3） 变量标识符中单词均使用小写字母，结构和类的成员变量名前加“m_”前缀。（4） 除了指针和句柄变量名前必须分别添加前

10、缀“p-”和“h-”外，其余变量名前通常不加表示数据类型的前缀（如数值前缀“n-”，布尔前缀“b-”，字符串前缀“sz”，等等），只有在通过以下两种方式无法标识变量的数据类型时，才采用标注前缀的方法：一种方式是通过变量名中包含的特征单词来标识数据类型，例如，包含size、number、length、count、interval、time、index等单词的变量均为数值变量，包含单词name、path的变量总是字符串变量，布尔变量名均以助词is或do开始。另外一种方式是通过 “就近声明”的原则来省略数据类型前缀。（5） 对于过长或过多单词构成的标识符，使用了通用和易理解的单词缩写或单词首字头缩写

11、形式。这样做是为了使学生熟悉规范代码中的简写形式，从而有助于学生去阅读源代码。（6） 循环变量使用字母i及其组合（如ii和iii，字母i的重复次数表示循环嵌套层数），或i、j和k分别表示循环嵌套的第1、2和3层。循环嵌套层次不得超过3层。出于占用篇幅和易于阅读的考虑，在描述函数的实现时，构造函数、析构函数和一些实现代码比较简单的类成员函数都在头文件的类定义中进行了描述。但在实际的课程设计中，还是应该将其定义在实现文件中。另外，许多语句的编写没有遵循统一的风格也是出于同样的原因。如有的条件语句是分行编写的，有的则直接编写在了同一行上。在实际实现时，都应分行编写。17.1.2 进程间通信机制和线程

12、间同步机制在进行模拟实现时，每台网络设备通过一个单独运行的进程来模拟，而网络设备上的每个驱动程序则通过进程下各个单独运行的线程来模拟。这样，就涉及到数据包在模拟不同设备的进程之间和在模拟不同协议层驱动程序的线程之间的传递问题。由于在单进程多线程环境中诸线程共享单进程的内存空间，因此，模拟不同协议层驱动程序的线程之间的数据传递问题并不难解决，只要将多线程共享的内存资源定义为进程中的全局变量即可，这时不需要进程间的通信机制。但在多进程环境中，每个进程都有自己的运行空间，不同进程的运行空间是相互隔离的，因此，数据在不同进程之间的传递则要通过各种进程间通信机制（IPC，InterProcess Com

13、munication）来实现。在模拟实现中，该问题是通过内存映射文件（MMF，Memory Mapping File）这一进程间通信机制来实现的。MMF缓冲区共享方案的原理是：首先，在一个单独的进程中调用函数CreateMMF生成一个由系统页文件支持的被命名的共享缓冲区。接着，需要使用缓冲区的进程用生成该缓冲区时所使用的名字调用函数OpenMMF打开共享缓冲区，并通过函数GetMMFView将其映射到自己的进程地址空间中，就可以使用该缓冲区与其它进程交换数据了。注意，无论是生成还是打开共享缓冲区的进程，最后都必须调用FreeMMF，以释放文件映射（映射到内存页）句柄和文件视（映射到进程空间）句

14、柄。在模拟实现中，线程间的同步问题是采用事件通知的方式解决的。其中，处理数据的线程调用函数WaitForEvent睡眠等待一个命名事件（Named Event）；提供数据的线程将数据送入队列后，调用函数SignalEvent通知该命名事件，唤醒因等待数据而睡眠的线程。os.cpp _ #ifndef _OS_H_#define _OS_H_#include <windows.h>HANDLE CreateMMF(char* name, unsigned int size) / Create a paging file-backed MMF. HANDLE hFileMappingO

15、bject = NULL; hFileMappingObject = CreateFileMapping(INVALID_HANDLE_VALUE, NULL, PAGE_READWRITE, 0, size, TEXT(name); if (!hFileMappingObject) return NULL; if (GetLastError() = ERROR_ALREADY_EXISTS) CloseHandle(hFileMappingObject); return hFileMappingObject;/HANDLE OpenMMF(char* name) / Map a view o

16、f the file into the address space. HANDLE hFileMappingObject = OpenFileMapping(FILE_MAP_READ | FILE_MAP_WRITE, FALSE, TEXT(name); if (!hFileMappingObject) return NULL; return hFileMappingObject;/PVOID GetMMFView(HANDLE hFileMappingObject) / map The MMF into the process's address space. PVOID pVi

17、ew = MapViewOfFile(hFileMappingObject, FILE_MAP_READ | FILE_MAP_WRITE, 0, 0, 0); if (!pView) return NULL; return pView;/void FreeMMF(HANDLE hFileMappingObject, PVOID pView) if (pView) UnmapViewOfFile(pView); if (hFileMappingObject) CloseHandle(hFileMappingObject);/void WaitForEvent(char* peventname)

18、 / 以0结束表明事件名的字符串 LPSECURITY_ATTRIBUTES pinherited = NULL; BOOL ismanualreset = TRUE; BOOL isinitstatesignaled = FALSE; HANDLE hevent = CreateEvent(pinherited, ismanualreset, isinitstatesignaled, peventname); if (hevent = NULL) return; DWORD milliseconds = INFINITE; WaitForSingleObject(hevent, millis

19、econds); CloseHandle(hevent); return;/void SignalEvent(char* peventname) DWORD desiredaccess = EVENT_ALL_ACCESS; BOOL is_inherited = FALSE; HANDLE hevent = OpenEvent(desiredaccess, is_inherited, peventname); if (hevent = NULL) return; SetEvent(hevent); CloseHandle(hevent);/#include <process.h>

20、inline unsigned long BeginThreadEx(unsigned ( _stdcall *pFuncName )( void* ) PSECURITY_ATTRIBUTES psa = NULL; unsigned cbStackSize = 0; void *pvParam = NULL; unsigned initfalg = 0; unsigned threadID; unsigned *threadaddr=&threadID; return _beginthreadex(psa, cbStackSize, pFuncName, pvParam, init

21、falg, threadaddr);#endif_ os.cpp17.1.3 通用的数据结构和函数 1内存缓冲区 网络协议对于内存缓冲区的管理提出了许多要求，这些要求包括：能够很容易地处理变长缓冲区；当低层协议对来自高层协议的数据进行封装时，要能够很容易地在缓冲区的头部或尾部添加数据；相反，当数据包在协议栈中向上传递时，要能够很容易地对缓冲区中的协议头结构进行定位；另外，在这些操作过程中要尽可能地减少数据的复制。内存缓冲区的管理方式直接关系着网络协议的性能。 通过对开放源代码操作系统实现中所使用的缓冲区管理方式的研究，在本篇网络协议的模拟实现中使用了一个MBuf结构及其相关函数，来对不同协议层

22、间传递的数据块进行操作。与该结构有关的函数提供了申请数据缓冲区和设置/获取各协议层头指针的接口。由于数据缓冲区是一次性申请和分配的，所以，在发送数据时要根据实际需要估算所需的内存空间。内存空间按照三种规格进行分配：128字节的缓冲区用于较小的数据帧，如ARP请求应答帧、TCP握手控制帧等；2048字节的缓冲区用于一般的数据帧，如以太帧最大长度为1518字节；而65535字节的缓冲区通常用于高层协议封装大量数据时使用，如IP数据包的数据部分最大长度可达65535字节。分配的缓冲区中已经包含了用于协议头结构的空间。mbuf.h_#ifndef _MBUF_H#define _MBUF_Hstruc

23、t Mbuf / Mbuf是为操作在协议层间传递的内存数据块而定义的数据结构 unsigned int m_size; / 缓冲区大小 #define MBUF_SIZE_SMALL 128; #define MBUF_SIZE_MIDDLE 2048; #define MBUF_SIZE_LARGE 65535; unsigned int m_datasize; / 服务数据单元SDU的大小 char* m_pdatahead; / 指明SDU/PDU的开始位置 char* m_pdatatail; / 指明SDU/PDU的结束位置 int m_direction; #define MBUF

24、_DIRECTION_UP 1 / 用于向协议栈上层传递的数据块 #define MBUF_DIRECTION_DOWN 2 / 用于向协议栈下层传递的数据块 struct DEV_NetIf* m_pif; / 接口层填写收到该数据的接口指针 unsigned long m_ip; / IP层填写源IP地址 BITS_16 m_flag; #define MBUF_FLAG_BCAST 0x0001 / 广播 #define MBUF_FLAG_MCAST 0x0002 / 多播;#endif_ mbuf.h在内存缓冲区的实现中，除了申请缓冲区的函数MBuf_Get外，其它函数都以一个MBu

25、f缓冲区指针作为第一个参数。通过修改函数MBuf_Get和函数MBuf_Free的实现，还可以使该结构用于其它类型的缓冲区。如上述的用于进程间进行数据传递的MMF缓冲区。mbuf.cpp_ / 函数MBuf_Get供最初收到或生成数据的例程调用，以分配缓冲数据和协议控制信息/ 的内存块。该数据块在协议层间传递，最后处理数据的协议层负责释放该内存块。struct Mbuf* MBuf_Get(unsigned int size, int direction) struct Mbuf* ptr = NULL; / MBuf首地址 unsigned int bytes = 0; / 初始化数据指针时

26、从尾部计算的字节数 if (size <= MBUF_SIZE_SMALL ) ptr = (struct Mbuf*) new (MBUF_SIZE_SMALL * sizeof(char); if (ptr = NULL) return NULL; ptr->m_size = MBUF_SIZE_SMALL; bytes = 32; else if (size <= MBUF_SIZE_MIDDLE ) ptr = new (MBUF_SIZE_MIDDLE * sizeof(char); if (ptr = NULL) return NULL; ptr->m_si

27、ze = MBUF_SIZE_MIDDLE; bytes = 64; else if (size <= MBUF_SIZE_LARGE ) ptr = new (MBUF_SIZE_LARGE * sizeof(char); if (ptr = NULL) return NULL; ptr->m_size = MBUF_SIZE_LARGE; bytes = 128; ptr->m_datasize = 0; if (direction = MBUF_DIRECTION_UP) / 向上层协议传递的数据块 ptr->m_datahead = ptr->m_data

28、tail = ptr + sizeof(struct MBuf); else if (direction = MBUF_DIRECTION_DOWN) / 向下层协议传递的数据块 ptr->m_datahead = ptr->m_datatail = ptr + ptr->m_size - bytes; ptr->m_flag = ptr->m_flag & 0x00000000; return ptr;/void MBuf_Free(char* pmbuf) / 释放不再使用的空间。 if (pmbuf ) delete pmbuf;/ 函数MBuf_P

29、rependHdr用于添加数据或协议头int MBuf_PrependHdr(struct MBuf* pmbuf, char* pbuf, unsigned int size ) int rv = RV_OK if (pmbuf->m_pdatahead pmbuf sizeof(struct MBuf) > size ) / 前面有足够空间 pmbuf->m_pdatahead = size; / 为复制调整头指针 memcpy(pmbuf->m_pdatahead, pbuf, size); / 复制数据或协议头 pmbuf->m_datasize += s

30、ize; / 加上协议头长度 else rv = RV_MBUF_NOROOM; return ptr;/ 函数MBuf_AppendTail用于添加协议尾，如校验字节等。int MBuf_AppendTail(struct MBuf* pmbuf, char* pbuf, unsigned int size ) int rv = RV_OK if (pmbuf->m_datatail + size) < (pmbuf + pmbuf->m_size) / 后面有足够空间 memcpy(pmbuf->m_pdatatail, pbuf, size); / 复制协议尾 p

31、mbuf->m_pdatatail += size; / 调整指针以包括协议尾部 pmbuf->m_datasize += size; / 加上协议尾部的长度 else rv = RV_MBUF_NOROOM; return ptr;/int MBuf_GetPDUSize(struct MBuf* pmbuf) / 返回当前协议层的PDU大小。 return (pmbuf->m_datatail pmbuf->m_pdatahead);/char* MBuf_GetHdrPtr(struct MBuf* pmbuf) / 获得本层协议头指针。 return pmbuf

32、->pdatahead;/ 函数MBuf_AdjustHdrPtr为向上层协议传递数据块而调整指针，即将指针调整到/ 上层协议数据的开始处。int MBuf_AdjustHdrPtr(struct MBuf* pmbuf, unsigned int size) int rv = RV_OK; if (pmbuf->m_pdatahead + size) > pmbuf->m_pdatatail) rv = RV_MBUF_SIZETOOLARGE; else pmbuf->m_pdatahead += size; return rv;/ 函数MBuf_SetNet

33、IfPtr用于设置指向接收数据包的网络接口的指针void MBuf_SetNetIfPtr(struct MBuf* pmbuf, struct DEV_NetIf* pif) m_pif = pif;/ 函数MBuf_GetNetIfPtr用于获取指向接收数据包的网络接口的指针struct DEV_NetIf* MBuf_GetNetIfPtr(struct MBuf* pmbuf ) return m_pif;/ 函数MBuf_SetSrcIPAddr用于设置接收到的数据包的源IP地址void MBuf_SetSrcIPAddr(struct MBuf* pmbuf, unsigned l

34、ong srcip) pmbuf->m_ip = srcip;/ 函数MBuf_ GetSrcIPAddr用于获取接收到的数据包的源IP地址unsigned long MBuf_GetSrcIPAddr(struct MBuf* pmbuf ) return pmbuf->m_ip;/void MBuf_SetFlag(struct MBuf* pmbuf, int flag) / 设置数据帧为广播或多播帧。 m_flag |= flag;/int flag MBuf_GetFlag(struct MBuf* pmbuf) / 获取广播或多播帧标志。 return (pmbuf-&

35、gt;m_flag);_ mbuf.cpp 2队列和缓冲表相邻协议层间的数据传递接口是队列。此外，协议实现中还经常要用到列表和缓冲表。在模拟实现中用同一个类Cache来完成这三种数据结构的功能。这里没有使用C+ STL库中的模板类list，主要是因为该类没有重载下标运算符“”，且通过迭代子进行循环操作的方式不容易理解。在实现中应该注意，模板类的定义和实现必须在同一个文件中，否则，无法进行编译。cache.h_#ifndef _CACHE_H_#define _CACHE_H_#include "rv.h"#define RV_CACHE 2 / 避免绝对性的宏定义#defi

36、ne RV_CACHE_ALLOCERROR RV_CACHE + 1#define RV_CACHE_FULL RV_CACHE + 2template <typename T>class Cache public: struct LinkList struct LinkList* m_next; / 下一个表项的指针 struct LinkList* m_prev; / 前一个表项的指针 T m_entry; / 在抽象数据类型T中有指针成员时，要 / 注意必须实现赋值操作符"=" *m_head; / 表头指针 int m_entrynum; / 当前链表

37、中表项个数 int m_size; / 用户设置的链表大小 #define CACHE_SIZE_INFINITE 0 /不设置相当于INFINITE / 构造函数和析构函数 Cache(); Cache(int size); Cache(); / 操作函数 const T& operator(const unsigned int index); / 下标操作符重载 int Add(const T entry, int pos); / 添加一个表项 #define CACHE_ADD_POS_HEAD 0 #define CACHE_ADD_POS_TAIL 1 void Remove

38、(unsigned int index); / 删除一个表项 #define Prepend(a) Add(a, CACHE_ADD_POS_HEAD); / 添加表项到表头 #define Append(a) Add(a, CACHE_ADD_POS_TAIL); / 添加表项到表尾 unsigned int GetEntryNum(); / 获得链表中表项个数 bool IsEmpty(); bool IsFull(); #define Enqueue(a) Append(a); / 入队列 #define Dequeue() Remove(0); / 出队列 #define Push(a

39、) Prepend(a); / 入栈 #define Pop() Remove(0); / 出栈 const T& Top(); / 读队首/栈顶表项 void Clear(); / 清除所有表项;/template <typename T>Cache<T>:Cache() : m_head(NULL), m_entrynum(0), m_size(0) /template <typename T>Cache<T>:Cache(int size) : m_head(NULL), m_entrynum(0), m_size(size) /template <typename T>Cache<T>:Cache() if (m_entrynum > 0) Clear(); /templa