Title of Invention

METHOD AND APPARATUS FOR DETERMINING MOST DELAYED FRAME IN A VIRTUAL CONCATENATION GROUP

Abstract

The discloser is related to a method to determine most delayed frame for each VCG within TUs contained in stream comprising multiple multiplexed STM streams comprising acts of: generating a frame update event for each TU at a predetermined point in each frame, storing "frame number" for each VCG, the corresponding VCG that the TU belongs to, and an "age" indication in a memory, implementing state machine to compare the newly received frame number with stored frame number for the current "age" value, updating the stored frame number for each VCG if the newly received frame is less than the stored frame number in a given "age" period and obtaining the stored frame number at the end of the current "age" period as the most-delayed frame for the given "age" period at beginning of next "age" indication. Figure 1

Full Text

FIELD OF INVENTION Virtual Concatenation is technique where data is split across different tributary units (TU's) and tagged with a frame number. As these are carried independently, the TUs experience different delays through the network. At the receiver, there needs to be a mechanism to determine the TU that suffers the longest delay. Only when a frame for this most-delayed TU has been received the data in all the TU's used for interleaving can be read and the original data-stream recovered by the appropriate interleaving of bytes. The present invention describes a method where multiple streams of data of various granularities are processed by a single controller to determine, for each stream, the frame number that can be processed for recovering the stream. BACKGROUND OF THE INVENTION Virtual concatenation is a technique standardized in ITU G.707 standard that describes how a signal can be split across several members and re-combined at the destination. The basis of this is to add a Multi-Frame Indicator (MFI) value for each 125 micro second frame at the source. The MFI is a 12-bit number as defined in the standard and is incremented for each successive frame transmitted. Since each frame is tagged with an MFI reference, at the receiver we can re-align the received frames based on this MFI value and re-constitute the original signal. The re-construction has to wait for all the frames with the same MFI value to arrive. Thus re-construction has to wait for the most-delayed member to be received and so determining which of the constituent members suffered the most delay, and on its arrival, to reconstruct the signal is the basis for the Virtual Concatenation operation. The term Virtual Concatenation Group (VCG) is used to refer to the aggregate signal that is made up using the Virtual Concatenation (VCAT) technique. Each of the members of the VCG is a Tributary Unit (TU). The synchronous Digital Hierarchy (SDH) standard specifies TU's of various granularities (TU11, TU12, TU2, VC3, VC4), each of a different bandwidth. In a given SDH frame, there can be TU's of different granularities and these in turn can be combined to form VCGs of varying bandwidth. This flexibility of partitioning the Bandwidth in small increments leads to very good utilization of the Optical transmission capacity and has led to the adoption of the VCAT technique for transporting several types of signals. In particular, it is popular to use VCGs to transport Ethernet signals across the Wide Area Network (WAN). A carrier may use his SDH network to carry several data streams using VCAT and also carry traditional voice traffic mapped onto the Tributary units. The calculation of the most-delayed member in previous implementation was performed by storing in memory the frame number for each member on a continuous basis. On a periodic basis, or when there was a need to re-compute the most-delayed member, software would disable the updating of the frame-number memory. The result of this was that the frame number in memory reflected the approximate delay of the members. By reading the frame numbers and calculating in software the most-delayed member, implementations of VCAT would program the most-delayed member index into the logic. Then it was a simple matter to use the MFI value of the specified most-delayed member to be the reference for the frames to be re-combined. The SDH standard operates on byte-wide data. As the data-rates increase the time that it takes a byte to be transmitted decreases. This implies that the clock-frequency for the circuit that works on a byte-wide input increases. As an example for a 622Mb/s standardized stream (STM4 in SDH, OC-12 in SONET) we need to operate at 77MHz with byte wide data to be able to handle the stream. At 2.5Gb/s (STM16 or OC-48) the clock frequency is 311MHz. This is considerable speed for technologies like Field Programmable Gate Arrays (FPGAs) to be able to handle. Designers then typically rely on operating multiple designs running at slower speeds that take advantage of the fixed multiplexing that is part of the SDH/SONET standards. Thus we may use 4 separate byte-wide STM4 designs operating in parallel at 77MHz to realize a single STM16 data stream processing. When SW is given the task of updating the Most-delayed Member as the reference for the frame to be read, we are dependent on the SW architecture. In particular, we find that the delay in SW responding to an event can be quite significant in a chassis-based system where there are several cards competing for Software attention. Furthermore, when the design scales to multiple parallel instances, the Most-delayed member Tributary can move from one instance to another. This results in solving the problem of keeping a single most-delayed member definition across the multiple parallel design instances. OBJECTS OF PRESENT INVENTION The main object of the instant invention is to develop a method to determine most-delayed frame in a virtual concatenation group (VCG). Another object of the present invention is to develop said method by determining for each tributary Unit (TU) a frame-number event which happens once per "age" interval which can be SDH frame time of 125 micro-seconds. Another object of the present invention is to develop said method by accumulating data into memory wherein the memory address is function of the TU number, the frame number and page count. Another object of the present invention is to develop said method generating periodic signal to perform read of the accumulated data for all the Tributary Units (TU's) that comprise a Virtual Concatenation Group (VCG). Another main object of the present invention is to develop said method an apparatus to determine most-delayed frame across multiple tributary units (TUs) in a virtual concatenation group (VCG) that serves at the frame-number for which the accumulated data can be read from memory. Another object of the present invention is to develop said method processor for detecting the minimum frame number in the period to determine the most-delayed frame of a TU in a VCG that spans multiple parallel, lower speed, blocks. Another object of the present invention is to develop said method processor that can handle the most-delayed frame computation across multiple VCG's that can have multiple members which can span multiple parallel, lower-speed blocks. STATEMENT OF INVENTION The present invention provides for a method to determine most delayed frame for each VCG within TUs contained in stream comprising multiple multiplexed STM streams comprising acts of: generating a frame update event for each TU at a predetermined point in each frame, storing "frame number" for each VCG, the corresponding VCG that the TU belongs to, and an "age" indication in a memory, implementing state machine to compare the newly received frame number with stored frame number, updating the stored frame number for each VCG if the newly received frame is less than the stored frame number in a given "age" period, and obtaining the stored frame number at the end of the "age" period as the most-delayed frame for the given "age" period at beginning of next "age"; and it is also provides for an apparatus to determine most delayed frame for each VCG within TUs contained in stream comprising multiple multiplexed STM streams comprises: distributed memory for storing state of each VCG and continuously referencing to obtain frame-end event to generate frame event comprising frame number and its "age", a state machine being configured to compare the newly received frame number with stored frame number, wherein the frame number is updated provided newly received frame number is less than the stored frame number in a given "age" period as a subsequent update, and central age timer generator to generate the "age" period for all the STM write blocks. BRIEF DESCRIPTION OF THE DRAWINGS Figure 1 shows a High-Level organization of the VCAT processing Figure 2 shows details of Write Process Block Diagram Figure 3 is an Illustration of the frame-change events Figure 4 shows Most Delayed Logic that tracks the most-delayed frame per VCG Figure 5 shows a configuration with multiple Write Logic blocks providing updates Figure 6 illustrates jitter due to Pointer movement affecting Most-Delayed calculation DETAILED DESCRIPTION OF THE INVENTION The present invention relates to a method to determine most delayed frame for each VCG within TUs contained in stream comprising multiple multiplexed STM streams comprising acts of: a) Generating a frame update event for each TU at a predetermined point in each frame, b) storing "frame number" for each VCG, the corresponding VCG that the TU belongs to, and an "age" indication in a memory, c) implementing state machine to compare the newly received frame number with stored frame number, d) updating the stored frame number for each VCG if the newly received frame is less than the stored frame number for the current "age" value , and e) obtaining the stored frame number at the end of the current "age" period as the most-delayed frame for the given "age" period at beginning of next "age" indication, and f) communicating the most-delayed frame to the read side state machines to allow for the recovery of the data streams by performing the appropriate data interleaving. In one embodiment of the present invention the memory used for storing the state and other information for each TU and VCG is a distributed RAM available in several FPGA devices. In one embodiment of the present invention the most-delayed frame number is forwarded to a read machine for each VCG to ensure that frames earlier than the most-delayed frame are read. In one embodiment of the present invention multiple methods are multiplexed to determine the most-delayed frame over multiple parallel streams of multiplexed STM streams. In one embodiment of the present invention the update events are written into a FIFO using a first clock for each of the multiple parallel streams of multiplexed STM streams. In one embodiment of the present invention the update events are read from the multiple FIFO's using a second clock before comparing the events with the stored frame number for each VCG. In one embodiment of the present invention the period "age" is assigned with unique numbers to avoid ambiguity in comparing the frame updates across multiple interleaved STM streams. In one embodiment of the present invention the period is pre-determined time duration preferably 125us corresponding to an SDH frame. In one embodiment of the present invention the "age" period is being adopted to overcome jitter due to pointer movement. Another main embodiment of the present invention is apparatus to determine most delayed frame for each VCG within TUs contained in stream comprising multiple multiplexed STM streams comprises: a) distributed memory for storing state of each VCG and continuously referencing to obtain frame-end event to update frame number, b) a state machine being configured to compare the newly received frame number with stored frame number, wherein the frame number is updated provided newly received frame number is less than the stored frame number in a given "age" period as a subsequent update, and c) central age timer generator to generate the "age" indication that is used by all the multiple lower-speed write blocks. In one embodiment of the present invention the said apparatus comprises FIFO queue to store the most delayed frame. In one embodiment of the present invention the said apparatus comprises multiplexer for serially reading the FIFO data to determine the most delayed frame for the each VCG within the TUs contained in the multiple STM. In one embodiment of the present invention the multiplexer periodically selects inputs from the FIFO queues. In one embodiment of the present invention the most delayed frame for the given "age" period is determined at beginning of next "age" period. In one embodiment of the present invention the central age timer generator assign unique numbers for distinction of plurality of the "age" periods to avoid ambiguity in comparison of the frame updates. In one embodiment of the present invention the central age timer generator provides selection signal to the multiplexer. The invention described can be scaled from STM4 to STM 16, and can support many VCGs, each of them can be use Higher-Order or Lower-Order Virtual Concatenation. Since an STM 16 signal can be viewed as 4 STM4 signals that have been multiplexed, a byte at a time, we have the ability to replicate the processing for each STM4. In the case of multiple STM4s, the members of a VCG may now be split across several STM4 processing blocks and consequently, we would need to determine the most-delayed member of a VCG across all the STM4 blocks. However, since each of the processing blocks is identical, and it is not known which block will have the most-delayed member for a given VCG, we need to design the logic that each STM4 logic block will, for each VCG, determine when the most-delayed member within that STM4 block has been written, and then we need to combine the information across multiple STM4 blocks to determine the actual most-delayed member for that VCG. Differential Delay Compensation design (DD) is responsible for the proper recovery of the transmitted stream after the various members have been subjected to different delays in the network while propagating to the destination. Each 125us SDH frame of a Tributary Unit (TU) is tagged with a frame number at the source and a Sequence Number indicating its position in the interleaving of the members of a Virtually Concatenated Group (VCG). Figure 1 shows the broad organization of the HW Most-Delayed Logic. The functional description and the details of the individual blocks are explained below. Rx Telecom Logic 105 This block handles an STM4 worth of traffic. It operates at 77 MHz and byte-wide data path to accomplish all the Telecom Layer related logic. It is clear to a practitioner skilled in the art that this is for illustrative use only and that various combinations of Bandwidth and processing speeds can be used in the design of the telecom logic. This includes the pointer-interpreter, the path-overhead processing (extraction and alarm generation) as well as the VCAT and LCAS related processing. It is responsible for generating interrupts for various changes in alarms and other events that require a response from software. The operation of this block is controlled by configuration that is on a per Tributary Unit (TU). The entire logic is implemented in a TDMized scheme. A central block is responsible for generating the sequence of TU addresses. These are referred to as A-k-l-m numbers and the sequence of these is dependent on the multiplexing structure associated with an STM1. We use the terms A-k-l-m and TUno interchangeably. The data that is received from the Telecom Layer is passed to the Write Logic 102. In order to perform Virtual Concatenation, the data is written to external memory 101 based on the frame number and tributary Index. Write Logic 102 The write logic 102 works on a per STM4 basis and is responsible for accumulating byte-wide data into a page-memory and when a page is complete, generate an external memory access to transfer the accumulated data to external memory 101. The size of the page is determined by the memory technology used and in our implementation we use a 16 byte page. Thus once the state-machine accumulates 16 bytes of data for a TU, it will generate a write request for external memory. The address of the location in external memory 101 is a function of the Tu no, the frameno, and a page-count that is maintained by the state machine in the write-logic. See figure 2. The State Machine of the Write logic works on the incoming frame number. It detects the start of a 2 ms boundary based on a transition of the frame number. The state is itself stored in a Block RAM (due to the large number of possible TU's - 384 in an STM4). On completion of 16 bytes of writing, a "Page Write Request" is generated to transfer that page to external memory 101. Note that it is likely, though not necessary, that the memory sub-system is working off a different clock frequency. The state information for each TU consists of the following information. Most Delayed Logic 103 Also, when the write machine receives data, it compares the incoming frame-number with the frame number stored in its state memory. When a change occurs, it indicates that the corresponding TU has a frame completed, and an "update request" event is generated that records the VCG number, the frame number, and the TU number. By generating at the updaterequest event at the transition of a frame-number we are guaranteed that the data for the previous frame is written in external memory. The problem is how to determine, form these events that encompass several TU's and multiple STM4 write blocks, what frame number corresponding to each VCGg should be read. Figure 3 illustrates the problem. Each TU generates an event at an approximate interval of 125 micro seconds. Note, that due to the pointer movements that are part of the SDH standard, the distance between two successive frame-change events for a given TU is not guaranteed to be 125 micro seconds. Thus while in most cases there is 1 update event for each TU in a frame time, it is also possible to have 125 us intervals where there are 2 updates and some frames where there is no update event. This will have to be addressed in the design. The end-of-frame updates received from the write side from the multiple TU's belonging to multiple VCG's spanning across multiple STM4's need to be compared to determine up till what frame-number value can the reconstruction logic read frames from external memory. Essentially, the most-delayed member has the least frame number and that is where the reads must proceed till. Subsequent reads are stalled till we receive an update informing us that more data has been written to external memory and we can proceed with reading further. Since the end-of-frame events are periodic and their relation to one another is arbitrary, we need to group of events in a 125us interval and determine the appropriate frame number (also called an Multi-Frame Indication or MFI value in the G.707 standard) to update the read logic with it. We can generate a periodic signal called the "age" and for all events that are generated in a particular value of the "age" signals will be logically associated as a group for purposes of finding the minimum MFI value, which is a property of the most-delayed member. The events generated by the write-logic on detecting a change in the frame number in a particular value of the "age" signal form a logical set of events. Note, as explained in Figure 2 earlier, the association of "age" and the frame-end event is not exact since the timing of each TU can vary within the SDH frame (as the frequency reference of the source and the sink may not be exactly the same). To track all the events for multiple VCGs we implement a state machine with distributed RAM. The state for each VCG is stored in memory, and is referenced each time we get a frame-end event from the write-logic. See figure 4. For the first update we load the updated frame number in RAM, and on every subsequent update in the same "age" time period, we look at the frame number being signaled and if it is smaller we update the state replacing the cur_frm value with the updatefrm value. Thus at the end of the "age" period, we have the most-delayed update received in that 125us, At the first update of the next value of "age", this is signaled to the Read Logic to determine the MFI value for which reads can progress to. Thus the read side normally gets the update with the first event for that VCG of each "age" setting. It is important to understand that there is certain ambiguity in the frame number indicated to the read side. This arises from the fact that during some 125us period, the most-delayed TU may not signal an event on account of the pointer movement, thereby an incorrect frame-number (less delayed member) will be notified to the read side. Of-course, in the next period, the most-delayed frame will be indicated. It is therefore recommended that the read-side allow for this ambiguity when it is communicated the frame number. Since, typical implementations of VCAT have a read memory bandwidth slightly greater than the write memory bandwidth (to allow for the delay buffer to be drained when a most-delayed member is deleted), one technique is to read one or two less frames than indicated by the minimum in every period. When the Virtual Concatenation is implemented across multiple STM4 design blocks working in parallel, each unit is only capable of generating the update events for the TU's that are contained in that STM4 block. In order to compute, for a given VCG spanning multiple STM blocks, the most-delayed member we need to process all 4 of them simultaneously. See figure 5. We realize that the updates from the Write-logic for each STM4 are independent and hence in a given cycle we could have multiple updates for one or more VCGs. This would normally require a number of separate machines, one for each VCG, to track the events that each of the STM4's generate. This replication increases the logic required manifold. Note that in the case of STM4 worth of Tributaries, the maximum number of TU's that can be present is 384. If we use VC4 mapping, then only 4 updates are required. The actual number of updates is a function of the multiplexing scheme and the elements provisioned to carry VCAT traffic. Moreover, within the TU's that are provisioned, the membership within various VCGs is arbitrary. In the case pointer-movements are present in the incoming signal, the time between the successive frame-end events occasionally is less-than or more-than the frame time. As a result, it is possible for two successive frame-end events to be generated with the same value of the "age" signal and causing error in determining the frame number for the read logic. This is illustrated in the following example with figure 6. In the example shown in figure 6, when the Most-delayed frame number jumps to 151 after 141, the read logic is free to read fames in between. There may be a situation where for TU1, in the example, data has not been written to external memory. Note However, that the error will be recovered from in the next frame time and as a result, we need to ensure that the read-logic does not exceed the frame that has been written. Since the Bandwidth of the Read Logic typically exceeds the bandwidth of the write-logic by a small amount, we can subtract from the actual Most-delayed computation, a constant difference, which ensures that the read-logic does not go past the write side frame numbers.Rather than processing all the events as they are generated, which requires us to evaluate multiple update request in the same cycle with complex and replicated logic, we propose to simplify the implementation by realizing that an accurate computation of frame time can be avoided if we are willing to settle for some additional delay, which is anyways required to compensate for the jitter due to pointer movements. With this realization we can simplify the design and use a single stream of updates across all the STM4 logic blocks. Figure 7 illustrates an example. There is a central controller 702 that generates an "age" signal and this is input to each of the per-STM4 Write Logic Blocks 501, 502, 503 and 504 as well as a selection signal, named "stm4_sel", that gives each STM4 the opportunity to present its update to the most-delayed logic 704. When the updates are generated, they are tagged with the "age" at which they are generated and then stored into a First-ln First-Out (FIFO) structure for each of the STM4 blocks. 701 shows a FIFO structure for the STM4 write logic 501. Then based on the "stm4_sel" signal being valid, the FIFO for the relevant Write Block contributes an event into the interleaved stream of events. Note that the number of events contributed by each STM4 is a function of its multiplexing configuration and the provisioning of members to VCGs. The time at which these events are introduced into the interleaved event stream is a function of the network delays of the tributary units. The resulting structure is shown in the figure 7. It is often the case that the Telecom Logic, that runs in lock-step with the Cross Connect clock, and the memory system run at different frequencies. The FIFO also allows the clock-domain crossing structure required in this case Due to the interleaving and the pointer movements, it is possible that the updates arrive at the Most Delayed block in out-of-order. We rely on the change in the "age" value received to determine that a frame-time has elapsed. However, the interleaving can result in frame updates from a later value of "age" to be inserted between updates from a previous value of the "age" signal. As a result, we do not want to re-start the loading of the frame-time into the curfram value when this happens. We handle this case by ensuring that the "age" signal is a multiple-bit signal so that it is easy to distinguish this case. On an update request with a different "age" indication from the previous, we ignore the events that belong to the previous frame. Only on a change in framtime for the next period, we indicate the frame-time from the previous frame-time interval to the read-side (with the appropriate difference to account for the jitter). Subsequent, older updates can then be used in the computation of the most-delayed but it does not trigger the notification to the read side. Further this invention can easily be scaled to OC-192 design as well and a large number of streams. Retaining the structure of parallel blocks working at 77 MHz or 155MHz we will be able to determine the most-delayed member across multiple write blocks and the time to advance the read machine for each stream. Furthermore, since the logic is shared and only the current multi-frame indicator is used on a per stream basis, this design can be called to support arbitrary number of streams. We claim: 1. A method to determine most delayed frame for each VCG within TUs contained in stream comprising multiple multiplexed STM streams comprising acts of: a) generating a frame update event for each TU at a predetermined point in each frame, b) storing "frame number" for each VCG, the corresponding VCG that the TU belongs to, and an "age" indication in a memory, c) implementing state machine to compare the newly received frame number with stored frame number, d) updating the stored frame number for each VCG if the newly received frame is less than the stored frame number in a given "age" period ,and e) obtaining the stored frame number at the end of the "age" period as the most-delayed frame for the given "age" period at beginning of next "age". 2. The method as claimed in claim 1, wherein the memory is a distributed RAM. 3. The method as claimed in claim 1, wherein the most-delayed frame number is forwarded to a read machine for each VCG to ensure that frames earlier than the most-delayed frame are read by data interleaving. 4. The method as claimed in claim 3, wherein multiple methods are multiplexed to determine the most-delayed frame over multiple parallel streams of multiplexed STM streams. 5. The method as claimed in claim 3, wherein the read machine reads one or two less frames than indicated by the most-delayed frame in each period. 6. The method as claimed in claim 1, wherein the update events are written into a FIFO using a first clock for each of the multiple parallel streams of multiplexed STM streams. 7. The method as claimed in claim 6, wherein the update events are read using a second clock before comparing the events with the stored frame number. 8. The method as claimed in claim 1, wherein the period "age" is assigned with unique numbers to avoid ambiguity in comparing the frame updates across multiple interleaved STM streams. 9. The method as claimed in claim 1, wherein the period is pre-determined time duration preferably 125u,s corresponding to an SDH frame. 10. The method as claimed in claim 1, wherein the "age" counter is being adopted to overcome jitter due to pointer movement. 11. An apparatus to determine most delayed frame for each VCG within TUs contained in stream comprising multiple multiplexed STM streams comprises: a) distributed memory for storing state of each VCG and continuously referencing to obtain frame-end event to generate frame event comprising frame number and its "age", b) a state machine being configured to compare the newly received frame number with stored frame number, wherein the frame number is updated provided newly received frame number is less than the stored frame number in a given "age" period as a subsequent update, and c) central age timer generator to generate the "age" period for all the STM write blocks. 12. The apparatus as claimed in claim 11 comprises FIFO queue to store the update events. 13. The apparatus as claimed in claim 11 comprises multiplexer for serially reading the FIFO data to determine the most delayed frame for the each VCG within the TUs contained in the multiple STM. 14. The apparatus as claimed in claim 13, wherein the multiplexer periodically selects inputs from one of the FIFO queue. 15. The apparatus as claimed in claim 11, wherein the most delayed frame for the given "age" period is determined at beginning of next "age" period. 16. The apparatus as claimed in claim 11, wherein the central age timer generator assign unique numbers for distinction of plurality of the "age" periods to avoid ambiguity in comparison of the frame updates. 17. The method and apparatus to determine most delayed frame for each VCG within TUs contained in stream comprising multiple multiplexed STM streams as herein substantiated in the description along with accompanied drawings.

Documents:

0101-che-2008 abstract.pdf

0101-che-2008 claims.pdf

0101-che-2008 correspondence-others.pdf

0101-che-2008 description (complete).pdf

0101-che-2008 drawings.pdf

0101-che-2008 form-1.pdf

0101-che-2008 form-18.pdf

0101-che-2008 form-2.pdf

0101-che-2008 form-3.pdf

0101-che-2008 form-5.pdf

101-CHE-2008 FORM-1 01-08-2012.pdf

101-CHE-2008 FORM-13 01-08-2012.pdf

101-CHE-2008 CORRESPONDENCE OTHERS 01-08-2012.pdf

101-CHE-2008 AMENDED CLAIMS 05-12-2014.pdf

101-CHE-2008 AMENDED PAGES OF SPECIFICATION 05-12-2014.pdf

101-che-2008 correspondence others.pdf

101-CHE-2008 EXAMINATION REPORT REPLY RECEIVED 05-12-2014.pdf

101-CHE-2008 FORM-1 05-12-2014.pdf

101-che-2008 form-13.pdf

101-CHE-2008 FORM-3 05-12-2014.pdf

101-CHE-2008 FORM-5 05-12-2014.pdf

101-CHE-2008 POWER OF ATTORNEY 05-12-2014.pdf

101-che-2008 others.pdf

101-che-2008-correspondnece-others.pdf

101-che-2008-description(provisional).pdf

101-che-2008-drawings.pdf

101-che-2008-form 1.pdf

101-che-2008-form 3.pdf

101-che-2008-form 5.pdf

Abstract.pdf

abstract101-CHE-2008.jpg

Amended claims.pdf

Complete Specification.pdf

Correspondence.pdf

FER_REPLY along with all enclosures.pdf

Other documents.pdf

Petition_137.pdf