数据队列

数据队列（精选8篇）

数据队列 篇1

消息队列是一种进程间通讯机制, 本文对单机消息队列进行了有效的扩展, 使其分布在网络上作为一种基础中间件平台为分布式计算提供服务。随着各种计算机标准的出现和技术的进步, 中间件技术作为软件行业崛起的一个崭新分支, 正在全球范围内迅猛发展, 缺少一个开放的标准是消息中间件不能被大量使用的重要障碍。中间件技术的广泛运用是在最近10年。消息中间件是中间件范畴中发展最快的中间件类型之一。

一、消息队列方法的基本设计

消息队列是操作系统的进程之间用于通信的一种机制, 两个或多个进程间通过访问共同的消息队列完成消息的交换。将消息队列的概念扩展到位于分布式环境下不同站点上应用程序间的通信, 由消息队列机制实现网络上的可靠消息传送, 其中涉及的消息队列有消息接收队列、更新发送表、消息发送管理器和消息接收管理器。

当应用程序在处理数据库修改或更新事务时, 修改更新了本地服务器的数据库中所保存的数据, 同时应用程序将更新信息和更新所执行的SQL (Structured Query Language) 语句以消息的形式写入到更新发送表, 更新发送表的内容和本次本地服务器数据库更新的内容一致。根据服务器软件的设定, 当服务器发起与其他服务器的数据一致操作时, 触发消息发送管理器将更新发送表的内容封装成Message消息发送给其他服务器。对本地而言, 若无异常, 消息将送到目的地址所指示的远端站点的消息接收队列中。同时接送端, 一个后台消息接收管理器一直监视着消息接收队列。当检测到有消息到达时, 开始读取消息, 并根据读到的消息内容恢复成相应的SQL语句, 根据SQL语句对本地数据库执行所描述的更新事务。如果更新成功, 则处理结束, 并返回“更新成功”, 否则返回“更新失败”。此时发送端的消息发送管理器一直监视接收队列, 根据收到的消息类型进行相应的操作, 若各服务器更新成功, 则将该更新发送表内容删除, 若失败, 则周期性地重发该消息。

二、分布式消息队列操作

分布式消息队列的写操作就是向一个已有的消息队列中发送数据的过程。写消息之前, 用户进程应获得其消息队列描述符msqid的值, 然后由msgsnd_d () 系统调用将数据写入由msqid值指定的消息队列。具体过程如下:用户进程调用msgsnd_d () 时, 系统调用msg s nd_d () 首先向本地的守护进程发送“写数据”的请求信息, 在请求信息中包含msgsnd_d () 调用的参数msqid、msgflg和msgp, 然后等待守护进程返回应答信息, 收到应答信息后把结果返回给用户进程, 若是错误信息, 还要设置相应的错误信号errno。守护进程收到“写数据”的请求后也派生出一个子进程处理。从请求信息中分离出参数ms q id、ms g flg和要写入的信息, 然后在ke y值表中查找ms q id, 若不存在则将错误信息返回给用户进程, 若存在则返回其key值表中的ke y值及所在节点的IP值, 然后守护进程根据得到的IP来判断消息队列在本地还是在异地。若在本地则调用msgsnd () 向本地消息队列中写入数据并将结果返回给用户进程;若在异地则根据IP向相应的节点发送包括key、msgflg和要写入信息的“写数据”请求, 在收到应答信息后将结果返回给用户进程。

三、消息队列在分布式系统数据中的应用

分布式数据库系统中的每个网络节点上, 在数据一致性功能模块下, 都由5个功能模块构成:发送更新消息, 接收更新消息, 消息发送管理, 消息接收管理和更新消息处理。

1. 发送更新消息

发送更新消息的功能是向整个网络所有的服务器发送更新消息数据, 由此使其他所有的服务器根据该消息的内容实现与本服务器间的数据一致。发送更新消息通过接收本地服务器所执行的SQL语句中对服务器中数据做出了修改的语句, 接收数据修改信息, 并将接收的数据修改信息封装成消息的格式, 存储在更新发送表中, 在收到发送命令后, 发送给其他服务器, 实现各服务器与本服务器的数据同步。

当发送更新消息收到数据库执行SQL发来的数据修改信息时, 先将数据修改信息封装成消息中的数据信息格式。消息发送命令被触发后, 在消息发送管理器的控制下, 将消息以组播的形式发送给其他所有在线服务的业务服务器, 实现正常情况下的多服务器间的数据同步。

2. 接收更新消息

接收更新消息的功能是实现接收所有数据同步信息 (业务层发来的业务数据、其他服务器发来的数据同步消息) , 并根据收到消息的类型对数据进行相应处理。当收到的数据是业务服务器发送来的业务数据时, 对数据加以解析后将解析的数据存储到相应的缓存区域。当接收到的数据是其他服务器发来的数据同步信息时, 对同步数据加以解析, 解析消息中的数据信息部分, 获取一次业务的所有数据操作并对本服务器数据库中的数据执行相应的SQL语句, 进行相应的操作, 从而实现本服务器与消息发送端服务器之间的数据同步。从而实现了在正常运转情况下的数据同步操作。

3. 消息发送管理

每个服务器在执行对数据库中的数据进行修改操作的SQL语句后, 消息发送管理模块对更新发布表执行插入操作, 添加一条与该条SQL语句相应的消息。服务器触发进行数据一致过程后, 要求与其他服务器进行数据一致, 服务器发送数据一致命令给消息发送管理模块, 消息发送管理模块被触发后将消息信息发送表的内容取出封装成用于传送消息, 并根据当前服务器的拓扑信息将消息发送给其他服务器。当消息发送管理器模块接收到消息收管理模块发来的重新发送请求时, 将消息信息发送表中的数据重新发送给数据同步出错的服务器。

4. 更新消息处理

服务器的接收更新消息模块收到新消息后, 消息接收管理模块要求接收更新消息模块将该消息交给更新消息处理模块。更新消息处理模块接收到消息后, 按照消息编码过程的反过程解析消息。将消息中的数据信息解析为相应的SQL语句, 并根据这一SQL语句对服务器的数据进行更新。如果更新成功则向发送方返回数据更新成功并将本次更新的数据写入数据交换表, 否则返回发送失败。

参考文献

[1]黄姝娟, 杜承烈, 尤涛.中间件技术实时性能的比较[J].计算机工程, 2009, 35 (11) :32-37.[1]黄姝娟, 杜承烈, 尤涛.中间件技术实时性能的比较[J].计算机工程, 2009, 35 (11) :32-37.

[2]徐高潮, 胡亮, 鞠九宾.分布式计算系统[M].北京:高等教育出版社, 2004:23-36.[2]徐高潮, 胡亮, 鞠九宾.分布式计算系统[M].北京:高等教育出版社, 2004:23-36.

[3]勒敏, 刘建辉.分布式数据库系统数据一致性维护方法[J].科技广场, 2008 (3) :31-33.[3]勒敏, 刘建辉.分布式数据库系统数据一致性维护方法[J].科技广场, 2008 (3) :31-33.

数据队列 篇2

队列简称队, 也是一种操作受限的线性表, 只允许在表的一端进行插入, 而在表的另一端进行删除.其特点为”先进先出(FIFO)”,故又称为先进先出的线性表,简单队列如图所示:

循环队列

顺序队列有一个先天不足, 那就是空间利用率不高, 会产生”假溢出”现象,即:其实队列中还有空闲的空间以存储元素, 但我们在判断队列是否还有空间时, 队列告诉我们队列已经满了, 因此这种溢出并不是真正的溢出, 在data数组中依然存在可以放置元素的空位置, 所以说这是一种”假溢出”;

于是我们就引入了循环队列的概念, 将顺序队列臆造为一个环状的空间, 即把存储队列元素的表从逻辑上看成一个环, 称为循环队列,其示意图如下:

注意:如图中所示,我们的循环队列为了在实现上的便利, 会有一个位置的空闲, m_front(如图中的front)指针总会指向一个元素值为空的位置,因此(m_front+1)%capacity才真正的指向队首元素, 而m_rear(图中为rear)才指向一个真实存在的队尾元素;<?www.2cto.com/kf/ware/vc/“ target=”_blank“ class=”keylink“>vcD48cD48cHJlIGNsYXNzPQ==”brush:java;“>//循环队列的实现与解析templateclass MyQueue{ templatefriend ostream &operator<<(std::ostream &os, const MyQueue&queue);public: MyQueue(int queueSize = 64); ~MyQueue; void push(const Type &item); void pop() throw (std::range_error); const Type &front() const throw (std::range_error); const Type &rear() const throw (std::range_error); bool isEmpty() const;private: Type *m_queue; int m_front; //队首指针(其实(m_front+1)%capacity才真正的指向队首元素) int m_rear; //队尾指针 int capacity; //队列的内存大小, 但实际可用的大小为capacity-1};

templateMyQueue::MyQueue(int queueSize): capacity(queueSize){ if (queueSize< 1) throw std::range_error(”queueSize must >= 1“); m_queue = new Type[capacity]; if (m_queue == NULL) throw std::bad_alloc(); m_front = m_rear = 0;}

templateMyQueue::~MyQueue(){ delete []m_queue; m_queue = NULL; m_front = m_rear = 0; capacity = -1;}

templateinline bool MyQueue::isEmpty() const{ return m_front == m_rear;}

templateinline void MyQueue::push(const Type &item){ if ((m_rear+1)%capacity == m_front) //队列已满 { Type *newQueue = new Type[2 * capacity]; //新队列的长度为原队列的2倍 if (newQueue == NULL)throw std::bad_alloc(); int start = (m_front+1)%capacity; //数据序列的起始地址 if (start<= 1) //队列指针尚未回绕 {//只需拷贝一次:从start所指向的元素直到m_rear所指向的元素//std::copy(m_queue+start, m_queue+start+capacity-1, newQueue);std::copy(m_queue+start, m_queue+m_rear+1, newQueue); } else {//需要拷贝两次//1:从start所指向的元素直到数组(不是队列)末尾std::copy(m_queue+start, m_queue+capacity, newQueue);//2:从数组(不是队列)起始直到队列末尾std::copy(m_queue, m_queue+m_rear+1, newQueue+capacity-start); } //重新设置指针位置:详细信息请看下面图解 m_front = 2*capacity-1; m_rear = capacity-2; capacity *= 2; delete []m_queue; m_queue = newQueue; } //队尾指针后移 //注意:此处m_front+1可能需要回绕 m_rear = (m_rear+1)%capacity; m_queue[m_rear] = item;}

templateinline const Type &MyQueue::front() constthrow (std::range_error){ if (isEmpty()) throw range_error(”queue is empty“); //注意:此处m_front+1可能需要回绕 return m_queue[(m_front+1)%capacity];}templateinline const Type &MyQueue::rear() constthrow (std::range_error){ if (isEmpty()) throw range_error(”queue is empty“); return m_queue[m_rear];}

templateinline void MyQueue::pop()throw (std::range_error){ if (isEmpty()) throw range_error(”queue is empty“); //注意:此处m_front+1可能需要回绕 m_front = (m_front+1)%capacity; m_queue[m_front].~Type(); //显示调用析构函数以销毁(析构)对象}

//输出队列所有内容以做测试templateostream &operator<<(ostream &os, const MyQueue&queue){ for (int i = (queue.m_front+1)%(queue.capacity);i<= queue.m_rear; /**空**/ ) { os<< queue.m_queue[i]<< ‘ ‘; if (i == queue.m_rear)break; elsei = (i+1)%(queue.capacity); } return os;}

补充说明

当队列已满时的两类扩充操作:

扩充之后的内存布局:

附-测试代码:

数据队列 篇3

关键词：DNA计算机,队列数据结构,设计及实现

一、基本原理

机器计算的历史可以追溯到1641年, 当年18岁的法国数学家帕斯卡尔成功地制造了一台齿轮传动的八位加法计算机。这使人类计算方式、计算技术进入了一个新的阶段。后经人们数百年的艰辛努力, 终于在1945年成功地研制出了世界上第一台电子计算机。从此, 人类进入了一个全新的计算技术时代。到了21世纪, 可以说是信息时代的大爆炸。新型芯片的诞生使得计算机越来越小, 越来越普及。从最早的帕斯卡尔齿轮机到今天最先进的电子计算机, 其计算方式都是一种物理性质的符号变换, 具体是由“加”和“减”这种基本动作构成的。将计算数据运用进制的方式输入电脑中, 使得人们的计算量加大, 并且计算精准度也相对较高。然而, 目前的DNA计算则有了本质的变化, 计算不再是一种物理性质的符号变换, 而是一种化学性质的符号变换, 即不再是物理性质的“加”“减”操作而是化学性质的切割和粘贴、插入和删除。这种新的计算方式的变革是前所未有的, 具有划时代的意义。

DNA分子链, 是一条双螺旋长链, 上面布满了核苷酸, 共拥有四种碱基:腺瞟呤 (A) 、鸟瞟呤 (T) 、胞嘧啶 (C) 和胸腺嘧啶 (G) , DNA分子的不同排列方式构成了大千世界中生物细胞的信息。数学家、生物学家、化学家以及计算机专家从中得到了启迪, 他们利用DNA能够编码信息的特点, 先合成具有特定序列的DNA分子, 使它们代表要求解的问题, 然后通过生物酶的作用 (相当于加减乘除运算) , 使他们相互反应, 形成各种组合, 最后过滤掉非正确的组合而得到的编码分子序列就是正确答案。

二、目前DNA计算机存在的问题

1. 空间指数暴增的问题

随着问题规模的不断增大, 所需要的DNA数据量也会成一定比例的递增趋势。数值在运算过程中, 随着数据输入的增多而计算机根据DNA链的原理将数据进行捆绑式计算。这样会增加计算的反应难度, 降低了计算程序的反映速率。对于数据程序的控制要求非常高, 造成数值或指数暴增的问题。

2. 编码难的问题

作为较大规模的DNA计算问题, 在编码上存在一定的问题。这就要求一个DNA分子数据在编码的时候需要四个相应的数据来进行编码, 在编码的时候还不能出现差错和编码不一的情况, 编码不一会导致DNA分子的变异。在数据上则表现为数据的乱码和出错问题, 而这也是解决DNA计算机在数据处理上的一大难题。

3. 解码检测难的问题

DNA解码的检测充满了整个计算的始终, 如何快速准确地进行解码也是一个很重要的问题。在将计算机数据进行了编码之后, 在进行计算的时候在进行一组一组的解码也是问题的关键所在, 找不到合理的解码方式会导致前面所做的编码也是一个无用功, 在编码的时候就应该有解码的相应处理, 解码也是DNA计算机的重要症结所在。

三、DNA计算机中队列数据结构的设计

1.“碱基配对互补”原则

在DNA分子链中是运用共价键的方式结合在一起, 使生物活性分子与不溶性载体表面上的反应基团发生化学反应形成共价键, 而这种共价键一般情况下是很稳定的不容易出现断裂或是损坏。在活性酶的作用下运用化学反应的方式才能对共价键造成一定的破坏。而在DNA计算机的运用当中则表现为计算机数据当中数值与数值之间存在的载体的处理, 而这一载体的体现, 通过共价键将数据以电磁的方式固定到电极针上, 根据不同的电极表面, 可采用不同的共价键的方法来对数值进行“碱基配对”从而达到数值的编码与解码问题。

2. 分子标记

在遗传试验与育种实践中, 如果发现了新的基因, 就需要对基因进行标记。而在数据的配对原则中, 也可以根据这种标记的方法对数据进行一定的编码。举个例子说明:在计算机的进制中我们可以将其分为二进制、八进制、十六进制等。而在计算机数据当中我们也可以对一些特殊的数据进行编码, 特别专门进行解码。这样就缓解了数据在处理时出现的乱码或者编码不正确的情况, 使得它的计算速率和错误纠正率得到很大的提高。

DNA计算机是一项新型的信息技术, 在原有计算机的基础上将会使计算机的整体性能得到很大的提高, 这项技术的研究任重而道远, 需要长期的不断探索, 在技术的研究上要不断地更新。同时, 根据DNA分子的特性进行一定的分析与探讨。可以看出, 在DNA计算问题中, 探针DNA分子固定的稳定性是影响着与靶DNA分子杂交效率的重要因素, 将其应用与计算机当中, 能够极大地提高解码检测的灵敏度。高密度和高效率固定化将成为目标, 使其在DNA计算中的应用日趋成熟, 进一步提高DNA计算的有效性和检测的灵敏度。

参考文献

[1]许进, 王淑栋, 潘林强.DNA计算:一种新的计算模式.清华大学出版社, 2004.

[2]方刚.基于三链核酸与压电基因传感器DNA计算研究与探索.华中科技大学, 2006:2-9.

队列创新报数 篇4

一、让学生用英语26个字母进行报数

首先, 全班从第一列横队排头开始至第四列横队排尾结束。其次, 每列横队分别用英语第一字母连续报数。再其次, 四列横队同时用英语第一字母连续报数, 还可以用英语数字ONE……若干单词报数。

二、让学生用22个汉语拼音音节报数

首先, 全班从第一列横队排头开始至第四列横队排尾结束报数。其次, 四列横队分别用汉语拼音音节第一字母连续报数。再其次, 四列横队同时用汉语拼音节第一字母连续报数。还可以从汉语拼音a……若干字母报数。

三、用口号、校风和校训进行报数

师生可以创编口号或利用学校校风、校训等等进行报数。如:好好学习, 天天向上;锻炼身体, 迎接奥运;团结勤奋, 求实创新;文明礼仪, 永争先锋;集中精力, 认真听讲;奥运在我心中, 我为奥运做贡献;更高、更快、更强等等。在这些口号报数中, 可以节选其中的一句进行报数;可以采取四列横队同时报数;可以采用四列横队分别用一句口号报数;可以采用四列横队同时用一句口号报数;可以根据情况四列横队用不同的口号同时, 分别进行报数。

四、用国内外优秀队员的名字进行报数

优秀队员有很多, 如姚明、邓亚萍、张怡宁、刘翔、邓肯……此方法可以采用四列横队用一个运动员的名字进行报数, 也可以采用多个运动员名字分别、同时报数, 也可以用几个队员的名字连续报数。

以上四种报数的方法是我们在教学中报数的创新, 用英语、汉语拼音报数做到了体育课和文化知识课的有机结合, 在体育课中达到了新颖好奇的效果。同时还复习了书本知识, 真正顺应了国际教育改革和国内基础教育的大潮。

用校训、校规、办学理念目标等进行报数, 既教育学生从小要当文明小使者, 也让他们通过体育课得到思想教育的熏陶, 同时给体育课的报数创造了新颖的方法。

为队列队形教学支招 篇5

一、寻找“兴奋点”,促进学生学习兴趣化

在进行队列队形教学前,教师可以利用多媒体播放一些大型团体操和广播操中的队列变化录像,在视觉上和听觉上给学生一个比较强烈的刺激,集中学生注意力、调节情绪、提高兴奋性,形成“先入为主、先声夺人”的美感和节奏感,让学生有跃跃欲试的冲动和表现的欲望。以此激发学生的学习兴趣,寻找“兴奋点”,促进学生学习兴趣化。这就要求教师一方面要深入钻研教材,充分挖掘教材;另一方面要广泛搜集、积累各种素材性课程资源,使抽象的教材内容形象化,使学生能轻松地掌握队列队形练习。

二、掌握“重难点”,凸显教学方法科学化

在队列队形教学中,教师可以利用学生动作易犯的错误,有针对性地将教学的重难点自编学生容易接受的顺口溜。例如,摆臂时:四指微曲握空拳一二一、前摆向中同脐高一二一、后摆有力胸挺直一二一、两眼平视肩不摇一二一;站队时:队列里莫说话,老师就会把你夸。两臂摆动踏步走,嘴里数着一二一;立正时:抬头挺胸收小腹,两脚并拢肩放松。双手紧贴大腿边,双目炯炯视前方。通过科学化的教学方法来激发学生的练习兴趣,使学生对动作要领的掌握和形成良好的精神面貌起到催化剂的作用。

三、探索“结合点”,体现教学内容生活化

在教学原地四面转法时,教师可以设计场景,把操场模拟成热闹的十字路口。让一部分学生来扮演行人和车辆,另一部分学生就模仿交警指挥交通。让“小交警”打着手势让学生进行不同的方向转动,改变以往练习中重复单一的原地四面转法。结合学生的生活实际,寻找“结合点”,使教学内容生活化让学生置身其中,这就需要教师创设情景,把场地布置或用语言描绘成一个特定的场景,利用小学生好奇、爱新鲜的心理特征,激起他们练习的热情。

四、立足“知识点”,实施教学方法多样化

在课前队列队行练习时,教师可以在练习地点用色彩标明练习时的路线,采用跑步、齐步、大小步及舞蹈步等进行练习,还加上了躯干和上肢的配合练习,立足“知识点”,大胆选用适合培养学生创新能力的新教法,力求形式多样,生动活泼,把个人尝试练,自由结组练,小组分别练和整体练等方式结合起来,避免用“军训”的方式进行。来提高学生的兴趣和审美能力,可以很好地完成了教学目标。这就需要教师在练习前必须了解同学们对队列队形练习的实际需要,鼓励同学们大胆进行队列队形的设想和创新。

五、抓住“情感点”,实现教学目标最优化

在齐步走的训练中,教师可以利用多媒体出示国庆阅兵的场面,让学生感觉自己就是一名光荣的解放军战士,教师也要置身其中,扮演好检阅者的角色,用语言激发他们的激情,用口令来指挥他们的行动。同时教师要向部队教官那样,严格要求自己,给学生树立正确的表率;只有教师规范的动作、准确的口令,以及一丝不苟的负责态度,去感化他们,抓住学生的“情感点”,学生才会在信任教师和崇敬解放军战士的心理驱使下,乐于接受队列队形练习,来实现教学目标最优化。

六、发现“错误点”,教学语言幽默化

主动队列管理算法的研究 篇6

随着Internet的蓬勃发展, 网络业务量的不断增长, 人们对网络的服务质量 (QOS) 的要求越来越高。现有的Internet采用的是传统的“尽力而为”的服务机制, 这种机制的优势是设计简单, 但是存在一个主要的问题就是会产生拥塞崩溃现象, 使得链路利用率大大下降, 所以因特网必须提供拥塞控制机制。而传统的TCP端到端的拥塞控制并不能避免拥塞的发生, 所以网络本身的节点就必须自主地参与到拥塞控制中, 依靠网络结点主动感知缓冲区的占有率来管理缓存, 从而有效地避免拥塞的发生。

队列管理是指在网络发生拥塞时, 通过丢包来管理队列长度, 调节缓冲区的占有率, 对队列长度进行管理将直接影响到网络结点的拥塞控制能力和网络的QOS。而目前队列管理机制主要有两大类:被动队列调度机制 (PQM) 与主动队列调度机制 (AQM) 。PQM在因特网上得到了广泛的应用, 但是存在两个重要的问题:死锁和满队列。由于因特网的数据具有突发性, 在满队列的状态下导致了“TCP全局同步”现象, 导致了整个链路的利用率在下降。为此IEFT又提出了AQM, AQM方法是根据队列长度的变化对队列满行提前丢包, 从而预先告之网络拥塞, 使得发送节点在链路缓存溢出前作出反映, 有效减少和避免拥塞的发生。

本文首先简单介绍网络仿真软件NS2的原理, 再对IEFT提出并推荐的AQM主要的算法随机早期检测 (RED) , 与现有网络采用的去尾算法 (Droptail) 在网络仿真平台NS2上进行了仿真研究, 通过队列长度、延迟、抖动、丢包情况和吞吐量进行比较, 最后重点对随机早期检测 (RED) 算法的公平性进行分析。

1NS2网络仿真平台

目前常用的网络仿真工具主要有OPNET、NS等。其中NS是一种针对网络技术的、源代码公开的、免费的软件模拟平台。它是美国DARPA支持的项目VINT (Virtual Internet Testbed) 开发的通用、多协议网络模拟软件, 通过为研究者提供一套网络模拟工具, 更好地促进各种新协议的设计和实施。它能够有效地支持有线和无线网络、局域网和广域网, 具有强大的二次开发能力以及可扩展、易配置的特性, 在国际网络研究界得到了广泛的应用。图1是NS2架构图。

NS是一个离散事件仿真器。NS中有一个“调度器” (Scheduler) 类负责记录当前时间, 调度网络事件队列中的事件, 并提供函数产生新的事件, 指定事件发生的时间。

NS有丰富的构件库。NS构件库支持的网络类型包括广域网、局域网、移动通信网、卫星通信网等;流量产生模型有telnet流量模型、FTP流量模型、CBR流量模型、实时音频流量模型、RTP模型、WEB流量模型、指数分布流量模型、Pareto分布流量模型等;跟踪监测包括包类型、队列监测和流监测;路由模型有点到点传播路由、组播路由、网络动态路由、层次路由。由于NS具有的开放性, 网络研究人员可以根据自己的需要添加各种协议, 满足自己的研究需要。

NS具有分裂对象模型。NS的构件库是用两种面向对象的语言编写的:C++和Otcl (Object Toolkit Command Language) 。NS构件一般都是由相互关联的两个类来实现, 一个在C++中, 一个在Otcl中。这种方式称为分裂对象模型。构件的主要功能在C++中实现, Otcl中的类用来提供C++对象面向用户的接口。通过TclCL机制, 用户可以在C++中直接调用Otcl解释器的功能, Otcl和C++能够互相直接操作对方定义的数据。用户先通过编写C++程序来描述链路中的算法和增加各种网络协议, 再使用Otcl脚本来描述需要仿真的场景、拓扑结构、链路中使用的算法和协议, 并对这些对象进行配置、组合, 最后调用NS来完成仿真[1]。

2Droptail和RED算法分析

2.1Droptail算法

Droptail算法又称FIFO即先进先出, 是一种被动的队列管理机制, 也是当前网络上采用的重要的队列管理方法。其基本的思想就是当网络结点缓存队列长度达到最大值时, 通过丢弃分组来指示拥塞, 先到达路由器的分组首先被传输。由于网络结点的缓存有限, 如果分组到达时缓存已满, 那么网络就丢弃该分组。一旦发生丢包, 发送端立即被告知网络发生拥塞, 从而调整发送速率。这种队列管理机制目前仍然是因特网上使用最为广泛的分组排队、丢弃的方式。但是它将网络发生拥塞的责任全部都推给了网络边缘。所以TCP假设网络中的节点 (如路由器) 对拥塞起不了任何作用, 而由协议本身独立承担检测和响应拥塞的全部责任。这种方式最大的优点是实现很简单;缺点是容易造成队列死锁, 进而导致“TCP全局同步”, 降低了网络的利用率[2]。

2.2RED算法

为了解决全局同步等问题, RED (随机早期检测) 应运而生, 与Droptail相比, RED为队列管理增添了两种机制, 第一, 不等队列完全满的时候再进行丢弃分组, 而是利用节点的缓存占有率情况, 事先丢弃部分分组来预防即将可能发生的拥塞;第二, 通过计算平均队列长度而不是瞬时队列的长度来调整分组丢弃的概率, 以此避免突发的数据流的丢弃。其基本思想就是对拥塞进行提前预测, 在拥塞发生之前就按照一定的概率丢弃分组, 通过分组的丢弃来通知发送端减少进入网络链路的数据量。

对新到的分组, RED路由器首先计算平均队列长度, 将它与预先设置的最大门限值与最小门限值进行比较, 如果介于两者之间, 每个新到达的分组都会按照概率p被丢弃, 而p又是平均队列的函数。在实际应用中, 连接中分组丢弃的概率大致和该连接占用的带宽成正比。简而言之, 对于一个发送量较大的数据流来说, 可供随机丢弃的分组的数量也相对较多[3]。图2是RED算法流程图。

2.3仿真实验及性能分析

为了对两种队列管理机制进行分析, 我们在网络仿真平台NS2上进行了仿真, 操作系统为Windows+Cygwin, 通过实验对Droptail与RED在队列长度、队列延迟、抖动以及吞吐量几个方面的性能进行比较。最后再重点分析了采用RED时, 链路中存在不同数据流时的带宽竞争情况, 也就是RED算法的公平性, 并指出了算法的改进方向。

实验1到实验3采用哑铃网络模型, 网络拓扑结构见图3, 分别在各条链路上配置参数, 链路带宽与时延分别如图3所示, 其中0到1是网络的瓶颈链路, 所有输入都是TCP流, 由FTP驱动。

2.3.1 平均队列长度的比较与TCP全局同步

图4是Droptail队列长度, 很显然Droptail的队列长度较长, 并且图中显示队列长度的变化幅度也很大, 造成这种现象的直接原因是, Droptail算法总是在队列满的时候再进行尾丢弃, 即链路缓存直到满的状态才发送拥塞通知。这就导致了一旦发生拥塞, 所有的发送端就同时降低发送速率, 这样各条链路的队列长度又急剧减少, 链路缓存又处于空闲状态, 接着发送端的所有TCP流又同时提高发送速度, 再一次造成链路缓存急剧增加, 如此反复, 从而产生 “TCP全局同步现象” (如图5所示) , 进而导致了整个链路的利用率在下降。图6是RED的平均队列长度, RED队列的平均长度变化幅度较小, RED算法提前对队列进行丢包, 使得队列长度达到某个长度的时候就通知发端降低发送数据, 避免了缓冲区被完全占满, 如图7所示, RED的TCP窗口变化, 能够在一定程度上避免TCP同步的现象。

2.3.2 队列时延的比较与抖动分析

图8所示为队列时延, 由于Droptail的队列管理机制的特点是直到链路的缓存满的状态才进行丢弃到达的分组, 导致了队列长度有很大幅度的变化, 同时也导致了队列有很大的时延, 而RED由于队列长度变化是按照某个概率进行丢弃, 其链路的缓存变化缓慢, 时延就很小。抖动是时延的变化率, 是与时延相近的概念, 表示的是网络的不稳定性, 如图9所示, 它与图8所示的时延一致。

2.3.3 吞吐量与丢包比较

链路的吞吐量如图10所示, 虽然RED算法在平均队列长度和队列的时延上都比Droptail算法要好, 但是RED算法的链路吞吐量比Droptail要小, 尤其是在开始的阶段。这是因为算法本身不同所引起的, RED由于预先就作好了丢包的准备, 所以在整个过程当中的吞吐量要小于其它两种算法。表1是对两种算法在NS2进行模拟产生的trace文档进行分析所得到的丢包数比较。显然RED的丢包情况要比Droptail算法差, 这也就导致了它的吞吐量要次于Droptail算法。

2.4带宽竞争分析

按传输层协议是否具有端到端拥塞控制机制Internet中的业务可分为响应流 (responsive flow, 如TCP) 和非响应流 (unresponsive flow, 如UDP) 。响应流能根据网络拥塞状况调整发送速率拥塞时降低发送速率, 拥塞减轻后, 又逐渐增加发送速率。非响应流的发送速率与拥塞状况无关。TCP流是一种典型的响应流。当响应流占绝大多数时, 对于Internet的正常运行和多用户共享带宽, TCP的这种端到端拥塞控制机制是行之有效的。然而随着较多非响应流 (如以UDP为传输层协议的IP电话等) 的加入, 情况有可能改变。但由于非响应流对分组丢失不作反应, 网络拥塞时, 响应流降低发送速率, 非响应流仍有可能保持高发送速率。其后果是, 网络拥塞难以缓解, 有限的带宽被非响应流大量抢占, 情况严重时, 还会出现拥塞崩溃[4], 为了在响应流和非响应流并存的环境中维持前者的正常通信, 就有必要考虑带宽竞争问题。下面两个实验分析带宽竞争即算法的公平性, 均采用的是如图11所示的网络拓扑结构。

2.4.1 仅存TCP流的情况

采用图11所示的网络拓扑结构, 仿真时间50s, 节点0-1是瓶颈链路, 带宽是10Mbps, 时延10ms, 其它所有链路的带宽都是45Mbps, 且从发端2到结点0之间以及接点1到接收端5的时延为2ms, 其它链路时延均为20ms, 所有的发端都是TCP流。为了分析算法对带宽分配的影响, 定义公平算子作为评价标准, 有如下定义:整个系统仿真时间t, 瓶颈链路的带宽为B, 发端与接收端的连接数为k, 接收端接收来自相应发端的数据总量为M, 则定义平均速率为V=log (M/t) , 而期望的平均速率为VE=B/k;公平算子J=V/VE。表2是对RED算法公平算子的测量, 由表2可以看出, RED对于响应流TCP流而言, 对时延较小的TCP流FTP1, 它的公平算子比其他时延较大的TCP流要大, 即它占据整个链路的带宽要大。

2.4.2 TCP与UDP在链路上共存

本实验对不同流的goodput[5]作了记录。所谓goodput, 是指除去所有重传分组后获得的吞吐量, 它直接反映出带宽的分配和有效利用程度。对于UDP数据, 由于不存在分组重传, goodput等价于吞吐量。

采用的还是图11的拓扑图, 在进行仿真设置的时候, 节点2、3、4到节点0都是TCP流, 由FTP驱动, 而节点5到节点0是UDP流, 由CBR驱动。为了更好地分析在仿真过程中不同流的带宽占有情况, 设置FTP相继在0.5s、1s、1.5s的时候启动, 在49.5s的时候停止;而CBR在第5s的时候启动, 第15s的时候停止。TCP与UDP共存的公平性仿真如图12所示, tredput1表示TCP流, 而tredput2则表示UDP流, 可以看出RED算法, 属于响应流的TCP连接对丢包很敏感链路发生拥塞的时候会自动通知发端降低发送速率, 而非响应流没有响应机制, 依然保持着高速率的发送, 故在整个仿真时段内, 当出现非响应流UDP的时候, 它几乎占据了瓶颈链路的整个带宽。若提高缓冲区大小, TCP的速率有点提高, 但是继续增大的时候, 两者占据的带宽比已经达到极限, 依然UDP占有大部分的带宽, 这样依然存在很大的不公平性。所以RED算法也不能保证各个连接的带宽的公平性。

3结论

本文通过在NS2上进行的仿真实验, 对Droptail、RED算法的性能进行了比较, 并重点对RED在公平性方面进行了分析。RED算法在队列长度、时延等方面要比Droptail要好, 但是吞吐量较Droptail要略小。如果链路上只存在单一的数据流, 对于RED算法, 那么小时延的链路, 将会占据链路的更多的带宽, 而大时延的链路将占据相对较少的带宽。在链路上同时存在响应流跟非响应流的时候, 带宽竞争是很多算法要面临的问题, 经过分析表明, 当链路上同时存在响应流跟非响应流, RED算法的也不能保证链路上带宽的公平性。针对带宽公平性问题, 很多人提出了不同的改进算法, 如RED-PD对带宽竞争的公平性就有很大的改进。针对如何提高带宽分布的公平性将是以后的努力方向。

参考文献

[1]于斌, 孙斌, 温暖, 等.NS2与网络模拟[M].北京:人民邮电出版社, 2007, 4.

[2]任丰原, 林闯, 刘卫东.IP网络中的拥塞控制[J].计算机学报, 2003, 29 (9) :1025-1034.

[3]李方敏, 李仁发, 欧青立.路由队列管理机制[J].计算机工程, 2001, 27 (8) :29-32.

[4]F loyd S, Fall K.promoting the use of end-to-end congestion control in the Internet.IEEE/ACMTrans.on Networking, 1999, 7 (4) :458-472.

路由器队列调度机制研究 篇7

关键词：视频点播,实时业务,队列调度,区分服务

1 常见路由器队列调度机制

(1) 先进先出队列FIFO调度算法

(2) 优先级队列PQ调度算法

(3) 加权公平队列WFQ调度算法

(4) 差值加权轮训队列DWRR调度算法

2 队列调度算法的性能指标

队列调度算法性能的好坏主要涉及到时延性能、公平性、复杂性这三个方面。

时延性能:队列调度算法应为不同的业务流提供端到端的时延保证, 而且只与此业务流的某些参数 (如带宽需求等) 有关, 而与其他的业务流无关。Stiliadis和Varma首先提出了一种分析网络中不同队列调度算法带来的端到端时延的模型;时延速率调度器 (LRS:Latency2Rate Server) 。Francini随后又提出了另一种分析端到端时延的模型:速率分隔 (RST:Rate2Spaced2Timestamp Scheduler) , 此模型的限制条件比LRS要少且在定长分组环境下应用时更加有效。

公平性:可用的链路带宽必须以公平的方式分配给共享此链路的各业务流:此外队列调度算法必须能够隔离不同的业务流, 让不同的流只享用自己可以享用的带宽, 这样即使存在恶意或高突发性业务, 它也不致影响到其他的正常业务流。关于算法公平的定义有:服务公平指数 (SFI:Service Fairness Index) 和最坏公平指数 (WFI:Worst2case Fairness Index) 两种。

复杂性和可扩展性:调度算法实现起来应该比较简单.在高速网络中, 传输一个分组的时间很小, 所以调度算法必须在短时间里完成对分组的调度, 这就要求调度算法尽量简单, 易于实现。另外当业务流数量增加和链路速率变化范围较大时, 调度算法仍应有效工作;这要求调度算法应该具有良好的可扩展性。

3 现有队列调度算法性能比较

3.1 基于轮询的调度算法

传统的轮循 (RR:Round Robin) 算法对不同队列 (业务流) 进行无区别的循环调度服务.这样, 如果不同的队列具有不同的分组长度, 则分组长度大的队列可能会比分组长度小的队列接受更多的服务, 使队列之间产生不公平的现象;而且, 这种算法不能对业务提供时延保证.后来为了改进RR算法, 出现了一些改进型的算法。如加权轮询 (WRR Weighted Round Robin) , 差额轮询 (DRR Deficit Round Robin) , 紧急轮询 (URR Urgencybased Round Robin) 。

3.2 加权公平队列WFQ调度算法

WFQ调度机制是由Demers等人提出, 又由Parekh等人实现基于报文的PGPS (packet by packet generalized processor sharing) 的排队算法。

WFQ调度机制主要分为基于流的WFQ和基于类的WFQ (CBWFQ) 2种。它们的主要区别在于:前者的队列数在理论上没有限制, 但队列数目太多会增大调度的复杂度, 而后者最多为64个队列。WFQ算法能到达很好的公平性和时延保证, 但是系统其系统需时间函数计算复杂度为O (N) (N为总的队列数) , 且具有较大的WFI, 使得输出的突发度增加。它虽然很好的解决了RR机制的不公平性, 但是包含了GPS调度机制的局限性, 它调度的结果会带来带宽保证和时延保证的耦合性 (即低带宽保证总以为着不严格的时延保证) , 这个特性使得WFQ不适合调度某些类型的业务, 这类业务的特点是带宽需求不大, 但是有着极严格的时延要求, 如语音等实时业务。

3.3 基于时延的调度算法

基于轮询和WFQ的调度算法可以看成是基于速率的调度算法, 这种算法通常为每个队列提供一定的速率保证来达到提供时延保证的目的。而基于时延的调度算法则是以 (为各队列) 直接提供时延保证为目的, 这类算法的代表是最早期限优先 (EDF, Earliest Deadline First) 。

4 基于区分服务的调度算法

区分业务 (Diffserv Differentiated Service) 体系结构正成为解决因特网上服务质量的一种有效的办法, 能支持Diff Serv技术的一个子网被称为Diff Serv域, 它由一些边缘路由器和域内路由器组成, 边缘路由器执行较为复杂的业务流分类、业务量调节及队列管理和调度的功能, 而域内路由器则执行较为简单的队列管理和调度的功能。之前介绍的队列调度都没有边缘交换节点和域内交换节点。都是基于每个业务流的调度算法, 他们需要交换节点维护每个业务流的一些状态信息, 尽管这样可以达到很好的调度性能, 但同时带来了不易扩展和不强壮的缺点。

基于这种考虑, Stocia提出了两种新的调度算法:CSFQ (Core Stateless Fair Queueing) 和CJVC (Core Jitter Virtual Clock) , 其核心在于对交换节点进行了“边界交换节点”和“域内交换节点”的区分, 从而不需要每个交换节点都维护所有业务流的状态信息。

5 结论

一种基于延迟的队列调度实现 篇8

随着网络技术的发展, 各种新应用的出现, 它们要求计算机网络在带宽和延时[1]等方面能提供一定的保证, 特别是多媒体应用对网络服务质量 (QoS) [2,3]的需求更是与日俱增。优先级算法 (PQ) [4]根据各业务对带宽和延时的要求设置优先级, 但PQ算法中优先级的设置是静态的, 不能满足具体变化的需要, 另外PQ算法中存在“饿死”现象, 公平性差。EDF算法[5]是基于时延的调度算法, 它根据任务的截止期 (Deadline) 大小对任务的优先级进行分配, 但EDF算法中延时的计算复杂。文献[[6]]提出了PQBEDF (Priority Queue Based on EDF) 算法, 基于EDF的思想, 对分组的优先级进行设置。每过一个时间片, 每一分组的优先级加1;每次挑选优先级最高的分组转发。截止期是一个时间点, 随着时间的流逝而越来越靠近, 进而优先级也随时间的流逝而提高, 这一点与EDF相吻合。

在PQBEDF算法中, 初始优先级低的业务流因等待时间的增加, 优先级提高而获得服务, 具有一定的公平性, 但是如果出现大量这样的分组, 那么将使得初始优先级高的业务得不到相应的服务, 延迟增加, 带宽得不到保证。此外, PQBEDF算法中要记录每个分组的优先级, 每次调度后还要对其优先级进行设置, 也比较麻烦。为此, 本文对PQBEDF算法进行了修改, 提出PQBEDF_α算法。

1PQBEDF_α算法

1.1 PQBEDF_α算法介绍

在PQBEDF_α算法中, 为了处理的方便也按PQBEDF算法中的方式, 采用等长的数据包[7,8], 各业务流按优先级的大小进入相应的队列中等待调度。对于同一队列中的分组, 它们在队列中存在一定的先后顺序, 并且在队列中的等待时间也有一定联系。只要记录各分组的到达时间, 再根据前一个分组的等待时间, 就可以计算出后一个分组的等待时间, 并由等待时间进而得出相应的优先级。这样就不需要象PQBEDF算法那样为每个分组动态设置优先级了。

在PQBEDF_α算法中, 优先级的增加仍按PQBEDF算法的方式, 分组在队列中每过一个时间片, 优先级增加1, 由于优先级是通过计算得到的, 因此只需设置队头分组的优先级就行了。此外还可将初始优先级设置成阶梯值, 如10, 25, 40等。这样方便处理, 同时也能防止优先级增加过快。

下面对一个队列中的分组进行分析。如果分组i的到达时间用ai表示, 等待时间用wi表示, 假设各分组都恰好在每个时间片的开始时刻到达, 且每个时间片只到达一个分组。那么不难得出如下关系式:

$\begin{array}{l}w{}_2=w{}_1-(a{}_2-a{}_1)\\ w{}_3=w{}_2-(a{}_3-a{}_2)\\ \cdots \\ w{}_n=w{}_{n-1}-(a{}_n-a{}_{n-1})\end{array}$

由w2+w3+…+wn可得:

$w{}_n=w{}_1-(a{}_n-a{}_1)(1)$

式中:a1为队头分组的到达时间。根据分组的等待时间和初始优先级, 由算法可以得出分组的优先级。再假设队头分组的优先级用p1表示, 那么可以得出分组n的优先级为:

$p{}_n=p{}_1+w{}_n=p{}_1+w{}_1-(a{}_n-a{}_1)(2)$

从式 (2) 可以得知, 只要保留队头分组的到达时间a1和优先级w1, 再根据各分组的到达时间, 就可以得出队列中每个分组的优先级。

一般地, 分组并不是按上面假设的情况达到, 而是随意到达的。如果取分组到达时刻所在时间段的整数部分, 如3.4和5.7时间片到达的分组, 取它们到达的时间分别为3和5, 那么在这种情况下, 式 (2) 仍然成立。

下面来讨论调度算法的具体实现。在系统中维持一个时钟, 用于对各分组的到达时间进行计时。数据流flowi中第j个分组的到达时间用aij表示, 队头分组用ai1表示。那么flowi中第j个分组相对队头分组的等待时间之差为aij-ai1。再假设pi1表示队头分组的优先级, 那么由式 (2) 可得队列中任一分组的优先级pij为:

$p{}_{ij}=p{}_{i1}+w{}_{i1}-(a{}_{ij}-a{}_{i1})$

其实在调度过程中并不需要计算每个分组的优先级, 只需要比较各队头分组的优先级, 找出最大的那个分组, 就是将要发送的分组。此外还要保留该分组的到达时间和优先级, 以便计算队列中下一个分组的优先级。若发送分组后队列为空, 则置ai1为0, pi1为pi0, 以便重新开始计算。

下面是算法实现的一个例子, 其中pi0表示flowi的初始优先级。

1.2 堆与动态优先级

下面讨论如何进行查找和比较队头分组的优先级。为了便于节点删除、插入等操作, 将“堆”[9]用于优先级队列是最合适的。由于在查找过程中, 不仅与优先级的大小有关, 而且也与分组所在的队列编号有关, 因此算法使用一种特殊的数据结构:双单元堆。在一个双单元堆中, 每一个节点由两个单元组成, 第一个单元的内容为优先级, 第二个单元的内容为该优先级所对应的队列编号。

首先, 按第一单元的内容采用堆排序的方式对队列中的优先级进行建堆和排序, 再由第二个单元的内容找到相应的队列, 选出队头分组进行发送。堆总是从堆头删除 (最高优先级先得到服务) , 如图1中的“20”, 且无论删除或插入, 其时间复杂度均只有O (log N) 。

1.3 队列长度设置

队列长度是一个十分重要的参数。队列长度过短, 将会导致分组大量溢出;队列长度过长, 又会导致低优先级队列中积压大量分组, 这些分组随等待时间的增加, 优先级变得较高而使得初始优先级高的分组得不到相应的服务, 出现PQBEDF算法中相同的问题。在PQBEDF_α算法中为了避免这种现象的发生, 可以通过队列长度的设置来解决。

队列的长度设置为某一值, 那么队列中分组超过这一范围时将被丢弃。当队列因获得服务而出现空余时, 新到达的分组由于优先级较低, 要获得较高的优先级还需要较长的时间, 这时高优先级业务流就可以获得服务。另外, 高优先级业务流的初始优先级本身就高, 它们在队列中的优先级也随等待时间的增加而增加, 从而使高优先级业务流获得服务的机会要多得多。因此, 只要将低优先级业务流的队列长度设置为某一值, 就可以将低优先级业务的服务次数控制在一定范围内, 进而控制其带宽, 使之不影响高优先级业务流的服务。

在PQBEDF_α算法中, 队列长度的设置, 不仅可以达到丢弃分组, 控制分组流入网络中的流量, 还与分组的等待时间有关系, 影响分组的优先级。

1.4 算法性能分析

PQBEDF_α算法中, 初始优先级低的业务流由于随等待时间的增加, 优先级增大而获得一定的服务, 但队列的长度是一定的, 超过某一范围, 分组将被丢弃。在获得一定服务后, 新到达的分组又将因优先级低而需等待较长时间才能获得服务。对于高优先级业务, 其初始优先级本身就高, 并且它在队列中也随等待时间的增加而增加, 不难看出, 初始优先级高的业务流比初始优先级低的业务流的平均优先级要高得多。因此, 其获得服务的概率也就更大。PQBEDF_α算法从总体上保证了各业务流按初始优先级的大小获得相应的服务。

网络仿真软件采用OPNET Modeler[10,11]。3个源节点的分组生成间隔都是constant (2.8) , 进行仿真, 结果如图2所示。

sink_3表示的是初始优先级较高的业务流在一段时间内获得的平均服务情况, sink_2表示的是初始优先级为中等的业务流在一段时间内获得的平均服务情况, sink_1表示的是初始优先级较低的业务流在一段时间内获得的平均服务情况。从仿真结果可以看出初始优先级高的业务流获得的服务最多, 初始优先级中等的业务流次之, 初始优先级低的业务流最少, 但还是获得了一定的服务。仿真结果表明, PQBEDF_α算法不仅满足高优先级业务流对带宽和延时的要求, 对低优先级业务流也有一定保障, 各业务流按初始优先级的大小获得相应比例的服务, 具有良好的公平性。

2结语

在PQBEDF_α算法中, 优先级的设置是通过对分组的等待时间计算而得到的, 不需要在每次调度后对各分组的优先级动态调整, 大大地简化了优先级设置操作。同时, 通过合理的队列长度设置, 避免了低优先级业务流中较多分组因等待时间的原因达到高优先级, 使得高优先级业务流得不到相应的服务。此外, 它还能保证各业务流按初始优先级的大小获得相应的服务, 具有较好的公平性和合理性。

参考文献

[1]SHENKER S, PARTRIDGE C, GUERIN R.RFC2212Specification of guaranteed quality of service[S/OL].[2001-08-07].http://China-pub.com.

[2]林闯.计算机网络的服务质量[M].北京:清华大学出版社, 2004.

[3]CHARIKAR M, NAOR J, SCHIEBER B.Resource opti-mization in QoS multicast routing of real-time multimedia[J].IEEE/ACM Trans.on Networking, 2004, 12 (2) :340-348.

[4]KUROSE J F, ROSS K W.计算机网络自顶向下方法与In-ternet特色[M].陈鸣, 译.北京:机械工业出版社, 2005.

[5]BAKER T P.An analysis of EDF schedulability on a multi-processor[J].IEEE Trans.on Parallel and Distributed Sys-tems, 2005, 16 (8) :760-768.

[6]钱光明.基于业务的多优先级队列区别服务方案[J].计算机工程与应用, 2006, 42 (10) :118-120.

[7]MCKEOWN N.The iSLIP scheduling algorithm for input-queued switches[J].IEEE/ACM Trans.on Networking, 1999, 7 (2) :188-201.

[8]MARSAN M A, BIANCO A, GIACCONE P, et al.Pack-et-mode scheduling in input-queued cell-based switches[J].IEEE/ACM Trans.on Networking, 2002, 10 (5) :666-678.

[9]梁田贵, 张鹏.算法设计与分析[M].北京:冶金工业出版社, 2004.

[10]陈敏.OPNET网络仿真[M].北京:清华大学出版社, 2002.