Patent Publication Number: US-6222850-B1

Title: Dynamic transmit tuning for ethernet device drivers

Description:
Continuation of prior application Ser. No. 08/670,310 filed Jun. 27, 1996 now U.S. Pat. No. 5,864,558. 
    
    
     BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     This invention relates to communication networks. More specifically, the invention relates to Local Area Networks (LANs) of the Carrier Sense Multiple Access with Collision Detection (CSMA/CD) type which provide both half-duplex and full-duplex communication channels. 
     2. Description of the Prior Art 
     Ethernet is a commonly used name for a network access protocol of the CSMA/CD type. The CSMA/CD protocol is defined in ANSI/IEEE Standard 802.3, published by the Institute of Electrical and Electronic Engineers, Inc., 3445 East 45th Street, New York, N.Y. 10017, and referred to as the IEEE 802.3 standard. Under the CSMA/CD rules for access to a network, any node or station wishing to transmit must first “listen” to make sure that the channel is clear before beginning to transmit. All nodes on the network have equal priority of access and after a required inter-packet delay (IPG) of 9.6 μs (microseconds) may begin transmitting as soon as the channel is clear. However, if the first node that has started transmitting detects a “collision” with a transmission from another node, the first node continues transmitting for a short time to make sure that all nodes wishing to transmit will detect the collision. Every other node detecting collision also continues to transmit for a short time. Then each node that has detected a collision terminates transmission of the packet or frame. The nodes involved in the collision enter a collision avoidance mode. In the collision avoidance mode, the nodes wait for the required IPG of 9.6 μs and then use different delay times, referred to as backoff times, before trying transmission of the same packet again. When the number of nodes is small, e.g. two nodes, the IEEE standard 802.3 exhibits an undesirable effect, referred to as the “capture effect” in which one of the nodes may effectively capture and transmit a succession of data packets which essentially “freezes out” the other node from transmitting messages. 
     The nature of ethernet is changing in that there are now multiple methods of connecting to a network. Ethernet can be connected in half-duplex, half-duplex switched or full-duplex switched domains. Each of these environments has characteristics that define the highest performing method of transmitting data on the network. When the network hardware is programmed to operate half-duplex, which is the standard node for ethernet, chaining transmit packets together can result in poor network performance due to the speeds at which some signal drivers can drive the network, particularly when the network is in a high traffic collision domain. In a lightly loaded half-duplex network, however, there is less need to incur artificially extended inter-packet delay between packets or frames, since the level of competition for the network is greatly reduced. On the other hand, in full-duplex, it is not necessary to incur an artificially extended inter-packet delay since the station is no longer competing for access to the network. Therefore, in full-duplex it is more beneficial not to incur the overhead of artificially extended inter-packet delay between packets, since there is no competition for the network. 
     Accordingly, there is a need to provide an ethernet driver transmit technique for both half and full-duplex that maximizes performance of the network in terms of latency and throughput, regardless of whether half or full-duplex is being used on the network. 
     The prior art related to the problem addressed by the present invention is, as follows: 
     European patent application 063,262,082 entitled “Backoff Time Evaluation Method for ethernet,” published Apr. 1, 1995, discloses an ethernet capture effect avoidance scheme which uses a special capture avoidance binary exponential backoff (CABEB) algorithm. 
     A publication entitled “Solving Capture in Switched Two-Node Ethernets By Changing Only One Node” by W. Hayes, et al. published in the proceedings, Twentieth Conference on Local Computer Networks, Minneapolis, Minn., USA, Oct. 16-19, 1995, pages 387-95, discloses a method for solving capture effect in switched multi-mode ethernet systems by allowing a node to keep a local copy of attempts counter of other nodes and to use this information to trigger switching its medium access protocol policy between two extremes, one aggressively persistent and the other completely passive. 
     U.S. Pat. No. 5,432,775 entitled “Auto Negotiation System for a Communication Network,” issued Jul. 11, 1995, filed Dec. 3, 1993, discloses a system for detection of enhanced capability of stations on a communications network. A specified pattern of late test pulses are detected and transmitted to provide for the indication of enhanced capability. The system is particularly useful for determining whether a particular station is in full-duplex or half-duplex mode without affecting overall network performance. 
     U.S. Pat. No. 5,305,317 issued Apr. 19, 1994, discloses an adaptive circuit for a local area network whereby the adaptive circuit can operate in a token ring protocol or in an ethernet protocol. A protocol handler is operable to communicate with internal buses in either a token ring or ethernet protocol. 
     None of the prior art addresses the problem of dynamically tuning ethernet device drivers for improved network performance, i.e., latency and throughput, regardless of whether the network hardware is in a half or full-duplex mode, and without the use of special algorithms or other mechanisms to alter the inter-packet delay gap for collision avoidance. 
     SUMMARY OF THE INVENTION 
     An object of the invention is an improved local area network (LAN) of the ethernet type operating in either a half or full-duplex mode with improved latency and throughput. 
     Another object is a LAN of the ethernet type employing transmit chaining in half or full duplex mode without involving a “capture” problem or mode testing. 
     Another object is a tunable device driver for a LAN of the ethernet type which provides improved performance for either a half-duplex or full-duplex environment. 
     Another object is a method to dynamically throttle back a device driver in a communications network to reduce the number of collisions when the driver detects the network is heavily utilized in a half duplex mode, yet provide the maximum throughput when the network is lightly loaded in a half duplex mode or in a full duplex mode. 
     Another object is a method of increasing throughput on a LAN of the ethernet type when operated in a lightly loaded half-duplex or a full-duplex mode. 
     Another object is a method to avoid a capture effect in a LAN of the ethernet type operating in a half-duplex mode using the IEEE 802.3 standard for collision backoff procedure. 
     These and other objects, features and advantages are achieved in a LAN of the ethernet type employing CSMA/CD protocol for channel access by a plurality of network nodes. Each node transmits data packets to the LAN in accordance with the IEEE 802.3 standard. Each node includes an adapter coupled at one side to the network in either a half or full-duplex mode. The other side of the adapter is bound to a device driver which is dynamically tuned for reduced latency and increased network throughput, regardless of the transmitting mode of the node and the capture effect of an ethernet LAN. Each device driver operates in a transmit chaining mode when the network is in a lightly loaded half-duplex, or full-duplex mode. The driver includes means for monitoring data packet collisions on a channel. A “collision rate” or the percentage of data packets which were transmitted on the channel with collisions in a pre-selected time interval is calculated by the device driver. A “collision threshold” is assigned or calculated by the device driver. Data packets transmitted by each device driver are chained to increase network throughput when the “collision rate” is below the “collision threshold”. Transmit chaining of data packets is disabled for the device driver when the “collision threshold” is exceeded on the channel. 
     In summary, the present invention satisfies the need for a communication network of the ethernet type for improved latency and throughput by dynamically tuning device drivers according to a “collision rate” and “collision threshold”. The device driver is tuned by calculating or assigning a “collision rate” and determining whether the “collision rate” exceeds the assigned or calculated “collision threshold.” When the “collision rate” does not exceed the “collision threshold” the LAN hardware or adapter performs transmit chaining which improves latency and increases network throughput, regardless of whether the hardware is in a half or full-duplex mode and without testing to determine the mode or duplex status of the channel. When the “collision rate” is exceeded, the device driver artificially extends the IPG by transmitting data packets one at a time which tends to avoid the capture effect problem of ethernet LANS. 
    
    
     DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a representation of a communications network of the ethernet type having a plurality of stations using a half or full-duplex mode for communications with other stations. 
     FIG. 2 is a representation of a station or node in the network of FIG. 1 which incorporates the principles of the present invention. 
     FIG. 3 is a representation of a counter included in the station of FIG.  2  and used in the method of FIG.  4 C. 
     FIG. 4A is a flow diagram which implements the method of the present invention in transmitting data frames from a station to the network. 
     FIG. 4B is a flow diagram which describes the operation of transmit complete for the station of FIG.  2 . 
     FIG. 4C is a flow diagram for calculating a “collision rate” for the method of the present invention. 
    
    
     DESCRIPTION OF A PREFERRED EMBODIMENT 
     In FIG. 1, a communications network  10  of the ethernet type includes a plurality of stations or nodes  12 ′ . . .  12   n  coupled to a hub  14  in a half-duplex (HDX) or full-duplex (FDX) mode with the FDX mode being implemented in the hub. The network operates in the CSMA/CD mode as described in IEEE standard 802.3 with collision avoidance. The text “Ethernet—Building a Communications Infrastructure” by H. Hegering et al, published by Addison-Wesley Publishing Company, Wokingham, England, 1993 (ISBN: 0-201-62405-2), pages 12, 33 provides additional details on an ethernet and the full text is incorporated by reference into the present application. 
     In FIG. 2, a representative station or node  12  in the network includes an input/output (I/O) bus  16  coupled to a conventional memory  18 , central processing unit  20 , display/input device  22  and a disk storage device  23  which accepts a computer usable medium e.g. a floppy disk or mini embodying stored computer program instructions for entry into or down loading from the memory  18 . Also connected to the I/O bus  16  is one side of an adapter  24 , typically a Medium Access Unit (MAU), described in the text by H. Hegering et al supra and including a collision detection function  26 . The other side of the adapter is connected to the ethernet  10 . 
     The memory  18  includes a series of stored program instructions including a conventional operating system  28 , e.g OS/2, Windows 95, UNIX, etc; a device driver  30  and an adapter buffer  32 . The device driver provides instructions for reformatting or interpreting software command for transfer to and from peripheral devices and the CPU  20 . The device driver manages a device driver buffer  34  for storing data frames sent by the operating system  28  to the adapter  24  when the station is in a collision avoidance mode. The adapter buffer stores frames sent by the device driver for transmission to the network  10  when the station is not in a collision avoidance mode. 
     The device driver monitors a transmit complete counter  33  and a transit collision counter  36  to calculate a collision rate occurring on the network  10  in a specified time period, as will be described hereinafter. The device driver employs a collision rate calculating algorithm  38  stored in the memory  18  for such purpose. Lastly, a collision threshold  40  is stored in the memory  18  for use in the exercise of the calculating algorithm  38 . The threshold  40  may be arbitrarily selected by a user based on network collision experience or dynamically calculated based on the type of network, i.e. full or half-duplex; number of stations or nodes; lightly or heavily loaded traffic on the network, and other network parameters having a bearing on the probability of collisions occurring on the network. The collision threshold  40  would be reset in the memory, as required after the dynamic calculation of the threshold. 
     A brief overview of the invention will be provided before describing the flow diagrams of FIGS. 4A, B and C., as follows: 
     In FIGS. 1 and 2, each device driver  30  in the network monitors the number of frames that are transmitted using the transit collision counter and collision detector  26 , with collisions indicating network competition among the transmitting stations or nodes  12 . The more collisions detected by a node, the more competition, and therefore, the device driver should transmit frames one at a time in accordance with the IEEE 802.3 backoff procedure. Conversely, the fewer collisions detected, the less competition, and therefore, the device should chain transmit packets together regardless of half or full-duplex mode. 
     Once per second the device driver calculates the percentage of frames that were transmitted with collisions over a defined time interval, typically four seconds. Transmit chaining is enabled as long as this number is below a certain percentage or collision threshold, typically in the range of ten percent, but this percentage may be dynamically changed according to the network status. Once the collision threshold is exceeded, transmit chaining is disabled which occurs only for a half-duplex mode when in a high network traffic/high collision rate status. Full-duplex mode is not subject to the collision threshold since each node transmits and receives messages directly from other nodes without competition from the circuit. Accordingly, there is no need for the channel to be tested to determine the transmit mode or duplex status in which the channel is operating. 
     To implement the calculation of a collision rate, a “transmit complete” counter  33  is incremented every time a frame completes transmission from the node. Every time a frame completes transmission with collisions indicated, a “transmit complete with collision” counter  36  is incremented. These counters are maintained in such a way as to indicate the current state of the network over the past four seconds, so as not to be affected by bursts of activity. A decision is made periodically by the device driver taking the ratio of the two counters. If more than the threshold value of collisions to the total frames is reached, new frames will be enqueued on the pending queue in buffer  34  of the device driver. Otherwise, new frames will be enqueued on the “ready” queue in the buffer  32  of the adapter. The decision for enqueuing the packets at the device driver or the adapter is based upon the following equation:          if          transmit                 collision                 counter   ×   100               transmit                 complete                 counter                 then                 enqueued                 pending     =   TRUE                 else                 enqueued                 pending     =   FALSE               ≥     threshold                 value                     
     In FIG. 3, each counter covers only the past “4” seconds. The counts maintained are only the number of occurrences within that time period. In implementations, there are four subcounters  42 ′,  42 ″,  42 ′″ and  42 ″″ maintained, the counter value being the sum of the occurrences for the four subcounters. Thus, in the first calculation, the counter value is the sum of the counts for the time periods  1 ,  2 ,  3  and  4  which occurs at time period  4 . In the next calculation, which occurs in time period  1 , the counter value is the sum of the counts for time periods  2 ,  3 ,  4  and  5 . In the next calculation which occurs in time period  2 , the counter value is the average of the counts for time periods  3 ,  4 ,  5  and  6 , and so forth. After each count calculation, the oldest count is cleared from the subcounter to begin counting new frames. Each counter, therefore, is the sum of the four subcounters over a four second period. 
     In FIG. 4A, a process will be described for transmitting a frame from the node to the network. The process is entered in a step  401  when the operating system  28  presents a frame to the device driver  30  for transmission to the network using the CSMA/CD procedure of IEEE 802.3. In step  403  the driver performs a collision avoidance mode test and a “yes” condition enqueues the frame in the device driver buffer  34  and the process ends. Additional frames are enqueued in the device driver buffer in a step  405  until the collision avoidance mode test indicates a “no” condition. When a “no” condition results from the test of step  403 , all pending frames are moved to the adapter  24  the new frame is enqueued in the adapter buffer  32  in step  407  whereupon the process ends. 
     In FIG. 4B, a process will be described for the device driver during the interrupt time on the network after a transmit complete has been indicated for a transmitted frame. The process is entered in a step  409  when the device driver notifies the operating system of a transmit complete. In a step  411 , the device driver updates the transmit complete counter  34 . Next, in a step  413  the device driver updates the transmit collision counter  36 . In a step  415 , the device driver checks if it is in collision avoid mode. A “no” condition ends the process. A “yes” condition will cause the device driver to interrogate the operating system for frames pending in a step  417 . A “no” condition ends the process. A “yes” condition enqueues the next pending frame in the adapter buffer in a step  419 , after which the process ends. 
     In FIG. 4C, a process will be described for the device driver in calculating at each second of the network clock a collision rate for the network to determine if the device driver should enter a collision avoidance mode and wait to transmit the next frame. The process is entered in a step  423  performed by the device driver in which the sum of the transmit collision subcounters is divided by the sum of the transmit complete subcounters and the result compared to the collision threshold. If the collision threshold is greater than the results of the division, a “yes” condition initiates a “collision avoidance mode off” condition for the device driver in a step  425 . If the collision threshold is less than the results of the division, a “no” condition initiates a “collision avoidance mode on” condition for the device driver in a step  427 . After determination of the collision avoidance mode for the device driver, the oldest count is cleared from the transmit complete and transmit collision counters in a step  429 , after which the process ends. 
     Summarizing, a device driver performs transmit chaining in an ethernet in either a half or full-duplex mode without testing the network to determine which mode exists. When the network is in a half-duplex mode and collisions occur which exceed a collision threshold, the node enters a collision avoidance mode which minimizes the probability of a capture effect from occurring on the network. When in a collision avoidance mode, the device driver stores frames in a device driver buffer, otherwise the device driver performs transmit chaining which improves latency and throughput on the network. Stated another way, the device driver is dynamically tuned to the network for transmit chaining according to a comparison of an assigned or dynamically calculated collision threshold to the ratio of a transmit complete counter and a transmit collision counter. 
     While the invention has been described with respect to a specific embodiment it is apparent that various changes and modifications may be to the embodiment without departing from the spirit and scope of the invention as described in the appended claims.