Wide field indexing for packet tracking

NOTICE OF COPYRIGHTS AND TRADE DRESS

A portion of the disclosure of this patent document contains material which is subject to copyright protection. This patent document may show and/or describe matter which is or may become trade dress of the owner. The copyright and trade dress owner has no objection to the facsimile reproduction by anyone of the patent disclosure as it appears in the Patent and Trademark Office patent files or records, but otherwise reserves all copyright and trade dress rights whatsoever.

BACKGROUND

1. Field

This disclosure relates to generating connections for testing a network or network device.

2. Description of the Related Art

In many types of communications networks, each message to be sent is divided into portions of fixed or variable length. Each portion may be referred to as a packet, a frame, a cell, a datagram, a data unit, or other unit of information, all of which are referred to herein as packets.

Each packet contains a portion of an original message, commonly called the payload of the packet. The payload of a packet may contain data, or may contain voice or video information. The payload of a packet may also contain network management and control information. In addition, each packet contains identification and routing information, commonly called a packet header. The packets are sent individually over the network through multiple switches or nodes. The packets are reassembled into the message at a final destination using the information contained in the packet headers, before the message is delivered to a target device or end user. At the receiving end, the reassembled message is passed to the end user in a format compatible with the user's equipment.

Communications networks that transmit messages as packets are called packet switched networks. Packet switched networks commonly contain a mesh of transmission paths which intersect at hubs or nodes. At least some of the nodes may include a switching device or router that receives packets arriving at the node and retransmits the packets along appropriate outgoing paths. Packet switched networks are governed by a layered structure of industry-standard protocols.

Layer 1 protocols define the physical (electrical, optical, or wireless) interface between nodes of the network. Layer 1 protocols include various Ethernet physical configurations, the Synchronous Optical Network (SONET) and other optical connection protocols, and various wireless protocols such as Wi-Fi.

Layer 2 protocols govern how data is logically transferred between nodes of the network. Layer 2 protocols include the Ethernet, Asynchronous Transfer Mode (ATM), Frame Relay, and Point to Point Protocol (PPP).

Layer 3 protocols govern how packets are routed from a source to a destination along paths connecting multiple nodes of the network. The dominant layer 3 protocols are the well-known Internet Protocol version 4 (IPv4) and version 6 (IPv6). A packet switched network may need to route IP packets using a mixture of the Ethernet, ATM, FR, and/or PPP layer 2 protocols. At least some of the nodes of the network may include a router that extracts a destination address from a network layer header contained within each packet. The router then used the destination address to determine the route or path along which the packet should be retransmitted. A typical packet may pass through a plurality of routers, each of which repeats the actions of extracting the destination address and determining the route or path along which the packet should be retransmitted.

In order to test a packet switched network or a device included in a packet switched communications network, test traffic comprising a large number of packets may be generated, transmitted into the network at one or more ports, and received at different ports. In this context, the term “port” refers to a communications connection between the network and the equipment used to test the network. The term “port unit” refers to a module within the network test equipment that connects to the network at a port. The received test traffic may be analyzed to measure the performance of the network. Each port unit connected to the network may be a source of test traffic, a destination for test traffic, or both a source of and a destination for test traffic. Each port unit may emulate a plurality of logical source or destination addresses. The number of port units and the communications paths that connect the port units to the network are typically fixed for the duration of a test session. The internal structure of the network may change during a test session, for example due to failure of a communications path or hardware device.

For the purpose of collecting test data, the test traffic for each traffic item may be organized into packet groups, where a “packet group” is any plurality of packets for which network traffic statistics are accumulated. The packets in a given packet group may be distinguished by a packet group identifier (PGID) contained in each packet. The PGID may be, for example, a dedicated identifier field or combination of two or more fields within each packet.

For the purpose of reporting network traffic data, the test traffic for each traffic item may be organized into flows, where a “flow” is any plurality of packets for which network traffic statistics are reported. Each flow may consist of a single packet group or a small plurality of packet groups. Each packet group may typically belong to a single flow.

Within this description, the term “logic circuit” means a collection of hardware, which may be augmented by firmware and/or software, which performs a described function or set of functions. The term “logic circuit” encompasses combinatorial logic and sequential logic such as, for example, state machines. All or portions of a “logic circuit” may be implemented by a micro-controller or other processor. Logic circuits may typically be designed using a hardware description language (HDL) that defines the logic circuits primarily in functional terms. The HDL design may be verified using an HDL simulation tool. The verified HDL design may then be converted into a gate netlist or other physical description of the logic circuits in a process commonly termed “synthesis”. The synthesis may be performed automatically using a synthesis tool. The gate netlist or other physical description may be converted into process instructions and masks for fabricating the engine within an application specific integrated circuit (ASIC).

A gate netlist or other physical description of logic circuits may be further converted into configuration data for implementing the logic circuits in a field programmable gate array (FPGA), a programmable logic device (PLD), or a programmable logic arrays (PLA), or other programmable semiconductor device, all of which will be referred to herein as “programmable circuit devices”. Configuration data for programming a programmable circuit device may be stored in a memory or a machine readable storage medium and used to configure a programmable circuit device upon power-up of a test system. In this patent, the term “machine readable storage medium” means a non-volatile medium for storing digital data. Examples of machine readable storage media include optical discs such as CD-ROM, CD-RW, and DVD discs; magnetic medium such as hard and flexible magnetic discs and magnetic tape; and nonvolatile semiconductor devices such as read-only and flash memories. The term “machine readable storage medium” is not intended to encompass transitory media such as signals and waveforms that may convey digital data.

Within this description, a hardware “unit” also means a collection of hardware, which may be augmented by firmware and/or software, which may be on a larger scale or have a more focused function than a “logic circuit”. The terms “logic circuit” and “unit” do not imply any physical separation or demarcation. All or portions of one or more logic circuits and/or units may be collocated on a common card, such as a network card or within a common programmable device, ASIC, or other circuit device.

DESCRIPTION OF THE DRAWINGS

<figref idrefs="DRAWINGS">FIG. 1</figref> is a block diagram of a network environment.

<figref idrefs="DRAWINGS">FIG. 2</figref> is a block diagram of a port unit.

<figref idrefs="DRAWINGS">FIG. 3</figref> is a graphical representation of accessing a flow statistics memory.

<figref idrefs="DRAWINGS">FIG. 4</figref> is a graphical representation of accessing a flow statistics memory.

<figref idrefs="DRAWINGS">FIG. 5</figref> is a flow chart of a process for receiving packets.

Throughout this description, elements appearing in figures are assigned three-digit reference designators, where the most significant digit is the figure number where the element is introduced and the two least significant digits are specific to the element. An element that is not described in conjunction with a figure may be presumed to have the same characteristics and function as a previously-described element having the same reference designator.

In block diagrams, arrow-terminated lines may indicate data paths rather than signals. Each data path may be multiple bits in width. For example, each data path may consist of 4, 8, 16, 64, 256, or more parallel connections.

DETAILED DESCRIPTION

Description of Apparatus

<figref idrefs="DRAWINGS">FIG. 1</figref> shows a block diagram of a network testing environment. The network testing environment may include a network traffic analyzer <b>100</b>, a network traffic simulator <b>104</b>, and a network <b>190</b> including one or more network devices <b>192</b>. The network traffic simulator <b>104</b> may generate test traffic that is received by the network traffic analyzer <b>100</b> via the network <b>190</b> and/or network devices <b>192</b> under test. The network traffic analyzer <b>100</b> and the network traffic simulator <b>104</b> may be separate physical units, as shown, or may be combined in a single unit the both generates and receives test traffic.

The network traffic analyzer <b>100</b> may be a network testing device, performance analyzer, conformance validation system, network analyzer, or network management system. The network traffic analyzer <b>100</b> may be a portion of the network <b>190</b> or a device within the network <b>190</b> performing self-testing. The network traffic analyzer <b>100</b> may include one or more network cards <b>112</b> enclosed within a chassis <b>102</b>. The chassis <b>102</b> may be a fixed or portable chassis, cabinet, or enclosure suitable to contain the network test equipment. The network traffic analyzer <b>100</b> may be an integrated unit, as shown in <figref idrefs="DRAWINGS">FIG. 1</figref>. Alternatively, the network traffic analyzer <b>100</b> may comprise a number of separate units cooperative to provide traffic generation and/or analysis.

The network traffic simulator <b>104</b> may be a network testing device, performance analyzer, conformance validation system, network analyzer, or network management system. The network traffic simulator <b>104</b> may be a portion of the network <b>190</b> or a device within the network <b>190</b> performing self-testing. The network traffic simulator <b>104</b> may include one or more network cards <b>116</b> enclosed within a chassis <b>106</b>. The chassis <b>106</b> may be a fixed or portable chassis, cabinet, or enclosure suitable to contain the network test equipment. The network traffic simulator <b>104</b> may be an integrated unit, as shown in <figref idrefs="DRAWINGS">FIG. 1</figref>. Alternatively, the network traffic simulator <b>104</b> may comprise a number of separate units cooperative to provide traffic generation and/or analysis. The network cards <b>112</b>/<b>116</b> may be permanently installed in the network traffic analyzer <b>100</b> and network traffic simulator <b>104</b> or may be removable.

The network cards <b>112</b>/<b>116</b> may include one or more field programmable gate arrays (FPGAs), application specific integrated circuits (ASICs), programmable logic devices (PLDs), programmable logic arrays (PLAs), processors, and other kinds of programmable circuit devices. In addition, the network cards <b>112</b>/<b>116</b> may include software and/or firmware. The term network card encompasses line cards, test cards, analysis cards, network line cards, load modules, interface cards, network interface cards, data interface cards, packet engine cards, service cards, smart cards, switch cards, relay access cards, and the like. The term network card also encompasses modules, units, and assemblies that may include multiple printed circuit boards. Each network card <b>112</b>/<b>116</b> may contain one or more port unit <b>110</b>/<b>114</b>. Each port unit <b>110</b>/<b>114</b> may connect to the network <b>190</b> through one or more ports. Each port unit <b>110</b>/<b>114</b> may be connected to the network <b>190</b> through a communication medium <b>195</b>, which may be a wire, an optical fiber, a wireless link, or other communication medium. Each network card <b>112</b>/<b>116</b> may support a single communications protocol, may support a number of related protocols, or may support a number of unrelated protocols.

The network devices <b>192</b> may be any devices capable of communicating over the network <b>190</b>. The network devices <b>192</b> may be computing devices such as workstations, personal computers, servers, portable computers, personal digital assistants (PDAs), computing tablets, cellular/mobile telephones, e-mail appliances, and the like; peripheral devices such as printers, scanners, facsimile machines and the like; network capable storage devices including disk drives such as network attached storage (NAS) and storage area network (SAN) devices; networking devices such as routers, relays, hubs, switches, bridges, server load balancers (SLBs), and multiplexers. In addition, the network devices <b>192</b> may include appliances, alarm systems, and any other device or system capable of communicating over a network.

The network <b>190</b> may be a Local Area Network (LAN), a Wide Area Network (WAN), a Storage Area Network (SAN), wired, wireless, or a combination of these, and may include or be the Internet. Communications on the network <b>190</b> may take various forms, including frames, cells, datagrams, packets or other units of information, all of which are referred to herein as packets. The network traffic analyzer <b>100</b> and the network devices <b>192</b> may communicate simultaneously with one another, and there may be plural logical communications paths between the network traffic analyzer <b>100</b> and a given network device <b>192</b>. The network itself may be comprised of numerous nodes providing numerous physical and logical paths for data to travel.

Referring now to <figref idrefs="DRAWINGS">FIG. 2</figref>, an exemplary port unit <b>210</b> may include a port central processing unit (CPU) <b>220</b>, a traffic receiver <b>240</b> coupled to a traffic statistics memory <b>255</b>, and a network interface unit <b>230</b> which couples the port unit <b>210</b> to a network <b>290</b>. The port unit <b>210</b> may be all or part of a network card for use in a traffic analyzer, such as the network cards <b>112</b> in the network traffic analyzer <b>100</b>. A port unit may also contain a traffic generator, not shown in <figref idrefs="DRAWINGS">FIG. 2</figref>.

The port CPU <b>220</b> may include one or more processors, a memory coupled to the processors, and various specialized units, circuits, software and interfaces for providing the functionality and features described here. The processes, functionality and features may be embodied in whole or in part in software which operates on the processor and may be in the form of firmware, an application program, an applet (e.g., a Java applet), a browser plug-in, a COM object, a dynamic linked library (DLL), a script, one or more subroutines, or an operating system component or service. The hardware and software and their functions may be distributed such that some functions are performed by the processor and others by other devices.

The port CPU <b>220</b> may communicate with a test administrator <b>205</b>. The test administrator <b>205</b> may be a computing device contained within, or external to, the network traffic analyzer <b>100</b>. The test administrator <b>205</b> may provide the port CPU <b>220</b> with instructions and data required for the port unit to participate in testing the network <b>290</b>. The instructions and data received from the test administrator <b>205</b> may include, for example, definitions of traffic statistics that may be accumulated and reported by the port unit <b>210</b>.

The network interface unit <b>230</b> may receive electrical, optical, or wireless signals from the network <b>290</b> over the link <b>295</b> and may convert the received signals into incoming test traffic <b>235</b> in a format usable to the traffic receiver <b>240</b>.

The traffic receiver <b>240</b> may receive the incoming test traffic <b>235</b> from the network interface unit <b>230</b>. The traffic receiver <b>240</b> may include logic circuits to determine if each received packet is a member of a specific flow, and to accumulate traffic statistics for each flow in accordance with test instructions <b>222</b> provided by the port CPU <b>220</b>.

Accumulated traffic statistics <b>255</b> may be stored in the statistics memory <b>250</b>. The statistics memory <b>250</b> may store n records such as the record <b>260</b>, where n is a positive integer. The number of records n may be a large binary number such as 65,536 (2¹⁶) or 262,144 (2¹⁸). The number of records n is not limited to a binary number. Each of the n records may contain the traffic statistics for a corresponding flow. Each of the n records may contain traffic statistics including quantitative information such as a number of packets received and a number of packets received out-of-order, temporal information such as maximum and minimum latency times, and other information. The records stored in the statistics memory <b>250</b> may be logically organized as a table having c columns and r rows of records, where c and r are positive integers such that cr=n.

The traffic receiver <b>240</b> may also include logic circuits to capture and store selected packets in accordance with capture criteria included in the test instructions <b>222</b>. The traffic receiver <b>240</b> may provide traffic statistics <b>242</b> and/or captured packets <b>244</b> to the port CPU <b>220</b>, in accordance with the test instructions <b>222</b>, for additional analysis during, or subsequent to, the test session.

The port unit <b>210</b> may accumulate traffic statistics for a plurality of flows. For example, each flow may be identified by a packet group identification number (PGID) embedded within a payload portion of each received packet, as described in U.S. Pat. No. 6,717,917, entitled “METHOD OF DETERMINING REAL-TIME DATA LATENCY AND APPARATUS THEREFOR”. However, in some circumstances, the incoming test traffic <b>235</b> may not contain PGIDs within each packet. For example, a traffic analyzer may be used to analyze actual network traffic rather than test traffic generated by a traffic simulator, or a traffic analyzer may be used to analyze test traffic generated by a traffic simulator that does not have the capability of embedding PGIDs in each packet. In situations where received packets do not contain embedded PGIDs, packet flows may be identified by data extracted from other fields in the received packets.

<figref idrefs="DRAWINGS">FIG. 3</figref> shows a graphical representation of determining a flow identifier for a received packet and accessing the corresponding traffic statistics in a statistics memory. The statistics memory <b>350</b> may store n=2²records organized as a single column of records. The statistics memory <b>350</b> may be the statistics memory <b>250</b> of <figref idrefs="DRAWINGS">FIG. 2</figref> with c=1. Each of the 2^wrecords may be accessed using a corresponding w-bit address pointer.

A received packet <b>305</b> may have a header portion divided into a plurality of fields including some or all of source and destination media access (MAC) addresses, source and destination internet protocol (IP) addresses, source and destination transmission control protocol (TCP) port numbers, a sequence number, a quality of service (QOS) field, and one or more checksums. The received packet <b>305</b> may also include a payload portion. When the received packet <b>305</b> does not contain a PGID embedded in the payload portion, data from one or more fields may be extracted and combined to generate a flow identifier that associates the received packet <b>305</b> with a particular flow and with a corresponding record in the statistics memory <b>350</b>. U.S. Pat. No. 7,643,431, entitled “DISTRIBUTED PACKET GROUP IDENTIFICATION FOR NETWORK TESTING”, describes developing a packet group identifier by combining multiple fields extracted from a received packet.

In the example of <figref idrefs="DRAWINGS">FIG. 3</figref>, two fields <b>310</b>, <b>315</b> may be extracted from the received packet. The extracted fields may typically be header fields such as MAC or IP addresses, TCP port numbers, QOS, or other fields. More than two fields may be extracted and combined to form a flow identifier. Masks <b>320</b>, <b>325</b> may be applied to the extracted fields <b>310</b>, <b>315</b>, respectively. For example, the shaded portions of the masks <b>320</b>, <b>325</b> may represent bits set to “0” and the unshaded portions may represent bits set to “1”. The extracted fields <b>310</b>, <b>315</b> and the respective masks <b>320</b>, <b>325</b> may be combined by an AND function to produce masked data fields <b>330</b>, <b>335</b>. In the masked data fields <b>330</b>, <b>335</b>, the masked bits (shown shaded) may set to zero, and the unmasked bits (shown with single hatching) may be equal to the corresponding bits of the extracted fields <b>310</b>, <b>315</b>.

The masked data fields <b>330</b>, <b>335</b> may then be combined to form a flow identifier <b>340</b>. The unmasked bits (shown with single hatching) may be shifted such that all unmasked bits are contiguous within the flow identifier <b>340</b>. The resulting flow identifier <b>340</b> may contain m bits, where m is the sum of the bit lengths of the extracted fields <b>310</b> and <b>315</b>, including k contiguous unmasked bits. The k contiguous unmasked bits may be located anywhere within the flow identifier <b>340</b>. In the case where k≦w, the k unmasked bits may simply be used as the address pointer to access a corresponding row of the statistics memory <b>350</b>. However, if k&gt;w, the k unmasked bits cannot be used directly as the address pointer to access the statistics memory <b>350</b>, since some possible values of the k unmasked bits will point to rows that do not exist within the statistics memory.

When k&gt;w, the k unmasked bits of the flow identifier <b>340</b> may be mapped to a w-bit address pointer value using a hash function. A hash function is any algorithm or mathematical function that converts a larger amount of data into a smaller amount of data, typically a single integer. The value returned by a hash function is called hash value. For example, an order-w CRC (cyclic redundancy check) polynomial may be used to generate a w bit hash value <b>345</b> for use as the address pointer to access the statistics memory <b>350</b>. A CRC polynomial has the desirable property that the mapping from the flow identifier <b>340</b> to the hash value <b>345</b> is unique when k≦w. This may not necessarily be true of other hash functions.

When k&gt;w, multiple possible values of the k unmasked bits of the flow identifier may map to the same value of the w-bit hash value <b>345</b>. Thus there is a possibility that traffic statistics for two or more flows may be erroneously combined in a single record within the statistics memory <b>350</b>. To avoid accumulation of erroneous flow statistics, each record in the statistics memory <b>350</b> may include a field containing the flow identifier of the corresponding flow.

When the packet <b>305</b> is received by the traffic receiver <b>240</b>, dedicated logic circuits or a combination of software and hardware may generate the flow identifier <b>340</b>. A hash function <b>342</b> may then be applied to map the flow identifier <b>340</b> to the hash value <b>345</b>. The hash value <b>345</b> may then be used to retrieve a record <b>360</b> from the statistics memory <b>350</b>. The retrieved record <b>360</b> may include a field <b>362</b> containing a flow identifier value corresponding to the traffic statistics stored in the retrieved record. A comparator <b>370</b> may then compare the generated flow identifier <b>340</b> and the retrieved flow identifier field <b>362</b>. If the two values are equal, the packet <b>305</b> belongs to the flow corresponding to the traffic statistics stored in the retrieved record <b>360</b>. In this case, the retrieved record <b>360</b> may be updated to reflect the receipt of the packet <b>305</b>. The updated record may be stored back in the statistics memory <b>350</b>.

If the comparator <b>370</b> indicates that the two flow identifier values are not equal, the packet <b>305</b> does not belong to the flow corresponding to the traffic statistics stored in the retrieved record, but rather belongs to a different flow that maps to the same hash value. This situation may be referred to as a “collision”, since a second flow has “collided” with the flow whose traffic statistics were already stored in the statistics memory <b>350</b>. In this case, the traffic statistics contained in the retrieved record <b>360</b> may not be updated, and the packet <b>305</b> may be discarded. A packet receiver may maintain a count <b>380</b> indicating the number of collisions that have occurred. This count may be incremented each time a collision occurs. Although not shown in <figref idrefs="DRAWINGS">FIG. 3</figref>, a count of collisions may be maintained for each record. In this case, a field (not shown) within the retrieved record <b>360</b> may be incremented when a collision occurs, and the updated record may then be stored back in the statistics memory <b>350</b>.

A traffic receiver that uses a hash function to map a flow identifier to an address pointer for accessing a traffic statistic memory may not be able to accumulate traffic statistics for all flows due to collisions. Typically, the hash function <b>342</b> randomly maps a flow identifier <b>340</b> to a hash value <b>345</b>. In this case, as the number of different received flow identifiers approaches the number of available records in the traffic statistics memory, about 37% of the received flow identifiers will be discarded due to collisions. Thus the traffic receiver may be able to accumulate traffic statistics on only about 63% of the actual flows.

<figref idrefs="DRAWINGS">FIG. 4</figref> shows a graphical representation of determining a flow identifier for a received packet and accessing the corresponding traffic statistics in a statistics memory. The statistics memory <b>450</b> may store n=2^wrecords organized as 2 columns by 2^w/=2^w-1rows. The statistics memory <b>450</b> may be the statistics memory <b>250</b> of <figref idrefs="DRAWINGS">FIG. 2</figref> with c=2. Each row of the 2^w-1records may be accessed using a corresponding w−1 bit address pointer.

As described in conjunction with <figref idrefs="DRAWINGS">FIG. 3</figref>, fields <b>410</b>, <b>415</b> may be extracted from a received packet <b>405</b>. Masks <b>420</b>, <b>425</b> may be applied to the extracted fields <b>410</b>, <b>415</b>, and the resultant masked fields <b>430</b>, <b>435</b> may be combined to form a flow identifier <b>440</b>. A hash function, such as a w−1 order CRC polynomial, may be applied to the flow identifier <b>440</b> to produce a w−1 bit hash value <b>445</b>.

When the packet <b>405</b> is received by a traffic receiver such as the traffic receiver <b>240</b>, dedicated logic circuits or a combination of software and hardware may generate the flow identifier <b>440</b> and the hash value <b>445</b>. The hash value <b>445</b> may then be used to retrieve a row containing records <b>462</b> and <b>464</b> from the statistics memory <b>450</b>. Since two records are retrieved simultaneously, the width in bits of the data path from the statistics memory must be twice as wide as the data path required to read a single-column statistics memory (as shown in <figref idrefs="DRAWINGS">FIG. 3</figref>). Each retrieved record <b>462</b>, <b>464</b> may include respective fields <b>463</b>, <b>465</b> containing a flow identifier value corresponding to the traffic statistics respectively stored in the retrieved records.

Respective comparators <b>470</b>, <b>475</b> may then compare the generated flow identifier <b>440</b> and the retrieved flow identifier fields <b>463</b>, <b>465</b>. If the generated flow identifier <b>440</b> matches the retrieved flow identifier <b>463</b>, the packet <b>405</b> belongs to the flow corresponding to the traffic statistics stored in the retrieved record <b>462</b>. In this case, the retrieved record <b>462</b> may be updated to reflect the receipt of the packet <b>405</b>. If the generated flow identifier <b>440</b> matches retrieved flow identifier <b>465</b>, the packet <b>405</b> belongs to the flow corresponding to the traffic statistics stored in the retrieved record <b>464</b>. In this case, the retrieved record <b>464</b> may be updated to reflect the receipt of the packet <b>405</b>. The updated versions of records <b>462</b>, <b>464</b> may be stored back in the statistics memory <b>450</b>.

If the comparators <b>470</b>, <b>475</b> indicate that the generated flow identifier <b>440</b> is not equal to either of the retrieved flow identifiers <b>463</b>, <b>465</b>, the packet <b>405</b> does not belong to the flow corresponding to the traffic statistics stored in either retrieved record, but may belong to a different flow that maps to the same hash value. This situation may be referred to as a “collision”, since a third flow has “collided” with the two flows whose traffic statistics were already stored in the statistics memory <b>450</b>. In this case, a counter <b>480</b>, indicating a total number of collisions that have occurred, may be incremented.

A traffic receiver that uses a hash function to map a flow identifier to an address pointer for accessing a traffic statistic memory organized as multiple columns of records may not be able to accumulate traffics statistics for all flows due to collisions. However, the number of collisions may be greatly reduced compared to a traffic statistics memory organized as a single column. In the two-column example of <figref idrefs="DRAWINGS">FIG. 4</figref>, as the number of different received flow identifiers approaches the number of available records in the traffic statistics memory, only about 27% of the received flow identifiers will be discarded due to collisions. Thus the traffic receiver may be able to accumulate traffic statistics on about 73% of the actual flows. The number of collisions may be further reduced by increasing the number of columns in the statistics memory, at a cost of a proportional increase in the width of the data path from the statistics memory.

Description of Processes

Referring now to <figref idrefs="DRAWINGS">FIG. 5</figref>, a process <b>500</b> for accumulating traffic statistics may begin at <b>505</b> when instructions to start accumulating traffic statistics are received at a port unit such as the port unit <b>210</b>. The process <b>500</b> may be cyclic in nature, and the actions from <b>515</b> to <b>585</b> may be performed repeatedly to accumulate traffics statistics for a large number of received packets. Multiple instances of the process <b>500</b> may be performed concurrently at a plurality of port units to accumulate traffic statistics for a network or network device under test.

For ease of discussion, the process <b>500</b> is shown in <figref idrefs="DRAWINGS">FIG. 5</figref> as a flow chart with sequential actions. However all or portions of the process <b>500</b> may be performed in parallel by logic circuits within a traffic receiver. In particular, the actions from <b>535</b> to <b>585</b> may be performed nearly simultaneously during a single hardware memory cycle. A traffic receiver may perform the actions from <b>515</b> to <b>585</b>, at least in part, as a pipeline such that multiple instances of the process occur simultaneously.

When an instruction to start accumulating traffic statistics is received at <b>505</b>, a statistics memory, such as the statistics memory <b>250</b> of <figref idrefs="DRAWINGS">FIG. 2</figref>, may be cleared or emptied to indicate that no traffic statistics are currently stored. Alternatively, the statistics memory may be cleared at the conclusion of a previous test session or at some other time in anticipation that a start instruction will be received at <b>505</b>. A statistics memory may be considered to be cleared or empty when a traffic receiver coupled to the statistics memory can determine whether or not a record contains currently valid statistics data. For example, a “number of received packets” field within each record may be set to zero to empty a statistics memory.

A packet may be received at <b>515</b>. At <b>520</b>, one or more predetermined fields may be extracted from the received packet <b>518</b>. The extracted fields may contain information useful to characterize and report flow statistics information. The extracted fields may include, for example, one or more of source and destination MAC addresses, source and destination IP addresses, source and destination TCP port numbers, a protocol identifier, a quality of service value, flags, and other fields.

At <b>520</b>, masks may be applied to the fields extracted at <b>520</b> and the resultant unmasked bits may be compressed to form a flow identifier <b>528</b>, as previously described in conjunction with <figref idrefs="DRAWINGS">FIG. 3</figref>. At <b>530</b>, a hash function may be applied to the flow identifier <b>528</b>, and the resulting hash value may be used to retrieve a plurality of records from the statistics memory at <b>535</b>. As previously described, the statistics memory <b>250</b> may be configured as a table having c columns and 2^w/c rows, where 2^wis the total capacity of the statistics memory in records. At <b>535</b>, an entire row of the table may be retrieved, such that the number of records retrieved is equal to the number of columns.

At <b>540</b>, the c records retrieved at <b>535</b> may be processed to determine if any one of the retrieved records should be updated based on the received packet <b>518</b>. At <b>545</b>, a determination may be made whether or not the flow identifier <b>528</b> matches the content of a “flow identifier” field within the first record. When a match is found, the first record may be updated at <b>550</b>. Updating the first record at <b>550</b> may include incrementing a “number of received packets” field within the first record to reflect receipt of the received packet <b>518</b>. Other fields within the first record may be updated based on the packet received at <b>515</b>. For example, a latency time of the received packet <b>518</b> may be written into a “minimum latency” field or a “maximum latency” field within the first record if appropriate. The updated first record may be stored back into the statistics memory at <b>585</b>, and the process <b>500</b> may return to <b>515</b> to await the receipt of another packet.

The actions at <b>540</b> may be performed for each of the c records retrieved at <b>535</b>. As shown in <figref idrefs="DRAWINGS">FIG. 5</figref>, the actions at <b>540</b> may be performed in parallel for each retrieved record, for example using dedicated hardware. Although not shown, the actions at <b>540</b> may be performed sequentially for each of the n retrieved records.

When the flow identifier <b>528</b> does not match a flow identifier field within any of the c retrieved records, the c records retrieved at <b>535</b> may be processed at <b>560</b> to determine if one of the retrieved records should be initialized based on the received packet <b>518</b>. A determination may be made at <b>565</b> whether or not the first retrieved record is empty. For example, a determination may be made if a “number of received packets” field within the first record is set to zero. When a determination is made that the first record is empty, the first record may be initialized based on the received packet <b>518</b> at <b>570</b>. Initializing the first record at <b>570</b> may include setting the value of a number of received packets field within the first record to one. Initializing the first record at <b>570</b> may also include copying the flow identifier <b>528</b> to a “flow identifier” field within the first record. Other fields within the first record may be updated based on the received packet <b>518</b>. For example, a latency time of the received packet <b>518</b> may be written into both a “minimum latency” field and a “maximum latency” field within the first record. The initialized first record may be stored back into the statistics memory at <b>585</b>, and the process <b>500</b> may return to <b>515</b> to await the receipt of another packet.

The actions at <b>560</b> may be performed for each of the c records retrieved at <b>535</b>. As shown in <figref idrefs="DRAWINGS">FIG. 5</figref>, the actions at <b>560</b> may be performed in parallel for all retrieved record, for example using dedicated hardware. Although not shown, the actions at <b>560</b> may be performed sequentially for each of the retrieved records. When two or more retrieved records are empty, priority logic (not shown) may be used to determine which of the empty records is initialized.

When the flow identifier <b>528</b> does not match the content of a flow identifier field within any of the retrieved records, and none of the retrieved records is empty, a collision has occurred. In this event, a collision counter may be incremented at <b>580</b> and the process <b>500</b> may return to <b>515</b> to await the receipt of another packet.

Closing Comments

Throughout this description, the embodiments and examples shown should be considered as exemplars, rather than limitations on the apparatus and procedures disclosed or claimed. Although many of the examples presented herein involve specific combinations of method acts or system elements, it should be understood that those acts and those elements may be combined in other ways to accomplish the same objectives. With regard to flowcharts, additional and fewer steps may be taken, and the steps as shown may be combined or further refined to achieve the methods described herein. Acts, elements and features discussed only in connection with one embodiment are not intended to be excluded from a similar role in other embodiments.

As used herein, “plurality” means two or more. As used herein, a “set” of items may include one or more of such items. As used herein, whether in the written description or the claims, the terms “comprising”, “including”, “carrying”, “having”, “containing”, “involving”, and the like are to be understood to be open-ended, i.e., to mean including but not limited to. Only the transitional phrases “consisting of” and “consisting essentially of”, respectively, are closed or semi-closed transitional phrases with respect to claims. Use of ordinal terms such as “first”, “second”, “third”, etc., in the claims to modify a claim element does not by itself connote any priority, precedence, or order of one claim element over another or the temporal order in which acts of a method are performed, but are used merely as labels to distinguish one claim element having a certain name from another element having a same name (but for use of the ordinal term) to distinguish the claim elements. As used herein, “and/or” means that the listed items are alternatives, but the alternatives also include any combination of the listed items.