公开(公告)号：US06947931B1

公开(公告)日：2005-09-20

申请号：US09544992

申请日：2000-04-06

申请人： Brian Mitchell Bass ,  Jean Louis Calvignac ,  Marco C. Heddes ,  Antonios Maragkos ,  Piyush Chunilal Patel ,  Michael Steven Siegel ,  Fabrice Jean Verplanken

发明人： Brian Mitchell Bass ,  Jean Louis Calvignac ,  Marco C. Heddes ,  Antonios Maragkos ,  Piyush Chunilal Patel ,  Michael Steven Siegel ,  Fabrice Jean Verplanken

IPC分类号： G06F17/30 ,  G06F17/00

CPC分类号： G06F17/30985 ,  H04L45/7457 ,  Y10S707/99931 ,  Y10S707/99933 ,  Y10S707/99936 ,  Y10S707/99942 ,  Y10S707/99943 ,  Y10S707/99945

摘要： Novel data structures, methods and apparatus for finding the longest prefix match search when searching tables with variable length patterns or prefixes. To find the exact match or the best matching prefix, patterns have to be compared a bit at a time until the exact or first match is found. This requires “n” number of comparisons or memory accesses to identify the closest matching pattern. The trees are built in such a way that the matching result is guaranteed to be a best match, whether it is an exact match or a longest prefix match. Using the trail of all the birds and associated prefix lengths enables determination of the correct prefix result from the trail. By construction, the search tree provides the best matching prefix at or after the first compare during walking of the trail or tree.

摘要翻译： 当搜索具有可变长度模式或前缀的表时，用于查找最长前缀的新型数据结构，方法和装置匹配搜索。 要找到完全匹配或最匹配的前缀，模式必须一次比较一下，直到发现确切或第一个匹配。 这需要“n”个比较或存储器访问来识别最接近的匹配模式。 树的建立方式使得匹配结果保证是最佳匹配，无论是完全匹配还是最长匹配前缀。 使用所有鸟的踪迹和相关的前缀长度可以确定路线中正确的前缀结果。 通过构建，搜索树在步道或树的步行期间在第一次比较之前或之后提供最佳的匹配前缀。

公开(公告)号：US06804249B1

公开(公告)日：2004-10-12

申请号：US09548911

申请日：2000-04-13

申请人： Brian Mitchell Bass ,  Jean Louis Calvignac ,  Marco C. Heddes ,  Michael Steven Siegel ,  Fabrice Jean Verplanken

发明人： Brian Mitchell Bass ,  Jean Louis Calvignac ,  Marco C. Heddes ,  Michael Steven Siegel ,  Fabrice Jean Verplanken

IPC分类号： H04L1256

CPC分类号： H04L47/28 ,  H04L45/02 ,  H04L47/2441 ,  H04L47/50 ,  H04L2012/5681

摘要： A system and method of moving information units from a network processor toward a data transmission network in a prioritized sequence which accommodates several different levels of service. The present invention includes a method and system for scheduling the egress of processed information units (or frames) from a network processing unit according to service based on minimum bandwidth specifications where position in the queue is adjusted after each service based on minimum bandwidth specificaiton and the length of frame, a process which is subject to rounding errors. To avoid the accumulation of rounding errors inequitably influencing the position of some in the queue, a system to adjust for the rounding errors adds an increased measure of fairness to the system.

摘要翻译： 一种将信息单元从网络处理器移动到数据传输网络的系统和方法，其以容纳几个不同级别的服务的优先顺序排列。 本发明包括一种方法和系统，用于基于最小带宽规范来调度来自网络处理单元的处理的信息单元（或帧）的处理的信息单元（或帧），其中基于最小带宽规定在每个服务之后调整队列中的位置，并且 帧的长度，一个进行舍入误差的过程。 为了避免累积误差不均衡地影响队列中某些队员的位置，调整舍入误差的系统增加了系统的公平性。

公开(公告)号：US06769033B1

公开(公告)日：2004-07-27

申请号：US09384691

申请日：1999-08-27

申请人： Brian Mitchell Bass ,  Jean Louis Calvignac ,  Anthony Matteo Gallo ,  Marco C. Heddes ,  Ross Boyd Leavens ,  Piyush Chunilal Patel ,  Mark Anthony Rinaldi ,  Michael Steven Siegel ,  Fabrice Jean Verplanken

发明人： Brian Mitchell Bass ,  Jean Louis Calvignac ,  Anthony Matteo Gallo ,  Marco C. Heddes ,  Ross Boyd Leavens ,  Piyush Chunilal Patel ,  Mark Anthony Rinaldi ,  Michael Steven Siegel ,  Fabrice Jean Verplanken

IPC分类号： G06F900

CPC分类号： H04L49/602 ,  G06F15/80 ,  H04L49/351

摘要： A network processor useful in network switch apparatus and methods of operating such a processor in which data flow handling and flexibility is enhanced by the cooperation of an embedded processor complex with a suite of peripherals, all formed on a common semiconductor substrate. The interface processors provide data paths for inbound and outbound data flow and operate under the control of instructions stored in an instruction store formed on the semiconductor substrate, while storage of transiting data flow portions is provided by memory peripherals and interfaces to external memory elements.

摘要翻译： 可用于网络交换设备的网络处理器和操作这样的处理器的方法，其中通过嵌入式处理器复合体与一组外围设备的协作来增强数据流处理和灵活性，这些外围设备都形成在公共半导体衬底上。 接口处理器提供用于入站和出站数据流的数据路径，并且在存储在形成于半导体衬底上的指令存储器中的指令的控制下操作，同时由存储器外围设备和与外部存储器元件的接口提供过渡数据流部分的存储。

公开(公告)号：US06633920B1

公开(公告)日：2003-10-14

申请号：US09479028

申请日：2000-01-07

申请人： Brian Mitchell Bass ,  Jean Louis Calvignac ,  Marco C. Heddes ,  Steven Kenneth Jenkins ,  Michael Steven Siegel ,  Fabrice Jean Verplanken

发明人： Brian Mitchell Bass ,  Jean Louis Calvignac ,  Marco C. Heddes ,  Steven Kenneth Jenkins ,  Michael Steven Siegel ,  Fabrice Jean Verplanken

IPC分类号： G06F1300

CPC分类号： H04L29/06 ,  H04L69/18 ,  H04L69/22

摘要： A system and method of data flow management, particularly in a multiple network processor architecture where a plurality of independent processing units are simultaneously processing information from different frames of input information. The present invention includes first-in-first-out files identifying the individual frames and correlating the frames with the processor to which the frames have been assigned for processing as well as a first-in-first-out file of processed frames for each processor to allow the frames to be processed independently, then reassembled into the same order as the frames had been received without communication between the independent processors. Additionally, the present system supports newly-created frames as well as the concept of flushing the system without regard to frame order whereby frames are sent out to the network as the processing is completed without regard to input order, overriding the system of putting the output frames in the same order as the input frames were received from the network.

摘要翻译： 特别是在多个独立处理单元同时处理来自不同输入信息帧的信息的多网络处理器架构中的数据流管理系统和方法。 本发明包括识别各个帧的先进先出文件，并且将帧与已被分配帧进行处理的处理器相关联，以及每个处理器的处理帧的先进先出文件 以允许帧被独立地处理，然后重新组装成与已经被接收的帧相同的顺序，而没有独立处理器之间的通信。 此外，本系统支持新创建的帧以及刷新系统的概念，而不考虑帧顺序，由此在不考虑输入顺序的情况下处理完成而将帧发送到网络，覆盖输出的系统 与从网络接收输入帧相同顺序的帧。

公开(公告)号：US06584518B1

公开(公告)日：2003-06-24

申请号：US09479751

申请日：2000-01-07

申请人： Brian Mitchell Bass ,  Jean Louis Calvignac ,  Marco C. Heddes ,  Michael Steven Siegel ,  Michael Raymond Trombley ,  Fabrice Jean Verplanken

发明人： Brian Mitchell Bass ,  Jean Louis Calvignac ,  Marco C. Heddes ,  Michael Steven Siegel ,  Michael Raymond Trombley ,  Fabrice Jean Verplanken

IPC分类号： G06F1314

CPC分类号： G06F12/023

摘要： A method and system for queueing data within a data storage device including a set of storage blocks each having an address, a pointer field, and a data field. This set of storage blocks comprises a linked list of associated storage blocks and also a free pool of available storage blocks. The storage device further includes a tail register for tracking an empty tail block from which a data object is enqueued into the linked list. A request to enqueue a data object into the linked list is received within the data storage system. In response to the data enqueue request, an available storage block from the free pool is selected and associated with the tail register. A single write operation is then required to write the data object into the data field of a current tail block and to write the address of the selected storage block into the pointer field of the current tail block, such that the selected storage block becomes a new tail block to which the tail register points.

摘要翻译： 一种用于在数据存储设备内排队数据的方法和系统，包括一组存储块，每个存储块具有地址，指针字段和数据字段。 这组存储块包括相关联的存储块的链表以及可用存储块的空闲池。 存储装置还包括用于跟踪空尾部块的尾部寄存器，数据对象从该尾部块排入链接列表。 在数据存储系统内接收到将数据对象排入链表的请求。 响应于数据排入请求，从空闲池中选择一个可用的存储块并将其与尾部寄存器相关联。 然后需要单个写入操作来将数据对象写入当前尾部块的数据字段，并将所选择的存储块的地址写入当前尾部块的指针字段，使得所选择的存储块变为新的 尾部寄存器指向的尾部块。

公开(公告)号：US06473838B1

公开(公告)日：2002-10-29

申请号：US09477576

申请日：2000-01-04

申请人： Brian Mitchell Bass ,  Jean Louis Calvignac ,  Marco C. Heddes ,  Steven Kenneth Jenkins ,  Michael Steven Siegel ,  Michael Raymond Trombley ,  Fabrice Jean Verplanken

发明人： Brian Mitchell Bass ,  Jean Louis Calvignac ,  Marco C. Heddes ,  Steven Kenneth Jenkins ,  Michael Steven Siegel ,  Michael Raymond Trombley ,  Fabrice Jean Verplanken

IPC分类号： G06F1200

CPC分类号： G06F13/1647 ,  G06F15/167

摘要： The ability of network processors to move data to and from dynamic random access memory (DRAM) chips used in computer systems is enhanced in several respects. In one aspect of the invention, two double data rate DRAMS are used in parallel to double the bandwidth for increased throughput of data. The movement of data is further improved by setting 4 banks of full ‘read’ and 4 banks of full ‘write’ by the network processor for every repetition of the DRAM time clock. A scheme for randomized ‘read’ and ‘write’ access by the network processor is disclosed. This scheme is particularly applicable to networks such as Ethernet that utilize variable frame sizes.

摘要翻译： 网络处理器在计算机系统中使用的动态随机存取存储器（DRAM）芯片中移动数据的能力在几个方面得到了增强。 在本发明的一个方面，并行使用两个双数据速率DRAMS以使带宽增加一倍以增加数据吞吐量。 数据的移动通过为DRAM时钟的每次重复通过网络处理器设置4组完整“读”和4组完整“写”来进一步改进。 公开了一种由网络处理器进行随机“读取”和“写入”访问的方案。 该方案特别适用于利用可变帧大小的诸如以太网的网络。

公开(公告)号：US06185185B2

公开(公告)日：2001-02-06

申请号：US08976430

申请日：1997-11-21

申请人： Brian Mitchell Bass ,  Michael Steven Siegel ,  Norman Clark Strole

发明人： Brian Mitchell Bass ,  Michael Steven Siegel ,  Norman Clark Strole

IPC分类号： H04L1226

CPC分类号： H04L12/1886 ,  H04L47/12 ,  H04L47/15 ,  H04L47/2441 ,  H04L47/32

摘要： Methods, systems and computer program products are provided which control message storms in a network by classifying multiple destination messages into a plurality of broadcast message classes based upon characteristics of the broadcast messages. The number of multiple destination messages for each class of broadcast messages of the plurality of classes of broadcast messages are then counted so as to provide a plurality of broadcast message class counts. Multiple destination messages of a class of broadcast messages are then selectively transmitted based upon the broadcast message class count for the class of broadcast messages.

摘要翻译： 提供方法，系统和计算机程序产品，其通过基于广播消息的特征将多个目的地消息分类为多个广播消息类别来控制网络中的消息风暴。 然后对多个广播消息类的每个类别的广播消息的多个目的地消息的数量进行计数，以便提供多个广播消息类别计数。 然后基于广播消息类的广播消息类别计数来选择性地发送一类广播消息的多个目的地消息。

公开(公告)号：US07167471B2

公开(公告)日：2007-01-23

申请号：US09940758

申请日：2001-08-28

申请人： Jean Louis Calvignac ,  Gordon Taylor Davis ,  Marco Heddes ,  Michael Steven Siegel

发明人： Jean Louis Calvignac ,  Gordon Taylor Davis ,  Marco Heddes ,  Michael Steven Siegel

IPC分类号： H04L12/56

CPC分类号： H04L49/3009 ,  G11C15/00 ,  H04L45/745 ,  H04L45/7453 ,  H04L49/90

摘要： A method and system for identifying a data structure associated with a packet of data. A processor internal to a packet processor may extract one or more fields in a packet header field of a received packet of data to generate a search key. The internal processor may then be configured to select which table, e.g., routing table, quality of service table, filter table, needs to be accessed using the search key in order to process the received packet of data. A determination may then be made by the internal processor as to whether a CAM or a hash table and a Patricia Tree are used to identify the data structure associated with the received packet of data. Based on table definitions in a register, the internal processor may make such a determination.

摘要翻译： 一种用于识别与数据包相关联的数据结构的方法和系统。 分组处理器内部的处理器可以提取接收到的数据分组的分组报头字段中的一个或多个字段以生成搜索关键字。 然后可以将内部处理器配置为选择哪个表，例如路由表，服务质量表，过滤表，需要使用搜索关键字进行访问，以便处理接收的数据分组。 然后内部处理器可以确定CAM或散列表和Patricia Tree是否用于标识与所接收的数据分组相关联的数据结构。 根据寄存器中的表定义，内部处理器可以作出这样的确定。

公开(公告)号：US07953077B2

公开(公告)日：2011-05-31

申请号：US11457952

申请日：2006-07-17

申请人： Jean Louis Calvignac ,  Gordon Taylor Davis ,  Marco Heddes ,  Michael Steven Siegel

发明人： Jean Louis Calvignac ,  Gordon Taylor Davis ,  Marco Heddes ,  Michael Steven Siegel

IPC分类号： H04L12/56

CPC分类号： H04L49/3009 ,  G11C15/00 ,  H04L45/745 ,  H04L45/7453 ,  H04L49/90

摘要： A method and system for identifying a data structure associated with a packet of data. A processor internal to a packet processor may extract one or more fields in a packet header field of a received packet of data to generate a search key. The internal processor may then be configured to select which table, e.g., routing table, quality of service table, filter table, needs to be accessed using the search key in order to process the received packet of data. A determination may then be made by the internal processor as to whether a CAM or a hash table and a Patricia Tree are used to identify the data structure associated with the received packet of data. Based on table definitions in a register, the internal processor may make such a determination.

摘要翻译： 一种用于识别与数据包相关联的数据结构的方法和系统。 分组处理器内部的处理器可以提取接收到的数据分组的分组报头字段中的一个或多个字段以生成搜索关键字。 然后可以将内部处理器配置为选择哪个表，例如路由表，服务质量表，过滤表，需要使用搜索关键字进行访问，以便处理接收的数据分组。 然后内部处理器可以确定CAM或散列表和Patricia Tree是否用于标识与所接收的数据分组相关联的数据结构。 根据寄存器中的表定义，内部处理器可以作出这样的确定。

公开(公告)号：US07440417B2

公开(公告)日：2008-10-21

申请号：US10870730

申请日：2004-06-17

申请人： Anthony Matteo Gallo ,  Marco C. Heddes ,  Ross Boyd Leavens ,  Michael Steven Siegel ,  Jean Louis Calvignac ,  Gordon Taylor Davis

发明人： Anthony Matteo Gallo ,  Marco C. Heddes ,  Ross Boyd Leavens ,  Michael Steven Siegel ,  Jean Louis Calvignac ,  Gordon Taylor Davis

IPC分类号： H04L12/28

CPC分类号： H04L29/06 ,  H04L69/18 ,  H04L69/22

摘要： A system and method of protocol and frame classification in a system for data processing is disclosed, including, analyzing a portion of the, packet or frame according to predetermined tests, and storing characteristics of the packet for use in subsequent processing of the frame. The characteristics are preferably obtained with hardware, which does so quickly and in a uniform time period. The stored characteristics of the packet are then used by the network processing complexes in further processing of the frame. The processor is preconditioned with a starting instruction address or cede entry point and the location of the beginning of the layer 3 header as well as flags for the type of frame.

摘要翻译： 公开了一种用于数据处理的系统中的协议和帧分类的系统和方法，包括：根据预定的测试分析一部分数据包或帧，以及存储该数据包的特性以用于帧的后续处理。 这些特征优选地通过硬件获得，硬件在快速且均匀的时间周期内这样做。 然后，分组的存储特性由网络处理复合体用于帧的进一步处理。 处理器使用开始指令地址或者入门点进行预处理，并且第3层头的开始位置以及帧类型的标志。