US7269697B1

Apparatus and methodology for an input port scheduler

Summary by NHIP

Input Port Scheduler Apparatus

The apparatus manages reading activity for multiple read hubs accessing different memory banks within a single operation cycle. A scheduler defines hubs as active or inactive and classifies active hubs into low speed or high speed modes based on packet read rates, dynamically adjusting these counts according to traffic conditions.

Claim Score by NHIP

Read claim 68, the broadest

Abstract

A scheduler to manage the reading activity of a plurality of read hubs is described. Each read hub is capable of reading a piece of a packet from a different memory bank within a same cycle of operation so that pieces of different packets can be read from the memory banks within the same cycle of operation. The scheduler: 1) defines each read hub as an active read hub or inactive read hub, wherein an active read hub is engaged to read at least one packet from the memory banks and an inactive read hub is not so engaged; 2) defines each active read hub as a low speed mode read hub or a high speed mode read hub, wherein, a first packet read by a high speed mode read hub is read from the memory banks at a faster rate than a second packet read by a low speed mode read hub; and, 3) dynamically changes the number of active read hubs, the number of low speed mode read hubs and the number of high speed mode read hubs in light of traffic conditions.

US7269697B1, drawing sheet 1 — Sheet 1 of 19

Term

Term ended

Expired 23 November 2025, 0.8 years ago.

92 claims: 3 independent, 89 dependent

1
An apparatus, comprising:a scheduler to manage the reading activity of a plurality of read hubs, each read hub capable of reading a piece of a packet from a different memory bank within a same cycle of operation so that pieces of different packets can be read from said memory banks within said same cycle of operation, said scheduler to: 1) define each read hub as an active read hub or inactive read hub, wherein an active read hub is engaged to read at least one packet from said memory banks and an inactive read hub is not so engaged;2) define each active read hub as a low speed mode read hub or a high speed mode read hub, wherein, a first packet read by a high speed mode read hub is read from said memory banks at a faster rate than a second packet read by a low speed mode read hub;and 3) dynamically change the number of active read hubs, the number of low speed mode read hubs and the number of high speed mode read hubs in light of traffic conditions.
24
An apparatus, comprising:a) a plurality of read hubs, each read hub capable of reading a piece of a packet from a different memory bank within a same cycle of operation so that pieces of different packets can be read from said memory banks within said same cycle of operation, each of said read hubs comprising: a plurality of registers, each one of said registers to help generate a read address to a different one of said memory banks, each of said registers arranged in a ring so that each register can pass a pointer value toward a next register within said ring, said ring of registers further comprising a multiplexer between each of said registers, each multiplexer having an output path that flows toward a next register within said ring relative to said multiplexer, each multiplexer to introduce a pointer value to said ring at said next register within said ring;and b) a scheduler to manage the reading activity of said plurality of read hubs, said scheduler to: 1) define each read hub as an active read hub or inactive read hub, wherein an active read hub is engaged to read at feast one packet from said memory banks and an inactive read hub is not so engaged;2) define each active read hub as a low speed mode read hub or a high speed mode read hub, wherein, a first packet read by a high speed mode read hub is read from said memory banks at a faster rate than a second packet read by a low speed mode read hub;and 3) dynamically change the number of active read hubs, the number of low speed mode read hubs and the number of high speed mode read hubs in light of traffic conditions.
68
Broadest claimClaim Score 69, broad(NHIP)A method, comprising:dynamically changing a number of active read hubs, a number of low speed mode read hubs and a number of high speed mode read hubs over time in light of changing traffic conditions, each of said read hubs to read information from a plurality of memory banks, each of said read hubs having a high speed mode and low speed mode.

Independent claims3

137 paragraphs in 4 sections, as filed

FIELD OF INVENTION

The field of invention relates generally to networking; and, more specifically, to an apparatus and methodology for an input port scheduler.

BACKGROUND

Computing systems are typically viewed as a processing core that is coupled to a plurality of “Input/Output” (I/O) devices. The processing core is often viewed as the central intelligence function of the computing system, while the I/O devices are often viewed as a means for sending information to the processing core and/or receiving information from the processing core.

A good example is a large computing system such as a UNIX based server or workstation. The processing core of a large computing system is usually implemented as a plurality of general purpose processor chips and a system memory that together execute the system's software routines. The I/O devices of a server or workstation are often implemented as some sort of “plug in” device (peripheral or otherwise). Examples of I/O devices within a server environment tend to include a graphics display, a networking interface, a data storage device (e.g., disk array unit), etc.

Large computing systems have traditionally used a bus to communicatively couple most all of the I/O devices to the processing core. For example, if a server's software requires a file from a disk drive unit, the file is transported from the disk drive unit to the processing core over a bus. Because a bus is a passive group of wires that are physically coupled to a plurality of I/O devices (or a plurality of I/O device connectors), typically, a number of different I/O devices are designed to communicate with the processing core over the same bus.

As such, system congestion (wherein two or more different I/O devices are contending for the resources of the bus) is not an unlikely occurrence. For example, if a disk drive unit and networking interface share the same bus; and, if both have information to send to the processing core at approximately the same time; then, one of the I/O devices has to wait for the other before its communication can commence (e.g., the networking adapter card, before sending information to the processing core, has to wait until the disk drive unit has sent its information to the processing core).

In cases where the processing core is of lower performance, no real loss in computing system performance is observed. That is, in a sense, if the processing core is only capable of handling the information from the I/O devices “one at a time” (e.g., if the processing core in the above example does not posses the resources to process the networking adapter card's information even if it was received “in parallel” with the disk drive unit's information), then the computing system may be said to be “processing core constrained”; and, there is no real loss in system performance as a result of the inefficiencies associated with the communication of the I/O devices over a shared bus.

The trend, however, is that processing core performance of large computing systems is outpacing bus performance. Semiconductor manufacturing technology improvements (which provide faster and more functionally robust processor chips) as well as “multi-processor” processing core designs (e.g., wherein a plurality of processor chips are designed to work together as a cooperative processing whole) have resulted in high performance processing core implementations that can simultaneously handle the emissions from two or more I/O devices.

As such, true losses in computing system performance are being observed for those high performance systems having a bus design between the processing core and the I/O devices of the system. In order to combat this trend, various system design approaches that “work around” the use of a bus as the principle means of communication between the processing core and the I/O devices have been proposed. One of these, referred to as “Infiniband”, embraces the use of a switching fabric between the processing core and the I/O devices. <figref idref="DRAWINGS">FIG. 1</figref> shows an example of an Infiniband or other switching fabric based architecture.

The processing core of the computing system 100 shown in <figref idref="DRAWINGS">FIG. 1</figref> may be viewed as the collection of hosts 1011 through 1016. Each of the hosts 1011 through 1016 has an associated processor 1031 through 1036 that may be assumed to have its own associated memory. Each of the hosts 1011 through 1016 are coupled to a switching fabric 104 via their own host channel adapter (HCA) 1021 through 1026. In a sense, each of the HCAs 1021 through 1026 act as a media access layer for their corresponding processor (e.g., by preparing and receiving packets that are sent/received to/from the switching fabric 104).

The I/O devices of the computing system are referred to as its “targets” 1071 through 1076. Each of the targets 1071 through 1076 has an associated I/O unit 1081 through 1086 (e.g., a gateway to another network, a file server, a disk array, etc.) and target channel adapter (TCA) 1091 through 1096. Similar to the HCAs 1021 through 1026, the TCAs 1091 through 1096 act as a media access layer for their corresponding I/O (e.g., by preparing and receiving packets that are sent/received to/from the switching fabric 104).

The I/O units 1081 through 1086 are communicatively coupled to the processors 1031 through 1036 through the switching fabric 104. A switching fabric 104 is a network of switching nodes such as switching nodes 1051 through 1055. Consistent with the use and purpose of a network, the switching nodes 1051 through 1055 are responsible for directing packets toward their appropriate destination. For example, if I/O unit 1086 desires to send information to processor unit 1031, one or more packets that contain the information are directed over the switching fabric 104 from network access link 10612 to network access link 1061.

As such, switching node 1055 will direct these packets (upon their reception from access link 10612) toward switching node 1052 (e.g., by directing them to switching node 1051 which subsequently directs them to switching node 1052). A number of sophisticated computer architecture approaches are possible through the use of the switching fabric 104. These include (among possible others): 1) the implementation of a multi-processor computing system (because the switching fabric 104 allows the processors 1031 through 1036 to efficiently communicate with one another); 2) intelligent I/O units (because the switching fabric 104 allows the I/O units 1081 through 1086 to efficiently communicate with one another); 3) scalability (i.e., if an increase in processing performance is desired, more processors can be coupled to the network; if I/O needs to be expanded, more I/O units can be added to the fabric, with the fabric being expanded to meet the increased connectivity, and/or, if faster communication is desired through the network 104, more switches can be added to the network 104); and 4) partitioning (wherein a subset of processors are identified as being part of a unique multi-processing core resource that can operate privately).

The switching fabric 104 also provides a performance advantage over bus architectures because a large number of communications can be simultaneously carried between the various processors and I/O units. That is, a particular processor or I/O unit typically does not have to “wait” to send information until another unit has completed its own transmission of information. As a result, the various units are allowed to simultaneously inject their information into the network.

FIGURES

The present invention is illustrated by way of example, and not limitation, in the Figures of the accompanying drawings in which:

<figref idref="DRAWINGS">FIG. 1</figref> shows an example of an Infiniband network;

<figref idref="DRAWINGS">FIG. 2</figref> shows an example of a switching node that may be used within an Infiniband network;

<figref idref="DRAWINGS">FIG. 3</figref> shows an example of a design for an input port that may be used within the switching node observed in <figref idref="DRAWINGS">FIG. 2</figref>;

<figref idref="DRAWINGS">FIG. 4</figref> shows a methodology for processing a packet that may be performed by the input port of <figref idref="DRAWINGS">FIG. 3</figref>;

<figref idref="DRAWINGS">FIG. 5</figref> shows an example of a design for a scheduler that may be used within the input port of <figref idref="DRAWINGS">FIG. 4</figref>;

<figref idref="DRAWINGS">FIG. 6</figref>a shows an exemplary depiction of the register contents of a scheduler having a register ring architecture such as the scheduler of <figref idref="DRAWINGS">FIG. 5</figref>;

<figref idref="DRAWINGS">FIG. 6</figref>b shows an exemplary depiction of the register contents of a read hub, in a low speed mode, having a register ring architecture such as the read hub observed in <figref idref="DRAWINGS">FIG. 11</figref>;

<figref idref="DRAWINGS">FIG. 6</figref>c shows a first exemplary depiction of the register contents of a read hub, in a high speed mode, having a register ring architecture such as the write hub observed in <figref idref="DRAWINGS">FIG. 11</figref>;

<figref idref="DRAWINGS">FIG. 6</figref>d shows a second exemplary depiction of the register contents of a read hub, in a high speed mode, having a register ring architecture such as the write hub observed in <figref idref="DRAWINGS">FIG. 11</figref>;

<figref idref="DRAWINGS">FIG. 7</figref> shows an embodiment of a state machine that may be used by a scheduler to determine how many write hubs should be set to a particular speed mode in light of current traffic conditions;

<figref idref="DRAWINGS">FIG. 8</figref> shows an embodiment of a design for a pointer manager such as the pointer manager observed in <figref idref="DRAWINGS">FIG. 3</figref>;

<figref idref="DRAWINGS">FIG. 9</figref> shows a trio of methodologies that can be performed by the pointer manager observed in <figref idref="DRAWINGS">FIG. 8</figref>;

<figref idref="DRAWINGS">FIG. 10</figref> shows an embodiment of a link list;

<figref idref="DRAWINGS">FIG. 11</figref> shows an embodiment of a read hub having a register ring architecture that is capable of operating in a high speed mode or a low speed mode;

<figref idref="DRAWINGS">FIG. 12</figref>a shows an embodiment of a low speed mode methodology for a read hub having a register ring architecture such as the read hub observed in <figref idref="DRAWINGS">FIG. 11</figref>;

<figref idref="DRAWINGS">FIG. 12</figref>b shows a more detailed embodiment of a low speed mode methodology for a read hub having a register ring architecture such as the read hub observed in <figref idref="DRAWINGS">FIG. 11</figref>;

<figref idref="DRAWINGS">FIG. 13</figref>a shows an embodiment of a high speed mode methodology for a read hub having a register ring architecture such as the read hub observed in <figref idref="DRAWINGS">FIG. 11</figref>;

<figref idref="DRAWINGS">FIG. 13</figref>b shows an embodiment of a high speed mode methodology for a read hub having a register ring architecture such as the read hub observed in <figref idref="DRAWINGS">FIG. 11</figref>;

DESCRIPTION

Overview of Infiniband Switch Embodiment

<figref idref="DRAWINGS">FIG. 2</figref> shows an embodiment of a design 205 for a switching node. That is, switching node 205 may be viewed as an “in-depth” perspective of any of the switching nodes 1051 through 1055 shown in <figref idref="DRAWINGS">FIG. 1</figref>. According to the switch design of <figref idref="DRAWINGS">FIG. 2</figref>, a plurality of links 2061 through 206n are coupled to the switch 205. A link is a networking line that propagates information from switch to switch within the network (or acts as an access link that allows devices outside the network to send/receive information to/from the network). Examples include copper or fiber optic cabling.

In the Infiniband scheme, currently, links are characterized as having a “4×’ speed or a “1×” speed. Currently, a 1× speed link has as a 2.5 Gbps link rate (2 Gbps data rate) and is implemented as a single link that is operated at this speed. A 4× speed link may be implemented as the combination of four 1× speed links that operate in unison together (e.g., four 1× speed links collectively transport different pieces of the same packet). As such, the total speed of the 4× link is a 10 Gbps link rate (8 Gbps data rate). It is important to note, however, that as the Infiniband standard evolves, other link speeds and topologies are possible (e.g., a 4× link constructed from a single link that operates at a 10 Gbps link rate). As seen in <figref idref="DRAWINGS">FIG. 2</figref>, each link 2061 through 206n has an associated link interface 2071 through 207n.

A link interface is responsible for launching packets onto a link and receiving packets from a link. Thus, for example, link interface 2071 launches packets onto link 2061 and receives packets from link 2061. Each link interfaces 2071 through 207n also has an associated input port (that accepts incoming packets) and output port (that provides output packets). That is, for example, link interface 2071 sends incoming packets that have arrived from link 2061 to input port 2011; and, output port 2021 provides outgoing packets to link interface 2071 for transmission over link 2061. Alternate embodiments may deviate from the 1:1:1 link:link interface:port ratio just described above (e.g., 1:1:2, 1:1:3, etc.).

The general traffic flow for an incoming packet is to flow firstly from its link interface to its input port. Then, the packet flows from its input port to a switching core 208 (which can be constructed with a crossbar switching architecture (as suggested by <figref idref="DRAWINGS">FIG. 2</figref>) or other types of switching architectures). The switching core 208 is a unit that switches the incoming packet from its input port to its appropriate output port; and, in so doing, effectively converts the incoming packet to an outgoing packet. For example, if an incoming packet from link 2061 is to be emitted as an outgoing packet on link 206n, the switching core 208 will “switch” the packet from switching core input 2131 to switching core output 210n.

As such, the packet will be directed from input port 2011 to output port 202n which effectively converts the packet from an input packet to an output packet. Note that in the switch design 205 of <figref idref="DRAWINGS">FIG. 2</figref>, each input port 2011 through 2011 has a plurality (“k”) of output lines. That is, each input port enjoys multiple inputs to the switching core 208 In an embodiment, k=3. As such, each input port 2011 through 201n is capable of simultaneously sending 3 different packets to the switching core 209; and, for a switch 205 where n=8, the switching core 209 corresponds to a 24×8 (input/output) switch.

The timing as to when an incoming packet is permitted to be switched by the switching core 208 is controlled by the arbiter 208. In an embodiment, for each incoming packet, a request data structure is issued by the corresponding input port to the arbiter 208. For example, if link interface 2071 sends a packet to input port 2011, input port 2011 issues a request data structure along request interface 2111 to the arbiter 208. As a request data structure is issued for each incoming packet, the arbiter 208 effectively collects these requests and is able to develop an understanding of the overall offered load being presented to switch 205.

Arbiter 208, which may be viewed as the central intelligence of the switch 205, “decides” when a particular request is to be favorably responded to. When such time arrives, a grant is directed from the arbiter 208 to the input port that issued the request. For example, for the aforementioned packet in which a request data structure was issued by input port 2011, the arbiter 208 will issue a grant along interface 2121 to input port 2011 at a moment in time that is consistent with a moment or region of time that the arbiter 208 has decided is suitable for switching the packet through the switch 205.

In an embodiment, each of the input ports 2011 through 201n are configured to have some sort of queuing or blocking so that one or more incoming packets can “wait” until the arbiter 208 decides the time is appropriate for each of their individual releases to the switching core 209. The arbiter 208 typically has designed into its intelligence the ability to determine when a grant should be provided to each incoming packet (that has had a request data structure issued to the arbiter 208 by its input port) based upon a number of factors.

The factors may include: 1) whether or not sufficient bandwidth resources currently exist at the output port and output link to which each packet is directed; 2) whether or not sufficient bandwidth resources currently exist at the switching core 209 to handle the switching of a next packet; 3) the relative priority of each packet (e.g., as based upon the source/destination of each packet and/or the packet type of each packet). The arbiter 208, depending on its particular design, may also possess functionality that determines the appropriate output port for each incoming packet (e.g., based upon the destination address embedded within each packet's header information).

As such, each request data structure that is issued from an input port to the arbiter 208 may be embedded with (or otherwise include) various specific information about its corresponding incoming packet. For example, in one embodiment, each request includes: 1) the size of the packet; 2) information that characterizes the packet (e.g., whether or not the packet is a “VL15” packet, which partition the packet belongs to, etc.); 3) the service level (SL) of the packet (which, as is known in the art, is an Infiniband packet header parameter that indicates the priority level of the packet); 4) the destination address of the packet; etc. Thus, in a sense, as the arbiter 208 makes bandwidth allocation decisions that are based upon a number of factors, such factors may be embedded with each request data structure as they pertain to its corresponding incoming packet. A more detailed discussion of various arbiter embodiments may be found in U.S. patent application Ser. No. 09/949,367, filed on Sep. 7, 2001 and entitled “METHOD AND SYSTEM TO MANAGE RESOURCE REQUESTS UTILIZING LINK-LIST QUEUES WITHIN AN ARBITER ASSOCIATED WITH AN INTERCONNECT DEVICE”.

Before progressing to <figref idref="DRAWINGS">FIG. 3</figref>, as is consistent with the Infiniband approach, note that in an embodiment each link can support up to 16 different Virtual Lanes (VLs) in the same direction (i.e., input or output). VLs effectively “break down” the traffic being transported by a link so that it can be viewed as a collection of unique traffic flows each having their own specific amount of bandwidth consumption. Typically, each VL on a link is given a number of “credits” where a credit corresponds to an amount of data allowed to be carried by the VL to which the credit is assigned. Other VL schemes besides 16 VLs per link may be developed (e.g., as a proprietary solution; or, as the Infiniband standard evolves in the future).

A link source node is typically allowed to transmit packets along a particular VL until the credit count for the VL is completely consumed. That is, each transmission of a packet along a particular VL decrements the credit count at the source node for that VL; and, if the credit count is less than the size of the next packet to be sent on that VL, no more transmissions are allowed on the link by the link source node for that VL. After a packet has been received by a link receiving node and switched through the switch core 209, it is re-transmitted by another outgoing link (and therefore another VL). In response, the link receiving node sends the credit count that was consumed by the packet back to the link source node so that the link source node's credit count for the VL can be refreshed (which permits the sending of a subsequent packet).

Overview of Input Port Operation

<figref idref="DRAWINGS">FIG. 3</figref> shows an embodiment 301 of an input port that may be used for any of the input ports 2011 though 201n observed in <figref idref="DRAWINGS">FIG. 2</figref>. In an embodiment, the link interface that feeds the input 3031 performs bit recovery and byte synchronization from the incoming data stream(s) being received on the input link(s) and the request manager 306 performs packet synchronization. That is, is a sense, the link interfaces have no “packet awareness” and merely determine the individual bytes of data that they are receiving. These bytes of data are then passed along the port input 3031 to the request manager 306; and, the request manager 306 determines where packets start and end from the stream of information that it receives from the link interface.

In various embodiments, the link interface may be designed to handle different link speeds. As such, the input port 301 should also be suitably designed to handle different link speeds. For example, a simple link interface may be designed to handle either one high speed link (e.g., one 4× link) or one low speed link (e.g., one 1× link). A more sophisticated link interface may be designed to handle either a high speed link or one or more low speed links. For example, as just one possible implementation, a link interface may be designed to be configured into either a high speed mode (e.g., that supports one 4× speed link); or, a low speed mode that supports individual lower speed links (e.g., a plurality of different 1× speed links).

An embodiment of the input port 301 observed in <figref idref="DRAWINGS">FIG. 3</figref> can handle a link interface that is designed to provide either one 4× speed link (in its high speed mode) or up to four separate 1× speed links (in its low speed mode). It is to be emphasized, however, that an input port capable of properly handling traffic from link interfaces having different configuration characteristics that defined just above may be readily designed in light of the underlying operational principles of the input port described below. As such, unless specifically recited, the following claims should not be automatically construed as being limited to covering only those implementations designed to handle a link interface that is designed to provide either one 4× speed link (in its high speed mode) or up to four separate 1× speed links (in its low speed mode). Better said, because the description that follows describes basic underlying concepts for handling a high speed traffic stream or a plurality of different lower speed traffic streams, its application can be extended to different link speeds (e.g., other than 1×, 4×, etc.), different high speed vs. low speed configuration combinations (e.g., other than 4× vs. 1×), and/or different numbers of links to be handled (e.g., other than one high speed link, four low speed links, etc.). Furthermore, consistent with this perspective, the discussion provided herein can be applied to proprietary or future Infiniband applications; or even, applications that are not directed to the Infiniband standard.

For simplicity, the following discussion is mostly directed to input port embodiment 301 that is configured to handle a link interface that is designed to provide either one 4× speed link (in its high speed mode which may also be referred to as the “4× mode”) or up to four separate 1× speed links (in its low speed mode which may also be referred to as the “1× mode”). Here, note that four separate inputs 30311, 30312, 30313, 30314, are associated with the input 3031 to the input port logic 302. As these inputs are provided by the underlying link interface, in a first “high speed” mode (the 4× mode) all four of the separate inputs 30311, 30312, 30313, 30314 are used together to provide the data from a single 4× speed link; and, in “low speed” mode (the 1× mode), each of the separate inputs 30311, 30312, 30313, 30314 is responsible for providing the flow of data from its own corresponding 1× speed link.

That is, in high speed mode consecutive groups of received data from the high speed link are distributed in a round robin sequence across the four inputs (e.g., such that a first group of received data is provided at input 30311, a second group of information is provided at input 30312, a third group of information is provided at input 30313, and a fourth group of information is provided at input 30314; where, the first through fourth groups of information provide a larger group of received information in its proper sequence and the same can be said for following groups of information. In low speed mode, each of the four inputs corresponds to its own unique 1× link (e.g., data from a first 1× link is received at input 30311, data from a second 1× link is received at input 30312, data from a third 1× link is received at input 30313, and data from a fourth 1× link is received at input 30314). Note that “up to” four 1× links may be active in low speed mode at one time. Thus, less than four 1× links (e.g., three 1× links; or two 1× links; or one 1× link) may actually be operating when in low speed mode. The number of links in use depends upon the configuration of the overall switch.

In a further embodiment, each input corresponds to a byte wide interface. As such, a byte of information is received at once along input 30311, a byte of information is received at once along input 30312, a byte of information is received at once along input 30313; and, a byte of information is received at once along input 30314. As such, in 4× mode, the overall input 3031 can be viewed as a 32 bit wide interface that provides 32 consecutive bits of received data from the 4× link; while, in 1× mode, the overall input 3031 can be viewed as providing four separate byte-wide interfaces. Again, less than four 1× links may be active during low speed mode. Note that in alternate embodiments the bit-width of each input may be different than 8 bits (e.g., 10 bits, 16 bits, etc.).

Note that, if the link interface is configured in 4× mode, a single stream of packets will be provided by the overall input 3031; while, in 1× mode, up to four distinct streams of packets will be provided by the overall input 3031 (i.e., one distinct stream for each of inputs 30311, 30312, 30313, 30314). An important part of the input port 301 design is the ability to identify and separately manage the storage and retrieval of each packet whether in 4× mode or in 1× mode. <figref idref="DRAWINGS">FIG. 4</figref>, when viewed together with <figref idref="DRAWINGS">FIG. 3</figref>, helps to describe, at a high level, an embodiment of an overall processing flow that may be applied to the packets that are managed by the input port 301. According to the methodology of <figref idref="DRAWINGS">FIG. 4</figref>, for each newly arriving packet: 1) a request data structure 319 is built by the request manager 306 and issued 401 to the arbiter at output 311 (so as to effectively request the permission of the arbiter to send the packet to the switch core as described with respect to <figref idref="DRAWINGS">FIG. 2</figref>); and, 2) the newly arriving packet is written 402 across a plurality of memory banks 3071 through 3074 by a write hub unit 305 so that it can be temporarily stored while the arbiter consumes time deciding when it is appropriate to send the packet to the switch core. A write hub is collection of circuitry used to write packets into the memory banks. Various write hub approaches are discussed in more detail below.

Upon the receipt of a grant from the arbiter at input 312 (which signifies permission to forward the packet from the memory banks 3071 through 3074 has been obtained from the arbiter), a scheduler 309 helps to organize the reading of the packet from the memory banks 3071 through 3074. Here, a particular read hub unit (e.g., one of read hub units 3161 through 3163) is notified of its responsibility to read 404 the packet from the memory banks 3071 through 3074; and, the packet's information is read from the memory banks 3071 through 3074 by the notified read hub and directed to the switch core along the appropriate input port output (e.g., output 3131 for read hub 3161, output 3132 for read hub 3162, output 3133 for read hub 3163). A read hub is a collection of circuitry used to read packets from the memory banks. Various read hub approaches are discussed in more detail below. Here, from the discussion of <figref idref="DRAWINGS">FIG. 2</figref>, recall that each input port may have “k” outputs to the switch core 209. Further recalling that in one embodiment k=3, note that the embodiment of <figref idref="DRAWINGS">FIG. 3</figref> corresponds to such an approach.

Before commencing with in-depth discussions of various architectural approaches that may be used for each of the write hub unit 305, the scheduler 309, the read hub units 3161 through 3163, and the pointer manager 314; a brief discussion of the operation of the request manager 306 and the function of link-lists will be provided. Noting that the request manager 306 is able to observe the packet streams being sent from the link interface (by being coupled to the output of each of Rx queues 3041 through 3044), the request manager 306 is configured, for each stream of packets received by the input port 301, to determine: 1) where packets start and end; 2) the VL the packet belongs to; and 3) the size of the packet. These determinations may be made by analyzing each input packet's header information. In various embodiments, this information may be used to help build the request data structure 319 that is sent to the arbiter at along output 311.

Based upon the size of the packet and the VL to which the packet belongs, the request manager 306 may also be configured to check the credit count for the packet's VL (e.g., from VL credit register space built into the request manager 306 which is not shown in <figref idref="DRAWINGS">FIG. 3</figref> for simplicity) to see if sufficient credits existed on the link to receive the packet. That is, recalling the discussion provided toward the end of the preceding section, VL credits are “kept track of” so that proper link operation can be verified. Specifically, VL credit registers (which are associated with the request manager 306 and are not shown in <figref idref="DRAWINGS">FIG. 3</figref> for simplicity) effectively keep a record of the credits that are available to each VL (or a subset thereof). For each packet that arrives to the input port 301, the request manager decrements the credit count of the VL that carried the packet. Upon the packet's being read out memory (in response to a grant being received from the arbiter), the credit count is refreshed.

In various embodiments, the Infiniband approach has allocated the 0th through 14th VLs for typical data transportation. As such, only 15 registers (or register fields) are implemented within the request manager 306 (one register/register field for each of VLs 0 through 14) for each separate packet stream the request manager 306 may have to monitor (in this case, four). The 15th VL (upon which “VL15 packets” flow) is reserved for network maintenance/control information. As VL15 packets are considered “high priority” packets, in an embodiment, no flow control is performed and credit counts are not kept track of for a link's VL15 virtual lane. As such, in an embodiment, the request manager 306 is designed to not only recognize the arrival of a VL15 packet (e.g., from the packet's header information), but also does not refer to the credit count related register space for any VL15 packet. Instead, if a second VL15 packet arrives to the port 301 before a first VL15 packet leaves the port 301, the second packet is automatically dropped. In an alternative embodiment, a fixed number of VL15 packets can be queued before VL15 packets begin to be dropped.

After a packet begins to be observed by the request manager 306 (and the credit count is deemed sufficient for the packet), the request manager 322, then scans the packet's header information and builds a request data structure 319 for the packet. The request data structure 319 is then forwarded to the arbiter (along the request interface 311). Recall from the discussion above with respect to <figref idref="DRAWINGS">FIG. 2</figref> that a request data structure may be configured to include: 1) the size of the packet; 2) information that characterizes packet; 2) the service level (SL) of the packet; 3) the destination address of the packet, etc. Each of these may be extracted from the header of the packet. In at least one embodiment, each request data structure also includes: 1) an indication as to which one of the four memory banks 3071 through 3074 where a first piece of the corresponding packet is stored; and 2) the corresponding address (referred to as a “head pointer”) for that memory where the first piece can be found. Both the indication as to which memory bank and the head pointer are then included in the grant for the packet (which is received from the arbiter at grant interface 312), so that the read hub responsible for reading the packet understands where the next packet is to be found. The read hub responsible for reading the packet uses the head pointer (and the memory bank indication) to begin reading the packet from correct memory bank at the proper address.

Here, note that part of the function of the write hub is to organize a received packet into fixed size “chunks” or pieces of data. These chunks or pieces may be referred to as a “buffer” or a “buffer's worth of data”. The write hub 305 is responsible for writing a buffer across the memory banks 3071 through 3074. Here, one pointer value is consumed per buffer. That is, recalling the discussion from just above, a head pointer is used to identify a memory address where the first buffer of a packet is stored. For each following buffer that is formed from the packet, a new pointer is used to point to a memory region across the memory banks 3071 through 3074 where the buffer can be stored. Here, pointers are retrieved from the pointer manager 314. The pointer manager 314 is responsible for maintaining a “link-list” for the packet. A link-list is a record of the pointer values used to store a packet.

Thus, after a packet has been completely stored across the memory banks 3071 through 3074 and a grant has been received from the arbiter for that packet, the pointer values stored in the link list may be referred to by a write hub to read the packet from memory at the correct addresses. Note that, perhaps depending on the size of the packet, if a grant for a packet is received shortly after a request was sent to the arbiter for that packet, the earlier arriving buffers of a packet may be read from the memory banks 3071 through 3074 and forwarded to the switch core while later portions of the packet are still arriving and being written into the memory banks 3071 through 3074. The term “cut-through” is used to describe this processing sequence where a packet is simultaneously being read from and written to memory as described just above. <figref idref="DRAWINGS">FIG. 4</figref> shows the possibility of cut-through by border 402c (which shows the writing 402 of a packet may overlap in time with the reading 404 of a packet). Border 402a corresponds to a situation where a packet is completely written before a grant is received 403 from the arbiter; and, border 402b corresponds to a situation where a packet is completely written after a grant has been received 403 but before the packet begins to be read 404 from memory).

Scheduler

Referring to <figref idref="DRAWINGS">FIG. 3</figref>, note that the particular embodiment shown therein possesses one write hub 305 and three read hubs 3161 through 3163. As all four of these hubs 305, 3161 through 3163 are capable of using a different one of the memory banks 3071 through 3074 within the same cycle of operation; and, as each packet is stored across each of the different memory banks 3161 through 3163, some form of organizing presence is needed to prevent the different hubs from interfering with each other's needs of the various memory banks 3161 through 3163. In the particular embodiment of <figref idref="DRAWINGS">FIG. 3</figref>, a scheduler unit 309 is used to control the channel select input for each of a plurality of multiplexers 3081 through 3084 such that each hub 305, 3161 through 3163 (while moving the data of a packet) gains access to the memory banks 3071 through 3074 via a round robin sequence; where, after a first memory bank (e.g., memory bank 3071) is accessed during a first cycle of operation, a second “next” memory bank (e.g., memory bank 3072) is accessed during a “next” second cycle of operation.

By identifying the first memory bank (e.g., memory bank 3071) as the “next” memory bank relative to the last memory bank (e.g., memory bank 3074) in the round robin scheme, from the perspective of one of the hubs, a different memory bank is “rotated” to the hub for its use for each cycle of operation. Over time, the hub will be provided cyclical access to all of the memory banks (e.g., BANK1, BANK2, BANK3, BANK4, BANK1, BANK2, BANK3, BANK4, etc.). By allowing each hub to have access to a different memory bank during any same cycle of operation, all four hubs can simultaneously enjoy rotated access to each of the memory banks. Here, the scheduler unit 309 in the embodiment of <figref idref="DRAWINGS">FIG. 3</figref> is responsible for controlling the multiplexers 3081 through 3084 in a fashion that is consistent with the scheme described just above. That is, under full loading conditions, not only is each multiplexer configured to give memory access to a different hub during any same cycle of operation (e.g., during a first cycle: 1) multiplexer 3081 gives access to read hub 33163; 2) multiplexer 3082 gives access to read hub 23162; 3) multiplexer 3083 gives access to read hub 13161; and, 4) multiplexer 3084 gives access to the write hub 305); but also, each multiplexer is configured to select hubs (giving them access to its corresponding memory) in round robin fashion. In the embodiment of <figref idref="DRAWINGS">FIG. 3</figref>, the scheduler 309 is responsible for providing the correct channel select values across the multiplexer channel select lines 3101 through 3104 to realize this scheme.

<figref idref="DRAWINGS">FIG. 5</figref> shows an embodiment of a scheduler unit 509 that can be used to implement the scheduler unit 309 of <figref idref="DRAWINGS">FIG. 3</figref>. The read demand logic 522 and associated circuitry 520, 521, 5231 through 5233 comes into play for the reading of packets from the memory banks. A discussion of the read demand logic 522 and its associated circuitry 520, 521, 5231 through 5233 will be provided further below in a section entitled “Read Operation”. Referring to the scheduler unit embodiment 509 of <figref idref="DRAWINGS">FIG. 5</figref>, note that ring of registers 5261 through 5264 is observed. A ring of registers (which may also be referred to as a “register ring”, a “register ring architecture” and the like, etc.) is an arrangement of registers where: 1) the contents of each register can be shifted to “next” register in the ring; and, 2) the continuous shifting of the contents through registers causes the contents to circulate through the registers. The circulation is caused by a feedback path that flows from the last register to the first register in the ring (e.g., as observed from by the feedback path that flows from register 5264, through multiplexer 5251, and into register 5261). Here, the circulation of the register contents is used to implement the round robin scheduling scheme that was just discussed above.

Insight into how the register ring can be used to implement a round robin scheduling scheme can be gleaned by referring to both <figref idref="DRAWINGS">FIGS. 5 and 6</figref>a. <figref idref="DRAWINGS">FIG. 6</figref>a shows the circular rotation of the register contents over time. The columns of the chart observed in <figref idref="DRAWINGS">FIG. 6</figref>a correspond to a consecutive string of operational cycles that the time of operation of the input port is organized into. The rows of the chart observed in <figref idref="DRAWINGS">FIG. 6</figref>a correspond to the contents of the registers 5261 through 5264 (or the outputs MUX15101 through MUX45104 that are respectively derived from them). The rows have been labeled according to the memory bank that is accessed by way of the contents held within the register that each row corresponds to. That is, referring briefly to <figref idref="DRAWINGS">FIGS. 5 and 3</figref>, register 5261 controls access to the first memory bank (BANK 1) 3071, register 5262 controls access to the second memory bank (BANK 2) 3072, register 5263 controls access to the third memory bank (BANK 3) 3073, and register 5264 controls access to the fourth memory bank (BANK 4) 3074.

The fact that the registers control access to the memory banks as described above can be recognized by realizing that the output nodes MUX15101 through MUX45104 of the scheduler 509 of <figref idref="DRAWINGS">FIG. 5</figref> corresponds to the output nodes MUX13101 through MUX43104 of the scheduler 309 of <figref idref="DRAWINGS">FIG. 3</figref>. As such, in the implementation of <figref idref="DRAWINGS">FIG. 5</figref>, the contents of register 5261 correspond to the logical value that is applied to the channel select input 3101 of the first multiplexer 3081; the contents of register 5262 correspond to the logical value that is applied to the channel select input 3102 of the second multiplexer 3082; etc. Referring now to <figref idref="DRAWINGS">FIGS. 3 and 6</figref>a, note that each of the four multiplexers 3081 through 3084 have the same input channel design. That is, each of the four multiplexers 3081 through 3084 have: 1) their first input channel coupled to read hub_33163; 2) their second input channel coupled to read hub_23162; 3) their third input channel coupled to read hub_13161; and, 4) their fourth input channel coupled to the write hub 305.

As such, a specific channel select value will have the same effect regardless as to which multiplexer's channel select input receives it. That is, for example, if a value of “11” is placed upon the channel select input of any of the multiplexers 3081 through 3084 causes the multiplexer to select its fourth input; then, rotating a value of “11” across the channel select lines 3101 through 3104 will cause the write hub to enjoy round robin access to the memory banks as described above. Referring then to <figref idref="DRAWINGS">FIGS. 3</figref>, 5 and 6a and continuing with this example, note that if the logical value for “W” corresponds to “11”; then, <figref idref="DRAWINGS">FIG. 6</figref>a accurately represents how the channel select value for the selecting of the write hub 305 can be rotated across the channel select lines 3101 through 3104 (so as to provide round robin access to the memory banks 3071 through 3074 for the write hub 305) by rotating the “W” value forward in the register ring according to the register sequence 5261, 5262, 5263, 5264, 5261, 5262, . . . etc. where one shift of the “W” value occurs per cycle.

<figref idref="DRAWINGS">FIG. 6</figref>a also demonstrates how the channel select values for selecting the read hubs 3161 through 3163 are circulated through the scheduler's register ring. That is, the label “Hub 1” in <figref idref="DRAWINGS">FIG. 6</figref>a corresponds to a data structure value that would cause any of multiplexers 3081 through 3084 to give its corresponding memory bank access to Read_Hub_13161. Similarly, the label “Hub 2” in <figref idref="DRAWINGS">FIG. 6</figref>a corresponds to a data structure value that would cause any of multiplexers 3081 through 3084 to give its corresponding memory bank access to Read_Hub_23162; and, the label “Hub 3” in <figref idref="DRAWINGS">FIG. 6</figref>a corresponds to a data structure value that would cause any of multiplexers 3081 through 3084 to give its corresponding memory bank access to Read_Hub_33163. From the exemplary scheduling example of <figref idref="DRAWINGS">FIG. 6</figref>a, note that Cycles 12 through 16 demonstrate how each of the four hubs 3161 through 3163 and 305 can share each of the four memory banks 3071 through 3074 via their round robin memory bank accesses that are out-of-phase with one another.

Note that each of the read hub labels (“Hub_1”, “Hub_2”, “Hub_3”) are also labeled with a speed label of “LS” or “HS”. Here, “LS” represents “low speed” and “HS” represents “high speed”. In various embodiments, each of the read hubs 3161 through 3163 are capable of either low speed or high speed operation. Having a read hub capable of operating in a low speed mode or a high speed mode means that the read hub is capable of reading packets from memory at either of two speeds. In a further embodiment, the low speed mode is for reading packets from memory that will be emitted (e.g., after they are switched through the switch core) as an output packet along a low speed (e.g., 1× speed) Infiniband link; and, the high speed mode is for reading packets from memory that will be emitted (e.g., after they are switched through the switch core) as an output packet along a high speed (e.g., 4× speed) Infiniband link.

More insight to this perspective by referring back to <figref idref="DRAWINGS">FIG. 2</figref>. <figref idref="DRAWINGS">FIG. 2</figref> shows an exemplary architecture for a networking switch. Note that the networking switch has a plurality of outgoing links 2061 through 206n. In various configurations, some of these outgoing links 2061 through 206n may be high speed outgoing links (e.g., 4× speed outgoing links) whereas others may be low speed outgoing links (e.g., 1× speed outgoing links). Given that an input (e.g., input port 2011 may receive packets destined to one or more of the high speed outgoing links as well as receive packets destined to one or more of the low speed outgoing links, designing an input port so that packets destined for a high speed outgoing link are sent to the switch core 209 at a higher speed than those packet destined for a low speed outgoing link allows for a more efficiently designed switch 205.

Better said, if packets destined for a high speed outgoing link are sent to the switch core at too slow a speed, the output port (e.g., output port 2021) responsible for handling the output packet may not be able to feed the high speed outgoing link at a proper rate (e.g., the outgoing high speed link may become starved). Similarly, if packets destined for a low speed outgoing link are sent to the switch core at too high a speed, the output port (e.g., output port 2021) responsible for handling the output packet may become overrun with data because the outgoing link could not bleed off traffic from the output port at a fast enough rate. As such, designing an input port to be able to send traffic to the switch core 209 at either of a pair of speeds allows traffic flow rates through the switch to be modulated in accordance with the traffic flow rates that emanate from the switch itself. As such, wasteful under-run or over-run conditions are more easily avoided.

Referring now to <figref idref="DRAWINGS">FIGS. 3 and 6</figref>a, in an embodiment, each read hub 3161 through 3163 is capable of reading packets from the memory banks 3071 through 3074 at a high speed rate or a low speed rate so that the output ports that ultimately receive these packets receive them at a rate that is commensurate with their own outgoing link speeds. According to the scheduling diagram of <figref idref="DRAWINGS">FIG. 6</figref>a, the “LS” and “HS” labels indicate that read hub_13161 is configured as a low speed hub while read hubs 2 and 33162, 3163 are each configured as high speed hubs. In at least one embodiment, to say that a read hub is configured as a high speed read hub means that the read hub is capable of reading a single stream of packets at least at a 4× Infiniband speed. In a further embodiment, to say that a read hub is configured as a low speed hub means that the read hub is capable of reading four separate streams of packets each of which are read at least at a 1× Infiniband speed. Note that the total bandwidth capability of either mode is a sufficient for a 4× speed rate of traffic flow (e.g., 1×4×=4×; or, 4×1×=4×).

<figref idref="DRAWINGS">FIGS. 6</figref>b through 6d relate to the operation of each of read hubs 3161 through 3163, respectively (whereas, as mentioned just above, read hub_13161 is configured as a low speed hub while read hubs 2 and 33162, 3163 are each configured as high speed hubs). However, before commencing a more thorough discussion of an embodiment of the operation of the read hubs 3161 through 3163 themselves, note that it may be desireable to have the read hubs be configured into a high speed mode or a low speed mode “on the fly”. That is, for example, if the input port is asked to handle a steady stream of packets that are only destined for low speed outgoing links—it would be efficient to configure every read hub as a low speed read hub. Then, continuing with this same example, if the same input port was suddenly asked to process nothing but packets destined for high speed outgoing links—it would suddenly become more efficient to configure every read hub as a high speed read hub. This simple example shows that it may be more efficient to allow an input port to adjust the number of read hubs devoted to a particular speed mode in light of changes that arise in the characteristics of the traffic (i.e., “traffic conditions”) it is asked to handle over time.

<figref idref="DRAWINGS">FIG. 5</figref> shows an embodiment of a scheduler 509 that can, over time, tweak the number of read hubs that are devoted to a particular speed in light of present or expected trafficking conditions. More particularly, the scheduler of <figref idref="DRAWINGS">FIG. 5</figref> gains insight into how many “high speed” packets (i.e., packets to be read a high rate of speed from memory) and how many “low speed” packets (i.e., packets to be read a high rate of speed from memory) are to be read from memory in the near future. Based at least partially upon the number of high speed and low speed packets that are to be read from memory in the near future, the scheduler configures an appropriate number of high speed read hubs and an appropriate number of low speed read hubs. Here, referring to <figref idref="DRAWINGS">FIGS. 3 and 5</figref>, recall the a grant is received from the arbiter (e.g., along interface 312, 512). In an embodiment, the grant indicates the speed at which the packet should be read from memory. Note that this is consistent with the function of the arbiter whose role it is to oversee the traffic flows throughout the switch core as a whole. Better said, as the function of the arbiter involves an understanding of the applicable input and output rates (e.g., incoming link speeds and outgoing link speeds), the arbiter should be able to recognize the applicable outgoing link speed for a packet simply by recognizing the output port and/or destination address of a packet. As such, each grant provided to an input port can readily be adapted to indicate whether the packet should be read from memory at high speed or at low speed.

Referring to <figref idref="DRAWINGS">FIG. 5</figref> then, note that a pair of queues 520, 521 are configured to receive and enqueue the stream of grants that are sent from the arbiter at interface 512. Here queue 520, the low speed queue 520, collects those grants having been specified by the arbiter to be read from memory at low speed (e.g., a 1× speed); and, queue 521, the high speed queue 521, collects those grants having been specified by the arbiter to be read from memory at high speed. The read demand logic 522, by making reference to the relative population of these queues 520, 521 and the state of each read hub (via read hub state registers 5231 through 5233) decides upon: 1) which hubs should be actively reading a packet from memory; and, 2) of these active read hubs, how many should be configured in low speed mode and how many should be configured in high speed mode.

The read demand logic 522 activates a particular read hub (e.g., Read_Hub_13161 of <figref idref="DRAWINGS">FIG. 3</figref>) by placing its corresponding data structure (e.g., “Read_Hub_1” as observed in <figref idref="DRAWINGS">FIG. 6</figref>a) into one of the scheduler's registers 5261 through 5264. The data structure will then circulate through the ring so as to give its corresponding read hub round robin access to the memory banks. When a read hub is to be deactivated, for the time being, it is removed from the ring. Here, the read demand logic 522 informs the ring control logic 524 which data structures should be entered into the ring and which data structures should be removed from the ring so that the appropriate read hubs are active over time in light of the read demand logic's decisions.

<figref idref="DRAWINGS">FIG. 7</figref> presents an embodiment of a state machine that is executed by the read demand logic to determine how many low speed read hubs should be active. Note that, consistent with the embodiment observed in <figref idref="DRAWINGS">FIG. 3</figref>, the maximum number of allowable low speed read hubs is three 1104. Here, the maximum number of allowable high speed read hubs is (3—(the state of <figref idref="DRAWINGS">FIG. 7</figref>)). Thus, if the state machine of <figref idref="DRAWINGS">FIG. 7</figref> is at state 1104 there are no high speed read hubs, if the state machine of <figref idref="DRAWINGS">FIG. 7</figref> is at state 1103 there is one allowable high speed read hub, etc. Assuming that the initial “start up” state is state 1101, the number of active read hubs will be set to “one” 1102 in response to the first low speed grant being enqueued in the low speed queue 1105 (recalling the presence of low speed 520 and high speed 521 queues). The number of active low speed hubs will remain at “one” unless: 1) the high speed queue becomes non-empty and the low speed queue becomes empty 1108 (in which case the number of low speed hubs will return to “zero” 1101); or, 2) the one active low speed read becomes “full” and the high speed queue becomes empty 1106 (in which case the number of low speed hubs will set to “two” 1103).

Here, a low speed read hub is deemed “full” if it is reading traffic at its maximum rate. In the embodiments written at length herein, this corresponds to a low speed read hub that is currently entertaining the management of four separate “1×” packet streams. As will be described in more detail below, for read hubs that are implemented with their own register ring architecture, a “full” read hub will have all its registers populated within its register ring. Note that state transition 1106 allows low speed grants to be built up within the low speed queue 520 while keeping the versatility of allowing any of 0, 1, or 2 active high speed hubs (depending on the rate at which high speed grants are being sent from the arbiter). That is, even in the face of a throttling up of low speed grants from the arbiter, the number of active low speed hubs is kept at one 1102 unless the active low speed queue 520 becomes full and the high speed queue 521 becomes empty 1106.

Continuing with a discussion of the state machine of <figref idref="DRAWINGS">FIG. 7</figref>, should the state of the number of active low speed read hubs reach “two” 1103, the number remains at two unless: 1) both of the active low speed read hubs become full and the high speed queue 521 becomes empty 1107 (in which case the number of active low speed read hubs is set to “three” 1104); or, 2) the high speed queue 521 becomes full 1109 (in which case the number of active low speed read hubs is reduced to “one” 1102); or, 3) the low speed queue 520 becomes empty while the high speed queue is non-empty 1109 (in which case the number of active low speed read hubs is reduced to “one” 1102). Finally, should the number of active low speed red hubs become equal to “three” 1104, the number remains at “three” unless the high speed queue becomes non-empty 1110 (in which case the number of active low speed read hubs is reduced to “two” 1103).

Referring to <figref idref="DRAWINGS">FIG. 5</figref>, note the presence of read hub state register 5231 through 5233. In an embodiment that can be used consistently with the state machine embodiment of <figref idref="DRAWINGS">FIG. 7</figref>, each read hub state resister informs the read demand logic 522 whether or not its respective read hub is: 1) active or inactive; 2) high speed (e.g., 4×) or low speed (e.g., 1×) (if the respective read hub is active); and 3) “full” (if the respective read hub is active and configured to be in low speed mode). From this information, as well as the state of the low speed and high speed queues 520, 521, a state machine (such as the state machine observed in <figref idref="DRAWINGS">FIG. 7</figref>) can be executed by the read demand logic 522 for the purpose of deciding which read hubs should be active and, of those, which should be configured in low speed mode.

In an embodiment, each grant for a packet that is entered into one of the queues 520, 521 includes the head pointer for that packet. Once a packet is scheduled to be read by a particular read hub, as part of the scheduling process, the scheduler forwards the head pointer for the packet to the particular read hub that is to read the packet. Here each of outputs 5211 through 5214 run to a different read hub for the purpose of allowing a head pointer to be forwarded to any read hub. Here, note that each of outputs 5211 through 5214 can be viewed as corresponding to scheduler outputs 3211 through 3214 of <figref idref="DRAWINGS">FIG. 3</figref>. Referring to <figref idref="DRAWINGS">FIG. 3</figref>, the discussion of the present section focused upon the scheduler portion 309 of the input port 301. The immediately following section focuses on the pointer manager 314 and the pointer RAM 318.

Pointer Management

<figref idref="DRAWINGS">FIGS. 8</figref>, 9 and 10 relate to a discussion of the pointer manager 314 and the pointer manager RAM 318 that is observed in <figref idref="DRAWINGS">FIG. 3</figref>. Upon the arrival of a packet, the write hub 305 will eventually receive (at the WPTR interface 315) a fresh “head” pointer that defines the memory address where the packet should first begin to be written into the memory banks 3071 through 3074. Note that the initial directive to send a fresh head pointer to the write hub 305 may be a signal, command or other communicative technique that exists between the request manager 306 and the pointer manager 314. That is, for example, upon recognition of a newly arriving packet, the request manager 306 may send some form of communication to the pointer manager 314 that the pointer manager interprets as a command to send a fresh head pointer to the write hub 305. For simplicity, such communicative capabilities are not shown in <figref idref="DRAWINGS">FIG. 3</figref>.

Upon reception of the fresh head pointer from the pointer manager 314, the write hub 305 will begin to write consecutive pieces of the packet in a round robin fashion across the memory banks 3071 through 3074. At some point the head pointer for the packet will be exhausted. That is, at some point all that could be written with respect to the issuance of the head pointer will be written into memory and the write hub 305 will need “another” pointer in order to continue the successful writing of the packet into memory. In various embodiments, the write hub 305 employs more than one memory address per pointer value that is received from the pointer manager 314. For example, in a further embodiment, four usable memory addresses are used by the write hub 305 per pointer value received from the pointer manager 314 (e.g., each pointer value from the pointer manager 314 is of the form XXX . . . XX00; and, the write hub is configured to use each of memory addresses XXX . . . XX00, XXX . . . XX01, XXX . . . XX10, and XXX . . . XX11 in response to the pointer value's reception).

Here, once each memory address for the pointer value has been used, the pointer value is said to be “exhausted” and the write effectively requests another pointer value in order to continue writing the packet. In an embodiment, the write hub 305 is configured to “return” the exhausted pointer value to the pointer manager 314. The pointer manager 314 interprets the returned pointer value as a request for a new pointer value and sends a “next linked to” pointer value to the write hub as its response to the write hub's request. Here, the pointer manager 314 maintains a link list for the packet within the pointer RAM 318. A link list is a record held within a memory (such as pointer RAM 318) that effectively links together each pointer value used for the same packet (e.g., by keeping, at each address that corresponds to a pointer value used for a packet, a data value that corresponds to the “next” pointer value that was used for the packet (from the perspective of the pointer value that the data value's address corresponds to)).

<figref idref="DRAWINGS">FIG. 8</figref> shows an embodiment of a pointer manager 814 that can operate as described just above. The pointer manager 814 communicates with the pointer RAM 818; and, the pointer RAM is further constructed from a pair of RAMs: 1) a link list RAM 821; and, 2) a free pointer queue RAM 822. The link list RAM 821 stores a link list for each packet stored in the memory banks 3071 through 3074. An embodiment of the contents of the link list pointer RAM 821 is shown in <figref idref="DRAWINGS">FIG. 10</figref> and will be described in more detail below. The free pointer queue RAM 822 is used to implement a simple first-in-first-out (FIFO) queue 823 that effectively queues “free” pointer values.

Here, a free pointer value is a pointer value that points to “free space” in the memory banks 3071 through 3074 of the input port. In an embodiment, a free pointer corresponds to an address value for memory banks 3071 through 3074 where a portion of a packet can be written without writing over a portion of another packet that has not yet been read from memory banks 3071 through 3074. According to this definition, the pointer values held within the free pointer queue therefore correspond to those locations in the memory banks 3071 through 3074 that: 1) are not presently being used to store a portion of a packet; or, 2) are presently holding “stale” data that can be written over.

Some basic functions of the pointer manager 814 (some of which have already been described above) are illustrated in <figref idref="DRAWINGS">FIG. 9</figref>. These basic functions include: 1) the response 901 to the reception of a request for a fresh head pointer; 2) the response 902 to the reception of an “exhausted” pointer value from the write hub 305; and, 3) the response 903 to the reception of an “exhausted” pointer value from one of the read hubs 3071 though 3074. Referring to <figref idref="DRAWINGS">FIGS. 8 and 9</figref>, if a request for a fresh head pointer (e.g., as made by the request manager 306 in response to the arrival of a new packet) is received by the request manager 814 at input 806, the pointer manager 814 reads 901 the fresh head pointer from the head of the free pointer value queue 823. According to the pointer manager embodiment 814 observed in <figref idref="DRAWINGS">FIG. 8</figref>, this entails triggering a request (along request signal line 807) to the read channel logic 803 that interfaces to the free pointer queue RAM 822. In response to the request, the read channel logic 803 reads the “next” free pointer value from the head of the queue 822. The pointer value is then sent to the write hub 305 at output 815b.

If the write hub returns an exhausted pointer value to the pointer manager 814 (e.g., at input 815a), a pair of sub-actions occur 902. The first sub-action involves the reading of the next “free” pointer from the head of the free pointer queue 823 (which, again, entails triggering a request (along request signal line 807) to the read channel logic 803 that interfaces to the free pointer queue RAM 822). The second sub-action involves constructing the next portion of the link list for the packet that the returned, exhausted pointer value was used to store into the memory banks. The constructing of the next portion of the link list involves storing, into the link list RAM 821, the “next” free pointer value (that was just retrieved from the head of the free pointer queue 822 in response to the return of the exhausted pointer) at the address specified by the returned, exhausted pointer value.

<figref idref="DRAWINGS">FIG. 10</figref> helps demonstrate the second sub-action in more detail. <figref idref="DRAWINGS">FIG. 10</figref> illustrates a simplistic perspective 1000 of the link-list RAM 821 of <figref idref="DRAWINGS">FIG. 8</figref>. Here, a pair of links that track the pointer values used to store a pair of packets, respectively, are observed. The first packet is stored in the memory banks with pointer values 3, 12, 6, 1, 9; and, the second packet is stored in the memory banks with pointer values 7-18-13-4-8. Taking the first packet as an example, when the first packet arrived to the input port, a request was made to the pointer manager 814 for a fresh head pointer (so that the first packet could begin to be written into the memory banks). At the time the request was processed by the pointer manager 814, a pointer value of “3” was at the head of the free pointer value queue 823; and, in response to the request, the pointer value of “3” was read 901 (along data bus 811) from the free pointer queue RAM 822 and issued to the write hub (at output 815b) so that the first packet could begin to be written into memory.

Eventually, the write hub exhausted the pointer value of “3” and returned it to the pointer manager (at input 815a) as a second request for a pointer for the first packet. At the time this second request was processed by the pointer manager 814, a pointer value of “12” was at the head of the free pointer value queue 822; and in response to this second request, the pointer value of “12” was read from the free pointer queue RAM 822. A pair of uses arose from this reading. First, the pointer value of “12” was issued to the write hub (at output 815b) so that the write hub could continue writing the first packet into the memory banks 3071 through 3074. Second, the returned pointer value of “3” was used as an address for writing the pointer of value of “12” into the link list RAM 821. As such, after this write, a data value of “12” is stored at address “3” in the link list RAM 821. This explains data entry 1001 in <figref idref="DRAWINGS">FIG. 10</figref>.

In order to write the “next linked to” pointer value of an exhausted pointer value into the link list RAM 821 at the address of the exhausted pointer value, the write channel logic 804 of the link list RAM 821 should have access to: 1) the exhausted pointer (for using as an address along address bus 812); and, 2) the “next linked to” pointer value that appears at the output of the free pointer queue RAM read channel logic 803 (for using as a data value along data bus 813). In the embodiment of <figref idref="DRAWINGS">FIG. 8</figref>, both of these are accounted for as input 815a runs to the address input of the write channel logic 804; and, output 815b runs to the data input of the write channel logic 804. The link list for an entire packet can be constructed using a similar process as that just described above.

Eventually the write hub finished writing the first packet and further pointer values such that no further requests for pointer were made (for the first packet). Here, note that an “End-Of-Packet (EOP)” data value is stored within the link list RAM 821 for the last pointer value used to store pieces of the first packet. Here, some communication should be made to the pointer manager 814 signify to the pointer manager 814 that another pointer is not being requested. In an embodiment, the write hub returns the “last” pointer value needed for a packet to the pointer manager 814; but, the returned “last” pointer value has an extra bit of information appended to it that identifies it as the last pointer value needed for the packet. In response, write channel logic 804 writes an EOP into the link list RAM 821 at the address of the returned “last” pointer value. In alternate embodiments, no such communication between the write hub and the pointer manager needs to be made if the size of the packet is known to the pointer manager (e.g., by including the size of the packet in the request for a fresh head pointer that is received from the request manager 306).

After a packet has been fully written into the memory banks 3071 through 3074, it remains stored in the memory banks until a grant is received for the packet from the arbiter. Here, the grant includes the head pointer value for the packet (e.g., pointer value “3” for the first packet as observed in <figref idref="DRAWINGS">FIG. 10</figref>). The scheduler 309 schedules a read hub to read the packet from memory, extracts the head pointer from the grant, and forwards it to the scheduled read hub. Upon receipt of the head pointer, the read hub begins to read the packet from the memory banks at the head pointer position; and, in those embodiments where the write hub employs more that one memory address per pointer value, the read hub correspondingly generates the same memory addresses per pointer value. Eventually, the head pointer will be exhausted for the purposes of reading the packet from memory; and, as such, the exhausted head pointer will be forwarded from the read hub to the pointer manager 814.

The return of a pointer value to the pointer manager 814 from a read hub signifies that the packet information that is stored at the returned pointer value's corresponding memory bank location(s) have been read from memory and now represent “stale” information that is free to be written over. As such, the returned pointer value is written into the tail of the free pointer queue 823. Here, as seen in <figref idref="DRAWINGS">FIG. 8</figref>, in order to convert a pointer value that is returned from a read hub into a next entry into the tail of the free pointer queue 823, the returned pointer value is returned at input 817a so that the write channel logic 802 of the free pointer queue RAM 822 can write the returned pointer value along data bus 808. Note that, as the pointer queue RAM 822 is used to implement a simple FIFO queue, the pointer queue RAM's write channel logic 802 and read channel logic 803 are together responsible for generating the addresses at address busses 809 and 810, respectively, that result in a simple FIFO queue being realized from RAM 822.

The return of an exhausted pointer value from a read hub can also be interpreted as a request for looking up, from the corresponding packet's link list, the next linked to pointer value for the packet. For example, referring briefly to <figref idref="DRAWINGS">FIG. 10</figref> again, upon the return of the head pointer “3” from the read hub that is reading the first packet from the memory banks, the returned value of “3” is used as a look-up parameter, against the link list for the first packet, so that the next “linked-to” pointer value needed to successfully continue reading the packet from memory (“12”) can be retrieved. As such, referring back to <figref idref="DRAWINGS">FIG. 8</figref>, an exhausted pointer value that is returned from a read hub is not only entered at the tail of the free pointer queue; but also, is used as an address for performing a read operation into the link list RAM 821.

As such, according to the pointer manager 814 architecture observed in <figref idref="DRAWINGS">FIG. 8</figref>, the read channel logic 805 of the link list RAM 821 accepts a returned pointer value from a read hub and uses it to form an address that is presented on address bus 812. The next linked to pointer value that is read from the link list RAM in response appears on data bus 820 and is presented at output 817b to the read hub that sent the returned pointer value. The activity of returning an exhausted pointer value to the tail of the free pointer queue and using the exhausted pointer value as a look up parameter for looking up the next linked to pointer value for the continued reading of the packet is represented as the third 903 of the three basic functions 901, 902, 903 of the pointer manager that are shown in <figref idref="DRAWINGS">FIG. 9</figref>.

Note that, for simplicity, the pointer manager 814 embodiment observed in <figref idref="DRAWINGS">FIG. 8</figref> is on-dimensional in the sense that a single input from a read hub 817a is shown and a single output to a read hub 817b is shown. By contrast, referring to <figref idref="DRAWINGS">FIG. 3</figref>, separate input/outputs RPTR_1 through RTPR_33171 through 3173 are shown for each read hub 3161 though 3163. Here, some form of recognition as to which read hub a next linked to pointer value (that was just read from the link list pointer) should be sent to is appropriate; and, some form of correlation can be constructed into the pointer manager 314, 814 so that the next linked to pointer appears at the output that corresponds to the input where the returned pointer value was received (e.g., if a returned pointer value appears at input 3171, the next linked to pointer appears at output 3171). For simplicity a bi-directional communication path is observed between each read hub and the pointer manager. However, each input may also be separate from its corresponding output as suggested by <figref idref="DRAWINGS">FIG. 8</figref>.

Read Operation

<figref idref="DRAWINGS">FIG. 11</figref> shows a design embodiment for a read hub 1116 that may be used to implement any of the read hubs 3161 through 3163 that are observed in <figref idref="DRAWINGS">FIG. 3</figref>. According to the design approach of <figref idref="DRAWINGS">FIG. 11</figref>, a register ring architecture is used to control the address values that are applied to the memory banks during the reading of information from the memory banks. Here, pointer values are received for each buffers worth of information that is to be read from memory. A pointer value is inserted into the ring and circulates through the ring until the information to be read with the pointer value has been read from the memory banks and stored, as appropriate, into the Tx queues 11061 through 11063. After the pointer value has been exhausted (e.g., after each address to be applied from the original pointer value is used), it is removed from the ring (e.g., so that it can be replaced by a “next” linked pointer value so that the packet can continue to be read from memory).

The read hub architecture of <figref idref="DRAWINGS">FIG. 11</figref> can be adapted to allow the read hub 1116 to support at least a pair of operating modes. For example, according to one embodiment, the read hub 1116 can be configured to operate in either a low speed mode or a high speed mode. Here, and as described above with respect to the operation of the scheduler, different read hub operating speeds result in a different rate at which data is read from memory for a particular packet. For example, in a further embodiment, the low speed mode corresponds to a 1× Infiniband speed (at which packets are read from memory at a speed that is compatible with a 1× Infiniband speed); and, the high speed mode corresponds to a 4× Infiniband speed (at which packets are read from memory at a speed that is compatible a 4× Infiniband speed).

In an even further embodiment, during the low speed mode, the read hub can handle as many as four separate packet streams at a 1× compatible speed of operation (such that the total bandwidth of operation is compatible with a 4× speed); but, during the high speed mode, can handle only one packet stream at a 4× compatible speed of operation. Here, the ability to tweak the speed at which packets are read from memory allows an overall switch to more efficiently manage its internal traffic flows in the sense that both the overloading of low speed outgoing links and the starving of high speed outgoing links should be avoided. A more detailed explanation of the reading process for both a low speed mode and a high speed mode for such an embodiment are discussed immediately below with respect to <figref idref="DRAWINGS">FIGS. 12</figref>a,b and 13a,b, respectively.

a. Low Speed Mode Read Operation

<figref idref="DRAWINGS">FIGS. 12</figref>a and 12b correspond to methodologies that may be used to implement a low speed mode of operation (noting that the methodology of <figref idref="DRAWINGS">FIG. 12</figref>b can be viewed as an embodiment of a more detailed implementation of the methodology of <figref idref="DRAWINGS">FIG. 12</figref>a). Here, according to at least one embodiment, the low speed mode of operation corresponds to a 1× Infiniband speed. Furthermore, as the read hub embodiment 1116 of <figref idref="DRAWINGS">FIG. 11</figref> is capable of operating in either a high speed mode or a low speed mode, the “extra” bandwidth associated with reading a stream of packets at a low speed rate can be used to read multiple low speed packet streams. For example, according to one approach, while in low speed mode, the read hub is able to separately manage four different packet readings at a 1× compatible speed. As an example, the ability of the read hub 1116 to separately manage the reading of up to four low speed streams of packets is described with respect to <figref idref="DRAWINGS">FIGS. 6</figref>b, 11, 12a and 12b.

<figref idref="DRAWINGS">FIG. 6</figref>b shows an example of the state of a read hub's register contents over the course of sixteen scheduler cycles observed in <figref idref="DRAWINGS">FIG. 6</figref>a. Note that, for the sake of consistency with the example of <figref idref="DRAWINGS">FIG. 6</figref>a, the example of <figref idref="DRAWINGS">FIG. 6</figref>b may be viewed as the low speed operation of Read_Hub_13161 of <figref idref="DRAWINGS">FIG. 3</figref>. Better said, as <figref idref="DRAWINGS">FIG. 6</figref>a has scheduled Read_Hub_1 for low speed operation, <figref idref="DRAWINGS">FIG. 6</figref>b can be viewed as an embodiment of the operation of Read_Hub_13161 responsive to the scheduling of the scheduler that is observed in <figref idref="DRAWINGS">FIG. 6</figref>a. <figref idref="DRAWINGS">FIGS. 12</figref>a and 12b show methodologies that can be used to describe the operation observed in <figref idref="DRAWINGS">FIG. 6</figref>b. <figref idref="DRAWINGS">FIG. 6</figref>b demonstrates an example of the processing involved while throttling up to four separate low speed traffic streams. Firstly, a brief high level discussion will be provided by reference to <figref idref="DRAWINGS">FIG. 12</figref>a; then, a more detailed discussion of a particular methodology flow will be provided that focuses on the methodology presented in <figref idref="DRAWINGS">FIG. 12</figref>b.

In the combined example of <figref idref="DRAWINGS">FIGS. 6</figref>a and 6b, no reading activity takes places during Cycle 1. However, as of Cycle 2, the scheduler 309 has suddenly scheduled Read Hub_1 as a low speed mode. Referring briefly back to <figref idref="DRAWINGS">FIG. 5</figref>, which shows an embodiment 509 of the scheduler 209, the arrival of a grant from the arbiter for a “first” packet that, according to the grant, is to be read from the memory banks 3071 through 3073 at a low speed, causes the read demand logic 524 to command the ring control logic 524 to insert the appropriate “Read_Hub_1” data structure into the scheduler's first register ring 5261 (e.g., because it is the first register in the scheduler's register ring that is available at Cycle 2). This gives Read_Hub_13161 access to the first memory bank 3071 at Cycle 2. Here, note that the arrival of a low speed grant into the low speed queue 520 for the first packet corresponds to an embodiment of transition 1105 of <figref idref="DRAWINGS">FIG. 7</figref>. As such, one hub (Read_Hub_13161) is identified as a low speed read hub (which corresponds to state 702 of <figref idref="DRAWINGS">FIG. 7</figref>).

As part of the scheduling of Read_Hub_1, the head pointer for the first packet “P1” is extracted from the grant and is forwarded to Read_Hub_1 along communication line/bus IPTR_13211, 5211. In response, referring to <figref idref="DRAWINGS">FIGS. 3 and 7</figref>, Read_Hub_13161, 1116 inserts the pointer value “P1” into register REG111031 in time for Cycle 2. As such, as observed in <figref idref="DRAWINGS">FIG. 6</figref>b, the pointer value P1 has been placed into the REG.1 register as of Cycle 2. According to a low speed mode of operation for the read hub 1116, referring to <figref idref="DRAWINGS">FIGS. 3</figref>, 11 and 12a, another register ring (such as the ring of registers 11231 through 11234 observed in <figref idref="DRAWINGS">FIG. 11</figref>) is used to control the address values presented to each memory bank 3071 through 3074. That is, referring briefly to <figref idref="DRAWINGS">FIGS. 3 and 11</figref>, the contents of register 11231 (REG. 1) are used to provide a read address to memory bank 3071; the contents of register 11232 (REG. 2) are used to provide a read address to memory bank 3072; the contents of register 11233 (REG. 3) are used to provide a read address to memory bank 3073; and, the contents of register 11234 (REG. 4) are used to provide a read address to memory bank 3074.

The read hub 1116 is configured to focus upon 1251 each register in the ring at a rate of one register per cycle (such that, for a particular round trip through the ring, the answer to inquiry 1253 is “no” until the last register in the ring has been focused upon). Here, a focused upon register is a register whose turn it is to generate a read address (noting that, as described in more detail below, a focused upon register may fail to generate a read address during its turn (e.g., if its contents include an invalid pointer).

If, during a cycle when a particular register is being focused upon, the read hub 1116 also happens to be given access to the register's corresponding memory bank (and if the register's contents are deemed to be a valid read address), the read hub reads 1208 a buffer's worth of data from the register's corresponding memory bank and stores it into an appropriate Tx queue (e.g., one of queues 11061 though 11063 as observed in <figref idref="DRAWINGS">FIG. 11</figref>). After the last register in the ring has been focused upon (such that the answer to inquiry 1253 is “yes”), the register contents are shifted 1254 and the entire process repeats 1250.

<figref idref="DRAWINGS">FIGS. 6</figref>b, 11 and 12b may be used to help demonstrate an embodiment of a more detailed approach. Starting at sequence 1201 of <figref idref="DRAWINGS">FIG. 12</figref>b, the hub reading process, for the sake of convenience (and as observed in <figref idref="DRAWINGS">FIG. 6</figref>b at Cycle 2), can be viewed as starting at the first register 11231 in the ring. In an embodiment, an “invalid” pointer value is used to indicate that no reading activity is to occur with a register that is presently storing an invalid pointer. As such, if a read hub is not deemed active by the scheduler, invalid pointer values continuously circulate through the register ring until the scheduler activates the hub (e.g., by sending it a first head pointer). The methodology described with respect to <figref idref="DRAWINGS">FIG. 12</figref>b can be assumed to be within such a state, with respect to the read hub 1116, during Cycle 1 as observed in <figref idref="DRAWINGS">FIG. 6</figref>b.

Here, with register REG. 111231 being the next register in the ring starting from the beginning of the loop, register REG. 111231 becomes the first focused upon or “active” register 1202 within the ring. Some further explanations are presently in order. As will become evident, the circuitry 1101 responsible for controlling the register 11231 through 11234 contents steps through and focuses upon each register in the ring at a rate of one register per cycle. While a particular register is being focused upon, it may be referred to as the “active” register. When a register becomes the active register a set of implications arise. These implications include an “an active pointer value”, an “active packet”, an “active Tx queue” and an “active memory bank”. The active pointer value is found within the contents of the active register and corresponds to an address value used for addressing the register's corresponding memory bank.

The “active memory bank” is the memory bank that is targeted by the active register (i.e., the register's corresponding memory bank (e.g., REG1 corresponds to memory bank 3071 etc.). The “active packet” is the packet whose contents are at least partially stored at the “active pointer value” (e.g., as pointer value “P1” is a memory address where the first packet to be granted in <figref idref="DRAWINGS">FIGS. 6</figref>a and 6b is stored). For each subsequent pointer that is fetched (e.g., from the pointer manager) in order to read a portion of the same packet, all of these pointers can be said to have the same active packet. The “active Tx queue” is the Tx queue (e.g., one of Tx queues 11061 through 11064) where the portions of the active packet are enqueued after they have been read from memory.

Continuing with an approach were four separate addresses evolve from the head pointer provided by scheduler (and each subsequent pointer for a packet as provided by the pointer manager), once four separate reads have been made from each memory bank, the pointer value is “exhausted” (because no further reads can be made from it) and the next-linked to pointer value (from the exhausted pointer value) has to be received from the pointer manager so that addresses sufficient for four more reads can be made. This operation has been described above with respect to the operation of the pointer manager. An invalid pointer value may be marked with an extra bit within the register space that is used to signify that no read is take place. Note that, under inactive conditions (i.e., no packets are waiting to be read by a read hub), no reading activity will take place from the memory banks 3071 through 3074. As such, the register's 11231 through 11234 will circulate invalid pointer values to ensure that no reading activity takes place.

Recalling that the example of <figref idref="DRAWINGS">FIG. 6</figref>b can be assumed to with such a state at Cycle 1, and recognizing that the active register for Cycle 2 is register 11231, note that methodology of <figref idref="DRAWINGS">FIG. 12</figref>b leads to sequence 1205 because the invalid pointer presently within register 11231 needs to be replaced with the first packet's head pointer “P1” in order to commence the reading of the first packet. The replacement of the invalid pointer with the valid pointer “P1” causes the head pointer “P1” to be written into register 11231. Note that the register ring includes a first multiplexer 11021 whose output determines the contents of the first register 11231. Here, in order to implement sequence 1205, the register ring control logic 1101: 1) places the head pointer value “P1” on the first multiplexer input channel 1111; and, 2) manipulates the channel select input 1110 so that the fresh head pointer value “P1” is written into the first register 11231. Cycle 2 of <figref idref="DRAWINGS">FIG. 6</figref>b corresponds to this state because a value of “P1” is observed for the REG.1 register 11231 during Cycle 2. With the invalid pointer value having been replaced 1205 with the valid head pointer value “P1”, the methodology flows to sequence 1220 (because the active pointer is now valid).

Sequence 1220 indicates that a read only takes place if the active register has been given access to the active memory bank. From the discussion of <figref idref="DRAWINGS">FIG. 6</figref>a, recall that the scheduler unit 309 is responsible for determining during which cycles the read hub 3161 will have access to a particular memory bank. This access, for each of the instances provided in <figref idref="DRAWINGS">FIG. 6</figref>b, is shown in <figref idref="DRAWINGS">FIG. 6</figref>a. That is, Read_Hub_13161 only has access to memory bank 13071 during Cycles, 2, 6, 10, 14, etc; memory bank 23072 during Cycles 3, 7, 11, 15, etc., etc. Exactly when Read_Hub_13161 has been given access to a particular memory bank has been indicated in <figref idref="DRAWINGS">FIG. 6</figref>b through the use of shaded regions. That is, if a region is shaded in <figref idref="DRAWINGS">FIG. 6</figref>b, Read_Hub_1 has access to the memory bank during the cycle that the shaded region corresponds to. Here, note that the shaded regions of <figref idref="DRAWINGS">FIG. 6</figref>b merely correspond to the scheduling properties of <figref idref="DRAWINGS">FIG. 6</figref>a being superimposed upon the read hub ring activity of <figref idref="DRAWINGS">FIG. 6</figref>b.

As such, sequence 1220 of <figref idref="DRAWINGS">FIG. 12</figref>b effectively tests whether or not the active register has been given access to its corresponding memory bank. If not, no read operation takes place 1209 and the cycle becomes an empty read cycle (i.e., no reading from memory takes place); if so, the next buffer's worth of information is read 1208 from the active memory bank and is placed into the active Tx queue. Referring to <figref idref="DRAWINGS">FIG. 6</figref>b, note that the active register REG 111231 does have access to its corresponding memory bank (memory bank 3071) during Cycle 2; and, as such, the first buffer of information for the first packet is read 1208 from memory bank 3071 at address “P1”. Assuming that the active Tx queue for the first packet is Tx queue 11061, note that part of the reading process for the first packet involves correctly manipulating the read port multiplexer 11151 that feeds Tx queue 11061. Here, each read port multiplexer 11151 through 11154 is used to properly couple its corresponding Tx queue to any of the memory banks as appropriate.

In an embodiment, the contents of the active register (e.g., active register 11231 in the present case) not only include the active pointer value (e.g., “P1”) but also include an identification of the Tx queue into which the portions of the packet that are read with the active pointer value are to be enqueued into. Here, the contents of the register are used not only to present an address read value; but also, to control the channel select line of the corresponding read port multiplexer. For example, with respect to the read that occurs in Cycle 2 of <figref idref="DRAWINGS">FIG. 6</figref>b, a first portion of the contents of register REG111231 are directed along the memory bank 1 address bus ADDR_BANK_1 (which is drawn as an output from REG111231) and a second portion of the contents of register REG111231 are used to manipulate the channel select line of multiplexer 11151 (where no such output from the register has been drawn for simplicity); where, the second portion effectively corresponds to a value that identifies the proper Tx queue (e.g., “00” if Tx queue 111031 is the Tx queue where the portions of the packet being reads are stored; “01” if Tx queue 211032 is the Tx queue where the active packet is stored; etc.).

Note that these first and second portions (i.e., pointer value and Tx queue identifier) may “ride” through the ring together with one another so that whenever a read is to actually take place from a particular register, the correct Tx queue can be immediately identified along with the address value to be used for the read. Note that read hub input/outputs 1161 through 1164 of <figref idref="DRAWINGS">FIG. 11</figref> correspond to read hub input/outputs 361 through 364 of <figref idref="DRAWINGS">FIG. 3</figref>. Here, a complete input/output for a memory read includes both the address and the data to be read. <figref idref="DRAWINGS">FIG. 3</figref> is drawn simplistically to suggest that a single multiplexer 3081 through 3083 is used to channel both the data from and the address to their respective memory banks 3071 through 3074. Although such a design is possible, it is also possible to use a pair of multiplexers for each memory bank 3071 through 3074—one multiplexer for propagating address signals and a second multiplexer for propagating data.

Continuing with the example then of <figref idref="DRAWINGS">FIG. 6</figref>b and referring to <figref idref="DRAWINGS">FIG. 12</figref>b, after the first buffer has been read 1208 from memory bank 1, the next active register (register REG211232) is focused upon as the active register 1202, 1103 for the following cycle (Cycle 3). Here, because the packet can be assumed to be more than four buffer's worth of information, more than four reads are to be made from the memory banks in this example. As such, sequence 1210 is avoided and the answer to inquiry 1211 is “no” because the present round trip through the ring has not been completed. As a blank region in the chart of <figref idref="DRAWINGS">FIG. 6</figref>b corresponds to the placement of an invalid pointer in the corresponding register space, <figref idref="DRAWINGS">FIG. 6</figref>b indicates that the contents of the second register REG211232 in the ring include an invalid pointer during Cycle 3. Because the example of <figref idref="DRAWINGS">FIG. 6</figref>b corresponds to a situation where a fresh head pointer for another low speed packet has not been received by Read_Hub_1 as of Cycle 3, during Cycle 3, the process flows through the “invalid pointer” paths of sequences 1205 and 1209. As such, no read activity takes place during Cycle 3.

As of Cycle 4, however, a grant for a second packet requiring a low speed transmission rate has been received by the scheduler 309 and the head pointer P2 for that packet has been entered into the register ring of Read_Hub_1. Because the scheduler 309 has already activated Read_Hub_13161 in low speed mode (to handle the first packet), and because a read hub in low speed mode can handle the reading of as many as four separate 1× speed packets, the scheduler 309 will recognize that Read_Hub_13161 has the capacity to handle the reading of the second low speed packet. Here, referring briefly to <figref idref="DRAWINGS">FIG. 5</figref>, note that the scheduler 509 may make reference to the state register 5231 for Read_Hub_1 to recognize not only that Read_Hub_1 has been configured into low speed mode; but also, that Read_Hub_1 is currently entertaining the reading of only one low speed packet and can therefore entertain the reading of the second low speed packet.

In a further embodiment, the grant for a packet not only informs the scheduler of the proper speed at which the packet should be read from memory; but also, informs the scheduler of which memory bank is the packet's “starting” memory bank. Here, referring to <figref idref="DRAWINGS">FIG. 3</figref>, the write hub 305 may be configured to allow an incoming packet to start to be written into whichever memory bank (amongst memory banks 3071 through 3074) happens to be first available for writing into. A patent application describing such as write hub entitled “APPARATUS AND METHODOLOGY FOR A WRITE HUB THAT SUPPORTS HIGH SPEED AND LOW SPEED DATA RATES”, filed simultaneously with the present application as U.S. application Ser. No. 10/431,875, now U.S. Pat. No. 7,124,241 and assigned to the same assignee as the present application describes such a write hub. As such, if the packet is to be correctly read from memory (i.e., where the buffers are read from memory in the proper order), the first buffer's worth of information for a packet should be the first information read for the packet. As such, the first read for a packet should be made from the particular bank where the first buffer for the packet was written. In order to convey this information, the grant for a packet includes information that identifies which memory bank has the packet's first buffer.

In response to this information, and by reference to the appropriate read hub's state register, in an embodiment, the scheduler is configured to provide the appropriate read hub with the head pointer for the packet so as to allow the packet to begin to be read from its appropriate “starting” memory bank. For example, according to one approach, the scheduler recognizes when a register within the register ring of the read hub will be both: 1) scheduled to have access to the packet's starting memory bank; and, 2) will be available to receive the head pointer for the packet. As a consequence of conditioning the timing of the issuance of a head pointer to a read hub based upon these factors, by inserting the head pointer into the register that corresponds to the starting memory bank in time to perform a read operation from it while the register has access to the starting memory bank, the first buffer of a packet is guaranteed to be read from its proper “starting” memory bank. In such a case, according to the example of <figref idref="DRAWINGS">FIG. 6</figref>b, the first packet (whose head pointer is P1) has memory bank 3071 as its starting memory bank. As such, the head pointer P1 was entered into register REG111031 for the cycle (Cycle 2) when REG111031 had access to the first packet's starting memory bank 3071. Similarly, the head pointer P2 was entered into register REG311033 for the cycle (Cycle 4) when REG311033 had access to the second packet's starting memory bank 3073.

Referring to <figref idref="DRAWINGS">FIGS. 6</figref>b and 12b, at Cycle 4, the process runs through sequences 1205 and 1208. The subsequent cycle (Cycle 5) is an empty cycle 1209. After Cycle 5 has been executed, the answer to inquiry 1211 will be “yes”. That is, after Cycle 5, each register will have had a turn as being recognized as the active register; and, as such, a complete run-through the ring will have been completed. As such, between Cycles 5 and 6, the contents of the registers REG1 through REG411231 through 11234 are shifted 1212 forward in the ring by one register unit (i.e., the contents of register REG111231 are shifted into register REG211232; the contents of register REG211232 are shifted into register REG311233; etc.). Note that because the pointer value being shifted out of register REG411144 and into REG111141 is an invalid pointer, the pointer value does not need to be incremented. Incrementing a valid and non exhausted pointer value that has been shifted out of the last register REG4 in the ring is a technique that allows for the generation of more than one address per pointer value that is received from the pointer manager 314 as described below.

Referring still to <figref idref="DRAWINGS">FIG. 6</figref>b, observe that Cycle 6 is an empty cycle for Read_Hub_1 because REG1 has the invalid pointer (that was shifted into REG1 from REG4 between Cycles 5 and 6). During Cycle 7 a read for the first packet with pointer value P1 is made from memory bank 3072. Now, referring to <figref idref="DRAWINGS">FIGS. 6</figref>a and 6c, note that a grant for third packet (which happens to be a high speed packet and whose starting memory bank is memory bank 3071) arrives in time to begin to be read at Cycle 7 from memory bank 3071. Note that, from <figref idref="DRAWINGS">FIG. 6</figref>a, the scheduler has identified Read_Hub_23162 as the read hub that will be responsible for reading the third packet (as represented by the placement of a “Read_Hub_2” data structure into the scheduler's register as seen in <figref idref="DRAWINGS">FIG. 6</figref>a). Furthermore, the scheduler has issued the head pointer for the third packet “P2” to Read_Hub_23162 in time for it to be entered into register REG111231 so that a read can take place from the third packet's starting memory bank 3071 during Cycle 7. More details regarding the reading of high speed packets is provided in a following sub-section.

A grant for a fourth packet (which happens to be a low speed packet and whose starting memory bank is memory bank 3073) is received by the scheduler in sufficient time such that the packet can begin to be read as of Cycle 8. Again, because the scheduler 309 has already activated Read_Hub_13161 in low speed mode, and because a read hub in low speed mode can handle the reading of as many as four separate 1× speed packets, the scheduler 309 will recognize that Read_Hub_13161 has the capacity to handle the reading of the fourth packet. As such, the head pointer for the fourth packet P4 is issued to Read_Hub_1 and entered into REG311233 so that an initial read for the fourth packet (from the starting memory bank 3073) can take place during Cycle 8. During Cycle 9, a second read for the second packet takes place. After Cycle 9, another round trip through the register ring takes place and the contents of the register ring are shifted forward. Here, a buffer is read for each of the three low speed packets; and, note that a fourth low speed packet is scheduled and begins to read from its starting memory bank 3072 during Cycle 11. Thus, as of Cycle 11 and the following cycles observed in <figref idref="DRAWINGS">FIG. 6</figref>b, the full capacity of Read_Hub_13161 has been reached.

After Cycle 17 has been completed (which is not shown in <figref idref="DRAWINGS">FIG. 6</figref>b), the pointer value “P1” will be shifted 1212 out of register 11234. Here, even though the value “P1” has been used to write to each memory banks 3071 through 3074, recall that a scheme may be used to derive more than one address value per pointer value received from the pointer manager 314. According to the embodiment of <figref idref="DRAWINGS">FIG. 11</figref>, an incrementer 1104 is used to increment 1214 the value removed from register 11074 by one (i.e., “+1”). Here, consistent with discussions provided in prior sections, in an embodiment, pointer values issued by the pointer manager (such as the value “P1”) take the form XXX . . . XX00. That is, the least significant bits are of the form “00”. Upon the rotation of the initial pointer value P1 out of the last register 11234 after Cycle 17, the least significant pair of bits are incremented from “00” to “01”.

Here, referring to <figref idref="DRAWINGS">FIG. 6</figref>b, this means that while Cycles 2 through 17 use an address value of P1 having the form XXX . . . XX00 within the ring, Cycles 18 through 33 will use an address value within the ring of P1* having the form XXX . . . XX01 where the same binary representation is used for the higher order content XXX . . . XX through Cycles 2 through 33. Moreover, the same XXX . . . XX content is used as a basis for pointer value P1** (=XXX . . . XX10) used within the ring during Cycles 34 through 49 and pointer value P1*** (=XXX . . . XX11) used within the ring during Cycles 50 through 65. After Cycle 65, however, the basis content XXX . . . XX of the pointer value P1 will be exhausted requiring a fresh pointer from the pointer manager. Note that this will cause the methodology of <figref idref="DRAWINGS">FIG. 12</figref>b to flow through sequence 1206 during Cycle 66, wherein, the pointer value P1*** is replaced 1206 by the next pointer value that the pointer manager has link listed to pointer P1.

Before commencing with a discussion of high speed mode operation, referring to <figref idref="DRAWINGS">FIG. 12</figref>b, note that the register ring control logic 1101 may be configured to replace 1210 a valid pointer value with an invalid pointer value once the packet for which the valid pointer was dedicated is completely read from memory. That is, once a packet is completely read from memory, there is no need for one of its valid pointer values to be circulated within the ring. As such, its pointer value can be replaced with an invalid pointer value after its packet has been completely read from memory. Here, replacing a valid pointer with an invalid pointer is particularly useful if there are no other packets waiting to be immediately read from memory. In a further embodiment, the register ring control logic 701 may be designed to replace a pointer value for a completely read packet with a fresh head pointer for the next packet waiting to be read that has an appropriate starting memory bank (e.g., the same starting memory bank that the active register corresponds to). Note that the ring control logic 1101 can recognize that a packet has been completely read from memory when an end of packet EOP parameter is received from the pointer manager. Alternatively, if the read hub is informed of the size of the packet (e.g., by passing the size of the packet along with the packet's head pointer within the grant from the arbiter; which, in turn, are both forwarded to the appropriate read hub).

b. High Speed Mode Operation

Referring to <figref idref="DRAWINGS">FIG. 3</figref>, the above discussion related to the low speed operation of a read hub. Recall, however, that a read hub (in various embodiments) may be configured to support high speed operation as well. In an embodiment, high speed operation corresponds to a 4× Infiniband speed. Recall from the discussion in the preceding section that <figref idref="DRAWINGS">FIG. 6</figref>c shows the state of the register ring over the course of 16 consecutive cycles in high speed mode for Read_Hub_23162; and, that Read_Hub_2 begins to read a packet at Cycle 7. Here, <figref idref="DRAWINGS">FIGS. 13</figref>a and 13b show a high level embodiment and a more detailed embodiment, respectively, of a methodology that may be used to control the operation of a read hub during high speed mode. Referring to <figref idref="DRAWINGS">FIGS. 6</figref>c and 13a, note that one valid pointer value exists in the ring at any time; and, the register contents are shifted once per cycle (rather than once per four cycles as observed in <figref idref="DRAWINGS">FIGS. 6</figref>b and 6c). This difference in operation effectively converts the processing of the read hub toward a single packet (as such, only one pointer is in the ring at a time) that is operating at four times the speed of a low speed link (hence one shift per cycle) as compared to the low speed mode operation of the hub.

That is, note that the packet that pointer “P3” refers to in <figref idref="DRAWINGS">FIG. 6</figref>c enjoys a read from memory every cycle whereas the packet that pointer “P1,” referred to in <figref idref="DRAWINGS">FIG. 6</figref>b enjoys a read from memory once every four cycles (on average). As such, the packet being read in <figref idref="DRAWINGS">FIG. 6</figref>c is being read at four times the speed of the packet(s) being read in <figref idref="DRAWINGS">FIG. 6</figref>b. According to the methodology of <figref idref="DRAWINGS">FIG. 13</figref>a, starting at the beginning of the ring at register REG111231, the pointer value that is entered at the start of the ring completes a round trip through the ring at a rate of one shift per cycle. As observed in the methodology of <figref idref="DRAWINGS">FIG. 13</figref>a, whether or not the round trip through the ring is spent idling 1304, 1305, 1306 (i.e., no reads) or reading at a rate of one read per cycle 1307, 1308, 1309 (as observed in <figref idref="DRAWINGS">FIG. 6</figref>c) depends upon whether or not the pointer value is invalid or valid. Each time a round trip 1301 through the ring is completed (e.g., the pointer value is shifted out of the last register REG411234), the pointer value for the next round trip through the ring is determined 1303.

<figref idref="DRAWINGS">FIG. 13</figref>b elaborates in more detail on one approach for determining the pointer value for each round trip through the ring. Note that the term “active packet” corresponds to a packet that was being read during the immediately prior round trip through the ring. According to the approach of <figref idref="DRAWINGS">FIG. 13</figref>b, the pointer value is set to a new head pointer 1310 if a new head pointer is received from the scheduler. The pointer value is incremented 1311 if the active packet has not yet been completely read from memory and the pointer value is not yet exhausted. The pointer value is set to the next linked-to pointer value for the packet 1312 if the active packet has not yet been completely read from memory and the pointer value is exhausted. The pointer value is set to an invalid pointer value 913 if the active packet has been completely written from memory and a fresh head pointer for a next packet has not been received.

Lastly, note that the embodiments discussed above with respect to <figref idref="DRAWINGS">FIGS. 13</figref>a and 13b may be construed so as to correspond to an approach where a high speed mode read must start with the first register 11231 in the register ring (i.e., a packet's head pointer must first be used from register 11231 of <figref idref="DRAWINGS">FIG. 11</figref> during high speed mode). It is important to realize that alternative embodiments may be readily engineered where a packet may begin to be read from a register other than the first register in the ring (and therefore may first begin to be read from any of the memory banks rather than only a particular memory bank) through slight modification of the low speed methodology observed in <figref idref="DRAWINGS">FIGS. 12</figref>a and 12b.

In particular, <figref idref="DRAWINGS">FIG. 12</figref>a can be modified to describe a “read first from any bank” high speed mode hub simply by removing sequence 1254 (so that the “yes” output of sequence 1253 directly feeds sequence 1250) and inserting sequence 1254 between sequences 1252 and 1253 (so that sequence 1252 feeds sequence 1254; and, sequence 1254 feeds sequence 1253). Moreover, <figref idref="DRAWINGS">FIG. 12</figref>b can be modified to describe a more detailed implementation of a “read first from any bank” high speed mode hub simply by moving sequence 1212 to just prior to sequence 1211 in the observed method flow (to ensure that the register contents are shifted once per cycle tick regardless if a read operation is 1208 or is not 1209 performed). Moreover, for a read hub capable of handling the reading of only a single packet at a time it should be understood that only a single valid pointer should be in the ring.

Note also that embodiments of the present description may be implemented not only within a semiconductor chip but also within machine readable media. For example, the designs discussed above may be stored upon and/or embedded within machine readable media associated with a design tool used for designing semiconductor devices. Examples include a netlist formatted in the VHSIC Hardware Description Language (VHDL) language, Verilog language or SPICE language. Some netlist examples include: a behaviorial level netlist, a register transfer level (RTL) netlist, a gate level netlist and a transistor level netlist. Machine readable media also include media having layout information such as a GDS-II file. Furthermore, netlist files or other machine readable media for semiconductor chip design may be used in a simulation environment to perform the methods of the teachings described above.

Thus, it is also to be understood that embodiments of this invention may be used as or to support a software program executed upon some form of processing core (such as the CPU of a computer) or otherwise implemented or realized upon or within a machine readable medium. A machine readable medium includes any mechanism for storing or transmitting information in a form readable by a machine (e.g., a computer). For example, a machine readable medium includes read only memory (ROM); random access memory (RAM); magnetic disk storage media; optical storage media; flash memory devices; electrical, optical, acoustical or other form of propagated signals (e.g., carrier waves, infrared signals, digital signals, etc.); etc.

In the foregoing specification, the invention has been described with reference to specific exemplary embodiments thereof. It will, however, be evident that various modifications and changes may be made thereto without departing from the broader spirit and scope of the invention as set forth in the appended claims. The specification and drawings are, accordingly, to be regarded in an illustrative rather than a restrictive sense.

Contents4

Every citation, both ways

Citations
Document	Relation	Office	Cited during
US11627087B2	Cited by	United States of America	Search report
US2013067160A1	Cited by	United States of America	Pre-grant
US2008298261A1	Cited by	United States of America	Pre-grant
US12506694B2	Cited by	United States of America	Applicant
US11431647B2	Cited by	United States of America	Applicant
US12224941B2	Cited by	United States of America	Applicant
KR20220164458A	Cited by	Republic of Korea	Search report
US8806168B2	Cited by	United States of America	Search report
US7925793B2	Cited by	United States of America	Search report
US10680957B2	Cited by	United States of America	Search report
US11936568B2	Cited by	United States of America	Applicant
US11201828B2	Cited by	United States of America	Applicant
US11005775B2	Cited by	United States of America	Applicant
US11005776B2	Cited by	United States of America	Applicant
KR20150137017A	Cited by	Republic of Korea	Search report
US11765099B2	Cited by	United States of America	Applicant
US2015350089A1	Cited by	United States of America	Search report
US10630602B1	Cited by	United States of America	Search report
US2004039867A1	Cites	United States of America	Search report
US2005146950A1	Cites	United States of America	Search report
US4839866A	Cites	United States of America	Search report
US5564698A	Cites	United States of America	Applicant
US5597161A	Cites	United States of America	Applicant
US5695420A	Cites	United States of America	Applicant
US5707308A	Cites	United States of America	Applicant
US5718648A	Cites	United States of America	Applicant
US5733213A	Cites	United States of America	Applicant
US6272569B1	Cites	United States of America	Search report
USD394483S	Cites	United States of America	Applicant
USD396255S	Cites	United States of America	Applicant
USD401649S	Cites	United States of America	Applicant

1 member in 1 office

This recordMember, by publication datePriority claim

Priority claims2

Priority claims
Document	Office	Kind	Date
43400103	United States of America	A	2003-05-07
US20030434001	–	–	–

Members1

Family members, oldest first
Document	Office	Kind
US7269697B1This record	United States of America	B1	2007-09-11

40 transactions on the USPTO file

Allowed after 1 non-final rejection.

Non-final rejections: 1
Final rejections: 0
RCEs: 0
Appeals: 0

Over time

Point at a mark for the transaction

Transactions

Prosecution transactions, newest first
	Event	Code
2015-10-09	Expire PatentEXP.	EXP.
2009-01-29	Post Issue Communication - Certificate of CorrectionN423	N423
2007-09-11	Recordation of Patent Grant MailedPGM/	PGM/
2007-09-11	Patent Issue Date Used in PTA CalculationAllowedPTAC	PTAC
2007-08-22	Issue Notification MailedAllowedWPIR	WPIR
2007-07-31	Dispatch to FDCD1935	D1935
2007-07-27	Application Is Considered Ready for IssuePILS	PILS
2007-07-25	Issue Fee Payment VerifiedN084	N084
2007-07-25	Issue Fee Payment ReceivedIFEE	IFEE
2007-05-01	Mail Notice of AllowanceAllowedMN/=.	MN/=.
2007-05-01	Mail Examiner's AmendmentMEX.A	MEX.A
2007-04-29	Notice of Allowance Data Verification CompletedAllowedN/=.	N/=.
2007-04-29	Examiner's Amendment CommunicationEX.A	EX.A
2007-04-23	Date Forwarded to ExaminerFWDX	FWDX
2007-04-17	Response after Non-Final ActionA...	A...
2007-01-24	Mail Non-Final RejectionNon-final rejectionMCTNF	MCTNF
2007-01-22	Non-Final RejectionNon-final rejectionCTNF	CTNF
2007-01-09	Case Docketed to Examiner in GAUDOCK	DOCK
2006-11-02	Case Docketed to Examiner in GAUDOCK	DOCK
2006-07-28	IFW TSS Processing by Tech Center CompleteTSSCOMP	TSSCOMP
2006-01-05	Correspondence Address ChangeC.ADB	C.ADB
2004-05-20	Correspondence Address ChangeC.AD	C.AD
2003-11-24	New or Additional Drawing FiledC614	C614
2003-08-09	Case Docketed to Examiner in GAUDOCK	DOCK
2003-08-09	Case Docketed to Examiner in GAUDOCK	DOCK
2003-08-04	Case Docketed to Examiner in GAUDOCK	DOCK
2003-07-31	Transfer Inquiry to GAUTI1050	TI1050
2003-07-28	Transfer Inquiry to GAUTI1050	TI1050
2003-07-18	Application Is Now CompleteCOMP	COMP
2003-07-18	Application Is Now CompleteCOMP	COMP
2003-07-17	Application Return from OIPEWROIPE	WROIPE
2003-07-17	Application Return TO OIPEROIPE	ROIPE
2003-07-17	Application Return from OIPEWROIPE	WROIPE
2003-07-17	Application Return TO OIPEROIPE	ROIPE
2003-07-17	Application Dispatched from OIPEOIPE	OIPE
2003-07-17	Application Is Now CompleteCOMP	COMP
2003-06-03	Cleared by L&R (LARS)L128	L128
2003-05-23	IFW Scan & PACR Auto Security ReviewSCAN	SCAN
2003-05-19	IFW Scan & PACR Auto Security ReviewSCAN	SCAN
2003-05-07	Initial Exam Team nnIEXX	IEXX

13 legal events, as the office reported them to INPADOC

Over the term

Point at a mark for the event

Events

Legal events, newest first
	Event	Code
2016-05-06	AssignmentAS	AS
2016-05-06	AssignmentAS	AS
2015-11-03	Lapsed due to failure to pay maintenance feeLapsedFP	FP
2015-10-12	Information on status: patent discontinuationPATENT EXPIRED DUE TO NONPAYMENT OF MAINTENANCE FEES UNDER 37 CFR 1.362STCH	STCH
2015-10-09	Information on status: patent discontinuationPATENT EXPIRED DUE TO NONPAYMENT OF MAINTENANCE FEES UNDER 37 CFR 1.362STCH	STCH
2015-09-11	Lapse for failure to pay maintenance feesLapsedLAPS	LAPS
2015-04-24	Maintenance fee reminder mailedREMI	REMI
2011-02-10	Fee paymentFPAY	FPAY
2009-08-11	Certificate of correctionCC	CC
2006-02-22	AssignmentAS	AS
2006-02-22	AssignmentAS	AS
2003-10-29	AssignmentAS	AS
2003-09-26	AssignmentAS	AS