【摘要】 路由器多队列数据包缓存管理与输出队列调度系统属于因特网主干网核心路由器技术领域。其特征在于用一片FPGA配合片外数据片存储器和链表存储器构成。该FPGA芯片含有：接收外界数据的数据片FIFO存储器及链表管理电路，链表管理电路通过两个接口电路分别和数据片存储器及链表存储器相连，链表管理电路输出经过队列状态存储器的1024个队列状态信息到队列调度电路，队列调度电路把1024个队列中加权和最大的队列调度出来，并将调度出来的队列编号通过调度结果FIFO存储器送到链表管理电路，链表管理电路通过数据片存储器接口电路，将数据片存储器存储的数据片经数据包发送电路输出。系统支持质量服务，数据包速率为2.5Gbps时，能线速处理进出存储器的数据包。 【专利类型】发明授权 【申请人】清华大学 【申请人类型】学校 【申请人地址】100084 北京市100084-82信箱 【申请人地区】中国 【申请人城市】北京市 【申请人区县】海淀区 【申请号】CN200810103051.1 【申请日】2008-03-31 【申请年份】2008 【公开公告号】CN101252536B 【公开公告日】2010-06-02 【公开公告年份】2010 【授权公告号】CN101252536B 【授权公告日】2010-06-02 【授权公告年份】2010.0 【IPC分类号】H04L12/56; H04L12/02; H04L12/863 【发明人】杨珂; 徐明伟; 赵有健; 全成斌 【主权项内容】1.路由器多队列数据包缓存管理与输出队列调度系统，其特征在于：它含有一个FPGA芯片，作为该FPGA芯片片外存储器的链表存储器，以及同样作为该FPGA芯片片外存储器的数据片存储器，其中： 数据片存储器，被分成大小相等的2(N+1)个存储块，2(N+1)取不小于8192的自然数，每个存储块存储一个数据包的一个数据片，组成每个存储块的存储单元的地址是连续的；同一个输入线卡，具有相同优先权的数据包构成一个队列，每个队列所占用的存储块采用链表的形式进行管理； 链表存储器，用于保存数据片存储器中的所有链表，每一个链表结点保存数据片存储器的一个存储块，链表结点的存储地址和存储块的序列号一一对应，每一个链表结点存储在链表存储器的一个存储单元中，作为链表存储器的存储器，每个存储单元的数据宽度由数据片存储器分成的存储块数量，以及数据片的最大长度决定，具有如下数据结构： 0～N比特位，表示同一队列的下一个链表结点地址， N+1比特位，表示数据包的边界结点， N+2比特位，为存储单元使用的指示标识， N+3～N+K比特位，为数据片长度，K和系统定义的数据片最大值相关，K最大值为8，其中： N+2比特位为1，表示该节点对应的存储块存有数据片，该存储器单元已经被使用，否则置0； N+1比特位为1，表示这是数据包的最后一个数据片，否则置0； N+3～N+K比特位，保存对应数据片的实际长度，长度以4字节为单位； 链表结点分为：数据片队列链表结点和空链表结点； FPGA芯片含有：数据片存储器接口电路、数据片FIFO存储器、数据片输入电路、链表管理电路、数据包输出电路、链表存储器接口电路、队列状态存储器、调度结果FIFO存储器，以及队列调度电路，其中： 数据片FIFO存储器，含有外界数据输入端，所连数据片输入电路输出的读数据信息输入端，还含有指向所连外界数据输入端的快满信号； 数据片输入电路，第一个输入端与所连FIFO存储器的数据片输出端相连，第一个输出端与所连链表管理电路的数据片输入端相连，而第二个输入端则与所连链表管理电路的快满信号输出端相连； 队列状态存储器，是由4个双端口的片内RAM存储器组合而成，其数据输入端口和所连链表管理电路的数据输出端相连，若输入的队列含有至少一个完整的数据包，则队列对应的存储单元置1，反之，置0，它的读地址和读信号队列调度电路，组成队列状态存储器的每个RAM存储器读写端口地址线、数据线宽度不同，读端口地址线有3根，输出数据位宽为32位，它的写端口，有8根写地址线，但写入数据宽度为1位； 队列调度电路，数据输入端和所连队列状态存储器的数据输出端相连，而该队列调度电路的数据输出端和所连队列调度结果FIFO存储器的输入端相连； 队列调度结果FIFO存储器，它的输入端和所连队列调度电路的输出端相连，同时它输出快满信号给队列调度电路，它的输出端和链表管理电路相连，而读信号也链表管理电路； 数据片存储器接口电路，两个输入端分别和所连数据片输入电路、链表管理电路的数据输出端相连，同时，另外又和数据片存储器相连； 链表存储器接口电路，分别和所连链表管理电路、链表存储器互联； 数据包输出电路，数据包输入端与所连数据片存储器接口电路的输出端相连，另外还有一个数据包输出端和外界相连； 链表管理电路，含有：存储器、寄存器和内部逻辑控制电路，用于管理片外的链表存储器，最多管理1024个链表队列，其中： 存储器，含有：队列含数据片个数存储器、队列含数据包个数存储器、链表队列头地址存储器、链表队列尾地址存储器以及待发送数据片首地址FIFO存储器，其中： 链表队列头地址存储器，是双端口存储器，地址宽度为10位，数据宽度为N+1位，各个存储单元存放不同队列的链表头地址，以便索引某个队列的第一个数据片链表结点地址和相应的数据片； 链表队列尾地址存储器，是双端口存储器，地址宽度为10位，数据宽度为N+1位，各个存储单元存放不同队列的尾地址，以便索引某个队列的最后一个数据片链表结点地址和相应的数据片； 队列含数据片个数存储器，是双端口存储器，地址宽度为10位，数据宽度为N+1位，各个存储单元存放不同队列含数据片个数信息； 队列含数据包个数存储器，是双端口存储器，地址宽度为10位，数据宽度为N+1位，各个存储单元存放不同队列含数据包个数信息； 待发送数据片首地址FIFO存储器，是一个先入先出FIFO队列存储器，数据宽度为N+1比特，深度为8，存储4个数据后，发出快满信号； 寄存器含有：空链表头指针寄存器、空链表下一个头指针寄存器、空链表尾指针寄存器、数据片队列头指针寄存器、数据片队列尾指针寄存器、外存含数据片个数寄存器，每个寄存器的位宽为N+1位，其中：数据片队列头指针指定当前队列第一个数据包的第一个数据片的结点地址，数据片队列尾指针指定当前队列最后一个数据包的最后一个数据片的结点地址； 内部逻辑控制电路，对链表管理电路内的存储器和寄存器进行数据信息和控制信息的交互，同时对所连数据片存储器接口电路、数据片输入电路、链表存储器接口电路、队列状态存储器，以及调度结果FIFO存储器进行控制信息和数据信息的交互； 队列调度电路，由队列加权和更新电路、1024选1数据比较器构成，其中： 队列加权和更新电路，含有：队列调度结果存储器、队列加权和存储器以及加权计算电路，其中： 队列调度结果存储器，是一个双端口存储器，输入端与1024选1数据比较器的输出端相连，也与加权计算电路相连，从加权计算电路中输入存储器读地址和读信号，输出端和加权计算电路相连，输出队列调度结果； 队列加权和存储器，是一个双端口存储器，与加权计算电路相连，输入输出每个队列的加权和W； 加权计算电路，从队列状态存储器得到两个线卡共128个优先权队列的状态信息，同时根据队列调度结果存储器保存的最后一次1024个队列的调度结果，按以下方式计算出2个线卡128个队列的加权和，对于某线卡优先级为m的数据包队列： 若：通过队列调度结果存储器，知道最近一次调度中它没有被选中，但从队列加权和存储器了解其以前加权和为W，且从队列状态存储器输入值了解该队列含有完整未发送的数据包，则优先级为m的队列新的加权和为W+m； 若：最近一次调度它未被选中，以前的加权和为W，该队列不含有未发送数据包，则优先级为m的队列新的加权和为0； 若：最近一次调度被选中，该队列以前的加权和为W，且含有完整未发送的数据包，则优先级为m的队列新加权和为m； 若：最近一次调度被选中，以前的加权和为W，但不含有完整未发送的数据包，则优先级为m的队列的新加权和为0， 加权计算电路输出：每次输出2个线卡号，以及每个线卡64个队列的加权和，它实现16个线卡的1024个数据包队列加权和更新； 1024选1数据比较器含有：加权和比较和当前加权和最大的优先级生成电路，以及16选1数据比较器电路，其中： 加权和比较与当前加权和最大的优先级生成电路，共分两组，每组由延时电路、64选1数据比较器和线卡加权和最大优先级更新电路组成，两个延时电路分别输入0-7线卡号及8-15线卡号，两个64选1数据比较器分别输入相应线卡内64个队列的各自加权和，各自输出一个线卡的64个队列中队列加权和的最大值，该最大值是通过同一线卡的64个队列中，每个队列的加权和经过俩俩比较以后，得到的；而两个线卡加权和最大优先级更新电路共同输出更新后的16个加权和及16个加权和对应的线卡号； 16选1数据比较器电路，含有两个含优先级输入的8选1数据比较器及一个2选1数据比较器，两个含优先级输入的8选1数据比较器共同输入16个更新后的队列加权和，共同输出其中两个最大的加权和及相应的最大加权和队列编码，而2选1数据比较器则从输入的2个加权和及相应编码中挑选一个最大的输出； 构成64选1的8选1数据比较器和16选1数据比较器电路的含优先级输入的8选1数据比较器都包含28个16位数据比较器，一个多路选择器，16位数据比较器有A和B 2个16位输入数据，复位RESET是16位数据比较器的复位端，如果A大于或等于B，16位数据比较器的输出AgeB为1，否则为0，16位数据比较器完成2个16位数据的比较需要耗费一个时钟周期，对应8选1数据比较器或含优先级输入的8选1数据比较器，让8个输入数据A8～A1，进行俩俩比较，根据所有的比较结果，可以确定8个输入数据中，哪一个最大；如果A8≥A7，A8≥A6，A8≥A5，A8≥A4，A8≥A3，A8≥A2，A8≥A1都成立，则A8就是最大数，否则，若A7≥A6，A7≥A5，A7≥A4，A7≥A3，A7≥A2，A7≥A1都成立，则A7就是最大数，以此类推，通过28个16位数据比较器和一个多路选择器的配合，可以从8个输入数据中选择到一个最大数据，8选1数据比较器完成一次运算需要2个时钟周期； 队列调度电路把从1024选1数据比较器得到的加权和最大的队列及其编码送往调度结果FIFO存储器，由链表管理电路读取后，通过链表管理电路的运行，得到调度成功队列队头数据包的所有数据片在数据片存储器存储的首地址，这些地址保存在待发送数据片首地址FIFO存储器，通过该FIFO存储器，发往数据片存储器接口电路，数据片存储器接口电路从FPGA片外数据片存储器读取数据包的每一个分片，发送到数据包输出电路，通过数据包输出电路输出。。 【当前权利人】清华大学 【当前专利权人地址】北京市100084-82信箱 【专利权人类型】公立 【统一社会信用代码】12100000400000624D 【引证次数】3.0 【自引次数】2.0 【他引次数】1.0 【家族引证次数】3.0 【家族被引证次数】28
