Abstract:
A method and apparatus for generating a unique packet identifier from receive packet header information accepts a series of packet words that make up a packet and selects a subset of a first packet word and a subset of a second packet word. The unique packet identifier is generated from a combination of the subsets selected from the first and second packet words for each packet received.

Description:
BACKGROUND 
     A current challenge for network equipment and network service suppliers is testing and evaluating products under realistic network volume and conditions. Packet processing requires a priori knowledge of a current state of a connection associated with the packet to be processed. When processing protocol exchange packets, therefore, the packet header field provides information that is used to retrieve state information from memory. During operation, the devices that are tested maintain and process information for millions of connections. Therefore, realistic header fields are large. A look up function that uses a large number of bits to perform the addressing is complex and time-consuming and can potentially be a limiting factor in packet processing. It is important, therefore, to perform the retrieval step as efficiently as possible. 
     Prior art approaches to the retrieval step include a hardware implementation using content addressable memory (herein “CAM”). The hardware implementation using CAM is fast, but can be very expensive for a large number of connections. Additionally, CAM consumes significant printed circuit board real estate, which is also costly. Another prior art approach is a software implementation using sort algorithms. The software implementation is optimized for the specific sort involved, but is relatively slow and can be a limiting factor in the rate of packets processed. A hybrid implementation is also known involving a number of CAMs to create a hardware assisted search, however hybrid systems are expensive to implement on a large scale. 
     There remains a need, therefore, for efficient process and apparatus to perform the look up function of state information based upon packet header information. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       An understanding of the present teachings can be gained from the following detailed description, taken in conjunction with the accompanying drawings of which like reference numerals in different drawings refer to the same or similar elements. 
         FIG. 1  illustrates connections between an embodiment of a tester according to the present teachings and a device under test. 
         FIG. 2  illustrates an embodiment of a tester that supports one of the ports shown in  FIG. 1  and benefits from the present teachings. 
         FIG. 3  is a block diagram of an embodiment according to the present teachings. 
         FIG. 4  is a block diagram of an alternative embodiment according to the present teachings. 
     
    
    
     DETAILED DESCRIPTION 
     In the following detailed description, for purposes of explanation and not limitation, example embodiments disclosing specific details are set forth in order to provide an understanding of embodiments according to the present teachings. However, it will be apparent to one having ordinary skill in the art and having benefit of the present disclosure that other embodiments according to the present teachings that depart from the specific details disclosed herein remain within the scope of the appended claims. Moreover, descriptions of well-known apparatus and methods may be omitted so as to not obscure the description of the example embodiments. Such methods and apparatus are clearly within the scope of the present teachings. 
     A specific embodiment of a tester according to the present teachings generates and measures “stateful” network traffic according to the DoD Standard Transmission Control Protocol as defined in Request For Comment 793 published September 1981 (herein “the TCP standard”) including retransmission of segments that are not acknowledged and timeouts. Measurements made in a system according to the present teachings, therefore, include measurements relating to the quality of a connection within context at layer 3/4 of the Open Systems Interconnect model. In a specific embodiment, the tester generates TCP segments without regard to payload content, receives TCP segments, processes them according to the TCP standard retransmitting segments as dictated by the standard. A TCP connection is bi-directional, consists of two endpoints, and establishes a vehicle for communication via the TCP standard. In a specific embodiment, hardware circuitry, specifically a field programmable gate array (“FPGA”) implements the TCP standard. To test and measure a greater number of connections to emulate a larger network, the tester is scaleable by simply adding state memory. The advantage of this scalability lies in the feature that an increase in the cost of the tester is relatively small relative to the overall system. 
     With specific reference to  FIG. 1  of the drawings, there is shown an illustration of connections between an embodiment of a tester  100  according to the present teachings and a device under test (herein “DUT 102”). In the example disclosed herein, the DUT  102  is a non-terminating TCP networking device that accepts TCP segments and forwards them. A specific embodiment of a tester according to the present teachings is able to measure the performance of the DUT as a networking device. Non-terminating DUTs include but are not limited to routers, switches, and edge aggregation devices. The tester  100  generates TCP traffic, receives the TCP traffic forwarded by the DUT, and measures the performance of the DUT in terms of whether it properly processes and forwards the TCP traffic it received according to the TCP standard. As one of ordinary skill in the art with benefit of the present teachings also appreciates that terminating devices may be tested as well. Examples of terminating devices include without limitation firewalls, servers, and web proxy devices. The present teachings are also applicable to other network standards in addition to the TCP standard. 
       FIG. 1  illustrates the tester  100  comprising multiple printed circuit boards (herein “PCB 104”). The tester  100  may use one or more of the PCBs  104  depending upon the size of the DUT  102  and the number of desired communication ports to be tested. In the specific embodiment illustrated, each printed circuit board  104  is able to accept four ports  106 . Each port  106  provides full duplex communication and may be configured to be either a client port, a server port, or a combination client/server port. A server port is one where most of the data packets flow from the tester and to the device under test. The port remains full-duplex because there is control information flowing in both directions, but a bulk of the data flows from the tester to the device under test. A client port is one where most of the data communication flows from the device under test and to the tester. A client/server port is one where substantially equivalent volume of data traffic flows in both directions. In a specific implementation, there is always at least one server port or client/server port and one client port or client/server port for each tester  100 , but the remaining two ports may be configured as client, server, or client/server as desired by a user. 
     With specific reference to  FIG. 2  of the drawings, there is shown a block diagram of an embodiment of tester logic that is used to support each port  106  of the client/server PCB  104  and obtains benefit from the present teachings. Packets in a received data stream  220  are received through the port  106  by a stream processor controller (herein “SPC 200”). The SPC  200  receives packets, identifies and filters certain packets from the received stream  220 . The SPC  200  extracts receive packet header fields  201  and forwards them to Packet Processor  202 . As it extracts the receive packet header fields  201 , the SPC  200  also determines a unique packet identifier  300  that identifies a connection to which the packet is associated and sends it along with the header field  201 . The SPC  200  indicates valid data in the receive packet header fields  201  to packet processor  202  with receive packet event signal  203 . The SPC  200  then forwards the received data stream  220  to other circuitry unrelated to the present teachings. 
     The packet processor  202  accesses state memory  212  with state address  213  and state data  214 . Rate generator  206  sends transmit packet requests  211  to the packet processor  202 . The packet processor  202  sends outgoing packet header information  209  to packet generator  207 . The packet generator  207  accesses templates stored in packet generator RAM  210  and uses the templates in conjunction with the outgoing packet header information  209  to generate a transmit packet for presentation as transmit data stream  221  to the port  106 . 
     Central processing unit (herein “CPU”)  204  is connected to all functional blocks  200 ,  202 ,  206 ,  207 ,  210 ,  212 . The actual connections are not shown for purposes of clarity. The interaction between the CPU  204  and the functional blocks to which it communicates is through an address bus  205 , a bi-directional data bus  208 , a read/write signal  210  providing indication from the CPU  204  as to which direction data flows on the data bus and an acknowledgement signal  215  permitting the functional blocks to acknowledge completion of a transfer of information. The CPU  204  configures each of the functional blocks in preparation for a test. The CPU  204  is also able to dynamically modify test parameters during a test. The dynamically modifiable test parameters permit the tester to more closely emulate realistic TCP traffic and application behavior. 
     With specific reference to  FIG. 3  of the drawings, there is shown an embodiment of logic according to the present teachings for determining a packet identifier  300  from each receive packet header field  201 . The packet identifier  300  is used for purposes of addressing an appropriate location in the state memory  212 . The present teachings are based on a principle that a test environment is different from normal operation of the device being tested in that there is some control over a range of possible packet identifiers. That being the case, the range of packet identifiers may be limited to a smaller predetermined range of values. Advantageously, the state memory  212  that supports the tester  100  may be smaller than might otherwise be necessary. 
     Using this principle to an advantage in the context of test, the present teachings propose to generate the packet identifier  300  from a subset of the receive packet header fields  201 . Additionally, the subset is configurable by a user over an entire range of possible values. 
       FIG. 3  of the drawings illustrates a 32-bit implementation according to the present teachings in which there are five instantiations of logic. Each instantiation includes a respective field selector  301 , a respective selector latch  302 , respective enable RAM  303 , and a respective CPU latch  304 . An output of a single counter  311  is provided to each instantiation. An incoming packet in the data stream  220  is received as multiple packet words  310  that arrive in a time serial fashion. In the specific embodiment shown in  FIG. 3  of the drawings, there are sixteen (16) 32-bit packet words  310  in each receive packet header  201 . 
     Each instantiation receives the same 32-bit packet word  310  at the same time, but processes each packet word  310  independently. Each instantiation outputs a 4-bit output. The collective outputs of all instantiations comprise the unique packet identifier  300 , which is 20-bits in the specific implementation shown in  FIG. 3 . 
     Structure and operation of a single instantiation during a test is now described for processing one packet, wherein a system clock is received by the selector latch  302 , the CPU latch  304 , the counter  311 , and the enable RAM  303 . The system clock transitions as each packet word  310  is received and valid. In the specific 32-bit implementation, CPU latch output  305  maintains a 3-bit value programmed into it prior to test. The value of the CPU latch output  305  selects one of eight (8), 4-bit fields in the packet word  310  for presentation at an output of the field selector  301 . 
     At a start of receipt for each packet, counter  311  is reset to zero via packet reset signal  312 . As each subsequent packet word  310  in the packet is received, a logic one is maintained at the count enable signal  313  causing a next transition of the system clock to increment the counter  311  by one. During test, a counter output  314  is presented at an output of programming selector  315  that addresses the enable RAM  303 . The enable RAM  303  is a  16  by 1-bit memory. The enable RAM  303  is programmed prior to test with only one of the  16  address locations storing a logic one. The address location that contains the logic one defines which one of the packet words  310  is used to generate the packet identifier  300  for each instantiation. 
     An enable RAM output  316  connects to a clock enable of the selector latch  302 . As the counter  311  increments and cycles through the addresses of the enable RAM  303  as each packet word  310  is received, all but one cycle outputs a logic zero. A logic zero inhibits the selector latch  302  from presenting an output of the selector  301  to a selector latch output  317 . Accordingly, on most cycles, the selector latch  302  does not propagate a value to the selector latch output  317 . 
     One of the address locations of the enable RAM  303 , however, stores a logic one. As the counter  311  increments through its cycle, the output of the enable RAM  303  is a logic one for one of the cycles. When the location storing the logic one is addressed, a logic one is presented to the clock enable of the selector latch  302 . While the clock enable is asserted on the selector latch  302 , the next transition of the system clock causes the 4-bit output of the field selector  301  to be propagated to a selector latch output  317 . The latched value at the selector latch output  317  remains because all remaining address locations store a logic zero, thereby disabling the clock enable of the selector latch  302  until all remaining packet words  310  of the current packet are processed. 
     After all of the packet words  310  are processed for one packet, each of the five instantiations has a latched 4-bit output  317 . As one of ordinary skill in the art appreciates, each instantiation most typically presents a different subset of different packet words  310  at the selector latch output  317 . A composite of the five 4-bit outputs  317  for each instantiation comprises a unique identifier  300  for the packet. The unique identifier  300  may then be used by the packet processor  202  to access the state memory  212 . 
     Structure and operation for programming a single instantiation prior to test is now described, wherein the CPU latch  304  and the programming selector  315  permit the CPU to programmatically select those packet words  310  and fields of the receive packet header field  201  that are to be used to generate the unique identifier  300 . Specifically, the CPU  204  performs a routine that stores a 3-bit code into the CPU latch  304 . CPU data  208  with the desired value is presented to the CPU latch  304 . The CPU read/write signal  210  is then asserted to propagate and hold the CPU data  208  at the output of the CPU latch  304 . Each instantiation is independent of the others in that each 3-bit code may be, but is not necessarily, different from all other instantiations. The CPU latch output  305  defines which field is selected for the packet word  310 . Once each CPU latch is programmed by the CPU  204 , the values are held constant by de-asserting the CPU read/write signal  210 . 
     The enable RAM  303  is also programmed by the CPU  204  prior to test by storing a logic one in one of  16  address locations and storing a logic zero in all remaining address locations. In a specific embodiment, the CPU  204  writes to the enable RAM  303  by asserting the CPU read/write signal  210  and incrementing through each one of the  16  address locations via CPU address bus  205 . The asserted CPU read/write signal  210  causes CPU selector  315  to present the CPU address  205  at its output instead of the output of the counter  311  and also causes data to be written to the enable RAM  303 . 
     After programming the enable RAM  303 , only one of the  16  address locations stores a logic one. The location of the logic one defines the packet word  310  that is to be used as part of the packet identifier  300 . During test, the CPU read/write signal  210  remains de-asserted and the CPU signals  208 ,  205  are not relevant to operation of each instantiation during test. It is also to be noted that a de-asserted read/write signal  210  causes CPU selector  315  to pass through the counter output  314  while also inhibiting alteration of stored values in the CPU latch  304  and the enable RAM  303 . 
     With specific reference to  FIG. 4  of the drawings, there is shown an alternative embodiment of an apparatus according to the present teachings that includes 20 instantiations, each instantiation presenting a 1-bit selector latch output  317  to contribute to the collective packet identifier  300 . In the embodiment of  FIG. 4 , each instantiation processes a total of 32, 16-bit packet words  310  for each packet. The CPU latch  304  is programmed with a 4-bit value to direct which one of  16  possible one bit fields is presented at the output of the selector  301  and propagated to the selector latch output  317 . In the embodiment relevant to  FIG. 4  of the drawings, the enable RAM  303  has 32 1-bit locations that are cycled through using a 5-bit counter  311  to select which packet word  310  is used for each instantiation. As one of ordinary skill in the art appreciates, the embodiment of  FIG. 4  is programmed in similar fashion to the embodiment of  FIG. 3  except for differences in the numbers of bits programmed and processed. 
     Embodiments of the teachings are described herein by way of example with reference to the accompanying drawings describing a method and apparatus for generating a unique packet identifier from receive packet header information in a tester that makes measurements on network traffic. Other variations, adaptations, and embodiments of the present teachings will occur to those of ordinary skill in the art given benefit of the present teachings.