Patent Publication Number: US-2005135251-A1

Title: Method and system for reducing congestion in computer networks

Description:
BACKGROUND  
      1. Field of the Invention  
      The present invention relates to computer networks, and more particularly to reducing congestion in computer networks.  
      2. Background of the Invention  
      Computer networks are used in every facet of today&#39;s business and personal life. Whether it involves sending electronic mail or accessing remote data, a computer network is used to accomplish various tasks.  
      In a typical computer network, data packets enter a data path serially, one after another, and then data packets are processed individually. The number of data of data packets received in a data queue is based on the size of the queue, which can be programmed by a user. Hence, in some instances a large number of data packets may be received in a data packet queue. If in-order data packet processing is required, then the packet at the beginning (“head packet”) must be processed first and packets following the head packet must wait for processing. This results in packet congestion. If the head packet never gets processed, then the data path stalls and hence must be re-set. This results in inefficiency and can be very expensive for businesses.  
      Computer networks today cannot afford to have congestion and stall problems. Conventional data packet techniques do not solve the foregoing congestion and stalling problems. Conventional techniques require separate memory buffers to store data packets. This increases cost and makes the process inefficient since additional operations are needed to write/read data packets from the memory buffers.  
      Therefore, what is needed is a process and system in a network for discarding data packets that have been received for a certain period.  
     SUMMARY OF THE INVENTION  
      In one aspect of the present invention, a system for discarding expired network data packets is provided. The system includes a counter for assigning a time stamp value for data packets received in a data packet queue; and a comparator for comparing an extracted time stamp value with a counter value generated by the counter. The time stamp value may be based on the upper two bits of the counter value. The counter value may include a base increment value and a value generated by a first programmable register.  
      The system also includes a second register for storing the extracted time stamp value.  
      The comparator checks for data packet expiration if the counter value has changed or if the second register is loaded with a new data packet at the head of the data packet queue.  
      In another aspect of the present invention, a method for discarding expired network data packets is provided. The method includes assigning a time stamp value to data packets that are received in a data packet queue, wherein the time stamp value is based on a counter value; extracting the time stamp value after the counter value changes or a new data packet is received at the head of the data packet queue; comparing the extracted time stamp value with the counter value; and discarding a data packet if the time stamp value has expired.  
      In one aspect of the present invention, separate memory buffers or timestamp headers are not required to determine when a packet has expired.  
      In another aspect of the present invention, the time stamp and expiration value may be programmed to meet the granularity needs of different networks.  
      In yet another aspect of the present invention, serial data packet reception is streamlined and data packet congestion is avoided.  
      This brief summary has been provided so that the nature of the invention may be understood quickly. A more complete understanding of the invention can be obtained by reference to the following detailed description of the preferred embodiments thereof concerning the attached drawings. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
      The foregoing features and other features of the present invention will now be described with reference to the drawings of a preferred embodiment. In the drawings, the same components have the same reference numerals. The illustrated embodiment is intended to illustrate, but not to limit the invention. The drawings include the following Figures:  
       FIG. 1A  is a block diagram showing plural computer systems operationally coupled to a network;  
       FIG. 1B  is a block diagram of the computing systems shown in  FIG. 1A   
       FIG. 1C  is a block diagram showing a network using the INFINIBAND standard, according to one aspect of the present invention;  
       FIG. 1D  is a block diagram of a switch using the system, according to one aspect of the present invention;  
       FIG. 2  is a block diagram of a system according to one aspect of the present invention; and  
       FIG. 3  is a flow diagram of executable process steps for reducing network data packet congestion, according to one aspect of the present invention. 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS  
       FIG. 1A  is a block diagram showing plural computing systems  101 - 103  operationally coupled to a network  104 . In one aspect of the present invention, network  104  may operate using multiple protocols, for example, TCP/IP, fiber channel or any other protocol.  
       FIG. 1B  is a block diagram showing the internal functional architecture of a computing system (e.g.  101 ). As shown in  FIG. 1B , computer  101  includes a central processing unit (“CPU”)  101 A for executing computer-executable process steps and interfaces with a computer bus  101 F. CPU  101 A may be a Pentium™ class processor sold and marketed by Intel Corp.™ or any other processor.  
      Among other components, computing system  101  includes a network interface card (“NIC”)  101 B, a rotating disk  101 D, random access memory (“RAM”)  101 E and read only memory (“ROM”)  101 C.  
      NIC  101 B provides system  101  with connectivity to network  104 . NIC  101 B may have its own processor or dedicated chip to conduct specific operations.  
      Disk  101 D stores operating system program files, application program files, and other files. Some of these files are stored on disk  101 D using an installation program. For example, CPU  101 A executes computer-executable process steps of an installation program so that CPU  101 A can properly execute the application program.  
      A random access main memory (“RAM”)  101 E also interfaces to computer bus  101 F to provide CPU  101 A with access to memory storage. When executing stored computer-executable process steps from disk  101 D (or other storage media such as a floppy disk  16  or via network connection  104 ), CPU  101 A stores and executes the process steps out of RAM  101 E.  
      Read only memory (“ROM”)  101 C is provided to store invariant instruction sequences such as start-up instruction sequences or basic input/output operating system (BIOS) sequences for operation of keyboards etc. (not shown).  
       FIG. 1C  shows a block diagram of plural computing devices operationally coupled using the Infiniband architecture as described in the Infiniband standard specification, published by the Infiniband Trade Association.  
       FIG. 1C  shows system  117 A with a fabric  117 . Fabric  117  includes plural switches  106 ,  107 ,  111  and  112 . Fabric  117  also includes a router  108  that is coupled to a wide area network  109  and local area network  110 . It is noteworthy that network  104  may include both WAN  109  and LAN  110 .  
      Switch  106  is operationally coupled to a RAID storage system  105  and system  102 , while system  101  may be operationally coupled to switch  107 .  
      Switch  112  may be coupled to a small computer system interface (“SCSI”) SCSI port  113  that is coupled to SCSI based devices. Switch  112  may also be coupled to Ethernet  114 , fiber channel device (s)  115  and other device(s)  116 .  
       FIG. 1D  shows a block diagram of switch  112  that includes a processor  120  which is operationally coupled to plural ports  122 ,  123 ,  124  and  125  via a control port  121  and cross-bar  119 . In one aspect of the present invention, processor  120  may be a reduced instruction set computer (RISC) type microprocessor. Ports  122 - 125  may be similar to ports  113 - 116 , respectively.  
      Switch  112  may be coupled to a processor  129  that is coupled to Ethernet  127  and serial port  128 . In one aspect of the present invention, processor  129  may be similar to CPU  101 A in system  101 .  
       FIG. 2  is a block diagram of a system  200  that reduces data packet congestion in a network data path  208 . Network data path  208  shows data packets received from a device or the network into a switch ( 112 ).  
      Network data path  208  shows data packets  200  and  201  moving in direction  208 . Data packet  200  includes a start of frame header  200 A and end of frame  200 C. Similarly, data packet  201  includes a start of frame header  201 A and end of frame  201 C.  
      When a data packet (e.g.)  200  is received, a counter  203  tags a time stamp  200 B to the data packet. Typically, the time stamp code  200 B is embedded in the first word of data packet  200 . Before data packet  200  is processed or while waiting at the head of a packet queue  208 , time stamp code  200 B value is extracted by register  206 . As discussed below, comparator  205  compares the extracted value  206 A with counter  203  value ( 203 A).  
      Counter  203  value  203 A may be based on a base increment value and programmable variable time stamp (VTS) register  204  value  204 A or any other command from RISC processor  120 . This allows VTS register  204  to program the time stamp value  202  using counter  203 .  
      Comparator  205  checks if the timer for data packets has expired whenever counter  203  value changes or register  206  is re-loaded (i.e. if new data packets arrive at the head of queue  208 ). Comparator  205  compares value  206 A with counter value  203 A to determine if the timer for a packet has expired. Based on the comparison, Comparator  205  generates a pass signal  205 B if the timer has not expired, or fail signal  205 A, if the timer expired.  
      An example of how the expiration value is determined is provided below: 
      VTS Register  204  value=VTS     Base Increment for VTS register  204 : M milli-seconds     Expiration value: 2M* 2{circumflex over ( )}VTS+X %−Y %      

      In one aspect of the present invention, the following values may be used: 
      VTS=8, M=2, X=1% and Y=51%, and expiration value is between 250 ms to 500 ms.    

      The foregoing illustration is an example to show how the components of  FIG. 2  will determine if a packet has expired. The example is only an illustration and is not intended to limit the adaptive aspects of the present invention.  
       FIG. 3  shows a flow diagram of executable process steps that allows efficient processing of data packets.  
      Turning in detail to  FIG. 3 , in step S 300  data packets are received from the network. Data packets flow serially in data path  208 .  
      In step S 301 , a time stamp is assigned for a data packet. In one aspect of the present invention, the time stamp is embedded in the start of frame header of the data packet (e.g.  201 B). Time stamp  202  is based on VTS register value  204  and may be 2 bits.  
      In step S 302 , the time stamp value is extracted. The time stamp value is extracted and sent to register  206 .  
      In step S 303 , the time stamp value  206 A is compared to counter value  203 A. Counter value  203 A may be based on VTS register  204  output  204 A.  
      In step S 304 , the process determines if the timer for a data packet has expired. This is determined by the comparison in step S 303 .  
      In step S 305 B the packet is discarded if the timer has expired, or kept in the queue, in step S 305 A, if the timer has not expired.  
      In one aspect of the present invention, separate memory, buffers or timestamp headers are not required to determine when a packet has expired.  
      In another aspect of the present invention, the time stamp and expiration value may be programmed to meet the needs of different networks.  
      In yet another aspect of the present invention, serial data packet reception is streamlined and data packet congestion is avoided.  
      Although the present invention has been described with reference to specific embodiments, these embodiments are illustrative only and not limiting. Many other applications and embodiments of the present invention will be apparent in light of this disclosure and the following claims.