（信号与信息处理专业论文）netsim网络仿真系统中mac层协议的研究与实现.pdf

n e t s i m 网络仿真系统中m a c 层协议的研究与实现 摘要 网络仿真技术是伴随着网络的产生而产生的，网络仿真技术是 一种通过建立网络设备，链路和协议模型，并模拟网络流量地传输， 从而获取网络设计和优化所需要地网络性能数据的仿真技术。 本论文的研究内容来源于德国“高等教育中的网络多媒体教学 体系研究及实现”( 2 m n m o d u l e sf o rt h em u l t i m e d i an e t w o r k b a s e dh i g h e re d u c a t i o n ) 课题的子课题一n e t s i m 。n e t s i m 是为 t c p i p 计算机网络技术教学和工程师培训而设计的交互式试验环境 和仿真工具。网络仿真软件的设计和开发是一个非常复杂的系统工 程，涉及到仿真方法学、网络协议分析、软件工程等多方面的内容。 本论文首先简要介绍了计算机仿真，尤其是离散事件系统仿真 的基本理论和基本的建模、仿真方法，这些理论和方法是计算机网 络仿真的基础。此次对通用网络仿真软件的设计进行了分析，描述 了网络仿真软件的设计原理和系统架构。然后对n e t s i m 中m a c 层网 桥协议模块进行了研究，并在现有的计算机网络仿真系统n e t s i m 基 础上进行设计和仿真。具体而言，包括： 网桥中m a c 层的生成树协议的设计与实现 在交换式以太网中虚拟局域网协议的设计与实现 生成树协议和虚拟局域网是网桥的重要功能，它们可以帮助局域 网抑制网络广播风暴。目前这些模块的代码已经完全编写、调试通过， 各模块工作正常。至此，n e t s i m 又增加了m a c 层网桥协议模块，可 以进行更加灵活的应用。 关键词：网络仿真生成树协议虚拟局域网以太网 t h e d e s i g na n di m p l e m e n l ：f 气o n0 f n e t w o r ks i m i 。棚0 ns y s l e m n e t s i m a b s t r a c t n e t w o r ks i m u l a t i o nt e c h n o l o g yi sa c c o m p a n i e db yt h ec r e a t i o no f n e t w o r k , n e t w o r ks i m u l a t i o nc a nc r e a t ev i r t u a ln e t w o r ke q u i p m e n t , l i n k a n dp r o t o c o lm o d e l ，a n ds i m u l a t e dn e t w o r kt r a f f i ct r a n s m i t t e d , o b t a i n n e c e s s a r yt oo p t i m i z en e t w o r kd e s i g na n dn e t w o r kp e r f o r m a n c ed a t a n e t w o r ks i m u l a t i o ns y s t e mc o n s t r u c t sav i r t u a ln e t w o r ke n v i r o n m e n t w h i c hp o s s e s s e st h ec h a r a c t e r i s t i c so fc o n t r o l l a b l ea n dr e p e a t a b l en e t w o r k c o n d i t i o n s t h i sm a k e si t p o s s i b l e t o p r e d i c tt h ec o r r e c t n e s sa n d p e r f o r m a n c e o fn o v e ln e t w o r kp r o t o c o l s ，s e r v i c e s ，a p p l i c a t i o n sa n d c o n t r o la l g o r i t h m sb e f o r ed e p l o y i n gt h e mt oi n t e r a c t t h ec o n t e n to ft h ep a p e rc o m e sf r o mas u b - p r o j e c to fag e r m a n p r o j e c t2 m n ( m o d u l e sf o r t h em u l t i m e d i an e t w o r k - b a s e dh i g h e r e d u c a t i o n ) _ n e t s i m n e t s i mi sa ni n t e r a c t i v es i m u l a t i o ne n v i r o n m e n t t o o ld e s i g n e df o rt c p wn e t w o r k st e a c h i n ga n dt r a i n i n g t h ed e s i g na n d d e v e l o p m e n to fn e t w o r ks i m u l a t i o ns o f t w a r ei s av e r yc o m p l i c a t e d s y s t e m a t i cp r o j e c t ，i n v o l v i n gs i m u l a t i o nm e t h o d o l o g y , n e t w o r kp r o t o c o l a n a l y s i s ，s o f t w a r ee n g i n e e r i n ga n do t h e ra s p e c t so ft h ec o n t e n t f i r s t , t h i sa r t i c l eb r i e f l yi n t r o d u c e st h eb a s i ct h e o r yo fm o d e l i n ga n d s i m u l a t i o nm e t h o d sf o rd i s c r e t ee v e n ts y s t e ms i m u l a t i o n n e x ti tt a l k s a b o u tt h e d e s i g n a n di m p l e m e n t a t i o no fs o m em a cl a y e rp r o t o c o l m o d u l e sb a s e do i lt h en e t s i m s y s t e m ，i n c l u d i n g ： 。t h ed e s i g na n di m p l e m e n t a t i o no fs p a n n i n gt r e ep r o t o c o li n n e t s i m 。t h ed e s i g na n di m p l e m e n t a t i o no fv l a ni nn e t s i m s p a n n i n gt r e ep r o t o c o la n dv i r t u a ll a nb r i d g ep l a yi m p o r t a n tr o l ei n b r i d g e ，t h e yc a nh e l pa v o i d i n gn e t w o r kb r o a d c a s ts t o r m c u r r e n t l y , t h e a b o v em o d u l e sh a v eb e e nf i n i s h e da n dc a nw o r kp r o p e r l yi nn e t s i m ， w h i c hm a k e st h en e t s i ms y s t e mm o r ev a l u a b l e k e yw o r d s ：s i m u l a t i o ns 7 i pv iane t h e m e t 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究成果。尽我所 知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰 写过的研究成果，也不包含为获得北京邮电大学或其他教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢 意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保留并向国家 有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借阅；学校可以公布 学位论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存、汇编学位 论文。( 保密的学位论文在解密后遵守此规定) 本学位论文属于保密在一年解密后适用本授权书。 本人签名：圭d 凶堡日期：1 聋：! ：! ! 导师签名：兰氢盔：1 日期：2 1 12 三：! ! 北京邮电大学硕士论文n e t s i m 网络仿真系统中m a c 层协议的设计与实现 第一章绪论 本章首先会介绍当前世界上网络仿真软件的发展，现状及趋势，接着分析并 介绍n e t s i m 项目背景及其意义，最后简述了本论文研究内容。 1 1 引言 经过多年的发展，以t c p i p 技术为基础的数据通信网络逐渐演化为世界范 围内规模最大的计算机网络i n t e m e t 。近年来，随着数据通信技术的不断发展， 网络的传输带宽和交换能力都有了大幅度的增长，各种新的网络协议和应用也层 出不穷。网络的高速化和复杂化，网络业务的多样化，使得网络协议研究，网络 拓扑设计和网络管理控制变得更为重要和困难。在目前，对网络进行性能与分析 和仿真测试是研究开发新的网络设备的分析大多基于两种方法：理论研究分析方 法。理论分析过于复杂，并且没有公认成熟的网络行为模型作为基础，不太适合 一般研究开发人员使用。仿真分析可以通过仿真软件详细跟踪网络活动细节，准 确的模拟实际网络的各种行为，而且仿真得到的结果更容易进行详细的分析。因 此，网络仿真技术作为辅助网络技术开发和测试的重要手段显得尤为重要。综上 所述，研究先进的网络仿真方法，开发拥有自主知识产权的网络仿真平台是十分 有意义的一个研究方向。 1 2 网络仿真软件的发展、现状及趋势 网络仿真技术是伴随着网络的产生而产生的，网络仿真技术是一种通过建立 网络设备，链路和协议模型，并模拟网络流量地传输，从而获取网络设计和优化 所需要地网络性能数据的仿真技术。 目前，对网络进行性能在网络仿真系统中，仿真方法的研究和网络协议的仿 真是两个重要的方面。通过仿真技术建立的网络模型不仅可以在实施之前预测拓 扑和设备规划，还有助于在网络的运行中保持其有效性。网络结构和规模日趋复 杂庞大，业务种类增加，网络负载日益繁重；设计，构建并运营如此多种网络的 成本投入越来越昂贵。为了避免研发，运营的风险，合理投入成本。需要一个有 效的工具对网络的可靠性和有效性进行客观地评估，从而降低网络建设地投资风 险，缩短网络建设地周期，提高网络建设中决策地科学性。 根据设计目标和应用范围的不同计算机网络仿真软件大致可以分为两类：专 用网络仿真软件和通用网络仿真软件。专用仿真软件一般是以某一个协议或是某 北京邮电大学硕士论文 n e t s i m 网络仿真系统中m a c 层协议的设计与实现 一种网络环境为仿真对象；通用网络仿真软件的仿真对象是多协议平台在各种网 络环境下的行为。其主要目的是帮助研究者验证网络协议的性能，或是专用于仿 真某种类型的网络或是网络设备的性能。通用网络仿真软件可以对多种协议进行 仿真，这类产品一般具有网络拓扑设计、网络业务源和网络网络协议运行过程的 仿真、性能分析等较为完备的功能。代表产品有n s 2 ，o p n e t ，r e a l ，o m n e t + + ， c o m n e ti i i 等，现在实际应用得比较广泛的是o p n e t 和n s 2 ，下面简要介绍一 下这两种产品。 o p n e tm o d u l a r 是o p n e t 公司开发的商业软件，产品主要面向专业人 士，帮助客户进行网络结构、设备和应用的设计、建设、分析和管理。2 o p n e t m o d e l e r ；为技术人员( 工程师) 提供一个网络技术和产品开发平台。可以帮助 他们设计和分析网络、网络设备和通信协议。o p n e tm o d e l e r 具有下面的突出特 点，使其能够满足大型复杂网络的仿真需要： 1 提供三层建模机制，最底层为p r o c e s s 模型，以状态机来描述协议；其次 为n o d e 模型，由相应的协议模型构成，反映设备特性；最上层为网络模型。三 层模型和实际的网络、设备、协议层次完全对应，全面反映了网络的相关特性； 2 提供了一个比较齐全的的基本模型库，包括：路由器、交换机、服务器、 客户机、a t m 设备、d s l 设备、i s d n 设备等等； 3 采用离散事件驱动的模拟机理( d i s c r e t ee v e n td r i v e n ) ，与时间驱动相比， 计算效率得到很大提高。 4 采用混合建模机制，把基于包的分析方法和基于统计的数学建模方法结合 起来，既可得到非常细节的模拟结果，也大大提高了仿真效率。 5 o p n e t 具有丰富的统计量收集和分析功能。它可以直接收集常用的各个 网络层次的性能统计参数，能够方便地编制和输出仿真报告。 6 提供了和网管系统、流量监测系统的接口，能够方便的利用现有的拓扑和 流量数据建立仿真模型，同时还可对仿真结果进行验证。 n s 2 ，是n e t w o r ks i m u l a t o r v e r s i o n2 的简写。在1 9 8 9 年首先由r e a l n e t w o r k s i m u l a t o r 改版而来，当时由v i n t p r o j e c t ( v l r t u a l i n t e r n e t w o r k t e s t b e d ) 这个团体所维护，现在由d a r p a 支持的s a m a n 和由n s f 支持的 c o n s e r 负责。与其它的网络方正软件相比开放源代码是n s 2 最大的特点。这 意味着每个使用者都可以免费的使用它，并可以根据自己的需要修改n s 2 的源 代码，对其进行二次开发。 n s 2 是一个面向对象，离散事件驱动的网络仿真软件，它主要是由0 1 c l 和 c + + 两种语言进行开发的。最初开发n s 2 的目标是为局域和广域的i p 网络提供 仿真工具，发展到现在它已经可以用于无线移动网络和卫星网络的仿真。下图是 2 北京邮电大学硕士论文n e t s i m 网络仿真系统中m a c 层协议的设计与实现 n s 2 的系统架构图，n s 2 采用了编译和解释的双层架构：编译层是系统的基础 由c + + 语言实现，解释层由o t c l 语言来实现。在图中，作为n s 2 的一般用户( 不 是开发者) 大致是位于图的左下部分。你可能会用o t c l 语言来描述网络的拓扑， o t c l 在t e l 语言的基础上增加了面向对象扩展而成。在e v e n ts c h e d u l e r 和 n e t w o r kc o m p o n e n t 这两部分，是由c + + 编写而成的，这是n s 2 离散事件驱动 仿真的核心部分。n e t w o r kc o m p o n e n t 则是n s 中的a g e n tf l o p 、u d e 。) 、 t r a f f i cg e n e r a t o r ( f t p ，c b r 1 这两部分。最底层的c + + 表示整个n s 2 都是 以其作为基础开发语言。 e v e n ts c h e d u l e r u i t c l c l 霎凹c l 爹 t c l 藿 c + + 卜毽a f c h 醅曲j r c 图1 - 1 ：n s 2 系统架构图 图1 - 2 ：c + + 争0 t c ! 对应关系图 n s 设计的出发点是基于网络仿真，它集成了多种网络协议，业务类型，路 由排队管理机制，路由算法。此外，n s 还集成了组播业务和应用于局域网仿真 有关的部分、m a c 层协议。其仿真主要针对路由层，传输层，数据链路层展开， 因此n s 可以进行对固定，无线，卫星以及混合等多种网络的仿真。但它最适用 3 北京邮电大学硕士论文 n e t s i m 网络仿真系统中m a c 层协议的设计与实现 于t c p 层以上的模拟。n s 的特点是源代码公开；可扩展性强；速度和效率优势 明显。 1 3 h e r s i m 网络仿真系统 n e t s i m 是在由德国研究与技术部门资助的多媒体学习和教学网2 m ne l , a t ( m u l t im e d i an e t w o r kf o re l e c t r o n i cl e a r n i n ga n d t e a c h i n g ) 项目中，提出了为 基于计算机的教学和培o f i n 作一个仿真工具和实验环境的子项目。与前文中提到 产品不同，n e t s i m 网络仿真系统的开发的目标是用于t c i i p 计算机网络技术的 教学和培训的一个交互性和演示性强的实验和仿真环境。虽然现有的其他网络仿 真软件也有在教学和培训领域的应用，但是由于其不是为此目的专门设计开发 的，其操作都比较复杂并且不易掌握，使得学习者学习和使用比较不便，难以成 为教学和培训的得力助手。 n e t s i m 是为t c p a p 计算机网络技术的教学和工程师培训而设计的交互式实 验环境和仿真工具。目前，n e t s i m 可以支持的网络设备有：h o s t ，r o u t e r ，h u b ， e t h e r n e t ，t o k e n r i n g ：可仿真的协议有8 0 2 3 ，8 0 2 5 ，a r p ，i p ，r a w i p ，i c m p ， 0 s p f ，r 口2 ，u d p ，t c p ，t e l n e t ，f t p ；并对应用层n e t s i m 提供自己的s o c k e t 接口。 n e t s i m 底层是仿真器，上层以g u i 的形式直观、生动的展现出底层网络的 运行情况。用户可以自己编辑网络拓扑结构，组建并运行自己的实验网，并进行 一系列的实验。用户可以查看协议栈输出，数据包内容，路由表等来获得网络的 运行情况。 1 4 本论文的工作 n e t s i m 作为一个自主研发的网络仿真系统，其设计与开发涉及软件工程，仿 真方法学，网络协议分析等多方面的内容。本论文第二章将介绍系统仿真原理， 并针对网络仿真软件的设计进行讨论；第三章中介绍了本人对网络仿真软件设计 和开发方面得到的一些研究；第四章介绍了n e t s i m 网络仿真系统；第五章和第 六章中将介绍本人在n e t s i m 系统中所做的工作，主要是完成系统中m a c 层协 议模块的设计与实现。 4 北京邮电大学硕士论文n e t s i m 网络仿真系统中m a c 层协议的设计与实现 第二章离散事件系统仿真原理 2 1 系统仿真概论 为了能够全面、正确地理解系统仿真，必须了解系统仿真的对象。本节介绍 了有关系统、模型和系统仿真的基本概念。 2 1 1 系统与模型 系统的定义有许多，这里给出一个一般性的定义。系统是指具有某些特定功 能、按照某些特定规律组织起来的所有物体的总和。系统具有如下基本特征：整 体性、相关性。整体性是指系统是一个整体，其各部分不可分割；相关性是指系 统内部各物体之间以一定的规律联系着，它们的特定关系形成了具有特定性能的 系统。任何系统都存在一下三方面的需要研究的内容，即实体、属性和活动。实 体是指存在于系统中的每一项确定的物体；属性是指实体所具有的每一项有效的 特征；活动只是导致系统状态发生变化的一个过程，活动是一段时间发生的情况， 活动反应了系统的变化规律。 模型是对实际系统的一种抽象，使系统某种本质的描述，是人们对客观世界 反复认识、分析、经过多级转换、整合等形似过程而形成的最终结果，它具有与 系统相似的数学描述或物理属性，以公众可用的形式，给出研究系统的信息正 确建立的模型能更深刻、更具体、更集中地反应试题的主要特征和运动规律，从 而达到对实体的抽象。 2 1 2 系统仿真 系统仿真是以相似的原理，系统技术、信息技术以及其应用领域有关专业技 术为基础，以计算机、仿真器和各种专用物理设备为工具，利用系统模型对真实 的或设想的系统进行动态研究的- - n 多学科的综合性技术。b e r n a r dp z e i g l c 教 授在1 9 7 6 年对系统仿真还做过这样的定义：构造出复杂的真实系统行为模型， 并在计算机上模拟它们。 由此不难看出，真实系统、模型和计算机构成了系统仿真的三要素。除了以 上的三要素，仿真学科的理论体系还涉及到下几个方面理论体系。 1 相似理论 相似理论是研究事物之间相似规律以及其应用的科学，是仿真科学的基本理 5 北京邮电大学硕士论文 n e t s i m 网络仿真系统中m a c 层协议的设计与实现 论。相似是指各事物问某些共性的客观存在，反应了客观世界的特性和共同规律。 所谓形似大致有以下基本类型：几何相似，离散相似，等效，感觉相似，思维相 似。 2 建模理论 建模理论是以各应用领域内的科学理论为基础，建立符合仿真应用要求的， 通用的或专用的各种模型的理论和方法。 3 仿真系统理论 研究和论述构建符合应用需求的仿真系统理论核技术。包括仿真系统的体系 和构成，仿真系统的设计以及公共关键技术，仿真系统的研制和应用 4 仿真方法论 结合各应用的不同需求，研究仿真基本思想和方法。 5 仿真的可信性理论 表述仿真过程及结果评价、控制的概念和方法的基本理论，研究仿真环境和 真实环境的相似性的理论和方法，研究提高仿真可信性的各种方法、技术和规范。 6 仿真科学和技术的应用理论 论述仿真运行实验设计、仿真管理、仿真的可视化、仿真及其结果综合分析 的理论。 2 1 3 连续系统与离散事件系统 根据实际系统的不同性质，我们可以把它们分为两大类：连续系统和离散事 件系统。连续系统是指系统状态变化在时间上是连续的，可以用方程式( 常微分 方程、偏微分方程、差分方程) 描述系统模型，过程控制系统，调速系统等都可 以看作是连续系统。离散事件系统是指系统的状态只是在离散时间点上发生变 化，系统状态的变化称为事件，而这些离散时间点都是随机的，库存系统、交通 控制系统，计算机系统都可以看作是离散事件系统。 2 2 离散事件仿真 离散事件系统是指受事件驱动、系统状态跳跃式变化的动态系统，系统的状 态迁移发生在一系列的离散事件点上。这种系统往往是随机的，具有复杂的变化 关系。离散事件系统大量地存在与我们的周围，超级市场的管理系统、银行服务 系统、交通管理系统等都可以看作是离散事件系统。离散事件系统内部状态变化 是随机的，同一内部状况可以向多种状态转变，很难用函数形式来描述系统内部 状态变化的统计规律。另外，系统内部状态只在离散的随机时间点上发生变化， 6 北京邮电大学硕士论文n e t s i m 网络仿真系统中m a c 层协议的设计与实现 且状态在一段时间内保持不变。因此，在建立离散事件模型时，只需考虑系统内 部状态发生变化的过程 2 2 1 描述离散事件系统的基本要素 为了正确地对系统建模，有必要弄清离散事件系统的一些基本要素：实体、 活动、事件等。 1 实体( e n t i t y ) 与连续系统一样，离散事件系统也是由实体组成的。实体可以分为临时实体 和永久实体两大类。在系统中只存在一段时间的实体叫临时实体，例如计算机系 统中的待处理信息、电话交换系统中的电话呼叫、商店排队等待的顾客以及网络 中的数据包等，系统的工作过程实质上就是这类实体流动和接受加工、处理的过 程。永远存在于系统内的实体叫永久实体。例如上述系统中的计算机设备、电话 交换系统、商店营业员以及网络中的物理设备等。临时实体按一定规律不断到达， 在永久实体作用下通过系统，最后离开系统。系统状态的变化主要也就是有实体 状态的变化而变化。 2 事件( e v e n t ) 引起系统状态变化的行为称为时间。他是在某一时间点的瞬间行为，例如 被处理的信息、电话呼叫、顾客、数据包的“到达”或“离开”。事件不仅用来 协调两个实体之间的同步活动，还用于各实体之间传递信息。 3 活动( a c t i v i t y ) j 把实体所做的或对实体施加的事件称为活动，它是实体在两个事件之间保持 某种状态的持续过程，例如信息处理过程、通话过程、顾客接受服务的过程、数 据包转发的过程。 4 进程( p r o c e s s ) 是由与某类实体相关的时间和若干活动组成的，它描述了这些事件和活动间 的相互逻辑关系和时序关系。例如，顾客到达系统排队开始接受服务一 服务完毕的过程，就构成了一个进程。 2 2 2 。离散事件系统模型 离散事件系统研究和仿真中最基本的问题是系统的建模。许多学者围绕对离 散事件动态系统d e d s ( d i s c r e t ee v e n td y n a m i cs y s t e m ) 建模这个问题从不同层 面或用不同数学工具进行了描述，形成了多种方法体系。例如，根据时间发生时 间对所考察对象演变过程的分析而言是否有必要纳入研究范围，可划分为： ( 1 ) 不带时标的d e d s 模型：有限状态自动机模型，p c t r i 网络模型、过程代数 7 北京邮电大学硕士论文 n e t s i m 网络仿真系统中m a c 层协议的设计与实现 模型、时序逻辑模型等； ( 2 ) 带时标的d e d s 模型：赋时p c t f i 网络模型，t i m r t i l 模型、双子代数模 型、排队网络模型、m a r k o v 链与g s m p 模型等。 或根据系统输入信息及状态演变的确定不确定性，分成确定性d e d s 模型和随 机性d e d s 模型；也可根据状态变化的量化特征，分成逻辑( 定性) 模型与数 量( 定量) 模型等。 离散事件系统的建模，大致按照以下步骤进行：1 ) 明确仿真目的；2 ) 正确 描述系统；3 ) 仿真模型的建立；4 ) 输出函数的确定。 2 2 3 离散事件系统仿真模型 离散事件系统仿真建模的目的，是要建立与系统模型有同构或同态关系能在 计算机上实验的模型。离散事件系统大多是人造系统，系统状态跳跃式变化，具 有复杂的非线性。仿真模型通常采用流图或网络图描述。例如，事件图模型、p e t r i 网络模型、排队网络模型、自动机模型，等等。 下面介绍一下离散事件系统仿真程序的主要成分的： ( 1 ) 仿真时钟，提供仿真时间的当前值。 ( 2 ) 事件表，由策划和事件调度生成事件的名称，时间的二维表，即未来事件 表 ( 3 ) 系统状态变量，描述系统状态的变量。 ( 4 ) 初始化子程序，用于模型初始化。 ( 5 ) 事件子程序，每一类事件的服务子程序。 ( 6 ) 调度子程序，将未来事件插入事件表中的子程序。 ( 7 ) 随机数产生子程序，产生给定分布的随机数的子程序。 ( 8 ) 输出函数子程序，用于系统分析的子程序。 ( 9 ) 统计计数器，用来存放与系统性能分析有关的统计数据的各个变量值。 ( 1 0 ) 主程序，调用上述各种子程序并完成仿真任务全过程。 仿真流程管理( 即仿真调度) 是仿真建模的核心，在此主要讨论时间进程管 理。研究系统一般是为了认识其状态随时间变化的规律，所以需要一个仿真时间 变量。离散时间系统仿真中的时间的变化是用一个逻辑时钟时间数来表示的。除 了实时仿真以外，仿真时间意味着仿真时钟而不是仿真所用“机时”，两者之间 并无直接联系。它与所有实体的活动及所有事件的调度有关系，下面介绍仿真时 钟的两种推进方式： ( 1 ) 时间步长法。在进行系统仿真的同时，可以把整个仿真过程分为许多相等 的时间间隔，时间步长的长度可根据实际问题分别取作秒、分、小时等。程序中 8 北京邮电大学硕士论文n 嘲m 网络仿真系统中m a c 层协议的设计与实现 按此步长前进的时钟就是仿真时钟。 图2 - 1 ：时同步长法流程图 ( 2 ) 事件驱动法。时间步法发是以事件发上的时间为增量，按照时间的进展， 一步一步地对系统的行为进行仿真，知道预定的仿真时间结束为止。 宙 图2 - 2 ：事件驱动法流程图 事件驱动法和时间步长法主要的区别是； ( 1 ) 事件驱动发与时间步长法都是一时间为增量来考察系统状态的变化。但在 9 北京邮电大学硕士论文 n e t s i m 网络仿真系统中m a c 层协议的设计与实现 时间步长法中，仿真时钟是以等步长前进，而在事件驱动法中，仿真时钟的步长 取决于事件之间的间隔。 ( 2 ) 时间步长法在一个步长内，认为系统所处的状态相同，因而所选的步长大 小将影响仿真的精度。而在事件驱动法中，每个事件的发生均有确切的时刻，不 需要人为选取步长，步长的大小对仿真精度的影响较小。 ( 3 ) 时间步长法每步进一个步长就要对整个系统进行一次全面的考察，即时状 态没有发生变化时也要扫描。而事件驱动法只是在某事件发生时才进行扫描。 无论用哪种方法仿真，在仿真过程中每一个时间点上总要判断和比较事件是否出 现。因此，一般地讲，当判断比较的数目较大或事件变化成周期性特点时，用时 间步长法可以节省机时，而当相继两个事件出现的平均间隔较长时，更适合用事 件驱动法。 2 2 4 离散事件系统仿真策略 要将系统模型转换为计算机模型，必须要从总体上确定仿真模型的控制逻辑 和仿真时钟的推进机制，即确定仿真策略。仿真策略是仿真模型的核心，反映了 仿真模型的本质，并从根本上确定了仿真模型的结构。根据离散事件的特点，实 体活动、进程都是以事件为基础构成的，其粒度大于事件。从事件、活动、进程 三个层次来组织事件即构成了处理离散事件模型的三种典型的仿真策略：事件调 度( e v e n ts c h e d u l i n g ) 法、活动扫描( a c t i v i t ys c a n n i n g ) 法和进程交互( p r o c e s s i n t e r a c t i v e ) 法。 事件调度法：事件调度法最早由1 9 6 3 年l a n d 公司m a r k o w i z z 等人提出。 事件是最能反应离散事件系统的本质属性，它是导致系统状态产生变化的操作或 行为，事件发生的时刻称为事件点。事件调度法主要关注的事件点和依次引发的 状态变化。它的基本思想是，将事件例程作为仿真程序的基本模型单元，按时间 发生的先后顺序不断地执行相应的事件例程，用以处理事件发生后对实体状态所 产生的影响，并安排后续事件。 活动扫描法：活动扫描法是在1 9 6 2 年由英国的b u x t o n 和l a s k i 提出。活动 是实体在一段时间内持续进行的操作或过程。活动可能是由多个实体协同完成 的，他总是与一个或几个试题的状态相对应，因此可用事件标识活动的开始和结 束，也就是任意活动都由开始和结束两个事件来表示。活动扫描法主要关注的是 活动和活动的激活条件，其基本思想是：按照各个主动型试题的递减时标变量值 来推进仿真时钟，确定仿真时钟后，按优先次序执行可激活的活动例程，是相关 的事件得以发生，并改变系统的状态和安排相关确定时间的发生时间。 进程交互法：进程交互法是在1 9 6 1 年由i b m 公司的c o r d o n 等提出，在使 1 0 北京邮电大学硕士论文 n e t s i m 网络仿真系统中m a c 层协议的设计与实现 用进程交互的仿真策略时，不一定对所有各类实体都进行进程描述，将系统的演 进过程归结为临时实体的产生，等待和被永久实体处理的过程。进程交互法的基 本思想是，通过所有进程中时间值最小的无条件延迟复活点来推进仿真时钟；当 时钟推进到一个新时刻点后，如果某一实体在进程中解锁，就将该实体从当前复 活点一直推进到下一次延迟发生为止。从计算机程序设计的观点出发，采用活动 扫描法建立的仿真模型是最简单的，这是因为实体活动之间的关系可以由活动的 开始和结束活动例程中的条件进行比较清晰，独立的描述，建模者可以把注意力 集中在测试条件满足后所要完成的工作上。一般说来面向活动仿真模型的基本模 型单元的规模是三种仿真模型中最小的，而且它们之间的独立性较强，在程序的 设计上比较容易实现为独立的程序模块。 总的来说，事件调度法、活动扫描法、进程交互法各有优缺点。事件调度法 建模灵活，可应用范围相对较广。活动扫描法对各事件之间相关性很强的系统来 说，模型执行效率高，但需要用户对各实体的活动进行建模，仿真执行程序也比 较复杂。进程交互法建模最为直观，其模型表示接近真实系统，特别适用于活动 可以预测，顺序比较确定的系统，但是其流程控制复杂，建模灵活性差。在复杂 系统仿真中，按进程来组织事件可以使众多的事件条理清晰，因而成为最通用的 方法。在具体建模时可根据需要采用一种方法，或同时采用几种。 1 1 北京邮电大学硕士论文 n e t s i m 网络仿真系统中m a c 层协议的设计与实现 第三章通用网络仿真软件设计 网络仿真软件的设计和开发是一个非常复杂的系统工程，涉及到仿真方法 学、网络协议分析、软件工程等多方面的内容。本章介绍了事件驱动的网络仿真 软件的一般设计，讨论了仿真器核心工作的原理以及面向对象技术在网络软件开 发中的应用。 3 1 通用网络仿真软件设计目标 通用网络仿真软件的主要功能是模拟各种网络条件对网络协议进行测试和 评估，我们不但可以研究单个协议的运作方式还能够通过仿真软件得到多种协议 之间的相互作用和相互影响。对于仿真的结果，用户希望可以方便的进行统计和 分析。当仿真涉及到大规模网络研究行为时，仿真器的性能也是要重点考虑的问 题。为了满足这些基本的要求，常见网络仿真软件一般都具有以下几个特征： 仿真：作为仿真软件最为基本的一点就是要与真实网络的行为方式尽可能的 致。为了实现这个目的，我们需要仔细研究网络协议，了解他们的工作方式。 有的仿真系统为了能够在最大程度上与实际的协议实现保持一致，甚至直接使用 了操作系统的协议实现库。 抽象：为了满足用户的不同需求，我们在设计网络仿真软件的时候最好能够 提供不同层次的抽象。不同的层次的抽象表现在许多方面，例如，用户可以仅仅 对数据报再带宽受限环境下的行为方式进行抽象，而不去考虑上层的协议的会 话；用户还可以单只研究一个网络协议而暂时不去考虑与上下层次协议的相互作 用。提供不同的层次的抽象不但可以提供给用户更多的灵活性，而且可以提高仿 真软件的效率在较高的抽象环境中我们可以忽略一些细节。主流的仿真工具 如璐，o p n e t ，g l o s i m ，o m n e t + + ，都提供了多种层次的仿真。 脚本生成：在适当的网络设置环境中对通信协议和网络结构进行测试是网络 仿真软件的基本功能。由于用户可能需要在仿真环境中搭建复杂的网络，因此能 够自动生成复杂的流量模型，拓扑结构和动态事件( 例如，线路中断、路由器失 效) 对于一个仿真软件来说就显得十分关键了。 可扩展：尽管我们可以在软件中集成常见的各种网络协议，但是可扩展性对 于网络仿真来说仍有着非常重要的意义。因为网络仿真软件的一个重要的功能就 是设计和研究新的网络协议，我们在设计软件的时候就要考虑到为用户提供方便 的扩展接口。 可视化：可视化是用来帮助我们更简单的理解网络仿真中发生的各种事件。 北京邮电大学硕士论文n e t s i m 网络仿真系统中m a c 层协议的设计与实现 可视化工具不但可以使网络仿真软件应用到教学领域，还可以帮助研究人员更好 的理解协议行为。可视化工具一般都提供了对网络行为的动态展示，有的实现中 是与仿真器同步生成画面( 如o p n e t ) ，有的实现中是通过分析仿真结果生成动 画( 如h a m ) 3 2 仿真器核g , m 作的原理 3 2 1 仿真器 仿真器是仿真软件的核心部分，一般来说网络仿真软件中都采用了上述的离 散事件仿真的策略。通用网络仿真软件中都是把数据包的状态变化看成是相互独 立的事件，仿真器其实就是一个离散事件处理器，整个系统实现了离散事件仿真 的模型。 在实现仿真系统的时候，我们一般要给每个事件加上时间戳，这个时间戳代 表这个事件的发生时间。需要注意的是这里我们所说的时间不是实际的时间，而 是在仿真环境中的时间，即仿真时间。对于时间参数选择什么样的数据类型，不 同的仿真软件有不同的选择。我认为选择浮点数更有优势，使用浮点数保存时间 参数，由于计算机处理浮点数的方式我们很难得到的两个完全相同的浮点数，这 一点十分符合离散事件仿真需要事件发生在不同时间点的特点。另外我们还要考 虑到我们可能需要对网络进行不同层次的仿真，不同层次的事件发生的时间间隔 的数量级是不同的，如果使用整数来表示时间，我们就不得不使用更大的存储空 间来满足系统对整数位长的要求，而使用浮点数就避免了这个问题。这也是1 1 s 和o m n e t + + 都使用了浮点数的原因 离散事件仿真器简单的说就是集成事件调度引擎的仿真事件集合。这部分的 设计关系到仿真软件的仿真效率。离散事件仿真器的工作流程可以用下面的伪码 表示： 初始化离散事件集合 w h i l e 离散事件集合非空a n d 仿真没有被终止 从离散事件集合中取出第一事件 把仿真器时钟设定为事件时间戳 执行事件处理程序 记录事件发生结果 北京邮电大学硕士论文n e t s i m 网络仿真系统中m a c 层协议的设计与实现 ， 仿真解柬 在初始化的过程中我们把最开始的一组事件打上时间戳放入离散事件集合。 紧跟着开始事件处理循环，这个循环的终止条件是离散事件集合中没有事件或是 外部终止指令。循环中的代码很容易理解，需要说明的是在执行事件处理程序的 部分，事件处理程序可能会向离散事件集合中添加新事件或移除己存在的事件。 这里的关键问题就是选择什么样的数据结构作为离散事件集合。早期的仿真 软件都采用了最简单的链表结构，但是这两种结构由于其固有的问题在集合中元 素较多的情况下效率不高。现在流行的实现中大多采用了日历队列算法( c a l e n d a r q u e u e ) ，二叉树( s p l a yt r e e ) ，算法和二叉堆( b i n a r yh e a p ) 。其中在大多数情况 下二叉堆( b i n a r yh e a p ) 是已知的效率最高的算法，在n s 和o r a n e t + + 中都有实 现 3 2 2 仿真时钟及其推进机制 仿真时钟是随着仿真的进程而不断更新的时间机构。仿真时钟是仿真模型中 的时间指示，它代表仿真环境中的时间。通常，在仿真开始时将仿真时钟置零， 随后，仿真时钟不断地给出仿真时间的当前值。仿真时钟一般有两种推进方式： 面向事件和面向时间间隔。面向事件的仿真时钟不是连续推进，而是按照下一个 事件预计要发生的时刻推进，在3 2 1 中的伪码就是采用了这样的机制；而面向 时间间隔的仿真时钟则依据很小的时间区间等距推进，每次推进都需扫描所有的 活动，以检查在此时间区间内是否有一个事件发生，所以这种方式又被称为活动 扫描方式。 一般来说，面向事件的推进方式具有更高的效率，因为我们在离散事件集合 中已经按仿真时间顺序插入了各个事件，仿真开始后只需要按顺序弹出事件即 可。但是在某些特殊的应用中活动扫描方式还是有其独特的优势的。通常在我们 需要仿真器和实际时间进行某种程度同步的时候，比如实时显示仿真结果和模拟 ( e m u l a t i o n ) ，采用活动扫描方式实现更为方便。 3 2 3 队列 在网络仿真软件中，所有的数据包都是存放在队列中，我们用队列来代表链 路和网络设备的各种缓存。为了满足不同应用的要求，我们需要实现不同的队列 调度算法。最为常见的队列调度算法有d r o p - t a i l ( f i f o ) ，r e d ( r a n d o me a r l y d e t e c t i o n ) ，c b q ( c l a s sb a s so u e u e ) 和f q ( f a i rq u e u e ) 。其中最常见的是d r o p - t a i l 和r e d ，我们在数据链路和大部分网络设备的发送，接收缓存都是使用的这种队 1 4 北京邮电大学硕士论文 n e t s i m 网络仿真系统中m a c 层协议的设计与实现 列。其他的队列调度方式，大多应用在路由器的各种调度算法中。在此就不详述 了，简要介绍一下常见的d r o p - t a i l 和r e d 。 1 d r o p - t a i h 先进入队列的数据包捧在队列的最前端可以首先出队，所以有 被称为( f i f o f i r s ti nf i r s to u t ) 系统。当队列已满的时候，想要进入队列 的数据包就被丢弃掉，d r o p - t a i l 由此得名。 2 r e d ：是一种根据平均队长来决定丢包概率的队列调度算法。其思想是队 列会根据概率随机丢弃一些包，这个丢包概率跟队列的长度有关，在队列 越满的时候队列的丢包概率越大。这种算法在t c p 协议中有所应用。 3 3 面向对象技术在网络仿真软件的应用 面向对象( o b j e c t - o r i e n t e d ，o o ) 技术与计算机仿真有着