Abstract:
A method, apparatus, and system are provided for multi-link extensions and bundle skew management. According to one embodiment, multiple parallel links between a central processing unit (CPU) and a peripheral device are combined into a single channel, and cells on the various links are received in a round-robin order, and variations in flight time between the various links are compensated through a timer at each receive port of the bundle.

Description:
RELATED APPLICATIONS 
     This is a Continuation Application of a prior U.S. application Ser. No. 09/470,189, filed Dec. 22, 1999 now U.S. Pat. No. 6,646,991. 
    
    
     FIELD OF THE INVENTION 
     This invention relates to network server input/output (I/O) architecture and in particular, to aggregating bandwidth between a network server&#39;s central processing unit (CPU) and its I/O system by bundling multiple physical links. 
     BACKGROUND OF THE INVENTION 
     The Next Generation Input/Output (NGIO) architecture, as described in  Next Generation I/O Link Architecture Specification: Link Specification  published Mar. 26, 1999, is a channel-oriented, switched fabric, serial point-to-point link architecture aimed at meeting the growing needs of I/O reliability, scalability and performance on servers. NGIO introduces the use of an extremely efficient engine that is directly coupled to host memory which replaces shared buses with a fabric of switchable point-to-point links. This approach decouples the CPU from the I/O subsystem, as opposed to today&#39;s load/store memory-mapped I/O, and addresses the problems of reliability, scalability, modular packaging, performance and complexity. CPU communication with peripherals occurs asynchronously with the I/O channel engine being responsible for moving data to and from main memory and allowing the bus to act as a switch with point-to-point links capable of near linear scaling with CPU, memory and peripheral performance improvements. The use of standard, off-the-shelf components, such as the link physicals, also permit this architecture to scale as higher bit rate frequencies become available providing backward compatibility and investment protection. 
     NGIO link architecture provides a method called Multiple Link Expansion (MLX) that aggregates the bandwidth of multiple parallel links to increase bandwidth and reduce latency. MLX allows multiple links to be connected between two devices. These parallel links can be bundled through MLX to work in concert as a single high bandwidth link. 
     During transmission, MLX transmits cells across bundled links. A bundle is made up of an ordered set of links. The transmitter must initiate cells across links of a bundle in a specified, round-robin order. The receiver knows this order and expects the cells to be distributed in that order. 
       FIG. 1  is a block diagram of the prior art showing a normal transmission in round-robin fashion over bundled links. Here, transmitter  100  transmits three packets, A, B, and C. Each packet is segmented into appropriately sized cells. Packet A consisting of two cells (A 1  and A 2 ), packet B consisting of three cells (B 1 , B 2 , and B 3 ), and packet C consisting of a single cell (C 1 ) are then sent from transmitter,  100 , across bundled links connected to ports  104 ,  105 , and  106 . The order of the bundled links has been specified by a fabric manager as  104 ,  105  and  106 . 
     A cell is first dispatched from the port at the top of the round-robin order, here  104 . The next port in the round-robin order,  105 , if staged with a cell, A 2 , may start transmitting that cell after the previous port,  104 , has started to dispatch the previous cell, A 1 . 
     When the round-robin order reaches the last port in the order,  106 , it wraps to the first port in the bundle,  104 . To dispatch a cell, each port must wait until the previous port starts transmitting the previous cell. A port may start transmission at the same time as the previous port but must not transmit any earlier.  FIG. 2  is a block diagram of the prior art showing such a simultaneous transmission. Transmission doesn&#39;t occur until the port satisfies the minimum inter-cell gap requirement. 
     All ports of the bundle must follow this MLX order behavior. If the next port in the round-robin order does not have a cell staged, the round-robin ordering does not advance. 
     The receiver expects cells to arrive in a specified, round-robin order.  FIG. 3  is a block diagram of the prior art showing a typical reception in round-robin fashion over bundled links. Here, packet A consisting of four cells, A 1 -A 4 , is sent to receiver  113  across a four-link bundle consisting of links  108 ,  109 ,  110  and  111 . The reception sequence in the example is port  114 , 115 , 116 , then  117 . Port  114  is currently at the top of the receive round-robin order. All sequence numbers were correctly applied by the transmitter. Each cell follows MLX transmission order from the perspective of the transmitter. 
     Under MLX, cells must be received in the expected round-robin order. Links bundled together under MLX must use the same transmission rate. However, even links with the same transmission rate may have different flight times due to physical characteristics such as length. Therefore, cells may sometimes be received in violation of the ordering requirement. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The appended claims set forth the features of the invention with particularity. The invention, together with its advantages, may be best understood from the following detailed description taken in conjunction with the accompanying drawings of which: 
         FIG. 1  is a block diagram of the prior art showing a normal staggered transmission in round-robin fashion over bundled links; 
         FIG. 2  is a block diagram of the prior art showing a normal simultaneous transmission in round-robin fashion over bundled links; 
         FIG. 3  is a block diagram of the prior art showing a typical reception in round-robin fashion over bundled links; 
         FIG. 4  is a block diagram of one embodiment of the present invention; 
         FIG. 5  is a block diagram of a reception in round-robin fashion over bundled links in which the reception has been skewed but remains valid according to one embodiment of the present invention; 
         FIG. 6  is a block diagram of a reception in round-robin fashion over bundled links in which the reception has been skewed but remains valid according to one embodiment of the present invention; 
         FIG. 7  is a flow diagram of bundle skew management according to one embodiment of the present invention; 
         FIG. 8  is a block diagram of a reception in round-robin fashion over bundled links in which the reception has been excessively skewed resulting in a failure due to a dropped cell according to one embodiment of the present invention; 
         FIG. 9  is a flow diagram of cell synchronization according to one embodiment of the present invention; and 
         FIG. 10  is a flow diagram of link failure processing according to one embodiment of the present invention. 
     
    
    
     DETAILED DESCRIPTION 
     A method and apparatus are described for aggregating bandwidth of multiple parallel links between two devices to increase bandwidth and reduce latency. These parallel links can be bundled to work in concert as a single high bandwidth link. The various links of the bundle are handled in a round-robin order. Variations in flight time between the various links are compensated for through a timer at each receive port of the bundle. 
     In the following description, for the purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the present invention. It will be apparent, however, to one skilled in the art that the present invention may be practiced without some of these specific details. In other instances, well-known structures and devices are shown in block diagram form. 
     The present invention includes various steps, which will be described below. The steps of the present invention may be performed by hardware components or may be embodied in machine-executable instructions, which may be used to cause a general-purpose or special-purpose processor or logic circuits programmed with the instructions to perform the steps. Alternatively, the steps may be performed by a combination of hardware and software. 
     Importantly, while embodiments of the present invention will be described with reference to NGIO and bundled physical links between a network server&#39;s CPU and its I/O system, the method and apparatus described herein are equally applicable to other systems using multiple physical links between devices. 
     One embodiment of the present invention is illustrated in  FIG. 4 . Here, a transmitter  100  and a receiver  113  are shown for ease of explanation. However, it should be realized that transmissions between these two devices can be duplex and therefore each device can act as both a transmitter and receiver as necessary. The transmitter  100  can be a device such as a host channel adapter (HCA) and the receiver  113  can be a device such as a target channel adapter (TCA). 
     The transmitter  100  and the receiver  113  can be connected by several physical links  108 - 111 . These links are connected to the transmitter at ports  104 - 107  and to the receiver at ports  114 - 117 . Links  108 - 111  are bundled together to form one logical channel  112 . Packets to be transmitted across channel  112  are separated into appropriately sized cells by the segmentation controller  102 . These cells are then transmitted from ports  104 - 107  in an appropriate round-robin order determined by the round-robin controller  103 . 
     Cells arriving at the receiver ports  114 - 117  are temporarily stored in the incoming message buffers  118 . The cells are read from the ports in an appropriate round-robin order determined by the round-robin controller  119 . These cells are then recombined into the original packets by the reassembly controller  121 . 
     Links in a bundle may have different flight times. Therefore, cells which are transmitted following MLX ordering behavior may arrive at the receiver in apparent violation of this ordering behavior. In one embodiment of the current invention this skew is compensated for through a timer at each receive port of the bundle. The timer is loaded with time T skew . MLX does not specify the timeout which can be long and conservative since it is not the primary mechanism for detecting lost cells or validating good cells. A longer timeout allows cables of significantly different flight time characteristics, such as different cable lengths, to be successfully bundled. A longer timeout requires deeper buffers and produces some additional latency in servicing good cells in other receive port buffers, but cells will not be lost or mistaken. Preferably, the T skew  value represents the worst-case flight time of the smallest possible cell (e.g., 20 bytes) across the particular physical media. 
     Bundle Skew Management Processing 
     In one embodiment of the current invention when a cell arrives on an unexpected link of a bundle, the receiver continues waiting for a cell to arrive on the expected link for a time interval equal to Tskew. This is called the bundled link skew value. 
     In one embodiment of the current invention illustrated in  FIG. 5 , packet A is a packet consisting of four cells (A 1 -A 4 ) which is sent across four bundled links  108 - 111 . These links are connected to receiver ports  114 - 117 . The round-robin order of the bundled links is receiver port  114 ,  115 ,  116  then  117 . Port  114  is currently at the top of the round-robin order. The transmitter correctly assigns all sequence numbers. Each cell follows the MLX transmission order from the perspective of the transmitter. 
     Unexpected cell arrival can occur on any link, or any number of links. According to embodiments of the present invention, if the arrival occurs before the expiration of the tskew timer for the expected link, the reception is still valid.  FIG. 6  is a block diagram of a reception in round-robin fashion over bundled links in which the reception has been skewed but remains valid according to on embodiment of the present invention. Here, port  114  is at the top of the round-robin order. Cells A 4 , A 3 , and A 2  all arrive before A 1  but the reception is still valid because Al arrived before the expiration of the tskew timer,  120 . A tskew failure occurs when the expected receive port tskew window is exceeded. This failure can only occur in a link which drops a cell. In one embodiment, under conditions of tskew failure, the receiver advances the expected link, round-robin order, to the next link which has already received a cell. 
     This process, according to one embodiment of the present invention, is further described in  FIG. 7 . First, a cell is received  701 . Next, a determination is made as to whether this cell is out of the proper order  702 . This determination is based on whether the cell arrived on the next expected link of the round-robin order. If the cell is out of order, that is, arrived on a link other than the expected link, the receiver will wait for a period up to the value of the tskew timer for the expected link  7 O 3 . If a cell has not yet arrived on the expected link  7 O 4 , that link is removed from the round-robin order  705  and the cell synchronization process can be done. 
     Cell Synchronization Process 
       FIG. 8  is a block diagram of a reception in round-robin fashion over bundled links in which the reception has been excessively skewed resulting in a failure due to a dropped cell according to one embodiment of the present invention. Here, port  114  is currently at the top of the receiver round-robin order. The receiver expects a cell to arrive at port  114 . When the cell (A 2 ) arrives at port  115 , the receiver continues waiting for a cell at port  115  for an additional tskew time window. When the expected cell on port  114  does not arrive, the receiver advances port  115  to the top of the round-robin order, overriding and resetting sequence number and round-robin expectations. 
     In one embodiment of the current invention illustrated in  FIG. 9 , this process is entered when more than a simple cell skip is detected. Basically, detecting skipped cells means that the expected cell doesn&#39;t match the bundle sequence number (BSN)  901  and the next expected cell doesn&#39;t match BSN+1  902 . Current cells in the other port&#39;s buffers should be emptied out in a best effort fashion. In this mode, the lowest BSN cell at the head of a port buffer is always processed first  903 - 904 . When this technique establishes a linear sequence, N times in a row (N=number of links in bundle)  905 - 906  then both transmitter and receiver have re-established synchronization and can go into normal servicing mode. MLX does not specify how to determine the lowest BSN cell. MLX can be a fast parallel process, or a slow serial, scan process. The receiver is expected to use flow control to throttle the transmitter if this process takes a long time. 
     Transmitter Behavior on Failed Link of Bundle 
     In one embodiment of the current invention illustrated in  FIG. 10 , when a transmitter detects that a link of the bundle has failed (link loses sync), the receiver sends a trap to a fabric manager  1001  and removes the failed link from the round robin order. The receiver then continues to handle the other links in the round-robin order  1002 . If the round robin order reaches the failed link  1003  and the link has not resynchronized  1004  the receiver skips the BSN corresponding to the failed link and continues to exclude that link from the round-robin order  1005 . Until the node receives a new bundle configuration or the failed link resynchronizes by itself, the transmitter dispatches all cells, in order, over the remaining functional links. 
     This dispatch differs from normal operation in one aspect. When the transmitter passes the position in the round-robin order held by a failed link, the transmitter skips a BSN corresponding to the skipped position previously held by that link. 
     This behavior guarantees minimal data loss caused by a link failure, and poses minimal disruption to the receive cell synchronization process. 
     Flow Control 
     MLX does not affect link level flow control. If a cell arrives on an unexpected link of a bundle, depending on the offset of the links from expected to unexpected and the depth of its receive buffers, the receiver may choose to flow control the link until the port synchronization event is resolved. 
     Flow control on a link of a bundle may affect other links of the bundle. Assertion by the receiver of flow control on a link of the bundle will affect the transmitted flow behavior on other links of the bundle when the flow-restricted link is at the top of the round-robin order. As long as the previous conditions are met, all bundled links will behave according to the flow control of the most restrictive link. 
     In view of the many possible embodiments to which the principles of our invention may be applied, it will be appreciated that the embodiments and aspects thereof described herein with respect to the drawings/figures are only illustrative and should not be taken as limiting the scope of the invention. To the contrary, the invention as described herein contemplates all such embodiments as may come within the scope of the following claims and equivalents thereof.