Abstract:
A method and apparatus of reorganizing cells received over data communication lines at a receive node is provided. The cells have an initial order identified by monotonically increasing sequence identifiers. The receive node has buffers associated with respective ones of the communication lines. Each of the buffers has an output position. A cell having a smallest sequence identifier is detected from one or more cells at the output positions of the buffers. It is determined if the smallest sequence identifier is sequentially consecutive to a specified sequence identifier. If the smallest sequence identifier is sequentially consecutive to the specified sequence identifier, the cell having the smallest sequence identifier is dequeued from an output position of one of the buffers and the specified sequence identifier is redefined as the smallest sequence identifier.

Description:
FIELD OF THE INVENTION  
       [0001]     The present invention relates generally to communication systems, and more particularly to techniques for reorganizing cells received over a set of bundled data communication lines at a receive node.  
       BACKGROUND OF THE INVENTION  
       [0002]     Asymmetric digital subscriber line (ADSL) connections use standard phone lines to deliver high speed data communications by utilizing a portion of a phone line&#39;s bandwidth that is not utilized by voice. This utilization allows for simultaneous voice and data transmission. The data transmission over an ADSL connection is continuously available, and ADSL technology helps to bring full-motion video, telecommuting and high-speed Internet access to a home or business. The line is termed “asymmetric” because it uses most of the channel to transmit downstream to the user, and only a small portion of the channel to receive upstream information from the user. A typical ADSL connection may deliver upstream at speeds of approximately 16-768 kilobytes per second (kbps) and downstream at speeds of approximately 1.5-10 megabytes per second (Mbps).  
         [0003]     Since the origin of ADSL, improvements have been made in the technology in areas such as efficiency, affordability and functionality, resulting in the adoption of new standards. ADSL2 standards, completed and approved by the International Telecommunications Union (ITU) in 2002, supersede existing ADSL standards. Additionally, ADSL2+, approved by the ITU in January 2003, doubles the downstream bandwidth of ADSL2 to as much as approximately 25 Mbps.  
         [0004]     Loop bonding technology provides the telecommunications industry with a revolutionary technique for combining multiple data communication lines, such as ADSL2 and ADSL2+ connections, together into a single, aggregated connection. This combination is possible even when multiple connections have different data rate capacities. In January 2005, the ITU passed the G.998.1 (G.Bond-ATM) standard. G.Bond-ATM enables ADSL equipment to electronically bond together ADSL2 or ADSL2+ links using multiple copper phone lines. These bonded links may be utilized to dramatically increase the bandwidth provisioned to subscribers, via a single asynchronous transmission mode (ATM) data stream, to approximately 45 Mbps. These ultra-high data rates support advanced services such as broadcast video and video on demand for customers otherwise out of reach because of their distance from the central office or digital loop carrier (DLC). Even multiple streams of high-definition television can be supported using bonded ADSL2+. The bonding, or other type of bundling, may be automated using software.  
         [0005]     Disparate data rates may be supported among the bundled lines, for example, up to a ratio of 4:1. Thus, if some lines have lower capacity than others, it is not necessary to reduce the data rates of the other lines.  
         [0006]     However, along with the benefits resulting from the ability to bundle and support disparate data rates among the set of bundled data communication lines come several disadvantages. Cells are assigned to lines in an order in accordance with their associated sequence identifiers (SIDs). However, the SID difference between simultaneously transmitted cells on different ADSL connections may increase due to the different data transmission speeds of the different lines. Buffers in a transmit node, corresponding to the ADSLs, that accept multiple cells and operate using a simple round robin cell assignment technique, may result in large SID differences. This is due to the fact that buffers associated with slow data communication lines may not be restricted from accepting cells with consecutively numbered SIDs.  
         [0007]     A reorganization procedure at a receive node is required because ATM cells are received in a different sequence than that in which they were assigned to the lines, due to the differing line speeds. Thus, those cells arriving before their proper placement in the sequence, based on their SID, are buffered in a memory until the proper position in the sequence is reached. The reorganization procedure awaits the longest delayed cell that is out of order. Previous reorganization techniques implemented many operations and multiple tables to track the status of every cell in the buffers of the receive node, which resulted in complicated or unreliable recoveries from line errors.  
         [0008]     Accordingly, what is needed is an improved approach to reorganizing buffered cells at a receive node, which were received over a set of bundled data communication lines.  
       SUMMARY OF THE INVENTION  
       [0009]     The present invention in an illustrative embodiment provides techniques for reorganizing received cells in accordance with SIDs at a receive node of a set of bundled data communication lines.  
         [0010]     In accordance with one aspect of the invention, a method of reorganizing cells received over data communication lines at a receive node is provided. The cells have an initial order identified by monotonically increasing sequence identifiers. The receive node has buffers associated with respective ones of the communication lines. Each of the buffers has an output position. A cell having a smallest sequence identifier is detected from one or more cells at the output positions of the buffers. It is determined if the smallest sequence identifier is sequentially consecutive to a specified sequence identifier. If the smallest sequence identifier is sequentially consecutive to the specified sequence identifier, the cell having the smallest sequence identifier is dequeued from an output position of one of the buffers and the specified sequence identifier is redefined as the smallest sequence identifier.  
         [0011]     In an illustrative embodiment, before determining if the smallest sequence identifier is sequentially consecutive to a specified sequence identifier, a timeout counter is initialized. When at least one of the timeout counter has timed out and at least one buffer has reached a fullness threshold, the cell with the smallest sequence identifier is dequeued from an output position of one of the buffers and the specified sequence identifier is redefined as the smallest sequence identifier.  
         [0012]     In an additional embodiment, when the smallest sequence identifier is not sequentially consecutive to a specified sequence identifier it is determined if the smallest sequence identifier is less than the specified sequence identifier. If the smallest sequence identifier is less than the specified sequence identifier, the queued cell with the smallest sequence identifier is discarded. If the smallest sequence identifier is not less than the specified sequence identifier and at least one buffer is empty, a cell having a sequence identifier sequentially consecutive to the specified sequence identifier is awaited. If the smallest sequence identifier is greater than the specified sequence identifier value and at least one buffer is not empty, the cell with the smallest sequence identifier is dequeued and the specified sequence identifier value is redefined as the value of the smallest sequence identifier.  
         [0013]     Advantageously, the present invention in the illustrative embodiments provides a faster, more efficient and less expensive cell reorganization implementation. This implementation allows for robust recovery from transmission errors, timing out and buffer fullness thresholds, through utilization of FIFO buffers that do not require visibility of every cell location. Only those cells at the output ports of the FIFO buffers are considered by the methodology, which simplifies logic and memory storage requirements. The embodiments of the present invention also reduce the overall expense of G.Bond equipment by reducing the buffer size necessary for reorganization at a receive node. More specifically, the present invention allows for implementation of a reorganization engine, for example, in a low cost field programmable gate array (FPGA). 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0014]      FIG. 1  is a block diagram illustrating a set of bundled data communication lines at a transmit node, according to an embodiment of the present invention;  
         [0015]      FIG. 2  is a block diagram illustrating a set of bundled data communication lines at a receive node, according to an embodiment of the present invention;  
         [0016]      FIG. 3  is a flow diagram illustrating a received cell reorganization methodology, according to an embodiment of the present invention;  
         [0017]      FIG. 4  is a flow diagram illustrating an event driven smallest queued SID determination methodology, according to an embodiment of the present invention; and  
         [0018]      FIG. 5  is a flow diagram illustrating a polling driven smallest queued SID determination methodology, according to an embodiment of the present invention.  
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0019]     The invention will be illustrated herein in conjunction with exemplary communication systems comprising one or more bidirectional data communication lines. It should be understood, however, that the invention is more generally applicable to any system comprising two or more data communication lines in which it is desirable to reorganize received cells or packets in accordance with assigned SIDs in a receive node of the communication system.  
         [0020]     Referring initially to  FIG. 1 , a block diagram illustrates a set of bundled data communication lines  102  at a transmit node  104 , according to an embodiment of the present invention. A data stream  106  is received at transmit node  104 . Data stream  106  is broken up into multiple data cells  108  by a processor  110  of transmit node  104  and labeled with sequence identifiers (SIDs). Data cells  108  are fed into a scheduler  112  of transmit node  104 . In accordance with the embodiments of the present invention, data cells  108  are provided as a result of a fixed size packet application, for example, an ATM data cell of an ATM data stream. Scheduler  112  assigns data cells  108  to buffers  114 . Each buffer  114  is associated with an individual bundled data communication line  116  in set of bundled data communication lines  102 . Bundled data communication lines  102  may incorporate any bundled parallel data communication lines, including those having differing data transmission speeds, for example, ADSL, ADSL2, ADSL2+ or very high bit-rate digital subscriber line (VDSL).  
         [0021]     Referring now to  FIG. 2 , a block diagram illustrates a set of bundled data communication lines  102  at a receive node  204 , according to an embodiment of the present invention. The data cells of  FIG. 1  are transmitted to receive node  204  via bundled data communication lines  102 . Each individual bundled data communication line  116  is associated with a buffer  214  of receive node  204 , for reception and storage of the received cells before reorganization into sequential order according to the cells&#39; SIDs. In a preferred embodiment of the present invention, buffers  214  are first-in first-out (FIFO) buffers, each having an output position where the next cell to be dequeued is situated. A smallest SID of those queued cells at output ports of the buffers  214  is referred to herein as SQSID. A SID of a last dequeued cell from an output position of a buffer  214  is referred to herein as DSID. In accordance with the embodiments of the present invention, a processor  210  determines the proper order to dequeue received cells from buffers  214  through an examination of the output ports, SQSID and DSID in order to reorganize the received cells and form a data stream  206 .  
         [0022]     A flow diagram of  FIG. 3  illustrates a received cell reorganization methodology, according to an embodiment of the present invention. This methodology takes place at the receive node of the communication system after one or more cells have been transmitted and/or received out of order, as evidenced by their respective SIDs, due to the differing transmission speeds of the bundled data communication lines. The methodology begins in block  302 . In block  304 , DSID, representing a SID of a last dequeued cell, is initialized by setting it equal to a series of 1&#39;s, 0xfff . . . ff, or mathematically written as 2 EXP (MAX SID BITS-1), where MAX SID BITS is the number of bits used to represent the SID. For example, if a SID is represented by 16 bits, the initial value is FFFF hex.  
         [0023]     Further, in block  304 , a timeout counter is initialized. The timeout counter is loaded with a value of TA 0 , which corresponds to the maximum amount of time the system can afford to wait for a cell having a SID subsequent to DSID. This maximum amount of time is based on internal storage of the FIFO buffers in the receive node and latency specifications. It is recommended that this time be computed in relation to the maximum delay variation between any two cells sent on different transmission channels at a given point in time. TA 0  may also be dynamically updated based on system status, such as FIFO buffer loads and timeout event profiles.  
         [0024]     In block  306 , it is determined if the FIFO buffers of the receive node are empty. More specifically, it is determined whether the system has received any cells. If a cell has not been received and the FIFO buffers are empty, the methodology will return to block  306 . Thus, the reorganization methodology will not proceed until at least one cell is received at the receive node.  
         [0025]     If a cell has been received and the FIFO buffers are not empty, the methodology proceeds to block  308 , where it is determined whether any of the FIFO buffers in the receive node have reached a fullness threshold of received cells, or whether a timeout event relating to the timeout counter has occurred. Block  308  allows the methodology to execute specific steps dependent on system wait time and queue status.  
         [0026]     The fullness threshold of the FIFO buffers may be determined and set based on a function of the communication line transmission speed, as well as communication line latency and random delay. As described above, in this embodiment of the present invention, the timeout counter is considered fixed at TA 0 , however, in alternative embodiments of the present invention, the timeout counter number may be dynamically altered.  
         [0027]     If either of the events of block  308  is determined to have occurred, the cell having a SID subsequent to DSID in the sequence is considered lost in block  310 . In block  312 , the timeout counter is reset to TA 1 , which, in a preferred embodiment, is a considerably shorter amount of time than TA 0 . This is due to the fact that the timeout counter has either already timed out or is likely to be near timing out due to the existence of a full FIFO buffer. The setting of TA 1  allows for a shorter amount of time for consequent cells to be received, which is less likely to result in an overflow of the FIFO buffers. In a preferred embodiment of the present invention TA 1  is set equal to the slowest line intercell arrival time.  
         [0028]     In block  314 , the methodology continues by dequeuing a queued cell from an output position of one of the FIFO buffers having the smallest SID (SQSID) and in block  316 , DSID is updated and set equal to the value of SQSID. The methodology then returns to block  306 .  
         [0029]     If either of the events of block  308  is determined to not have occurred, it is then determined in block  318  if SQSID succeeds DSID in the sequence, by determining if SQSID=DSID+1. If SQSID succeeds DSID in the sequence, the timeout counter is reset to TA 0  in block  220 , and the methodology continues in blocks  314  and  316 , dequeuing SQSID as described above.  
         [0030]     If the current SQSID does not succeed DSID in the sequence, it is determined in block  322  whether SQSID is less than DSID. If SQSID is less than DSID, then the cell associated with SQSID is discarded by dequeuing it into a virtual trash bin in block  324 . This cell is discarded because a smaller SID indicates that either the cell associated with DSID was incorrectly inserted or the cell associated with SQSID is excessively delayed. The methodology then returns to block  306 .  
         [0031]     If it is determined that SQSID is not less than DSID in block  322 , the methodology determines if any empty FIFO buffers exist in block  326 . The fact that SQSID is not subsequent to DSID and is not less than DSID likely indicates that SQSID is further in the sequence than the SID subsequent to DSID. Thus, an empty FIFO buffer would allow a chance for a new cell to be received at an output position of a FIFO buffer that provides a new SQSID, which is subsequent to DSID. When an empty FIFO buffer exists, the methodology returns to block  306 .  
         [0032]     When an empty FIFO buffer does not exist, it is determined if SQSID=DSID in block  330 , in order to test whether SQSID was updated since a last dequeuing action. When SQSID equals DSID, the SQSID was not yet updated by a parallel SQSID determination process, described in further detail below with regard to  FIGS. 3 and 4 . The methodology returns to block  306  to allow more time for the SQSID update. When SQSID does not equal DSID, the methodology labels the cell having the SID subsequent to DSID as lost and the methodology continues at block  310 .  
         [0033]     Additional mechanisms may also be implemented to take into account situations in which a communication line of the bundle is down and removed from the bundle. For example, this may be assumed when no cells are received for two consecutive timeouts. The management layer may consider any change in the empty status of a down link and reintegrate it in the bundle once it is ready to run within parameters.  
         [0034]     Referring now to  FIG. 4 , a flow diagram illustrates an event driven SQSID determination methodology, according to an embodiment of the present invention. This methodology is performed in order to determine SQSID, or the smallest SID of those cells at the output ports of the FIFO buffers in the receive node. The methodology begins in block  402 . In block  404  SQSID is initialized. The initial value of SQSID is provided as a series of 1&#39;s or mathematically written as 2 EXP (MAX SID BITS-1), where max SID bits is the number of bits used to represent the SID. This is due to increased probability that next expected SID+1 is a series of 0&#39;s (0h) so the methodology would be forced into a wait state until the SQSID is updated by an arriving cell. This is similar to the technique utilized for the initialization of DSID in  FIG. 3 .  
         [0035]     In block  406 , it is determined if there is a new cell at an output position of one of the FIFO buffers. A new cell may be at the output position of a FIFO buffer when a formerly empty FIFO buffer receives a transmitted cell or when a cell has been dequeued from the output position of a FIFO buffer having multiple cells. More specifically, a new Invalid FE (FIFO empty) signal indicates that an output position of a FIFO buffer has received at least some or all of a new cell&#39;s data. The FE threshold level may be specified accordingly. In a preferred embodiment of the present invention, the system is designed so that a premature deactivation of this FE signal during a cell transfer does not cause starvation at the dequeuing end of the FIFO.  
         [0036]     If it is determined that there is not a new cell at the output position of a FIFO buffer, the methodology repeats at block  406  until a new cell is found. If it is determined that there is a new cell at an output position of a FIFO buffer, it is determined if the SID of the new cell is less than SQSID in block  408 . If the SID of the new cell is not less than SQSID, the methodology returns to block  406  to await a next new cell. If the SID of the new cell is less than the SQSID, SQSID is set equal to the SID of the new cell in block  410 , and the methodology returns to block  406  to await a next new cell.  
         [0037]     A flow diagram in  FIG. 5  illustrates an alternative polling driven SQSID determination methodology, according to an embodiment of the present invention. The methodology begins in block  502 . In block  504 , SQSID is initialized as all 1&#39;s, or 0xfff . . . ff. The same value is assigned to a currently polled queued SID (PQSID). The methodology begins with a single line in the bundle. In block  506 , it is determined if a FIFO buffer associated with the examined line in the bundle is empty. When the FIFO buffer is empty the methodology returns to block  506  to test a FIFO buffer associated with a next line in the bundle until one non-empty FIFO buffer is found. When a next FIFO buffer is not empty, the SID of a cell at the output position of the FIFO buffer is assigned as PSQSID in block  508 . In block  510 , it is determined if PSQSID is less than SQSID. If PSQSID is less than SQSID, SQSID is set equal to PSQSID in block  512 , and the methodology returns to block  506 . If PSQSID is not less than SQSID, the methodology simply returns to block  506  without updating SQSID value.  
         [0038]     The present invention may be implemented in the form of one or more integrated circuits. For example, a given system node in accordance with the invention may be implemented as one or more integrated circuits comprising at least one processor and at least one memory. Numerous other configurations are possible.  
         [0039]     In such an integrated circuit implementation, a plurality of identical die are typically formed in a repeated pattern on a surface of a semiconductor wafer. Each die includes a device described herein, and may include other structures or circuits. The individual die are cut or diced from the wafer, then packaged as an integrated circuit. One skilled in the art would know how to dice wafers and package die to produce integrated circuits. Integrated circuits so manufactured are considered part of this invention.  
         [0040]     Although illustrative embodiments of the present invention have been described herein with reference to the accompanying drawings, it is to be understood that the invention is not limited to those precise embodiments, and that various other changes and modifications may be made by one skilled in the art without departing from the scope or spirit of the invention. It is also possible to be implemented as a Software program of any other logical method to process information.