基于定长单元存储变长分组的队列管理方法及设备

摘要

本发明公开了一种基于定长单元存储变长分组的队列管理方法及设备。其方法是：将队列存储空间划分成等大小的基本缓存单元，并为每个单元设置一个缓存描述符，将这些描述符存在缓存描述符存储表中形成链表；从缓存描述符存储表中为入队分组分配所需的缓存描述符，填写对应的表项信息，给出入队逻辑地址；从缓存描述符存储表中找出出队分组占用的缓存描述符，并给出出队逻辑地址；分组入队或出队后，更新空闲队列信息表和输出队列信息表；由入队逻辑地址，将分组分片搬到队列存储空间中，由出队逻辑地址，将分组分片从队列存储空间中搬出。本发明提高了队列存储空间的利用率，降低了队列维护的复杂度，可用于分组交换系统中。

主权项

一种基于定长单元存储变长分组的队列管理方法，包括如下步骤： （1）将分组交换系统中用于存储分组的队列存储空间划分为m个等长度的基本缓存单元Buffer，并编号为Buffer0，Buffer1，…，Buffer(m‑1)，Buffer(m)，当分组交换系统中有分组进入时，将该分组分片存储到n个基本缓存单元Buffer中，m由队列存储空间的大小决定，n由分组的长度决定，m和n都是正整数且n<m； （2）为每个基本缓存单元Buffer设置一个缓存描述符BD，并编号为BD0，BD1，…，BD(m‑1)，BD(m)，每个BD编号与Buffer号和分组写入/读出队列存储空间的逻辑入队/出队地址相对应； （3）分别配置缓存描述符存储表BD RAM、空闲队列信息表和输出队列信息表，并将所有的缓存描述符BD初始化到一条链表中，并用空闲队列信息表和输出队列信息表共同维护这条链表， 所述缓存描述符存储表BD RAM，用于存放缓存描述符BD，它由m个表项组成，每个表项有4项信息：第一分片标志位F_s、最后分片标志位F_l、有效数据长度L_v和下一跳地址A_n，其中m为基本缓存单元Buffer的个数； 所述空闲队列信息表，用于存放空闲队列状态信息，它由1个表项组成，表项有3项信息：空闲队列长度L₁、空闲队列尾指针P_t1和空闲队列头指针P_h1； 所述输出队列信息表，用于存放输出队列状态信息，它由r个表项组成，一个表项对应一个输出队列且每个表项有4项信息：输出队列最大允许长度L_max、输出队列长度L₂、输出队列尾指针P_t2和输出队列头指针P_h2，其中r为输出队列的个数； （4）在分组入队时，根据分组的大小计算出存储该分组需要的缓存描述符BD个数，然后访问空闲队列信息表和输出队列信息表，查看是否有足够的缓存描述符BD分配给该分组，如果有，则填写缓存描述符存储表BD RAM的相应表项，更新空闲队列信息表和输出队列信息表中相应的表项，给出分组逻辑入队地址，反之，则给出入队失败指示； （5）当某一输出队列有分组出队时，读取并修改缓存描述符存储表BD RAM的相应表项，更新空闲队列信息表和输出队列信息表中相应的表项，给出该分组的逻辑出队地址； （6）按照分组逻辑入队地址，将分组分片存储到队列存储空间中；按照分组逻辑出队地址，将分组分片从队列存储空间中搬出。