Abstract:
A network buffer memory is divided into pools of locations including a plurality of tinygram contiguous sections and a plurality of jumbogram contiguous sections. The tinygram contiguous sections available for storage of packets are listed in a list of tinygram pointers. The jumbogram contiguous sections available for storage of packets are also listed in a list of jumbogram pointers. A threshold for distinguishing the packets as tinygrams and jumbograms is programmed. As packets are received, they are measured against the threshold. Responsive to detection of an end of packet condition prior to reaching the threshold, storing the packet in a tinygram contiguous section. Otherwise, the packet is stored in a jumbogram contiguous section. Availability of sections is determined by query to the FIFO lists of pointers.

Description:
This application is a continuation of Ser. No. 08/171,050, filed Dec. 21, 1993, now abandoned. 
    
    
     BACKGROUND OF THE INVENTION 
     1. Technical Field 
     The invention relates to distributed data processing systems and more particularly to management of a buffer for a network adaptor receiving and/or transmitting data packets for a node of a distributed data processing system. 
     2. Description of the Related Art 
     The passing of data between a communications link and a node comprising a computer or terminal is commonly supported by buffering the data. The object of buffering is to avoid rigid synchronization in operation of the communications link and the internal operations of the node. A buffer may be implemented using memory or data storage registers, a disk drive, a delay line, or any one of a number of technologies. Use of a buffer allows for differences in the rate of flow of information or time of occurrence of events when transmitting information between the communications link and node. 
     The organization of data for transmission over a communications link has a number of consequences relating to efficient use of the communications link, management of transmission and receipt of the data, efficient use of memory upon receipt of the data, among other things. For example, a common way of handling organization of data is the use of packets, in which control and data elements are switched and transmitted as a composite whole. The use of packets simplifies a number of issues concerning routing. 
     Packets, or other types of data frames, may be variable in length. This has an advantage over fixed length frames in terms of efficient utilization of a communications link throughput capacity. The allocation of space in a buffer for the creation, transmission, copying and manipulation of variable length frames can, however, consume a considerable portion of the processing power of a node if the task is implemented in sequential software. The computation and construction of direct memory access (DMA) control blocks is a major part of the problem. 
     One way to reduce the computational load imposed on a receiving node by the use of variable length frames is to receive the frames into buffer locations of fixed length, which allow for any possible size of frame, including headers which may be added to the frame after the bulk data copy. A problem with this approach is that requires use of a great deal of memory to implement because of internal fragmentation of the buffer. 
     Buffer location chaining has also been used as an approach to the problem. However, doing so requires construction of descriptions of the chains and the need to allocate memory bandwidth for the reading of the chains. 
     Also known is the use of a first-in, first-out (FIFO) receive buffer where only so much location as is needed for a packet/frame is used. This approach suffers from the complication of a need for clearing memory. When a memory location is released, all of the frames preceding the released frame in time must also be released before the particular location may be reused. 
     SUMMARY OF THE INVENTION 
     It is an object of the present invention to provide a system and method for the management of a buffer for a network adaptor receiving data packets for a node in a distributed data processing system. 
     It is another object of the present invention to provide for a system and method for segregating data frames into two classes for managing buffer space. 
     The above and other objects of the invention are provided for by a network adaptor for implementing method of managing communication data. A network adaptor buffer memory is divided into pools including a plurality of tinygram contiguous sections and a plurality of jumbogram contiguous sections. The tinygram contiguous sections available for storage of packets are indicated by a list of pointers to the available tinygram contiguous sections. The jumbogram contiguous sections available for storage of packets are also indicated by a list of pointers to the available jumbogram contiguous sections. A threshold for distinguishing the packets as tinygrams and jumbograms is selected. Then, as packets are received, they are measured against the threshold. Responsive to detection of an end of packet condition prior to reaching the threshold, the packet is stored in a tinygram contiguous section. Otherwise, the packet is stored in a jumbogram contiguous section. The availability of sections is determined by query to the FIFO lists of pointers. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The novel features believed characteristic of the invention are set forth in the appended claims. The invention itself however, as well as a preferred mode of use, further objects and advantages thereof, will best be understood by reference to the following detailed description of an illustrative embodiment when read in conjunction with the accompanying drawings, wherein: 
     FIG. 1 is a block diagram of a token ring network interconnecting a plurality of nodes; 
     FIG. 2 is a block diagram of data flow within a network adaptor for use on the network of FIG. 1; 
     FIG. 3 is a graphical depiction of the frequency of occurrence length differentiated packets; 
     FIG. 4 is a logical flow chart of a packet reception process for implementing the invention; 
     FIG. 5 is a logical flow chart of a process for setting up transmission of packets in accordance with the invention; and 
     FIG. 6 is a logical flow chart of a process for transmitting packets in accordance with the invention. 
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     FIG. 1 depicts a block diagram of an illustrative local area network  8  for supporting transmittal of data including file server and multimedia data between a plurality of nodes. Local area network  8  is depicted in a token ring geometry, however other geometries are possible. Server  12  communicates with computers  12 A- 12 C over a communications channel  10 . Server  12  is a conventional computer such as an IBM Personal System/2 or AS/400 system programmed to practice this invention, and includes a central processing unit  60 , a memory  64 , and a network adapter  62  for buffering outgoing and incoming transmissions of data frames or packets. Server  12  includes a hard drive unit  56  storing a plurality of multimedia and other data objects pending a request for access by one or more users. Such a request results in staging of the data object from hard drive unit  56  to computer memory  64  or network adaptor  62  over system bus  58 . A number of objects exist within memory  64 . An operating system and local area network server  66  are represented as one object. Objects stored on hard drive unit  64  and memory  64  to be transmitted must be organized into frames or packets and handed off to network adaptor  62 . Similarly, data being received over ring  10  may be staged from network adaptor  62  for transfer to hard drive unit  56  or memory  64 . CPU  60  can program a direct memory access (DMA) controller  61  to handle transfer of data over system bus  58  to and from network adaptor  62 . 
     Users access data files stored on sever  12  through computers  12 A- 12 C. Computer  12 B is a typical example. A computer  12 B operates as a personal workstation communicating with computer  12 . Schematically the personal workstation  12 B is substantially similar to server  12 , and includes a network adapter  78 , a display adapter  84 , a hard drive unit  90 , a central processing unit (CPU)  82  and an addressable memory  88 . Components of personal workstation  12 B transfer data internally over a system bus  83 . CPU  82  directly controls input peripherals  80  which may include a keyboard and a mouse. Display adapter  84  drives a display device  86 , upon which data from a file is visually presented. Memory  88  includes a command structure  94  for use in establishing a communications session on network  8 . DMA controller  87  fulfills the same function in computer  12 B as DMA controller  61  does in server  12 . 
     FIG. 2 is a block diagram of network adaptor  62 . Data frames or packets are received on a First-In, First-Out input buffer  31 . Concurrently, packets are provided as an input to control logic block  33 , which tracks the size of a packet being received from framing information for the packet. A threshold  43  accessible by control logic block  33  in memory  35  is used for size categorization, i.e. if the packet meets or is bigger than the threshold the packet is deemed a jumbogram, otherwise it is a tinygram. The size category of an incoming packet is known when end of packet information is received or when the threshold is met, whichever comes first. At this point an appropriately sized section of memory  35  may be selected for the packet. Memory  35  is usually an array of Random Access Memory on the adaptor card, but may be part of System Memory  64 . 
     Memory  35  includes a reserved area of data blocks  37  for receiving incoming packets. Data blocks  37  come in two sizes, one sized to take any packet smaller than the threshold and a second sized to take the largest expected size of packet. The threshold  43  is programmable and may be changed. Tinygram pointer list  41  and jumbogram pointer list  42  include pointers to all of the smaller and larger size of blocks available for receiving data, respectively. Pointer lists  41  and  42  are preferably implemented as First-In, First-Out lists. Alternatively, a chained link list of pointers may be used in a stack implementation. A FIFO is easier to debug and implement while a stack has greater versatility. Upon retrieving a pointer and completion of reception of the packet, control logic block  33  addresses memory device  35  using the pointer (and associated addresses) and enables FIFO input buffer  31  to write the packet to the locations associated with the pointer into memory device  35 . The pointer is then placed into receive queue  39 . The CPU for the node may then be interrupted or some other technique employed to advise an application that data has been received. After the data packet is released from memory device  35  the pointer is returned to the appropriate list, either tinygram pointer list  41  or jumbogram pointer list  42 . 
     Although not required, transmission of data packets may also utilize the division of memory device  35  into jumbograms and tinygrams. In such a case a system CPU may obtain a pointer from lists  41  or  42  and supply the pointer to transmit control  43  through a transmit queue  40 . After obtaining the pointer transmit control  43  asserts the pointer (and/or associated addresses) as an address to memory device  35  to write the contents of the associated locations into an output buffer  45  for transmission. The pointer is then returned to the appropriate list  41  or  42 . Release of the pointer may be delayed until acknowledgement of successful reception is received from the destination node. 
     FIG. 3 is a graphical depiction of the frequency distribution by size of packets in a network, e.g. for multimedia data. The length of frame increases along the X-axis and the probability of occurrence increases along the Y-axis. Short packets, generally corresponding to requests, acknowledgements and control information are the predominant type of traffic. Longer packets correspond to multimedia data which peak in frequency at a much longer frame length. The distribution curve shows two peaks with an intervening trough in distribution. The tendency of multimedia data to exhibit such behavior makes division of a memory structure into two predetermined sizes of frames advantageous. If for some reason traffic tended to exhibit three pronounced frequency peaks, then utilizing three categories of presized contiguous sections of memory  35  might be advantageous. 
     FIG. 4 is a high level logical flow chart of a process for receiving data packets on network adaptor  62 . Upon entry to the process on power up, the FIFO jumbogram list  42  and FIFO tinygram list are initialized at step  101 . Initialization includes allocation of contiguous sections of memory  35  to function as tinygrams and jumbograms. The lowest address of the contiguous section may be used as a pointer. A section of memory may be reserved for identifying tinygrams and jumbograms by beginning location and type. Next, at step  103 , a threshold is programmed for use in categorizing packets as either large or small. 
     At step  105 , an incoming packet is received into an input buffer. Receipt of the packet is monitored and at step  107  it is determined if the packet has ended before the threshold condition is met or not. If the threshold is met or exceeded, step  109  follows step  107 . At step  109 , the process attempts to obtain a pointer to a jumbogram in memory device  35  from FIFO jumbogram list  42 . At step  111  it is determined if a pointer was available. If none was, step  113  follows step  111  and the received frame is flushed. A failure acknowledgement may now be generated for return to the transmitting node on the network. The process is then exited. 
     If an end of frame condition was detected for a packet before reaching the threshold, the end of frame branch is taken from step  107  to step  115 . At step  115  the FIFO tinygram list is accessed for a pointer. Step  117  determines is a pointer was available. If none was available, step  119  may be executed to access the FIFO jumbogram list for a pointer. Whether step  119  is used or not depends upon whether the cost of using a grossly oversized location in memory for a packet is considered worth the cost. Step  121  provides for determining if step  119  failed to return a pointer. If no pointer is available, step  123  is executed to flush the frame. Step  123  may be executed following detection of a failure at step  117 . A failure acknowledgement may be sent back to the transmitting node. 
     It at any of steps  111 ,  117 , or  121  it was determined that a pointer was available, step  125  is executed to write the packet from input buffer  31  into memory device  35 . For jumbograms, the frame does not reside entirely in the input buffer. When a packet is determined to be a jumbogram, staging of the packet classes and data goes essentially straight to memory. Next, at step  117  the pointer is placed into a receive queue. At step  129  the process for which the packet is destined is notified of it availability. 
     The program fork following step  129  relates to logical division of processing between control block  33  and a system CPU and DMA controller. Control logic block  33  processing returns to step  105  following step  129 . Steps  131 ,  133  and  135  reflect node response to notification of a process of receipt of a packet. At step  131  the CPU receives the pointer previously stored in the receive queue. Direct memory access controller  61  is then programmed to handle transfer of the packet, typically to system memory. If buffer memory is implemented in system memory this step is omitted. This operation is reflected by step  133 . Once the DMA operation is complete, step  135  provides for returning the pointer to the appropriate FIFO jumbogram or tinygram list, indicating that the corresponding locations in memory are now available for reuse. 
     FIG. 5 is a high level logical flow chart of a process for preparing data packets for transmission. Step  141  provides for any required initialization of the transmission processor. Next, at step  143 , the process enters an enforced wait until data becomes available for network transmission. Once a frame is available, the frame is categorized as small or large at step  145 . If the frame is small, step  147  is executed to attempt to obtain a pointer to a tinygram location in memory device  37 . Otherwise, step  149  is executed to attempt to obtain a pointer to a jumbo location in memory device  37 . Following either step, step  151  is executed to determine if a pointer was in fact obtained. If not, step  153  is executed to interrupt the CPU to handle the error. Otherwise, step  155  is executed to perform a direct memory access operation to transfer the data from system memory to memory device  35 . Next, step  157  provides for placing the pointer into the transmit queue. The process is an endless loop and is executed until the system is powered down. 
     FIG. 6 is a high level logical flow chart of a process relating to transmission of tinygrams and jumbograms. The discussion is not intended as a full discussion of the operation of a transmission controller. The process is entered as step  161  where a pointer location is read from the transmit queue. If the pointer value is zero, as determined at step  163 , the controller loops back to step  161  to read another location in the queue. It a pointer was present, step  165  is executed to determine the buffer size type. This allows the process to determine the correct queue to which to return the pointer. At step  167  the pointer is returned to the appropriate pool list,  41  or  42  and deleted from the transmit queue. Step  167  may wait upon return of a receipt acknowledgement. 
     Transmit control block  43  and control block  33  are preferably implemented as logic gates for optimal speed. Compared to a software implemented FIFO input buffer, this implementation reduces memory bandwidth demands by obviating the need for an additional memory move. 
     The invention allows the large buffer memory of a network adaptor to be used in a manner other than first-in, first-out. Individual management of buffer locations allows for out of order processing of frames. This offers much simpler support of multiple queues. Compared with buffer location chaining, the software and memory bandwidth overheads required are considerably reduced. Compared with fixed buffering schemes the invention reduces internal memory fragmentation. Compared with FIFO buffering with out of sequence memory recovery external fragmentation is substantially reduced. 
     While the invention has been particularly shown and described with reference to a preferred embodiment, it will be understood by those skilled in the art that various changes in form and detail may be made therein without departing from the spirit and scope of the invention.